Gibt es eine effiziente Möglichkeit, Knoten in einem Diagramm mit der Jaccard-Ähnlichkeit zu gruppieren, sodass jeder Cluster mindestens K Knoten hat?
Jaccard-Ähnlichkeit zwischen den Knoten i und j :
S sei die Menge der Nachbarn von i und T sei die Menge der Nachbarn von j . Dann ist die Ähnlichkeit zwischen i und j durch |(S ⋂ T)| / |(S ⋃ T)| gegeben.
Haben Sie selbst versucht, einen Algorithmus zu implementieren?
Berechne alle paarweisen Nicht-Null-Ähnlichkeiten (d. h. wenn sie mindestens einen Nachbarn gemeinsam haben; dies macht den Kandidatensatz viel kleiner als eine quadratische Matrix).
Sortiere sie nach Ähnlichkeit und verarbeite Paare in abnehmender Ähnlichkeit. Anfangs ist jedes Objekt ein eigener Cluster.
Wenn A und B noch nicht im selben Cluster sind und jeder Cluster weniger als k Mitglieder hat, verbinden Sie die beiden Cluster. Wiederholen Sie dies, bis alle Ähnlichkeiten verarbeitet wurden.
Beachten Sie, dass Sie möglicherweise weiterhin Cluster mit weniger als k Mitgliedern haben. Zum Beispiel, wenn Ihr Datensatz weniger als k Knoten insgesamt hat, oder es kleine Untergraphen gibt, die nicht verbunden sind usw.
Sie sollten Cluster mit weniger als k Knoten, d. h. nicht gruppierte Knoten , wirklich akzeptieren. Warum würde alles zusammenfließen? Es wird immer Ausreißer und Rauschen in realen Daten geben.
Tags und Links algorithm cluster-analysis graph-algorithm hierarchical-clustering