kdtree 是否用于加速 k 均值聚类？

Question

我正在使用 k-means 做一个项目，我的教授建议使用 kdtree。我在 python 中找到了 kdtree 的实现（我知道 scipy 中也有，但我找不到任何示例实现）。我的问题与标题相同，是使用kdtree来加速k-means，还是我错了？

data = [(2,2),(1,0),(2,3),(10,5),(59,8),(4,2)]

tree = KDTree.construct_from_data(data)
nearest = tree.query(query_point=(5,4), t=3)
print nearest

输出：

[(4, 2), (2, 3), (2, 2)]

Answer 1

正如“让 k 均值更快”，第 137 页，论文表明，kd 树可用于加速低维数据的 k 均值算法，而直接的劳埃德算法对于高维数据更有效。

对于高维数据，kd树等索引方案效果不佳

请参阅论文中的解释。

我建议您使用一种已建立的 k-means 实现，并且只有在遇到严重问题时才担心速度的提高。例如，据我所知，sklearn 的KMeans是基于 Lloyd 的原始算法。