K邻近算法

K 近邻算法（K-Nearest Neighbors，KNN）既可以处理分类问题，也可以处理回归问题。

KNN 是一种懒惰学习算法。

• 懒惰学习算法：指直到出现新的测试样本，该算法才开始依据训练样本进行样本的预测处理工作。
  • 也就是说，该算法事先不会对训练样本进行任何处理，只会懒散地等待测试样本的到来，然后才开始工作。

懒惰学习算法构建的目标函数能够更近似测试样本数据本身，但同时它需要更大的存储空间用于存储训练样本数据。

• 懒惰学习算法非常适用于 具有较少特征属性 的 大型数据库 的问题。

KNN 算法原理

在训练集中，每个样本假设都是一个具有 $n$ 个特征属性的向量，即 $x=(x_1, x_2, x_3, ..., x_n)$ ，可看作每个样本在 $n$ 维特征空间内分布。每个样本还有一个标签 $y$。

目的是找到一个函数，使得 $y=f(x)$，以确定新样本 $u$ 的标签。

样本在 $n$ 维特征空间内分布，可以找到样本间的一种“距离”，用于评估样本间的相似程度。

• 欧氏距离：（适用于特征属性是连续变量）

$D_{Eu}(x, u)=\sqrt{\sum_{i=1}^n(x_i-u_i)^2}$

• 曼哈顿距离：（适用于特征属性是连续变量）

$D_{Man}(x, u)=\sum_{i=1}^n|x_i-u_i|$

• 闵可夫斯基距离：（适用于特征属性是连续变量）

$D_{Min}=\sqrt[q]{\sum_{i=1}^n|x_i-u_i|^q}$

• 汉明距离：（适用于特征属性是离散变量）

$D_{Ham}(x, u)=\sum_{i=1}^n|x_i-u_i|,\begin{cases}当x_i=u_i时，D_{Ham}(x, u)=0\\当x_i\neq u_i时，D_{Ham}(x, u)=1\end{cases}$

KNN 的任务是在训练集中，依据距离找到与新样本（测试样本） $u$ 最相似的那 $K$ 个训练样本。

• 若做分类问题，则多数表决，在 $K$ 个训练样本中，哪个分类的样本数多，哪个分类就是 $u$ 的预测分类。
• 若做回归问题，$u$ 的预测值 $v$ 为：

$v=\frac{\sum_{i=1}^Ky_i}{K}$

在考虑训练集与测试样本之间距离大小的影响下，使得距离更小的样本具有更大的权值，$K$ 个最邻近样本中第 $i$ 个样本 $x^i$ 与测试样本 $u$ 的权值定义为：

$w(x^i, u)=\frac{\exp{(-D(x^i, u))}}{\sum_{i=1}^n\exp{(-D(x^i, u))}}$

• 对于回归问题，预测结果 $v$ 变成：

$v=\sum_{i=1}^Kw(x^i, u)y_i$

• 对于分类问题，最终分类结果为权值最大的类。

KNN 的 $K$ 需要预先确定：

• 若值过大，会使特征空间内明确分类边界变得模糊；
• 若值过小，则引入误差。

常用 交叉验证法 选择 $K$ 值。

• 把训练数据 $D$ 分为 $K$ 份，用其中的 $(K-1)$ 份训练模型，把剩余的1份数据用于评估模型的质量。

基于OpenCV实现KNN

OpenCV 并没有采用交叉验证和距离权值的方法。

相关函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 创建模型
cv::Ptr<cv::ml::KNearest> model=cv::ml::KNearest::create();

// 设置默认 K 值
model->setDefaultK(k);

// 是否分类
model->setIsClassifier(true);

// 设置算法类型
model->setAlgorithmType(cv::ml::KNearest::BRUTE_FORCE);

// 训练，实际上是初始化训练样本数据
model->train(trainDataPtr);

// 找到最近邻
model->findNearest(testMat, k, result);

例子-小麦品种籽粒数据集

数据集地址：https://archive.ics.uci.edu/dataset/236/seeds

三种不同小麦品种籽粒几何特性的测定。数据集具有7个属性：

1. 一个区域
2. 周边P
3. 紧性 $C=4\times\pi\times A / P^2$
4. 核的长度
5. 核的宽度
6. 不对称系数
7. 核槽长度

部分数据如下：

使用自实现 KNN 和 OpenCV 提供的 KNN 类进行训练计算，结果如下：

1
2
3
4
5
6
7
8
9
10
11

Train Data imported: 150
Test Data imported: 60
K近邻算法：
正确率：0.933333
计算花费时长：1ms

Train Data imported: 150
Test Data imported: 60
K近邻算法(基于OpenCV实现)：
正确率：0.95
计算花费时长：50ms

代码及数据集地址：KNN - Gitee