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

Antonio Piepoli piepoli.antonio a gmail.com
Mer 23 Maggio 2012 20:06:26 CEST


Salve a tutti,

sono Antonio PIepoli, studente universitario, ed attualmente mi trovo in
Olanda per svolgere la mia tesi specialistica.
È da un pò che utilizzo python per tutti i miei progetti, quindi, lo
utilizzerò anche per il mio lavoro di tesi.


Premetto che avrei dovuto creare tre mail con tre differenti oggetti... ma
ho preferito non farlo perchè in questo modo avete un quadro generale del
mio progetto e magari potete darmi un feedback generale :P.

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.


Cerco di spiegarvi in maniera molto generale cosa sto facendo ... poi
passerò alle domande.

Considerate di avere una tabella con questi attributi

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

tupla1 = (Antonio, PIepoli) tupla2= (Antonio,Studente) tupla3 =
(Piepoli,datadinascita)

verosimilmente la somiglianza tra tupla1 e tupla2 dovrebbe essere inferiore
a quella tra tupla1 e tupla3.

Dopo avere 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.

Spero che sia tutto chiaro perchè adesso mi sposterò su dettagli un pò più
tecnici.

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).
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...

la prima domanda che vi pongo è: che modelli dovrei creare? un modello per
ogni attributo o un modello generale ?

per esempio... devo fare il training solo sul nome sul cognome etc ...
separatamente o devo creare un modello per tutta la tabella e quando mi
servirà sapere il valore di verosimiglianza su nome e cognome trattare gli
altri attributi come mancanti?


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.


alla fine ho un pò affrettato le domande... se non sono chiare provo a
riformularle... questa volta magari con difersi oggetti

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 :( )


-
Antonio Piepoli
-------------- parte successiva --------------
Un allegato HTML è stato rimosso...
URL: <http://lists.python.it/pipermail/python/attachments/20120523/c5fff92d/attachment-0001.html>


Maggiori informazioni sulla lista Python