我现在正在阅读《数据挖掘：实用机器学习工具和技术第三版》一书。在 4.8 节中，它讨论了如何使用k-d trees或ball trees提高k-means algorithm.
在用所有数据点构建球树之后，它会搜索所有叶节点以查看其中的点各自靠近哪个预先选择的聚类中心。它说有时由更高的内部节点表示的区域完全落在单个集群中心的域内。这样我们就不需要遍历它的子节点，所有的日期点都可以一次处理。
问题是，在实现数据结构和算法时，如何判断指向内部节点的区域是否落入单个簇中心？
在二维或三维空间中，这并不难。我们可以看到集群中心中每一对的所有中垂线是否都穿过指向内部节点的区域。
但是在更高维空间中，如何识别呢？有没有通用的方法？
您需要考虑最大和最小距离。
如果空间对象（例如，半径为 r 的球体）与所有其他均值的最小距离大于与一个的最大距离，则容器内的所有对象都将属于该均值。因为如果
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 变得非常相似，这种情况很少会成立。此外，如果您的树结构良好（即小型容器）或结构不良（重叠容器），则会产生巨大的差异。
kd-trees 非常适合内存中的只读操作。对于插入，它们的表现相当糟糕。R*-trees 在这里好多了。此外，改进的 R*-trees 分割策略确实得到了回报，因为它比其他策略生成更多的矩形框。
我自己有一个解决方案，但在我看来不是一个很好的解决方案。
对于k维空间，两点的中垂线是一个超平面。我们计算每一对所有聚类中心的中垂线。
面对上述问题，我们看到一个节点，它可以指定一个区域——空间中的一个超球面。首先，我们找到离超球体中心点 P 最近的聚类中心。然后，我们迭代地对每对中心的每个中垂线（一个超平面），其中一个是上述中心，我们计算点 P 和点之间的欧几里德距离中垂线。如果距离小于超球面的半径，则推断超球面与中垂线相交。所以这个内部节点可能包含可能不属于上述聚类中心的数据点，迭代中断。如果迭代结束时没有break，可以说，毫无疑问，把这个节点包含的所有数据点都放到上面的聚类中心是可以的。