Home Διπλωματικές Παλιότερα Θέματα Διασύνδεση Εγγραφών με χρήση Τεχνικών Εκμάθησης Μηχανής
Διασύνδεση Εγγραφών με χρήση Τεχνικών Εκμάθησης Μηχανής PDF Εκτύπωση E-mail
Συντάχθηκε απο τον/την Georgios Alexandridis   

Η εκτεταμένη χρήση των υπολογιστικών συστημάτων και των δικτύων στις μέρες μας έχει οδηγήσει στη διάχυση της πληροφορίας σε πολλές επιμέρους αυτόνομες συλλογές δεδομένων. Συνεπώς αποκτά ιδιαίτερο ενδιαφέρον η συσχέτιση των συλλογών δεδομένων αυτών με σκοπό την ανακάλυψη κοινών οντοτήτων που ενυπάρχουν σε αυτές. Η επιστημονική περιοχή που ασχολείται με αυτό το αντικείμενο ονομάζεται Διασύνδεση Εγγραφών (Record Linkage).

Στις περιπτώσεις που οι οντότητες που περιέχονται στις συλλογές δεδομένων έχουν κάποιο μοναδικό χαρακτηριστικό (πχ το πρωτεύον κλειδί σε μια εγγραφή βάσης δεδομένων) τότε μπορούν να εφαρμοστούν ντετερμινιστικοί αλγόριθμοι για την σύνδεση εγγραφών (Deterministic Record Linkage). Αρκετά συχνά όμως τα δεδομένα δεν περιγράφονται από κάποιο τέτοιο μοναδικό χαρακτηριστικό, οπότε η συσχέτιση των εγγραφών γίνεται με μη-ντετερμινιστικό τρόπο. Σε αυτή την περίπτωση, σημαντική συνεισφορά προσφέρει η εργασία του Winkler, ο οποίος παρουσιάζει την Πιθανοτική Σύνδεση Εγγραφών (Probablistic Record Linkage). Η σύγκριση των εγγραφών πραγματοποιείται με την χρήση του διανύσματος σύγκρισης \gamma, το οποίο  ορίζεται αυθαίρετα και έχει  ως συνιστώσες κάποια από τα πεδία των εγγραφών που συγκρίνονται. Για ένα δεδομένο διάνυσμα \gamma, υπολογίζονται οι a posteriori πιθανότητες P(\gamma|M), δηλαδή η πιθανότητα όταν το διάνυσμα \gamma ικανοποιείται οι εγγραφές όντως να ταιριάζουν και P(\gamma|U), δηλαδή η πιθανότητα όταν το διάνυσμα \gamma ικανοποιείται οι εγγραφές να μην ταιριάζουν, στο σύνολο του dataset και από αυτές προκύπτει ο λόγος σύνδεσης R = \frac{P(\gamma|M)}{P(\gamma|U)}.

 

Στη συνέχεια, μπορεί να κατασκευαστεί ένας απλός κανόνας απόφασης (decision rule), ο οποίος τοποθετεί τις συγκρινόμενες εγγραφές σε 3 κατηγορίες, ανάλογα με την τιμή του λόγου σύνδεσης:

1. Ταίριασμα: Αν ο λόγος σύνδεσης είναι πάνω από το κατώφλι ταιριάσματος (match thresold)
2. Μη Ταίριασμα: Αν ο λόγος σύνδεσης είναι χαμηλότερος από το κατώφλι μη-ταιριάσματος (non-match threshold)
3. Πιθανό Ταίριασμα: Αν ο λόγος σύνδεσης βρίσκεται μεταξύ των δύο κατωφλίων


Οι “a posteriori” πιθανότητες P(\gamma|U) και P(\gamma|U) καθώς και τα αντίστοιχα κατώφλια απόφασης και μη-απόφασης μπορούν να προσεγγιστούν με μια σειρά από τεχνικές, όπως πχ οι Expectation-Maximization αλγόριθμοι. Μπορούν όμως να ειδωθούν και ως ένα πρόβλημα ταξινόμισης (classification), όπου το ζητούμενο είναι να κατασκευαστεί ένας ταξινομητής (classifier), ο οποίος θα παρέχει μια εκτίμηση των εν λόγω τιμών.

 

Στην εργασία του Minton, κατασκευάζει έναν ταξινομητής που βασίζεται σε Support Vector Machines. Οι προς σύγκριση εγγραφές απεικονίζονται στην είσοδο του SVM με την χρήση ενός learned distance metric που προτείνει ο συγγραφέας. Το όλο σύστημα εμφανίζει ενθαρρυντικά αποτελέσματα στα datsets στα οποία δοκιμάζεται.

 

Σκοπός αυτής της εργασία είναι:

 

1. Να εξεταστεί η απόδοση της συγκεκριμένης μεθοδολογίας στο δημόαια διαθέσιμο Record Linkage Comparison Dataset (από το UCI Repository) καθώς και σε ένα μη-δημόσια διαθέσιμο dataset που κατέχει το εργαστήριο.

 

2. Να βρεθούν οι αλλαγές που μπορούν να γίνουν στα συστατικά στοιχεία του συστήματος έτσι ώστε τα αποτελέσματα να βελτιωθούν στον καλύτερο δυνατό βαθμό.

 

Attachments:
Download this file (01565694.pdf)Minton05Heterogeneous[Minton, S.N: ]Georgios Alexandridis571 Kb
Download this file (2286061.pdf)Fellengi69Theory[Fellegi, I.P. and A.B. Sunter: A theory for record linkage]Georgios Alexandridis2100 Kb
Download this file (rrs2006-02.pdf)Winkler06Overview[William E. Winkler, “Overview of Record Linkage and Current Research Directions”]Georgios Alexandridis465 Kb
Download this file (WinklerJPSMTlk04.pdf)WinklerJPSMTlk04.pdf[Εισαγωγικές Διαφάνειες από τον William E. Winkler]Georgios Alexandridis198 Kb
 

Powered by Joomla!. Valid XHTML and CSS.