K近邻分类算法.docx

K近邻分类算法（K–nearestneighbors，简称KNN）
算法的提出与发展
最初的近邻法是由Cover和Hart与1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。
算法原理
2.1基本原理
最近邻方法(k-nearestneighbor,简称kNN)是一种简洁而有效的非参数分类方法，是最简单的机器学习算法之一，该算法最初由Cover和Hart提出的，用于解决文本的分类问题。
K近邻算法是最近邻算法的一个推广。该规则将是一个测试数据点x分类为与它最接近的K个近邻中出现最多的那个类别。K近邻算法从测试样本点x开始生长，不断的扩大区域，直到包含进K个训练样本点为止，并且把测试样本点x归为这最近的K个训练样本点中出现频率最大的类别。其中测试样本与训练样本的相似度一般使用欧式距离测量。
如果K值固定，并且允许训练样本个数趋向于无穷大，那么，所有的这K个近邻都将收敛于x。如同最近邻规则一样，K个近邻的标记都是随机变量，概率P（wi|x），i=1,2,…,K都是相互独立的。假设P（wm|x）是较大的那个后验概率，那么根据贝叶斯分类规则，则选取类别wm。而最近邻规则以概率P（wm|x）选取类别。而根据K近邻规则，只有当K个最近邻中的大多数的标记记为wm，才判定为类别wm。做出这样断定的概率为

通常K值越大，选择类别wm概率也越大。
K值的选择
K近邻规则可以被看作是另一种从样本中估计后验概率P（wi|x）的方法。为了得到可高的估计必须是的K值越大越好。另一方面，又希望又希望x的K个近邻x距离x1越近越好，因为这样才能保证P（wi|x1）尽可能逼近P（wi|x）。在选取K值的时候，就不得不做出某种折衷。只有当n趋近于无穷大时，才能保证K近邻规则几乎是最优的分类规则。
K值的选择：需要消除K值过低，预测目标容易产生变动性，同时高k值时，预测目标有过平滑现象。推定k值的有益途径是通过有效参数的数目这个概念。有效参数的数目是和k值相关的，大致等于n/k，其中，n是这个训练数据集中实例的数目。
确定K的值：通过实验确定。进行若干次实验，取分类误差率最小的k值。
算法步骤
依公式计算Item与D1、D2……、Dj之相似度。得到Sim(Item,D1)、Sim(Item,D2)……、Sim(Item,Dj)。
将Sim(Item,D1)、Sim(Item,D2)……、Sim(Item,Dj)排序，若是超过相似度门槛t则放入邻居案例集合NN。
自邻居案例集合NN中取出前k名，依多数决，得到Item可能类别。
KNN优缺点
优点：1）原理简单，实现起来比较方便；
2）支持增量学习；
3）能对超多边形的复杂决策空间建模。
缺点：1）样本的不均衡可能造成结果错误：如果一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。
2）计算量较大，需要有效的存储技术和并行硬件的支撑：因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。
KNN的改进
针对上述KNN算法的几个主要缺陷，主要有以下三类改进方法：
1）为了降低样本的不均衡对结果造成的不好影响可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
2）对于计算量大的问题目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。这样可以挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到减少计算量，有减少存储量的双重效果。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
3）对样本进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本领域的小范围内，避免盲目地与训练样本集中的每个样本进行距离计算。
4.1快速搜索近邻法
其基本思想是将样本集按邻近关系分解成组，给出每组的质心所在，以及组内样本至该质心的最大距离。这些组又可形成层次结构，即组又分子组，因而待识别样本可将搜索近邻的范围从某一大组，逐渐深入到其中的子组，直至树的叶结点所代表的组，确定其相邻关系。这种方法着眼于只解决减少计算量，但没有达到减少存储量的要求。
用树结构表示样本分级：
p:树中的一个结点，对应一个样本子集Kp
Np:Kp中的样本数
Mp:Kp中的样本均值
rp:从Kp中任一样本到Mp的最大距离

规则1：如果满足：则Kp中的样本都不可能是x的最近邻，B是算法执行中当前到x的最近距离
规则2：如果满足：则xi不是x的最近邻
剪辑近邻法
其基本思想是，利用现有样本集对其自身进行剪辑，将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。
剪辑的过程是：将样本集KN分成两个互相独立的子集：test集KT和