kd-tree是kmeans聚类的替代方案吗？

我正在使用BOW对象检测，并且正在编码阶段工作。我已经看到一些在编码阶段使用kd-tree的实现，但大多数写作都表明kmeans集群是一条可行的路。两者有什么区别？kd-tree是kmeans聚类的替代方案吗？

2012-06-18 mugetsu

kd-tree AFAIK用于标记阶段，当聚类到大量的组，数百甚至数千个时，它的速度要快得多，然后简单地采用到每个组的所有距离的argmin的幼稚方法，k-指http://en.wikipedia.org/wiki/K-means_clustering是实际的聚类算法，它的速度快但并不总是很精确，一些实现返回的组，而其他组和训练数据集的标签，这是我ussually结合使用http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.cKDTree.html与http://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.vq.kmeans2.html

来源

2012-06-18 21:54:56

所以，为了澄清一下，你将使用kmeans来量化图像描述符。那么你会从这些描述符中创建一个kdtree，以便可以在对象识别中搜索最近的邻居？ – mugetsu

@mugetsu'那么你可以从这些描述符中完成一个kdtree'，我已经做了一些基准测试，当kdtree与大量组合工作时，kdtree会将我的所有优化都抛出水面......我建议你简单地运行一些测试:) –

所以通过使用kdtree，你会跳过直方图和SVM吗？我很困惑这是如何工作的。 http://stackoverflow.com/questions/11091972/implementing-bags-of-words-object-recognition-using-vlfeat – mugetsu

在对象检测中，使用k-means来量化描述符。可以使用kd树来搜索具有或不具有量化的描述符。每种方法都有其优点和缺点。具体来说，当描述符维数超过20时，kd-tree并不比蛮力搜索好得多。

来源

2012-06-18 21:54:59

我使用SIFT描述符， 128个维度，所以我想在我的编码阶段，我应该只用k-means来量化？ – mugetsu

我已经取得了很好的表现，使用分层k-均值聚类与词汇树和每个级别的蛮力搜索。如果我需要进一步提高性能，我会考虑使用局部敏感哈希或kd-tree结合通过PCA降维。 –

通过PCA减少维度+1 –

kd-tree是kmeans聚类的替代方案吗？

回答

相关问题