k近鄰算法KNN是一種簡單而強(qiáng)大的算法，可用于分類和回歸任務(wù)。他實(shí)現(xiàn)簡單，主要依賴不同的距離度量來判斷向量間的區(qū)別，但是有很多距離度量可以使用，所以本文演示了KNN與三種不同距離度量(Euclidean、Minkowski和Manhattan)的使用。

KNN算法概述

KNN是一種惰性、基于實(shí)例的算法。它的工作原理是將新樣本的特征與數(shù)據(jù)集中現(xiàn)有樣本的特征進(jìn)行比較。然后算法選擇最接近的k個(gè)樣本，其中k是用戶定義的參數(shù)。新樣本的輸出是基于“k”最近樣本的多數(shù)類(用于分類)或平均值(用于回歸)確定的。

有很多距離度量的算法，我們這里選取3個(gè)最常用度量的算法來進(jìn)行演示：

1、歐氏距離 Euclidean Distance

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

euclidean_distance函數(shù)計(jì)算多維空間中兩點(diǎn)(x1和x2)之間的歐氏距離，函數(shù)的工作原理如下：

• 從x1元素中減去x2，得到對應(yīng)坐標(biāo)之間的差值。
• 使用**2運(yùn)算將差值平方。
• 使用np.sum()對差的平方求和。
• 使用math.sqrt()取總和的平方根。

歐幾里得距離是歐幾里得空間中兩點(diǎn)之間的直線距離。通過計(jì)算歐幾里得距離，可以識別給定樣本的最近鄰居，并根據(jù)鄰居的多數(shù)類(用于分類)或平均值(用于回歸)進(jìn)行預(yù)測。在處理連續(xù)的實(shí)值特征時(shí)，使用歐幾里得距離很有幫助，因?yàn)樗峁┝艘环N直觀的相似性度量。

2、曼哈頓距離 Manhattan Distance

兩點(diǎn)坐標(biāo)的絕對差值之和。

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

Manhattan _distance函數(shù)計(jì)算多維空間中兩點(diǎn)(x1和x2)之間的曼哈頓距離，函數(shù)的工作原理如下：

• 用np計(jì)算x1和x2對應(yīng)坐標(biāo)的絕對差值。Abs (x1 - x2)
• 使用np.sum()對絕對差進(jìn)行求和。

曼哈頓距離，也稱為L1距離或出租車距離，是兩點(diǎn)坐標(biāo)的絕對差值之和。它代表了當(dāng)運(yùn)動被限制為網(wǎng)格狀結(jié)構(gòu)時(shí)，點(diǎn)之間的最短路徑，類似于在城市街道上行駛的出租車。

在數(shù)據(jù)特征具有不同尺度的情況下，或者當(dāng)問題域的網(wǎng)格狀結(jié)構(gòu)使其成為更合適的相似性度量時(shí)，使用曼哈頓距離可能會有所幫助。曼哈頓距離可以根據(jù)樣本的特征來衡量樣本之間的相似性或差異性。

與歐幾里得距離相比，曼哈頓距離對異常值的敏感性較低，因?yàn)樗鼪]有對差異進(jìn)行平方。這可以使它更適合于某些數(shù)據(jù)集或異常值的存在可能對模型的性能產(chǎn)生重大影響的問題。

3、閔可夫斯基距離 Minkowski Distance

它是歐幾里得距離和曼哈頓距離的一般化的表現(xiàn)形式，使用p進(jìn)行參數(shù)化。當(dāng)p=2時(shí)，它變成歐氏距離，當(dāng)p=1時(shí)，它變成曼哈頓距離。

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

minkowski_distance函數(shù)計(jì)算多維空間中兩點(diǎn)(x1和x2)之間的閔可夫斯基距離。

當(dāng)你想要控制單個(gè)特征的差異對整體距離的影響時(shí)，使用閔可夫斯基距離會很有幫助。通過改變p值，可以調(diào)整距離度量對特征值或大或小差異的靈敏度，使其更適合特定的問題域或數(shù)據(jù)集。

閔可夫斯基距離可以根據(jù)樣本的特征來衡量樣本之間的相似性或不相似性。該算法通過計(jì)算適當(dāng)p值的閔可夫斯基距離，識別出給定樣本的最近鄰居，并根據(jù)鄰居的多數(shù)類(用于分類)或平均值(用于回歸)進(jìn)行預(yù)測。

KNN 算法的代碼實(shí)現(xiàn)

因?yàn)镵NN算法的原理很簡單，所以我們這里直接使用Python實(shí)現(xiàn)，這樣也可以對算法有一個(gè)更好的理解：

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

這個(gè)' knn_euclidean_distance '函數(shù)對于解決分類問題很有用，因?yàn)樗梢愿鶕?jù)' k '個(gè)最近鄰居中的大多數(shù)類進(jìn)行預(yù)測。該函數(shù)使用歐幾里得距離作為相似性度量，可以識別測試集中每個(gè)數(shù)據(jù)點(diǎn)的最近鄰居，并相應(yīng)地預(yù)測它們的標(biāo)簽。我們實(shí)現(xiàn)的代碼提供了一種顯式的方法來計(jì)算距離、選擇鄰居，并根據(jù)鄰居的投票做出預(yù)測。

在使用曼哈頓距離時(shí)，KNN算法與歐氏距離保持一致，只需要將距離計(jì)算函數(shù)euclidean_distance修改為manhattan_distance。而閔可夫斯基距離則需要多加一個(gè)參數(shù)p，實(shí)現(xiàn)代碼如下：

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

距離度量對比

我使用的數(shù)據(jù)集是乳腺癌數(shù)據(jù)集，可以在kaggle上直接下載

這個(gè)數(shù)據(jù)集是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中廣泛使用的基準(zhǔn)數(shù)據(jù)集，用于二元分類任務(wù)。它是由威廉·h·沃爾伯格(William H. Wolberg)博士及其合作者在20世紀(jì)90年代從麥迪遜的威斯康星大學(xué)醫(yī)院收集的。該數(shù)據(jù)集可通過UCI機(jī)器學(xué)習(xí)存儲庫公開獲取。

Breast Cancer Wisconsin數(shù)據(jù)集包含569個(gè)實(shí)例，每個(gè)實(shí)例有32個(gè)屬性。這些屬性是：

ID number：每個(gè)樣本的唯一標(biāo)識符。

Diagnosis：目標(biāo)變量有兩個(gè)可能的值——“M”(惡性)和“B”(良性)。

剩下的是30個(gè)從乳腺腫塊的細(xì)針抽吸(FNA)的數(shù)字化圖像中計(jì)算出來的特征。它們描述了圖像中細(xì)胞核的特征。對每個(gè)細(xì)胞核計(jì)算每個(gè)特征，然后求平均值，得到10個(gè)實(shí)值特征：

• Radius：從中心到周邊點(diǎn)的平均距離。
• Texture：灰度值的標(biāo)準(zhǔn)偏差。
• Perimeter：細(xì)胞核的周長。
• Area：細(xì)胞核的面積。
• Smoothness：半徑長度的局部變化。
• Compactness：周長2/面積- 1.0。
• Concavity：輪廓中凹部分的嚴(yán)重程度。
• Concave points：輪廓的凹部分的數(shù)目。
• Symmetry：細(xì)胞核的對稱性。
• Fractal dimension：“Coastline approximation”- 1

對每張圖像計(jì)算這十個(gè)特征的平均值、標(biāo)準(zhǔn)誤差和最小或最大值(三個(gè)最大值的平均值)，總共得到30個(gè)特征。數(shù)據(jù)集不包含任何缺失的屬性值。

由于數(shù)據(jù)集包含30個(gè)特征，我們需要對數(shù)據(jù)集進(jìn)行特征選擇。這種方法的主要目的是通過選擇與目標(biāo)變量具有強(qiáng)線性關(guān)系的較小的特征子集來降低數(shù)據(jù)集的維數(shù)。通過選擇高相關(guān)性的特征，目的是保持模型的預(yù)測能力，同時(shí)減少使用的特征數(shù)量，潛在地提高模型的性能和可解釋性。這里需要注意的是，該方法只考慮特征與目標(biāo)變量之間的線性關(guān)系，如果底層關(guān)系是非線性的，或者特征之間存在重要的交互作用，則該方法可能無效。

讀取數(shù)據(jù)并計(jì)算相關(guān)系數(shù)：

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ùn)練代碼：

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算法應(yīng)用于分類問題，同時(shí)改變鄰居的數(shù)量(k)以找到最高精度的最佳k值。它使用訓(xùn)練集(X_train_np和y_train_np)來訓(xùn)練模型，使用測試集(X_test_np和y_test_np)來進(jìn)行預(yù)測和評估模型的性能。

k是KNN算法的一個(gè)超參數(shù)，選擇正確的k值對于實(shí)現(xiàn)最佳模型性能至關(guān)重要，因?yàn)閗值太小可能導(dǎo)致過擬合，而k值太大可能導(dǎo)致欠擬合。通過可視化k值與其對應(yīng)的精度之間的關(guān)系，可以深入了解模型的性能，并為問題選擇最合適的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(
     xaxis_title='k',
     yaxis_title='p',
     zaxis_title='Accuracy'
 ))
 
 fig.show()

為了進(jìn)一步改善我們的結(jié)果，我們還可以數(shù)據(jù)集進(jìn)行縮放。應(yīng)用特征縮放的主要目的是確保所有特征具有相同的尺度，這有助于提高基于距離的算法(如KNN)的性能。在KNN算法中，數(shù)據(jù)點(diǎn)之間的距離對確定它們的相似度起著至關(guān)重要的作用。如果特征具有不同的尺度，則算法可能會更加重視尺度較大的特征，從而導(dǎo)致次優(yōu)預(yù)測。通過將特征縮放到均值和單位方差為零，算法可以平等地對待所有特征，從而獲得更好的模型性能。

本文將使用StandardScaler()和MinMaxScaler()來擴(kuò)展我們的數(shù)據(jù)集。StandardScaler和MinMaxScaler是機(jī)器學(xué)習(xí)中兩種流行的特征縮放技術(shù)。這兩種技術(shù)都用于將特征轉(zhuǎn)換為公共尺度，這有助于提高許多機(jī)器學(xué)習(xí)算法的性能，特別是那些依賴于距離的算法，如KNN或支持向量機(jī)(SVM)。

使用不同的尺度和不同的距離函數(shù)訓(xùn)練KNN，可以進(jìn)行比較并選擇最適合數(shù)據(jù)集的技術(shù)。我們得到了以下結(jié)果:

可以使用柱狀圖表示來更好地分析和理解這些結(jié)果。

總結(jié)

根據(jù)上面的結(jié)果，我們可以得到以下的結(jié)論：

在不進(jìn)行特征縮放時(shí)，歐幾里得距離和閔可夫斯基距離都達(dá)到了0.982456的最高精度。

曼哈頓離在所有情況下的精度都比較低，這表明歐幾里得或閔可夫斯基距離可能更適合這個(gè)問題。當(dāng)閔可夫斯基距離度量中的p值為2時(shí)，它等于歐幾里得距離。在我們這個(gè)實(shí)驗(yàn)中這兩個(gè)指標(biāo)的結(jié)果是相同的，也證明了這是正確的。

對于歐幾里得和閔可夫斯基距離度量，不應(yīng)用任何特征縮放就可以獲得最高的精度。而對于曼哈頓距離，與非縮放數(shù)據(jù)相比，StandardScaler和MinMaxScaler都提高了模型的性能。這表明特征縮放的影響取決于所使用的距離度量。

最佳k值:最佳k值取決于距離度量和特征縮放技術(shù)。例如，k=11是不應(yīng)用縮放并且使用歐幾里得距離或閔可夫斯基距離時(shí)的最佳值，而k=9是使用曼哈頓距離時(shí)的最佳值。當(dāng)應(yīng)用特征縮放時(shí)，最佳k值通常較低，范圍在3到11之間。

最后，該問題的最佳KNN模型使用歐式距離度量，無需任何特征縮放，在k=11個(gè)鄰居時(shí)達(dá)到0.982456的精度。這應(yīng)該是我們這個(gè)數(shù)據(jù)集在使用KNN時(shí)的最佳解。