应该选择哪种算法来完成这项任务？

Question

嗨，我是集群的新手，我不知道哪种算法适合我的任务。让我描述一下我的任务：

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)。