權值加權:為每個點的距離增加一個權重,使得距離近的點可以得到更大的權重,在此描述如何加權。
反函數
該方法最簡單的形式是返回距離的倒數,比如距離d,權重1/d。有時候,完全一樣或非常接近的商品權重會很大甚至無窮大。基於這樣的原因,在距離求倒數時,在距離上加一個常量:
weight = 1 / (distance + const)
這種方法的潛在問題是,它為近鄰分配很大的權重,稍遠一點的會衰減的很快。雖然這種情況是我們希望的,但有時候也會使算法對噪聲數據變得更加敏感。
高斯函數
高斯函數比較複雜,但克服了前述函數的缺點,其形式:
其中a,b,c∈R
高斯函數的圖形在形狀上像一個倒懸著的鐘。a是曲線的高度,b是曲線中心線在x軸的偏移,c是半峰寬度(函數峰值一半處相距的寬度)。
半峰寬度
def gaussian(dist, a=1, b=0, c=0.3):
return a * math.e ** (-(dist - b) ** 2 / (2 * c ** 2))
上面的高斯函數在距離為0的時候權重為1,隨著距離增大,權重減少,但不會變為0。下圖是高斯函數和其它幾個函數的區別,其它函數在距離增大到一定程度時,權重都跌至0或0以下。
計算過程
加權kNN首先獲得經過排序的距離值,再取距離最近的k個元素。
1.在處理離散型數據時,將這k個數據用權重區別對待,預測結果與第n個數據的label相同的概率:
將各個類預測的權重值相加,哪個類最大,就屬於哪個類。
f(x) = Wi屬於類x / Wi總和 i=1,2,...,k
2.在處理數值型數據時,並不是對這k個數據簡單的求平均,而是加權平均:通過將每一項的值乘以對應權重,然後將結果累加。求出總和後,除以所有權重之和。
f(x) = Wi*Vi總和 / Wi總和 i=1,2,...,k
Vi代表近鄰i的值,Wi代表其權重,f(x)是預測的數值型結果。每預測一個新樣本的所屬類別時,都會對整體樣本進行遍歷,可以看出kNN的效率實際上是十分低下的。
---------------------
原文:https://blog.csdn.net/weixin_41770169/article/details/81560946