NNB: An efficient nearest neighbor search method for hierarchical clustering on large datasets
NNB: An efficient nearest neighbor search method for hierarchical clustering on large datasets
复制标题
DOI：
10.1109/icosc.2015.7050840
复制
发表时间：
2015-03
期刊：
影响因子：
--
通讯作者：
Wei Zhang-;Gongxuan Zhang;Yongli Wang;Zhaomeng Zhu;Tao Li
中科院分区：
文献类型：
--
作者：
Wei Zhang-;Gongxuan Zhang;Yongli Wang;Zhaomeng Zhu;Tao Li
最近邻搜索是层次聚类中的一项关键技术。标准的凝聚层次聚类的时间复杂度是O（n3），而更高级的层次聚类算法（如最近邻链）的时间复杂度是O（n2）。本文提出了一种新的最近邻搜索方法--最近邻边界（NNB），该方法首先将一个大数据集划分成独立的子集，然后在子集中找到每个点的最近邻。当使用NNB时，层次聚类的时间复杂度可以降低到O（nlog 2n）。在NNB的基础上，提出了一种快速的层次聚类算法--最近邻边界聚类（NBC），该算法也适用于并行和分布式计算框架。实验结果表明，该算法对大数据集是实用的。
Nearest neighbor search is a key technique used in hierarchical clustering. The time complexity of standard agglomerative hierarchical clustering is O(n3), while the time complexity of more advanced hierarchical clustering algorithms (such as nearest neighbor chain) is O(n2). This paper presents a new nearest neighbor search method called nearest neighbor boundary(NNB), which first divides a large dataset into independent subsets and then finds nearest neighbor of each point in the subsets. When NNB is used, the time complexity of hierarchical clustering can be reduced to O(n log2n). Based on NNB, we propose a fast hierarchical clustering algorithm called nearest-neighbor boundary clustering(NBC), and the proposed algorithm can also be adapted to the parallel and distributed computing frameworks. The experimental results demonstrate that our proposal algorithm is practical for large datasets.