Clustering methods based on deep learning and unimodality testing

Abstract

Data clustering is the process of partitioning a dataset into a finite set of groups, or clusters, such that data points within each cluster exhibit intra-cluster similarity, while those belonging to different clusters are characterized by inter-cluster dissimilarity. Clustering remains a challenging task due to the inherent complexity of uncovering meaningful structures within data. Revealing these hidden structures provides valuable insights and facilitates a deeper understanding of the underlying patterns. This thesis concerns the development, implementation and evaluation of novel clustering methodologies mainly focused on three important problems: i) partitional clustering in both Euclidean and kernel spaces, ii) unimodality-based clustering, which incorporates the concept of unimodality into the clustering process, and iii) deep clustering, which leverages the representational power of deep learning methods. We first introduce global k-means++, a method developed to address the initialization challenges inherent in the standard k-means algorithm. The approach integrates the incremental strategy of global k-means with the probabilistic center selection mechanism of k-means++, effectively combining the strengths of both techniques. The resulting synergy delivers high-quality clustering solutions while significantly reducing the computational cost typically associated with global k-means. Furthermore, we extend this concept from Euclidean to kernel space by proposing global kernel k-means++, an algorithm specifically designed to overcome the initialization problem in kernel k-means. The optimization effectiveness of both global k-means variants is thoroughly validated through extensive experimental evaluation. Afterwards, we present UniForCE, a clustering method that simultaneously partitions data and estimates the number of clusters k. UniForCE introduces a novel notion of locally unimodal clusters, focusing on unimodality at local regions of the data density rather than in the entire cluster. By identifying unimodal pairs of neighboring subclusters, the method aggregates them into larger, statistically coherent structures via a unimodality graph. This flexible formulation enables the discovery of arbitrarily shaped clusters. A statistical test determines unimodal pairs, and clustering is achieved with automatic estimation k by detecting the number of connected components in the unimodality graph. Extensive experiments on synthetic and real datasets validate both the conceptual soundness of the method and its practical effectiveness. Furthermore, we introduce the soft silhouette score, a generalization of the widely used silhouette measure that accommodates probabilistic cluster assignments. Building on this differentiable measure, we develop an autoencoder-based deep clustering method utilizing the soft silhouette score. Our method guides the learned latent representations to form clusters that are both compact and well-separated. This property is crucial in real-world applications, as simultaneously ensuring compactness and separability guarantees that clusters are not only densely packed but also clearly distinct from each other. We evaluate our method on a variety of benchmark datasets and against state-of-the-art methods to demonstrate that it outperforms established deep clustering approaches, highlighting the effectiveness of the soft silhouette score as a principled objective for improving the quality of learned latent representations. Finally, we present the neural implicit maximum likelihood clustering, which is a neural-network-based approach that frames clustering as a generative task within the Implicit Maximum Likelihood Estimation framework. By adapting ideas from ClusterGAN, our method avoids several well-known shortcomings of GAN-based clustering while maintaining a simple and stable training objective. The method performs particularly well on small datasets, with experimental comparisons against both deep and conventional clustering algorithms underscoring its competitive potential. A notable strength of our method is its ability to capture diverse cluster geometries without requiring hyperparameter tuning. Experiments on synthetic datasets show that the method can successfully cluster both cloud-shaped and ring-shaped data.

Ομαδοποίηση ονομάζεται η διαδικασία διαμέρισης ενός συνόλου δεδομένων σε ένα πεπερασμένο σύνολο ομάδων, ή συστάδων, έτσι ώστε τα δεδομένα που εμπεριέχονται σε κάθε ομάδα να εμφανίζουν εσωτερική ομοιότητα, ενώ δεδομένα που ανήκουν σε διαφορετικές ομάδες να χαρακτηρίζονται από μεταξύ τους ανoμοιότητα. Η ομαδοποίηση παραμένει μια απαιτητική διαδικασία λόγω της εγγενούς πολυπλοκότητας που παρουσιάζει η εύρεση ουσιαστικών δομών μέσα στα δεδομένα. Η ανάδειξη αυτών των κρυμμένων δομών παρέχει πολύτιμες πληροφορίες και διευκολύνει την πιο βαθιά κατανόηση των κρυμμένων προτύπων. Η παρούσα διατριβή αφορά την ανάπτυξη, υλοποίηση και αξιολόγηση καινοτόμων μεθοδολογιών ομαδοποίησης, με κύρια εστίαση σε τρία σημαντικά ζητήματα: i) τη διαμεριστική ομαδοποίηση που βασίζεται στον αλγόριθμο k-means τόσο σε Ευκλείδειους όσο και σε χώρους που ορίζονται από συναρτήσεις πυρήνα (kernel functions), ii) την ομαδοποίηση βασισμένη στη μονοτροπικότητα, η οποία ενσωματώνει την έννοια της μονοτροπικότητας στη διαδικασία της ομαδοποίησης iii) τη βαθιά ομαδοποίηση, η οποία αξιοποιεί την ικανότητα δημιουργίας αποδοτικών αναπαραστάσεων.Αρχικά παρουσιάζουμε τον global k-means++, μια μέθοδο που αναπτύχθηκε για να αντιμετωπίσει τις προκλήσεις αρχικοποίησης που είναι εγγενείς στον κλασικό αλγόριθμο k-means. Η προσέγγιση αυτή ενσωματώνει την επαναληπτική στρατηγική επίλυσης του αλγορίθμου global k-means με τον πιθανοκρατικό μηχανισμό επιλογής κέντρων του αλγορίθμου k-means++, συνδυάζοντας αποτελεσματικά τα πλεονεκτήματα και των δύο τεχνικών. Η προκύπτουσα συνέργεια παρέχει λύσεις ομαδοποίησης υψηλής ποιότητας, μειώνοντας ταυτόχρονα σημαντικά το υπολογιστικό κόστος που συνήθως συνδέεται με τον αλγόριθμο global k-means. Επιπλέον, επεκτείνουμε την ιδέα αυτή από τον Ευκλείδειο χώρο σε χώρους χαρακτηριστικών που ορίζονται από συναρτήσεις πυρήνα, προτείνοντας τον global kernel k-means++, έναν αλγόριθμο σχεδιασμένο για να αντιμετωπίσει το πρόβλημα της αρχικοποίησης του κλασικού αλγορίθμου kernel k-means. Η ικανότητα ελαχιστοποίησης και των δύο προτεινόμενων παραλλαγών του global k-means επιβεβαιώνεται διεξοδικά μέσα από εκτεταμένη πειραματική αξιολόγηση. Στη συνέχεια παρουσιάζουμε τον αλγόριθμο UniForCE, μια μέθοδο ομαδοποίησης που ταυτόχρονα διαμερίζει τα δεδομένα και παρέχει μία εκτίμηση για τον αριθμό των ομάδων. Ο UniForCE εισάγει την έννοια των τοπικά μονοτροπικών ομάδων, εστιάζοντας στη μονοτροπικότητα σε τοπικές περιοχές των δεδομένων αντί σε ολόκληρη την ομάδα. Με την αναγνώριση μονοτροπικών ζευγών γειτονικών υποομάδων, η μέθοδος τις συνενώνει σε μεγαλύτερες, στατιστικά συνεκτικές δομές μέσω ενός γράφου μονοτροπικότητας. Αυτή η ευέλικτη διατύπωση καθιστά δυνατή την ανακάλυψη ομάδων αυθαίρετου σχήματος. Επιπρόσθετα, προτείνεται ένα στατιστικό τεστ για τον καθορίσμο των μονοτροπικών ζευγών και η ομαδοποίηση επιτυγχάνεται μέσω του εντοπισμού των συνδεδεμένων συνιστωσών στον γράφο μονοτροπικότητας. Με τον τρόπο αυτό καθιρίζεται αυτόματα και ο αριθμός των ομάδων. Εκτεταμένα πειράματα σε συνθετικά και πραγματικά σύνολα δεδομένων επικυρώνουν τόσο την ορθότητα της μεθόδου όσο και την πρακτική της αποτελεσματικότητα. Κατόπιν, εισάγουμε το soft silhouette, μια γενίκευση του ευρέως χρησιμοποιούμενου δείκτη silhouette, το οποίο υποστηρίζει πιθανοκρατικές αναθέσεις ομάδων στα δεδομένα. Βασιζόμενοι σε αυτό το διαφορίσιμο κριτήριο, προτείνουμε μια μέθοδο βαθιάς ομαδοποίησης με χρήση autoencoder, η οποία δημιουργεί αναπαραστάσεις που σχηματίζουν ομάδες που είναι ταυτόχρονα συμπαγείς αλλά και σαφώς διαχωρισμένες. Η μέθοδος αξιολογείται σε διάφορα σύνολα δεδομένων και συγκρίνεται με τις πλέον σύγχρονες μεθόδους. Φαίνεται να υπερτερεί έναντι καθιερωμένων προσεγγίσεων βαθιάς ομαδοποίησης, αναδεικνύοντας έτσι την αποτελεσματικότητα του κριτηρίου soft silhouette ως συνάρτηση στόχο για τη βελτίωση της ποιότητας των κρυμμένων αναπαραστάσεων. Τέλος παρουσιάζουμε τη μέθοδο neural implicit maximum likelihood clustering, μια προσέγγιση βασισμένη σε νευρωνικά δίκτυα, η οποία αντιμετωπίζει την ομαδοποίηση ως παραγωγική (generative) διαδικασία στο πλαίσιο της μεθόδου έμμεσης μεγιστοποίησης της πιθανοφάνειας (Implicit Maximum Likelihood Estimation). Προσαρμόζοντας ιδέες από τον αλγόριθμο ClusterGAN, η προτεινόμενη μέθοδος αποφεύγει αρκετές γνωστές αδυναμίες της ομαδοποίησης που βασίζεται στα Generative Adversarial Networks, διατηρώντας παράλληλα έναν απλό και ευσταθή κριτήριο εκπαίδευσης. Η μέθοδος επιτυγχάνει ιδιαίτερα καλά αποτελέσματα σε μικρά σύνολα δεδομένων, με πειραματικές συγκρίσεις τόσο έναντι μεθόδων βαθιάς όσο και συμβατικής ομαδοποίησης. Ένα αξιοσημείωτο πλεονέκτημα της μεθόδου είναι η ικανότητά της να επιλύει ποικίλες γεωμετρίες ομάδων χωρίς να απαιτείται ρύθμιση υπερπαραμέτρων. Πειράματα σε συνθετικά σύνολα δεδομένων δείχνουν ότι η μέθοδος μπορεί να ομαδοποιήσει επιτυχώς τόσο δεδομένα σε μορφή «νέφους» όσο και δεδομένα σε μορφή «δακτυλίου».