KNN算法介绍
interesting_soul_zjy
·
·
算法·理论
KNN算法介绍
简介
KNN（k-Nearest Neighbor，k 最邻近算法）分类算法，是最简单的机器学习算法之一。这可不是什么租房找邻居的算法，而是判断一种数据属于哪个类别的算法。
算法思路
该方法的思路是：在特征空间中，如果一个样本附近的 k 个最近（即特征空间中最邻近）样本的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。
算法流程
KNN 算法包括以下 4 个步骤：
- 准备数据，对数据进行预处理。
- 计算未知样本到其他每个样本的距离。
- 对距离进行排序，然后选择出距离最小的 k 个点。
- 对 k 个点所属的类别进行比较，将测试样本点归入 k 个点中占比高的那一类。
用法举例
机器在识别一样物品的时候，不会像人类一样，“觉得”这个物品“像”什么，它需要通过数据的计算和比较来识别。
我们要选择合适的比较对象，比如识别动物是狮子还是大象，我们就要比较它们的身长、身高、颜色等，而不是比较它们眼睛、腿的数量。
让我们就用识别数字是 1 还是 7 来举个例子。
计算像素数
1 和 7 的区别就在于 7 的上半部分占的像素会多一些，所以我们首先可以画一个 10 \times 10 的格子，并写出几个不同的 1 和 7 样本，并计算它们上半部分和下半部分占的像素数。
样本举例：
1：上半部分 7 个像素，下半部分 6 个像素。
7：上半部分 10 个像素，下半部分 5 个像素。
绘制坐标系
接着，我们可以把这些样本绘制在坐标系上,再绘制出一个需要分类的数据。x 轴表示上半部分像素数，y 轴表示下半部分像素数。
蓝点：1。
红点：7。
绿点：未知数据。
计算距离
最后，我们运算未知数据到每一个点的距离。我们一般使用直线距离。
$$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$
|样本|坐标|距离|
|:-:|:-:|:-:|
|蓝 $1$|$(6,5)$|$1.00$|
|蓝 $2$|$(7,6)$|$1.00$|
|蓝 $3$|$(7,7)$|$1.41$|
|红 $1$|$(9,4)$|$3.61$|
|红 $2$|$(9,5)$|$3.16$|
|红 $3$|$(10,5)$|$4.12$|
排序后就是：
|样本|坐标|距离|
|:-:|:-:|:-:|
|蓝 $2$|$(7,6)$|$1.00$|
|蓝 $3$|$(6,5)$|$1.00$|
|蓝 $1$|$(7,7)$|$1.41$|
|红 $2$|$(9,5)$|$3.16$|
|红 $3$|$(9,4)$|$3.61$|
|红 $1$|$(10,5)$|$4.12$|
### 分类并得出结论
我们需要选取前 $k$ 个邻居（$k$ 为奇数）来分类。
|$k$ 的值|蓝点数|红点数|
|:-:|:-:|:-:|
|$1$|$1$|$0$|
|$3$|$3$|$0$|
|$5$|$3$|$2$|
所以我们得出结论：未知数据是 `1`。
## 简单编程实现
```
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
struct Point // 一个样本点
{
char C; // 分类
int X; // X坐标
int Y; // Y坐标
double Dis; // 距离
};
double dis(int disx1, int disy1, int disx2, int disy2) // 算直线距离
{
return sqrt((disx1 - disx2) * (disx1 - disx2) + (disy1 - disy2) * (disy1 - disy2));
}
bool cmp(Point A, Point B) // 排序
{
return A.Dis < B.Dis;
}
Point P[200000];
int main()
{
int n; // 一种类别的样本数
int k; // 最近邻居数（默认为奇数）
int x, y; // 未知数据坐标
int a, b; //最小的 k 个样本中不同类别的数量
cin >> n >> k;
for (int i = 0; i < n; ++i) // 输入
{
P[i].C = 'A';
cin >> P[i].X >> P[i].Y;
}
for (int i = 0; i < n; ++i)
{
P[i].C = 'B';
cin >> P[i].X >> P[i].Y;
}
cin >> x >> y;
for (int i = 0; i < 2 * n; ++i) // 算距离
{
P[i].Dis = dis(P[i].X, P[i].Y, x, y);
}
sort(P, P + n, cmp); // 排序
for (int i = 0; i < k; ++i) // 分类
{
if (P[i].C == 'A')
{
a += 1;
}
else
{
b += 1;
}
}
if (a > b) // 输出
{
cout << 'A';
}
else
{
cout << 'B';
}
return 0;
}
```
## 优点和缺点
### 优点
- 思路简单。
- 容易实现。
- 无需训练。
### 缺点
- 计算量大。
- 计算复杂度高。
- 内存要求高。
###### 1.10：图床使用有误，图片被删除无法显示。修改格式和更新图片后重新提交申请。
## 猜你想看
[我的专栏](https://www.luogu.com.cn/user/1378097#article)