Exploratory cluster analysis with jointly optimized feature transformations

Mautz, Dominik (2022): Exploratory cluster analysis with jointly optimized feature transformations. Dissertation, LMU München: Fakultät für Mathematik, Informatik und Statistik

Abstract

Cluster analysis is one of the fundamental tasks in exploratory data mining. Data scientists use cluster analysis to discover previously unknown structures within a data set. Over the years, a vast variety of specialized clustering methods have been developed to deal with the high diversity of data domains, which can be found in industry and science. Clustering methods are the central topic of this cumulative dissertation. We discuss our contribution of five peer-reviewed and published clustering techniques aiming at different applications. The common ground of all proposed methods is the joint optimization of clustering objectives with linear and nonlinear feature transformations. The general idea behind the joint optimization is that a feature transformation can provide a clustering algorithm with a refined representation of the data. In return, the clustering target function provides information on how to improve and refine the data transformation. This joint optimization approach contrasts with the 'classical approach', in which the data scientist first transforms the data and then applies the cluster analysis in a separate step.With extensive experiments using synthetic and real-world data sets, we empirically show that the simultaneous optimization of both objectives has an advantage over separate optimization steps. With the data transformation, we pursue a twofold goal. First, it mitigates the influence of irrelevant, structure-less features on the clustering objective. Second, the transformation often results in a substantial dimensional reduction. This reduction, in turn, promises an easier (visual) inspection of the representation itself, as well as, the structures found by the clustering method. The first contribution is the SubKmeans algorithm. It extends the classic and well-known Lloyd's k-means method in a novel and elegant way to incorporate a linear feature transformation. SubKmeans aims to find a k-means-style clustering partition and transform the clusters linearly into a common, arbitrarily oriented subspace which is optimal for the cluster structures. Our method is able to pursue these two goals simultaneously. The dimensionality of this subspace is found automatically, and therefore the algorithm does not have any additional parameters compared to k-means. At the same time, this subspace helps to mitigate the curse of dimensionality. The second presented clustering method tackles the phenomenon that data in high-dimensional spaces can often be meaningfully clustered in multiple ways. For instance, objects could be grouped either by their shape, their material, or their color. Each of these groupings provides a unique view of the structures contained in the data, which is not covered by the other clusterings. With the Nr-Kmeans clustering algorithm, we follow the approach that different, non-redundant, k-means-like clusterings may exist in different, arbitrarily oriented subspaces of the high-dimensional input space. We assume that these subspaces (and optionally an additional subspace without any cluster structure) are orthogonal to each other. We empirically show that the orthogonality constraint induces the desired non-redundancy. Although Nr-Kmeans can find multiple non-redundant clusterings within a data set, a user must specify the number of clusters within each subspace as an input parameter. With Nr-DipMeans, we propose a method that automatically finds the number of clusters. The only remaining parameter is the number of expected subspaces. Nr-DipMeans harnesses Hartigan's dip test to identify the number of clusters for each subspace under the assumption that clusters follow a unimodal distribution. Deep clustering - the idea of combining deep learning techniques with clustering algorithms - has attracted much interest in recent years. With DeepECT, we contribute a novel method to this research area. DeepECT is the first method to combine a divisive, hierarchical clustering objective with the nonlinear transformation of an auto-encoding neural network (autoencoder). Previous deep clustering methods have only provided the user with a flat-clustering result where the user must specify the number of clusters. However, finding a suitable value for the number of clusters for these methods can be more complicated than in classical clustering settings. The nonlinear embedding adapts almost perfectly to the chosen number of clusters and destroys structural information not captured by the clusters. DeepECT utilizes a specialized optimization procedure that circumvents this problem. The level of detail to be analyzed (i.e., the selected number of clusters) can be chosen afterward and separately for each sub-tree. With the final contribution, we demonstrate that the non-redundant clustering objective of Nr-Kmeans can also be incorporated with deep clustering methods. ENRC is the first non-redundant clustering algorithm that utilizes the nonlinear transformation of an autoencoder. Like Nr-Kmeans, it can find multiple highly-non-redundant clusterings in subspaces of different dimensionality within a data set. In contrast to Nr-Kmeans, which hard-assigns each dimension of the rotated space to one clustering, we use in ENRC a differentiable soft assignment within the autoencoder's embedded space. The autoencoder's nonlinear transformation allows ENRC to cluster complex data sets like image data without the need for any explicit feature engineering.

Abstract

Die Clusteranalyse ist eine der grundlegenden Aufgaben des explorativen Data Minings. Data Scientists verwenden die Clusteranalyse, um bisher unbekannte Strukturen innerhalb eines Datensatzes zu entdecken. Über die Jahre wurden eine Vielzahl spezialisierter Clustering-Methoden entwickelt, welche für die vielfältigen Einsatzbereiche in Industrie und Wissenschaft notwendig sind. Clusterverfahren sind auch das zentrale Thema dieser kumulativen Dissertation. Wir diskutieren fünf von uns veröffentlichte Verfahren, mit welchen wir zu diesem Forschungsfeld beigetragen. Die gemeinsame Grundlage aller vorgeschlagenen Methoden ist die eng verbundene Optimierung einer Clustering-Zielfunktion mit einer linearen bzw. nichtlinearen Merkmalstransformation. Die grundlegende Idee hinter dieser gemeinsamen Optimierung ist, dass die Merkmalstransformation der Clustering-Zielfunktion eine verfeinerte Repräsentation der Strukturen in den Daten liefert. Im Gegenzug liefert die Clustering-Zielfunktion Informationen darüber, wie die Datentransformation verbessert und verfeinert werden kann. Dieser Ansatz der gemeinsamen Optimierung steht im Kontrast zur "klassischen Herangehensweise", bei dem der Data Scientist zunächst die Daten transformiert und dann in einem separaten Schritt die Clusteranalyse anwendet. Durch umfangreiche Experimente zeigen wir mit Hilfe von synthetischen und realen Datensätzen empirisch, dass die gleichzeitige Optimierung beider Ziele einen Vorteil gegenüber der getrennten Optimierung hat. Mit der Datentransformation werden dabei zwei Absichten gleichzeitig verfolgt. Erstens verringert diese den Einfluss irrelevanter, strukturloser Merkmale auf die Clustering-Zielfunktion. Zweitens führt die Transformation häufig zu einer substanziellen Dimensionsreduktion. Diese wiederum verspricht eine leichtere (visuelle) Überprüfung der Transformation selbst, als auch der von der Clustring-Methode gefundenen Strukturen. Der erste wissenschaftliche Beitrag ist der SubKmeans-Algorithmus. Das Verfahren erweitert die klassische und sehr bekannte Lloyd's k-means-Methode auf eine neuartige und elegante Art und Weise, um eine lineare Merkmalstransformation zu integrieren. SubKmeans zielt darauf ab, eine Clustering-Partition im Stil von k-means zu finden sowie die Cluster linear in einen gemeinsamen, beliebig orientierten Unterraum zu transformieren, welcher für die Clusterstrukturen optimal ist. Unsere Methode ist in der Lage, diese beiden Ziele gleichzeitig zu verfolgen. Die Dimensionalität des Unterraums wird automatisch gefunden, weshalb der Algorithmus über keine zusätzlichen Parameter gegenüber k-means verfügt. Gleichzeitig trägt dieser Unterraum dazu bei, den Fluch der Dimensionalität abzuschwächen. Die zweite vorgestellte Clustering-Methode befasst sich mit dem Phänomen, dass Daten in hochdimensionalen Räumen oft auf mehr als eine Weise sinnvoll geclustert werden können. Beispielsweise könnten Objekte entweder nach ihrer Form, ihrem Material oder ihrer Farbe gruppiert werden. Jede dieser Gruppierungen stellt eine einzigartige Sicht auf die in den Daten enthaltenen Strukturen dar, die von den anderen Gruppierungen nicht abgedeckt wird. Mit dem Nr-Kmeans-Clustering-Algorithmus verfolgen wir den Ansatz, dass in verschiedenen, beliebig orientierten Unterräumen des hochdimensionalen Ausgangsraums unterschiedliche, nicht redundante, k-means-ähnliche Clusterings existieren können. Wir gehen davon aus, dass diese Teilräume (und optional ein weiterer Teilraum ohne jegliche Clusterstruktur) orthogonal zueinanderstehen. Wir zeigen empirisch, dass die Orthogonalitätsbeschränkung die gewünschte Nicht-Redundanz induziert. Obgleich Nr-Kmeans mehrere nicht redundante Cluster innerhalb eines Datensatzes finden kann, hat ein Benutzer die Bürde, dass er die Anzahl der Cluster innerhalb jedes Unterraumes als Eingabeparameter angeben muss. Mit Nr-DipMeans schlagen wir eine Methode vor, welche in der Lage ist, die Anzahl der Cluster automatisch zu finden. Der einzige verbleibende Parameter ist die Anzahl der erwarteten Unterräume. Nr-DipMeans macht sich den Dip-Test von Hartigan zunutze, um die Anzahl der Cluster für jeden Unterraum unter der Annahme zu identifizieren, dass Cluster einer unimodalen Verteilung unterliegen. Deep Clustering - die Idee, Techniken des Deep Learings mit Clustering-Algorithmen zu kombinieren - hat in den letzten Jahren großes Interesse gefunden. Mit DeepECT tragen wir eine neuartige Methode zu dieser Forschungsrichtung bei. DeepECT ist die erste Methode, die ein hierarchisches Top-Down-Clustering-Ziel mit der nichtlinearen Transformation eines autocodierenden neuronalen Netzes (Autoencoder) kombiniert. Bisherige Methoden des Deep-Clustering haben dem Benutzer nur ein flaches Clustering-Ergebnis mit einer vorgegebenen Anzahl von Clustern geliefert. Das Finden eines passenden Wertes für die Anzahl von Clustern für diese Art von Methoden kann jedoch komplizierter sein als bei klassischen Clustering-Verfahren. Die nichtlineare Transformation passt sich an die gewählte Clusterzahl nahezu perfekt an und zerstört dabei Strukturinformationen, welche nicht durch die Cluster erfasst werden. DeepECT verwendet ein spezialisiertes Optimierungsverfahren, das dieses Problem umgeht. Der Detailgrad der Analyse (d.h. die gewählte Cluster-Anzahl) kann nachträglich und für jeden Teilbaum separat gewählt werden. Mit dem letzten Clustering Algorithmus zeigen wir, dass das nichtredundante Clusteringziel von Nr-Kmeans auch mit Deep-Clustering Algorithmen umgesetzt werden kann. ENRC ist der erste nicht-redundante Clustering-Algorithmus, welcher die nichtlineare Transformation eines Autoencoders nutzt. Wie Nr-Kmeans kann er in einem Datensatz mehrere hochwertige, nicht-redundante Clustering-Ergebnisse in Unterräumen unterschiedlicher Dimensionalität finden. Im Gegensatz zum Nr-Kmeans Verfahren, welches jede Dimension des eingebetteten Raums einem Clustering fest zuordnet, verwenden wir in ENRC eine differenzierbare weiche Zuordnung. Die nichtlineare Transformation des Autoencoders ermöglicht es ENRC, komplexe Datensätze wie z. B. Bilddaten zu gruppieren, ohne dass ein explizites Feature-Engineering erforderlich ist.

• Dokumententyp: Dissertationen (Dissertation, LMU München)
• Themengebiete: 000 Allgemeines, Informatik, Informationswissenschaft ; 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
• Fakultäten: Fakultät für Mathematik, Informatik und Statistik
• Sprache der Hochschulschrift: Englisch
• Datum der mündlichen Prüfung: 10. Februar 2022
• 1. Bericht­erstatter:in: Böhm, Christian