K最近鄰 (KNN) 算法是一種用于解決分類和回歸問題的監(jiān)督機器學(xué)習(xí)方法。 Evelyn Fix 和 Joseph Hodges 于 1951 年開發(fā)了該算法，隨后 Thomas Cover 對其進行了擴展。本文探討了 KNN 算法的基本原理、工作原理和實現(xiàn)。

什么是 K 最近鄰算法？

KNN 是機器學(xué)習(xí)中最基本但最重要的分類算法之一。它屬于監(jiān)督學(xué)習(xí)領(lǐng)域，在模式識別、數(shù)據(jù)挖掘和入侵檢測中有廣泛的應(yīng)用。

它在現(xiàn)實生活中被廣泛使用，因為它是非參數(shù)的，這意味著它不會對數(shù)據(jù)的分布做出任何基本假設(shè)。我們獲得了一些先驗數(shù)據(jù)（也稱為訓(xùn)練數(shù)據(jù)），它將坐標(biāo)分類為由屬性標(biāo)識的組。 作為示例，請考慮下表包含兩個特征的數(shù)據(jù)點：

現(xiàn)在，給定另一組數(shù)據(jù)點（也稱為測試數(shù)據(jù)），通過分析訓(xùn)練集將這些點分配到一組。請注意，未分類的點標(biāo)記為“白色”。

KNN算法背后的直覺

如果我們將這些點繪制在圖表上，我們也許能夠找到一些簇或組。現(xiàn)在，給定一個未分類的點，我們可以通過觀察其最近鄰居屬于哪個組來將其分配給一個組。這意味著靠近被分類為“紅色”的點簇的點被分類為“紅色”的概率更高。

直觀上，我們可以看到第一個點（2.5，7）應(yīng)該被分類為“綠色”，第二個點（5.5，4.5）應(yīng)該被分類為“紅色”。

為什么我們需要 KNN 算法？

KNN算法是一種通用且廣泛使用的機器學(xué)習(xí)算法，主要因其簡單性和易于實現(xiàn)而被使用。它不需要對底層數(shù)據(jù)分布進行任何假設(shè)。它還可以處理數(shù)值和分類數(shù)據(jù)，使其成為分類和回歸任務(wù)中各種類型數(shù)據(jù)集的靈活選擇。它是一種非參數(shù)方法，根據(jù)給定數(shù)據(jù)集中數(shù)據(jù)點的相似性進行預(yù)測。與其他算法相比，KNN 對異常值不太敏感。

KNN算法的工作原理是根據(jù)距離度量（例如歐幾里得距離）查找給定數(shù)據(jù)點的 K 個最近鄰。然后，數(shù)據(jù)點的類別或值由 K 個鄰居的多數(shù)票或平均值確定。這種方法允許算法適應(yīng)不同的模式并根據(jù)數(shù)據(jù)的局部結(jié)構(gòu)進行預(yù)測。

KNN 算法中使用的距離度量

眾所周知，KNN 算法可以幫助我們識別查詢點的最近點或組。但是為了確定查詢點的最近組或最近點，我們需要一些度量。為此，我們使用以下距離度量：

歐氏距離

這只不過是平面/超平面中兩點之間的笛卡爾距離。歐幾里得距離也可以可視化為連接所考慮的兩個點的直線的長度。該指標(biāo)幫助我們計算物體在兩種狀態(tài)之間完成的凈位移。

曼哈頓距離

當(dāng)我們對物體移動的總距離而不是位移感興趣時，通常使用曼哈頓距離度量。該度量是通過對 n 維點的坐標(biāo)之間的絕對差求和來計算的。

KNN算法如何選擇k的值？

k的值在KNN算法中非常關(guān)鍵，用于定義算法中鄰居的數(shù)量。 k近鄰 (kNN) 算法中的 k 值應(yīng)根據(jù)輸入數(shù)據(jù)進行選擇。如果輸入數(shù)據(jù)有更多異常值或噪聲，則 k 值越高越好。建議為 k 選擇一個奇數(shù)，以避免分類中出現(xiàn)平局。交叉驗證方法可以幫助為給定數(shù)據(jù)集選擇最佳 k 值。

KNN 算法的工作原理

K 最近鄰 (KNN) 算法根據(jù)相似性原理運行，通過考慮訓(xùn)練數(shù)據(jù)集中 K 個最近鄰的標(biāo)簽或值來預(yù)測新數(shù)據(jù)點的標(biāo)簽或值。

步驟1：選擇K的最佳值

• K表示進行預(yù)測時需要考慮的最近鄰居的數(shù)量。

步驟2：計算距離

• 為了測量目標(biāo)和訓(xùn)練數(shù)據(jù)點之間的相似性，使用歐幾里得距離。計算數(shù)據(jù)集中的每個數(shù)據(jù)點與目標(biāo)點之間的距離。

步驟3：尋找最近鄰居

• 與目標(biāo)點距離最小的 k 個數(shù)據(jù)點是最近鄰點。

步驟4：投票分類或取平均值進行回歸

• 在分類問題中， 的類標(biāo)簽是通過進行多數(shù)投票來確定的。鄰居中出現(xiàn)次數(shù)最多的類成為目標(biāo)數(shù)據(jù)點的預(yù)測類。
• 在回歸問題中，類標(biāo)簽是通過取 K 個最近鄰的目標(biāo)值的平均值來計算的。計算出的平均值成為目標(biāo)數(shù)據(jù)點的預(yù)測輸出。

KNN算法的優(yōu)點

• 算法復(fù)雜度不是很高，易于實現(xiàn)。
• 適應(yīng)度廣。根據(jù) KNN 算法的工作原理，它將所有數(shù)據(jù)存儲在內(nèi)存存儲中，因此每當(dāng)添加新示例或數(shù)據(jù)點時，算法都會根據(jù)該新示例進行自我調(diào)整，并對未來的預(yù)測做出貢獻。
• 很少的超參數(shù)。KNN 算法訓(xùn)練中所需的唯一參數(shù)是 k 的值和我們希望從評估指標(biāo)中選擇的距離指標(biāo)。

KNN算法的缺點

• 不能擴展，KNN 算法也被認為是一種惰性算法。該術(shù)語的主要意義在于，這需要大量的計算能力和數(shù)據(jù)存儲。這使得該算法既耗時又消耗資源。
• 維度災(zāi)難。意味著當(dāng)維數(shù)太高時，該算法很難對數(shù)據(jù)點進行正確分類。
• 容易過擬合。由于算法受到維度災(zāi)難的影響，因此也容易出現(xiàn)過度擬合的問題。因此，通常應(yīng)用特征選擇和降維技術(shù)來解決這個問題。

import math

def classifyAPoint(points,p,k=3):
 '''
 This function finds the classification of p using
 k nearest neighbor algorithm. It assumes only two
 groups and returns 0 if p belongs to group 0, else
 1 (belongs to group 1).

 Parameters - 
  points: Dictionary of training points having two keys - 0 and 1
    Each key have a list of training data points belong to that 

  p : A tuple, test data point of the form (x,y)

  k : number of nearest neighbour to consider, default is 3 
 '''

 distance=[]
 for group in points:
  for feature in points[group]:

   #calculate the euclidean distance of p from training points 
   euclidean_distance = math.sqrt((feature[0]-p[0])**2 +(feature[1]-p[1])**2)

   # Add a tuple of form (distance,group) in the distance list
   distance.append((euclidean_distance,group))

 # sort the distance list in ascending order
 # and select first k distances
 distance = sorted(distance)[:k]

 freq1 = 0 #frequency of group 0
 freq2 = 0 #frequency og group 1

 for d in distance:
  if d[1] == 0:
   freq1 += 1
  elif d[1] == 1:
   freq2 += 1

 return 0 if freq1>freq2 else 1

# driver function
def main():

 # Dictionary of training points having two keys - 0 and 1
 # key 0 have points belong to class 0
 # key 1 have points belong to class 1

 points = {0:[(1,12),(2,5),(3,6),(3,10),(3.5,8),(2,11),(2,9),(1,7)],
   1:[(5,3),(3,2),(1.5,9),(7,2),(6,1),(3.8,1),(5.6,4),(4,2),(2,5)]}

 # testing point p(x,y)
 p = (2.5,7)

 # Number of neighbours 
 k = 3

 print("The value classified to unknown point is: {}".\
  format(classifyAPoint(points,p,k)))

if __name__ == '__main__':
 main()

本文轉(zhuǎn)載自???????沐白AI筆記???????，作者：楊沐白