关键词: 聚类, k-最近邻, 三角不等式, 宽度加权, 高维数据

Abstract: The traditional k-Nearest Neighbor（kNN） algorithm has a wide range of applications as a non-parameterized data clustering algorithm. However, the algorithm has more redundancy calculations, which leads to more computation time when processing data. A large amount of research is currently focused on the preprocessing stage of data, and the computational complexity of kNN queries is reduced by modeling the data. This paper proposes a width-weighted clustering kNN algorithm based on the number of objects for kNN query（NOWCkNN）. The algorithm performs width learning based on the number of objects. Firstly, data sets are clustered with global width, and then each generated cluster calculates the weight of its width recursively based on the number of objects. The algorithm can adjust the width value according to the number of cluster’s objects. In terms of clustering, the algorithm not only reduces clustering time and the number of iterations, but also balances cluster size and maximizes the trigonometric inequality. Experimental results show that the work outperforms than the existing works in all dimensions of datasets, especially in high-dimensional and large datasets.

Key words: clustering, k-Nearest Neighbors（kNN）, trigonometric inequality, width-weighted, high-dimensional data