KNN中不同距離度量對比和介紹（1）

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算法的原理很簡單，所以我們這里直接使用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

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