Clusteranalyse (Deutsch)

Die Auswertung (oder „Validierung“) von Clusterergebnissen ist ebenso schwierig wie das Clustering selbst. Beliebte Ansätze beinhalten eine „interne“ Bewertung, bei der das Clustering zu einem einzigen Qualitätsfaktor zusammengefasst wird, eine „externe“ Bewertung, bei der das Clustering mit einer vorhandenen „Ground Truth“ – Klassifizierung verglichen wird, eine „manuelle“ Bewertung durch einen menschlichen Experten und eine „indirekte“ Bewertung durch Bewertung des Nutzens des Clusterings in seiner beabsichtigten Anwendung.,

Interne Evaluierungsmaßnahmen leiden unter dem Problem, dass sie Funktionen darstellen, die selbst als Clustering-Ziel gesehen werden können. Zum Beispiel könnte man den Datensatz nach dem Silhouette-Koeffizienten gruppieren; außer dass dafür kein effizienter Algorithmus bekannt ist. Durch die Verwendung eines solchen internen Maßes zur Auswertung vergleicht man eher die Ähnlichkeit der Optimierungsprobleme und nicht unbedingt, wie nützlich das Clustering ist.,

Die externe Bewertung hat ähnliche Probleme: Wenn wir solche „Grundwahrheitsetiketten“ haben, müssten wir uns nicht gruppieren; und in praktischen Anwendungen haben wir normalerweise keine solchen Etiketten. Andererseits spiegeln die Beschriftungen nur eine mögliche Partitionierung des Datensatzes wider, was nicht bedeutet, dass es kein anderes und vielleicht sogar besseres Clustering gibt.

Keiner dieser Ansätze kann daher letztendlich die tatsächliche Qualität eines Clusterings beurteilen, aber dies erfordert eine menschliche Bewertung, die sehr subjektiv ist., Dennoch können solche Statistiken sehr informativ sein, um schlechte Clusterings zu identifizieren, aber man sollte die subjektive menschliche Bewertung nicht ablehnen.

Interne evaluationEdit

Wenn ein Clusterergebnis basierend auf den Daten ausgewertet wird, die selbst gruppiert wurden, wird dies als interne Auswertung bezeichnet. Diese Methoden weisen dem Algorithmus, der Cluster mit hoher Ähnlichkeit innerhalb eines Clusters und geringer Ähnlichkeit zwischen Clustern erzeugt, normalerweise die beste Punktzahl zu., Ein Nachteil der Verwendung interner Kriterien bei der Clusterbewertung besteht darin, dass hohe Punktzahlen bei einer internen Maßnahme nicht notwendigerweise zu effektiven Informationsabrufanwendungen führen. Darüber hinaus ist diese Bewertung auf Algorithmen ausgerichtet, die dasselbe Clustermodell verwenden. Beispielsweise optimiert k-means Clustering auf natürliche Weise Objektabstände, und ein distanzbasiertes internes Kriterium wird das resultierende Clustering wahrscheinlich überbewerten.,

Daher sind die internen Bewertungsmaßnahmen am besten geeignet, um einen Einblick in Situationen zu erhalten, in denen ein Algorithmus eine bessere Leistung als ein anderer erbringt, dies darf jedoch nicht bedeuten, dass ein Algorithmus validere Ergebnisse als ein anderer liefert. Die Gültigkeit, gemessen anhand eines solchen Index, hängt von der Behauptung ab, dass diese Art von Struktur im Datensatz vorhanden ist. Ein Algorithmus, der für irgendeine Art von Modellen entwickelt wurde, hat keine Chance, wenn der Datensatz einen radikal anderen Satz von Modellen enthält oder wenn die Auswertung ein radikal anderes Kriterium misst., Beispielsweise kann k-means Clustering nur konvexe Cluster finden, und viele Bewertungsindizes gehen von konvexen Clustern aus. Bei einem Datensatz mit nicht konvexen Clustern ist weder die Verwendung von k-Mitteln noch ein Bewertungskriterium, das Konvexität annimmt, solide.

Es gibt mehr als ein Dutzend interner Evaluierungsmaßnahmen, die normalerweise auf der Intuition basieren, dass Elemente im selben Cluster ähnlicher sein sollten als Elemente in verschiedenen Clustern., folgende Formel: D B = 1 n ∑ i = 1 n max j ≠ i ( σ i + σ j d ( c i , c j ) ) {\displaystyle DB={\frac {1}{n}}\sum _{i=1}^{n}\max _{j\neq i}\left({\frac {\sigma _{i}+\sigma _{j}}{d(c_{i},c_{j})}}\right)} an, wobei n die Anzahl der Cluster, c i {\displaystyle c_{i}} ist der Schwerpunkt der cluster-i {\displaystyle i} , σ i {\displaystyle \sigma _{i}} ist der mittlere Abstand aller Elemente in cluster i {\displaystyle i} zu s c i {\displaystyle c_{i}} und d ( c i , c j ) {\displaystyle d(c_{i},c_{j})} ist der Abstand zwischen centroide c i {\displaystyle c_{i}} und c j {\displaystyle c_{j}} ., Da Algorithmen, die Cluster mit geringen Intra-Cluster-Entfernungen (hohe Intra-Cluster-Ähnlichkeit) und hohen Inter–Cluster–Entfernungen (niedrige Inter-Cluster-Ähnlichkeit) erzeugen, einen niedrigen Davies-Bouldin-Index aufweisen, wird der Clustering-Algorithmus, der eine Sammlung von Clustern mit dem kleinsten Davies-Bouldin-Index erzeugt, als der beste Algorithmus angesehen, der auf diesem Kriterium basiert.

• Dunn-Index

Der Dunn-Index zielt darauf ab, dichte und gut getrennte Cluster zu identifizieren. Es ist definiert als das Verhältnis zwischen dem minimalen Interclusterabstand und dem maximalen Intra-Cluster-Abstand., Für jede Clusterpartition kann der Dunn-Index nach folgender Formel berechnet werden: D = min 1 ≤ i < j ≤ n d ( i, j ) max 1 ≤ k ≤ n d ‚ ( k), {\displaystyle D={\frac {\min _{1\leq i<j\leq n}d(i, j)}{\max _{1\leq k\leq n}d^{\prime }(k)}}\,,} wobei d(i, j) den Abstand zwischen den Clustern i und j darstellt und d ‚(k) den Intra-Cluster-Abstand des Clusters k misst. Der Inter-Cluster-Abstand d(i,j) zwischen zwei Clustern kann eine beliebige Anzahl von Entfernungsmaßen sein, z. B. der Abstand zwischen den Zentroiden der Cluster., In ähnlicher Weise kann der Intra-Cluster-Abstand d ‚(k) auf verschiedene Arten gemessen werden, wie zum Beispiel der maximale Abstand zwischen einem beliebigen Elementpaar im Cluster k. Da internes Kriterium Cluster mit hoher Intra-Cluster-Ähnlichkeit und geringer Inter-Cluster-Ähnlichkeit sucht, sind Algorithmen, die Cluster mit hohem Dunn-Index erzeugen, wünschenswerter.

• Silhouette-Koeffizient

Der Silhouette-Koeffizient kontrastiert die durchschnittliche Entfernung zu Elementen im selben Cluster mit der durchschnittlichen Entfernung zu Elementen in anderen Clustern., Objekte mit einem hohen Silhouette-Wert gelten als gut gruppiert, Objekte mit einem niedrigen Wert können Ausreißer sein. Dieser Index funktioniert gut mit k-means Clustering und wird auch verwendet, um die optimale Anzahl von Clustern zu bestimmen.

Externe evaluationEdit

In der externen Evaluation werden Clustering-Ergebnisse basierend auf Daten ausgewertet, die nicht für Clustering verwendet wurden, wie z. B. bekannte Klassenbezeichnungen und externe Benchmarks. Solche Benchmarks bestehen aus einer Reihe von vorklassifizierten Elementen, und diese Sätze werden oft von (Experten -) Menschen erstellt., Somit können die Benchmark-Sets als Goldstandard für die Bewertung betrachtet werden. Diese Arten von Auswertemethoden messen, wie nah das Clustering an den vorgegebenen Benchmarkklassen ist. Es wurde jedoch kürzlich diskutiert, ob dies für reale Daten oder nur für synthetische Datensätze mit einer tatsächlichen Grundwahrheit ausreichend ist, da Klassen eine interne Struktur enthalten können, die vorhandenen Attribute möglicherweise keine Trennung von Clustern zulassen oder die Klassen Anomalien enthalten können., Darüber hinaus ist die Reproduktion von bekanntem Wissen aus Sicht der Wissensfindung möglicherweise nicht unbedingt das beabsichtigte Ergebnis. Im speziellen Szenario des eingeschränkten Clusterings, in dem Metainformationen (z. B. Klassenbeschriftungen) bereits im Clustering-Prozess verwendet werden, ist das Halten von Informationen zu Bewertungszwecken nicht trivial.

Aus Varianten zur Bewertung von Klassifizierungsaufgaben werden eine Reihe von Maßnahmen angepasst., Anstelle der Zählung der Häufigkeit, mit der eine Klasse einem einzelnen Datenpunkt korrekt zugewiesen wurde (bekannt als True Positive), bewerten solche Paarzählmetriken, ob sich jedes Paar von Datenpunkten, das sich wirklich im selben Cluster befindet, im selben Cluster befindet.

Wie bei der internen Auswertung gibt es mehrere externe Bewertungsmaßnahmen:125-129 zum Beispiel:

• Reinheit: Reinheit ist ein Maß dafür, inwieweit Cluster eine einzelne Klasse enthalten. Die Berechnung kann wie folgt erfolgen: Zählen Sie für jeden Cluster die Anzahl der Datenpunkte aus der häufigsten Klasse in diesem Cluster., Nehmen Sie nun die Summe über alle Cluster und dividieren Sie durch die Gesamtzahl der Datenpunkte. Formal kann bei einer Reihe von Clustern M {\displaystyle M} und einer Reihe von Klassen D {\displaystyle D} , die beide N {\displaystyle N} – Datenpunkte partitionieren, Folgendes definiert werden:

1 N ∑ m ∈ M max d ∈ D | m ∩ d | {\displaystyle {\frac {1}{N}}\sum _{m\in M}\max _{d\in D}{|m\cap d|}} Diese Maßnahme bestraft nicht, dass viele Cluster vorhanden sind, und mehr Cluster machen Sie es einfacher, eine hohe Reinheit zu produzieren. Ein Reinheitsgrad von 1 ist immer möglich, indem jeder Datenpunkt in einen eigenen Cluster eingefügt wird., Reinheit funktioniert auch nicht gut für unausgeglichene Daten, bei denen selbst schlecht funktionierende Clustering-Algorithmen einen hohen Reinheitswert ergeben. Wenn beispielsweise ein Dataset der Größe 1000 aus zwei Klassen besteht, von denen eine 999 Punkte und die andere 1 Punkt enthält, hat jede mögliche Partition eine Reinheit von mindestens 99,9%.

• Rand-Index

Der Rand-Index berechnet, wie ähnlich die Cluster (vom Clustering-Algorithmus zurückgegeben) den Benchmark-Klassifikationen sind., Es kann mit der folgenden Formel berechnet werden: R I = T P + T N T P + F P + F N + T N {\displaystyle RI={\frac {TP+TN}{TP+FP+FN+TN}} wobei T P {\displaystyle TP} die Anzahl der true Positiven ist, T N {\displaystyle TN} die Anzahl der True Negativen ist, F P {\displaystyle FP} die Anzahl der False Positiven ist und F N {\displaystyle FN} die Anzahl der False Negativen ist. Die hier gezählten Instanzen sind die Anzahl der korrekten paarweisen Zuweisungen., Das heißt, Tp {\displaystyle TP} ist die Anzahl der Paare von Punkten, die in der vorhergesagten Partition und in der Grundwahrheitspartition gruppiert sind, FP {\displaystyle FP} ist die Anzahl der Paare von Punkten, die in der vorhergesagten Partition gruppiert sind, aber nicht in der Grundwahrheitspartition usw. Wenn das dataset ist in der Größe N, dann T P + T N + F P + F N = ( N 2 ) {\displaystyle TP+TN+FP+FN={\binom {N}{2}}} .

Ein Problem mit dem Rand-Index ist, dass falsch Positive und falsch Negative gleichermaßen gewichtet werden. Dies kann ein unerwünschtes Merkmal für einige Clusteranwendungen sein., Die F-Maßnahme befasst sich mit diesem Problem, ebenso wie der zufallskorrigierte bereinigte Rand-Index.

• F-measure

Das F-measure kann verwendet werden, um den Beitrag von false Negative durch Gewichtung Rückruf durch einen Parameter β ≥ 0 {\displaystyle \beta \geq 0} auszugleichen . Lassen Sie Präzision und Rückruf (beide externe Auswertemaßnahmen an sich) wie folgt definiert werden: P = T P T P + F P {\displaystyle P={\frac {TP}{TP+FP}}} R = T P T P + F N {\displaystyle R={\frac {TP}{TP+FN}} wobei P {\displaystyle P} die Genauigkeitsrate und R {\displaystyle R} die Rückrufrate ist., Wir berechnen die F-Messung mithilfe der folgenden Formel: F β = ( β 2 + 1 ) ⋅ P ⋅ R β 2 ⋅ P + R {\displaystyle F_{\beta }={\frac {(\beta ^{2}+1)\cdot P\cdot R}{\beta ^{2}\cdot P+R -}}}, Wenn β = 0 {\displaystyle \beta =0} , F 0 = P {\displaystyle F_{0}=P} . Mit anderen Worten, der Rückruf hat keinen Einfluss auf das F-Maß, wenn β = 0 {\displaystyle \beta =0} und das Erhöhen von β {\displaystyle \beta } dem Rückruf im endgültigen F-Maß eine zunehmende Menge an Gewicht zuweist. Auch T N {\displaystyle TN} wird nicht berücksichtigt und kann von 0 nach oben ohne Bindung variieren.,

• Jaccard index

Der Jaccard Index wird verwendet, um die Ähnlichkeit zwischen zwei Datensätzen zu quantifizieren. Der Jaccard index nimmt einen Wert zwischen 0 und 1. Ein Index von 1 bedeutet, dass die beiden Datensätze identisch sind, und ein Index von 0 gibt an, dass die Datensätze keine gemeinsamen Elemente haben. Der Jaccard-Index wird durch die folgende Formel definiert: J(A , B ) = | A ∩ B | | A ∪ B | = T P + F P + F N {\displaystyle J (A,B)={\frac {|A\cap B|}{|A\cup B|}}={\frac {TP}{TP+FP+FN}} Dies ist einfach die Anzahl der eindeutigen Elemente, die beiden Mengen gemeinsam sind, geteilt durch die Gesamtzahl der eindeutigen Elemente in beiden Sätzen., Auch T N {\displaystyle TN} wird nicht berücksichtigt und kann von 0 nach oben ohne Bindung variieren.

• Würfel-index

Der Würfel symmetrisch Maßnahme verdoppelt sich das Gewicht auf T P {\displaystyle TP}, während Sie noch ignorieren T N {\displaystyle TN} : D S C = 2 T P 2 T P + F P + F N {\displaystyle DSC={\frac {2TP}{2TP+FP+FN}}}

• Fowlkes–Malven-index

Die Fowlkes–Malven-index berechnet die ähnlichkeit zwischen den Clustern wieder durch den clustering-Algorithmus und die benchmark-Klassifikationen., Je höher der Wert des Fowlkes-Mallows-Index ist, desto ähnlicher sind die Cluster und die Benchmark-Klassifikationen. Es kann mit der folgenden Formel berechnet werden: F M = T P T P + F P ⋅ T P T P + F N {\displaystyle FM={\sqrt {{\frac {TP}{TP+FP}}\cdot {\frac {TP}{TP+FN}}}} wobei T P {\displaystyle TP} die Anzahl der true Positiven ist, F P {\displaystyle FP} die Anzahl der False Positiven und F N {\displaystyle FN} die Anzahl der False Negativen ist., Der F M {\displaystyle FM} Index ist das geometrische Mittel der Genauigkeit und des Rückrufs P {\displaystyle P} und R {\displaystyle R} und wird daher auch als G-Maß bezeichnet, während das F-Maß ihr harmonisches Mittel ist. Darüber hinaus sind Präzision und Rückruf auch als Wallaces Indizes B I {\displaystyle B^{I}} und B I I {\displaystyle B^{II}} bekannt . Die normalisierten Versionen von Recall, Precision und G-Measure entsprechen Information, Markedness und Matthews Korrelation und beziehen sich stark auf Kappa.,

• Die gegenseitige Information ist ein informationstheoretisches Maß dafür, wie viele Informationen zwischen einem Clustering und einer Grundwahrheitsklassifikation geteilt werden, die eine nichtlineare Ähnlichkeit zwischen zwei Clusterings erkennen kann. Normalisierte gegenseitige Informationen sind eine Familie korrigierter Varianten, die eine reduzierte Verzerrung für unterschiedliche Clusterzahlen aufweisen.
• Verwirrungsmatrix

Eine Verwirrungsmatrix kann verwendet werden, um die Ergebnisse eines Klassifizierungs – (oder Clustering -) Algorithmus schnell zu visualisieren. Es zeigt, wie unterschiedlich sich ein Cluster vom Goldstandard-Cluster unterscheidet.,

Cluster tendencyEdit

Um Cluster-Tendenz zu messen, ist zu messen, in welchem Grad Cluster in den Daten vorhanden sind, gruppiert werden, und kann als ein erster Test durchgeführt werden, bevor Clustering versucht. Eine Möglichkeit besteht darin, die Daten mit zufälligen Daten zu vergleichen. Im Durchschnitt sollten zufällige Daten keine Cluster haben.

• Hopkins-Statistik

Es gibt mehrere Formulierungen der Hopkins-Statistik. Ein typischer ist wie folgt. Sei X {\displaystyle X} die Menge von n {\displaystyle n} Datenpunkten im Dimensionsraum d {\displaystyle d}., Betrachten Sie eine Stichprobe (ohne Ersatz) von m ≪ n {\displaystyle m\ll n} Datenpunkte mit den Mitgliedern x i {\displaystyle x_{i}} . Generieren Sie auch einen Satz Y {\displaystyle Y} von m {\displaystyle m} gleichmäßig zufällig verteilte Datenpunkte. Definieren Sie nun zwei Entfernungsmaße, u i {\displaystyle u_{i}} der Abstand von y i ∈ Y {\displaystyle y_{i}\in Y} von seinem nächsten Nachbarn in X und w i {\displaystyle w_{i}} der Abstand von x i ∈ X {\displaystyle x_{i}\in X} von seinem nächsten Nachbarn in X., Wir definieren dann die Hopkins-Statistik als: H = ∑ i = 1 m u i d ∑ i = 1 m u i d + ∑ i = 1 m w i d , {\displaystyle H={\frac {\sum _{i=1}^{m}{u_{i}^{d}}}{\sum _{i=1}^{m}{u_{i}^{d}}+\sum _{i=1}^{m}{w_{i}^{d}}\,,} Bei dieser Definition sollten einheitliche Zufallsdaten Werte in der Nähe von 0,5 haben, und gruppierte Daten sollten Werte in der Nähe von 1 haben., Daten, die nur einen einzelnen Gaußschen Wert enthalten, werden jedoch auch nahe bei 1 liegen, da diese Statistik die Abweichung von einer einheitlichen Verteilung misst, nicht die Multimodalität, was diese Statistik in der Anwendung weitgehend unbrauchbar macht (da reale Daten niemals aus der Ferne einheitlich sind).