Machine learning methods based on unimodality testing

Abstract

Recognizing unimodal data distributions is of great significance in statistics, machine learning and data science. The characteristic property of a unimodal distribution is that data values are gathered around a single value (peak), which is the mode of the distribution. Due to this property, data can be characterized as homogeneous, forming a single and coherent group. Well-known distributions, such as Gaussian, Student’s t and Gamma are typical examples of unimodal distributions. Also, the uniform distribution is considered as an extreme unimodal case. Unimodality tests have been proposed to decide on the unimodality of a set of data values, thus providing useful knowledge about the structure of the data. This thesis concerns the development and implementation of machine learning methods based on the notion of unimodality, focusing on four main axes: i) the creation of a new unimodality test for deciding data unimodality, ii) the analysis of key characteristics of data density, such as modes and valleys, which leads to the discovery of innovative properties explored in detail, iii) the development of statistical models, specifically mixture models, for modeling univariate unimodal and multimodal (multiple peaks) data, and iv) the development of partitioning methods for multidimensional data into clusters that are unimodal along each axis, achieved through the unsupervised construction of axis-aligned binary decision trees. We begin, by proposing a new unimodality test called Unimodal Uniform test (UU-test) to decide if a dataset has been generated by a unimodal distribution or not. The method utilizes the empirical distribution function (ecdf) and attempts to obtain a unimodal piecewise linear approximation of the ecdf under the constraint that the data corresponding to each linear segment follow the uniform distribution. Compared to other unimodality tests, it also produces a generative model of the unimodal data in the form of a mixture of uniform distributions (UMM). Thus, it can be used for statistical data modeling of unimodal distributions with arbitrary shape. Next, we improve UMM performance by substituting the uniform distribution with a more flexible and differential one, called Π-sigmoid. The Π-sigmoid distribution, defined as the difference of two translated logistic sigmoids, can approximate a wide range of distributions. We employ and train a mixture model of Π-sigmoids, called UΠsMM, initialized using the output of the UU-test. Additionally, we introduce a mechanism to maintain the unimodality of the model during training via the Expectation-Maximization (EM) algorithm. UΠsMM achieves an accurate fit while often requiring fewer components than UMM. Afterward, we address the problem of modeling univariate multimodal data, with two main contributions. First, we introduce properties of critical points of the data ecdf that provide indications on the existence of density valleys. Using these properties, we propose UniSplit, an algorithm that detects valley points and partitions the dataset into unimodal subsets, automatically estimating their number. Second, we propose a statistical model, the Unimodal Mixture Model (UDMM), which models each unimodal subset with a UMM. A key strength of UDMM is its flexibility and independence from specific parametric assumptions, making it well-suited for datasets generated by sources of different probability density (e.g., one Gaussian and one uniform). Another important property is that the number of components is automatically estimated, therefore, a major issue in mixture modeling is addressed. Finally, we focus on developing an unsupervised method for clustering multidimensional data using decision trees. We introduce the concept of axis unimodal clusters, i.e., clusters where all features are unimodal as decided by a unimodality test. We present a method that constructs binary decision trees, providing axis-aligned partitions of the data and offering interpretable clustering solutions. Two criteria are proposed to identify the best split pair (feature and threshold) at each node, aiming to improve the unimodality of the partition after each split. Compared to other unsupervised decision tree methods, this approach has several advantages: it is simple, avoids preprocessing steps and does not employ computationally expensive optimization methods or difficult to tune hyperparameters, such as number of clusters or maximum tree depth.

Η αναγνώριση μονοτροπικών (unimodal) κατανομών διαδραματίζει σημαντικό ρόλο στη στατιστική, τη μηχανική μάθηση και την ανάλυση δεδομένων. Η χαρακτηριστική ιδιότητα των μονοτροπικών κατανομών είναι ότι τα δεδομένα βρίσκονται πολύ κοντά σε μία τιμή, η οποία είναι η κορυφή (mode/peak) της κατανομής. Εξαιτίας αυτής της ιδιότητας, τα δεδομένα χαρακτηρίζονται ως ομοιογενή, σχηματίζοντας μία συνεκτική ομάδα. Γνωστές κατανομές, όπως οι: Κανονική (Gaussian), Student’s t και Γάμμα είναι παραδείγματα μονοτροπικών κατανομών. Επίσης, η Ομοιόμορφη (uniform) κατανομή είναι μια ακραία περίπτωση μονοτροπικής κατανομής. Τα τελευταία χρόνια έχουν προταθεί τεστ μονοτροπικότητας (unimodality tests) που αποφασίζουν τη μονοτροπικότητα ενός συνόλου δεδομένων, παρέχοντας χρήσιμη γνώση για τη δομή των δεδομένων. Η παρούσα διατριβή επικεντρώνεται στην ανάπτυξη και εφαρμογή μεθόδων μηχανικής μάθησης βασισμένες στην έννοια της μονοτροπικότητας, εστιάζοντας σε τέσσερις βασικούς θεματικούς άξονες: α) τη δημιουργία ενός νέου τεστ μονοτροπικότητας για να αποφασίζουμε σχετικά με τη μονοτροπικότητα των δεδομένων, β) την ανάλυση χαρακτηριστικών της πυκνότητας των δεδομένων, όπως είναι οι κορυφές και οι κοιλάδες (valleys), που οδηγεί στην ανακάλυψη καινοτόμων ιδιοτήτων που θα εξερευνηθούν ενδελεχώς, γ) την ανάπτυξη στατιστικών μοντέλων, συγκεκριμένα μεικτών μοντέλων (mixture models), για μοντελοποίηση μονοδιάστατων μονοτροπικών και πολυτροπικών (πολλαπλές κορυφές) (multimodal) δεδομένων και δ) την ανάπτυξη μεθόδων διαμέρισης πολυδιάστατων δεδομένων σε ομάδες (clusters), ώστε να είναι μονοτροπικά σε κάθε άξονα, η οποία πραγματοποιήθηκε με την κατασκευή χωρίς επίβλεψη παράλληλων με τους άξονες δυαδικών δέντρων απόφασης. Αρχικά, προτείνουμε ένα νέο τεστ μονοτροπικότητας που λέγεται Μονοτροπικό-Ομοιόμορφο τεστ (UU-τεστ) για να αποφασίζουμε εάν ένα σύνολο δεδομένων έχει παραχθεί ή όχι από μονοτροπική κατανομή. Η μέθοδος αυτή χρησιμοποιεί την εμπειρική συνάρτηση κατανομής (ecdf) και προσπαθεί να κατασκευάσει μια μονοτροπική κατά τμήματα γραμμική προσέγγιση (piecewise linear approximation) αυτής υπότον περιορισμό ότι τα δεδομένα που αντιστοιχούν σε κάθε γραμμικό κομμάτι να ακολουθούν ομοιόμορφη κατανομή. Συγκριτικά με άλλα τεστ μονοτροπικότητας, παράγει επίσης ένα μοντέλο για μονοτροπικά δεδομένα που έχει τη μορφή μεικτών ομοιόμορφων κατανομών (UMM). Επομένως, μπορεί να χρησιμοποιηθεί για στατιστική μοντελοποίηση μονοτροπικών κατανομών οποιασδήποτε μορφής. Ακολούθως, βελτιώνουμε την επίδοση του ομοιόμορφου μεικτού μοντέλου αντικαθιστώντας την ομοιόμορφη κατανομή με μια πιο ευέλικτη, που ονομάζεται Π-σιγμοειδή. Η Π-σιγμοειδής κατανομή ορίζεται ως η διαφορά δύο μετατοπισμένων σιγμοειδών και μπορεί να προσεγγίσει ένα ευρύ φάσμα κατανομών. Εκπαιδεύουμε ένα μεικτό μοντέλο Π-σιγμοειδών, που ονομάζεται UΠsMM και αρχικοποιείται χρησιμοποιώντας το αποτέλεσμα του UU-τεστ. Επιπροσθέτως, προτείνουμε ένα μηχανισμό για να διατηρείται η μονοτροπικότητα του μοντέλου κατά τη διάρκεια της εκπαίδευσης με τον αλγόριθμο ΕΜ. Το UΠsMM βελτιώνει την ακρίβεια της μοντελοποίησης, ενώ συχνά απαιτεί λιγότερες συνιστώσες (components) σε σχέση με το ομοιόμορφο μεικτό μοντέλο. Στη συνέχεια, ασχολούμαστε με το πρόβλημα της μοντελοποίησης μονοδιάστατων πολυτροπικών δεδομένων κάνοντας δύο βασικές συνεισφορές. Αρχικά, προτείνουμε ιδιότητες κρίσιμων σημείων της εμπειρικής συνάρτησης κατανομής των δεδομένων, οι οποίες παρέχουν ενδείξεις για την ύπαρξη κοιλάδων στην πυκνότητα των δεδομένων. Χρησιμοποιώντας αυτές τις ιδιότητες, προτείνουμε τον UniSplit, έναν αλγόριθμο που εντοπίζει κοιλάδες και διαμερίζει το σύνολο δεδομένων σε μονοτροπικά υποσύνολα, εκτιμώντας αυτόματα τον αριθμό τους. Ακολούθως, προτείνουμε ένα στατιστικό μοντέλο, το μονοτροπικό μεικτό μοντέλο (UDMM), το οποίο μοντελοποιεί κάθε μονοτροπικό υποσύνολο με ένα ομοιόμορφο μεικτό μοντέλο. Βασικό πλεονέκτημα του μονοτροπικού μεικτού μοντέλου είναι η ευελιξία και η ανεξαρτησία του από συγκεκριμένες παραμετρικές υποθέσεις, καθιστώντας το κατάλληλο για σύνολα δεδομένων που προέρχονται από πηγές διαφορετικής πυκνότητας πιθανότητας (π.χ., μία κανονική και μία ομοιόμορφη). Επιπλέον, ο αριθμός των συνιστωσών υπολογίζεται αυτόματα, αντιμετωπίζοντας έτσι, ένα σημαντικό πρόβλημα των μεικτών μοντέλων. Τέλος, εστιάζουμε στην ανάπτυξη μια μεθόδου χωρίς επίβλεψη (unsupervised) για ομαδοποίηση (clustering) πολυδιάστατων δεδομένων χρησιμοποιώντας δέντρα απόφασης σε ομάδες μονοτροπικές σε κάθε άξονα (axis unimodal), δηλαδή ομάδες όπου όλα τα χαρακτηριστικά τους είναι μονοτροπικά, σύμφωνα με τις αποφάσεις ενός τεστ μονοτροπικότητας. Αυτή η μέθοδος κατασκευάζει δυαδικά δέντρα απόφασης, παρέχοντας διαμερίσεις των δεδομένων παράλληλες με τους άξονες και προσφέροντας ερμηνεύσιμες λύσεις ομαδοποίησης. Δύο κριτήρια προτείνονται για να εντοπίσουμε το καλύτερο ζεύγος διάσπασης (χαρακτηριστικό και τιμή) σε κάθε κόμβο του δέντρου, στοχεύοντας στην βελτίωση της μονοτροπικότητας της διαμέρισης μετά από κάθε διάσπαση. Συγκριτικά με άλλες μεθόδους δέντρων απόφασης χωρίς επίβλεψη, αυτή η προσέγγιση έχει αρκετά πλεονεκτήματα: είναι απλή, αποφεύγει βήματα προεπεξεργασίας και δεν χρησιμοποιεί ακριβές υπολογιστικά μεθόδους βελτιστοποίησης ή πολλές υπερπαραμέτρους, όπως είναι ο αριθμός των ομάδων και το μέγιστο βάθος του δέντρου.