質量閾值聚類算法的高效數據結構

Question

我試圖實現質量閾值聚類算法。 （從here截取）的它的概要如下：

1. 初始化允許簇閾值距離和最小羣集大小
2. 構建爲通過包括最近點的每個數據點處的候選聚類，下最近，依此類推，直到集羣的距離超過閾值
3. 保存最點作爲第一個真正的集羣候選集羣，並從進一步考慮刪除所有點的集羣中
4. 重複使用減少的組直到沒有更多的聚類可以形成具有最小聚類r大小

我一直在閱讀一些最近的鄰居搜索算法和空間分區數據結構，因爲它們似乎是我需要的東西，但我不能確定使用哪一個，或者如果我'米應該是在看別的東西。

我想爲了教育目的而自己實現數據結構，並且我需要一個能夠連續返回某個點的最近點的數據結構。然而，因爲我不知道我需要查詢的次數（即直到超過閾值），所以我不能使用k-最近鄰居算法。我一直在尋找四叉樹和k-d樹。另外，由於該算法不斷地建立新的候選集羣，因此使用使用緩存信息加速後續查詢（但也考慮到點刪除）的修改數據結構將是有趣的。

Answer 1

這個算法聽起來像DBSCAN (Wikipedia)的前身，已知它與R*-Tree indexes (Wikipedia)一起工作得很好。但當然，kd樹也是一種選擇。這兩者之間的主要區別在於R * - 樹是用於數據庫使用的 - 它們支持在線插入和刪除，並且是面向塊的 - 而kd樹更多的是基於二進制分割的內存數據結構。 R * -trees執行重新平衡，而kd-trees會慢慢失去平衡，需要重建。 我發現R *樹中的最近鄰居搜索比k-d樹更容易理解，因爲你有邊界矩形非常直觀。

DBSCAN還從進一步考慮中「移除」了一些要點，但只是將它們標記爲已分配。這樣你就不需要更新索引。並且一開始就可以批量加載一次就足夠了。你也應該可以爲QT做到這一點。所以除非我弄錯了，否則可以通過運行設置爲QT集羣的epsilon和設置爲minPts=2的DBSCAN來高效地獲得QT集羣（儘管在適當的DBSCAN中更喜歡更高的值）。

有許多DBSCAN實現。 Weka中的一個非常糟糕，所以遠離它。 R中的fpc實現可以，但仍然可能會快很多。 ELKI似乎是唯一一個提供全面索引支持，並且速度差異很大。他們的Benchmark通過在這個數據集上使用索引來顯示12倍的速度增益，允許它們在50秒內而不是603（沒有索引）下進行聚類。 Weka在那裏花費了37917秒，R fpc 4339。這與我的經歷相一致，Weka的聲譽相當緩慢，而R只是在矢量化操作中踢屁股，一旦R解釋器必須工作，它比本地任何東西都慢很多。但是，這是一個很好的例子，說明不同的人使用相同的算法時可以執行不同的算法。我預計這是2x-5x，但顯然，實現相同算法的程序員彼此的差異很容易達到50倍。