algorithm - 应该选择哪种算法来完成这个任务

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