[人工智能]KNN算法

Overview

K近邻值算法 KNN (K — Nearest Neighbors) 是一种机器学习中的分类算法；K-NN是一种非参数的惰性学习算法。非参数意味着没有对基础数据分布的假设，即模型结构是从数据集确定的。

它被称为惰性算法的原因是，因为它**不需要任何训练数据点来生成模型。**所有训练数据都用于测试阶段，这使得训练更快，测试阶段更慢且成本更高。

如何工作

KNN 算法是通过计算新对象与训练数据集中所有对象之间的距离，对新实例进行分类或回归预测。然后选择训练数据集中距离最小的 K 个示例，并通过平均结果进行预测。

如图所示：一个未分类的数据（红色）和所有其他已分类的数据（黄色和紫色），每个数据都属于一个类别。因此，计算未分类数据与所有其他数据的距离，以了解哪些距离最小，因此当K= 3 （或K= 6 ）最接近的数据并检查出现最多的类，如下图所示，与新数据最接近的数据是在第一个圆圈内（圆圈内）的数据，在这个圆圈内还有 3 个其他数据（已经用黄色分类），我们将检查其中的主要类别，会被归类为紫色，因为有2个紫色球，1个黄色球。

KNN算法要执行的步骤

• 将数据分为训练数据和测试数据
• 选择一个值 K
• 确定要使用的距离算法
• 从需要分类的测试数据中选择一个样本，计算到它的 n 个训练样本的距离。
• 对获得的距离进行排序并取 k最近的数据样本。
• 根据 k 个邻居的多数票将测试类分配给该类。

影响KNN算法性能的因素

• 用于确定最近邻居的距离的算法

• 用于从 K 近邻派生分类的决策规则

• 用于对新示例进行分类的邻居数

如何计算距离

测量距离是KNN算法的核心，总结了问题域中两个对象之间的相对差异。比较常见的是，这两个对象是描述主题（例如人、汽车或房屋）或事件（例如购买、索赔或诊断）的数据行。

汉明距离

汉明距离（Hamming Distance）计算两个二进制向量之间的距离，也简称为二进制串 binary strings 或位串 bitstrings ；换句话说，汉明距离是将一个字符串更改为另一个字符串所需的最小替换次数，或将一个字符串转换为另一个字符串的最小错误数。

示例：如一列具有类别 “红色”、“绿色” 和 “蓝色”，您可以将每个示例独热编码为一个位串，每列一个位。

注：独热编码 one-hot encoding：将分类数据，转换成二进制向量表示，这个二进制向量用来表示一种特殊的bit（二进制位）组合，该字节里，仅容许单一bit为1，其他bit都必须为0

如：

apple	banana	pineapple
1	0	0
0	1	0
0	0	1

100 表示苹果，100就是苹果的二进制向量
010 表示香蕉，010就是香蕉的二进制向量

red = [1, 0, 0]
green = [0, 1, 0]
blue = [0, 0, 1]

而red和green之间的距离就是两个等长bitstrings之间bit差（对应符号不同的位置）的总和或平均数，这就是汉明距离

• $HammingDistanced(a,b)=sum(xi!=yiforxi,yiinzip(x,y))$

上述的实现为：

def hammingDistance(a, b):
    if len(a) != len(b):
        raise ValueError("Undefined for sequences of unequal length.")
    return sum(abs(e1 - e2) for e1, e2 in zip(a, b))

row1 = [0, 0, 0, 0, 0, 1]
row2 = [0, 0, 0, 0, 1, 0]

dist = hammingDistance(row1, row2)
print(dist)

可以看到字符串之间有两个差异，或者 6 个位位置中有 2 个不同，平均 (2/6) 约为 1/3 或 0.333。

from scipy.spatial.distance import hamming
# define data
row1 = [0, 0, 0, 0, 0, 1]
row2 = [0, 0, 0, 0, 1, 0]

# calculate distance
dist = hamming(row1, row2)
print(dist)

欧几里得距离

欧几里得距离（Euclidean distance） 是计算两个点之间的距离。在计算具体的数值（例如浮点数或整数）的两行数据之间的距离时，您最有可能使用欧几里得距离。

欧几里得距离计算公式为两个向量之间的平方差之和的平方根。

$EuclideanDistance=\sqrt[]{\sum (a?b{)}^2}$

如果要执行数千或数百万次距离计算，通常会去除平方根运算以加快计算速度。修改后的结果分数将具有相同的相对比例，并且仍然可以在机器学习算法中有效地用于查找最相似的示例。

$EuclideanDistance=sumforitoN(v1[i]–v2[i]{)}^2$

# calculating euclidean distance between vectors
from math import sqrt
from scipy.spatial.distance import euclidean

# calculate euclidean distance
def euclidean_distance(a, b):
	return sqrt(sum((e1-e2)**2 for e1, e2 in zip(a,b)))
 
# define data
row1 = [10, 20, 15, 10, 5]
row2 = [12, 24, 18, 8, 7]
# calculate distance
dist = euclidean_distance(row1, row2)
print(dist)
print(euclidean(row1, row2))

曼哈顿距离

曼哈顿距离（ Manhattan distance ）又被称作出租车几何学 Taxicab geometry；用于计算两个向量之间的距离。

对于描述网格上的对象（如棋盘或城市街区）的向量可能更有用。出租车在城市街区之间采取的最短路径（网格上的坐标）。

粗略地说，欧几里得几何是中学常用的平面几何和立体几何 Plane geometry

曼哈顿距离可以理解为：欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。

图中： 红、蓝与黄线分别表示所有曼哈顿距离都拥有一样长度（12），绿线表示欧几里得距离 $6\times \sqrt{2}\approx 8.48$

对于整数特征空间中的两个向量，应该计算曼哈顿距离而不是欧几里得距离

曼哈顿距离在二维平面的计算公式是，在X轴的亮点

$Manhattandistanced(x,y)=\left|x_1?x_2\right|+\left|y_1?y_2\right|$

如果所示，描述格子和格子之间的距离可以用曼哈顿距离，如国王移动到右下角的距离是？

$King=|6?8|+|6?1|=7$

两个向量间的距离可以表示为 $MD=\Sigma |Ai–Bi|$

python中的公式可以表示为 ：sum(abs(val1-val2) for val1, val2 in zip(a,b))

from scipy.spatial.distance import cityblock
# calculate manhattan distance
def manhattan_distance(a, b):
	return sum(abs(e1-e2) for e1, e2 in zip(a,b))
 
# define data
row1 = [10, 20, 15, 10, 5]
row2 = [12, 24, 18, 8, 7]
# calculate distance
dist = manhattan_distance(row1, row2)
print(dist)
print(cityblock(row1, row2))

闵可夫斯基距离

闵可夫斯基距离（Minkowski distance）并不是一种距离而是对是欧几里得距离和曼哈顿距离的概括，用来计算两个向量之间的距离。

闵可夫斯基增并添加了一个参数，称为**“阶数”**或 p：$d(x,y) = (\sum(|x-y|)^p)\frac{1}{p} $

在python中的公式：

(sum for i to N (abs(v1[i] – v2[i]))^p)^(1/p)

p 是一个有序的参数，当 $p=1$ 时，计算的是曼哈顿距离。当 $p=2$ 时，计算的是欧几里得距离。

在实现使用距离度量的机器学习算法时，通常会使用闵可夫斯基距离，因为可以通过调整参数“ p ”控制用于向量的距离度量算法的类型。

# calculating minkowski distance between vectors
from scipy.spatial import minkowski_distance
 
# calculate minkowski distance
def minkowski_distance(a, b, p):
	return sum(abs(e1-e2)**p for e1, e2 in zip(a,b))**(1/p)
 
# define data
row1 = [10, 20, 15, 10, 5]
row2 = [12, 24, 18, 8, 7]

# 手动实现的算法用来使用闵可夫斯基计算距离
dist = minkowski_distance(row1, row2, 1)
# 1为曼哈顿
print(dist)
# 1为欧几里得
dist = minkowski_distance(row1, row2, 2)
print(dist)

# 使用包 scipy.spatial来计算
print(minkowski_distance(row1, row2, 1))
print(minkowski_distance(row1, row2, 2))

Reference

distance measures

阅读世界，共赴山海

423全民读书节，邀你共读