训练样本分布不均knn分类改进算法

《训练样本分布不均knn分类改进算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、训练样本分布不均KNN分类改进算法　　摘要：分类是数据挖掘的重要组成部分，它根据类标号已知的数据建立模型，进而使用该模型来预测类标号未知的数据所属的类。KNN方法作为一种简单、有效、非参数的分类方法，在文本分类中得到广泛的应用，但是这种方法在训练样本的分布不均匀时会造成分类准确率的下降。针对KNN方法存在的这个问题，本文提出了一种基于相对距离的KNN分类方法，这种方法减少了边界点处测试样本的误判。实验结果显示，这种方法具有很好的性能。Abstract：Classificationisanessentialpartofdatamining.Itbuildsamodelacco

2、rdingtothedatawhoseclasslabelsareknown，andthenusesthismodeltopredicttheclassesofthedatawhoseclasslabelsareunknown.Asasimple，effectiveandnonparametricclassificationmethod，KNNmethodiswidelyusedindocumentclassification.ButKNNclassifiermaydecreasetheprecisionofclassificationbecauseoftheunevend

3、ensityoftrainingdata.Inthispaper，arelative-distancemethodwhichsolvesproblemmentionedaboveispresented.Itdecreasesthewrongclassification8betweentheedgeofclasses.Theexperimentalsoshowsthatithasgoodperformance.关键词：KNN；相对距离；准确率Keywords：KNN；relative-distance；precision中图分类号：TP181文献标识码：A文章编号：1006-

4、4311（2014）02-0180-030引言KNN分类算法是一种易于理解和实现的算法，其基本思想是在训练样本中找到测试样本的k个最近邻，然后根据这k个最近邻的类别来决定测试样本的类别；KNN分类是一种基于要求的或懒惰的学习方法，它存放所有的训练样本，直到测试样本需要分类时才建立分类，由于现在的计算机有强大的计算性能，KNN算法的较差的时间性能已不在是太大的问题；但是，训练样本分布的不均匀性也会造成分类准确率的下降。本文提出了一种基于相对距离的KNN算法，在计算测试样本与训练样本之间的距离时，利用相对距离进行计算。实验结果显示削弱了训练样本分布的不均匀性对分类性能的影响，提

5、高了分类的准确率。1训练样本分布不均对分类结果的影响8KNN方法实际上是一种基于类比的学习方法，这就要求训练样本中样本必须具有代表性，这种代表性不仅应该体现在样本间的距离（或相似度）上，还应该体现在样本分布的均匀性上。为了描述方便，下面我们以二维空间两种分类为例，看一下训练样本的分布密度对KNN分类器分类结果的影响。从图1我们可以看到KNN方法存在以下问题。在类边界区域，训练样本分布的不均匀性可能会造成测试样本类别的误判。在图1中，我们可以直观地看到测试样本应该属于类2，但是由于类1比类2的分布密度要大，这样当我们选测试样本的7个最近邻来判别它的类别时，分类器就出现了误判，

6、如果k值更大些，则误判更为明显。而在实际设计分类器的时候，由于一些类别比另一些类别的训练样本更容易获得，往往会造成训练样本分布的不均匀，而且，即使训练样本在各个类中的数目基本接近，由于其所占区域大小的不同，也会造成训练样本分布的不均匀。针对训练样本分布不均时KNN分类算法中容易出现误判的问题，本文提出基于相对距离的KNN算法。其基本思想是：首先计算训练集各个类的1-最近邻距离均值；然后对测试样本利用相对距离进行KNN分类。2基于相对距离的KNN算法2.1相关概念为便于描述，我们引入以下一些概念：8给定一个样本集D={X1，…，XL}，其中Xi∈Rn，i=1，…，L；设样本共

7、有ClassNum个类；设Ci表示第i类中的所有样本的集合，且Ci∩Cj=Φ（i，j=1，…，ClassNum），样本集也可表示为：D=C1∪C2∪…∪Cr。定义1两个样本间的距离，设数据集D有m个属性，其数据库模式为R（A1，A2，…，Am），X（x1，x2，…，xm）和Y（y1，y2，…，ym）分别为数据集D中的两个样本，则X与Y的距离度量公式为：Dist（X，Y）=■一般来说，我们习惯使用欧几里德距离，即取ρ=2。定义2设Dist（X，Y）代表样本集D中两个样本X和Y间的距离，则测试样本中第i类的1-最近邻距