Optimizing k-Nearest Neighbor for Color Detection
摘要
This paper presents an improvement to the efficiency of the k-Nearest Neighbor (KNN) algorithm by reducing its time and space complexity while keeping accuracy high. KNN is a popular classification algorithm in machine learning that classifies a new data point by considering the k-number of nearest neighbors surrounding it. However, the naive implementation of KNN requires computing the distance of the entire dataset to the unknown point, resulting in significant time and space consumption. To address this issue, a new implementation of KNN is proposed for datasets that have distinct clusters of condensed data points. The new implementation reduces the clusters of condensed data points into a single data point. The k-value is improved from the square root of n to 1; where n is the total number of points in the dataset and 1 comes from the single closest data point to the unknown point. This new implementation significantly reduces the time and space complexity of the KNN algorithm. The clusters of data now represented by a single point reduce the number of comparisons and the amount of data the machine needs to store to use the algorithm. A color detection application was used to analyze the results from the naive to the improved implementation. Time complexity, space complexity, and an accuracy experiment were done to test the improved implementation from the naive. It is concluded that the improved implementation outperforms the naive in both space and time complexity while keeping the same accuracy.