基于最重要特征的裁剪k-近邻分类算法设计

Design of cutting k-nearest neighbor classification algorithm based on the most important feature search

k-近邻分类算法是机器学习分类算中一个重要的算法。其精度高具有广泛应用。但时间和空间复杂度高。本文着眼于此,根据香农熵理论,提出了一种通过计算信息增益寻找对分类结果影响最大的特征,并根据该特征进行原始训练集划分并进行样本裁剪构造训练子集,在该子集上应用传统k-近邻的方法,从而降低传统k-近邻分类算法的时间复杂度。实验结果表明,该方法保持了传统k-近邻分类算法的精度,引入了最重要特征对分类结果的影响,有效降低了传统k-近邻分类算法的时间复杂度。

K- nearest neighbor classification algorithm is an important algorithm in machine learning classification. High precision makes it widely used. But it has shortcoming of high time complexity and storage space. This paper focuses on this,according to the Shannon entropy theory,proposes a method which calculates the information gain of the most important feature Influencing classification results,and according to it,divides the original training set into several subsets. Base on the subsets,this paper constructs a new training subset which has less sample than the original .After that,this paper apply the traditional k- nearest neighbor algorithm in the new training subset,in order to reduce the traditional knearest neighbor classification algorithm’s time complexity. Experimental results show that the method of this paper keeps the accuracy of the traditional k- nearest neighbor classification algorithm,and introduces the most important characteristic of the classification result,and effectively reduces the time complexity of the traditional k- nearest neighbor classification algorithm.