Clustering in transformed feature spaces by analyzing distinct modes

Leiber, Collin (2024): Clustering in transformed feature spaces by analyzing distinct modes. Dissertation, LMU München: Fakultät für Mathematik, Informatik und Statistik

Abstract

The ability to extract valuable information from data is becoming increasingly relevant due to the growing number of available data sets. Since annotating data is very costly, methods that provide this information without any annotations are of particular interest. However, so-called clustering methods, which identify groups of objects with similar characteristics, often run into problems when working with extensive data sets or data sets with numerous features. Therefore, we require new methods that return high-quality results even when working with large, high-dimensional data. A common practice is to accompany the clustering process with a dimensionality reduction, leading to a simplified data set consisting only of those features that contain valuable information for the cluster analysis. If this dimensionality reduction occurs through a linear transformation, it is usually referred to as subspace clustering. Here, intermediate clustering results can significantly influence the resulting features. This ability is in contrast to a simple, preceding dimensionality reduction. When discussing subspace clustering, one must distinguish between traditional methods that define a separate subspace for each cluster and those that create a common feature space for all clusters. In this dissertation, we only deal with common subspace approaches, as they preserve the comparability between the clusters. One can go one step further and create multiple common subspaces for multiple clustering results, which is the case with so-called non-redundant clustering methods. Applying those approaches is often challenging because suitable parameters for the dimensionalities of the subspaces and the number of clusterings and clusters per clustering have to be defined. We tackle this problem by using the current modes in each subspace to encode the data and apply the Minimum Description Length principle. Here, the model with the minimum encoding cost is assumed to be the best solution. Existing modes are further analyzed by utilizing statistical modality tests, such as the Dip-test of unimodality. The Dip-test outputs a Dip-value that describes the deviation of an empirical cumulative distribution function to an arbitrary unimodal distribution. Using a novel transformation function, we can further state how likely a unimodal or multimodal distribution is to be present, which helps to interpret the Dip-value better. Due to the differentiability of this function, it is used to identify projection axes that show a high degree of multimodality within the clusters. Combining these axes, one obtains a lower-dimensional feature space containing the main modes within the data set, where each mode defines a separate cluster. For complex data sets, there is a need for more powerful processes than linear transformations to obtain suitable feature spaces for clustering. Non-linear transformations using neural networks are often applied in these cases. The combination of clustering and neural networks is known as deep clustering. Such methods directly integrate the clustering approach into the optimization function of, e.g., an autoencoder. Once again, the problem arises of selecting a suitable value for the number of clusters. A solution is to overestimate the initial number of clusters deliberately and, based on the current modalities obtained by the Dip-test, decide whether two clusters can be merged. The embedding then adapts to the existing clustering structure. As a result, the number of clusters does not have to be known in advance but is learned by the algorithm. Further analyses show that the Dip-test can be directly used to optimize an autoencoder. For this purpose, we utilize the gradient of the Dip-test to train the parameters of an autoencoder and identify high-quality clustering results. Thus, no specific distribution function for the embedded data must be assumed apriori. The only assumption is that each cluster adopts a unimodal and each pair of clusters a multimodal structure, which is a relaxation compared to established methods. The described approaches fulfill their goal of identifying informative structures in large, high-dimensional data sets without requiring any annotations. Compared to competitor methods, they achieve state-of-the-art results, while the parameterization is greatly simplified. All methods presented in this thesis are provided in our open-source package ClustPy.

Abstract

Die Fähigkeit wertvolle Informationen aus Daten zu extrahieren, wird aufgrund der wachsenden Anzahl an verfügbaren Datensätzen immer wichtiger. Da die Annotation von Daten sehr kostspielig ist, sind insbesondere Methoden interessant, die diese Informationen ohne vordefinierte Annotationen ausgeben. Sogenannten Clustering-Methoden, die automatisiert Gruppen von Objekten mit ähnlichen Charakteristiken identifizieren, stoßen jedoch häufig beim Arbeiten mit sehr großen Datensätzen oder Datensätzen mit einer Vielzahl von Merkmalen auf Probleme. Es werden daher neue Methoden benötigt, die auch bei großen, hochdimensionalen Daten qualitativ hochwertige Ergebnisse liefern. Eine gängige Praxis ist es, den Clustering-Prozess mit einer Dimensionsreduktion zu kombinieren. Dies führt zu einem vereinfachten Datensatz, der nur aus denjenigen Merkmalen besteht, die wertvolle Informationen für die Clusteranalyse enthalten. Erfolgt diese Reduktion der Dimensionen durch eine lineare Transformation, so spricht man vom Subspace Clustering. Im Gegensatz zu einer einfachen, vorangehenden Dimensionsreduktion können beim Subspace Clustering die Zwischenergebnisse des Clusterings die resultierenden Merkmale erheblich beeinflussen. Bei der Betrachtung vom Subspace Clustering muss man zwischen traditionellen Methoden, die für jedes Cluster einen eigenen Unterraum definieren, und solchen, die einen gemeinsamen Merkmalsraum für alle Cluster erstellen, unterscheiden. In dieser Dissertation befassen wir uns nur mit Subspace Verfahren, die einen einzelnen Unterraum erstellen, da sie eine bessere Vergleichbarkeit zwischen den Clustern bieten. Man kann noch einen Schritt weiter gehen und mehrere solcher Unterräume für mehrere Clustering-Ergebnisse erstellen. Dies ist bei sogenannten nicht-redundanten Clustering-Methoden der Fall. Die Ausführung dieser Ansätze ist oft eine Herausforderung, da geeignete Parameter für die Dimensionalität der Unterräume und die Anzahl der Clusterings und Cluster pro Clustering definiert werden müssen. Wir gehen dieses Problem an, indem wir die aktuellen Modi in jedem Unterraum zur Kodierung der Daten verwenden und das Minimum Description Length Prinzip anwenden. Dabei wird angenommen, dass das Modell mit den geringsten Kodierungskosten die beste Lösung darstellt. Vorhandene Modi werden ebenfalls durch statistische Modalitätstests, wie dem Dip-Test der Unimodalität, analyisert. Der Dip-Test liefert einen Dip-Wert, der den Abstand zwischen einer empirische Verteilungsfunktion zu einer beliebigen unimodalen Verteilung angibt. Mithilfe einer neuartigen Transformationsfunktion können wir außerdem angeben, wie wahrscheinlich es ist, dass eine unimodale oder multimodale Verteilung vorliegt, wodurch der Dip-Wert besser interpretierbar ist. Aufgrund der Differenzierbarkeit dieser Funktion wird sie weiter dazu verwendet, Projektionsachsen zu identifizieren, die einen hohen Grad an Multimodalität innerhalb der vorhandenen Cluster aufweisen. Kombiniert man diese Achsen, erhält man einen niedrigdimensionalen Merkmalsraum, der die wesentlichen Modi innerhalb des Datensatzes enthält, wobei jeder Modus ein eigenes Cluster definiert. Für komplexe Datensätze benötigen wir leistungsfähigere Verfahren als lineare Transformationen, um geeignete Merkmalsräume für das Clustering zu erhalten. Nichtlineare Transformationen unter Verwendung neuronaler Netze werden häufig in diesen Fällen angewandt. Diese Kombination aus Clustering und neuronalen Netzen wird als Deep Clustering bezeichnet. Solche Methoden integrieren den Clustering-Vorgang direkt in die Optimierungsfunktion bspw. eines Autoencoders. Auch hier stellt sich das Problem, einen geeigneten Wert für die Anzahl der Cluster zu wählen. Eine Lösung besteht darin, die anfängliche Anzahl der Cluster bewusst zu überschätzen und auf der Grundlage der aktuellen Modalitäten, die durch den Dip-Test ermittelt werden, zu entscheiden, ob zwei Cluster zusammengefasst werden können. Das Embedding passt sich dann an die vorhandene Clusterstruktur an. Dadurch muss die Anzahl der Cluster nicht im Voraus bekannt sein, sondern wird vom Algorithmus selbstständig erlernt. Weitere Analysen zeigen, dass der Dip-Test direkt zum Optimieren eines Autoencoders verwendet werden kann. Hierzu nutzen wir den Gradienten des Dip-Tests zum Trainieren der Parameter eines Autoencoders und für die Identifikation hochwertiger Clustering-Ergebnisse. Es muss keine spezifische Verteilungsfunktion für die transformierten Daten vorausgesetzt werden. Die einzige Annahme ist, dass jedes Cluster eine unimodale und jedes Clusterpaar eine multimodale Struktur annimmt. Dies stellt eine Reduzierung der Annahmen gegenüber etablierten Methoden dar. Die beschriebenen Ansätze erfüllen ihr Ziel, informative Strukturen in großen, hochdimensionalen Datensätzen zu identifizieren, ohne dass Annotationen erforderlich sind. Im Vergleich zu konkurrierenden Methoden erzielen sie sehr gute Ergebnisse, wobei die Parametrisierung stark vereinfacht ist. Alle in dieser Arbeit vorgestellten Verfahren, werden durch unser Open-Source-Paket ClustPy bereitgestellt.

• Dokumententyp: Dissertationen (Dissertation, LMU München)
• Keywords: Clustering, Deep Clustering, Subspace Clustering, Non-redundant Clustering, Feature Transformation, Dimensionality Reduction, Autoencoder, Hartigan’s Dip-test of Unimodality, Minimum Description Length
• 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: 16. April 2024
• 1. Bericht­erstatter:in: Böhm, Christian