关键词: 平均互信息, 类别区分性, 修剪规则, K最近邻算法, 类别特征

Abstract: Large sample size and characteristics of high dimension affects the K-Nearest Neighbor (KNN) classification algorithm in classification performance. Therefore, an improved KNN method named AMI&CD-KNN was put forward, which had feature dimension reduction and pruning mechanism based on average mutual information and class distinction of the feature parameters. Firstly, it used the concept of average mutual information in entropy to measure the accuracy of the feature parameters reflecting the class characteristic information. Secondly, it described the class distinction through the feature parameters odd ratio relative class and its distribution probability in the dataset, measured the size of the amount of class information provided by feature parameters. Finally, the relation was established between average mutual information and class distinction, and the sample pruning method was designed. Therefore, the classification was speeded up while ensuring the classification accuracy. The theoretical analysis and simulation experiment show that compared with the KNN and other algorithms with pruning mechanism, the improved algorithm has better classification generalization.

Key words: average mutual information, class distinction, pruning rule, K-Nearest Neighbor (KNN) algorithm, class feature