Clustering großen Vektorraum

Question

Ich mache einige Tests Clustering eine große Anzahl von sehr großen spärlichen Vektoren, die Term-Frequenz-Inverse-Dokument-Frequenz von verschiedenen hypertextuellen Dokumenten. Welchen Algorithmus würden Sie vorschlagen, um diese Daten unter Berücksichtigung der Proportionen des Datensatzes zu gruppieren? Die Dimension der Vektoren wäre> 3 · 10 und die Anzahl der Vektoren könnte etwa 10 sein. Ich habe mir dbscan und optische Algorithmen angeschaut. Die Anzahl der Cluster ist nicht bekannt. Und ein räumlicher Index mit solch hoher Dimensionalität erscheint kompliziert.

Answer 1

Ich hatte fast so gute Ergebnisse mit einem einfachen K-Means Clustering wie fast alles andere, und es ist definitiv schneller als die meisten Alternativen. Ich habe auch gute Ergebnisse mit paarweiser Agglomeration bekommen, aber es ist ein bisschen langsamer. Für K-means müssen Sie mit einer geschätzten Anzahl von Clustern beginnen, aber Sie können sie algorithmisch anpassen, während Sie fortfahren. Wenn Sie zwei Cluster mit zu nah beieinander liegenden Mitteln finden, reduzieren Sie die Anzahl der Cluster. Wenn Sie Cluster mit einer zu großen Variationsbreite finden, versuchen Sie mehr Cluster. Ich habe gefunden, dass sqrt (N) ein vernünftiger Ausgangspunkt ist - aber ich beginne normalerweise mit mehr als 10^7 Dokumenten anstatt 10^9. Für 10^9 könnte es sinnvoll sein, das etwas zu reduzieren.

Wenn es aber an mir liegen würde, würde ich sehr hart daran denken, die Dimensionalität mit etwas wie Landmark MDS, und dann zu reduzieren.

Answer 2

Entscheidungsbäume sind beliebt für effizientes Arbeiten in hochdimensionalen Räumen. Auschecken Clustering Via Decision Tree Construction.

Auch Randomized Forests sind extrem effiziente Lerner und eine OpenCV implementation exists, wenn Sie damit spielen wollen.

Answer 3

Ich höre, dass semantic hashing hervorragende Ergebnisse erzielt. Tiefe Überzeugungsnetze sind jedoch ziemlich schwer zu implementieren. Vielleicht möchten Sie min Hashing (das ist ein probabilistischer Ansatz) oder locality sensistive hashing for euclidean spaces versuchen.

Im Allgemeinen ist Clustering in solchen hochdimensionalen Räumen aufgrund des Fluches der Dimension und der Tatsache, dass die meisten Objekte ähnliche Abstände zueinander haben, schwierig. Standardansätze wie K-Means funktionieren möglicherweise, wenn Sie die Dimensionalität zuvor über SOMs oder PCA reduzieren.

Answer 4

Wenn Daten Clustering Ich würde immer zumindest diese beiden Algorithmen in dieser Reihenfolge versuchen:

1. K-Means: versuchen, die Ergebnisse so weit wie möglich zwicken. Wenn Sie K-Means dazu bringen können, für Sie zu arbeiten und anständige Ergebnisse zu liefern, werden Sie fast sicher nicht besser sein, wenn Sie einen anderen Algorithmus verwenden.

2. Erwartungsmaximierung: Der K-Means-Algorithmus wurde eigentlich als kostengünstige und gute Alternative zum EM-Algorithmus entwickelt. Der EM-Algorithmus ist komplexer zu verstehen und teurer zu berechnen, aber die Ergebnisse von EM sind ausgezeichnet. Sie können mehr über EM http://en.wikipedia.org/wiki/Expectation-maximization_algorithm erfahren. Es gibt eine OpenCV Implementierung von EM: http://opencv.willowgarage.com/documentation/expectation-maximization.html

Wenn die Ergebnisse von keiner dieser beiden zufrieden stellend sind, würde ich anfangen woanders suchen, aber nicht, bis Sie beide versucht haben.