algorithm - 递增的代表层级结构

Question

我有一个遵循这个方案的增量聚类算法:

Let x a new data-point, and c the centroid that is closest from x
if( distance(x, c) > threshold )
   x becomes a new cluster center (i.e. a new centroid)
else assign x to c (i.e. update the centroid by taking x)

为了加快从 x 搜索最近的中心，我想要中心的分层结构(使用树)，我们可以在每次考虑新数据点时增量更新。

树的每个内部节点表示为该节点下质心的平均值。当更新一个给定的质心时(因为一个新的数据点被分配给这个质心)，我们应该重建这个质心之上的所有节点。

因此算法变成了这样的:

Let x a new data-point
c = searchClosestCenter(x, tree) // return the centroid closest to x
if( distance(x, c) > threshold )
   x becomes a new cluster center (i.e. a new centroid)
   AddCenterToTree(x, tree)
else
   assign x to c (i.e. update the centroid by taking x)
   UpdateTree(c) // update all nodes that are  on top of c

在这种情况下如何定义这个函数？有没有更好的解决方案？

Answer 1

使用 R 树 怎么样？它使用最小边界矩形来概括叶页中的对象。您也可以使用 kd-tree，但它的性能会随着时间的推移而降低(除非您重建它)，因为它会变得不平衡。

无论如何，R-tree 是一种非常流行的数据结构，适用于此类数据。它用于 Oracle、SQLite、Postgres、MySQL、...

R* 树是 R 树的改进版本。他们有更好的拆分策略，对插入进行了细微的更改，并重新插入作为拆分的替代方法以改善树的平衡。搜索是相同的。

作为优化，您可以通过以下优化来增强 R 树:除了删除旧条目并插入新条目之外，您还可以添加“替换”操作。您首先检查新均值将插入的位置。如果是和之前一样的页面，就在页面中替换它，最后更新边界框。