machine-learning - 在进行k-means算法时，如何识别球树中所有包含点都在一个簇中的内部节点？

Question

我现在正在阅读《数据挖掘:实用机器学习工具和技术第三版》这本书。在4.8节聚类中，讨论了如何使用k-d trees或ball trees提高 k-means algorithm 的性能.

用所有数据点构建球树后，它会搜索所有叶节点以查看其中的点各自靠近哪个预先选择的聚类中心。它说有时由较高内部节点代表的区域完全落在单个聚类中心的范围内。那么我们就不需要遍历它的子节点了，所有的数据点都可以一次性处理完。

问题是，在实现数据结构和算法时，如何判断引用内部节点的区域是否落入单个聚类中心？

在二维或三维空间中，这并不困难。我们可以看到簇中心中每对的所有中垂线是否都穿过指向内部节点的区域。

但是在高维空间中，如何认识到这一点？有通用的方法吗？

Answer 1

您需要考虑最大和最小距离。

如果空间对象(例如，半径为 r 的球体)到所有其他均值的最小距离大于到 1 的最大距离，则容器内的所有对象都将属于该均值。因为如果

maxdist(mean_i, container) < min of all j != i mindist(mean_j, container)

然后特别是对于容器中的任何对象

dist(mean_i, obj_in_container) < min of all j != i dist(mean_j, obj_in_container)

即该对象将属于平均值 i。

球体和矩形的最小和最大距离可以在任意维度上轻松计算。然而，在更高的维度中，mindist 和 maxdist 变得非常相似，并且该条件很少成立。另外，如果您的树结构良好(即小容器)或结构不良(重叠容器)，则会产生巨大的差异。

k-d-tree 非常适合内存中的只读操作。对于插入，它们的表现非常糟糕。 R* 树在这里要好得多。另外，改进的 R* 树分割策略确实得到了返回，因为它比其他策略生成更多的矩形框。