Gibt es nicht entfernungsbasierte Clustering-Algorithmen?

Es scheint, dass für K-means und andere verwandte Algorithmen das Clustering auf der Berechnung des Abstands zwischen Punkten basiert. Gibt es eine, die ohne funktioniert?

Ein Beispiel für eine solche Methode sind Finite-Mixture-Modelle (z. B. hier oder hier ), die zum Clustering verwendet werden. In FMM betrachten Sie die Verteilung ( $f$ ) Ihren Variable $X$ als eine Mischung aus $K$ - Verteilungen ( $f_1,...,f_k$ ):

wobei ein Vektor der Parameter θ = ( π ' , θ ' 1 , . . . , θ ' k ) ' und π k ist ein Anteil der k -ten Verteilung in der Mischung und θ k ein Parameter ist (oder Parameter) der f k Verteilung.$\vartheta$$\vartheta = (\pi', \vartheta_1', ..., \vartheta_k')'$$\pi_k$$k$$\vartheta_k$$f_k$

Ein spezieller Fall für diskrete Daten ist die Latent Class Analysis (z. B. hier ), definiert als:

wobei die Wahrscheinlichkeit ist, die latente Klasse k (dh π k ) zu beobachten, P ( x ) die Wahrscheinlichkeit ist, einen x- Wert zu beobachten, und P ( x | k ) die Wahrscheinlichkeit ist, dass x in der Klasse k ist .$P(k)$$k$$\pi_k$$P(x)$$x$$P(x|k)$$x$$k$

Normalerweise wird sowohl für FMM als auch für LCA ein EM-Algorithmus für die Schätzung verwendet, aber der Bayes'sche Ansatz ist auch möglich, jedoch aufgrund von Problemen wie Modellidentifizierung und Etikettenwechsel etwas anspruchsvoller (z. B. Xi'ans Blog ).

Es gibt also kein Entfernungsmaß, sondern ein statistisches Modell, das die Struktur (Verteilung) Ihrer Daten definiert. Aus diesem Grund lautet der andere Name dieser Methode "modellbasiertes Clustering".

Überprüfen Sie die beiden Bücher über FMM:

• McLachlan, G. & amp; Peel, D. (2000). Modelle mit endlicher Mischung. John Wiley & Söhne.
• Frühwirth-Schnatter, S. (2006). Finite Mixture und Markov Switching Modelle. Springer.

Eines der beliebtesten Clustering-Pakete, das FMM verwendet, ist mclust(überprüfen Sie hier oder hier ), das in R implementiert ist . Es sind jedoch auch kompliziertere FMMs möglich. Überprüfen Sie beispielsweise das flexmixPaket und dessen Dokumentation . Für die Ökobilanz gibt es ein R poLCA-Paket .

K-means ist nicht "wirklich" entfernungsbasiert. Es minimiert die Varianz . (Aber Varianz euklidischen Abstände im Quadrat, so dass jeder Punkt wird auf die nächste Schwerpunkt von euklidischen Abstand zugeordnet, auch).$\sim$

Es gibt viele gitterbasierte Clustering-Ansätze . Sie berechnen keine Entfernungen, da dies häufig zu einer quadratischen Laufzeit führt. Stattdessen partitionieren sie die Daten und aggregieren sie in Rasterzellen. Aber die Intuition hinter solchen Ansätzen hängt gewöhnlich sehr eng mit Entfernungen zusammen.

Es gibt eine Reihe von Clustering-Algorithmen für kategoriale Daten wie COOLCAT und STUCCO. Entfernungen sind mit solchen Daten nicht einfach zu verwenden (One-Hot-Codierung ist ein Hack und ergibt keine besonders aussagekräftigen Entfernungen). Aber ich habe noch nie von jemandem gehört, der diese Algorithmen verwendet ...

Es gibt Clustering-Ansätze für Diagramme. Aber entweder reduzieren sie sich auf klassische Diagrammprobleme wie Clique- oder Near-Clique-Finding und Diagrammfärbung, oder sie hängen eng mit entfernungsbasiertem Clustering zusammen (wenn Sie ein gewichtetes Diagramm haben).

Dichte-basiertes Clustering wie DBSCAN hat einen anderen Namen und konzentriert sich nicht auf die Minimierung von Entfernungen. "Dichte" wird jedoch normalerweise in Bezug auf eine Entfernung angegeben, so dass diese Algorithmen technisch entweder entfernungsbasiert oder gitterbasiert sind.

Der wesentliche Teil Ihrer Frage, den Sie ausgelassen haben, ist, wie lauten Ihre Daten ?

Zusätzlich zu den bisherigen netten Antworten würde ich vorschlagen, Dirichlet-Mischungsmodelle und Bayes-basierte hierarchische Dirichlet-Prozessmodelle in Betracht zu ziehen . Eine ziemlich umfassende und allgemeine Übersicht über Ansätze und Methoden zur Bestimmung einer optimalen Anzahl von Clustern finden Sie in dieser hervorragenden Antwort auf StackOverflow : /programming//a/15376462/2872891 .

Ein rein diskriminativer Ansatz ist die "regularisierte Informationsmaximierung" von Gomes et al . Es gibt keinerlei Vorstellung von Ähnlichkeit / Distanz.

Die Idee ist, ein logistisches Regressionsmodell zu haben, das Punkte in Behälter legt. Aber anstatt es zu trainieren, um eine Art von Log-Wahrscheinlichkeit der Klassenbeschriftungen zu maximieren, ist die Zielfunktion eine, die Punkte in verschiedene Cluster einordnet.

$\lambda$

Die Erweiterung auf Kernel-Methoden oder neuronale Netze für nichtlineares Clustering ist unkompliziert.