# K最近邻算法
## 概述
K最近邻算法适用于找出距离A坐标最近的几个点，可以用来做推荐系统
## 计算公式以及模拟
K最近邻算法有两个公式：距离公式，相似度公式（余弦）
### 距离公式
距离公式是：
$$
\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}
$$
举个栗子：
你要做电影推荐系统，他有以下参数：
```
(a, b, c, d)
科幻片 动作片 爱情片 喜剧片
```
四个值是历史评分的总和
> 小明的打分是`(10, 5, 9, 4)`, 小红的打分是`(9, 1, 2, 5)`, 小张的打分是`(10, 3, 4, 5)`, 假设目前就这几个用户，小红几个小时前看了《独行月球》，小张几个小时前看了《流浪地球》，应该给小明推荐哪一部电影？
这里计算的是**四维空间**的距离，但是只要扩展一下就行
$$
\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2 + (z_1-z_2)^2 + (t_1-t_2)^2}
$$
代入公式，小明与小红在电影评分上的距离为：
$$
\sqrt{(10-9)^2 + (5-1)^2 + (9-2)^2 + (4-5)^2} = \sqrt{67}
$$
非常简单！小明与小红的距离为$\sqrt{67}$
小明与小张在电影评分上的距离为：
$$
\sqrt{(10-10)^2 + (5-3)^2 + (9-4)^2 + (4-5)^2} = \sqrt{30}
$$
由此可见，小明的电影偏好与小张比较相似，所以应该给小明推荐《流浪地球》
### 余弦相似度公式
余弦相似度的公式是
$$cos(\theta) = \frac{x_1x_2+y_1y_2}{\sqrt{x_1^2+y_1^2} \times {\sqrt{x_2^2+y_2^2}}}$$
别急，这是纸老虎，给你举个栗子就懂了
同样是电影推荐系统的栗子，当然，为了减少计算量，我们只设二维空间的坐标值
```
(x, y)
科幻片 喜剧片
```
> 小明的电影偏好为`(10, 4)`, 小红的为`(9, 5)`, 小张的为`(10, 5)`，小红几个小时前看了《独行月球》，小明几个小时前看了《流浪地球》，请问？按照余弦相似度，该给小明推荐哪一部电影
代入公式，小明与小红的相似度为：
$$\frac{10 \times 9 + 4 \times 5}{\sqrt{10 ^ 2 + 4 ^ 2} \times {\sqrt{9^2+5^2}}} \approx 0.9919979 $$
> 余弦相似度的逻辑是：越接近1，越相似
小明与小张的相似度为：
$$\frac{10 \times 10 + 4 \times 5}{\sqrt{10 ^ 2 + 4 ^ 2} \times {\sqrt{10 ^ 2 + 5 ^ 2}}} \approx 0.996545$$
因为小明与小张的相似度更接近1,所以应该给小明推荐《流浪地球》
## Python代码
### 距离公式的代码解析
由于要使用到根号，所以需要导入`math.sqrt`
```python
from math import sqrt
```
还要设置坐标
```python
A_vector = (2, 3) # 实例所需
B_vector = (5, 9)
```
最后就是计算了
```python
result = sqrt((A_vector[0]-B_vector[0]) ^ 2 + (A_vector[1]-B_vector[1]) ^ 2)
print('坐标{}与坐标{}的距离是{}'.format(A_vector, B_vector, result))
```
完整代码：
```python
from math import sqrt
A_vector = (2, 3) # 实例所需
B_vector = (5, 9)
result = sqrt((A_vector[0]-B_vector[0]) ^ 2 + (A_vector[1]-B_vector[1]) ^ 2)
print('坐标{}与坐标{}的距离是{}'.format(A_vector, B_vector, result))
```
输出：
```
坐标(2, 3)与坐标(5, 9)的距离是1.7320508075688772
```
### 余弦相似度的代码解析
导入以及坐标设置就不说了，直接说计算过程
余弦相似度的计算是一个分数，先看分子的计算
```python
(a_Vector[0] * b_Vector[0] + a_Vector[1] * b_Vector[1])
```
等同于以下数学公式
$$
x_1x_2+y_1y_2
$$
再看分母的计算
```python
# from math import sqrt
(sqrt(a_Vector[0] ** 2 +a_Vector[1] **2) * sqrt(b_Vector[0] ** 2 +b_Vector[1] ** 2)) # ** 等同于 ^
```
相当于以下数学公式
${\sqrt{x_1^2+y_1^2} \times {\sqrt{x_2^2+y_2^2}}}$
这下明白了吧，直接亮出完整代码
```python
from math import sqrt
a_Vector = (2, 3)
b_Vector = (5, 9)
result = (a_Vector[0] * b_Vector[0] + a_Vector[1] * b_Vector[1]) / (sqrt(a_Vector[0] ** 2 +a_Vector[1] **2) * sqrt(b_Vector[0] ** 2 +b_Vector[1] ** 2))
print("∠ θ = {}".format(result))
```
关于K最近邻算法的介绍就到这，如果在实际工作中使用此算法，建议使用`余弦相似度`公式计算，K最近邻算法的应用场景还很多，你可以用它来预测上下班高峰的的人数，预测成绩，做推荐系统……希望这篇博客对你有帮助！
标签：小明,Vector,10,sqrt,times,算法,vector,最近 From： https://www.cnblogs.com/heikeling/p/16705497.html