增量层次结构

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-tree？它使用最小边界矩形来汇总叶页中的对象。你也可以使用kd-tree，但是它的性能会随着时间的推移而降低（除非你重建它），因为它可能会变得不平衡。

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

R * -trees是R-tree的改进版本。他们有一个更好的分裂战略，稍微改变插入，并重新插入作为分裂的替代方案，以改善树木平衡。搜索是相同的。

作为一种优化，您可以通过以下优化来增强R-tree：除了删除旧条目并插入新条目，还可以添加“替换”操作。你首先检查插入新的含义的位置。如果它与之前的页面相同，只需将其替换为页面，并最终更新边界框。