K邻近（k-Nearest Neighbor，KNN）分类算法是最简单的机器学习算法了。它采用测量不同特征值之间的距离方法进行分类。它的思想很简单：计算一个点A与其他所有点之间的距离，取出与该点最近的k个点，然后统计这k个点里面所属分类比例最大的，则点A属于该分类。

---

K近邻的理论基础

一、什么是分类

分类是指通过对大量的训练样本进行提取和分析，训练出用来分类的规则，即分类器或者分类模型，最终判断未知样本的类别。常见的分类算法有：决策树（ID3和C4.5），朴素贝叶斯，人工神经网络 （Artificial Neural Networks，ANN），k-近邻(kNN)，支持向量机（SVM），基于关联规则的分类，Adaboosting方法等等。这篇文章主要介绍KNN算法。

二、KNN算法原理

1 原理

KNN算法又称为K近邻算法，根据训练样本和样本类别，计算与待分类样本相似度最大的K个训练点，然后对这K个训练点进行投票并排序，选择投票数最高的样本类别作为待分类数据的类别。这里的相似性度量可采用欧氏距离、马氏距离，余弦相似度等等。K为人为设定，一般选择奇数。

2 算法优点

1）、算法简单、有效，通常用于文本分类。 

2）、重新训练的代价较低（类别体系的变化和训练集的变化，在Web环境和电子商务应用中是很常见的）。 

3）、该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

3 算法缺点

1）、K值得选择对算法精度影响较大。 

2）、依赖于相似性度量的优劣。 

3）、当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个 邻居中大容量类的样本占多数。 

4）、计算量较大。

---

K近邻的模型基础

用空间内两个点的距离来度量。距离越大，表示两个点越不相似。距离的选择有很多[13]，通常用比较简单的欧式距离。

欧式距离：

马氏距离：马氏距离能够缓解由于属性的线性组合带来的距离失真，是数据的协方差矩阵。

曼哈顿距离：

切比雪夫距离：

闵氏距离：r取值为2时：曼哈顿距离；r取值为1时：欧式距离。

平均距离：

弦距离：

测地距离：

模型图：

目标点临近分类点

---

K近邻的Java基础(以欧式距离为例)

1. 先定义一个KNN类，用于存放每个数据节点

类具有距离属性

2. 初始化加载数据集的方法（伴随数据集合的加载，中途获取不同类别数据的总个数）

数据加载，构建类集合

3. 写核心算法，目的是计算计算点与点之间的【欧式距离】

计算欧式距离

4.  排序，将数据节点按照临近距离从小到大排列

排序

5.  打印计算结果

具体输出方法 得到分类结果

总结：KNN是机器学习算法中最简单的一种算法，思想和实现比较容易。没有像梯度下降一样需要引入和实现导函数的概念；也没有像SVM一样需要先训练数据再分类执行。那KNN到底可以用在什么方面呢？

文本分类（文字识别），回归，产品推荐等。欢迎大家一起学习，讨论~！