kee*_*ple 6 cluster-analysis machine-learning data-mining k-means
我现在正在阅读" 数据挖掘:实用机器学习工具和技术"第三版.在4.8聚类中,它讨论了如何使用k-d trees或ball trees改进性能k-means algorithm.
在用所有数据点构建球树之后,它搜索所有叶子节点以查看哪个预先选择的聚类中心各自的点都接近.它表示,较高内部节点所代表的区域有时完全属于单个集群中心的范围.然后我们不需要遍历其子节点,并且可以一次处理所有日期点.
问题是,在实现数据结构和算法时,我们如何确定引用内部节点的区域是否属于单个集群中心？
在二维或三维空间中,这并不困难.我们可以看到聚类中心中每对的所有中间垂线是否都涉及到指向内部节点的区域.
但在高维空间中,如何识别？有一般的方法吗？
您需要考虑最大和最小距离。
如果空间对象（例如，半径为 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 变得非常相似，并且该条件很少成立。另外，如果您的树结构良好（即小容器）或结构不良（重叠容器），则会产生巨大的差异。
kd 树非常适合内存中的只读操作。对于插入，它们的表现非常糟糕。R* 树在这里要好得多。另外，改进的 R* 树分割策略确实得到了回报，因为它比其他策略生成更多的矩形框。