应该选择哪种算法来完成这个任务
你好 我是集群的新手，我不知道哪种算法适合我的任务。让我描述一下我的任务：
- 首先，给定一组点及其之间的距离，
- 根据距离将它们聚类成几个簇。
- 将添加一些新点，还将给出所有点之间的距离。
- 以重复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)。
有什么建议吗？
谢谢
Hi
I am new to Cluster,I don't know which algorithm is appropriate to my task. let me describe my task:
- first, given a set of points and their distances between them
- clustering them into several clusters based on distance.
- a few new points will be added, the distance among all of points will also be given.
- repeating 2
for example,first we have the following matrix
| p1 | p2 | p3 |
---|----|----|----|
p1 | | | |
p2 | d1 | | |
p3 | d2 | d3 | |
after clustering, we add a new point and the distance is also given:
| p1 | p2 | p3 | p4 |
---|----|----|----|----|
p1 | | | | |
p2 | d1 | | | |
p3 | d2 | d3 | | |
p4 | d4 | d5 | d6 | |
The problem here is the speed, I expect that the clustering is the incremental cluster, i.e. the later clustering can utilize previous result. Because we will add the points frequently(if we find one), and if we re-cluster the points each time. Even if the cluster itself has O(n), the total time of cluster will be O(n^2).
Any suggestion?
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
一种选择是固定簇的数量（假设您有 K 个簇）。每当添加新点时，都会将其添加到重心（簇中点坐标的平均值）最接近您添加的点的簇中。如果每当空间中的点数变为 2 的幂（1、2、4、8、16、32 ...）时就完全重新聚类，则重新聚类的摊销成本仍然是 O(n)。
One option is to fix the number of clusters (say, you have K clusters). Whenever you add a new point, you add it to the cluster whose center of gravity (average of the coordinates of the points in the cluster) is nearest to the point you added. If you recluster completely whenever the number of points in your space becomes a power of two (1, 2, 4, 8, 16, 32 ...), the amortized cost of reclustering is still O(n).