我正在阅读《数据挖掘：实用机器学习工具与技术第三版》这本书。在第4.8节聚类部分，它讨论了如何使用k-d树或球树来提高k-means算法的性能。
在用所有数据点构建球树后，它会搜索所有叶节点，看看这些节点中的点分别靠近哪个预选的聚类中心。它提到，有时由较高层次的内部节点代表的区域完全落在一个单一聚类中心的范围内。那么我们就不需要遍历它的子节点，所有数据点可以一次性处理完毕。
问题是，在实现数据结构和算法时，我们如何判断一个内部节点所指的区域是否落入一个单一聚类中心？
在二维或三维空间中，这并不困难。我们可以查看聚类中心每对之间的中垂线是否穿过内部节点所指的区域。
但在更高维度的空间中，该如何识别呢？是否有通用的方法论？
回答：
你需要考虑最大和最小距离。
如果一个空间对象（比如半径为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变得非常相似，且该条件很少成立。此外，如果你的树结构良好（即小容器）或结构不好（重叠容器），这会产生巨大的差异。
k-d树适用于内存中只读操作。对于插入操作，它们的表现相当差。R*-树在这方面表现得更好。此外，R*-树改进的分割策略是有回报的，因为它生成的盒子比其他策略更接近矩形。
