别再只用欧氏距离了！用Python手写曼哈顿距离，搞定KNN和K-Means中的特征选择

实战指南用曼哈顿距离优化KNN与K-Means的特征选择当我们在处理一个房价预测项目时发现数据中存在大量异常值和不同量纲的特征。使用传统的欧氏距离计算相似度时模型表现总是不尽如人意。这时曼哈顿距离Manhattan Distance可能就是你需要的解决方案。与欧氏距离不同曼哈顿距离对异常值更具鲁棒性在特征尺度差异大的情况下表现更稳定。本文将带你深入理解这一距离度量方式并展示如何在Python中实现它来提升KNN和K-Means算法的实际效果。1. 为什么曼哈顿距离在机器学习中很重要曼哈顿距离又称出租车距离或L1距离得名于纽约曼哈顿区规整的街道布局。想象一辆出租车在城市中行驶它不能穿过建筑物直线到达目的地只能沿着街道直角转弯前进。这种现实世界的运动方式正是曼哈顿距离的直观体现。在机器学习领域距离度量是许多算法的核心。KNNK最近邻分类器依靠距离来确定最相似的样本K-Means聚类则用距离来分配数据点到最近的簇中心。当数据具有以下特点时曼哈顿距离往往比欧氏距离更合适特征尺度差异大比如同时包含年龄0-100和收入0-1,000,000的特征存在异常值某些数据点远偏离正常范围高维稀疏数据如文本处理中的词向量提示欧氏距离对大幅度的单一维度差异非常敏感而曼哈顿距离对各维度的差异处理更加均衡。下表对比了两种距离度量的关键特性特性欧氏距离(L2)曼哈顿距离(L1)计算公式√(Σ(xi-yi)²)Σ对异常值的敏感度高低计算效率相对较低涉及平方和开方高仅绝对值求和适用场景各维度相关性强的数据维度相对独立的数据几何形状圆形菱形2. 从零实现曼哈顿距离理解一个概念最好的方式就是自己实现它。下面我们用Python编写曼哈顿距离的计算函数并对比NumPy内置方法的性能。def manhattan_distance_naive(point1, point2): 基础版曼哈顿距离实现 :param point1: 第一个点的坐标如[1, 2, 3] :param point2: 第二个点的坐标需与point1维度相同 :return: 两点间的曼哈顿距离 if len(point1) ! len(point2): raise ValueError(点的维度必须相同) distance 0 for p1, p2 in zip(point1, point2): distance abs(p1 - p2) return distance # 使用NumPy优化版本 import numpy as np def manhattan_distance_numpy(point1, point2): NumPy优化的曼哈顿距离实现 point1 np.array(point1) point2 np.array(point2) return np.sum(np.abs(point1 - point2))让我们测试这两个函数的性能和结果# 测试数据 p1 [1.5, 2.3, 4.7] p2 [0.8, 3.2, 5.1] # 计算结果 print(f基础版结果: {manhattan_distance_naive(p1, p2)}) print(fNumPy版结果: {manhattan_distance_numpy(p1, p2)}) # 性能对比 %timeit manhattan_distance_naive(p1, p2) %timeit manhattan_distance_numpy(p1, p2)在真实项目中我们通常会处理更大的数据集。下面是一个向量化计算的示例可以同时计算多个点对之间的距离def batch_manhattan_distance(points1, points2): 批量计算曼哈顿距离 :param points1: 第一个点集形状(n_samples, n_features) :param points2: 第二个点集形状(m_samples, n_features) :return: 距离矩阵形状(n_samples, m_samples) return np.sum(np.abs(points1[:, np.newaxis] - points2), axis2)3. 在KNN算法中应用曼哈顿距离K最近邻(KNN)算法是一种简单而强大的分类和回归方法。默认情况下scikit-learn中的KNeighborsClassifier使用欧氏距离但我们可以轻松更改为曼哈顿距离。3.1 基础实现from sklearn.neighbors import KNeighborsClassifier from sklearn.datasets import load_iris from sklearn.model_selection import train_test_split from sklearn.preprocessing import StandardScaler # 加载数据 iris load_iris() X, y iris.data, iris.target # 分割数据集 X_train, X_test, y_train, y_test train_test_split(X, y, test_size0.3, random_state42) # 特征标准化 scaler StandardScaler() X_train_scaled scaler.fit_transform(X_train) X_test_scaled scaler.transform(X_test) # 创建KNN分类器使用曼哈顿距离 knn_manhattan KNeighborsClassifier(n_neighbors5, metricmanhattan) knn_manhattan.fit(X_train_scaled, y_train) # 评估模型 accuracy knn_manhattan.score(X_test_scaled, y_test) print(f使用曼哈顿距离的KNN准确率: {accuracy:.2f})3.2 距离度量对比实验为了展示不同距离度量的影响我们进行一个对比实验from sklearn.neighbors import KNeighborsClassifier import matplotlib.pyplot as plt # 测试不同的距离度量 metrics [euclidean, manhattan, chebyshev] results [] for metric in metrics: knn KNeighborsClassifier(n_neighbors5, metricmetric) knn.fit(X_train_scaled, y_train) acc knn.score(X_test_scaled, y_test) results.append(acc) # 可视化结果 plt.figure(figsize(8, 4)) plt.bar(metrics, results) plt.title(KNN不同距离度量准确率比较) plt.ylabel(准确率) plt.ylim(0.9, 1.0) plt.show()3.3 特征权重调整曼哈顿距离的一个优势是可以结合特征重要性进行加权计算# 定义特征权重假设来自领域知识或特征重要性分析 feature_weights [0.1, 0.3, 0.4, 0.2] # 自定义加权曼哈顿距离 def weighted_manhattan(u, v, weightsfeature_weights): return np.sum(np.abs(u - v) * weights) # 创建使用自定义距离的KNN knn_weighted KNeighborsClassifier( n_neighbors5, metricweighted_manhattan ) knn_weighted.fit(X_train_scaled, y_train) weighted_acc knn_weighted.score(X_test_scaled, y_test) print(f加权曼哈顿距离准确率: {weighted_acc:.2f})4. 优化K-Means聚类的距离选择K-Means算法默认也使用欧氏距离但我们可以通过自定义距离度量来使用曼哈顿距离这被称为K-Medians算法。4.1 基础实现from sklearn.cluster import KMeans from sklearn.metrics import silhouette_score # 使用欧氏距离的K-Means kmeans_euclidean KMeans(n_clusters3, random_state42) kmeans_euclidean.fit(X_train_scaled) euclidean_score silhouette_score(X_train_scaled, kmeans_euclidean.labels_) # 使用曼哈顿距离的K-Medians # 注意scikit-learn的KMeans不支持直接更改距离度量 # 我们需要使用更通用的方法或第三方实现 # 方法一使用K-Medoids算法PAM from sklearn_extra.cluster import KMedoids kmedoids KMedoids(n_clusters3, metricmanhattan, random_state42) kmedoids.fit(X_train_scaled) manhattan_score silhouette_score(X_train_scaled, kmedoids.labels_) print(f欧氏距离轮廓系数: {euclidean_score:.2f}) print(f曼哈顿距离轮廓系数: {manhattan_score:.2f})4.2 距离度量对聚类结果的影响让我们可视化不同距离度量下的聚类结果import matplotlib.pyplot as plt from sklearn.decomposition import PCA # 降维可视化 pca PCA(n_components2) X_pca pca.fit_transform(X_train_scaled) # 绘制欧氏距离结果 plt.figure(figsize(12, 5)) plt.subplot(1, 2, 1) plt.scatter(X_pca[:, 0], X_pca[:, 1], ckmeans_euclidean.labels_) plt.title(K-Means with Euclidean Distance) # 绘制曼哈顿距离结果 plt.subplot(1, 2, 2) plt.scatter(X_pca[:, 0], X_pca[:, 1], ckmedoids.labels_) plt.title(K-Medoids with Manhattan Distance) plt.show()4.3 处理混合类型特征在实际项目中我们经常遇到同时包含数值型和分类型特征的数据。这时可以组合不同的距离度量from sklearn.compose import ColumnTransformer from sklearn.preprocessing import OneHotEncoder from sklearn.pipeline import Pipeline from sklearn.neighbors import KNeighborsClassifier from sklearn.metrics.pairwise import manhattan_distances # 假设我们有一个包含数值和分类特征的数据集 # 这里使用iris数据集模拟将前两列视为数值后两列视为分类仅为示例 X_mixed X.copy() X_mixed[:, 2:] np.round(X_mixed[:, 2:]) # 模拟分类特征 # 定义不同的预处理 preprocessor ColumnTransformer( transformers[ (num, StandardScaler(), [0, 1]), # 数值特征标准化 (cat, OneHotEncoder(), [2, 3]) # 分类特征独热编码 ]) # 自定义混合距离度量 def mixed_distance(x, y): # 前两个数值特征使用曼哈顿距离 num_dist np.sum(np.abs(x[:2] - y[:2])) # 后两个分类特征使用汉明距离匹配则为0不匹配为1 cat_dist np.sum(x[2:] ! y[2:]) return num_dist cat_dist # 创建处理管道 pipeline Pipeline([ (preprocessor, preprocessor), (classifier, KNeighborsClassifier(n_neighbors5, metricmixed_distance)) ]) # 由于自定义距离度量我们需要预处理后再拟合 X_train_mixed, X_test_mixed, y_train_mixed, y_test_mixed train_test_split( X_mixed, y, test_size0.3, random_state42) # 注意需要先transform训练数据因为自定义距离函数无法在pipeline中直接使用 X_train_preprocessed preprocessor.fit_transform(X_train_mixed) X_test_preprocessed preprocessor.transform(X_test_mixed) # 创建使用混合距离的KNN knn_mixed KNeighborsClassifier(n_neighbors5, metricmixed_distance) knn_mixed.fit(X_train_preprocessed, y_train_mixed) mixed_acc knn_mixed.score(X_test_preprocessed, y_test_mixed) print(f混合距离KNN准确率: {mixed_acc:.2f})5. 高级应用与性能优化5.1 近似最近邻搜索当数据量很大时精确的最近邻搜索计算成本很高。我们可以使用近似算法加速曼哈顿距离下的邻居搜索from sklearn.neighbors import NearestNeighbors from sklearn.random_projection import SparseRandomProjection # 大数据集示例使用所有iris数据作为示例 X_large np.vstack([X] * 100) # 模拟大数据集 y_large np.hstack([y] * 100) # 使用随机投影降维 transformer SparseRandomProjection(n_components10, random_state42) X_projected transformer.fit_transform(X_large) # 构建近似最近邻模型 nbrs NearestNeighbors(n_neighbors5, algorithmauto, metricmanhattan) nbrs.fit(X_projected) # 查询最近邻 distances, indices nbrs.kneighbors(X_projected[:5]) # 查询前5个样本的邻居 print(近似最近邻索引:\n, indices)5.2 GPU加速计算对于超大规模数据可以使用GPU加速曼哈顿距离计算# 使用RAPIDS库需要NVIDIA GPU try: import cupy as cp from cuml.neighbors import NearestNeighbors as cuNearestNeighbors # 将数据转移到GPU X_gpu cp.array(X_train_scaled) # 创建GPU加速的最近邻模型 nn_gpu cuNearestNeighbors(n_neighbors5, metricmanhattan) nn_gpu.fit(X_gpu) # 查询最近邻 distances_gpu, indices_gpu nn_gpu.kneighbors(X_gpu[:5]) print(GPU加速的最近邻索引:\n, indices_gpu.get()) except ImportError: print(RAPIDS库未安装此示例需要NVIDIA GPU支持)5.3 距离矩阵缓存当需要重复使用相同的距离计算时可以预先计算并缓存距离矩阵from sklearn.metrics.pairwise import manhattan_distances import joblib # 计算并缓存距离矩阵 distance_matrix manhattan_distances(X_train_scaled) # 保存到磁盘 joblib.dump(distance_matrix, manhattan_distances.joblib) # 后续使用 cached_distances joblib.load(manhattan_distances.joblib) # 自定义KNN实现使用缓存距离 class CachedKNN: def __init__(self, n_neighbors5): self.n_neighbors n_neighbors def fit(self, X, y): self.X X self.y y return self def predict(self, X_test): # 计算测试样本到训练集的距离 test_distances manhattan_distances(X_test, self.X) # 找到最近的k个邻居 knn_indices np.argsort(test_distances, axis1)[:, :self.n_neighbors] # 获取邻居的标签 knn_labels self.y[knn_indices] # 多数投票 from scipy.stats import mode predictions, _ mode(knn_labels, axis1) return predictions.ravel() # 使用缓存距离的KNN cached_knn CachedKNN(n_neighbors5) cached_knn.fit(X_train_scaled, y_train) cached_acc np.mean(cached_knn.predict(X_test_scaled) y_test) print(f使用缓存距离的KNN准确率: {cached_acc:.2f})