Clustering hochdimensionaler Daten

Clustering hochdimensionaler Daten ist die Clusteranalyse von Daten mit einigen Dutzend bis zu vielen Tausend Dimensionen . Solche hochdimensionalen Datenräume treten häufig in Bereichen wie der Medizin auf , wo die DNA-Microarray -Technologie viele Messungen gleichzeitig ermöglicht, und beim Clustering von Textdokumenten , wo die Anzahl der Dimensionen – bei Verwendung eines Wortfrequenzvektors – der Größe des Vokabulars entspricht .

Für das Clustering in hochdimensionalen Daten müssen vier Probleme überwunden werden: ^{[ 1 ].}

• Mehrdimensionale Systeme sind schwer zu denken, unmöglich zu visualisieren, und aufgrund des exponentiellen Wachstums der möglichen Werte mit jeder Dimension wird die vollständige Aufzählung aller Unterräume mit zunehmender Dimensionalität praktisch unmöglich. Dieses Problem ist als Fluch der Dimensionalität bekannt .
• Mit zunehmender Dimensionszahl wird der Distanzbegriff ungenauer, da die Distanz zwischen je zwei Punkten in einem gegebenen Datensatz konvergiert. Insbesondere die Unterscheidung zwischen dem nächsten und dem entferntesten Punkt verliert ihre Bedeutung.

${\displaystyle \lim _{d\to \infty }{\frac {{\mathit {dist}}_{\max }-{\mathit {dist}}_{\min }}{{\mathit {dist}}_{\min }}}=0}$

• Ein Cluster dient dazu, verwandte Objekte anhand ihrer Attributwerte zu gruppieren. Bei einer großen Anzahl von Attributen sind jedoch einige davon für einen bestimmten Cluster in der Regel nicht aussagekräftig. Beispielsweise kann ein Cluster im Neugeborenen-Screening Neugeborene mit ähnlichen Blutwerten identifizieren, was Aufschluss über die Relevanz bestimmter Blutwerte für eine Krankheit geben kann. Bei unterschiedlichen Krankheiten können jedoch unterschiedliche Blutwerte einen Cluster bilden, während andere Werte unkorreliert sein können. Dies ist als Problem der lokalen Merkmalsrelevanz bekannt : Unterschiedliche Cluster können in verschiedenen Teilräumen liegen, weshalb eine globale Filterung der Attribute nicht ausreicht.
• Bei einer großen Anzahl von Attributen ist es wahrscheinlich, dass einige Attribute korreliert sind . Daher könnten Cluster in beliebig orientierten affinen Unterräumen existieren .

Jüngste Forschungsergebnisse deuten darauf hin, dass Diskriminierungsprobleme nur dann auftreten, wenn eine hohe Anzahl irrelevanter Dimensionen vorliegt, und dass Ansätze mit gemeinsamen nächsten Nachbarn die Ergebnisse verbessern können. ^{[ 2 ]}

Ansätze zur Clusteranalyse in achsenparallelen oder beliebig orientierten affinen Unterräumen unterscheiden sich in ihrer Interpretation des übergeordneten Ziels, nämlich der Clusterfindung in hochdimensionalen Daten. ^{[ 1 ]} Ein völlig anderer Ansatz besteht darin, Cluster anhand von Mustern in der Datenmatrix zu finden, oft als Biclustering bezeichnet . Diese Technik wird häufig in der Bioinformatik eingesetzt .

Subspace-Clustering zielt darauf ab, Cluster in verschiedenen Kombinationen von Dimensionen (d. h. Subräumen) zu finden und geht im Gegensatz zu vielen anderen Clustering-Ansätzen nicht davon aus, dass alle Cluster eines Datensatzes in denselben Dimensionen liegen. ^{[ 3 ]} Subspace-Clustering kann Bottom-up- oder Top-down-Ansatz verfolgen. Bottom-up-Methoden (wie CLIQUE) identifizieren relevante Dimensionen heuristisch, indem sie den Datenraum in eine Gitterstruktur unterteilen, dichte Einheiten auswählen und diese dann iterativ verbinden, sofern sie benachbart und dicht sind. ^{[ 3 ]}

Das nebenstehende Bild zeigt einen zweidimensionalen Raum, in dem mehrere Cluster identifiziert werden können. In den eindimensionalen Unterräumen befinden sich die Cluster (im Unterraum ) und , , (im Unterraum ). kann in einem zweidimensionalen (Unter-)Raum nicht als Cluster betrachtet werden, da es entlang der Achse zu dünn verteilt ist. In zwei Dimensionen lassen sich die beiden Cluster und identifizieren. ${\displaystyle c_{a}}$${\displaystyle \{x\}}$${\displaystyle c_{b}}$${\displaystyle c_{c}}$${\displaystyle c_{d}}$${\displaystyle \{y\}}$${\displaystyle c_{c}}$${\displaystyle x}$${\displaystyle c_{ab}}$${\displaystyle c_{ad}}$

Das Problem des Subspace-Clusterings ergibt sich aus der Tatsache, dass ein Raum mit n Dimensionen verschiedene Subräume besitzt. Sind die Subräume nicht achsenparallel, ist eine unendliche Anzahl von Subräumen möglich. Daher verwenden Subspace-Clustering-Algorithmen Heuristiken, um rechentechnisch effizient zu bleiben, was jedoch zu schlechteren Ergebnissen führen kann. Beispielsweise kann die Abwärtsabschluss-Eigenschaft (vgl. Assoziationsregeln ) genutzt werden, um höherdimensionale Subräume durch die Kombination niedrigdimensionaler zu konstruieren, da jeder Subraum T, der einen Cluster enthält, auch einen vollständigen Raum S erzeugt, der diesen Cluster enthält (d. h. S ⊆ T). Diesen Ansatz verfolgen die meisten traditionellen Algorithmen wie CLIQUE ^{[ 4 ]} und SUBCLU ^{[ 5 ]} . Alternativ kann ein Subraum auch durch die Verwendung unterschiedlicher Relevanzgrade für jede Dimension definiert werden, ein Ansatz, der von iMWK-Means ^{[ 6 ]} , EBK-Modes ^{[ 7 ] und CBK-Modes [ 8 ]} verwendet wird .${\displaystyle 2^{d}}$${\displaystyle d}$

Beim projizierten Clustering wird versucht, jedem Punkt einen eindeutigen Cluster zuzuordnen, wobei Cluster in unterschiedlichen Teilräumen existieren können. Der allgemeine Ansatz besteht darin, eine spezielle Distanzfunktion zusammen mit einem regulären Clustering-Algorithmus zu verwenden .

Der PreDeCon-Algorithmus prüft beispielsweise, welche Attribute für jeden Datenpunkt eine Clusterbildung begünstigen, und passt die Distanzfunktion so an, dass Dimensionen mit geringer Varianz verstärkt werden. ^{[ 9 ]} In der obigen Abbildung könnte das Cluster mithilfe von DBSCAN und einer Distanzfunktion gefunden werden, die die x-Achse weniger stark gewichtet und somit die geringe Differenz auf der y-Achse ausreichend hervorhebt, um die Punkte zu einem Cluster zusammenzufassen. ${\displaystyle c_{c}}$${\displaystyle x}$${\displaystyle y}$

PROCLUS verwendet einen ähnlichen Ansatz mit k-Medoid -Clustering. ^{[ 10 ]} Zunächst werden initiale Medoide geschätzt, und für jedes Medoid wird der von Attributen mit geringer Varianz aufgespannte Unterraum bestimmt. Punkte werden dem nächstgelegenen Medoid zugeordnet, wobei bei der Distanzbestimmung nur dessen Unterraum berücksichtigt wird. Anschließend verläuft der Algorithmus wie der reguläre PAM- Algorithmus.

Wenn die Distanzfunktion Attribute unterschiedlich gewichtet, jedoch niemals mit 0 (und somit auch niemals irrelevante Attribute auslässt), wird der Algorithmus als „weicher“ projizierter Clustering-Algorithmus bezeichnet .

Das projektionsbasierte Clustering beruht auf der nichtlinearen Projektion hochdimensionaler Daten in einen zweidimensionalen Raum. ^{[ 11 ]} Typische Projektionsverfahren wie t-SNE (t- distributed Stochastic Neighbor Embedding ) ^{[ 12 ]} oder NerV (Neighbor Retrieval Visualizer) ^{[ 13 ]} projizieren die Daten explizit in zwei Dimensionen, wobei höherdimensionale Unterräume unberücksichtigt bleiben und nur relevante Nachbarschaften in den hochdimensionalen Daten erhalten werden. Anschließend wird der Delaunay-Graph ^{[ 14 ]} zwischen den projizierten Punkten berechnet. Jeder Knoten zwischen zwei projizierten Punkten wird mit dem Abstand zwischen den entsprechenden hochdimensionalen Datenpunkten gewichtet. Danach wird der kürzeste Pfad zwischen jedem Punktepaar mithilfe des Dijkstra-Algorithmus berechnet . ^{[ 15 ]} Die kürzesten Pfade werden dann im Clustering-Prozess verwendet, der je nach Strukturtyp der hochdimensionalen Daten zwei Optionen beinhaltet. ^{[ 11 ]} Diese Entscheidung kann anhand der topografischen Karte hochdimensionaler Strukturen getroffen werden. ^{[ 16 ]} In einem Vergleich von 34 vergleichbaren Clustering-Methoden war das projektionsbasierte Clustering der einzige Algorithmus, der stets die hochdimensionale, distanz- oder dichteabhängige Struktur des Datensatzes ermitteln konnte. ^{[ 11 ]} Das projektionsbasierte Clustering ist im Open-Source-R-Paket „ProjectionBasedClustering“ auf CRAN verfügbar. ^{[ 17 ]}

Bootstrap-Aggregation (Bagging) ermöglicht die Bildung mehrerer Cluster und die Aggregation der Ergebnisse. Dazu werden zufällige Teilstichproben der Daten gezogen, für jede eine Clusteranalyse durchgeführt und die Ergebnisse anschließend aggregiert, um ein Unähnlichkeitsmaß zu generieren. Dieses kann dann zur Untersuchung und Clusterung der Originaldaten verwendet werden. ^{[ 18 ] [ 19 ]} Da hochdimensionale Daten häufig viele nicht-informative Merkmale aufweisen, können während des Bagging-Prozesses Gewichtungen verwendet werden, um den Einfluss der informativeren Aspekte zu erhöhen. Dies führt zu „ABC-Unähnlichkeiten“, die zur Untersuchung und Clusterung der Originaldaten sowie zur Beurteilung der Merkmale mit dem größten Einfluss auf die Clusterbildung genutzt werden können. ^{[ 20 ] [ 21 ] [ 22 ]}

Nicht alle Algorithmen versuchen, jedem Punkt eine eindeutige Clusterzuordnung zu geben oder alle Cluster in allen Unterräumen zu finden; viele begnügen sich mit einem Zwischenergebnis, bei dem eine Anzahl möglicherweise überlappender, aber nicht unbedingt vollständiger Clustermengen gefunden wird. Ein Beispiel hierfür ist FIRES, das von seinem Grundansatz her ein Subspace-Clustering-Algorithmus ist, aber eine zu aggressive Heuristik verwendet, um alle Subspace-Cluster zuverlässig zu erzeugen. ^{[ 23 ]} Ein weiterer hybrider Ansatz besteht darin, menschliche Expertise in den algorithmischen Prozess einzubinden: Menschliches Fachwissen kann durch heuristische Stichprobenauswahl dazu beitragen, den exponentiell wachsenden Suchraum zu reduzieren. Dies kann im Gesundheitswesen von Vorteil sein, wo beispielsweise Ärzte mit hochdimensionalen Beschreibungen von Patientenzuständen und Messungen zum Erfolg bestimmter Therapien konfrontiert sind. Eine wichtige Frage bei solchen Daten ist der Vergleich und die Korrelation von Patientenzuständen und Therapieergebnissen sowie Kombinationen von Dimensionen. Die Anzahl der Dimensionen ist oft sehr groß, daher müssen sie auf eine kleinere Anzahl relevanter Dimensionen abgebildet werden, um eine bessere Analyse durch Experten zu ermöglichen. Dies liegt daran, dass irrelevante, redundante und widersprüchliche Dimensionen die Effektivität und Effizienz des gesamten Analyseprozesses negativ beeinflussen können. ^{[ 24 ]}

Eine weitere Art von Unterräumen wird beim Korrelationsclustering (Data Mining) betrachtet .

• ELKI umfasst verschiedene Subspace- und Korrelationsclustering-Algorithmen.
• FCPS umfasst über fünfzig Clustering-Algorithmen ^{[ 25 ].}