An optimized K-Nearest Neighbor algorithm based on Dynamic Distance approach

The k-nearest neighbors algorithm (KNN) is one of the most widely used and effective nonparametric classification algorithms. The classification mechanism of this algorithm involves computing the distance between new instance and the other instances. When the dataset contains non-numerical (ordinal and nominal) attributes, the performance of the algorithm can be significantly affected by how this distance is measured. This paper presents a distance measurement method for improving the performance of KNN. The idea of the proposed method is based on the notion of dynamic distance, which refers to the distance defined between the two values of a non-numerical attribute and depends on the nature of the problem. The determination mechanism of this dynamic distance is formulated in the form of an optimization problem, which is embedded within the structure of KNN and solved using the invasive weed optimization algorithm. The performance of the proposed algorithm is tested on the datasets of the UCI machine learning repository. The results show a minimum of 8% and a maximum of 48.1% improvement in classification accuracy, compared to classic KNN.