机器学习算法 —— 1. K近邻算法

1. K近邻算法简介

K近邻算法的分类问题

2. K近邻算法常见距离度量

► 在机器学习中，函数$dist(x_i,x_j)$表示点 $i$ 和点 $j$ 之间的距离需要满足：
   ⮚ 非负性：$dist(x_i,x_j)\ge 0$；
   ⮚ 同一性：$dist(x_i,x_j)=0,当且仅当X_i=X_j$；
   ⮚ 对称性：$dist(x_i,x_j)=dist(x_j,x_i)$；
   ⮚ 直递性：$dist(x_i,x_j)\le dist(x_i,x_k)+dist(x_k,x_j)$；

2.1 欧氏距离（Euclidean Distance）

• 数学公式

二维平面的点 $a(x_1,y_1)$ 与点 $b(x_2,y_2)$ 间的欧式距离
$$d_{(a,b)}=\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$$
三维平面的点 $a(x_1,y_1,z_1)$ 与点 $b(x_2,y_2,z_2)$ 间的欧式距离
$$d_{(a,b)}=\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2+(z_1-z_2{)}^2}$$
n维空间点$a(x_{11},x_{12},\dots ,x_{1n})$与$b(x_{21},x_{22},\dots ,x_{2n})$间的欧氏距离（两个n维向量）
$$d_{(a,b)}=\sqrt{\sum _{k=1}^n(x_{1k}-x_{2k}{)}^2}$$

• Python代码

import numpy as np
# 欧氏距离
def EuclideanDistance(x, y):
    x = np.array(x)
    y = np.array(y)
    return np.sqrt(np.sum(np.square(x-y)))
1
2
3
4
5
6

2.2 曼哈顿距离（Manhattan Distance ）

• 数学公式

二维平面两点 $a(x_1,y_1)$ 与点 $b(x_2,y_2)$ 间的曼哈顿距离
$$d_{(a,b)}=|x_1-x_2|+|y_1-y_2|$$
n维空间点$a(x_{11},x_{12},\dots ,x_{1n})$与$b(x_{21},x_{22},\dots ,x_{2n})$间的曼哈顿距离
$$d_{(a,b)}=\sum _{k=1}^n|x_{1k}-x_{2k}|$$

• Python代码

import numpy as np
# 曼哈顿距离
def ManhattanDistance(x, y):
    x = np.array(x)
    y = np.array(y)
    return np.sum(np.abs(x-y))
1
2
3
4
5
6

2.3 切比雪夫距离（Chebyshev Distance）

• 数学公式

二维平面两点 $a(x_1,y_1)$ 与点 $b(x_2,y_2)$ 间的切比雪夫距离
$$d_{(a,b)}=max(|x_1-x_2|,|y_1-y_2|)$$
n维空间点$a(x_{11},x_{12},\dots ,x_{1n})$与$b(x_{21},x_{22},\dots ,x_{2n})$间的切比雪夫距离
$$d_{(a,b)}=max(|x_{1k}-x_{2k}|)$$

• Python代码

import numpy as np
# 切比雪夫距离
def ChebyshevDistance(x, y):
    x = np.array(x)
    y = np.array(y)
    return np.max(np.abs(x-y))
1
2
3
4
5
6

2.4 闵可夫斯基距离（Minkowski Distance）

• 数学公式

n维空间点$a(x_{11},x_{12},\dots ,x_{1n})$与$b(x_{21},x_{22},\dots ,x_{2n})$间的闵可夫斯基距离
$$d_{(a,b)}=\sqrt[p]{\sum _{k=1}^n|x_{1k}-x_{2k}{|}^p}$$
其中，p为一个变参数：当 p=1 时，表示曼哈顿距离
           当 p=2 时，表示欧氏距离
           当 p—> $\infty$ 时，表示切比雪夫距离

• Python代码

import math
import numpy as np
# 闵可夫斯基距离
def MinkowskiDistance(x, y, p):
    zipped_coordinate = zip(x, y)
    return math.pow(np.sum([math.pow(np.abs(i[0]-i[1]), p) for i in zipped_coordinate]), 1/p)
1
2
3
4
5
6

2.5 标准化的欧几里得距离（Standardized Euclidean Distance）

• 数学公式

思路：将各个分量“标准化”到均值，方差等的区间：
$$X^{\ast }=\frac{X-m}{S}$$
其中，$X^{\ast }$为标准化后的值，$X$为原值，$m$为分量的均值，$S$为分量的标准差

n维空间中标准化的欧几里得距离公式：
$$d_{(a,b)}=\sqrt{\sum _{k=1}^n\frac{(x_{1k}-x_{2k})}{S_k{)}^2}}$$
如果将方差的导数看成一个权重，则这个公式可以看成是一种加权欧氏距离(Weighted Euclidean Distance)

• Python代码

import numpy as np
# 标准化的欧几里得距离
def StandardizedEuclideanDistance(x, y):
    x = np.array(x)
    y = np.array(y)
    
    X = np.vstack([x,y])
    sigma = np.var(X, axis=0, ddof=1)
    return np.sqrt(((x - y) ** 2 /sigma).sum())
1
2
3
4
5
6
7
8
9

2.6 余弦距离（Cosine Distance）

• 数学公式

n nn维空间中的余弦距离：
$$cos(x,y)=\frac{x\cdot y}{|x|\cdot |y|}$$
即 $$cos(x,y)=\frac{{\sum }_{i=1}^n{x}_i{y}_i}{\sqrt{{\sum }_{i=1}^n{x}_i^2}\sqrt{{\sum }_{i=1}^n{y}_i^2}}$$
在机器学习中，经常需要比较和衡量向量之间的相似性或差异性 🢂 余弦距离计算的是两个向量之间的夹角（不仅仅是它们之间的欧氏距离，余弦距离在处理高维数据或稀疏数据时更加有效）

• Python代码

import numpy as np
# 余弦距离
def CosineDistance(x, y):
   
    x = np.array(x)
    y = np.array(y)
    return np.dot(x,y)/(np.linalg.norm(x)*np.linalg.norm(y))
1
2
3
4
5
6
7

3. K值的选择

4. KD树（K-Dimensional Tree）

• 构建原理：以2作为根节点（左子树的为小于2的值，右子树的值大于2），中间橙色的分割线为分割超平面

KD树用于优化K近邻算法：由于K近邻算法需要计算待分类样本与所有训练样本之间的距离，当训练集较大时，计算量会变得非常大。而使用KD树可以有效地减少计算量，通过构建KD树结构，在搜索过程中只需要考虑与待分类样本最近邻的子树，避免了对整个训练集的遍历。

KD树的构建和搜索：KD树可以通过递归地将特征空间划分为多个子区域来构建一棵二叉树

KD数的建立
如：有6个点(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)
根节点（此处以中位数确定根节点，如果中位数有两个则可随机选择一个）
   先6个点按照不同维度（此处为x，y两个维度）分开进行排序
      x轴：2,4,5,7,8,9
      y轴：1,2,3,4,5,6
   从两个维度中选择一个维度来划分（一般以方差最大化，均值最近邻等来选择先对那个维度划分），如选择方差较大的线划分，第一维度划分完成后，再以此对剩余维度进行划分，直到全部划分完成为止

5. 最近领域搜索（Nearest Neighbor Lookup）

持续更新中***

6. KD树的应用

图像搜索：通过构建KD树，可以将图像数据集中的每个图像表示为一个向量，并且可以高效地进行最近邻搜索。当用户输入一张图像时，可以使用KD树找到与之最相似的图像，实现图像搜索和推荐功能。

机器学习分类：在机器学习中，可以使用KD树来对训练数据进行组织和索引。当有一个新的测试样本需要分类时，可以使用KD树进行最近邻搜索，找到最相似的训练样本，并根据其标签进行分类。

数据库查询优化：在数据库系统中，通过使用KD树索引，可以提高查询的效率。例如，在地理信息系统中，可以使用KD树来索引地理位置信息，通过范围搜索或最近邻搜索快速检索符合条件的数据。

粒子模拟：在计算物理学中，粒子模拟是一种常见的方法，用于模拟物质中的粒子运动。通过使用KD树对粒子进行组织，可以高效地进行粒子之间的相互作用计算，加速模拟过程。

数据压缩：KD树可以用于数据压缩，特别是在高维数据中。通过对数据集进行适当的划分和组织，可以减小数据集的维度并降低存储空间。