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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Optimizing k-Nearest Neighbor for Color Detection

  • Omer Al Sumeri,
  • Luis Villanueva,
  • Drake Robert Sheela,
  • Hitender Singh Sidhu,
  • Jacob Luscomb,
  • Shahab Tayeb

摘要

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.