應選擇哪種算法來完成此任務

Question

嗨 我是Cluster的新手，我不知道哪個算法適合我的任務。讓我描述我的任務：

1. 第一，給定一組點和它們之間的距離長短
2. 聚類他們到基於距離幾個簇。
3. 會增加一些新的點數，也會給出所有點數之間的距離。
4. 重複2

例如，首先我們有以下矩陣

| p1 | p2 | p3 | 
---|----|----|----| 
p1 | | | | 
p2 | d1 | | | 
p3 | d2 | d3 | | 

聚類後

，我們添加一個新點和距離也被給出：

| p1 | p2 | p3 | p4 | 
---|----|----|----|----| 
p1 | | | | | 
p2 | d1 | | | | 
p3 | d2 | d3 | | | 
p4 | d4 | d5 | d6 | | 

的問題在於速度，我期望聚類是增量聚類，即後面的聚類可以利用以前的結果。因爲我們會頻繁地添加點（如果我們找到一個點），並且每次都重新聚合點。即使羣集本身具有O（n），羣集的總時間也將是O（n^2）。

有什麼建議嗎？

感謝

Answer 1

一種選擇是修復集羣（比如，你的K集羣）的數量。無論何時添加新點，都將其添加到其重心（羣集中點的座標的平均值）最接近您添加的點的羣集。如果只要您的空間中的點數變爲2的冪（1,2,4,8,16,32 ...）時您完全重新集羣，則重新聚集的分攤成本仍爲O（n）。