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 实现，这样也能够对算法有一个更好的了解：
defknn_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
foriinrange(len(X_test)):
distances= []
# Iterate over each point in the training set
forjinrange(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= {}
forneighborinneighbors:
label=neighbor[1]
iflabelincounts:
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)
returny_pred这个 ’ knn_euclidean_distance ‘ 函数对于解决分类问题很有用，因为它能够依据 ’ k ‘ 个最近街坊中的大多数类进行预测。该函数应用欧几里得间隔作为相似性度量，能够辨认测试集中每个数据点的最近街坊，并相应地预测它们的标签。咱们实现的代码提供了一种显式的办法来计算间隔、抉择街坊，并依据街坊的投票做出预测。
在应用曼哈顿间隔时，KNN 算法与欧氏间隔保持一致，只须要将间隔计算函数 euclidean_distance 批改为 manhattan_distance。而闵可夫斯基间隔则须要多加一个参数 p，实现代码如下：
defknn_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
foriinrange(len(X_test)):
distances= []
# Iterate over each point in the training set
forjinrange(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= {}
forneighborinneighbors:
label=neighbor[1]
iflabelincounts:
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)
returny_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= []
forkink_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= []
forkink_values:
forpinp_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}"fork, p, accinresults]
)])
fig.update_layout(scene=dict(
xaxis_title='k',
yaxis_title='p',
zaxis_title='Accuracy'
))
fig.show()为了进一步改善咱们的后果，咱们还能够数据集进行缩放。利用特色缩放的次要目标是确保所有特色具备雷同的尺度，这有助于进步基于间隔的算法 (如 KNN) 的性能。在 KNN 算法中，数据点之间的间隔对确定它们的类似度起着至关重要的作用。如果特色具备不同的尺度，则算法可能会更加器重尺度较大的特色，从而导致次优预测。通过将特色缩放到均值和单位方差为零，算法能够平等地看待所有特色，从而取得更好的模型性能。
本文将应用 StandardScaler()和 MinMaxScaler()来扩大咱们的数据集。StandardScaler 和 MinMaxScaler 是机器学习中两种风行的特色缩放技术。这两种技术都用于将特色转换为公共尺度，这有助于进步许多机器学习算法的性能，特地是那些依赖于间隔的算法，如 KNN 或反对向量机(SVM)。
应用不同的尺度和不同的间隔函数训练 KNN，能够进行比拟并抉择最适宜数据集的技术。咱们失去了以下后果:
能够应用柱状图示意来更好地剖析和了解这些后果。
总结
依据下面的后果，咱们能够失去以下的论断：
在不进行特色缩放时，欧几里得间隔和闵可夫斯基间隔都达到了 0.982456 的最高精度。
曼哈顿离在所有状况下的精度都比拟低，这表明欧几里得或闵可夫斯基间隔可能更适宜这个问题。当闵可夫斯基间隔度量中的 p 值为 2 时，它等于欧几里得间隔。在咱们这个试验中这两个指标的后果是雷同的，也证实了这是正确的。
对于欧几里得和闵可夫斯基间隔度量，不利用任何特色缩放就能够取得最高的精度。而对于曼哈顿间隔，与非缩放数据相比，StandardScaler 和 MinMaxScaler 都进步了模型的性能。这表明特色缩放的影响取决于所应用的间隔度量。
最佳 k 值: 最佳 k 值取决于间隔度量和特色缩放技术。例如，k=11 是不利用缩放并且应用欧几里得间隔或闵可夫斯基间隔时的最佳值，而 k = 9 是应用曼哈顿间隔时的最佳值。当利用特色缩放时，最佳 k 值通常较低，范畴在 3 到 11 之间。
最初，该问题的最佳 KNN 模型应用欧式间隔度量，无需任何特色缩放，在 k =11 个街坊时达到 0.982456 的精度。这应该是咱们这个数据集在应用 KNN 时的最佳解。
如果你想本人试验，残缺代码和数据都能够在这里找到：
https://avoid.overfit.cn/post/19200b7f741f4686a9b6ada15552d1ba
作者：Abdullah Siddique