基于属性信息熵的knn算法改进研究

《基于属性信息熵的knn算法改进研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、漳州师范学院硕士学位论文基于属性信息熵的KNN算法改进研究姓名：童先群申请学位级别：硕士专业：计算机应用技术指导教师：周忠眉20100601摘要摘要分类是数据挖掘任务之一，KNN算法是一种思路简单，易于实现的分类算法。KNN根据未知样本的K个近邻样本来预测未知样本的类别，近邻样本的选择是根据一定的距离公式判定的。距离的定义直接影响K个近邻样本的选取，最终影响分类的准确率。许多学者都对距离进行研究，但基本都没有考虑到属性值对类别的重要性。信息熵可用来度量属性值对类别的重要性，信息熵越小，此属性值对类别的重要性越大。本文首先采用信息熵度量属性值的重要性，给出

2、一种新的基于属性值信息熵的距离定义，同时投票时综合考虑各类近邻样本的平均距离及个数，提出了一种基于属性值信息熵的KNN改进算法Entropy-KNN。蘑菇数据集上实验表明Entropy-KNN算法的分类准确率高于传统KNN算法和距离加权KNN算法。其次，为了进一步提高分类的准确率，提出一种基于层次聚类法的Entropy-KNN算法，采用层次聚类法对每类的训练样本进行聚类后，选取与测试样本最接近的聚类作为新的训练集，最后对测试集进行Entropy-KNN算法分类。蘑菇数据集上实验表明此算法进一步提高Entropy-KNN算法的准确率。最后，为了加快分类的速

3、度，提出基于属性约简的Entropy-KNN算法，先对训练集进行属性约简，接着在测试集使用Entropy-KNN算法进行分类。关键词：分类；KNN算法；信息熵；距离；IAbstractAbstractClassificationisoneofresearchdirectionsofdatamining.TheKNNalgorithmisclearandeasyclassificationalgorithm.TheclasslabeldecisionoftheunknownsamplecomesfromtheKnearestneighbors,whichi

4、sdecidedbythedistance.ThedefinitionofthedistanceisdirectlyrelatedoftheselectionoftheKnearestneighbors,andeffectstheKNNclassificationaccuracy.ManypeoplewereabsorbedintheresearchoftheKNNdistance,whilefewpeopleconsideredtherelationbetweentheclasslabelandtheimportantattributevalue.In

5、formationentropycanmeasuretheclassficationimportantceoftheattributevalue.Ifitisless,thentheattributevalueismoreimportant.Inthepaper,animprovedalgorithmEntropy-KNNbasedontheinformationentropyofanattributevalueisproposed.Firstly,adistanceofthetwosamplesisdefinedastheaverageinformat

6、ionentropyofthesameattributevalues.Andthenwedecidetheclasslabelofthetestsamplebytheaveragedistanceandthenumbersontherespectiveclass.TheexperimentresultsonthemushroomdatashowthatourapproachhasmuchbetterthantraditionalKNNandKNNwithweighteddistance.Thenamethodbasedonhierarchicalaggl

7、omerativeclusteringandEntropy-KNNispresentedforthehigherclassificationaccuracy.Afterrepresentativesamplessetoftrainingsetsareacquiredbasedonthehierarchicalclusteralgorithm,therepresentativesamplessetistakenastheinitialsetoftheEntropyKNNalgorithmtofurthermaintain.Theexperimentresu

8、ltsonthemushroomshowthatourapproachhasbe