«上一篇/Previous Article|本期目录/Table of Contents|下一篇/Next Article»

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:

29

期数:

2019年09期

页码:

51-54

栏目:

智能、算法、系统工程

出版日期:

2019-09-10

文章信息/Info

Title:

K-Nearest Neighbor Algorithm Based on Information Gain and Gini Impurity

文章编号:

1673-629X(2019)09-0051-04

作者:

孙 傲; 赵礼峰

南京邮电大学 理学院,江苏 南京 210023

Author(s):

SUN Ao; ZHAO Li-feng

School of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China

关键词:

数据挖掘; K 近邻; 信息增益; 基尼不纯度

Keywords:

data mining; K-nearest neighbor; information gain; Gini impurity

分类号:

TP301.6

DOI:

10. 3969 / j. issn. 1673-629X. 2019. 09. 010

摘要:

传统 K 近邻算法忽略每个属性对分类的不同重要程度,将每个属性同等看待,在计算样本间距离时赋予每个属性相同的权重,影响样本分类的正确性。 利用单一指标来确定属性重要性过于片面,无法全面反应属性对分类的重要程度。针对这一问题,利用信息增益和基尼不纯度的综合指标作为判断属性重要程度的指标,该综合指标越大,属性对分类的重要程度越高。 并依据综合指标构造属性权重,计算样本间的加权距离进行分类。 为验证该方法的有效性,分别基于 UCI数据库中 Iris 数据集和 Wine 数据集对基于信息增益和基尼不纯度综合指标的加权 K 近邻算法进行仿真实验,并与传统 K 近邻算法和基于信息增益加权 K 近邻算法进行对比,基于信息增益和基尼不纯度综合指标的加权 K 近邻算法错误率均低于传统 K 近邻算法和基于信息增益加权 K 近邻算法。 结果表明该方法比传统 K 近邻法和基于单一指标加权 K 近邻算法能更有效地对样本进行分类。

Abstract:

The traditional K-nearest neighbor algorithm ignores the importance of each attribute to the classification,and treats each attribute equally. When calculating the distance between samples,the same weight is given to each attribute,which affects the correctness of the sample classification. The use of a single indicator to determine the importance of attributes is too one-sided and does not fully reflect the importance of attributes to classification. Aiming at this problem,the comprehensive index of information gain and Gini impurity is used as the index to judge the importance of the attribute. The larger the comprehensive index,the higher the importance of the attribute to the classification. The attribute weights are constructed according to the comprehensive index,and the weighted distance between the samples is calculated for classification. In order to verify the effectiveness of the proposed method,the weighted K-neares neighbor algorithm based on information gain and Gini impurity comprehensive index is simulated based on Iris dataset and Wine datasetin UCI database,and compared with traditional K-nearest neighbor algorithm and information gain-based weighting. Compared with the K-nearest neighbor algorithm,the error rate of the weighted K-nearest neighbor algorithm based on the information gain and Gini ntegrity comprehensive index is lower than the traditional K-nearest neighbor algorithm and the information-gain-weighted K-nearest neighbor algorithm. The results show that the proposed method can classify samples more effectively than the traditional K-nearest neighbor method and the single-index weighted K-nearest neighbor algorithm.

常用功能

更新日期/Last Update: 2019-09-10