Wie werden Diagramme von k-nächsten Nachbarn erstellt? (zum Clustering)

Ich habe gesehen, dass es mehrere Clustering-Algorithmen gibt (zum Beispiel CHAMELEON oder sogar Spectral Clustering), die die Daten in einen gewichteten (oder manchmal ungewichteten) k-Nächsten-Nachbarn-Graphen konvertieren, basierend auf den Abständen zwischen Punkten / Beobachtungen / Zeilen und Ich habe mich gefragt, wie diese Grafiken generiert werden.

Sind diese Grafiken gerichtet? Wenn ein Punkt A einen anderen Punkt B als nahen Nachbarn hat, Punkt B jedoch keinen Punkt A als nahen Nachbarn hat, wird dann noch eine Kante gezeichnet? Wie werden Gewichte berechnet?

clustering graph-theory anymous.asker
quelle

fügte zwei Beispiele hinzu

anymous.asker

CHAMELEON ist meiner Meinung nach nicht reproduzierbar, und bei der spektralen Clusterbildung wird normalerweise nur die paarweise Distanzmatrix verwendet, nicht wahr?

Hat aufgehört - Anony-Mousse

Nun, ich bin kein Experte für spektrales Clustering und ich weiß, dass es einige rechnerische Tricks gibt, um die Implementierung mithilfe der Kovarianz oder der Distanzmatrix, die ich denke, effizienter zu gestalten, aber in R, wenn ich mir eher die specClust-Funktion im kknn-Paket anschaue als im kernalb heißt es, dass es dies mit einem Diagramm von knn tut und die Option hat, die Anzahl der Nachbarn anzugeben.

anymous.asker

@ Anony-Mousse, warum denkst du, ist Chamäleon nicht reduzierbar? Wir haben eine funktionierende Implementierung, es ist ein bisschen hackig, funktioniert aber :)

Tombart

@Tombart Ich habe noch keine funktionierende, zuverlässige Implementierung gesehen. Dem Papier scheinen wesentliche Details zu fehlen - wie man das Diagramm wirklich partitioniert (sie beziehen sich einfach auf hMETIS, einen 4-seitigen abstrakten Übersichtsartikel). Ich stehe korrigiert da, sobald ich sehe, dass es in ELKI, sklearn, R usw. verfügbar ist - siehe auch: stackoverflow.com/questions/10958793/…

Hat aufgehört - Anony-Mousse

Antworten:

Jede normalisierte (Dis-) Ähnlichkeitsmatrix kann in die Adjazenzmatrix eines ungerichteten Graphen (gewichtet oder nicht) konvertiert werden. Für einen ungewichteten Graphen möchten Sie empirisch einen Schwellenwert für seine Adjazenzmatrix festlegen, dh einen minimalen Ähnlichkeitswert für eine Verbindung zwischen zwei Knoten. Für eine bestimmte Partition des Diagramms quantifiziert die Modularitätsmetrik die Gesamtstärke seiner Cluster. Durch Maximieren der Modularität erhalten Sie daher die optimale Community-Struktur, die diesem Diagramm entspricht (Clustering).

So beantworten Sie Ihre Fragen:

Das betreffende Diagramm bleibt ungerichtet, solange Ihre Ähnlichkeitsmatrix symmetrisch ist.
Gewichte (falls vorhanden) sind die normalisierten Ähnlichkeitswerte.

Die Modularitätsfunktion ist im Grunde die Zielfunktion eines NP-harten kombinatorischen Problems. Es gibt viele (Meta-) Heuristiken, die diese Aufgabe erfüllen, und wenn ich mich nicht irre, ist der beim spektralen Clustering verwendete normalisierte Schnittalgorithmus eine davon. Ich habe keine Erfahrung mit Chameleon, aber das Konzept der Maximierung der Intracluster-Ähnlichkeit bei gleichzeitiger Minimierung der Intercluster-Ähnlichkeit ist bei der Modularitätsoptimierung dasselbe.

Leider gibt es kein Paket (von dem ich weiß), das die Adjazenzmatrixkonvertierung automatisieren kann, da das Finden des optimalen Schwellenwerts ein manueller Prozess ist. Sobald Sie diese Matrix haben, haben R und Mathematica großartige Pakete, um den Rest zu erledigen.

Digio
quelle

Vielen Dank für die Antwort, obwohl ich einige R-Pakete gefunden habe, die dies tun, mit einer Methode, die ganz anders zu sein scheint (eine feste Anzahl von k Nachbarn in einem gerichteten Graphen zu erzeugen). Hier ist eines zum Beispiel: artax.karlin.mff.cuni.cz/r-help/library/cccd/html/nng.html

anymous.asker

Können Sie ein Buch empfehlen, das ich studieren muss, um diesen Satz verstehen zu können: "Die Modularitätsfunktion ist im Grunde die Zielfunktion eines NP-harten kombinatorischen Problems." ;)

K.-Michael Aye

@ K.-MichaelAye Für rechnerische Komplexität: Computerkomplexität von Christos Papadimitriou. Zur kombinatorischen Optimierung: Kombinatorische Optimierung: Algorithmen und Komplexität von Christos Papadimitriou. Für die Methode der optimalen Modularität und ihre Komplexität: On Modularity Clustering

Digio

Standard- Chamäleon wird unter Verwendung eines asymmetrischen k-NN-Algorithmus initialisiert, wobei Parameter $k$ könnte auf eine ausreichend große Anzahl festgelegt werden, z $10$ oder abgeleitet von der Datensatzgröße, z $k=\sqrt{n}$ .

Kantengewicht zwischen $A$ und $B$ ist eingestellt auf $w(e) = dist(A,B)$ , wobei der Abstand als euklidischer Abstand (oder jeder andere Abstand, der der dreieckigen Ungleichung entspricht) definiert ist. Der Graph ist nicht gerichtet.

Die Autoren schlagen vor, dass auch ein symmetrisches k-NN für die Graphinitialisierung verwendet werden könnte (wenn ein Punkt A einen anderen Punkt B als nahen Nachbarn hat, Punkt B jedoch keinen Punkt A als nahen Nachbarn hat, wird die Kante nicht erstellt ). Dieser Ansatz wird jedoch aufgrund seiner hohen Rechenkomplexität normalerweise nicht verwendet.

Einige Experimente mit symmetrischem k-NN werden von Lesna, Shatovska, vorgestellt .

Einfachen Datensatz haben:

Sie erstellen ein Diagramm aus k-NN:

Nach der Partitionierung wird das Diagramm stark vereinfacht (mit großen $k$ beim Betteln hat möglicherweise überhaupt keinen Einfluss, da die meisten Kanten beim Partitionieren entfernt werden).

Tombart
quelle