文档介绍：KNN算法总结
1KNN分类算法
K最近邻(k-NearestNeighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学****算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征方法是将不同距离的邻居对该样本产生的影响给予不同的权值（weight），如权值与距离成正比（组合函数）。
（1）文本分类：文本分类主要应用于信息检索，机器翻译，自动文摘，信息过滤，邮件分类等任务。文本分类在搜索引擎中也有着大量的使用，网页分类/分层技术是检索系统的一项关键技术，搜索引擎需要研究如何对网页进行分类、分层，对不同类别的网页采用差异化的存储和处理，以保证在有限的硬件资源下，提供给用户一个高效的检索系统，同时提供给用户相关、丰富的检索结果。在搜索引擎中，文本分类主要有这些用途：相关性排序会根据不同的网页类型做相应的排序规则；根据网页是索引页面还是信息页面，下载调度时会做不同的调度策略；在做页面信息抽取时，会根据页面分类的结果做不同的抽取策略；在做检索意图识别的时候，会根据用户所点击的
url所属的类别来推断检索串的类别。
（2）回归：通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值（weight），如权值与距离成正比。
（3）可以使用knn算法做到比较通用的现有用户产品推荐，基于用户的最近邻（长得最像的用户）买了什么产品来推荐是种介于电子商务网站和sns网站之间的精确营销。只需要定期（例如每月）维护更新最近邻表就可以，基于最近邻表做搜索推荐可以很实时［4］。
K-NN可以说是一种最直接的用来分类未知数据的方法。-NN的思想是什么
简单来说，K-NN可以看成：有那么一堆你已经知道分类的数据，然后当一个新数据进入的时候，就开始跟训练数据里的每个点求距离，然后挑离这个训练数据最近的K个点看看这几个点属于什么类型，然后用少数服从多数的原则，给新数据归类。
kNN算法的核心思想是如果一个样本在特征空间中的k个最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别［5］。kNN方法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。
------计算未知样本和每个训练样本的距离dist
---得到目前K个最临近样本中的最大距离maxdist
---如果dist小于maxdist,则将该训练样本作为K-最近邻样本
---重复步骤2、3、4，直到未知样本和所有训练样本的距离都算完
---统计K-最近邻样本中每个类标号出现的次数
---选择出现频率最大的类标号作为未知样本的类标号
2K值的选择
2・1交叉验证(Cross-validation)
交叉验证(Cross-validation)主要用于建模应用中，例如PCR、PLS回归建模中。在给定的建模样本中，拿出大部分样本进行建模型，留小部分样本用刚建立的模型进行预报，并求这小部分样本的预报误差，记录它们的平方加和。这个过程一直进行，直到所有的样本都被预报了一次而且仅被预报一次。把每个样本的预报误差平方加和，称为PRESS(predictedErrorSumofSquares)。
K折交叉验证，初始采样分割成K个子样本，一个单独的子样本被保留作为验证模型的数据，其他K-1个样本用来训练。交叉验证重复K次，每个子样本验证一次，平均K次的结果或者使用其它结合方式，最终得到一个单一估测。这个方法的优势在于，同时重复运用随机产生的子样本进行训练和验证，每次的结果验证一次，10折交叉验证是最常用的。
K近邻规则可以被看作是另一种从样本中估计后验概率P(wi|x)的方法。为了得到可高的估计必须是的K值越大越好。另一方面,又希望又希望x的K个近邻x距离X1越近越好，因为这样才能保证P(w」X1)尽可能逼近P(wjx)。在选取K值的时候，就不得不做出某种折衷。只有当n趋近于无穷大时，才能保证K近邻规则几乎是最优的分类规则。
K值的选择：需要消除K值过低，预测目标容易产生变动性，同时高k值时，预测目标有过平滑现象。推定k值的有益途径是通过有效