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

Abstract

In recent years, the amount of information transmitted online has greatly increased, which dictates the creation and usage of new systems, capable of handling large volumes of information. Machine Learning and Data Mining are two fields of study, which facilitate the analysis and classification of information. Machine learning algorithms "learn" directly from data, by discovering meaningful patterns, without the use of explicit instructions. In this thesis, three separate, but related, approaches for Community Detection and Intrinsic Plagiarism Detection, which utilize machine learning techniques, were studied and implemented. Community Detection, or graph clustering, is one of the most popular topics in modern science of networks, which aims to solve the problem of identifying the community structure in networks. Most networks display community structure, i.e. the vertices are organized in groups, called communities, groups or clusters. Community detection is not a well defined problem, as there is no strict and universally accepted definition of community. The definition often depends on the application, the research question at hand or on the specific system under study. In this thesis, the problem of community detection in social networks was studied and a methodology for identifying similar users on Twitter was proposed. Communities are defined as groups of users that are more densely connected to each other than to the rest of the network, interact more between them and share common interests. Therefore, this methodology does not solely depend on the network topology in order to group the users into communities, but also takes into account the text that users share, as well as their interactions. Initially, six different similarity metrics are defined, which are based on Twitter attributes that provide information regarding the interactions between users. These metrics are combined, and their combination is used for the clustering of users into communities. Additionally, a new method for extracting the topics discussed in each community is presented, which helps identify the users' interests. Also, a method for the elimination of the trivial topics is proposed, and a process for automatically generating labels for the topics is described. Secondly, graph embedding and the extraction of node embeddings are being studied. Graph embedding methods have been proposed as an alternative to traditional graph mining techniques. The objective is to convert a graph into a low dimensional representation, where each node of the graph would be mapped to a low dimensional vector. These vectors, also called node embeddings or feature vectors, can then be presented as input to any supervised learning algorithm, thus simplifying the original problem. Therefore, these methods can be useful in a variety of real-world applications, such as node classification, community detection, link prediction and network visualization. Based on the above, the second approach is proposed, which, contrary to previous approaches, which only take into account the edges of the graph when exploring the graph through random walks, also considers the similarities between the nodes. Plagiarism is the act of taking or closely imitating someone else's work and presenting it as original, without proper citation or acknowledgment. Plagiarism detection in text documents is divided into two major categories, extrinsic and intrinsic methods. Extrinsic methods detect the suspicious similarities between a collection of potential source documents and a set of suspicious documents, while in intrinsic methods the objective is to identify which of the passages of an investigated document are plagiarized by observing the variation of the writing style within the document. Intrinsic plagiarism detection is based on the idea that every author has its own personal and unique writing style, which can be detected and quantified using stylistic and/or semantic means. Based on the above, an intrinsic plagiarism detection approach for text documents is presented. Initially, a set of novel stylistic features, which help quantify the author's writing style for the whole document and each suspicious passage, is introduced. These features are then combined with a number of supervised learning methods, in order to classify the passages into plagiarized or non-plagiarized. Finally, the unbalanced nature of the datasets is examined, which is considered a crucial parameter for this task. As a result, over-sampling and under-sampling techniques are used in order to examine whether the performance of the proposed system is improved. The proposed approaches were evaluated on publicly available datasets. Due to the nature of the problem of community detection, the results of the first methodology are not evaluated in comparison to an already existing approach. On the contrary, the second and third approaches were compared to the state-of-the-art algorithms for each respective field of study. The experimental results demonstrate the satisfactory behavior of the proposed methodologies, which in many cases outperform the algorithms they are compared to.

Τα τελευταία χρόνια, η πληροφορία που διακινείται ηλεκτρονικά έχει αυξηθεί σε μεγάλο βαθμό, γεγονός που επιβάλλει τη δημιουργία και χρήση νέων συστημάτων, ικανών να διαχειρίζονται μεγάλο όγκο πληροφορίας. Η Μηχανική Μάθηση και η Εξόρυξη Δεδομένων είναι δύο πεδία μελέτης, τα οποία επιτρέπουν την ανάλυση και ταξινόμηση πληροφορίας. Οι αλγόριθμοι μηχανικής μάθησης "μαθαίνουν" από τα ίδια τα δεδομένα, ανακαλύπτοντας μοτίβα, χωρίς τη χρήση ρητών οδηγιών. Στο πλαίσιο της διατριβής, μελετήθηκαν και υλοποιήθηκαν τρεις ξεχωριστές, αλλά συναφείς προσεγγίσεις, για την Ανίχνευση Κοινοτήτων και την Εγγενή Ανίχνευση Λογοκλοπής, οι οποίες κάνουν χρήση τεχνικών μηχανικής μάθησης. H Ανίχνευση Κοινοτήτων, ή αλλιώς ομαδοποίηση γράφου, είναι ένα από τα πιο δημοφιλή θέματα της σύγχρονης επιστήμης δικτύων, που επιχειρεί να λύσει το πρόβλημα του εντοπισμού της κοινοτικής δομής σε δίκτυα. Τα περισσότερα δίκτυα εμφανίζουν κοινοτική δομή, δηλαδή οι κορυφές τους είναι οργανωμένες σε ομάδες, που ονομάζονται κοινότητες, ομάδες ή συστάδες. Η ανίχνευση κοινοτήτων δεν είναι ένα σαφώς ορισμένο πρόβλημα, καθώς δεν υπάρχει ένας αυστηρός και καθολικά αποδεκτός ορισμός για το τι είναι κοινότητα. Ο ορισμός αλλάζει ανάλογα με την εφαρμογή, δηλαδή με το ερευνητικό ερώτημα που καλούμαστε κάθε φορά να απαντήσουμε ή το συγκεκριμένο σύστημα το οποίο βρίσκεται υπό μελέτη. Στο πλαίσιο της διατριβής, μελετήθηκε το πρόβλημα της ανίχνευσης κοινοτήτων στα κοινωνικά δίκτυα και προτάθηκε μια μεθοδολογία για τον εντοπισμό όμοιων χρηστών στο Twitter. Οι κοινότητες ορίζονται ως ομάδες χρηστών με μεγαλύτερη πυκνότητα συνδέσεων μεταξύ τους παρά με το υπόλοιπο δίκτυο, που αλληλεπιδρούν ο ένας με τον άλλο και έχουν κοινά ενδιαφέροντα. Επομένως, η συγκεκριμένη μεθοδολογία δεν βασίζεται μόνο στην τοπολογία του δικτύου για να ομαδοποιήσει τους χρήστες σε κοινότητες, αλλά λαμβάνει επιπλέον υπ' όψιν το κείμενο που μοιράζονται οι χρήστες και τις αλληλεπιδράσεις τους. Αρχικά, ορίζονται έξι διαφορετικές μετρικές ομοιότητας, με βάση όλα τα χαρακτηριστικά στοιχεία του Twitter που παρέχουν πληροφορία για τις αλληλεπιδράσεις των χρηστών. Οι μετρικές αυτές συνδυάζονται, και ο συνδυασμός τους χρησιμοποιείται για την ομαδοποίηση των χρηστών σε κοινότητες. Επίσης, παρουσιάζεται μια νέα μέθοδος που εξάγει τα θέματα που συζητούνται σε κάθε κοινότητα, με στόχο να εντοπιστούν τα ενδιαφέροντα των χρηστών. Ακόμα, προτείνεται μια μέθοδος αφαίρεσης των θεμάτων που δεν παρουσιάζουν ενδιαφέρον και περιγράφεται μια διαδικασία για την αυτόματη παραγωγή επισημάνσεων για κάθε θέμα. Σε δεύτερη φάση, μελετάται η ενσωμάτωση γράφου και η εξαγωγή διανυσματικών παραστάσεων κόμβων. Οι μέθοδοι ενσωμάτωσης γράφου έχουν προταθεί ως εναλλακτική στις παραδοσιακές τεχνικές εξόρυξης γράφων. Στόχος τους είναι η μετατροπή ενός γράφου σε μια αναπαράσταση χαμηλών διαστάσεων, όπου κάθε κόμβος αντιστοιχεί σε ένα διάνυσμα χαμηλών διαστάσεων. Αυτά τα διανύσματα, που ονομάζονται, επίσης, διανυσματικές παραστάσεις κόμβων, μπορούν στη συνέχεια να δοθούν ως είσοδοι σε οποιονδήποτε αλγόριθμο επιβλεπόμενης μάθησης, μετατρέποντας, έτσι, το αρχικό πρόβλημα σε ένα ήδη γνωστό. Επομένως, οι μέθοδοι αυτές είναι χρήσιμες σε μια πληθώρα εφαρμογών του πραγματικού κόσμου, όπως είναι η ταξινόμηση κόμβων, η ανίχνευση κοινοτήτων, η πρόβλεψη συνδέσμου και η οπτικοποίηση δικτύων. Στα πλαίσια αυτά, προτείνεται η δεύτερη προσέγγιση της διατριβής, η οποία, σε αντίθεση με προηγούμενες προσεγγίσεις, οι οποίες λαμβάνουν υπ' όψιν μόνο τις ακμές ενός γράφου κατά την εξερεύνηση του μέσω τυχαίων περιπάτων, λαμβάνει επίσης υπ' όψιν τις ομοιότητες μεταξύ των κόμβων. Η λογοκλοπή είναι η πράξη της αντιγραφής ή της μίμησης του έργου κάποιου άλλου και η παρουσίασή του ως πρωτότυπη, χωρίς όμως την κατάλληλη αναφορά ή παραπομπή. Η ανίχνευση λογοκλοπής σε έγγραφα κειμένου χωρίζεται σε δύο κύριες κατηγορίες, τις εξωγενείς και τις εγγενείς μεθόδους. Οι εξωγενείς μέθοδοι συγκρίνουν μια συλλογή εγγράφων, η οποία αποτελεί πιθανή πηγή προέλευσης των αντιγραμμένων αποσπασμάτων, και ένα σύνολο ύποπτων εγγράφων, ενώ οι εγγενείς μέθοδοι προσδιορίζουν ποια από τα αποσπάσματα του εγγράφου υπό διερεύνηση είναι αντιγραμμένα, παρατηρώντας τις διαφοροποιήσεις στον τρόπο γραφής μέσα στο ίδιο το κείμενο. Η κεντρική ιδέα στην οποία βασίζεται η εγγενής ανίχνευση λογοκλοπής είναι ότι κάθε συγγραφέας έχει το δικό του προσωπικό και μοναδικό στυλ γραφής, το οποίο μπορεί να ανιχνευθεί και να ποσοτικοποιηθεί χρησιμοποιώντας στυλιστικές ή/και σημασιολογικές τεχνικές. Με βάση τα παραπάνω, παρουσιάζεται μια προσέγγιση εγγενούς ανίχνευσης λογοκλοπής για έγγραφα κειμένου. Αρχικά, προτείνεται μια σειρά νέων χαρακτηριστικών, τα οποία επιτρέπουν την ποσοτικοποίηση του τρόπου γραφής για κάθε απόσπασμα κειμένου. Τα χαρακτηριστικά αυτά συνδυάζονται με μια σειρά μοντέλων επιβλεπόμενης μάθησης, που εκπαιδεύονται να ταξινομούν τα αποσπάσματα ανάλογα με το αν έχουν προκύψει από λογοκλοπή ή όχι. Τέλος, μελετάται το πρόβλημα των μη ισορροπημένων δεδομένων, το οποίο αποτελεί μία κρίσιμη παράμετρο του προβλήματος. Για το λόγο αυτό, εξετάζεται το κατά πόσον οι τεχνικές υπερδειγματοληψίας και υποδειγματοληψίας βελτιώνουν τα αποτελέσματα του συστήματος. Οι προτεινόμενες προσεγγίσεις αξιολογήθηκαν σε δημόσια διαθέσιμα σύνολα δεδομένων. Λόγω της φύσης του προβλήματος της ανίχνευσης κοινοτήτων, τα αποτελέσματα της πρώτης μεθοδολογίας δεν αξιολογούνται σε σύγκριση με κάποιον ήδη υπάρχοντα αλγόριθμο.Αντίθετα, η δεύτερη και η τρίτη προσέγγιση συγκρίθηκαν με τους state-of-the-art αλγορίθμους στο εκάστοτε πεδίο έρευνας. Τα αποτελέσματα των πειραμάτων αποδεικνύουν την ικανοποιητική συμπεριφορά των προτεινόμενων μεθοδολογιών, οι οποίες σε πολλές περιπτώσεις υπερτερούν σε σχέση με τους αλγορίθμους με τους οποίους συγκρίνονται.