Efficient Computational Cost Reduction in KNN through Maximum Entropy Clustering

The K Nearest Neighbor (KNN) is a widely-used classification algorithm recognized for its simplicity and applicability across diverse domains in classification tasks. Despite its straightforward nature, KNN encounters a notable challenge regarding computational costs per classification instance. This paper introduces an algorithm to address this challenge by incorporating entropy-based clustering into the KNN algorithm. Unlike traditional distance-based clustering methods, the proposed algorithm involves partitioning data into disjoint clusters and minimizing entropy within the neighbors. Representative points are then extracted from these clusters to compute nearest neighbors. Experimental results on various UCI datasets reveal a significant reduction in computational costs achieved by utilizing a smaller set of representative samples to represent data instances. Furthermore, the statistical t-test analysis of the accuracy results indicates that KNN performs similarly when utilizing entropy-based representatives.