Το θέμα της διπλωματικής μου ήταν ο σχεδιασμός και η υλοποίηση ενός συστήματος λογισμικού, το οποίο δεδομένου ενός συνόλου από tweets, αναγνωρίζει γεγονότα του πραγματικού κόσμου που αναφέρονται σε αυτό. Ιδανικά, αναγνωρίζει και σχέσεις ανάμεσα στα γεγονότα που εξάγονται, παραγόντας έτσι ιστορίες. Τα αποτελέσματα παρουσιάζονται σε περιηγητή ιστού. Μπορείτε να δείτε την υλοποιημένη διεπαφή χρήστη μαζί με κάποια δείγματα αποτελεσμάτων εδώ και το συνοδευόμενο κείμενο εδώ.

Το σύστημα περιλαμβάνει ένα πρόγραμμα για την ανάκτηση και προ-επεξεργασία ιστορικών tweet μέσω του twitter REST API, ένα πρόγραμμα που προ-επεξεργάζεται tweets αποθηκευμένα σε αρχείο (χρήση του ενός από τα δύο προηγούμενα), ένα πρόγραμμα που αναλύει τα προ-επεξεργασμένα tweets και μια ιστοσελίδα που παρουσιάζει τα αποτελέσματα στον χρήστη. Η διεπαφή χρήστη χρησιμοποιείται για την αξιολόγηση των αποτελεσμάτων. Όλα τα προγράμματα είναι υλοποιημένα σε python και η ιστοσελίδα σε HTML + Javascript.

Εισαγωγή

Η χρήση του twitter ως πηγή ενημέρωσης προσφέρει σημαντικά πλεονεκτήματα σε σχέση με τα παραδοσιακά μέσα ενημέρωσης (εφημερίδες, blogs, κλπ). Οι ειδήσεις διαδίδονται με πολύ γοργούς ρυθμούς από χρήστη σε χρήστη και παρουσιάζονται από πολλές σκοπιές. Επιπρόσθετα, επειδή στο twitter διαδίδονται και σύνδεσμοι στα παραδοσιακά μέσα ενημέρωσης, μπορούμε να τα εκμεταλλευτούμε και αυτά.

Το πρόβλημα όμως που αντιμετωπίζομε είναι ότι το twitter είναι ένα κοινωνικό δίκτυο. Αυτό σημαίνει ότι υπάρχει μεγάλος όγκος spam και θορύβου. Επίσης ο τεράστιος όγκος από tweets είναι δύσκολο πολλές φορές να διαχειριστεί. Τα tweets που αναφέρονται σε ειδήσεις είναι περίπου στο 4-5% του συνόλου [source]. Είναι λοιπόν πολύ σημαντικό να φιλτράρουμε tweets και να είμαστε όσον το δυνατόν πιο αποδοτικοί από άποψη μνήμης.

Ένα ακόμα σημαντικό πρόβλημα που πρέπει να λάβουμε υπόψιν είναι ότι τα tweets έχουν αποσπασματικό χαρακτήρα και ανομοιογένεια ως προς τον τρόπο έκφρασης, καθώς προέρχονται από πολλές και διαφορετικές πηγές(χρήστες).

Μεθοδολογία

Φίλτρο και προ-επεξεργασία

Το πρώτο πράγμα που κάνουμε είναι να φιλτράρουμε τα tweets που εισέρχονται στο σύστημα. Ένα tweet το κρατάμε εάν ισχύουν όλα τα παρακάτω:

• είναι στην υποστηριζόμενη γλώσσα (αγγλικά), η οποία καθορίζεται από τα εργαλεία γλωσσικής ανάλυσης
• δεν είναι retweet και δεν έχει αναφορά (mention) σε χρήστη, γιατί αυτά τα είδη tweet είναι συνήθως κοινωνικός θόρυβος. Αυτή η συνθήκη είναι προαιρετική αλλά συνίσταται
• έχει μήκος τουλάχιστον 5 λέξεων και 20 χαρακτήρων
• έχει λιγότερα από 4 urls και 4 hashtags. Τέτοια tweet τείνουν να είναι spam
• έχουν ουσιαστικό ακολουθούμενο από ρήμα

Η εξακρίβωση της τελευταίας συνθήκης γίνεται με την χρήση ενός Part of Speech (POS) tagger. Ένας POS tagger είναι ένα γλωσσικό εργαλείο, στο οποίο δίνουμε μια σειρά από tokens και αυτό σημειώνει σε κάθε token τι μέρος του λόγου είναι. Με τον POS tagger μπορούμε να θεωρήσουμε υποψήφια κύρια ονόματα αυτά που σημειώνονται ως proper nouns.

Μετά από αυτό, απορρίπτουμε την πληροφορία που δεν χρησιμοποιούμε από τα tweet εισόδου, τα οποία δίνονται σε JSON και τα αποθηκεύουμε στην μορφή ένα tweet σε JSON ανά γραμμή. Αυτή η μορφή είναι η μορφή που δέχεται η φάση της ανάλυσης.

Επέκταση ερωτήματος

Αν επιλέξουμε να τρέξουμε το πρόγραμμα που ανακτά tweet από το twitter REST API, έχουμε την επιλογή να τρέξουμε ένα επιπλέον βήμα επέκτασης ερωτήματος. Αυτό είναι εντελώς προαιρετικό και συνήθως δεν χρειάζεται. Η μεθοδολογία με την οποία κάνουμε την επέκταση ερωτήματος είναι η ακόλουθη:

1. Εξαγωγή υποψηφίων με χρήση του αλγορίθμου Rapid Automatic Keyword Extraction (RAKE) [source]
2. Αγνοούμε αυτά που έχουν ρήματα, επιρρήματα και προθέσεις
3. Επιλογή αυτών που ξεπερνούν ένα κατώφλι σε συχνότητα
4. Από αυτά, απορρίπτουμε τα unigrams που εμφανίζονται σε digrams και trigrams
5. Το επεκταμένο ερώτημα είναι η διάζευξη των λέξεων κλειδιών που απομένουν

Μπορούμε τότε να ξανατρέξουμε το πρόγραμμα χρησιμοποιώντας το ερώτημα που προκύπτει. Παράδειγμα χρήσης επέκτασης ερωτήματος:

Αρχικό ερώτημα: korea
Επεκταμένο ερώτημα: north korea OR south korea OR kim jong OR north korean leader kim jong

Χρονκή κατάτμηση

Σε αυτό το σημείο μπαίνουμε στην φάση της ανάλυσης. Στο πρώτο βήμα χωρίζουμε τα tweets σε ομάδες, με βάση το timestamp τους. Οι χρονικές ομάδες που προκύπτουν καθορίζονται από τις κορυφές στο ιστόγραμμα όγκου-χρόνου. Για την ανίχνευση των κορυφών χρησιμοποιούμε ένα φίλτρο βασισμένο στην κινούμενη διάμεσο για να εξάγουμε μια κισιμη καμπύλη. Εάν υπάρχει ικανός αριθμός συνεχόμενων σημείων του ιστογράμματος πάνω από την κρίσιμη καμπύλη τότε σημειώνουμε αυτά τα σημεία ως μια περιοχή υψηλής κίνησης. Παράδειγμα εφαρμογής της μεθόδου φαίνεται στην εικόνα που ακολουθεί.

Ουσιαστικά, καταλήγουμε με ομάδες tweets υψηλής και χαμηλής κίνησης. Το σκεπτικό πίσω από αυτό τον διαχωρισμό είναι να μειώσουμε την πολυπλοκότητα κρατώντας ταυτόχρονα μαζί σχετικά tweets.

Λεξικογραφική Ομαδοποίηση

Εφαρμόζουμε τον αλγόριθμο ομαδοποίησης DBSCAN σε κάθε μία ομάδα tweets που παράγαμε από το προηγούμενο βήμα. Η υλοποίηση του αλγορίθμου είναι τετραγωνικής χρονικής πολυπλοκότητας.

Πριν την εφαρμογή του αλγορίθμου στις ομάδες tweets, πρέπει πρώτα να αναπαραστήσουμε τα κείμενα των tweets σε μια μορφή που υποστηρίζει την έννοια της απόστασης. Η αναπαράσταση που χρησιμοποιούμε είναι η bag-of-words. Η αναπαράσταση bag-of-words είναι πρακτικά ένα αραιό διάνυσμα, όπου κάθε διάσταση αναπαριστά μια λέξη (ή token) από ένα λεξικό. Όταν η λέξη δεν εμφανίζεται στο κείμενο, η αντίστοιχη διάσταση είναι μηδέν. Διαφορετικά, αναθέτουμε την τιμή 1 για λέξεις που δεν ανήκουν στο σύνολο των υποψηφίων κυρίων ονομάτων και b (συνήθως > 1) για λέξεις που ανήκουν. Έπειτα, εφαρμόζουμε ένα tf-idf μοντέλο και κανονικοποιούμε σε μοναδιαίο μήκος.

Ως απόσταση D μεταξύ των διανυσμάτων A, B χρησιμοποιούμε τον τύπο:

 

Ουσιαστικά υπολογίζουμε το συνημίτονο της γωνίας μεταξύ των δύο διανυσμάτων bag-of-words. Μπορούμε να υπολογίσουμε το συνημίτονο από τον τύπο του εσωτερικό γινόμενου και αφού έχουμε μοναδιαία διανύσματα δεν χρειάζεται να διαιρέσουμε με το γινόμενο των μηκών τους.

Για να μειώσουμε το κόστος που επιφέρει η τετραγωνική πολυπλοκότητα της υλοποίησης μας του DBSCAN, μπορούμε να κάνουμε προαιρετικά δειγματοληψία σε κάθε χρονική ομάδα. Η δειγματοληψία γίνεται θέτοντας ένα άνω όριο στον αριθμό των σημείων που επιλέγονται από κάθε χρονική περιοχή. Έτσι, δημιουργούμε ένα άνω φράγμα στον χρόνο εκτέλεσης για κάθε χρονική ομάδα. Στην συνέχεια κανονικοποιούμε το μέγεθος των ομάδων που προκύπτουν μετά από την λεξικογραφική ομαδοποίηση για να αντισταθμίσουμε την δειγματοληψία.

Επεξεργασία ομάδων

Σε αυτό το σημείο, επισυνάπτουμε διάφορα χαρακτηριστικά στις παραγόμενες ομάδες τραβώντας δεδομένα από τον δίσκο. Αυτά τα χαρακτηριστικά είναι:

• Centroid: κανονικοποιημένο διανυσματικό άθροισμα των επιμέρους bag-of-words
• Terms: το Centroid σε αναγνώσιμη μορφή
• Texts: Τα κοντινότερα 10 στο κέντρο μοναδικά κείμενα
• Title: Το κείμενο από τα texts με την καλύτερη ευριστική τιμή κατάταξης
• Time: Ελάχιστη/Έναρξης, Μέγιστη/Λήξης timestamp των tweets + Μίνι ιστόγραμμα όγκου-χρόνου
• Informal: Πλήθος informal tweets (ανιχνεύονται με χρήση κανονικών εκφράσεων)
• Size: Το μέγεθος της ομάδας, κανονικοποιημένο εάν προέρχεται από χρονική ομάδα που υπέστη δειγματοληψία

Μετά ενώνουμε της ομάδες με χρήση του τύπου:

 

Όπου a και threshold παραμέτροι, sim το συνημίτονο της γωνίας μεταξύ των centroids των ομάδωνe1,e2 και dt η απόσταση τους στον χρόνο σε δευτερόλεπτα. Με άλλα λόγια, ενώνουμε ομάδες που η απόσταση τους είναι μικρότερη από ένα κατώφλι, αφού εφαρμόσουμε απόσβεση ανάλογα με την απόσταση στον χρόνο. Το σκεπτικό σε αυτή την περίπτωση είναι να διορθώσουμε κακούς διαχωρισμούς στο στάδιο της χρονικής κατάτμησης.

Επιλογή ομάδων

Τώρα που έχουμε ομάδες στην τελική τους μορφή, απαλείφουμε αυτά που θεωρούμε ως κακής ποιότητας. Η επιλογή γίνεται με βάση ένα ευριστικό κατάταξης και ένα όριο στον λόγο informal/size. Το ευριστικό κατάταξης προτιμάει:

• Μεγαλύτερο μέγεθος
• Μικρότερη χρονική διάρκεια
• 1-2 urls
• Περισσότερους όρους(terms)
• Λιγότερα ‘informal’ tweets

Εξαγωγή συσχετίσεων

Για το τελευταίο βήμα της ανάλυσης, προσπαθούμε να εξάγουμε συσχετίσεις μεταξύ των ομάδων. Η εξαγωγή συσχετίσεων γίνεται με έναν σχετικό τρόπο. Οι συσχετίσεις ανιχνεύονται με την χρήση κατωφλιού στην απόσταση των κέντρων των ομάδων.

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

Μπορούμε να σκεφτούμε τις ομάδες σαν κορυφές ενός κατευθυνόμενου γράφου. Οι συσχετίσεις αναπαριστώνται στον γράφο σαν ακμές. Η κατεύθυνση των ακμών βασίζεται στην θέση των ομάδων στην γραμμή του χρόνου.

Παρουσίαση

Όπως ειπώθηκε προηγουμένως, τα αποτελέσματα παρουσιάζονται στον χρήστη μέσω μίας ιστοσελίδας. Υπάρχουν τρεις τρόποι αναπαράστασης. Πρώτα, χρησιμοποιούμε ένα σύνηθες feed. Μετά, ένας γράφος παρουσιάζεται όπου οι συσχετίσεις γίνονται πιο ξεκάθαρες. Τέλος, οι ομάδες τοποθετούνται πάνω στην γραμμή του χρόνου. Επιπρόσθετα, στο κάτω μέρος της σελίδας, παρουσιάζουμε το ιστόγραμμα όγκου μαζί με την κρίσιμη καμπύλη.

Η αξιολόγηση γίνεται μέσω της ιστιοσελίδας, με την χρήση checkbox στο πλάι των αντικειμένων του feed για την επισήμανση τους ως σχετικών ή όχι. Οι ομάδες που απαλείφονται από την φάση της επιλογής είναι επίσης διαθέσιμα και παρουσιάζονται με κόκκινο χρώμα εάν το κουτάκι eliminated που βρίσκεται στην κορυφή της σελίδας είναι σημειωμένο. Αφού έχουμε τελειώσει με την επισήμανση έχει τελειώσει, πατώντας έναν σύνδεσμο, υπολογίζονται οι μετρικές.

Μια ζωντανή έκδοση της διεπαφής χρήστη είναι διαθέσιμη εδώ.

Συμπεράσματα και Πιθανές βελτιώσεις

Τα αποτελέσματα είναι ικανοποιητικά και η μεθοδολογία φαίνεται να λειτουργεί σε datasets διαφόρων ειδών. Φυσικά υπάρχει περιθώριο για βελτίωση και επέκταση.

Το σύστημα μπορεί να υποστηρίξει άλλες γλώσσες αν λειτουργήσει σε συνδυασμό με εργαλεία ανάλυσης που τις υποστηρίζουν. Το μεγαλύτερο μέρος της δουλείας είναι επικεντρωμένο στο βήμα της προεπεξεργασίας. Η χρήση συνωνύμων μπορεί να αποτελέσει την γέφυρα μεταξύ των διαφόρων γλωσσών. Το σύστημα ως έχει μπορεί να χρησιμοποιηθεί για tweet σε άλλες γλώσσες, αλλά με υποβιβασμένη απόδοση.

Άλλα κοινωνικά δίκτυα μπορούν να υποστηριχθούν σχετικά εύκολα.

Τέλος, η μεθοδολογία μπορεί να τροποποιηθεί ώστε να εφαρμόζεται σε ροές από tweet που καταφτάνουν σε πραγματικό χρόνο. Η χρήση relevance feedback μπορεί να βελτιώσει τα αποτελέσματα ενώ το σύστημα βρίσκεται σε λειτουργία. Ένας hierarchical/agglomerative αλγόριθμος ομαδοποίησης είναι μια καλύτερη επιλογή στην περίπτωση των ροών πραγματικού χρόνου. Το φίλτρο ανίχνευσης κορυφών εισάγει μια καθυστέρηση στο σύστημα και αυτό μπορεί να είναι πρόβλημα. Άλλο ένα πρόβλημα είναι η αρχικοποίηση και η ανανέωση των μοντέλων και του λεξικού.