Ich mache einige Tests, bei denen eine große Anzahl sehr großer Vektoren mit geringer Dichte gruppiert wird, die die Terme-Frequenz-Invers-Dokument-Häufigkeit verschiedener hypertextueller Dokumente darstellen. Welchen Algorithmus würden Sie vorschlagen, um diese Daten unter Berücksichtigung der Proportionen des Datensatzes zu gruppieren? Die Dimension der Vektoren wäre & gt; 3 · 10 5 und die Anzahl der Vektoren könnte etwa 10 9 betragen. Ich habe mir dbscan und optische Algorithmen angeschaut. Die Anzahl der Cluster ist nicht bekannt. Und ein räumlicher Index mit so hoher Dimensionalität erscheint kompliziert.
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 nach mir ginge, würde ich mir sehr viel Mühe geben, die Dimensionalität mit etwas wie Landmark MDS zu reduzieren, dann mit dem Clustering.
Ich habe gehört, dass semantisches Hashing hervorragende Ergebnisse erzielt. Tiefe Überzeugungsnetze sind jedoch ziemlich schwer zu implementieren. Sie können versuchen, min Hashing (das ist ein probabilistischer Ansatz, obwohl) oder Lokalität sensistiven Hashing für euklidische Räume .
Im Allgemeinen ist das Gruppieren 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.
Beim Clustering von Daten würde ich immer mindestens diese beiden Algorithmen in dieser Reihenfolge versuchen:
K-Means: Versuchen Sie, die Ergebnisse so gut wie möglich zu optimieren. Wenn Sie K-Means dazu bringen können, für Sie zu arbeiten und anständige Ergebnisse zu liefern, werden Sie fast sicher keinen besseren Algorithmus mehr finden.
Erwartungsmaximierung: Der K-Means-Algorithmus wurde tatsächlich 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 Ссылка erfahren. Es gibt eine OpenCv-Implementierung von EM: Ссылка
Wenn die Ergebnisse beider nicht zufriedenstellend sind, würde ich mich anderswo umsehen, aber nicht , bis Sie beides versucht haben.
Entscheidungsbäume sind beliebt, um effizient in hochdimensionalen Räumen zu arbeiten. Schauen Sie sich Clustering Via Decision an Baumkonstruktion .
Auch Randomized Forests sind extrem effiziente Lerner und eine OpenCV-Implementierung existiert , wenn Sie damit spielen wollen.
Tags und Links algorithm cluster-analysis