3.2 欧氏距离与曼哈顿距离

3.2 欧氏距离与曼哈顿距离

本节导读：深入掌握欧氏距离和曼哈顿距离这两种最重要的距离度量方法，理解它们的数学原理、适用场景和计算优化，为向量检索中的距离计算提供全面的工具箱。

学习目标

• 掌握欧氏距离和曼哈顿距离的数学定义
• 理解两种距离度量的几何意义和应用差异
• 能够根据具体场景选择合适的距离度量
• 学会大规模距离计算的性能优化技巧

核心概念

距离度量的基本理论

距离度量是向量相似度计算的基础，用于量化向量之间的"差距"。在向量空间中，距离越小表示向量越相似。

核心性质：

1. 非负性：d(x,y) ≥ 0
2. 对称性：d(x,y) = d(y,x)
3. 三角不等式：d(x,z) ≤ d(x,y) + d(y,z)
4. 零等价性：d(x,y) = 0 当且仅当 x = y

欧氏距离（Euclidean Distance）

数学定义：
欧氏距离是最直观的距离度量，表示两点之间的直线距离：

d(A,B) = √Σ(ai - bi)² = √[(a1-b1)² + (a2-b2)² + ... + (an-bn)²]
​

几何意义：

• 欧氏距离对应笛卡尔坐标系中的直线距离
• 反映了向量在空间中的绝对差异
• 是最符合人类直觉的距离度量

性质分析：

• 范围：[0, +∞)
• 对异常值敏感：大差异会被平方放大
• 计算复杂度：O(n)

import numpy as np
from sklearn.metrics.pairwise import euclidean_distances

def euclidean_distance(vector1, vector2):
    """
    计算两个向量的欧氏距离
    """
    return np.linalg.norm(vector1 - vector2)

# 示例
vec1 = np.array([3.0, 4.0])
vec2 = np.array([0.0, 0.0])

distance = euclidean_distance(vec1, vec2)
print(f"欧氏距离: {distance:.4f}")  # 应该是5.0，因为3-4-5直角三角形
​

曼哈顿距离（Manhattan Distance）

数学定义：
曼哈顿距离也称为出租车距离或L1距离，表示两点在城市网格中的最短路径：

d(A,B) = Σ|ai - bi| = |a1-b1| + |a2-b2| + ... + |an-bn|
​

几何意义：

• 曼哈顿距离对应城市网格中的曼哈顿路径
• 反映了向量各维度差异的绝对值之和
• 在离散空间或有障碍物时更真实

性质分析：

• 范围：[0, +∞)
• 对异常值不敏感：绝对值不会放大差异
• 计算复杂度：O(n)

def manhattan_distance(vector1, vector2):
    """
    计算两个向量的曼哈顿距离
    """
    return np.sum(np.abs(vector1 - vector2))

# 示例
vec1 = np.array([3.0, 4.0])
vec2 = np.array([0.0, 0.0])

distance = manhattan_distance(vec1, vec2)
print(f"曼哈顿距离: {distance:.4f}")  # 应该是7.0，因为3+4=7
​

环境准备 / 前置知识

Python环境配置

# 安装必要的库
pip install numpy scikit-learn matplotlib seaborn
pip install faiss-cpu
​

核心库介绍

• numpy: 高性能数值计算库
• scikit-learn: 机器学习工具库，提供距离计算函数
• matplotlib/seaborn: 数据可视化库
• faiss: Facebook的相似度搜索库

import numpy as np
from sklearn.metrics.pairwise import euclidean_distances, manhattan_distances
from sklearn.preprocessing import normalize
import matplotlib.pyplot as plt
import seaborn as sns
import faiss
​

分步实战

步骤 1：基础距离计算与对比

实现欧氏距离和曼哈顿距离的计算，并进行对比分析。

def basic_distance_comparison():
    """
    基础距离计算对比
    """
    print("=== 基础距离计算对比 ===")
    
    # 创建示例向量
    vectors = np.array([
        [0.0, 0.0],      # 原点
        [1.0, 0.0],      # x轴上1单位
        [0.0, 1.0],      # y轴上1单位  
        [1.0, 1.0],      # 对角线上
        [3.0, 4.0],      # 3-4-5三角形
        [1.0, 1.0]       # 重复点
    ])
    
    vector_names = ['O(0,0)', 'A(1,0)', 'B(0,1)', 'C(1,1)', 'D(3,4)', 'E(1,1)']
    
    # 计算距离矩阵
    euclidean_dist_matrix = euclidean_distances(vectors)
    manhattan_dist_matrix = manhattan_distances(vectors)
    
    print("欧氏距离矩阵:")
    print(euclidean_dist_matrix)
    
    print("\n曼哈顿距离矩阵:")
    print(manhattan_dist_matrix)
    
    # 分析特定点对
    print("\n=== 特定点对分析 ===")
    point_pairs = [
        (0, 1, "O→A"),      # (0,0)→(1,0)
        (0, 2, "O→B"),      # (0,0)→(0,1)  
        (0, 3, "O→C"),      # (0,0)→(1,1)
        (1, 3, "A→C"),      # (1,0)→(1,1)
        (3, 4, "C→D")       # (1,1)→(3,4)
    ]
    
    for i, j, name in point_pairs:
        euclid_dist = euclidean_dist_matrix[i][j]
        manhattan_dist = manhattan_dist_matrix[i][j]
        
        print(f"{name}:")
        print(f"  欧氏距离: {euclid_dist:.4f}")
        print(f"  曼哈顿距离: {manhattan_dist:.4f}")
        print(f"  比例: {manhattan_dist/euclid_dist:.2f}")
    
    # 重复点测试
    print(f"\n重复点测试 (C和E):")
    print(f"欧氏距离: {euclidean_dist_matrix[3][5]:.6f}")
    print(f"曼哈顿距离: {manhattan_dist_matrix[3][5]:.6f}")
    print("结论: 相同点的两种距离都是0")

# 执行基础距离计算演示
basic_distance_comparison()
​

步骤 2：不同距离度量的可视化

通过可视化直观理解欧氏距离和曼哈顿距离的差异。

def distance_visualization():
    """
    距离度量可视化
    """
    print("=== 距离度量可视化 ===")
    
    # 创建测试点
    origin = np.array([0, 0])
    test_points = np.array([
        [1, 0], [0, 1], [1, 1], [2, 1], [1, 2], [2, 0],
        [0, 2], [3, 1], [1, 3], [2, 2], [3, 0], [0, 3]
    ])
    
    # 计算距离
    euclidean_dists = []
    manhattan_dists = []
    
    for point in test_points:
        euclid = euclidean_distance(origin, point)
        manhattan = manhattan_distance(origin, point)
        euclidean_dists.append(euclid)
        manhattan_dists.append(manhattan)
    
    # 创建等距离圈
    theta = np.linspace(0, 2*np.pi, 100)
    
    fig, (ax1, ax2, ax3) = plt.subplots(1, 3, figsize=(15, 5))
    
    # 欧氏距离可视化
    ax1.set_title('欧氏距离等值线')
    ax1.set_xlabel('X')
    ax1.set_ylabel('Y')
    
    # 绘制欧氏距离等值线
    for r in [1, 2, 3]:
        circle_x = r * np.cos(theta)
        circle_y = r * np.sin(theta)
        ax1.plot(circle_x, circle_y, 'b-', alpha=0.5, label=f'd={r}')
    
    # 绘制测试点
    ax1.scatter(test_points[:, 0], test_points[:, 1], c='red', s=50)
    ax1.scatter(0, 0, c='black', s=100, marker='o')
    ax1.grid(True, alpha=0.3)
    ax1.legend()
    ax1.set_aspect('equal')
    
    # 曼哈顿距离可视化
    ax2.set_title('曼哈顿距离等值线')
    ax2.set_xlabel('X')
    ax2.set_ylabel('Y')
    
    # 绘制曼哈顿距离等值线（菱形）
    for d in [1, 2, 3]:
        # 曼哈顿距离等值线是菱形
        diamond_x = np.array([d, 0, -d, 0, d])
        diamond_y = np.array([0, d, 0, -d, 0])
        ax2.plot(diamond_x, diamond_y, 'g-', alpha=0.5, label=f'd={d}')
    
    # 绘制测试点
    ax2.scatter(test_points[:, 0], test_points[:, 1], c='red', s=50)
    ax2.scatter(0, 0, c='black', s=100, marker='o')
    ax2.grid(True, alpha=0.3)
    ax2.legend()
    ax2.set_aspect('equal')
    
    # 对比分析
    ax3.set_title('距离对比')
    ax3.plot(euclidean_dists, manhattan_dists, 'o-', markersize=6)
    ax3.set_xlabel('欧氏距离')
    ax3.set_ylabel('曼哈顿距离')
    ax3.grid(True, alpha=0.3)
    
    plt.tight_layout()
    plt.show()
    
    print("可视化完成：")
    print("- 左图：欧氏距离等值线为圆形")
    print("- 中图：曼哈顿距离等值线为菱形")
    print("- 右图：两种距离的关系曲线")

# 执行可视化演示
try:
    distance_visualization()
except:
    print("可视化环境不可用，跳过可视化演示")
​

步骤 3：Lp范数族与距离度量

介绍更一般的Lp范数族，包括欧氏距离（L2）和曼哈顿距离（L1）作为特例。

def lp_norm_distance():
    """
    Lp范数距离计算
    """
    print("=== Lp范数距离 ===")
    
    # Lp范数定义
    def lp_norm(vector, p):
        """
        计算Lp范数
        """
        return np.power(np.sum(np.abs(vector) ** p), 1/p)
    
    def lp_distance(vector1, vector2, p):
        """
        计算Lp距离
        """
        diff = vector1 - vector2
        return lp_norm(diff, p)
    
    # 测试向量
    vec1 = np.array([1.0, 2.0, 3.0])
    vec2 = np.array([2.0, 3.0, 5.0])
    
    # 计算不同p值的距离
    p_values = [0.5, 1, 2, 3, 4, np.inf]
    
    print(f"向量1: {vec1}")
    print(f"向量2: {vec2}")
    print("\n不同Lp范数的距离:")
    
    for p in p_values:
        if p == np.inf:
            # L∞范数是最大值
            distance = np.max(np.abs(vec1 - vec2))
            print(f"L∞距离: {distance:.4f} (最大值范数)")
        else:
            distance = lp_distance(vec1, vec2, p)
            print(f"L{p}距离: {distance:.4f}")
    
    # 特殊情况说明
    print("\n=== 特殊情况说明 ===")
    print("L1: 曼哈顿距离 - 各维度绝对值之和")
    print("L2: 欧氏距离 - 各维度平方和的平方根")
    print("L∞: 切比雪夫距离 - 各维度最大值差")
    
    # 应用场景
    print("\n=== 不同p值的适用场景 ===")
    scenarios = [
        (0.5, "强调小差异，惩罚大差异", "异常检测"),
        (1, "线性差异，对异常值不敏感", "城市导航、图像处理"),
        (2, "欧氏几何，强调大差异", "大多数机器学习场景"),
        (3, "更强调大差异", "特定优化问题"),
        (np.inf, "只关注最大差异", "安全性相关、质量控制")
    ]
    
    for p, description, application in scenarios:
        print(f"L{p if p != np.inf else '∞'}: {description} - {application}")

# 执行Lp范数演示
lp_norm_distance()
​

步骤 4：大规模距离计算优化

实现高效的大规模距离计算，包括向量化和并行计算。

def optimized_distance_calculation():
    """
    优化的大规模距离计算
    """
    print("=== 大规模距离计算优化 ===")
    
    # 创建大规模数据
    n_vectors = 5000
    dimension = 128
    vectors = np.random.random((n_vectors, dimension)).astype('float32')
    
    print(f"创建 {n_vectors} 个 {dimension} 维向量")
    
    # 1. 暴力计算（基准）
    print("\n1. 暴力计算基准")
    import time
    
    start_time = time.time()
    euclidean_matrix_full = euclidean_distances(vectors)
    brute_force_time = time.time() - start_time
    
    print(f"暴力计算时间: {brute_force_time:.2f}s")
    print(f"矩阵大小: {euclidean_matrix_full.shape}")
    
    # 2. 采样计算（近似）
    print("\n2. 采样计算（近似方法）")
    n_samples = 100
    
    start_time = time.time()
    sampled_vectors = vectors[:n_samples]
    euclidean_matrix_sampled = euclidean_distances(sampled_vectors)
    sampled_time = time.time() - start_time
    
    print(f"采样计算时间: {sampled_time:.4f}s")
    print(f"采样向量数: {n_samples}")
    print(f"加速比: {brute_force_time/sampled_time:.2f}x")
    
    # 3. 分块计算
    print("\n3. 分块计算（内存优化）")
    
    def chunked_distance_calculation(vectors, chunk_size=1000):
        """
        分块计算距离矩阵
        """
        n = len(vectors)
        result_matrix = np.zeros((n, n))
        
        for i in range(0, n, chunk_size):
            for j in range(0, n, chunk_size):
                chunk_i = vectors[i:i+chunk_size]
                chunk_j = vectors[j:j+chunk_size]
                
                chunk_distances = euclidean_distances(chunk_i, chunk_j)
                
                # 存储结果
                i_end = min(i + chunk_size, n)
                j_end = min(j + chunk_size, n)
                result_matrix[i:i_end, j:j_end] = chunk_distances
        
        return result_matrix
    
    start_time = time.time()
    euclidean_matrix_chunked = chunked_distance_calculation(vectors, chunk_size=1000)
    chunked_time = time.time() - start_time
    
    print(f"分块计算时间: {chunked_time:.2f}s")
    print(f"分块大小: 1000x1000")
    
    # 4. GPU加速（如果可用）
    print("\n4. GPU加速（FAISS）")
    try:
        # 使用FAISS进行GPU加速
        gpu_res = faiss.StandardGpuResources()
        index = faiss.IndexFlatL2(dimension)
        gpu_index = faiss.index_cpu_to_gpu(gpu_res, 0, index)
        
        start_time = time.time()
        gpu_index.add(vectors)
        gpu_distances, gpu_indices = gpu_index.search(vectors, n_vectors)
        gpu_time = time.time() - start_time
        
        print(f"GPU计算时间: {gpu_time:.2f}s")
        print(f"GPU加速比: {brute_force_time/gpu_time:.2f}x")
        
    except Exception as e:
        print(f"GPU不可用: {e}")
    
    # 5. 稀疏矩阵优化
    print("\n5. 稀疏矩阵优化")
    
    # 创建稀疏向量
    from scipy.sparse import csr_matrix
    sparse_vectors = csr_matrix(vectors)
    
    start_time = time.time()
    sparse_distances = euclidean_distances(sparse_vectors[:100])  # 只计算前100个
    sparse_time = time.time() - start_time
    
    print(f"稀疏矩阵计算时间（100x100）: {sparse_time:.4f}s")
    
    # 性能对比
    print("\n=== 性能对比总结 ===")
    methods = ['暴力计算', '采样计算', '分块计算', '稀疏计算']
    times = [brute_force_time, sampled_time, chunked_time, sparse_time]
    
    for method, time_val in zip(methods, times):
        print(f"{method}: {time_val:.2f}s")
    
    return {
        'brute_force': brute_force_time,
        'sampled': sampled_time,
        'chunked': chunked_time,
        'sparse': sparse_time
    }

# 执行优化演示
optimized_distance_calculation()
​

常见问题 FAQ

Q1：欧氏距离和曼哈顿距离的主要区别是什么？

A：欧氏距离和曼哈顿距离的主要区别：

1. 数学公式：

   • 欧氏：d = √Σ(ai-bi)²
   • 曼哈顿：d = Σ|ai-bi|

2. 几何形状：

   • 欧氏：圆形等值线
   • 曼哈顿：菱形等值线

3. 异常值处理：

   • 欧氏：大差异被平方放大，对异常值敏感
   • 曼哈顿：绝对值不放大，对异常值不敏感

4. 计算开销：

   • 欧氏：需要开方，计算稍复杂
   • 曼哈顿：只有绝对值和，计算简单

Q2：如何选择合适的距离度量？

A：选择距离度量需要考虑：

1. 数据特征：

   • 连续数据：欧氏距离更合适
   • 离散数据或有噪声：曼哈顿距离更鲁棒
   • 高维数据：考虑降维后再用欧氏距离

2. 应用场景：

   • 计算机视觉：欧氏距离（特征向量）
   • 文本相似度：余弦相似度或曼哈顿距离
   • 推荐系统：欧氏距离或余弦相似度

3. 性能考虑：

   • 实时要求高：曼哈顿距离计算更快
   • 精度要求高：欧氏距离通常更准确

Q3：Lp范数族中的不同p值有什么特点？

A：Lp范数族中不同p值的特点：

1. L1（曼哈顿）：

   • 最直观的城市网格距离
   • 对异常值不敏感
   • 稀疏性保持

2. L2（欧氏）：

   • 最符合几何直觉
   • 对异常值敏感
   • 大多数机器学习默认选择

3. L∞（切比雪夫）：

   • 关注最大差异
   • 适用于安全边界
   • 最坏情况分析

4. 其他p值：

   • p < 1：强调小差异
   • p > 2：强调大差异

Q4：高维空间中的距离计算有什么挑战？

A：高维空间中的距离计算挑战：

1. 维度灾难：

   • 距离都趋向于相同
   • 邻居定义变得模糊

2. 计算复杂度：

   • O(n²)的内存需求
   • O(n²d)的时间复杂度

3. 解决方案：

   • 降维技术（PCA、t-SNE）
   • 近似算法（HNSW、IVF）
   • 采样和分块计算

最佳实践与避坑

实践1：距离度量的预处理

标准化流程：

def preprocess_for_distance_calculation(vectors):
    """
    距离计算前的标准化处理
    """
    import numpy as np
    from sklearn.preprocessing import StandardScaler, MinMaxScaler
    
    # 1. 检查数据分布
    print(f"原始数据范围: [{vectors.min():.4f}, {vectors.max():.4f}]")
    print(f"均值: {vectors.mean():.4f}, 标准差: {vectors.std():.4f}")
    
    # 2. 标准化（z-score）
    scaler = StandardScaler()
    standardized = scaler.fit_transform(vectors)
    print(f"标准化后范围: [{standardized.min():.4f}, {standardized.max():.4f}]")
    
    # 3. 归一化（0-1）
    normalizer = MinMaxScaler()
    normalized = normalizer.fit_transform(vectors)
    print(f"归一化后范围: [{normalized.min():.4f}, {normalized.max():.4f}]")
    
    return standardized, normalized

# 使用示例
vectors = np.random.random((1000, 10))
std_vec, norm_vec = preprocess_for_distance_calculation(vectors)
​

实践2：内存优化的大规模距离计算

内存优化策略：

def memory_efficient_distance(vectors, distance_metric='euclidean', chunk_size=500):
    """
    内存高效的大规模距离计算
    """
    n_vectors = len(vectors)
    result = np.zeros((n_vectors, n_vectors))
    
    # 使用对称性优化
    for i in range(0, n_vectors, chunk_size):
        for j in range(i, n_vectors, chunk_size):
            chunk_i = vectors[i:i+chunk_size]
            chunk_j = vectors[j:j+chunk_size]
            
            if distance_metric == 'euclidean':
                dist_matrix = euclidean_distances(chunk_i, chunk_j)
            elif distance_metric == 'manhattan':
                dist_matrix = manhattan_distances(chunk_i, chunk_j)
            
            result[i:i+chunk_size, j:j+chunk_size] = dist_matrix
            
            # 利用对称性
            if i != j:
                result[j:j+chunk_size, i:i+chunk_size] = dist_matrix.T
    
    return result

# 使用示例
vectors = np.random.random((2000, 64))  # 2000x64维向量
distance_matrix = memory_efficient_distance(vectors, chunk_size=500)
print(f"距离矩阵形状: {distance_matrix.shape}")
​

坑点1：忽视数据尺度差异

问题：不同维度的数据尺度差异影响距离计算

# 错误示例：未处理尺度差异
vectors = np.array([
    [1.0, 1000.0],    # 第二个维度数值很大
    [1.1, 1001.0],
    [10.0, 2000.0]    # 第一个维度也大
])

# 欧氏距离会被大维度主导
euclid_dist = euclidean_distance(vectors[0], vectors[1])
print(f"未标准化欧氏距离: {euclid_dist:.4f}")

# 正确做法：先标准化
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
normalized = scaler.fit_transform(vectors)
euclid_norm = euclidean_distance(normalized[0], normalized[1])
print(f"标准化后欧氏距离: {euclid_norm:.4f}")
​

坑点2：高维空间的距离计算效率问题

问题：高维距离矩阵占用大量内存

# 错误示例：直接计算大矩阵
high_dim_vectors = np.random.random((10000, 1000))  # 10Kx1000维
# distance_matrix = euclidean_distances(high_dim_vectors)  # 内存不足！

# 正确做法：分批处理或使用近似算法
def batch_distance_calculation(vectors, batch_size=100):
    """分批计算距离矩阵"""
    n = len(vectors)
    result = np.zeros((n, n))
    
    for i in range(0, n, batch_size):
        for j in range(0, n, batch_size):
            batch_i = vectors[i:i+batch_size]
            batch_j = vectors[j:j+batch_size]
            
            dist = euclidean_distances(batch_i, batch_j)
            result[i:i+batch_size, j:j+batch_size] = dist
    
    return result
​

本节小结

通过本节的学习，我们深入理解了欧氏距离和曼哈顿距离这两种重要的距离度量方法。主要收获包括：

1. 理论基础：掌握了两种距离的数学定义、几何意义和适用场景
2. Lp范数族：理解了更一般的距离度量框架，能够根据p值调整距离特性
3. 工程实践：学会了大规模距离计算的性能优化和内存管理
4. 应用选择：能够根据具体场景和数据特征选择合适的距离度量

距离度量是向量检索的基础，正确选择和优化距离计算方法对于构建高效的搜索系统至关重要。下一节我们将学习特殊的距离度量方法，进一步丰富我们的距离度量工具箱。

延伸阅读

• 官方文档：scikit-learn距离计算模块
• 相关章节：本教程 3.3 节 特殊距离度量
• 推荐阅读：《模式识别与机器学习》
• 进阶学习：流形学习和距离度量的最新研究

关键词：AI搜索技术内幕, 欧氏距离, 曼哈顿距离, 向量检索, 距离度量, Lp范数, 机器学习, 实战
难度：进阶
预计阅读：40 分钟