加權kNN，k近鄰算法的增強改進版本。

加權KNN算法

近鄰算法（k-Nearest Neighbors, kNN）是一種用于分類和回歸的非參數方法。它的基本思想是“看鄰居”，即通過查找離目標點最近的 K 個數據點，來判斷目標點的類別或數值。

舉個例子，假設有一個訓練集，其中有兩類點：紅色代表類別0，綠色代表類別1。現在有一個白色點，需要確定它的類別。我們選擇k=3，計算白色點到所有紅色點和綠色點的距離，選取距離最近的3個點。如果這3個點中有2個是綠色，1個是紅色，我們就認為白色點屬于綠色那一類，即類別1。

但是，KNN算法性能受到超參數k值選擇的影響。如果k值過小，算法對離群點會更敏感；如果k值過大，鄰域內可能包含過多來自其他類別的點。此外，考慮到一個普遍的認識，即：如果靠近的數據點之間在距離上差異很大，那么其中最靠近的那一個數據點更能可靠地表明對象的類別。 針對這一些情況，加權KNN算法隨之誕生。

更直觀的理解：

假設有以下訓練集：

• 紅色標簽表示類別0的點，綠色標簽表示類別1的點。

此時，如果我們將白色點作為查詢點（需要預測類別標簽的點），并且將上述數據集交給一個基于KNN的分類器，分類器會基于前面提到的最鄰近原則將查詢點歸為類別0。但是，從圖中可以明顯看出，該點應該更接近類別1的點。為了克服這一缺點，我們就可以使用加權kNN。

在加權kNN中，最近的k個點根據一個稱為核函數的函數賦予權重。加權kNN的直覺是，給距離較近的點更多的權重，而給距離較遠的點更少的權重。任何值隨距離增加而減少的函數都可以用作加權kNN分類器的核函數，其中最簡單的函數是反距離函數。

反距離函數是一種常用的加權函數，用于kNN算法中，通過距離的倒數來給近鄰點賦予權重。公式如下：

$$w_i=\frac{1}{d_i}$$

其中：

• $w_i$是第 $i$ 個近鄰點的權重。
• $d_i$ 是第 $i$ 個近鄰點到查詢點的距離。

這個函數的直觀理解是：距離越近的點，權重越大；距離越遠的點，權重越小。這樣可以更準確地反映近鄰點對查詢點的影響。

Python 代碼實現如下：

# Python3 program to implement the 
# weighted K nearest neighbour algorithm. import math def weightedkNN(points,p,k=3): ''' This function finds classification of p using weighted k nearest neighbour algorithm. It assumes only two two classes and returns 0 if p belongs to class 0, else 1 (belongs to class 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 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 # weighted sum of group 0 freq2 = 0 # weighted sum of group 1 for d in distance: if d[1] == 0: freq1 += (1 / d[0]) elif d[1] == 1: freq2 += (1 /d[0]) 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:[(0, 4),(1, 4.9),(1.6, 5.4),(2.2, 6),(2.8, 7),(3.2, 8),(3.4, 9)], 1:[(1.8, 1),(2.2, 3),(3, 4),(4, 4.5),(5, 5),(6, 5.5)]} # query point p(x,y) p = (2, 4) # Number of neighbours k = 5print("The value classified to query point is: {}".format(weightedkNN(points,p,k))) if __name__ == '__main__': main() 

參考鏈接：

• https://www.geeksforgeeks.org/weighted-k-nn/