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

Abstract

Most sciences today are in a state of rapid transition towards the new era of Big Data, which is characterized by the collection and processing of large data volumes aimed at extracting new knowledge. Increasing numbers of users are gaining access to the data, exploring and developing new techniques and algorithms for storage, processing, knowledge extraction, and visualization of results. Data Science encompasses models, methods, tools, and techniques that transform data of various types into clear information, which can be handled even by analysts with limited computing skills. Machine Learning plays a central role in Data Science, as it is part of both the analytical and the prediction process. A typical data analysis process usually includes the following stages: data understanding, data preparation/preprocessing, analysis, modeling, evaluation, visualization, and decision-making. Clustering is a Machine Learning technique used for organizing data into homogeneous groups, extracting patterns, and reducing the complexity of the problem. Hierarchical clustering algorithms retain more information about the groups and their interconnections, as they are organized in dendrograms that are useful in various applications, while not requiring initialization of the number of clusters and their centers. The main drawback of hierarchical clustering algorithms is that they rely on the computation of pairwise similarities between the elements of the entire dataset, in order to generate the clusters from scratch. This technique greatly increases the complexity of the problem, both in terms of memory consumption and execution time, which is not easily manageable for large volumes of data. The purpose of the dissertation was to develop a hierarchical clustering algorithm for categorical data based on features, suitable for domain experts. The algorithm should provide clean clusters represented by specific features, while overcoming the difficulties of classical hierarchical algorithms regarding memory consumption and execution time. The presentation of the results to the user should be done through a user-friendly environment that can assist the domain experts in their decision-making process. For this purpose, the FBC hierarchical clustering algorithm was developed, which is based on the frequency of appearance of features and overcomes the aforementioned difficulties of classical hierarchical algorithms. The algorithm is efficient, scalable, user-friendly, and offers the possibility of visualizing the results of the overall clustering using a binary tree or a graph, as well as the content of each group. To evaluate the algorithm and explore its generalization capability, three different usage scenarios were implemented that analyze different types of data. In the first scenario, gene sequence data (proteins) were used, which consist of very long sequences of characters. The second scenario handled text documents, where characters are organized into words, sentences, paragraphs, etc. In the third scenario, the data concerned fashion-clothing characteristics, and the algorithm was integrated into an AI fashion designer assistant system, demonstrating its usefulness and efficiency in practical applications.

Οι περισσότερες επιστήμες σήμερα βρίσκονται σε μια κατάσταση ραγδαίας μετάβασης προς τη νέα εποχή των Μεγάλων Δεδομένων, η οποία σηματοδοτείται από συλλογή και επεξεργασία δεδομένων με στόχο την εξαγωγή νέας γνώσης. Στα δεδομένα αποκτούν πρόσβαση ολοένα και περισσότεροι χρήστες που διερευνούν και αναπτύσσουν νέες τεχνικές και αλγόριθμους για την αποθήκευση, επεξεργασία, εξαγωγή γνώσης και την οπτικοποίηση των αποτελεσμάτων. Η Επιστήμη των Δεδομένων περιλαμβάνει μοντέλα, μεθόδους, εργαλεία και τεχνικές που μετατρέπουν δεδομένα διαφόρων τύπων σε καθαρή πληροφορία, η οποία είναι κατανοητή ακόμα και από αναλυτές χωρίς υπολογιστικό υπόβαθρο. Η Μηχανική Μάθηση έχει κεντρικό ρόλο στην Επιστήμη των Δεδομένων, καθώς αποτελεί μέρος της αναλυτικής διαδικασίας και της διαδικασίας πρόβλεψης. Μια τυπική διαδικασία ανάλυσης δεδομένων συνήθως περιλαμβάνει τα ακόλουθα στάδια: κατανόηση δεδομένων, προετοιμασία/προεπεξεργασία δεδομένων, ανάλυση, μοντελοποίηση, αξιολόγηση, οπτικοποίηση και λήψη αποφάσεων. Η ομαδοποίηση αποτελεί μια τεχνική Μηχανικής Μάθησης που χρησιμοποιείται για την οργάνωση των δεδομένων σε ομοιογενείς ομάδες, την εξαγωγή προτύπων και τη μείωση της πολυπλοκότητας του προβλήματος. Οι αλγόριθμοι ιεραρχικής ομαδοποίησης διατηρούν περισσότερη πληροφορία για τις ομάδες και τις διασυνδέσεις τους, καθώς οργανώνονται σε δενδρογράμματα που είναι χρήσιμα σε διάφορες εφαρμογές, ενώ δεν απαιτούν αρχικοποίηση των κέντρων και του αριθμού των ομάδων. Το βασικό μειονέκτημα των ιεραρχικών αλγορίθμων ομαδοποίησης είναι ότι βασίζονται στον υπολογισμό ομοιοτήτων μεταξύ των στοιχείων του συνόλου των σετ δεδομένων, προκειμένου να παράγουν τις ομάδες από το μηδέν. Αυτή η τακτική αυξάνει πολύ την πολυπλοκότητα του προβλήματος, τόσο σε επίπεδο κατανάλωσης μνήμης, όσο και σε υπολογιστικό χρόνο εκτέλεσης, κάτι το οποίο δεν είναι εύκολα διαχειρίσιμο για μεγάλους όγκους δεδομένων. Σκοπός της διατριβής ήταν η ανάπτυξη ενός ιεραρχικού αλγορίθμου ομαδοποίησης κατηγορικών δεδομένων βασισμένων σε χαρακτηριστικά, κατάλληλου για ειδικούς τομέα εφαρμογής. Ο αλγόριθμος θα πρέπει να παρέχει καθαρές ομάδες που να εκπροσωπούνται από συγκεκριμένα χαρακτηριστικά, ενώ ταυτόχρονα να ξεπερνάει τις δυσκολίες των κλασσικών ιεραρχικών αλγορίθμων όσον αφορά την κατανάλωση μνήμης και τον χρόνο εκτέλεσης. Η παρουσίαση των αποτελεσμάτων στον χρήστη θα πρέπει να γίνεται μέσω ενός φιλικού περιβάλλοντος που μπορεί να τον βοηθήσει στη διαδικασία λήψης αποφάσεων. Προς το σκοπό αυτό, αναπτύχθηκε ο ιεραρχικός αλγόριθμος ομαδοποίησης FBC, ο οποίος βασίζεται στη συχνότητα εμφάνισης των χαρακτηριστικών και ξεπερνάει τις δυσκολίες κλασσικών ιεραρχικών αλγορίθμων. Ο αλγόριθμος είναι αποδοτικός, επεκτάσιμος, εύχρηστος και φιλικός προς τον χρήστη, ενώ προσφέρει τη δυνατότητα οπτικοποίησης των αποτελεσμάτων της συνολικής ομαδοποίησης με χρήση δυαδικού δέντρου και γράφου, αλλά και του περιεχομένου κάθε ομάδας. Για την αξιολόγηση του αλγορίθμου και την διερεύνηση της δυνατότητας γενίκευσής του, υλοποιήθηκαν τρία διαφορετικά σενάρια χρήσης τα οποία αναλύουν διαφορετικούς τύπους δεδομένων. Στο πρώτο σενάριο χρησιμοποιήθηκαν γονιδιακές ακολουθίες πρωτεϊνών οι οποίες αποτελούνται από πολύ μεγάλου μήκους ακολουθίες χαρακτήρων. Το δεύτερο σενάριο χειρίστηκε έγγραφα κειμένου όπου οι χαρακτήρες οργανώνονται σε λέξεις, προτάσεις, παραγράφους, κλπ. Στο τρίτο σενάριο τα δεδομένα αφορούσαν χαρακτηριστικά ενδυμάτων και ο αλγόριθμος ενσωματώθηκε σε ένα έξυπνο σύστημα βοηθού σχεδιαστή μόδας, αποδεικνύοντας τη χρησιμότητα και την αποδοτικότητά του σε πρακτικές εφαρμογές.