KNN算法总结

KNN算法总结1KNN分类算法1.1KNN简述K最近邻(k-NearestNeighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别[1]。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。KNN最邻近规则，主要应用领域是对未知事物的识别，即判断未知事物属于哪一类，判断思想是，基于欧几里得定理，判断未知事物的特征和哪一类已知事物的的特征最接近。1.2KNN原理最近邻方法(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概率也越大[2]。K近邻法是有监督学习方法，原理很简单，假设我们有一堆分好类的样本数据，分好类表示每个样本都一个对应的已知类标签，当来一个测试样本要我们判断它的类别是，就分别计算到每个样本的距离，然后选取离测试样本最近的前K个样本的标签累计投票，得票数最多的那个标签就为测试样本的标签。下面我们用电影的分类来简述KNN的原理例子（电影分类）：图1.1电影分类图1.1中横坐标表示一部电影中的打斗统计个数，纵坐标表示接吻次数。我们要对图中的问号这部电影进行分类，其他几部电影的统计数据和类别如表1.1所示：表1.1Movietitle#ofkicks#ofkissesTypeofmovieCaliforniaMan3104RomanceHe’sNotReallyintoDudes2100RomanceBeautifulWoman181RomanceKevinLongblade10110ActionRoboSlayer3000995ActionAmpedII982Action？1890Unknown从表1.1中可以看出有三部电影的类别是Romance,有三部电影的类别是Action,那如何判断问号表示的这部电影的类别？根据KNN原理,我们需要在图1.1所示的坐标系中计算问号到所有其他电影之间的距离。计算出的欧式距离如表1.2所示：表1.2MovietitleDistancetomovie“?”CaliforniaMan20.5He’sNotReallyintoDudes18.7BeautifulWoman19.2KevinLongblade115.3RoboSlayer3000117.4AmpedII118.9由于我们的标签只有两类，那假设我们选K=6/2=3,由于前三个距离最近的电影都是Romance,那么问号表示的电影被判定为Romance。1.3KNN的应用KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性[3]。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比（组合函数）。（1）文本分类：文本分类主要应用于信息检索，机器翻译，自动文摘，信息过滤，邮件分类等任务。文本分类在搜索引擎中也有着大量的使用，网页分类/分层技术是检索系统的一项关键技术，搜索引擎需要研究如何对网页进行分类、分层，对不同类别的网页采用差异化的存储和处理，以保证在有限的硬件资源下，提供给用户一个高效的检索系统，同时提供给用户相关、丰富的检索结果。在搜索引擎中，文本分类主要有这些用途：相关性排序会根据不同的网页类型做相应的排序规则；根据网页是索引页面还是信息页面，下载调度时会做不同的调度策略；在做页面信息抽取时，会根据页面分类的结果做不同的抽取策略；在做检索意图识别的时候，会根据用户所点击的url所属的类别来推断检索串的类别。（2）回归：通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。（3）可以使用knn算法做到比较通用的现有用户产品推荐，基于用户的最近邻(长得最像的用户)买了什么产品来推荐是种介于电子商务网站和sns网站之间的精确营销。只需要定期(例如每月)维护更新最近邻表就可以，基于最近邻表做搜索推荐可以很实时[4]。1.4KNN的核心思想K-NN可以说是一种最直接的用来分类未知数据的方法。基本通过下面这张图1.2跟文字说明就可以明白K-NN的思想是什么图1.2简单来说，K-NN可以看成：有那么一堆你已经知道分类的数据，然后当一个新数据进入的时候，就开始跟训练数据里的每个点求距离，然后挑离这个训练数据最近的K个点看看这几个点属于什么类型，然后用少数服从多数的原则，给新数据归类。kNN算法的核心思想是如果一个样本在特征空间中的k个最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别[5]。kNN方法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。1.5算法步骤step.1---初始化距离为最大值step.2---计算未知样本和每个训练样本的距离diststep.3---得到目前K个最临近样本中的最大距离maxdiststep.4---如果dist小于maxdist，则将该训练样本作为K-最近邻样本step.5---重复步骤2、3、4，直到未知样本和所有训练样本的距离都算完step.6---统计K-最近邻样本中每个类标号出现的次数step.7---选择出现频率最大的类标号作为未知样本的类标号2K值的选择2.1交叉验证(Cross-validation)交叉验证(Cross-validation)主要用于建模应用中，例如PCR、PLS回归建模中。在给定的建模样本中，拿出大部分样本进行建模型，留小部分样本用刚建立的模型进行预报，并求这小部分样本的预报误差，记录它们的平方加和。这个过程一直进行，直到所有的样本都被预报了一次而且仅被预报一次。把每个样本的预报误差平方加和，称为PRESS(predictedErrorSumofSquares)。K折交叉验证，初始采样分割成K个子样本，一个单独的子样本被保留作为验证模型的数据，其他K-1个样本用来训练。交叉验证重复K次，每个子样本验证一次，平均K次的结果或者使用其它结合方式，最终得到一个单一估测。这个方法的优势在于，同时重复运用随机产生的子样本进行训练和验证，每次的结果验证一次，10折交叉验证是最常用的。2.2K值的选择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值。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数据（UCIMachineLearningRepository下载）用kNN算法进行分类，通过交叉验证（10次）的方式，对k取不同值时进行了实验，实验结果如图2.2所示，其中红线指的是实验选用的Ｋ值，黄线指的是实验的结果，我们发现在我所选取的k值中，当k=17时效果最好，在k=1时，即用最近邻来进行分类的效果也不错，实验结果呈现一个抛物线，与我们之前分析的结果相吻合。图2.23KNN算法的优缺点K近邻法(KNearestNeighbor，KNN)由Cover和Hart提出来的，是一种懒惰的、有监督的、基于实例的机器学习方法。相关研究证明该分类方法是向量空间模型下最好的分类算法之一。KNN的分类过程可以理解成：先将训练文本集中的所有文本表示成向量的形式，形成向量文本集并存储起来，当一个新的待分类文本到达时，计算该文本和训练文本集中每一个文本的相似度，并将计算得到的值按降序排列，选取出排在最前面的K篇文本，然后依照这K篇文本的类别对新文本进行归类。在依据这K篇文本确定待分类文本的类别时，通常有两种方法：，1．对选出的这K篇文本进行统计，看大多数属于哪一类，就把这个待分类文本归到这个类中。2．对这K篇文本与待分文本的相似度按公式(3-1)进行求和，将属于同一个类的文本的相似度相加求和，然后对每个类所求得的和进行排序，将待