Closed K-means improved algorithm with triangular inequality

• 1、Key Laboratory of Fiber Optic Sensing Technology and Information Processing, Ministry of Education, Wuhan University of Technology, Wuhan 430070
• 2、Department of Electrical and Computer Engineering，University of Houston， Houston, TX 77204

Abstract：This paper introduces a closed K-means improved algorithm that adds triangular inequalities, which significantly improves the computational efficiency of the traditional k-means algorithm. The improvement method mainly considers that the calculation process of the vast majority in the traditional K-means redistribution process is unnecessary, because the algorithm needs to find the nearest cluster center point, but does not care about the distance between the data points and other cluster centers. This improvement is based on the spirit of the Kd-tree with BBF algorithm, and the similarities mentioned in this article.First, the triangle inequality is used to determine the range of points that each cluster center does not need to calculate, and then the data is formed into neighbor points by using multiple random space partition trees to effectively identify those points that are easy to "move". The experimental results show that this method has higher computational efficiency than the traditional algorithm in computing large visual vocabulary datasets, and reduces the computation time by about 41%. This paper also evaluates the impact of some parameters, including the total amount of data, the number of clusters, and the threshold size. They have been shown that different parameter selection can effectively reduce time consumption, but at the cost of clustering.

Keywords： Image Processing K-means algorithm Principle of triangular inequality Random tree