Clustering using similarity and kernel matrices

Abstract

This thesis studies the (unsupervised) clustering problem, which aims at partitioning a dataset into groups, called clusters, such that instances falling in the same cluster are similar to each other and dissimilar to those of other clusters according to some similarity/dissimilarity measure. Specifically, this thesis concerns the development, implementation and evaluation of clustering methodologies, mainly focusing on three different axes: i) proximity-based clustering, where only the pairwise proximity matrix (i.e. similarity or distance matrix) of the data is available during training and not the instances themselves, ii) multi-view learning, where for the same instances multiple representations (views) are available, coming from different sources and/or feature spaces and iii) multiple kernel learning, where a kernel that suits the data is learned together with the cluster assignments. Usually, the kernel is parametrized as a combination of some predefined kernels, called basis kernels, and we wish to infer appropriate values for the combination parameters.We begin, by presenting an approach that tackles the initialization problem of the k-means algorithm by altering its sum of the intra-cluster variances objective. Weights are assigned to the clusters in proportion to their variance, which predispose the optimization towards primarily minimizing those clusters, that in the current iteration, exhibit large intra-cluster variance. In this way, the solution space is gradually restricted towards clusters with similar variances, allowing our method to systematically produce higher quality partitionings than k-means, while restarted from random initial centers. Moreover, we adapt our approach to perform clustering in kernel space, by altering the objective of the kernel k-means algorithm. The kernel space extension requires only the kernel matrix and not the instances as input, i.e. it is a proximity-based method.Afterward, we consider the problem of unsupervised multi-view learning. Our main contribution in this field is the assignment of weights to the views, which are automatically tuned to reflect the quality of the views and determine their contribution to the clustering solution accordingly. The majority of multi-view approaches treat all available views as being equally important, which may lead to a considerable drop in performance if degenerate views (e.g. noisy views) exist in the dataset. Analytically, we present two different methodologies for the above problem. In the first case, views are represented by convex mixture models and we develop an algorithm that associates a weight with each view and another that does not employ view weights. In the second case, each view is represented by a kernel matrix and a weighted combination of those kernel matrices is learned. This formulation includes a parameter that controls the sparsity of the weights, allowing its adaptation to the dataset.Finally, we focus on multiple kernel learning, where most of the existing clustering approaches of this type exploit the large margin principle of SVM and perform learning by maximizing the margin. Instead, here, we propose an objective that utilizes the ratio between the margin and the intra-cluster variance. Since the objective explicitly takes into account both the separation (margin) and the compactness (intra-cluster variance) of the clusters, higher quality solutions can be possibly attained compared to approaches that rely solely on either of the two. Moreover, it has been shown that the margin alone is an unsuitable measure of the goodness of the learned kernel, as it can become arbitrary large by simply scaling the kernel. We prove that our ratio-based objective is invariant to kernel scaling and, also, that its global optimum solution is invariant to the type of norm constraint on the kernel parameters. Experiments verify the properties of our objective and reveal the superior clustering performance of the proposed multiple kernel formulation.

Η παρούσα διατριβή μελετά το πρόβλημα της ομαδοποίησης (clustering), που έχει ως στόχο τον διαχωρισμό ενός συνόλου δεδομένων σε ομάδες (clusters), χωρίς τη χρήση επίβλεψης, ώστε τα δεδομένα που ανήκουν στη ίδια ομάδα να είναι όμοια μεταξύ τους και ανόμοια με αυτά των άλλων ομάδων, βάσει ενός μέτρου ομοιότητας/ανομοιότητας. Συγκεκριμένα, η διατριβή επικεντρώνεται στην παρουσίαση μεθόδων ομαδοποίησης που αφορούν τρεις βασικούς θεματικούς άξονες: α) την ομαδοποίηση δεδομένων για τα οποία έχουμε διαθέσιμο μόνο τον πίνακα εγγύτητας και όχι τα ίδια τα δεδομένα (proximity-based clustering), β) την μάθηση με πολλαπλές όψεις (multi-view learning), όπου για τα ίδια δεδομένα έχουμε στη διάθεσή μας πολλαπλές αναπαραστάσεις (όψεις) που προέρχονται από διαφορετικές πηγές ή/και διαφορετικούς χώρους χαρακτηριστικών και γ) την μάθηση με πολλαπλούς πυρήνες (multiple kernel learning), όπου ταυτόχρονα με την ομαδοποίηση θέλουμε να μάθουμε και τον κατάλληλο πυρήνα (kernel) για τα δεδομένα. Συνήθως ο πυρήνας παραμετροποιείται ως ένας συνδυασμός από δοθέντες πυρήνες (basis kernels) και στοχεύουμε στην μάθηση κατάλληλων τιμών για τις παραμέτρους του συνδυασμού.Αρχικά προτείνεται μια μέθοδος για την αντιμετώπιση του γνωστού προβλήματος της αρχικοποίησης (initialization problem), από το οποίο πάσχει ο αλγόριθμος k-means. Συγκεκριμένα, τροποποιούμε το κριτήριο (objective function) του k-means έτσι ώστε να δίδεται μεγαλύτερη έμφαση στην ελαχιστοποίηση των ομάδων που στην τρέχουσα επανάληψη εμφανίζουν μεγάλη διακύμανση (intra-cluster variance). Κατ’ αυτόν τον τρόπο ο χώρος λύσεων σταδιακά περιορίζεται σε ομάδες που εμφανίζουν παρεμφερή διακύμανση, το οποίο επιτρέπει στη μέθοδό μας να εντοπίζει σε συστηματική βάση λύσεις καλύτερης ποιότητας σε σχέση με τον k-means, καθώς επανεκκινείται από τυχαία αρχικά κέντρα. Επιπλέον, παρουσιάζεται η προσαρμογή της μεθόδου ώστε να μπορεί να εφαρμοστεί για ομαδοποίηση με πίνακα ομοιότητας (kernel matrix), τροποποιώντας το κριτήριο του αλγορίθμου kernel k -means.Στη συνέχεια, η διατριβή εστιάζεται στο πρόβλημα της ομαδοποίησης με πολλαπλές όψεις. Η βασική συνεισφορά στο αντικείμενο αυτό σχετίζεται με την ανάθεση βαρών στις όψεις, τα οποία μαθαίνονται αυτόματα και τα οποία αντικατοπτρίζουν την ποιότητα των όψεων. Οι υπάρχουσες προσεγγίσεις θεωρούν όλες τις όψεις εξίσου σημαντικές, κάτι που μπορεί να οδηγήσει σε σημαντική μείωση της απόδοσης εάν υπάρχουν εκφυλισμένες όψεις (π.χ. όψεις με θόρυβο) στο σύνολο δεδομένων. Ειδικότερα, παρουσιάζονται για το ανωτέρω πρόβλημα δύο διαφορετικές μεθοδολογίες. Στην πρώτη περίπτωση αναπαριστούμε τις όψεις μέσω κυρτών μικτών μοντέλων (convex mixture models) λαμβάνοντας υπόψη τις διαφορετικές στατιστικές ιδιότητές τους και παρουσιάζουμε έναν αλγόριθμο με βάρη στις όψεις και έναν χωρίς βάρη. Στην δεύτερη περίπτωση αναπαριστούμε την κάθε όψη μέσω ενός πίνακα ομοιότητας (kernel matrix) και μαθαίνουμε ένα συνδυασμό με βάρη από τους πίνακες αυτούς. Το προτεινόμενο μοντέλο διαθέτει μία παράμετρο που ελέγχει την αραιότητα των βαρών, επιτρέποντας την καλύτερη προσαρμογή του συνδυασμού στα δεδομένα.Η τελευταία ενότητα της διατριβής αφορά στην ομαδοποίηση με πολλαπλούς πυρήνες, όπου συνήθως το κριτήριο που βελτιστοποιείται είναι το εύρος (margin) της λύσης, όπως είναι γνωστό από τον ταξινομητή SVM (support vector machine). Στην προσέγγιση που προτείνεται, βελτιστοποιείται ο λόγος μεταξύ του εύρους και της διακύμανσης (intra-cluster variance) των ομάδων, λαμβάνοντας έτσι υπόψη τόσο τον διαχωρισμό (separability) τους όσο και το πόσο συμπαγείς (compactness) είναι οι ομάδες, το οποίο δύναται να οδηγήσει σε καλύτερες λύσεις. Έχει δειχθεί ότι το εύρος από μόνο του δεν επαρκεί ως κριτήριο για την μάθηση του κατάλληλου πυρήνα, καθότι μπορεί να γίνει αυθαίρετα μεγάλο μέσω μίας απλής κλιμάκωσης (scaling) του πυρήνα. Αντιθέτως, το κριτήριο που προτείνουμε είναι αμετάβλητο (invariant) σε κλιμακώσεις του πυρήνα και, επιπλέον, το ολικό του βέλτιστο είναι αμετάβλητο ως προς τον τύπο της νόρμας που εφαρμόζεται στους περιορισμούς (constraints) των παραμέτρων του πυρήνα. Τα πειραματικά αποτελέσματα επιβεβαιώνουν τις ιδιότητες του κριτηρίου μας, καθώς και τις αναμενόμενες βελτιωμένες επιδόσεις ομαδοποίησης.