聚類巨大的向量空間

Question

我正在做一些測試，聚集大量的表示各種超文本文檔的詞頻 - 逆文檔頻率的非常大的稀疏向量。考慮到數據集的比例，你建議用什麼算法對數據進行聚類？矢量的維度將是> 3，並且矢量的數量可以是大約10 。我看了一下dbscan和光學算法。集羣的數目並不是先驗的。一個具有如此高維度的空間索引似乎很複雜。

Answer 1

我幾乎和其他任何東西一樣，使用簡單的K均值聚類方法得到了幾乎同樣好的結果，而且它絕對比大多數替代方法快。我在成對集聚方面也取得了不錯的成績，但速度相對較慢。對於K均值，您不得不從一些估計數量的簇開始，但您可以隨着算法對其進行調整。如果發現兩個集羣的距離太近，則可以減少集羣的數量。如果您發現變化範圍過大的羣集，則嘗試更多羣集。我發現sqrt（N）是一個合理的起點 - 但我通常以10^7以上的文檔而非10^9開頭。對於10^9，可能會有所減少。

但是，如果這取決於我，那麼我會非常努力地開始降低像Landmark MDS，然後這樣的維度進行聚類。

Answer 2

決策樹在高維空間有效地工作是很受歡迎的。檢查出Clustering Via Decision Tree Construction。

另外，Randomized Forests是非常高效的學習者，如果你想玩它，可以使用OpenCV implementation exists。

Answer 3

我聽說semantic hashing取得了優異的成績。然而，深層次的信念網絡很難實現。你可能想嘗試min哈希（雖然這是一種概率方法）或locality sensistive hashing for euclidean spaces。

一般來說，由於維度的詛咒和大多數項目彼此具有類似距離的事實，在這樣的高維空間中聚類很困難。如果您事先通過SOM或PCA降低維度，則可以使用像K-Means這樣的標準方法。

Answer 4

如果分組數據我總是嘗試至少這兩種算法順序如下：

1. K-方式：試着調整的結果儘可能地。如果你能讓K-Means爲你工作，並提供可觀的結果，那麼當其他算法的時候幾乎肯定不會做得更好。

2. 期望值最大化：K-means算法實際上被開發成爲EM算法的一種廉價且很好的替代方案。 EM算法的理解更復雜，計算成本更高，但EM的結果非常好。你可以瞭解更多關於EM http://en.wikipedia.org/wiki/Expectation-maximization_algorithm。有一個OpenCV的實現EM的：http://opencv.willowgarage.com/documentation/expectation-maximization.html

如果既沒有這兩者的結果是令人滿意的，我會跳槽，但不，直到兩者都已嘗試過。