Clustering-Methoden, bei denen die Anzahl der Cluster nicht angegeben werden muss

17

Gibt es "nicht parametrische" Clustering-Methoden, für die die Anzahl der Cluster nicht angegeben werden muss? Und andere Parameter wie die Anzahl der Punkte pro Cluster usw.

clustering Learn_and_Share
quelle

Antworten:

22

Clustering-Algorithmen, bei denen Sie die Anzahl der Cluster im Voraus festlegen müssen, sind eine kleine Minderheit. Es gibt eine Vielzahl von Algorithmen, die dies nicht tun. Sie sind schwer zusammenzufassen; Es ist ein bisschen so, als würde man nach einer Beschreibung von Organismen fragen, die keine Katzen sind.

Clustering-Algorithmen werden häufig in große Königreiche eingeteilt:

  1. Partitionierungsalgorithmen (wie k-means und seine Nachkommen)
  2. Hierarchisches Clustering (wie @Tim beschreibt )
  3. Dichte-basiertes Clustering (z. B. DBSCAN )
  4. Modellbasiertes Clustering (z. B. finite Gaußsche Mischungsmodelle oder Latent Class Analysis )

Es kann zusätzliche Kategorien geben, und die Leute können mit diesen Kategorien nicht einverstanden sein und welche Algorithmen in welche Kategorie fallen, da dies heuristisch ist. Trotzdem ist so etwas üblich. Davon ausgehend erfordern in erster Linie nur die Partitionierungsmethoden (1) die Vorgabe der Anzahl der zu findenden Cluster. Welche anderen Informationen vordefiniert werden müssen (z. B. die Anzahl der Punkte pro Cluster) und ob es sinnvoll erscheint, verschiedene Algorithmen als "nichtparametrisch" zu bezeichnen, ist ebenfalls sehr variabel und schwer zusammenzufassen.

Beim hierarchischen Clustering müssen Sie die Anzahl der Cluster nicht wie bei k-means vorab angeben , sondern Sie wählen eine Anzahl von Clustern aus Ihrer Ausgabe aus. Auf der anderen Seite erfordert DBSCAN auch keine Angabe (aber es erfordert die Angabe einer Mindestanzahl von Punkten für eine "Nachbarschaft" - obwohl es Standardwerte gibt. In gewissem Sinne können Sie also die Angabe dieser Punkte überspringen -, wodurch ein Stockwerk entsteht die Anzahl der Muster in einem Cluster). GMM benötigt nicht einmal eines dieser drei Verfahren, sondern erfordert parametrische Annahmen zum Datenerzeugungsprozess. Soweit ich weiß, gibt es keinen Cluster-Algorithmus, bei dem Sie niemals eine Anzahl von Clustern, eine Mindestanzahl von Daten pro Cluster oder ein beliebiges Muster / eine beliebige Anordnung von Daten innerhalb von Clustern angeben müssen. Ich sehe nicht ein, wie es sein könnte.

Es kann hilfreich sein, einen Überblick über verschiedene Arten von Clustering-Algorithmen zu erhalten. Folgendes könnte ein Ausgangspunkt sein:

  • Berkhin, P. "Übersicht über Clustering-Data-Mining-Techniken" ( pdf )
gung - Wiedereinsetzung von Monica
quelle
Ich bin verwirrt von Ihrer Nr. 4: Ich dachte, wenn man ein Gaußsches Mischungsmodell an die Daten anpasst, muss man die Anzahl der zu passenden Gaußschen wählen, dh die Anzahl der Cluster muss im Voraus angegeben werden. Wenn ja, warum sagen Sie, dass "in erster Linie" # 1 dies erfordert?
Amöbe sagt Reinstate Monica
@amoeba, es hängt von der modellbasierten Methode und deren Implementierung ab. GMMs sind oft dazu geeignet, ein Kriterium zu minimieren (wie z. B. die OLS-Regression hier ). In diesem Fall geben Sie die Anzahl der Cluster nicht im Voraus an. Selbst wenn Sie dies gemäß einer anderen Implementierung tun, ist dies keine typische Funktion für modellbasierte Methoden.
gung - Wiedereinsetzung von Monica
Was Sie in der verknüpften Antwort getan haben (oder vielleicht, was die entsprechende R-Funktion für Sie getan hat), ist wahrscheinlich, GMMs mit 1, 2, 3, 4 usw. Clustern anzupassen, die resultierenden BICs zu vergleichen und das "optimale" auszuwählen. Eins, was ergibt . Ich würde es immer noch als Vorgabe der Anzahl von Clustern und Verwendung einer zusätzlichen allgemeinen Heuristik zur Auswahl des am besten passenden Modells beschreiben, aber ich kann sehen, dass ein Argument dafür vorgebracht werden kann, dass nicht sein muss vorgegeben. Kann man BIC aber nicht auch mit k-means verwenden? Wenn ja, dann scheinen sich k-means und GMM im selben Boot zu befinden. kk=3k
Amöbe sagt Reinstate Monica
Ich folge deinem Argument hier nicht wirklich, @amoeba. Wenn Sie ein einfaches Regressionsmodell mit dem OLS-Algorithmus anpassen, würden Sie sagen, dass Sie die Steigung und den Achsenabschnitt vorab festlegen oder dass der Algorithmus sie durch Optimieren eines Kriteriums festlegt? In letzterem Fall sehe ich nicht, was hier anders ist. Es ist sicher richtig, dass Sie einen neuen Meta-Algorithmus erstellen könnten, der k-means als einen seiner Schritte verwendet, um eine Partition ohne vorherige Angabe von k zu finden, aber dieser Meta-Algorithmus wäre nicht k-means.
gung - Wiedereinsetzung von Monica
1
@amoeba, dies scheint ein semantisches Problem zu sein, aber die Standardalgorithmen, die zur Anpassung an ein GMM verwendet werden, optimieren normalerweise ein Kriterium. Beispielsweise dient der eine Mclustzur Optimierung des BIC, der AIC kann jedoch auch als Folge von Likelihood-Ratio-Tests verwendet werden. Ich nehme an, Sie könnten es einen Meta-Algorithmus nennen, b / c, er hat konstituierende Schritte (z. B. EM), aber das ist der Algorithmus, den Sie verwenden, und auf jeden Fall müssen Sie k nicht vorab angeben. Sie können in meinem verknüpften Beispiel deutlich sehen, dass ich k dort nicht vorab angegeben habe.
gung - Wiedereinsetzung von Monica
13

Das einfachste Beispiel ist hierarchisches Clustering , wo Sie jeden Punkt mit jedem anderen Punkt zu vergleichen , einige mit Abstandsmessung , und kommt dann zusammen das Paar, das den kleinsten Abstand hat zu verbindendem pseudo-Punkt (zB erstellen b und c macht bc wie auf dem Bild unten). Als Nächstes wiederholen Sie den Vorgang, indem Sie die Punkte und Pseudopunkte anhand ihrer paarweisen Abstände verbinden, bis jeder Punkt mit dem Diagramm verbunden ist.

Wikipedia Abbildung

(Quelle: https://en.wikipedia.org/wiki/Hierarchical_clustering )

Das Verfahren ist nicht parametrisch und das einzige, was Sie dafür benötigen, ist das Abstandsmaß. Am Ende müssen Sie entscheiden, wie Sie den mit diesem Verfahren erstellten Baumgraphen bereinigen möchten , sodass eine Entscheidung über die erwartete Anzahl von Clustern getroffen werden muss.

Tim
quelle
Bedeutet das Beschneiden nicht, dass Sie sich für die Clusternummer entscheiden?
Learn_and_Share
1
@MedNait das habe ich gesagt. Bei der Clusteranalyse muss man immer eine solche Entscheidung treffen, die einzige Frage ist, wie sie getroffen wird - z. B. kann sie willkürlich sein oder auf einem vernünftigen Kriterium wie der Wahrscheinlichkeitsmodellanpassung usw. basieren.
Tim
1
Es hängt davon ab, was genau Sie suchen, @MedNait. Beim hierarchischen Clustering müssen Sie die Anzahl der Cluster nicht wie bei k-means vorab angeben , sondern Sie wählen eine Anzahl von Clustern aus Ihrer Ausgabe aus. Auf der anderen Seite erfordert DBSCAN auch nicht (aber es erfordert die Angabe einer Mindestanzahl von Punkten für eine "Nachbarschaft" - obwohl es Standardwerte gibt - was die Anzahl der Muster in einem Cluster einschränkt). . GMM benötigt dies nicht einmal, sondern erfordert parametrische Annahmen über den Datenerzeugungsprozess. Etc.
Gung - wieder einzusetzen Monica
10

Parameter sind gut!

Eine "parameterfreie" Methode bedeutet, dass Sie nur eine einzige Aufnahme erhalten (mit Ausnahme von Zufälligkeiten), ohne Anpassungsmöglichkeiten .

Jetzt ist Clustering eine explorative Technik. Sie dürfen nicht davon ausgehen, dass es nur ein einziges "echtes" Clustering gibt . Sie sollten eher daran interessiert sein , verschiedene Cluster mit denselben Daten zu untersuchen, um mehr darüber zu erfahren. Clustering als Black Box zu behandeln, funktioniert nie gut.

Sie möchten beispielsweise die verwendete Distanzfunktion in Abhängigkeit von Ihren Daten anpassen können (dies ist auch ein Parameter!). Wenn das Ergebnis zu grob ist, möchten Sie ein feineres Ergebnis erzielen, oder wenn es zu fein ist erhalten Sie eine gröbere Version davon.

Die besten Methoden sind häufig solche, mit denen Sie das Ergebnis gut navigieren können, z. B. das Dendrogramm in hierarchischen Clustern. Sie können dann problemlos Unterstrukturen erkunden.

Anony-Mousse - Setzen Sie Monica wieder ein
quelle
0

Schauen Sie sich Dirichlet-Mischungsmodelle an . Sie bieten eine gute Möglichkeit, die Daten zu verstehen, wenn Sie die Anzahl der Cluster vorher nicht kennen. Sie treffen jedoch Annahmen über die Formen von Clustern, gegen die Ihre Daten möglicherweise verstoßen.

Zeke
quelle