# 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