KNN算法总结
KNN算法总结
1 KNN分类算法
1.1KNN简述
K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别[1]。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
KNN最邻近规则，主要应用领域是对未知事物的识别，即判断未知事物属于哪一类，判断思想是，基于欧几里得定理，判断未知事物的特征和哪一类已知事物的的特征最接近。
1.2 KNN原理
最近邻方法(k-nearest neighbor,简称kNN)是一种简洁而有效的非参数分类方法，是最简单的机器学习算法之一，该算法最初由Cover和Hart提出的，用于解决文本的分类问题。
K近邻算法是最近邻算法的一个推广。该规则将是一个测试数据点x分类为与它最接近的K个近邻中出现最多的那个类别。K近邻算法从测试样本点x开始生长，不断的扩大区域，直到包含进K个训练样本点为止，并且把测试样本点x 归为这最近的K个训练样本点中出现频率最大的类别。其中测试样本与训练样本的相似度一般使用欧式距离测量。
如果K值固定，并且允许训练样本个数趋向于无穷大，那么，所有的这K个
近邻都将收敛于x。如同最近邻规则一样，K个近邻的标记都是随机变量，概率P（w i|x），i=1,2,…,K都是相互独立的。假设P（w m|x）是较大的那个后验概率，那么根据贝叶斯分类规则，则选取类别w m。而最近邻规则以概率P（w m|x）选取类别。而根据K近邻规则，只有当K个最近邻中的大多数的标记记为w m，才判定为类别w m。做出这样断定的概率为
通常K值越大，选择类别w m概率也越大[2]。
K近邻法是有监督学习方法，原理很简单，假设我们有一堆分好类的样本数据，分好类表示每个样本都一个对应的已知类标签，当来一个测试样本要我们判断它的类别是，就分别计算到每个样本的距离，然后选取离测试样本最近的前K 个样本的标签累计投票，得票数最多的那个标签就为测试样本的标签。
下面我们用电影的分类来简述KNN的原理例子（电影分类）：
图1.1 电影分类
图1.1中横坐标表示一部电影中的打斗统计个数，纵坐标表示接吻次数。我们要对图中的问号这部电影进行分类，其他几部电影的统计数据和类别如表1.1所示：
表1.1
Movie title# of kicks#of kisses Type of movie
从表1.1中可以看出有三部电影的类别是Romance,有三部电影的类别是Action,那如何判断问号表示的这部电影的类别？根据KNN原理,我们需要在图1.1所示的坐标系中计算问号到所有其他电影之间的距离。计算出的欧式距离如表1.2所示：
表1.2
由于我们的标签只有两类，那假设我们选K=6/2=3,由于前三个距离最近的电影都是Romance,那么问号表示的电影被判定为Romance。
1.3KNN的应用
KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性[3]。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比（组合函数）。
（1）文本分类：文本分类主要应用于信息检索，机器翻译，自动文摘，信息
过滤，邮件分类等任务。文本分类在搜索引擎中也有着大量的使用，网页分类/分层技术是检索系统的一项关键技术，搜索引擎需要研究如何对网页进行分类、分层，对不同类别的网页采用差异化的存储和处理，以保证在有限的硬件资源下，提供给用户一个高效的检索系统，同时提供给用户相关、丰富的检索结果。在搜索引擎中，文本分类主要有这些用途：相关性排序会根据不同的网页类型做相应的排序规则；根据网页是索引页面还是信息页面，下载调度时会做不同的调度策略；在做页面信息抽取时，会根据页面分类的结果做不同的抽取策略；在做检索意图识别的时候，会根据用户所点击的url所属的类别来推断检索串的类别。
（2）回归：通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。
（3）可以使用knn算法做到比较通用的现有用户产品推荐，基于用户的最近邻(长得最像的用户)买了什么产品来推荐是种介于电子商务网站和sns网站之间的精确营销。只需要定期(例如每月)维护更新最近邻表就可以，基于最近邻表做搜索推荐可以很实时[4]。
1.4 KNN的核心思想
K-NN可以说是一种最直接的用来分类未知数据的方法。基本通过下面这张图1.2跟文字说明就可以明白K-NN的思想是什么
图1.2
简单来说，K-NN可以看成：有那么一堆你已经知道分类的数据，然后当一个新数据进入的时候，就开始跟训练数据里的每个点求距离，然后挑离这个训练数据最近的K个点看看这几个点属于什么类型，然后用少数服从多数的原则，给新数据归类。
kNN算法的核心思想是如果一个样本在特征空间中的k个最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别[5]。kNN方法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。
1.5算法步骤
step.1---初始化距离为最大值
step.2---计算未知样本和每个训练样本的距离dist
step.3---得到目前K个最临近样本中的最大距离maxdist
step.4---如果dist小于maxdist，则将该训练样本作为K-最近邻样本
step.5---重复步骤2、3、4，直到未知样本和所有训练样本的距离都算完
step.6---统计K-最近邻样本中每个类标号出现的次数
step.7---选择出现频率最大的类标号作为未知样本的类标号
2 K值的选择
2.1交叉验证(Cross-validation)
交叉验证(Cross-validation)主要用于建模应用中，例如PCR 、PLS 回归建模中。在给定的建模样本中，拿出大部分样本进行建模型，留小部分样本用刚建立的模型进行预报，并求这小部分样本的预报误差，记录它们的平方加和。这个过程一直进行，直到所有的样本都被预报了一次而且仅被预报一次。把每个样本的预报误差平方加和，称为PRESS(predicted Error Sum of Squares)。
K折交叉验证，初始采样分割成K个子样本，一个单独的子样本被保留作为验证模型的数据，其他K-1个样本用来训练。交叉验证重复K次，每个子样本验证一次，平均K次的结果或者使用其它结合方式，最终得到一个单一估测。这个方法的优势在于，同时重复运用随机产生的子样本进行训练和验证，每次的结果验证一次，10折交叉验证是最常用的。
2.2 K值的选择
K近邻规则可以被看作是另一种从样本中估计后验概率P（w i|x）的方法。为了得到可高的估计必须是的K值越大越好。另一方面，又希望又希望x的K 个近邻x 距离x1越近越好，因为这样才能保证P（w i|x1）尽可能逼近P（w i|x）。在选取K 值的时候，就不得不做出某种折衷。只有当n趋近于无穷大时，才能保证K 近邻规则几乎是最优的分类规则。
K值的选择：需要消除K值过低，预测目标容易产生变动性，同时高k值时，预测目标有过平滑现象。推定k值的有益途径是通过有效参数的数目这个概念。
有效参数的数目是和k值相关的，大致等于n/k，其中，n是这个训练数据集中实例的数目。
确定K的值：通过实验确定。进行若干次实验，取分类误差率最小的k值。KNN 算法的分类效果很大程度上依赖于k 值的选取，以往人们都是根据个人经验来定。k 值选择过小，得到的近邻数过少，会降低分类精度；而如果k 值过大，容易造成噪声数据增加而降低分类准确率。最极端的情况下，参数k 取数据库中所有样本的个数，则新样本的分类结果为全局最优解，否则分类结果为局部最优解。所以，参数k 是全局最优解和局部最优解的一个折衷。针对k 值选择问题，文献［6］提出了根据上下文动态调整k 值的选择。中科院的STan 提出了一种适应性的KNN改进算法［7］，对样本数差异较大的类别,设定不同的K 值,减少了算法对样本分布的依赖性。如图2.1所示：
图2.1
此图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类
在给定了度量方式以后，我们自然而然会遇到一个问题就是到底要找多少个邻居才合适了，如图2.2所示，X是待分类样本，‘+’和‘-’是样本类别属性，如果K选大了的话，可能求出来的k最近邻集合可能包含了太多隶属于其它类别的样本点，最极端的就是k取训练集的大小，此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的累，模型过于简单，忽略了训练实例中大量有用信息。如果K选小了的话，结果对噪音样本点很敏感。那么到底如何选取
K值，其实我在前面也说了，其实完全靠经验或者交叉验证（一部分样本做训练集，一部分做测试集）的方法，就是是K值初始取一个比较小的数值，之后不段来调整K值的大小来时的分类最优，得到的K值就是我们要的，但是这个K值也只是对这个样本集是最优的。一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。下面我们可以通过交叉验证的方式求出最合适的K值，对iris数据（UCI Machine Learning Repository下载）用kNN算法进行分类，通过交叉验证（10次）的方式，对k取不同值时进行了实验，实验结果如图2.2所示，其中红线指的是实验选用的Ｋ值，黄线指的是实验的结果，我们发现在我所选取的k值中，当k=17时效果最好，在k=1时，即用最近邻来进行分类的效果也不错，实验结果呈现一个抛物线，与我们之前分析的结果相吻合。
图2.2
3 KNN算法的优缺点
K近邻法(K Nearest Neighbor，KNN)由Cover和Hart提出来的，是一种懒惰的、有监督的、基于实例的机器学习方法。相关研究证明该分类方法是向量空间
模型下最好的分类算法之一。
KNN的分类过程可以理解成：先将训练文本集中的所有文本表示成向量的形式，形成向量文本集并存储起来，当一个新的待分类文本到达时，计算该文本和训练文本集中每一个文本的相似度，并将计算得到的值按降序排列，选取出排在最前面的K篇文本，然后依照这K篇文本的类别对新文本进行归类。在依据这K篇文本确定待分类文本的类别时，通常有两种方法：，
1．对选出的这K篇文本进行统计，看大多数属于哪一类，就把这个待分类文本归到这个类中。
2．对这K篇文本与待分文本的相似度按公式(3-1)进行求和，将属于同一个类的文本的相似度相加求和，然后对每个类所求得的和进行排序，将待分类文本归到相似度和较大的那个类中。本文选用第二种方法。
k
T j(d)=T j(d i)sim(d，d i) (3-1)
I=1
其中，k表示选取的文本数：T j(d i)表示文本西是否属于C i类(若属于，则值为1；否则值为0)；)sim(d，d i)即为所求。
通过对KNN算法的分析我们可知，该分类算法的优点主要有：
1．思路比较简单并且实现起来比较容易；
2．当向训练样本集中加入新的文本时，不需要重新训练，因此可以减少训练时间。
虽然KNN有着上述的优点，但它也存在着一些缺点，如：
1．对待分文本类别的确定是根据选出的K篇文本来决定的，所以对K值的选取将会影响分类的效果，但是目前只能通过不断的实验来调整K的取值；
2．使用KNN对新进待分类文本进行分类时，首先要把训练文本集中的所有文本都存储起来，以便计算新文本和所有训练文本的相似度，用以选出较为相似的前K篇文本，因此，无论是计算文本间相似度所用的时间，还是存储训练文本所占用的空间，都会随着训练集文本规模的变大和特征维数的增加而增加，其时间复杂度可以用O(m*n)来表示，其中m是选出的特征项的个数，n是训练集中文本的个数。
该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K 个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的
样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分[8]。
4 KNN算法的改进
针对上述KNN算法的几个主要缺陷，主要有以下三类改进方法：
1）为了降低样本的不均衡对结果造成的不好影响可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
2）对于计算量大的问题目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。这样可以挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到减少计算量，有减少存储量的双重效果。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
3）对样本进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本领域的小范围内，避免盲目地与训练样本集中的每个样本进行距离计算。
4.1 快速搜索近邻法
其基本思想是将样本集按邻近关系分解成组，给出每组的质心所在，以及组内样本至该质心的最大距离。这些组又可形成层次结构，即组又分子组，因而待识别样本可将搜索近邻的范围从某一大组，逐渐深入到其中的子组，直至树的叶结点所代表的组，确定其相邻关系。这种方法着眼于只解决减少计算量，但没有达到减少存储量的要求。
用树结构表示样本分级：
p: 树中的一个结点，对应一个样本子集K p
N p : K p中的样本数
M p : K p中的样本均值
r p : 从K p中任一样本到M p的最大距离
规则1：
如果满足：
则K p中的样本都不可能是x的最近邻，B是算法执行中当前到x 的最近距离
规则2：
如果满足：
则x i不是x的最近邻
4.2剪辑近邻法
其基本思想是，利用现有样本集对其自身进行剪辑，将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。
剪辑的过程是：将样本集K N分成两个互相独立的子集：test集K T和reference 集K R。首先对K T中每一个X i在K R中找到其最近邻的样本Y i(X i) 。如果Y i与X i不属于同一类别，则将X i从K T中删除，最后得到一个剪辑的样本集K TE（剪辑样本集），以取代原样本集，对待识别样本进行分类。
4.3压缩近邻法
利用现有样本集，逐渐生成一个新的样本集，使该样本集在保留最少量样本的条件下，仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类，并保持正常识别率。
定义两个存储器，一个用来存放即将生成的样本集，称为Store；另一存储器则存放原样本集，称为Grabbag。其算法是：
1)初始化。Store是空集，原样本集存入Grabbag；从Grabbag中任意选择一样本放入Store
中作为新样本集的第一个样本。
2)样本集生成。在Grabbag中取出第i个样本用Store中的当前样本集按最近邻法分类。
若分类错误，则将该样本从Grabbag转入Store中，若分类正确，则将该样本放回Grabbag 中。
3)结束过程。若Grabbag中所有样本在执行第二步时没有发生转入Store的现象，或
Grabbag已成空集，则算法终止，否则转入第二步。
5 ML-KNN
ML—KNN是张敏灵和周志华提出的一种简单的非参数化的多标记学习分类器，它使用K最近邻算法，统计近邻样本的类别标记信息，通过最大化后验概率的方式推理未见示例的标记集合．与其它方法相比，具有方法简单、错误率较低的特点，它的分类精度取决于训练样本的可靠性与属性的选择．2009年，张敏灵等人又提出了MLNB算法，先用PCA进行特征抽取去除无关冗余属性，然后定义一个损失函数并使用生成算法(GA)得到最适合分类的特征子集，最后利用MLNB—BASIC算法对选择后的数据集进行学习[9]．
5.1 ML-KNN算法
给定多标记训练集D={(xi，yi)l 1≤i≤P)以及未见示例x，假设N(x)代表x在训练集中的k个近邻样本构成的集合，对于第j个类别Y j，(1≤j≤g)而言，ML—KNN 算法将计算如下统计量：
C j=Σ{y j∈Y*)．
(x*,y*)∈N(x)
可知,C j统计了N(x)中将作为其相关标记的样本个数．进一步地，设H j代表x具有类别标记Y j，这一事件，
P(H j|Y j)代表当N(x)中有C j个样本具有类别标记Y j时H j成立的后验概率．相应地，P(-H j|Y j)代表当N(x)中有C j个样本具有类别标记Y j时H j成立的后验概率.
令f(x,yj)= P(Hj|Yj)/ P(-Hj|Yj)
可得到所需的多标记分类器
h(x)={ y j| P(Hj|Yj)/ P(-Hj|Yj)>0.5,1 即当后验概率P(Hj|Yj)> P(-Hj|Yj)，将标记Y j赋予示例x.基于贝叶斯定理，函数可重写为h(x)={ y j| P(Hj) P(C j|Hj)/ P(-Hj ) P(C j|-Hj)>0.5,1 其中P(Hj)与P(-Hj)分别代表事件H j成立与不成立的先验概率，P(C j|Hj)与P(C j|-Hj)分别代表事件H j成立与不成立，N(x)中有C j个样本具有类别标记y j的条件概率．通过分析发现，ML—KNN是基于转换的PT(Problem Transformation)方法，将多标记分类转换为多个单标记分类，然后单独为每个分类进行考虑。然而多标记学习问题中大多数类别标记之间都是相关的，由此可见，忽略了多个标记之间的相关性，单纯使用与单标记分类相同的统计方式得到的结果是片面的．因此，本文在ML—KNN算法的基础上进行了改进，提出一种迭代的ML—KNN算法(Iterative ML —KNN，简称I-ML-KNN)，以提高多标记文本的分类效果． 5.2 2迭代的ML-KNN算法 在使用分类器函数h(x)时，P(Hj)与P(-Hj)分别代表事件H j成立与不成立的先验概率，这些先验概率在使用训练数据的训练模型时就可以确定．由于类别标记了yi与yj，可能相关，在对测试数据分类时，如果已经知道z是属于y i的话，那么x也很有可能属于y j或者不属于y j，对应测试用例．算法开始的时候设置类别标记集合V为空． 算法的具体步骤如下： 1)选取测试数据集的任一示例x． 2)初始化类别标记集合V为空． 3)循环开始． 4)如果V为空，使用分类器h(x)进行分类．如果示例x属于类标记y，则把y加入到V中． 5)如果V不为空，使用分类器hv(x)进行分类．如果示例x属于类标记y，则把y 加入到V中；如果x 不属于类标记y，且y在V中，则把y从V中移走． 6)如果集合V不变，循环结束，否则转至步骤4)． 7)得到集合V，即为示例x的一组类标记． 算法对ML—KNN的改进主要是在步骤5)，原算法总是用分类器函数h(x)对示例x进行分类，而h(x) 主要依赖于后验概率P(Hj|Cj)．改进的算法I—ML—KNN在多个分类即类标记集合非空时使用分类器函数 hv(x)对示例X进行分类，可以充分利用已经得到的类标记结果，提高分类的精度．6 个人思考和展望 在信息量激增的今天，文本分类在现实生活中占据了重要的地位，它已成功应用于多个领域中，并发挥出极大的作用。随着信息技术以及因特网的发展，对中文文本分类技术将会提出更多更高的新要求。 本文所做的工作主要有： 1．简介了KNN算法的核心思想 2．分析了K值得选取对算法的影响以及输入的次序对结果的影响。 3 举例分析了算法的复杂度 4 对比了KNN算法的优缺点 5 论述了如何实现多标签 由于KNN算法还有一些不足，我们需要针对不同的问题对KNN算法做一些改进。参考文献 [1]Piella G. A regiorr based multiresolution image fusion algorithm. In:ISIF Fusion 2002 Conference. [2]Kumar Han k. Text categorization using weight adjusted k-nearest neighbor classification［R］.Dept of CS,University of Minnesota,1999. [3]Wilson D R,Martinez TR. Improved heterogeneous distance functions [J]. Artificial Intelligence Research,1997,6:1-34. [4]PETER HALL, EONG U, PARK1 AND RICHARD J. SAMWORTH. CHOICE OF NEIGHBOR ORDER IN NEAREST-NEIGHBOR CLASSIFICATION. The Annals of Statistics 2008, 2135–2152. [5]Jia Pan, Dinesh Manocha. Bilevel Locality Sensitive Hashing for KNearest Neighbor Computation.2010. [6]Wen-Jyi Hwang , Kuo-Wei Wen . Fast kNN classification algorithm based on partial distance search Electronics Letters Volume: 34, Issue: 21On page(s): 2062-2063. [7]S Tan. An effective refinement strategy for KNN text classifier.Expert Systems with Applications［J］.2006,30(2):290-298. [8]Zhang minling,Zhou Zhihua.ML-KNN: a lazy learning approach to multi-bel learning[J].Pattern Recognition,2007,40(7):2038. [9]ZhangMinling. ML-RBF:RBF Neural Networks for Multi-label Learning[J].Neural Process 145 Letters,2009,29(2):61-74.