Συσταδοποίηση κειμένων με χρήση της μετρικής Wasserstein και τεχνικές βέλτιστης μεταφοράς
Για τη διερεύνηση ομοιότητας ανάμεσα σε κείμενα υπάρχουν πολλές τεχνικές που χρησιμοποιούν τις συχνότητες εμφάνισης λέξεων και άλλες στατιστικές πληροφορίες που παράγονται από τα μητρώα όρων - κειμένων. Τι γίνεται όμως όταν οι λέξεις εκλαμβάνονται ως οντότητες σε ειδικούς χώρους με ειδικά επιλεγμένε...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2018
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/11702 |
| id |
nemertes-10889-11702 |
|---|---|
| record_format |
dspace |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Συσταδοποίηση Ομοιότητα κειμένων Πρόβλημα βέλτιστης μεταφοράς Ενσωματώσεις Γλώσσα Νευρογλωσσικός προγραμματισμός Clustering Text similarities Wasserstein Optimal transport problem Embeddings Neuro-linguistic programming (NLP) TMG 004.35 |
| spellingShingle |
Συσταδοποίηση Ομοιότητα κειμένων Πρόβλημα βέλτιστης μεταφοράς Ενσωματώσεις Γλώσσα Νευρογλωσσικός προγραμματισμός Clustering Text similarities Wasserstein Optimal transport problem Embeddings Neuro-linguistic programming (NLP) TMG 004.35 Καλογερόπουλος, Διονύσιος Συσταδοποίηση κειμένων με χρήση της μετρικής Wasserstein και τεχνικές βέλτιστης μεταφοράς |
| description |
Για τη διερεύνηση ομοιότητας ανάμεσα σε κείμενα υπάρχουν πολλές τεχνικές που χρησιμοποιούν τις συχνότητες εμφάνισης λέξεων και άλλες στατιστικές πληροφορίες που παράγονται από τα μητρώα όρων - κειμένων. Τι γίνεται όμως όταν οι λέξεις εκλαμβάνονται ως οντότητες σε ειδικούς χώρους με ειδικά επιλεγμένες αποστάσεις ομοιότητας;
Στόχος της παρούσας εργασίας είναι η διερεύνηση τεχνικών μέτρησης υπολογισμού ομοιότητας και ομαδοποίησης κειμένων χρησιμοποιώντας ως μετρική την απόσταση Wasserstein . Ονομάζουμε τη μεθοδολογία αυτή W2EC (Wasserstein by Word Embedding Clustering). Για την εξαγωγή των πληροφοριών (στατιστικών και λεξιλογίου) χρησιμοποιείται η εργαλειοθήκη {\sc TMG} (Text to Matrix Generator).
Κάθε κείμενο εκλαμβάνεται ως μια κατανομή και κάθε στοιχείο της κατανομής ως ένας όρος από ένα λεξικό που έχει μετασχηματιστεί σε διανυσματικό χώρο μέσω ενσωματώσεων λέξεων (word embeddings) όπως word2vec και GloVe .
Το κάθε κείμενο αποτελείται από τους όρους που εμφανίστηκαν σε αυτό και ο έλεγχος ομοιότητας πραγματοποιείται επιλύοντας ένα πρόβλημα βέλτιστης μεταφοράς (optimal transport) \cite{kantorovich} της μιας κατανομής στην άλλη. Η εύρεση της στρατηγικής βέλτιστης μεταφοράς γίνεται είτε με επίλυση προβλήματος γραμμικού προγραμματισμού είτε με ομαλοποίηση του προβλήματος και εφαρμογή του αλγορίθμου Sinkhorn για αμφίπλευρη στοχαστικοποίηση.
%Ένα πρόβλημα που μελετάται είναι η απόδοση ως προς την ταχύτητα της βέλτιστης μεταφοράς καθώς είναι γνωστό ότι πρόκειται για μια διαδικασία με υψηλό υπολογιστικό κόστος και μπορεί να γίνει απαγορευτική καθώς μεγαλώνει ο όγκος των δεδομένων.
Εντέλει, για κάθε κείμενο υπολογίζεται η βέλτιστη μεταφορά του ως προς τα υπόλοιπα κείμενα και δημιουργείται ένα μητρώο με αποστάσεις Wasserstein. Η συσταδοποίηση επιτυγχάνεται βάσει αυτού του μητρώου με γνωστούς φασματικούς αλγόριθμους (kMeans, PDDP κλπ) και γίνεται σύγκριση των αποτελεσμάτων σε σχέση με την συσταδοποίηση που προκύπτει από το μητρώο όρων-κειμένων. Τα δεδομένα που χρησιμοποιήθηκαν αποτελούνται από γνωστές συλλογές κειμένων και η αξιολόγηση των αποτελεσμάτων για κάθε σύνολο δεδομένων γίνεται ως προς την ποιότητα, ταχύτητα αλλά και κλιμακωσιμότητα αυτών. Τα αποτελέσματα που παράγονται μέσω της μεθοδολογίας W2EC εμφανίζουν έντονες σημασιολογικές σχέσεις στα κείμενα που συσταδοποιήθηκαν μαζί και αναδεικνύουν τη χρησιμότητα τη μετρικής Wasserstein. |
| author2 |
Γαλλόπουλος, Ευστράτιος |
| author_facet |
Γαλλόπουλος, Ευστράτιος Καλογερόπουλος, Διονύσιος |
| format |
Thesis |
| author |
Καλογερόπουλος, Διονύσιος |
| author_sort |
Καλογερόπουλος, Διονύσιος |
| title |
Συσταδοποίηση κειμένων με χρήση της μετρικής Wasserstein και τεχνικές βέλτιστης μεταφοράς |
| title_short |
Συσταδοποίηση κειμένων με χρήση της μετρικής Wasserstein και τεχνικές βέλτιστης μεταφοράς |
| title_full |
Συσταδοποίηση κειμένων με χρήση της μετρικής Wasserstein και τεχνικές βέλτιστης μεταφοράς |
| title_fullStr |
Συσταδοποίηση κειμένων με χρήση της μετρικής Wasserstein και τεχνικές βέλτιστης μεταφοράς |
| title_full_unstemmed |
Συσταδοποίηση κειμένων με χρήση της μετρικής Wasserstein και τεχνικές βέλτιστης μεταφοράς |
| title_sort |
συσταδοποίηση κειμένων με χρήση της μετρικής wasserstein και τεχνικές βέλτιστης μεταφοράς |
| publishDate |
2018 |
| url |
http://hdl.handle.net/10889/11702 |
| work_keys_str_mv |
AT kalogeropoulosdionysios systadopoiēsēkeimenōnmechrēsētēsmetrikēswassersteinkaitechnikesbeltistēsmetaphoras AT kalogeropoulosdionysios clusteringdocumentswithwassersteinmetricandoptimaltransport |
| _version_ |
1771297322708238336 |
| spelling |
nemertes-10889-117022022-09-05T20:36:01Z Συσταδοποίηση κειμένων με χρήση της μετρικής Wasserstein και τεχνικές βέλτιστης μεταφοράς Clustering documents with Wasserstein metric and optimal transport Καλογερόπουλος, Διονύσιος Γαλλόπουλος, Ευστράτιος Στεφανόπουλος, Ευάγγελος Μεγαλοοικονόμου, Βασίλειος Kalogeropoulos, Dionysios Συσταδοποίηση Ομοιότητα κειμένων Πρόβλημα βέλτιστης μεταφοράς Ενσωματώσεις Γλώσσα Νευρογλωσσικός προγραμματισμός Clustering Text similarities Wasserstein Optimal transport problem Embeddings Neuro-linguistic programming (NLP) TMG 004.35 Για τη διερεύνηση ομοιότητας ανάμεσα σε κείμενα υπάρχουν πολλές τεχνικές που χρησιμοποιούν τις συχνότητες εμφάνισης λέξεων και άλλες στατιστικές πληροφορίες που παράγονται από τα μητρώα όρων - κειμένων. Τι γίνεται όμως όταν οι λέξεις εκλαμβάνονται ως οντότητες σε ειδικούς χώρους με ειδικά επιλεγμένες αποστάσεις ομοιότητας; Στόχος της παρούσας εργασίας είναι η διερεύνηση τεχνικών μέτρησης υπολογισμού ομοιότητας και ομαδοποίησης κειμένων χρησιμοποιώντας ως μετρική την απόσταση Wasserstein . Ονομάζουμε τη μεθοδολογία αυτή W2EC (Wasserstein by Word Embedding Clustering). Για την εξαγωγή των πληροφοριών (στατιστικών και λεξιλογίου) χρησιμοποιείται η εργαλειοθήκη {\sc TMG} (Text to Matrix Generator). Κάθε κείμενο εκλαμβάνεται ως μια κατανομή και κάθε στοιχείο της κατανομής ως ένας όρος από ένα λεξικό που έχει μετασχηματιστεί σε διανυσματικό χώρο μέσω ενσωματώσεων λέξεων (word embeddings) όπως word2vec και GloVe . Το κάθε κείμενο αποτελείται από τους όρους που εμφανίστηκαν σε αυτό και ο έλεγχος ομοιότητας πραγματοποιείται επιλύοντας ένα πρόβλημα βέλτιστης μεταφοράς (optimal transport) \cite{kantorovich} της μιας κατανομής στην άλλη. Η εύρεση της στρατηγικής βέλτιστης μεταφοράς γίνεται είτε με επίλυση προβλήματος γραμμικού προγραμματισμού είτε με ομαλοποίηση του προβλήματος και εφαρμογή του αλγορίθμου Sinkhorn για αμφίπλευρη στοχαστικοποίηση. %Ένα πρόβλημα που μελετάται είναι η απόδοση ως προς την ταχύτητα της βέλτιστης μεταφοράς καθώς είναι γνωστό ότι πρόκειται για μια διαδικασία με υψηλό υπολογιστικό κόστος και μπορεί να γίνει απαγορευτική καθώς μεγαλώνει ο όγκος των δεδομένων. Εντέλει, για κάθε κείμενο υπολογίζεται η βέλτιστη μεταφορά του ως προς τα υπόλοιπα κείμενα και δημιουργείται ένα μητρώο με αποστάσεις Wasserstein. Η συσταδοποίηση επιτυγχάνεται βάσει αυτού του μητρώου με γνωστούς φασματικούς αλγόριθμους (kMeans, PDDP κλπ) και γίνεται σύγκριση των αποτελεσμάτων σε σχέση με την συσταδοποίηση που προκύπτει από το μητρώο όρων-κειμένων. Τα δεδομένα που χρησιμοποιήθηκαν αποτελούνται από γνωστές συλλογές κειμένων και η αξιολόγηση των αποτελεσμάτων για κάθε σύνολο δεδομένων γίνεται ως προς την ποιότητα, ταχύτητα αλλά και κλιμακωσιμότητα αυτών. Τα αποτελέσματα που παράγονται μέσω της μεθοδολογίας W2EC εμφανίζουν έντονες σημασιολογικές σχέσεις στα κείμενα που συσταδοποιήθηκαν μαζί και αναδεικνύουν τη χρησιμότητα τη μετρικής Wasserstein. To extract similarities between texts there are many techniques that use the statistical information that is produced by the term - document matrices. What is the case though when the words are considered as entities in special spaces with special selected similarity distances? The target of this thesis is the research of the current techniques that compute similarities and clustering with Wasserstein metric. The methodology that is presented is name W2EC (Wasserstein by Word Embedding Clustering). To extract the statistical information we use the TMG toolkit (Text to Matrix Generator). All texts are represented as distributions and every element of these distributions as a term from a lexicon that has been transformed in a vector space through word embeddings (word2vec, GloVe). The components of every document are the terms that appeared in it and to compute the similarity between 2 documents we solve an optimal transport problem to transform the first to the second. To find the right optimal transport we use either a linear programming solver or Sinkhorn's algorithm for double stohastic matrices combined with a regularization term. A problem that concerns us is the speed of the optimal transport procedure as it is known to have a high complexity and does not scale well on big data. In the end, for every document we compute the optimal transport to all documents and thus we create a matrix with the Wasserstein distances. We perfom clustering on that matrix with various well known spectral algorithms (kMeans, PDDP etc) and we compare the results with the clustering results of the same algorithms on the term document matrix. We use data from well known collections of documents (Reuters etc) and for every dataset the evaluation of the results is with respect of the quality, speed and scalability. The results from the W2EC methodology produce semantic relationships between the documents in the same clusters and highlight the utility of the Wasserstein metric. 2018-10-17T13:50:19Z 2018-10-17T13:50:19Z 2018-03-23 Thesis http://hdl.handle.net/10889/11702 gr 0 application/pdf |
