一类强大算法总结！！

2023-10-24 16:33:22 浏览数 (2)

这几天看到有小伙伴在讨论距离算法问题，咱们今天也来说道说道。

在很多机器学习算法和实际具体的项目中使用频率很高！

通常情况下，在机器学习中距离算法常用于衡量数据点之间的相似性或差异性。包括以下几个主要应用场景：

  • 聚类分析：在聚类分析中，距离算法被广泛用于测量数据点之间的相似性或距离。常见的聚类算法如K均值聚类、层次聚类等都使用了距离度量来判断数据点之间的相似性和区分不同的聚类簇。
  • 最近邻分类：最近邻分类是一种基于距离的分类算法，它通过计算待分类样本与训练集中各个样本之间的距离来确定其所属类别。最常见的最近邻算法是K最近邻，它根据待分类样本与训练集中K个最近邻的距离来进行分类。
  • 特征选择：在特征选择过程中，距离算法可以用来衡量特征之间的相关性或互信息。通过计算特征之间的距离或相似性，可以选择与目标变量高度相关的特征，以提高模型的性能或减少特征空间的维度。
  • 异常检测：距离算法可用于检测异常或离群点。基于距离的异常检测方法将数据点与其邻近点之间的距离作为度量，根据距离的阈值判断数据点是否为异常或离群点。
  • 降维：在高维数据集中，距离算法可用于降低数据的维度。通过计算数据点之间的距离或相似性，可以将数据点映射到一个较低维度的空间，以减少特征的数量并保留重要的结构信息。

大家伙如果觉得还不错！可以点赞、转发安排起来，让更多的朋友看到。

ok，咱们一起来学习一下~

欧几里德距离（Euclidean Distance）

欧几里德距离（Euclidean Distance）是用来计算两个点之间的距离的一种度量方法。它在多个领域中被广泛应用，特别是在数据挖掘、机器学习和图像处理等领域。

常见使用场景

  • 数据挖掘：欧几里德距离可用于测量不同数据样本之间的相似度，例如聚类分析和推荐系统。
  • 机器学习：欧几里德距离可以作为分类算法中的特征之间的相似性度量，如K近邻算法。
  • 图像处理：欧几里德距离可用于比较两幅图像的相似性，如图像匹配、图像检索等。

下面是一个使用 Python 代码计算欧几里德距离：

代码语言：javascript复制
import math

def euclidean_distance(point1, point2):
    """
    计算两个点之间的欧几里德距离
    输入参数：
        point1: 第一个点的坐标，格式为 (x1, y1)
        point2: 第二个点的坐标，格式为 (x2, y2)
    返回值：
        两个点之间的欧几里德距离
    """
    x1, y1 = point1
    x2, y2 = point2
    distance = math.sqrt((x2 - x1)**2   (y2 - y1)**2)
    return distance

# 示例使用
point_1 = (2, 3)
point_2 = (5, 7)
distance = euclidean_distance(point_1, point_2)
print("两点之间的欧几里德距离：", distance)

对于示例中的点（2, 3）和（5, 7），计算结果为欧几里德距离为5。

下面咱们尝试画一个二维坐标系，在坐标系中， 表示欧几里得算法。

代码中，画出两个点，A 表示点(2, 3)和 B 表示点(5, 7)，画出欧几里得的长度线段。

代码语言：javascript复制
import matplotlib.pyplot as plt

point1 = (2, 3)
point2 = (5, 7)

# 计算欧几里德距离
distance = ((point2[0] - point1[0])**2   (point2[1] - point1[1])**2)**0.5

# 创建一个新的图形
fig, ax = plt.subplots()

# 网格
ax.grid(True, linestyle='--', linewidth=0.5, color='gray')

# 两个点
ax.plot(point1[0], point1[1], 'ro', label='A')
ax.plot(point2[0], point2[1], 'bo', label='B')

# 连线
ax.plot([point1[0], point2[0]], [point1[1], point2[1]], 'k-', label='Distance')

# 欧几里德距离标签
ax.annotate(f'Euclidean Distance: {distance:.2f}', xy=(3.5, 5), xytext=(3.5, 5))

# 添加每个点的标签
ax.annotate('A', xy=point1, xytext=(point1[0]-0.8, point1[1] 0.3))
ax.annotate('B', xy=point2, xytext=(point2[0]-0.8, point2[1] 0.3))
ax.annotate(f'{distance:.2f}', xy=((point1[0] point2[0])/2, (point1[1] point2[1])/2),
            xytext=((point1[0] point2[0])/2-0.5, (point1[1] point2[1])/2 0.4))

# 设置坐标轴范围
ax.set_xlim(0, 6)
ax.set_ylim(0, 8)

# 添加图例
ax.legend()

plt.show()

执行后，我们就会看到一个带有网格、用 A 表示点(2, 3)和 B 表示点(5, 7)的二维坐标图。

曼哈顿距离（Manhattan Distance）

曼哈顿距离也被称为城市街区距离或L1距离，是用来计算两个点之间的距离的一种度量方法。它在多个领域中被广泛应用，特别适用于需要考虑坐标轴上的差异的问题。

常见使用场景

  • 路径规划：曼哈顿距离可以用于计算从一个点到另一个点的最短路径，特别适合网格地图等。
  • 物流管理：曼哈顿距离可用于计算货物从仓库到目的地的最短配送路径。
  • 特征选择：曼哈顿距离可用于评估特征之间的相关性，从而进行特征选择和降维。

下面使用Python代码计算曼哈顿距离：

代码语言：javascript复制
def manhattan_distance(point1, point2):
    """
    计算两个点之间的曼哈顿距离
    输入参数：
        point1: 第一个点的坐标，格式为 (x1, y1)
        point2: 第二个点的坐标，格式为 (x2, y2)
    返回值：
        两个点之间的曼哈顿距离
    """
    x1, y1 = point1
    x2, y2 = point2
    distance = abs(x2 - x1)   abs(y2 - y1)
    return distance

# 示例使用
point_1 = (2, 3)
point_2 = (5, 7)
distance = manhattan_distance(point_1, point_2)
print("两点之间的曼哈顿距离：", distance)

对于示例中的点（2, 3）和（5, 7），计算结果为曼哈顿距离为7。

网上特别流行的一张图：

Manhattan Distance

该图形展示了二维平面上两个点A和B之间的曼哈顿距离。曼哈顿距离是通过在坐标轴上的横向和纵向移动来测量的，即将水平方向和垂直方向的距离相加。

切比雪夫距离（Chebyshev Distance）

切比雪夫距离是一种度量两个向量间差异的距离度量方法。它定义为两个向量在每个维度上元素差的最大值。

切比雪夫距离的公式如下：

D = max(|x_1-y_1|, |x_2-y_2|, ..., |x_n-y_n|)

其中，

D

是切比雪夫距离，

(x_1, x_2, ..., x_n)

和

(y_1, y_2, ..., y_n)

分别是两个向量的元素。

常见使用场景

切比雪夫距离常用于衡量两个向量之间的差异或相似性。

  • 图像处理：用于图像分类、对象识别和图像匹配等任务。
  • 机器学习：可用于聚类算法中的距离计算，例如 K-means 算法。
  • 异常检测：常用于异常数据点的识别。

下面使用 Python 计算切比雪夫距离：

代码语言：javascript复制
def chebyshev_distance(x, y):
    assert len(x) == len(y), "Vectors must have the same length"
    return max(abs(a - b) for a, b in zip(x, y))

# 例子：计算两个向量的切比雪夫距离
vector1 = [1, 2, 3]
vector2 = [4, 5, 6]
distance = chebyshev_distance(vector1, vector2)
print("切比雪夫距离:", distance)

这段代码定义了一个 chebyshev_distance 函数，接受两个向量 x 和 y。在函数中，我们首先确保两个向量具有相同的长度。然后，使用生成器表达式和 zip 函数计算每个维度上的差值，并取得差值的最大绝对值，即切比雪夫距离。

输出结果将显示切比雪夫距离，即在该示例中为 3。

闵可夫斯基距离（Minkowski Distance）

闵可夫斯基距离是一种在向量空间中度量两个点之间距离的方法，它是切比雪夫距离和欧几里得距离的一般化形式。取决于参数

p

的不同，可以计算出不同的闵可夫斯基距离。

闵可夫斯基距离的公式如下：

D = left( sum_{i=1}^{n} |x_i - y_i|^p right)^{frac{1}{p}}

其中，

D

是闵可夫斯基距离，

(x_1, x_2, ..., x_n)

和

(y_1, y_2, ..., y_n)

分别是两个向量的元素，

p

是一个正整数。

假设我们有两个二维向量，分别记为 A 和 B。A 的坐标为 (x1, y1)，B 的坐标为 (x2, y2)。

  • 当参数
p = 1

时，闵可夫斯基距离等同于曼哈顿距离，计算公式如下：

D = |x1 - x2| |y1 - y2|

曼哈顿距离表示从一个点到另一个点在网格上的最短路径（只能沿水平或垂直方向移动）。

  • 当参数
p = 2

时，闵可夫斯基距离等同于欧几里得距离，计算公式如下：

D = sqrt((x1 - x2)^2 (y1 - y2)^2)

欧几里得距离表示两点之间的直线距离。

也就是通过调整参数 p 的值，可以控制距离计算中各个维度的权重。

常见使用场景

闵可夫斯基距离常用于衡量两个向量之间的差异或相似性。

  • 数据挖掘：用于聚类、分类和异常检测等任务。
  • 图像处理：用于图像匹配、对象识别和图像检索等方面。
  • 文本挖掘：用于文本分类、信息检索和自然语言处理等领域。

下面使用 Python 计算闵可夫斯基距离：

代码语言：javascript复制
import math

def minkowski_distance(x, y, p):
    assert len(x) == len(y), "Vectors must have the same length"
    return math.pow(sum(math.pow(abs(a - b), p) for a, b in zip(x, y)), 1/p)

# 例子：计算两个向量的闵可夫斯基距离
vector1 = [1, 2, 3]
vector2 = [4, 5, 6]
distance = minkowski_distance(vector1, vector2, 3)
print("闵可夫斯基距离:", distance)

这段代码定义了一个 minkowski_distance 函数，接受两个向量 x 和 y，以及参数 p。在函数中，我们首先确保两个向量具有相同的长度。然后，使用生成器表达式和 zip 函数计算每个维度上的差值的

p

次幂，并将所有结果求和并开方（根据公式）。最终，得到闵可夫斯基距离。

输出结果将显示闵可夫斯基距离，即在该示例中为 4.326748710922225.

余弦相似度（Cosine Similarity）

余弦相似度是一种常用的相似性度量方法，用于确定两个向量之间的相似程度。它衡量的是两个向量之间的夹角的余弦值。

公式表示为：

text{similarity} = cos(theta) = frac{{A cdot B}}{{|A| cdot |B|}}

其中，

A

和

B

是要比较的两个向量。

使用场景：

1、文本相似度计算：可以应用于文本分类、信息检索等领域，根据文档的词向量来计算相似度。

2、推荐系统：可以根据用户和商品的特征向量，计算相似度来给用户推荐相关的商品。

3、图像处理：可以将图像转换为向量表示，计算不同图像之间的相似性。

下面使用Python代码计算余弦相似度：

代码语言：javascript复制
import numpy as np
from sklearn.metrics.pairwise import cosine_similarity

# 定义两个向量 A 和 B
A = np.array([1, 2, 3])
B = np.array([4, 5, 6])

# 将向量转换为行向量
A = A.reshape(1, -1)
B = B.reshape(1, -1)

# 计算余弦相似度
similarity = cosine_similarity(A, B)[0][0]

print("余弦相似度:", similarity)

这段代码首先导入了numpy库和cosine_similarity函数。然后定义了两个向量A和B，并使用reshape函数将它们转换为行向量。接下来，使用cosine_similarity函数计算余弦相似度，给出结果。

对于直观理解余弦相似度的计算过程，我们用Python代码再来表示：

代码语言：javascript复制
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.patches import Arc

# 定义两个向量 A 和 B
A = np.array([1, 2])
B = np.array([2, 3])

# 计算向量 A 和 B 的模
norm_a = np.linalg.norm(A)
norm_b = np.linalg.norm(B)

# 计算夹角余弦值
cos_theta = np.dot(A, B) / (norm_a * norm_b)

# 绘制向量 A 和 B
plt.quiver(0, 0, A[0], A[1], angles='xy', scale_units='xy', scale=1, color='r')
plt.quiver(0, 0, B[0], B[1], angles='xy', scale_units='xy', scale=1, color='b')

# 绘制夹角
theta = np.arccos(cos_theta)
arc = Arc((0,0), 0.5, 0.5, angle=0, theta1=0, theta2=np.degrees(theta))
plt.gca().add_patch(arc)

# 设置坐标轴范围
plt.xlim(-1, 3)
plt.ylim(-1, 4)

# 添加标签和标题
plt.text(1, 2.5, 'A', fontsize=12)
plt.text(2, 3.5, 'B', fontsize=12)
plt.title('Cosine Similarity')

# 显示图形
plt.grid()
plt.show()

这段代码使用matplotlib.pyplot库绘制了两个向量A和B，并在其中绘制了表示夹角的圆弧。通过设置坐标轴范围和添加标签，可以更好地理解余弦相似度的计算过程。最后通过plt.show()显示图形。

图像处理 函数 数据 算法 异常

0 人点赞