2.1 KNN算法

KNN（K-Nearest Neighbor）算法又称K近邻算法，是最简单的机器学习分类算法之一。所谓K近邻，是指K个最近的邻居，即每个样本都可以用与它最近的K个邻居来代表。KNN算法是基于实例的学习（Instance-based Learning），属于非参数模型，它学习的不是明确的泛化模型，而是样本之间的关系。当新样本到来时，这种学习方式不会用拟合好的算式去计算输出结果或输出结果的概率，而是根据这个新样本和训练样本之间的关系来确定它的输出[2-7]。

KNN算法的应用领域包括文本处理、模式识别、计算机视觉、通信工程、生物工程等。

2.1.1 算法原理

下面以一个实例来说明KNN算法原理。假定有8位同学，其身高与性别如表2-1所示。

现在有一个身高为183cm的同学，不知道他（她）的性别。根据“少数服从多数”的原则，可猜测这位同学的性别最大的可能是男。如果用KNN算法思想还原“少数服从多数”的原则，可按以下步骤：

（1）求这位同学与其他同学的身高差。

（2）设定一个K值，选择与这位同学身高相差最小的K个同学。

（3）在这K个同学中，哪种性别的人多，就认为这位同学属于哪种性别。

设K为5，计算这位同学与其他同学的身高差的绝对值，如表2-2所示。

与这位同学身高差最接近的5位同学中，有4位男生，1位女生，所以，认为这位同学也是男生。

现实中，肯定不仅考虑身高，还要考虑体重、头发长度等因素。算法的思想还是一样的，这时“距离”为欧氏距离。

一般，对于给定的样本集Z={（x0，y0），（x1，y1），…，（xm，ym）}，其中，xi∈Rn为实例样本的特例向量，yi∈{c0，c1，…，cn}为实例的标签或类别，那么，如何判断一个新样本的类别？依照判别一个人性别的思想方法，KNN算法原理是在特征空间中查找K个最相似或者距离最近的样本，然后根据K个最相似的样本对未知样本进行分类。

2.1.2 算法步骤

构建KNN算法主要分为4步：算距离、排序、取近邻和做决策。

（1）算距离：计算新样本与已知样本空间中所有样本点的距离。常用的距离有欧式距离和夹角余弦距离。

（2）排序：对所有距离按升序排列。

（3）取近邻：确定并选取与未知样本距离最小的K个样本或点。选定合适的K值，对分类的效果尤为重要。

（4）做决策：得到K近邻列表，采用多数表决的方法对样本进行分类。

2.1.3 算法描述

算法2-1是对KNN算法的描述。首先计算新样本与所有样本点（xi，yi）∈Z之间的距离，得到近邻列表DZ，然后根据列表的分类以多数判决的规则决定新样本的分类。

其中，c为类别标签，I（c=yji）为指示函数，如果参数为真，则值为1；如果参数为假，则值为0。

2.1.4 算法评价

KNN算法不仅可以用于分类，还可以用于回归。它具有以下4个优点：①模型简单，容易理解，易于实现，并且无须估计参数，也无须训练；②特别适合对离散类型的事件进行分类；③适合多分类问题（对象具有多个类别标签），比SVM的表现要好；④精度高、对异常值不敏感、无数据输入假定。

由于KNN算法实现相对简单，难以处理复杂的情况，在实际应用中也存在一定的缺陷，包括以下几方面。①当样本不平衡，如一个类的样本容量很大，而其他类的样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，若某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。②计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。③可解释性差，无法给出像决策树那样的规则。

2.1.5 算法实例

假设有一个女生要找一个男朋友，她收集了某网站上的一些男士的以下数据：①每天的运动时间；②每天玩游戏的时间；③每天的学习时间；④类别。在输出结果中，3表示优先见面，2表示再考察，1表示没兴趣。具体程序如下。

为了防止某个属性对结果产生很大的影响，如当3种属性取值分别为10000、4.5、6.8时，10000就对结果起了决定性作用，做如下优化。