K近邻(K-Nearest Neighbors, KNN)算法中距离度量方式和计算公式

news/2024/9/28 13:41:06 标签: 机器学习, 分类, k-近邻算法, 人工智能

在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=1n(xiyi)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)=(14)2+(26)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=1nxiyi

示例
对同样的点 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)=∣14∣+∣26∣=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=1nxiyip)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)=imaxxiyi

示例
同样对于 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(∣14∣,∣26∣)=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)=(xy)TS1(xy)
其中, S S S 是特征的协方差矩阵, S − 1 S^{-1} S1 是协方差矩阵的逆矩阵。

示例
马氏距离特别适合应用在金融领域,比如股票的价格波动,它们的波动率和协同关系会影响马氏距离的结果。

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∥∥yxy
其中, x ⋅ y x \cdot y xy 是两个向量的点积, ∥ 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=1n1(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=ABAB
杰卡德距离是相似度的补数:
d ( A , B ) = 1 − Jaccard Similarity d(A, B) = 1 - \text{Jaccard Similarity} d(A,B)=1Jaccard 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)=10.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=1nxi+yii=1nxiyi

示例
对于两个样本 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∣∣13∣+∣24∣=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=1nxi+yixiyi

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=1nwi(xiyi)2
其中 w i w_i wi 是第 i i i 个特征的权重。


这些距离度量方法适用于不同的数据类型和问题场景。可以根据具体的应用选择合适的度量方式。


http://www.niftyadmin.cn/n/5681200.html

相关文章

【网络安全安全管理入门必知必会】应急响应之服务器入侵排查,零基础入门到精通,收藏这篇就够了

前言 这是西西给粉丝盆友们整理的应急响应阶段第3篇。 喜欢的朋友们,记得点赞支持和收藏一下,关注我,学习黑客技术。 1. 应急响应 应急响应通常是在当服务器被黑客入侵后,我们需要对入侵事件进行系统的溯源和排查。主要思路就…

IIS HTTPS 网页可能暂时无法连接,或者它已永久性地移动到了新网址 ERR_HTTP2_INADEQUATE_TRANSPORT_SECURITY

问题描述:站点突然无法访问,经排查发现,HTTP协议的网址可以继续访问,HTTPS的网址不可以访问。 问题分析:在Windows更新和滚动之后,由于 HTTP/2,当站点启动了 HTTP/2 连接,会出现一个…

影刀RPA实战:CSDN资料查看小工具

1.实战目标 本次带来的实战,是制作一个查询小工具,作为技术人员,不可避免的就是查资料,在一个搜索引擎上来回折返跑,浏览页面,打开页面,关闭页面,反反复复,今天呢&#…

vue3中使用echarts折线图初始化只显示一条数据,其余折线根据用户点击进行显示

vue3中使用echarts折线图初始化只显示一条折线,其余折线根据用户点击进行显示 1、主要是在图例属性中去配置selected属性,将刚开始需要展示的折线设置为true,其余设置为false selected: {"云存储": false,"云胶片": fa…

我店生活系统小程序开发功能解析

一、市场定位与目标用户 市场定位:我店生活小程序旨在打造一个集购物、娱乐、服务于一体的综合性本地生活服务平台,满足用户多样化的生活需求。通过整合周边生活服务资源,提供一站式的生活服务体验。 目标用户:主要面向中青年人…

WebSocket 在 Spring Boot 中的高级应用指南

WebSocket 在 Spring Boot 中的高级应用指南 深入理解WebSocket协议 深入理解STOMP协议 1. 概述 WebSocket 是一种基于 TCP 的全双工通信协议,允许服务器和客户端之间进行持续的双向通信。与传统的 HTTP 请求-响应模型不同,WebSocket 是一个持久的连接,可以在服务器和客户…

深信服2025届全球校招研发笔试-C卷(AK)

前面14个填空题 T1 已知 子数组 定义为原数组中的一个连续子序列。现给定一个正整数数组 arr,请计算该数组内所有可能的奇数长度子数组的数值之和。 输入描述 输入一个正整数数组arr 输出描述 所有可能的奇数长度子数组的和 示例 1 输入 1,4,2,5,3 输出 58 说明 …

Spark Job 对象 详解

在 Apache Spark 中,Job 对象是执行逻辑的核心组件之一,它代表了对一系列数据操作(如 transformations 和 actions)的提交。理解 Job 的本质和它在 Spark 中的运行机制,有助于深入理解 Spark 的任务调度、执行模型和容…