人工智能之K近邻算法（KNN）
AI优化生活人工智能机器学习有关算法内容，请参见公众号“科技优化生活”之前相关文章。人工智能之机器学习主要有三大类：1）分类；2）回归；3）聚类。今天我们重点探讨一下K近邻（KNN）算法。
K近邻KNN（k－Nearest Neighbor）算法，也叫K最近邻算法，1968年由 Cover 和 Hart 提出，是机器学习算法中比较成熟的算法之一。K近邻算法使用的模型实际上对应于对特征空间的划分。KNN算法不仅可以用于分类，还可以用于回归。
KNN概念：
K近邻算法KNN就是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（K个邻居），这K个实例的多数属于某个类，就把该输入实例分类到这个类中。
如果一个样本在特征空间中的k个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。K近邻算法使用的模型实际上对应于对特征空间的划分。
通俗地讲，就是“物以类聚，人以群分”。
分类策略，就是“少数从属于多数”。
算法描述：
KNN没有显示的训练过程，在测试时，计算测试样本和所有训练样本的距离，根据最近的K个训练样本的类别，通过多数投票的方式进行预测。具体算法描述如下：
输入：训练数据集T＝｛（x1，y1），（x2，y2），．．．，（xn，yn）｝，其中xi∈Rn，yi∈｛c1，c2，．．．，cK｝和测试数据x
输出：实例x所属的类别
1） 根据给定的距离度量，在训练集T中找到与x距离最近的k个样本，涵盖这k个点的x的邻域记作Nk（x）。
2）在Nk（x）中根据分类规则（如多数表决）确定x的类别y：
核心思想：
当无法判定当前待分类点是从属于已知分类中的哪一类时，依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为到权重更大的那一类中。
kNN的输入是测试数据和训练样本数据集，输出是测试样本的类别。
KNN算法中，所选择的邻居都是已经正确分类的对象。KNN算法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
算法要素：
KNN 算法有3个基本要素：
1）K值的选择：K值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合；如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，使预测发生错误。在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的 K 值。随着训练实例数目趋向于无穷和 K＝1 时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。
2）距离度量：距离度量一般采用 Lp 距离，当p＝2时，即为欧氏距离，在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。
对于文本分类来说，使用余弦（cosine）来计算相似度就比欧式（Euclidean）距离更合适。
3）分类决策规则：该算法中的分类决策规则往往是多数表决，即由输入实例的K个最临近的训练实例中的多数类决定输入实例的类别。
算法流程：
1）准备数据，对数据进行预处理。
2）选用合适的数据结构存储训练数据和测试元组。
3）设定参数，如K。
4）维护一个距离由大到小的优先级队列（长度为K），用于存储最近邻训练元组。随机从训练元组中选取K个元组作为初始的最近邻元组，分别计算测试元组到这K个元组的距离，将训练元组标号和距离存入优先级队列。
5）遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离L与优先级队列中的最大距离Lmax。
6）进行比较。若L＞＝Lmax，则舍弃该元组，遍历下一个元组。若L＜Lmax，删除优先级队列中最大距离的元组，将当前训练元组存入优先级队列。
7）遍历完毕，计算优先级队列中K个元组的多数类，并将其作为测试元组的类别。
8）测试元组集测试完毕后计算误差率，继续设定不同的K值重新进行训练，最后取误差率最小的K值。
算法优点：
1）KNN从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。
2）由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
3）算法本身简单有效，精度高，对异常值不敏感，易于实现，无需估计参数，分类器不需要使用训练集进行训练，训练时间复杂度为0。
4）KNN 分类的计算复杂度和训练集中的文档数目成正比，即，如果训练集中文档总数为n，那么KNN的分类时间复杂度为O（n）。
5）适合对稀有事件进行分类。
6）特别适合于多分类问题（multi－modal），对象具有多个类别标签，kNN比SVM的表现要好。
算法缺点：
1）当样本不平衡时，样本数量并不能影响运行结果。
2）算法计算量较大；
3）可理解性差，无法给出像决策树那样的规则。
改进策略：
KNN算法因其提出时间较早，随着其他技术的不断更新和完善，KNN算法逐渐显示出诸多不足之处，因此许多KNN算法的改进算法也应运而生。算法改进目标主要朝着分类效率和分类效果两个方向。
改进1：通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。
改进2：将不同距离的邻居对该样本产生的影响给予不同的权值（weight），如权值与距离成反比（1／d），即和该样本距离小的邻居权值大，称为可调整权重的K最近邻居法WAKNN（weighted adjusted K nearestneighbor）。但WAKNN会造成计算量增大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。
改进3：事先对已知样本点进行剪辑（editing技术），事先去除（condensing技术）对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
考虑因素：
实现 K 近邻算法时，主要考虑的因素是如何对训练数据进行快速 K 近邻搜索，这在特征空间维数大及训练数据容量大时是非常必要的。
应用场景：
K 近邻算法应用场景包括机器学习、字符识别、文本分类、图像识别等领域。
结语：
K近邻算法KNN，也叫K最近邻算法，是机器学习研究的一个活跃领域。最简单的暴力算法，比较适合小数据样本。K近邻算法使用的模型实际上对应于对特征空间的划分。KNN算法不仅可以用于分类，还可以用于回归。KNN算法在人工智能之机器学习、字符识别、文本分类、图像识别等领域有着广泛应用。
原创 张志荣
