[Python] Aiuto per testi su machine learning e graph clustering

Gio 31 Maggio 2012 18:38:40 CEST

2012/5/23 Antonio Piepoli <piepoli.antonio a gmail.com>:

> Ulteriorie premessa... la mail è lunghetta e mi scuso di questo ... ma sono
> davvero in difficoltà e spero che qualcuno di voi abbia la gentilezza di
> aiutarmi.

Ci provo...

> Nome,Cognome,Data di nascita, Lavoro, email, città di residenza... in
> generale immaginate qualsiasi cosa sia riconducibile ad una identità
> digitale...
>
> Immaginate adesso di dividere questa tabella in questo modo:
>
> tabella1: Nome, Cognome
> tabella 2: Cognome, Data di nascita
> tabella 3: Data di nascita, lavoro
> etc...
>
> in sostanza la domanda è : partendo da tutte queste tabelle è possibile
> ricostruire la tupla iniziale?
>
> Come avrete notato non sto ragionando in termini di chiavi ... quindi, in
> generale, non posso fare un semplice Join sull'attributo in comune perchè
> per esempio banalmente esistono più persone con lo stesso nome etc ... sto
> considerando anche la possibilità che ci siano errori di battitura tra
> diverse tabelle.
>
> L'idea generale è ottenere un valore numerico di similarità (che poi è a
> tutti gli effetti una probabilità) tra due tuple di due tabelle diverse...
> per esempio

No, fermo: mi costringi a dare una temperatina di...
Sono d'accordo sull'idea generale, ma quella *non* e' una probabilita'.
E', come dici correttamente, un valore numerico di similarita'.

Per passare ad una probabilita' devi lavorarci un pochetto. Mi spiego:
quello e' *evidentissimamente* un priore.
Poi puoi usarlo per calcolare la probabilita' che dato un certo valore
di similarita' hai un match.

Io non sono uno statistico vero, eh. Pero' ti suggerisco di chiarirti
oltre ogni ragionevole dubbio tutte queste sottigliezze, perche' se no
finisce che ti complichi la vita per nulla.

Non ultimo il fatto che evidentemente tu vuoi fare statistica
bayesiana (vedi machine learning) e non statistica classica. E le due
cose sono leggermente diverse...

> Dopo ave re assimilato questo concetto la mia idea è stata quella di creare
> una rete, un grafo, in cui ogni nodo rappresenta una tupla ed ogni arco
> rappresentza il valore di somiglianza tra due tuple che hanno almento un
> attributo in comune (in generale si può pensare a tabelle con + di due
> attributi e quindi il valore di somiglianza deve considerare due attributi).
> Una volta ottenuta questa rete bisognerebbe clusterizzare il grafo in modo
> tale che ogni cluster rappresenti poi una tupla originaria.

Interessante. Sui due piedi non ho idea pero' se possa funzionare, a
meno di non beccare alcuni dettagli delicati.
Il problema e' che "clusterizzare" un grafo e' un problema abbastanza
complesso, nel senso che ci sono ottomilioni di concetti di cluster,
clique, k-plex, e ogni tizio che e' passato per graph theory ha
lasciato qualche algoritmo e qualche definizione e tu devi capire, *in
pratica* quali funzionano per te.

> 1)Come calcolo il valore di verosimiglianza? Risposta: machine learning.
> L'idea sarebbe quella di utilizzare un modello di supervised machine
> learning impostando un problema di classificazione (0 non match ed 1 match).

Io qui sono in pesante difficolta' morale...

> Ho scelto SVM (support vector machine) per la sua semplicità e per l'ottima
> libreria libsvm ma credo che una scelta vale l'altra.
> In sostanza la fase di training corrisponde ad una serie di vettori di
> dimensione pari alla cardinalità della tabella applicando ad ogni attributo
> opportune metriche (Jaro o Edit distance per esempio).
> Quindi il vettore di training ha questa forma
> metrica sul nome, metrica sul cognome, metrica sul lavoro .... classe
> 0.2 ,                        0,                             1
> ,                           0
> etc ...
>
> una volta fatto il training otterò un modello che potro interrogare con un
> vettore di testing ed in uscità avrò la probabilità di appartenzenza a
> ciascuna classe...

Cioe' in pratica la mia difficolta' e' proprio... come accidenti fare
il training set. Mi sembra drammaticamente arbitrario.
Io *non* sono un esperto di machine learning, eh. Ma mi sembra uno di
quei problemi per cui non e' troppo adatta una SVM.

Intanto vorrei capire come sono fatti i dati. Spiego meglio, li mi
mostri una tabella con "pseudo-chiave" cognome.
Ma ovviamente il cognome non e' per nulla una chiave, anche al netto
di errori di battitura e simili. Ci possono essere genuinamente
persone con lo stesso cognome.

In questo caso non ho idea tu come possa andare avanti, a meno che non
hai informazioni ridondanti per cui capisci quali dai appartengono a
chi. E non mi sembra banale.
Probabilmente non ho ben capito il tuo problema.

> 2) per realizzare i cluster... stavo pensando ad algoritmi di tipo community
> detection... pensate sia una cosa sensata? oppure c'è un sistema migliore?
> In pratica quello che mi aspetto è di avere una rete in cui ci saranno nodi
> connessi con archi "pesanti" a nodi della stessa persona e con archi leggeri
> a nodi della stessa tabella ma riferiti ad un'altra persona.

"Quale" algortimo? Non credo che in letteratura si sia giunti ad un
accordo su quale funziona meglio.

Cosi' a sboccio: questa e' la "miglior" risorsa free su complex
network analysis:

http://arxiv.org/abs/cond-mat/0303516

(completezza etc... poi e' diventata un libro di un migliaio di pagine).

Su community detection lui non dice nulla direttamente, ma nel
paragrafo dove ne parla ci sono un po' di link ad articoli utili.

> scusate se la mail è molto lunga... spero che qualcuno mi sappia aiutare
> perchè questo progetto è una cosa che sto faceno praticamente da solo, senza
> l'aiuto del mio supervisore perchè lui non conosce nessuno di questi
> argomenti ( e nemmeno io fino a qualche mese fa :( )

Fico! Deduco quindi che non sei con Aiello molto bravo (che invece
dovrebbe fare queste cose, e' un prof. italiano che sta a Groningen).

-- 
.
..: -enrico-