Apache Hadoop | Εξόρυξη κειμένου, Text Mining | Συσταδοποίηση Κειμένου, Text Clustering | KMeans | MapReduce | Java | BigKClustering
1
27
Περιέχει: εικόνες, αλγόριθμους, κώδικα, πίνακες
Την τελευταία δεκαετία έχει συντελεστεί ραγδαία εξέλιξη προς την κατεύθυνση της αποδοτικής διαχείρισης και επεξεργασίας μεγάλων δεδομένων (big data) με συνήθη εξοπλισμό σε κατανεμημένο περιβάλλον. Το MapReduce αποτελεί την πλέον διαδεδομένη στις μέρες μας πλατφόρμα (framework) η οποία έχει αναπτυχθεί με στόχο να προσφέρει μια επαρκώς ικανοποιητική (τόσο από πλευράς απόλυτων χρόνων απόκρισης, όσο και από πλευράς λόγου κόστους-απόδοσης) λύση στις ανάγκες επεξεργασίας που παρουσιάζουν πλέον οι αλγόριθμοι/υπολογισμοί σε τέτοιου είδους δεδομένα (σε όγκους της τάξεως των petabytes). Το μοντέλο του MapReduce δίνει τη δυνατότητα αποδοτικής ανάπτυξης παράλληλων αλγόριθμων συγκεκριμένης δομής για την οποία εγγυάται και υποστηρίζει την αποδοτική και αξιόπιστη εκτέλεσή τους πάνω από κλιμακούμενης έκτασης συστοιχίες υπολογιστών (clusters) είτε σε τοπικό-προσωποποιημένο επίπεδο είτε σε πιο ευρύ και διάφανο φάσμα αντίστοιχων υπηρεσιών (cloud). Το Apache Hadoop αποτελεί την πλέον διαδεδομένη ελεύθερη υλοποίηση του MapReduce. Σκοπός της πτυχιακής εργασίας ήταν καταρχήν η διερεύνηση των πιο πρόσφατων εξελίξεων σε παράλληλους αλγόριθμους και ήδη υπάρχουσες υλοποιήσεις σε MapReduce κλασικών αλγόριθμων εξόρυξης δεδομένων (data mining), όπως ο KMeans, ο Ιεραρχικός Αλγόριθμος και άλλοι. Στη συνέχεια επιλέχθηκε ο KMeans για επεξεργασία και εξαγωγή πληροφορίας από μεγάλης κλίμακας δεδομένα στον τομέα της ανάκτησης κειμένων. Σχεδιάστηκε και υλοποιήθηκε ο κλασικός αλγόριθμος KMeans, αλλά και παραλλαγές αυτού, όπως ο Improved KMeans, ο BigKClustering και άλλοι, στο μοντέλο του MapReduce. Τροποποιήθηκαν έτσι ώστε να είναι δυνατή η εφαρμογή τους σε συσταδοποίηση κειμένων και αξιολογήθηκε η απόδοσή τους σε πραγματικό κατανεμημένο περιβάλλον, με σκοπό την επίτευξη ικανοποιητικών χρόνων απόκρισης και τιμών επιτάχυνσης έναντι της σειριακής εκτέλεσής τους. Η ανάπτυξη έγινε στην πλατφόρμα Hadoop, σε γλώσσα προγραμματισμού Java, ενώ η πειραματική αξιολόγηση έγινε σε συστοιχία υπολογιστών του εργαστηρίου του Τμήματος Μηχανικών Πληροφορικής και Υπολογιστών του Πανεπιστημίου Δυτικής Αττικής.
In the last decade, there has been a rapid evolution towards the efficient management and processing of big data using commodity equipment in a distributed environment. MapReduce constitutes the most widely used framework developed to offer a sufficiently satisfying (as regarding both absolute response time and cost-performance ratio) solution to the processing needs that algorithms and calculations present while dealing with such data (an order of magnitude such as petabytes). The MapReduce programming model offers the ability to develop efficient parallel algorithms of a specific structure and guarantees and supports their efficient and reliable function over a scalable magnitude of computer clusters, either in a local, personalized level or in a wider and transparent spectrum of services (cloud). Apache Hadoop is the most widely known and used, open-source implementation of MapReduce. The purpose of this paper was firstly to explore the most recent developments in parallel algorithms and existing MapReduce implementations of original data mining algorithms, such as KMeans, the Hierarchical Algorithm and others. To continue, KMeans was selected to process and extract information from big data in the field of text retrieval. We designed and implemented KMeans in its original form, as well as some of its variations, such as the Improved KMeans, the BigKClustering and others, using the MapReduce programming framework. These algorithms were redesigned, so that they could be applied in document clustering and their performance was evaluated in real-world distributed environments, in order to achieve a satisfying response time and speed-up value, compared to their serial execution. The Hadoop platform and the Java programming language were used for the development, while the experimental evaluation was carried out in a computer cluster at the laboratory of the Department of Informatics and Computer Engineering, University of West Attica.
Παράλληλοι Αλγόριθμοι Εξόρυξης Κειμένου στο Μοντέλο του MapReduce