算法金 | 欧氏距离算法、余弦相似度、汉明、曼哈顿、切比雪夫、闵可夫斯基、雅卡尔指数、半正矢、Sørensen-Dice

cnblogs 2024-07-03 08:13:00 阅读 92

大侠幸会,在下全网同名「算法金」 0 基础转 AI 上岸,多个算法赛 Top 「日更万日,让更多人享受智能乐趣」

在算法模型构建中,我们经常需要计算样本之间的相似度,通常的做法是计算样本之间的距离。 今天,一键拿下九种距离算法。走你~

一、欧氏距离 (Euclidean Distance)

定义与公式

欧氏距离是两个点在 n 维空间中直线距离的度量。它是最常见的距离度量方法之一,用于计算两个向量之间的距离。欧氏距离的公式如下:

应用场景

欧氏距离广泛应用于许多领域,如机器学习、统计学、模式识别和数据挖掘。常见的应用场景包括:

  • 分类算法:如 k 近邻 (k-Nearest Neighbors, KNN) 算法,通过计算新样本与训练样本之间的欧氏距离来进行分类
  • 聚类分析:如 k 均值 (k-Means) 聚类算法,通过计算样本与聚类中心之间的欧氏距离来确定样本所属的簇
  • 图像处理:用于度量图像之间的相似度,如图像检索和图像匹配

优缺点分析

优点:

  • 计算简单:欧氏距离的计算公式简单易懂,且计算量较小,适用于大多数应用场景
  • 直观性强:欧氏距离直接反映了两个点之间的几何距离,具有很强的直观性

缺点:

  • 对尺度敏感:不同维度的数值尺度差异会影响距离的计算结果,需要对数据进行标准化或归一化处理
  • 对异常值敏感:欧氏距离对数据中的异常值非常敏感,异常值可能会显著影响计算结果

欧氏距离(Euclidean Distance)

二、余弦相似度 (Cosine Similarity)

定义与公式

余弦相似度是一种衡量两个向量夹角余弦值的度量,常用于评估两个向量的相似度。公式如下:

应用场景

余弦相似度在许多领域有广泛应用,特别是文本和信息检索领域:

  • 文本相似度计算:在自然语言处理 (NLP) 中,余弦相似度用于计算两个文本或文档之间的相似度,通过比较它们的词频向量
  • 推荐系统:如用户-物品推荐系统,通过计算用户之间或物品之间的相似度来进行推荐
  • 图像相似度计算:在计算机视觉中,用于比较图像特征向量的相似度

优缺点分析

优点:

  • 不受向量长度影响:余弦相似度仅关注向量的方向,而不受向量的长度影响,适用于不同规模的数据
  • 计算简单:公式简单,计算效率高,适合大规模数据处理

缺点:

  • 无法反映数值大小的差异:余弦相似度仅考虑向量的方向,不考虑数值的大小,可能会忽略重要的数值信息
  • 对稀疏向量效果较差:对于稀疏向量(如文本数据中的词频向量),计算结果可能不准确,需要结合其他方法使用

余弦相似度(Cosine Similarity)

防失联,进免费知识星球,直达算法金 AI 实验室 https://t.zsxq.com/ckSu3

更多内容,见免费知识星球

三、汉明距离 (Hamming Distance)

定义与公式

汉明距离用于衡量两个等长字符串之间的不同字符个数。公式如下:

应用场景

汉明距离主要用于以下场景:

  • 错误检测和纠正:在通信和存储系统中,用于检测和纠正数据传输和存储中的错误,如汉明码
  • 基因序列分析:在生物信息学中,用于比较 DNA 和 RNA 序列之间的差异
  • 密码学:在密码分析中,用于比较不同密文之间的差异

优缺点分析

优点:

  • 计算简单:汉明距离的计算过程非常简单,适合大规模数据处理
  • 适用于离散数据:汉明距离特别适用于比较离散数据,如字符串和二进制数据

缺点:

  • 仅适用于等长字符串:汉明距离只能比较长度相同的字符串,对于长度不同的字符串无法计算
  • 不考虑字符位置的重要性:汉明距离只关注字符是否相同,不考虑字符在字符串中的位置重要性

汉明距离(Hamming Distance)

四、曼哈顿距离 (Manhattan Distance)

定义与公式

曼哈顿距离,又称为城市街区距离,是指两个点在 n 维空间中各个坐标轴上的距离之和。公式如下:

应用场景

曼哈顿距离在以下领域有广泛应用:

  • 数据挖掘和机器学习:如在 k 近邻 (KNN) 算法中,用于计算样本之间的距离
  • 图像处理:用于图像像素之间的距离计算,如图像匹配和分割
  • 机器人路径规划:在路径规划中,用于计算机器人在网格地图中的移动距离

优缺点分析

优点:

  • 计算简单:曼哈顿距离的计算公式简单,计算量较小,适用于大多数应用场景
  • 适用于高维数据:在高维空间中,曼哈顿距离比欧氏距离更稳定,不易受到个别维度异常值的影响

缺点:

  • 不适用于所有场景:曼哈顿距离在某些场景中可能不如欧氏距离直观,如需要考虑斜向移动的场景
  • 对尺度敏感:不同维度的数值尺度差异会影响距离的计算结果,需要对数据进行标准化或归一化处理

曼哈顿距离(Manhattan Distance)

防失联,进免费知识星球,直达算法金 AI 实验室 https://t.zsxq.com/ckSu3

免费知识星球,欢迎加入交流

五、切比雪夫距离 (Chebyshev Distance)

定义与公式

切比雪夫距离,又称为棋盘距离,是指两个点在 n 维空间中各个坐标轴上的最大距离。公式如下:

应用场景

切比雪夫距离在以下领域有应用:

  • 棋盘游戏:如国际象棋中,王每次可以沿任意方向移动一个格子,切比雪夫距离用于计算王移动的步数
  • 仓储和物流:在仓储管理中,用于计算物品在网格仓库中的最远距离

优缺点分析

优点:

  • 计算简单:切比雪夫距离的计算公式简单,计算量小,适用于需要快速计算距离的场景
  • 直观性强:对于某些特定场景,如棋盘游戏,切比雪夫距离具有很强的直观性

缺点:

  • 应用范围有限:切比雪夫距离主要适用于特定场景,不适合所有类型的数据分析
  • 对异常值敏感:切比雪夫距离对数据中的异常值非常敏感,异常值可能会显著影响计算结果

切比雪夫距离(Chebyshev Distance)

六、闵可夫斯基距离 (Minkowski Distance)

定义与公式

闵可夫斯基距离是欧氏距离和曼哈顿距离的广义形式,通过调整参数 𝑝𝑝,可以得到不同的距离度量。公式如下:

应用场景

闵可夫斯基距离广泛应用于数据分析和机器学习中:

  • 分类算法:如 k 近邻 (KNN) 算法中,通过调整 𝑝𝑝 值来选择适合的距离度量
  • 聚类分析:如 k 均值 (k-Means) 聚类算法中,通过调整 𝑝𝑝 值来确定样本与聚类中心之间的距离

优缺点分析

优点:

  • 灵活性高:通过调整参数 𝑝,可以得到不同的距离度量,适应不同的应用场景
  • 计算公式统一:无论是曼哈顿距离还是欧氏距离,均可以通过统一的闵可夫斯基距离公式来计算

缺点:

  • 参数选择困难:在实际应用中,选择合适的 𝑝𝑝 值可能比较困难,需要根据具体问题进行调整
  • 对异常值敏感:闵可夫斯基距离对数据中的异常值较为敏感,可能会影响计算结果

闵可夫斯基距离 (Minkowski Distance)

七、雅卡尔指数 (Jaccard Index)

定义与公式

雅卡尔指数用于衡量两个集合的相似度,其值为两个集合交集的大小除以并集的大小。公式如下:

应用场景

雅卡尔指数在以下领域有广泛应用:

  • 信息检索:用于评估搜索结果与查询的相关性
  • 图像处理:用于比较图像分割结果与真实分割的相似度
  • 生态学:用于比较不同物种群落之间的相似度

优缺点分析

优点:

  • 适用于集合数据:雅卡尔指数特别适用于比较离散的集合数据
  • 计算简单:雅卡尔指数的计算过程简单,适用于大规模数据处理

缺点:

  • 对稀疏数据效果较差:对于稀疏数据(如文本数据),雅卡尔指数可能不准确,需要结合其他方法使用
  • 无法处理权重信息:雅卡尔指数仅考虑集合中元素的存在与否,不考虑元素的权重信息

雅卡尔指数(Jaccard Index)

八、半正矢距离 (Haversine Distance)

定义与公式

半正矢距离用于计算地球表面上两点之间的最短距离,考虑到地球的球形特性。公式如下:

应用场景

半正矢距离主要用于以下场景:

  • 地理信息系统 (GIS):用于计算地球表面两点之间的最短距离
  • 导航系统:用于GPS导航系统中,计算起点和终点之间的距离
  • 航空和海洋运输:用于计算航线和航程

优缺点分析

优点:

  • 考虑地球曲率:半正矢距离考虑到地球的球形特性,计算结果更准确
  • 适用于长距离计算:对于长距离的两点间距离计算,半正矢距离比直线距离更准确

缺点:

  • 计算复杂:半正矢距离的计算公式较复杂,计算量较大,不适合实时计算
  • 对短距离不敏感:对于短距离的两点间距离计算,半正矢距离与直线距离差异不大

半正矢距离 (Haversine Distance)

防失联,进免费知识星球,直达算法金 AI 实验室 https://t.zsxq.com/ckSu3

免费知识星球,欢迎加入,一起交流切磋

九、Sørensen-Dice 系数

(Sørensen-Dice Coefficient)

定义与公式

Sørensen-Dice 系数用于衡量两个集合的相似度,其值为两个集合交集的大小的两倍除以两个集合大小的总和。公式如下:

应用场景

Sørensen-Dice 系数在以下领域有广泛应用:

  • 信息检索:用于评估搜索结果与查询的相关性
  • 图像处理:用于比较图像分割结果与真实分割的相似度
  • 生态学:用于比较不同物种群落之间的相似度

优缺点分析

优点:

  • 适用于集合数据:Sørensen-Dice 系数特别适用于比较离散的集合数据
  • 计算简单:Sørensen-Dice 系数的计算过程简单,适用于大规模数据处理

缺点:

  • 对稀疏数据效果较差:对于稀疏数据(如文本数据),Sørensen-Dice 系数可能不准确,需要结合其他方法使用
  • 无法处理权重信息:Sørensen-Dice 系数仅考虑集合中元素的存在与否,不考虑元素的权重信息

Sørensen-Dice 系数 (Sørensen-Dice Coefficient)

[ 抱个拳,总个结 ]

各种距离和相似度的对比分析

数学性质对比

  • 欧氏距离:度量空间中两点之间的直线距离,具有平移不变性和对称性
  • 余弦相似度:度量两个向量之间夹角的余弦值,仅考虑向量的方向,不考虑向量的大小
  • 汉明距离:度量两个等长字符串之间不同字符的个数,适用于离散数据
  • 曼哈顿距离:度量空间中两点在各坐标轴上的距离之和,适用于高维数据
  • 切比雪夫距离:度量两个点在各坐标轴上的最大距离,适用于棋盘游戏等特定场景
  • 闵可夫斯基距离:欧氏距离和曼哈顿距离的广义形式,通过调整参数 𝑝𝑝 可得到不同的距离度量
  • 雅卡尔指数:度量两个集合的相似度,计算两个集合交集与并集的比值
  • 半正矢距离:计算地球表面两点间的最短距离,考虑地球的球形特性
  • Sørensen-Dice 系数:度量两个集合的相似度,计算两个集合交集大小的两倍与两个集合大小总和的比值

计算复杂度对比

  • 欧氏距离:𝑂(𝑛),计算简单,适用于大多数应用场景
  • 余弦相似度:𝑂(𝑛),计算简单,适合大规模数据处理
  • 汉明距离:𝑂(𝑛),计算简单,适合离散数据
  • 曼哈顿距离:𝑂(𝑛),计算简单,适用于高维数据
  • 切比雪夫距离:𝑂(𝑛),计算简单,适用于特定场景
  • 闵可夫斯基距离:𝑂(𝑛),通过调整参数 𝑝𝑝,适应不同的应用场景
  • 雅卡尔指数:𝑂(𝑛),计算简单,适用于集合数据
  • 半正矢距离:𝑂(1),公式复杂,适合地理信息系统等场景
  • Sørensen-Dice 系数:𝑂(𝑛),计算简单,适用于集合数据

适用场景对比

  • 欧氏距离:适用于空间距离计算、分类算法(如 KNN)、聚类分析(如 K-Means)
  • 余弦相似度:适用于文本相似度计算、推荐系统、图像相似度计算
  • 汉明距离:适用于错误检测和纠正、基因序列分析、密码学
  • 曼哈顿距离:适用于数据挖掘和机器学习、图像处理、机器人路径规划
  • 切比雪夫距离:适用于棋盘游戏、仓储和物流
  • 闵可夫斯基距离:适用于分类算法、聚类分析
  • 雅卡尔指数:适用于信息检索、图像处理、生态学
  • 半正矢距离:适用于地理信息系统、导航系统、航空和海洋运输
  • Sørensen-Dice 系数:适用于信息检索、图像处理、生态学

核心要点回顾

  • 欧氏距离:计算空间中两点间的直线距离,简单易懂
  • 余弦相似度:计算两个向量间夹角的余弦值,适合文本和向量数据
  • 汉明距离:计算两个等长字符串间不同字符的个数,适合离散数据
  • 曼哈顿距离:计算空间中两点在各坐标轴上的距离之和,适合高维数据
  • 切比雪夫距离:计算两点间各坐标轴上的最大距离,适用于特定场景
  • 闵可夫斯基距离:欧氏距离和曼哈顿距离的广义形式,通过参数调整适应不同场景
  • 雅卡尔指数:计算两个集合的相似度,适合集合数据
  • 半正矢距离:计算地球表面两点间的最短距离,考虑地球曲率
  • Sørensen-Dice 系数:计算两个集合的相似度,适合集合数据

- 科研为国分忧,创新与民造福 -

日更时间紧任务急,难免有疏漏之处,还请大侠海涵 内容仅供学习交流之用,部分素材来自网络,侵联删

[ 算法金,碎碎念 ]

这个神反馈,

有点意思

hhh~

全网同名,日更万日,让更多人享受智能乐趣

如果觉得内容有价值,烦请大侠多多 分享、在看、点赞,助力算法金又猛又持久、很黄很 BL 的日更下去;

同时邀请大侠 关注、星标 算法金,围观日更万日,助你功力大增、笑傲江湖



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。