增量層次結構

Question

我有以下這個方案的增量聚類算法：

Let x a new data-point, and c the centroid that is closest from x 
if(distance(x, c) > threshold) 
    x becomes a new cluster center (i.e. a new centroid) 
else assign x to c (i.e. update the centroid by taking x) 

爲了加快從X最接近中心的搜索，我想有中心的分層結構（使用一棵樹），我們可以在每次考慮一個新的數據點時增量更新。

樹的每個內部節點都表示爲該節點下的質心的平均值。當更新一個給定的質心（因爲一個新的數據點被分配給這個質心），我們應該重建所有高於這個質心的節點。

這樣的算法變成類似：

Let x a new data-point 
c = searchClosestCenter(x, tree) // return the centroid closest to x 
if(distance(x, c) > threshold) 
    x becomes a new cluster center (i.e. a new centroid) 
    AddCenterToTree(x, tree) 
else 
    assign x to c (i.e. update the centroid by taking x) 
    UpdateTree(c) // update all nodes that are on top of c 

怎麼可以這樣的功能在這種情況下如何界定？有沒有更好的解決方案？

Answer 1

如何使用R-tree？它使用最小邊界矩形來彙總葉頁中的對象。你也可以使用kd-tree，但是它的性能會隨着時間的推移而降低（除非你重建它），因爲它可能會變得不平衡。

無論如何，R-tree是這類數據非常流行的數據結構。它用於Oracle，SQLite，Postgres，MySQL，...

R * -trees是R-tree的改進版本。他們有一個更好的分裂戰略，稍微改變插入，並重新插入作爲分裂的替代方案，以改善樹木平衡。搜索是相同的。

作爲一種優化，您可以通過以下優化來增強R-tree：除了刪除舊條目並插入新條目，還可以添加「替換」操作。你首先檢查插入新的含義的位置。如果它與之前的頁面相同，只需將其替換爲頁面，並最終更新邊界框。