应选择哪种算法来完成此任务

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