Ich habe n Wörter und ihre Verwandtschaft gewicht dasgibt mir eine n * n Matrix. Ich werde dies für einen Suchalgorithmus verwenden, aber das Problem ist, dass ich die eingegebenen Schlüsselwörter basierend auf ihrer paarweisen Beziehung gruppieren muss. Sagen wir also, ob die Schlüsselwörter {Tennis, Federer, Wimbledon, London, Polizei} und wir sind haben folgende Daten aus unserer Gewichtsmatrix:
tennis federer wimbledon london police
tennis 1 0.8 0.6 0.4 0.0
federer 0.8 1 0.65 0.4 0.02
wimbledon 0.6 0.65 1 0.08 0.09
london 0.4 0.4 0.08 1 0.71
police 0.0 0.02 0.09 0.71 1
Ich brauche einen Algorithmus, um sie in 2 zu gruppierenCluster: {Tennis, Federer, Wimbledon} {London, Polizei}. Gibt es irgendeinen Clustering-Algorithmus, der mit so etwas umgehen kann? Ich habe einige Nachforschungen angestellt, es scheint, dass der K-means-Algorithmus der am besten bekannte Algorithmus ist, der für das Clustering verwendet wird, aber anscheinend passt K-means nicht zu diesem Fall. Ich würde jede Hilfe sehr schätzen.
Antworten:
1 für die Antwort № 1Erwägen DBSCAN. Wenn es Ihren Bedürfnissen entspricht, sollten Sie sich eine optimierte Version genauer ansehen, TI-DBSCAN, die die Dreiecksungleichung zum Reduzieren der räumlichen Abfragekosten verwendet.
DBSCAN's Vor- und Nachteile sind auf Wikipedia diskutiert. Es teilt Eingabedaten in eine Menge von Clustern auf, deren Kardinalität nicht bekannt ist a priori. Sie müssten Ihre Ähnlichkeitsmatrix in eine Abstandsmatrix umwandeln, zum Beispiel indem Sie nehmen 1 - similarity als eine Entfernung.
2 für die Antwort № 2
Sie können es als Netzwerkclusterproblem behandeln. Mit einer aktuellen Version der mcl-Software (http://micans.org/mcl), können Sie dies tun (ich habe Ihr Beispiel fe.data genannt).
mcxarray -data fe.data -skipr 1 -skipc 1 -write-tab fe.tab -write-data fe.mci -co 0 -tf "gq(0)" -o fe.cor
# the above computes correlations (put in data file fe.cor) and a network (put in data file fe.mci).
# below proceeds with the network.
mcl fe.mci -I 3 -o - -use-tab fe.tab
# this outputs the clustering you expect. -I is the "inflation parameter". The latter affects
# cluster granularity. With the default parameter 2, everything ends up in a single cluster.
Haftungsausschluss: Ich schrieb mcl und eine Reihe assoziierter Programme zum Laden / Konvertieren und Analysieren von Netzwerken, die kürzlich als "mcl-edge" umbenannt wurden. Sie alle kommen in einem einzigen Softwarepaket zusammen. Das Beispiel zu sehen hat mich neugierig gemacht, ob es mit mcl-edge machbar ist, also habe ich es schnell getestet.
0 für die Antwort № 3
Überprüfen Sie dieses Buch auf Information retrieval
http://nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html
Es erklärt sehr gut, was Sie tun möchten
0 für die Antwort № 4
Ihre Gewichte sind höher für ähnliche Wörterund niedriger für andere Wörter. Ein Clustering-Algorithmus erfordert, dass ähnliche Punkte / Wörter räumlich näher und andere Wörter entfernt sind. Sie sollten die Matrix ändern M in 1-M und dann benutzen irgendein Clustering-Methode, die Sie wollen, einschließlich k-Mittel.
0 für die Antwort № 5
Wenn Sie eine Entfernungsmatrix haben, ist es eine Schande, es nicht zu versuchen http://en.wikipedia.org/wiki/Single_linkage_clustering. Mit der Hand, ich denke, Sie erhalten folgende Clustering:
((Federer, Tennis), Wimbledon) (London, Polizei)
Die Ähnlichkeit für den Link, der die beiden verbindetHauptgruppen (entweder Tennis-London oder Federer-London) ist kleiner als jede der Ähnlichkeiten, die die beiden Gruppen bilden: London-Polizei, Tennis-Federer und Federer-Wimbledon: Diese Eigenschaft wird durch Single-Linking-Clustering garantiert, da es bindet zusammenhängenden Cluster in jeder Phase, und die beiden Hauptgruppen sind durch die letzte gefundene Bindung verbunden.
0 für die Antwort № 6
DBSCAN (siehe andere Antworten) und Nachfolger wie OPTICS sind eindeutig eine Option.
Während die Beispiele auf Vektordaten basieren, ist alles, was die Algorithmen benötigen, eine Abstandsfunktion. Wenn Sie eine Ähnlichkeitsmatrix haben, kann das trivialerweise als Abstandsfunktion verwendet werden.
Der Beispieldatensatz ist wahrscheinlich ein bisschen zu kleinfür sie, um sinnvolle Ergebnisse zu erzielen. Wenn Sie nur so wenig Daten haben, sollte jedes "hierarchische Clustering" machbar sein und die Arbeit für Sie erledigen. Sie müssen dann nur noch die beste Anzahl von Clustern auswählen.