A Fast Exact k-Nearest Neighbors Algorithm for High Dimensional Search Using k-Means Clustering and Triangle Inequality.
A Fast Exact k-Nearest Neighbors Algorithm for High Dimensional Search Using k-Means Clustering and Triangle Inequality.
复制标题
DOI：
10.1016/j.patcog.2010.01.003
复制
发表时间：
2012-02-08
期刊：
影响因子：
--
通讯作者：
Wang X
中科院分区：
文献类型：
--
作者：
Wang X
k 最近邻 (k-NN) 算法是一种广泛使用的机器学习方法，可在特征空间中查找测试对象的最近邻。我们提出了一种新的精确 k-NN 算法，称为 kMkNN（k-Means for k-Nearest Neighbors），它使用 k-means 聚类和三角不等式来加速在高维空间中搜索最近邻。 kMkNN 算法有两个阶段。在构建阶段，kMkNN 没有使用度量树、kd 树或球树等复杂的树结构，而是使用简单的 k 均值聚类方法来预处理训练数据集。在搜索阶段，给定一个查询对象，kMkNN从距查询对象最近的簇开始寻找最近的训练对象，并使用三角不等式来减少距离计算。实验表明，与传统的 k-NN 算法和基于树的 k-NN 算法（例如 kd-trees 和 ball-trees）相比，kMkNN 的性能出奇的好。在包含多达 106 个记录和 104 个维度的 20 个数据集上，对于 16 个数据集，kMkNN 的距离计算量减少了 2 到 80 倍，并且比传统的 k-NN 算法提高了 2 到 60 倍的速度。此外，对于所有数据集，kMkNN 的性能明显优于基于 kd 树的 k-NN 算法，并且对于大多数数据集，kMkNN 的性能优于基于球树的 k-NN 算法。结果表明，kMkNN 对于高维空间中的最近邻搜索是有效的。
The k-nearest neighbors (k-NN) algorithm is a widely used machine learning method that finds nearest neighbors of a test object in a feature space. We present a new exact k-NN algorithm called kMkNN (k-Means for k-Nearest Neighbors) that uses the k-means clustering and the triangle inequality to accelerate the searching for nearest neighbors in a high dimensional space. The kMkNN algorithm has two stages. In the buildup stage, instead of using complex tree structures such as metric trees, kd-trees, or ball-tree, kMkNN uses a simple k-means clustering method to preprocess the training dataset. In the searching stage, given a query object, kMkNN finds nearest training objects starting from the nearest cluster to the query object and uses the triangle inequality to reduce the distance calculations. Experiments show that the performance of kMkNN is surprisingly good compared to the traditional k-NN algorithm and tree-based k-NN algorithms such as kd-trees and ball-trees. On a collection of 20 datasets with up to 106 records and 104 dimensions, kMkNN shows a 2-to 80-fold reduction of distance calculations and a 2- to 60-fold speedup over the traditional k-NN algorithm for 16 datasets. Furthermore, kMkNN performs significant better than a kd-tree based k-NN algorithm for all datasets and performs better than a ball-tree based k-NN algorithm for most datasets. The results show that kMkNN is effective for searching nearest neighbors in high dimensional spaces.
登录
查看更多内容
影响因子：
8
作者：
Chen, Yong-Sheng;Hung, Yi-Ping;Fuh, Chiou-Shann
通讯作者：
Fuh, Chiou-Shann
影响因子：
1.1
作者：
SPROULL, RF
通讯作者：
SPROULL, RF
影响因子：
8.3
作者：
Tai, SC;Lai, CC;Lin, YC
通讯作者：
Lin, YC
影响因子：
8
作者：
Lai, Jim Z. C.;Liaw, Yi-Ching;Liu, Julie
通讯作者：
Liu, Julie
影响因子：
8
作者：
Liaw, Yi-Ching
通讯作者：
Liaw, Yi-Ching