K近邻(K-Nearest Neighbors, KNN)算法中距离度量方式和计算公式
在K近邻(K-Nearest Neighbors, KNN)算法中,距离度量方式用于计算样本之间的相似性或距离,这是选择“邻居”的基础。常见的距离度量方式有以下几种:
1. 欧氏距离(Euclidean Distance)
欧氏距离是最常用的度量方式之一,用于计算两个样本点之间的“直线”距离。适用于连续数值型特征。
公式为:
d
(
x
,
y
)
=
∑
i
=
1
n
(
x
i
−
y
i
)
2
d(x, y) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}
d(x,y)=i=1∑n(xi−yi)2
其中,
x
i
x_i
xi 和
y
i
y_i
yi 分别是两个样本
x
x
x 和
y
y
y 在第
i
i
i 个特征上的取值,
n
n
n 是特征的总数。
示例:
若有两个二维点
x
=
(
1
,
2
)
x = (1, 2)
x=(1,2) 和
y
=
(
4
,
6
)
y = (4, 6)
y=(4,6),则它们的欧氏距离为:
d
(
x
,
y
)
=
(
1
−
4
)
2
+
(
2
−
6
)
2
=
9
+
16
=
25
=
5
d(x, y) = \sqrt{(1-4)^2 + (2-6)^2} = \sqrt{9 + 16} = \sqrt{25} = 5
d(x,y)=(1−4)2+(2−6)2=9+16=25=5
2. 曼哈顿距离(Manhattan Distance)
曼哈顿距离也称为“绝对值距离”或“城市街区距离”,它度量的是两点在各个坐标轴方向上的距离总和,适合网格状布局的数据。
公式为:
d
(
x
,
y
)
=
∑
i
=
1
n
∣
x
i
−
y
i
∣
d(x, y) = \sum_{i=1}^{n} |x_i - y_i|
d(x,y)=i=1∑n∣xi−yi∣
示例:
对同样的点
x
=
(
1
,
2
)
x = (1, 2)
x=(1,2) 和
y
=
(
4
,
6
)
y = (4, 6)
y=(4,6),曼哈顿距离为:
d
(
x
,
y
)
=
∣
1
−
4
∣
+
∣
2
−
6
∣
=
3
+
4
=
7
d(x, y) = |1 - 4| + |2 - 6| = 3 + 4 = 7
d(x,y)=∣1−4∣+∣2−6∣=3+4=7
3. 闵可夫斯基距离(Minkowski Distance)
闵可夫斯基距离是欧氏距离和曼哈顿距离的泛化形式,通过改变参数 p p p 可以得到不同的距离度量方式。当 p = 1 p = 1 p=1 时,得到曼哈顿距离;当 p = 2 p = 2 p=2 时,得到欧氏距离。
公式为:
d
(
x
,
y
)
=
(
∑
i
=
1
n
∣
x
i
−
y
i
∣
p
)
1
/
p
d(x, y) = \left( \sum_{i=1}^{n} |x_i - y_i|^p \right)^{1/p}
d(x,y)=(i=1∑n∣xi−yi∣p)1/p
4. 切比雪夫距离(Chebyshev Distance)
切比雪夫距离用于度量任意两个点在某一维度上的最大差值。它适用于某些需要考虑最远距离的情况。
公式为:
d
(
x
,
y
)
=
max
i
∣
x
i
−
y
i
∣
d(x, y) = \max_{i} |x_i - y_i|
d(x,y)=imax∣xi−yi∣
示例:
同样对于
x
=
(
1
,
2
)
x = (1, 2)
x=(1,2) 和
y
=
(
4
,
6
)
y = (4, 6)
y=(4,6),切比雪夫距离为:
d
(
x
,
y
)
=
max
(
∣
1
−
4
∣
,
∣
2
−
6
∣
)
=
max
(
3
,
4
)
=
4
d(x, y) = \max(|1 - 4|, |2 - 6|) = \max(3, 4) = 4
d(x,y)=max(∣1−4∣,∣2−6∣)=max(3,4)=4
5. 马氏距离(Mahalanobis Distance)
马氏距离是一种考虑了样本分布的距离度量,它通过协方差矩阵来衡量样本的相关性。适合用于处理有相关性的多维特征数据,常用于异常检测。
公式为:
d
(
x
,
y
)
=
(
x
−
y
)
T
S
−
1
(
x
−
y
)
d(x, y) = \sqrt{(x - y)^T S^{-1} (x - y)}
d(x,y)=(x−y)TS−1(x−y)
其中,
S
S
S 是特征的协方差矩阵,
S
−
1
S^{-1}
S−1 是协方差矩阵的逆矩阵。
示例:
马氏距离特别适合应用在金融领域,比如股票的价格波动,它们的波动率和协同关系会影响马氏距离的结果。
6. 余弦相似度(Cosine Similarity)
余弦相似度用于衡量两个向量之间的角度,而非距离。适用于高维度稀疏向量(如文本向量化)。它的值在 [ − 1 , 1 ] [-1, 1] [−1,1] 之间,值越接近 1,说明两个向量越相似。
公式为:
Cosine Similarity
=
x
⋅
y
∥
x
∥
∥
y
∥
\text{Cosine Similarity} = \frac{x \cdot y}{\|x\| \|y\|}
Cosine Similarity=∥x∥∥y∥x⋅y
其中,
x
⋅
y
x \cdot y
x⋅y 是两个向量的点积,
∥
x
∥
\|x\|
∥x∥ 和
∥
y
∥
\|y\|
∥y∥ 分别是向量的模。
7. 汉明距离(Hamming Distance)
汉明距离用于衡量两个等长字符串(或二进制向量)之间不同字符的个数,常用于二值特征或者分类问题。
公式为:
d
(
x
,
y
)
=
∑
i
=
1
n
1
(
x
i
≠
y
i
)
d(x, y) = \sum_{i=1}^{n} \mathbf{1}(x_i \neq y_i)
d(x,y)=i=1∑n1(xi=yi)
其中
1
(
⋅
)
\mathbf{1}(\cdot)
1(⋅) 表示指示函数,当条件为真时取 1,假时取 0。
示例:
对于二进制字符串
x
=
10101
x = 10101
x=10101 和
y
=
10011
y = 10011
y=10011,它们的汉明距离为:
d
(
x
,
y
)
=
1
+
0
+
1
+
0
+
1
=
3
d(x, y) = 1 + 0 + 1 + 0 + 1 = 3
d(x,y)=1+0+1+0+1=3
8. 杰卡德距离(Jaccard Distance)
杰卡德距离用于衡量两个集合之间的相似度。它是基于集合交集和并集的比率,常用于比较文本、集合等离散数据。
杰卡德相似度的公式为:
Jaccard Similarity
=
∣
A
∩
B
∣
∣
A
∪
B
∣
\text{Jaccard Similarity} = \frac{|A \cap B|}{|A \cup B|}
Jaccard Similarity=∣A∪B∣∣A∩B∣
杰卡德距离是相似度的补数:
d
(
A
,
B
)
=
1
−
Jaccard Similarity
d(A, B) = 1 - \text{Jaccard Similarity}
d(A,B)=1−Jaccard Similarity
示例:
对于两个集合
A
=
{
1
,
2
,
3
}
A = \{1, 2, 3\}
A={1,2,3} 和
B
=
{
2
,
3
,
4
}
B = \{2, 3, 4\}
B={2,3,4},它们的杰卡德相似度为:
Jaccard Similarity
=
∣
{
2
,
3
}
∣
∣
{
1
,
2
,
3
,
4
}
∣
=
2
4
=
0.5
\text{Jaccard Similarity} = \frac{|\{2, 3\}|}{|\{1, 2, 3, 4\}|} = \frac{2}{4} = 0.5
Jaccard Similarity=∣{1,2,3,4}∣∣{2,3}∣=42=0.5
所以杰卡德距离为:
d
(
A
,
B
)
=
1
−
0.5
=
0.5
d(A, B) = 1 - 0.5 = 0.5
d(A,B)=1−0.5=0.5
9. 布雷叶距离(Bray-Curtis Distance)
布雷叶距离用于衡量两个样本之间的差异,常用于生态学和环境科学中。其值范围在 [ 0 , 1 ] [0, 1] [0,1] 之间。
公式为:
d
(
x
,
y
)
=
∑
i
=
1
n
∣
x
i
−
y
i
∣
∑
i
=
1
n
∣
x
i
+
y
i
∣
d(x, y) = \frac{\sum_{i=1}^{n} |x_i - y_i|}{\sum_{i=1}^{n} |x_i + y_i|}
d(x,y)=∑i=1n∣xi+yi∣∑i=1n∣xi−yi∣
示例:
对于两个样本
x
=
(
1
,
2
)
x = (1, 2)
x=(1,2) 和
y
=
(
3
,
4
)
y = (3, 4)
y=(3,4),它们的布雷叶距离为:
d
(
x
,
y
)
=
∣
1
−
3
∣
+
∣
2
−
4
∣
∣
1
+
3
∣
+
∣
2
+
4
∣
=
2
+
2
4
+
6
=
4
10
=
0.4
d(x, y) = \frac{|1 - 3| + |2 - 4|}{|1 + 3| + |2 + 4|} = \frac{2 + 2}{4 + 6} = \frac{4}{10} = 0.4
d(x,y)=∣1+3∣+∣2+4∣∣1−3∣+∣2−4∣=4+62+2=104=0.4
10. 马氏重合距离(Mahalanobis–Ovchinnikov Distance)
这是马氏距离的扩展,考虑了不同类别的重合性。它广泛用于带有类标签的样本分类问题中。
11. 地球移动距离(Earth Mover’s Distance, EMD)
地球移动距离用于度量两个分布之间的最小“代价”,通过计算将一个分布转化为另一个分布的最小工作量,常用于图像处理和计算机视觉中。
公式通过求解最优传输问题(Optimal Transport Problem)得出。
12. 动态时间规整距离(Dynamic Time Warping, DTW)
DTW 距离用于衡量两个时间序列之间的相似性,允许时间序列进行非线性对齐。广泛用于语音识别和时间序列分析。
13. Canberra距离
Canberra距离在比较两个向量时,通过标准化元素间的差异,能够更好地处理小值和大值。
公式为:
d
(
x
,
y
)
=
∑
i
=
1
n
∣
x
i
−
y
i
∣
∣
x
i
∣
+
∣
y
i
∣
d(x, y) = \sum_{i=1}^{n} \frac{|x_i - y_i|}{|x_i| + |y_i|}
d(x,y)=i=1∑n∣xi∣+∣yi∣∣xi−yi∣
14. 加权距离(Weighted Distance)
有时候为了体现某些特征对距离计算的重要性,可以给每个特征赋予不同的权重。加权欧氏距离的公式为:
d
(
x
,
y
)
=
∑
i
=
1
n
w
i
(
x
i
−
y
i
)
2
d(x, y) = \sqrt{\sum_{i=1}^{n} w_i (x_i - y_i)^2}
d(x,y)=i=1∑nwi(xi−yi)2
其中
w
i
w_i
wi 是第
i
i
i 个特征的权重。
这些距离度量方法适用于不同的数据类型和问题场景。可以根据具体的应用选择合适的度量方式。
原文地址:https://blog.csdn.net/u013172930/article/details/142614363
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!