KNN中不同距离度量对比和介绍

deephub

AI方向文章，看头像就知道，这里都是"干"货

k近邻算法KNN是一种简单而强大的算法，可用于分类和回归任务。他实现简单，主要依赖不同的距离度量来判断向量间的区别，但是有很多距离度量可以使用，所以本文演示了KNN与三种不同距离度量(Euclidean、Minkowski和Manhattan)的使用。

KNN算法概述

KNN是一种惰性、基于实例的算法。它的工作原理是将新样本的特征与数据集中现有样本的特征进行比较。然后算法选择最接近的k个样本，其中k是用户定义的参数。新样本的输出是基于“k”最近样本的多数类(用于分类)或平均值(用于回归)确定的。

有很多距离度量的算法，我们这里选取3个最常用度量的算法来进行演示：

1、欧氏距离 Euclidean Distance

def euclidean_distance(x1, x2): 
    return math.sqrt(np.sum((x1 - x2)**2))

euclidean_distance函数计算多维空间中两点(x1和x2)之间的欧氏距离，函数的工作原理如下:

从x1元素中减去x2，得到对应坐标之间的差值。
使用**2运算将差值平方。
使用np.sum()对差的平方求和。

使用math.sqrt()取总和的平方根。
欧几里得距离是欧几里得空间中两点之间的直线距离。通过计算欧几里得距离，可以识别给定样本的最近邻居，并根据邻居的多数类(用于分类)或平均值(用于回归)进行预测。在处理连续的实值特征时，使用欧几里得距离很有帮助，因为它提供了一种直观的相似性度量。

2、曼哈顿距离 Manhattan Distance

两点坐标的绝对差值之和。

def manhattan_distance(x1, x2): 
    return np.sum(np.abs(x1 - x2))

Manhattan _distance函数计算多维空间中两点(x1和x2)之间的曼哈顿距离，函数的工作原理如下:

用np计算x1和x2对应坐标的绝对差值。Abs (x1 - x2)
使用np.sum()对绝对差进行求和。

曼哈顿距离，也称为L1距离或出租车距离，是两点坐标的绝对差值之和。它代表了当运动被限制为网格状结构时，点之间的最短路径，类似于在城市街道上行驶的出租车。
在数据特征具有不同尺度的情况下，或者当问题域的网格状结构使其成为更合适的相似性度量时，使用曼哈顿距离可能会有所帮助。曼哈顿距离可以根据样本的特征来衡量样本之间的相似性或差异性。
与欧几里得距离相比，曼哈顿距离对异常值的敏感性较低，因为它没有对差异进行平方。这可以使它更适合于某些数据集或异常值的存在可能对模型的性能产生重大影响的问题。

3、闵可夫斯基距离 Minkowski Distance
它是欧几里得距离和曼哈顿距离的一般化的表现形式，使用p进行参数化。当p=2时，它变成欧氏距离，当p=1时，它变成曼哈顿距离。

def minkowski_distance(x1, x2, p): 
    return np.power(np.sum(np.power(np.abs(x1 - x2), p)), 1/p)

minkowski_distance函数计算多维空间中两点(x1和x2)之间的闵可夫斯基距离。
当你想要控制单个特征的差异对整体距离的影响时，使用闵可夫斯基距离会很有帮助。通过改变p值，可以调整距离度量对特征值或大或小差异的灵敏度，使其更适合特定的问题域或数据集。
闵可夫斯基距离可以根据样本的特征来衡量样本之间的相似性或不相似性。该算法通过计算适当p值的闵可夫斯基距离，识别出给定样本的最近邻居，并根据邻居的多数类(用于分类)或平均值(用于回归)进行预测。
KNN 算法的代码实现
因为KNN算法的原理很简单，所以我们这里直接使用Python实现，这样也可以对算法有一个更好的理解：

def knn_euclidean_distance(X_train, y_train, X_test, k): 
 # List to store the predicted labels for the test set 
    y_pred = [] 
 # Iterate over each point in the test set 
 for i in range(len(X_test)): 
        distances = [] 
 # Iterate over each point in the training set 
 for j in range(len(X_train)): 
 # Calculate the distance between the two points using the Euclidean distance metric 
            dist = euclidean_distance(X_test[i], X_train[j]) 
            distances.append((dist, y_train[j])) 
 # Sort the distances list by distance (ascending order) 
        distances.sort() 
 # Get the k nearest neighbors 
        neighbors = distances[:k] 
 # Count the votes for each class 
        counts = {} 
 for neighbor in neighbors: 
            label = neighbor[1] 
 if label in counts: 
                counts[label] += 1 
 else: 
                counts[label] = 1 
 # Get the class with the most votes 
        max_count = max(counts, key=counts.get) 
        y_pred.append(max_count) 
 return y_pred
这个' knn_euclidean_distance '函数对于解决分类问题很有用，因为它可以根据' k '个最近邻居中的大多数类进行预测。该函数使用欧几里得距离作为相似性度量，可以识别测试集中每个数据点的最近邻居，并相应地预测它们的标签。我们实现的代码提供了一种显式的方法来计算距离、选择邻居，并根据邻居的投票做出预测。
在使用曼哈顿距离时，KNN算法与欧氏距离保持一致，只需要将距离计算函数euclidean_distance修改为manhattan_distance。而闵可夫斯基距离则需要多加一个参数p，实现代码如下：
def knn_minkowski_distance(X_train, y_train, X_test, k, p): 
 # List to store the predicted labels for the test set 
    y_pred = [] 
 # Iterate over each point in the test set 
 for i in range(len(X_test)): 
        distances = [] 
 # Iterate over each point in the training set 
 for j in range(len(X_train)): 
 # Calculate the distance between the two points using the Minkowski distance metric 
            dist = minkowski_distance(X_test[i], X_train[j], p) 
            distances.append((dist, y_train[j])) 
 # Sort the distances list by distance (ascending order) 
        distances.sort() 
 # Get the k nearest neighbors 
        neighbors = distances[:k] 
 # Count the votes for each class 
        counts = {} 
 for neighbor in neighbors: 
            label = neighbor[1] 
 if label in counts: 
                counts[label] += 1 
 else: 
                counts[label] = 1 
 # Get the class with the most votes 
        max_count = max(counts, key=counts.get) 
        y_pred.append(max_count) 
 return y_pred

距离度量对比

我使用的数据集是乳腺癌数据集，可以在kaggle上直接下载
这个数据集是机器学习和数据挖掘中广泛使用的基准数据集，用于二元分类任务。它是由威廉·h·沃尔伯格(William H. Wolberg)博士及其合作者在20世纪90年代从麦迪逊的威斯康星大学医院收集的。该数据集可通过UCI机器学习存储库公开获取。
Breast Cancer Wisconsin数据集包含569个实例，每个实例有32个属性。这些属性是:
ID number:每个样本的唯一标识符。
Diagnosis:目标变量有两个可能的值——“M”(恶性)和“B”(良性)。
剩下的是30个从乳腺肿块的细针抽吸(FNA)的数字化图像中计算出来的特征。它们描述了图像中细胞核的特征。对每个细胞核计算每个特征，然后求平均值，得到10个实值特征:

Radius:从中心到周边点的平均距离。
Texture:灰度值的标准偏差。
Perimeter:细胞核的周长。
Area:细胞核的面积。
Smoothness:半径长度的局部变化。
Compactness:周长²/面积- 1.0。
Concavity:轮廓中凹部分的严重程度。
Concave points:轮廓的凹部分的数目。
Symmetry:细胞核的对称性。
Fractal dimension:“Coastline approximation”- 1

对每张图像计算这十个特征的平均值、标准误差和最小或最大值(三个最大值的平均值)，总共得到30个特征。数据集不包含任何缺失的属性值。

由于数据集包含30个特征，我们需要对数据集进行特征选择。这种方法的主要目的是通过选择与目标变量具有强线性关系的较小的特征子集来降低数据集的维数。通过选择高相关性的特征，目的是保持模型的预测能力，同时减少使用的特征数量，潜在地提高模型的性能和可解释性。这里需要注意的是，该方法只考虑特征与目标变量之间的线性关系，如果底层关系是非线性的，或者特征之间存在重要的交互作用，则该方法可能无效。

读取数据并计算相关系数：

df = pd.read_csv('/kaggle/input/breast-cancer-wisconsin-data/data.csv') 
corr = df.corr() 
corr_threshold = 0.6 
selected_features = corr.index[np.abs(corr['diagnosis']) >= corr_threshold] 
new_cancer_data = df[selected_features]

训练代码：

X_train_np = np.array(X_train)  
X_test_np = np.array(X_test) 
# Convert y_train and y_test to numpy arrays 
y_train_np = np.array(y_train) 
y_test_np = np.array(y_test) 
k_values = list(range(1, 15)) 
accuracies = [] 
for k in k_values: 
    y_pred = knn_euclidean_distance(X_train_np, y_train_np, X_test_np, k) 
    accuracy = accuracy_score(y_test_np, y_pred) 
    accuracies.append(accuracy) 
# Create a data frame to store k values and accuracies 
results_df = pd.DataFrame({'k': k_values, 'Accuracy': accuracies}) 
# Create the interactive plot using Plotly 
fig = px.line(results_df, x='k', y='Accuracy', title='KNN Accuracy for Different k Values', labels={'k': 'k', 'Accuracy': 'Accuracy'}) 
fig.show() 
# Get the best k value 
best_k = k_values[accuracies.index(max(accuracies))] 
best_accuracy = max(accuracies) 
print("Best k value is:", best_k , "where accuracy is:" ,best_accuracy)

上面代码使用欧几里得距离将KNN算法应用于分类问题，同时改变邻居的数量(k)以找到最高精度的最佳k值。它使用训练集(X_train_np和y_train_np)来训练模型，使用测试集(X_test_np和y_test_np)来进行预测和评估模型的性能。

k是KNN算法的一个超参数，选择正确的k值对于实现最佳模型性能至关重要，因为k值太小可能导致过拟合，而k值太大可能导致欠拟合。通过可视化k值与其对应的精度之间的关系，可以深入了解模型的性能，并为问题选择最合适的k值。

闵可夫斯基距离的代码修改如下:

# Run the KNN algorithm on the test set for different k and p values 
k_values = list(range(1, 15)) 
p_values = list(range(1, 6)) 
results = [] 
for k in k_values: 
 for p in p_values: 
        y_pred = knn_minkowski_distance(X_train_np, y_train_np, X_test_np, k, p) 
        accuracy = accuracy_score(y_test_np, y_pred) 
        results.append((k, p, accuracy)) 
# Create a data frame to store k, p values, and accuracies 
results_df = pd.DataFrame(results, columns=['k', 'p', 'Accuracy']) 
# Create the 3D plot using Plotly 
fig = go.Figure(data=[go.Scatter3d( 
    x=results_df['k'], 
    y=results_df['p'], 
    z=results_df['Accuracy'], 
    mode='markers', 
    marker=dict( 
        size=4, 
        color=results_df['Accuracy'], 
        colorscale='Viridis', 
        showscale=True, 
        opacity=0.8 
    text=[f"k={k}, p={p}, Acc={acc:.2f}" for k, p, acc in results] 
fig.update_layout(scene=dict(