常见距离算法

距离算法用于衡量数据点之间的相似性或差异性，根据数据特性的不同，可以采用不同的度量方法。

一般而言，定义一个函数 $\text{dist}(x, y)$，若它是一个“距离度量”(distance measure)，则需要满足以下基本性质：

1. 非负性: $\text{dist}(x_i, x_j) \geq 0$；
2. 同一性: $\text{dist}(x_i, x_j) = 0$ 当且仅当 $x_i = x_j$；
3. 对称性: $\text{dist}(x_i, x_j) = \text{dist}(x_j, x_i)$；
4. 三角不等式: $\text{dist}(x_i, x_j) \leq \text{dist}(x_i, x_k) + \text{dist}(x_k, x_j)$。

常见的有以下几种：

1. 欧氏距离 (Euclidean Distance)

• 定义: 两点在欧几里得空间中的直线距离。
• 公式: 对于点 $P = (p_1, p_2, \dots, p_n)$ 和 $Q = (q_1, q_2, \dots, q_n)$，欧氏距离为：
  $$
  d(P, Q) = \sqrt{\sum_{i=1}^n (p_i - q_i)^2}
  $$
• 应用: 适用于连续数据，如KNN、K-Means等。

2. 曼哈顿距离 (Manhattan Distance)

• 定义: 两点在标准坐标系上的绝对轴距总和。
• 公式:
  $$
  d(P, Q) = \sum_{i=1}^n |p_i - q_i|
  $$
• 应用: 适用于网格状路径，如城市街区距离。

3. 切比雪夫距离 (Chebyshev Distance)

• 定义: 两点在各坐标轴上的最大差值。
• 公式:
  $$
  d(P, Q) = \max_i |p_i - q_i|
  $$
• 应用: 适用于需要衡量最大差异的场景，如棋盘上的移动。

4. 闵可夫斯基距离 (Minkowski Distance)

• 定义: 欧氏距离和曼哈顿距离的推广，通过参数 $p$ 控制距离类型。
• 公式:
  $$
  d(P, Q) = \left( \sum_{i=1}^n |p_i - q_i|^p \right)^{1/p}
  $$
• 应用: 通过调整 $p$ 值适应不同场景。
• 特点：

  • p=1: 闵可夫斯基距离等同于曼哈顿距离。

  • p=2: 闵可夫斯基距离等同于欧氏距离。

    $$
    d(P, Q) = \left( \sum_{i=1}^n |p_i - q_i|^2 \right)^{1/2}
    $$

    进一步简化为：
    $$
    d(P, Q) = \sqrt{\sum_{i=1}^n (p_i - q_i)^2}
    $$

  • p→∞: 闵可夫斯基距离趋近于切比雪夫距离。

5. 汉明距离 (Hamming Distance)

• 定义: 两个等长字符串在相同位置上不同字符的数量。
• 公式:
  $$
  d(P, Q) = \sum_{i=1}^n \delta(p_i, q_i), \quad \delta(p_i, q_i) =
  \begin{cases}
  0 & \text{如果 } p_i = q_i \
  1 & \text{如果 } p_i \neq q_i
  \end{cases}
  $$
• 应用: 用于编码理论、信息检索等。

6. 余弦相似度 (Cosine Similarity)

• 定义: 通过计算两个向量的夹角余弦值来衡量相似性。
• 公式:
  $$
  \text{cosine}(P, Q) = \frac{P \cdot Q}{|P| |Q|}
  $$
• 应用: 适用于文本分析、推荐系统等。

7. 杰卡德距离 (Jaccard Distance)

• 定义: 衡量两个集合的差异，基于交集与并集的比例。
• 公式:
  $$
  d(P, Q) = 1 - \frac{|P \cap Q|}{|P \cup Q|}
  $$
• 应用: 用于集合相似性比较，如文档相似性。

8. 马氏距离 (Mahalanobis Distance)

• 定义: 考虑数据分布的距离度量，适用于多维数据。
• 公式:
  $$
  d(P, Q) = \sqrt{(P - Q)^T S^{-1} (P - Q)}
  $$
  其中 $S$ 是协方差矩阵。
• 应用: 适用于需要考虑数据相关性的场景。

这些距离算法各有特点，选择时应根据具体问题和数据特性进行权衡。