機器學習筆記（一） KNN K-最近鄰

05-14

零、摘要

本篇文章主要講述KNN演算法（K-nearest neighbor）的原理與技術細節，並簡單提及了數據預處理的方法。

主要參考資料:

斯坦福CS231n課程筆記：分類
《機器學習》周志華
《機器學習實戰》Peter Harrington
維基百科：K-nearestneighborsalgorithm

一、從1NN到KNN

近朱者赤，近墨者黑

考慮這樣一個問題：給定平面上十個點，其中五個紅色的點，五個黑色的點。現在要求預測虛線描出的點屬於哪一個類別。當然對於我們人類來說，顯然能斷定這一點更有可能是紅色的，但是我們應該怎樣設計一個演算法讓機器也這樣認為呢？

我們可以這樣做：

計算虛線圈出的點與給定的所有點之間的距離
找出與他距離最小的那個點
距離最小的點是什麼顏色，則預測所求點是什麼顏色

A點距離最短，是紅色的，斷定所求點應該是紅色的。這就使1NN即最近鄰演算法。

為了更好地理解最近鄰演算法，我們做這樣一件事情：在這個平面的所有位置都擺放一次要預測的點，然後用1NN演算法對他們進行預測。預測的點布滿整個平面後，我們就能得到兩個區域：

如果要預測的點出現在紅色邊界線左邊的黑色區域裡面，那麼他就會被預測為黑色，對於右側區域同理。從這張圖來看，我們的1NN分類器表現得還不錯。

但是如果我們換一個點集，再做一次同樣的事情呢？我們得到下面圖裡的結果：

顯然，點B有可能是統計數據時因為馬虎出現的錯誤，我們通常稱他為雜訊。點B附近的那一小塊區域看起來更應該屬於黑色才對。那麼我們怎麼讓機器也這樣認為呢？

考慮這樣一個方法：

- 計算要預測的點與給定的所有點之間的距離

- 找出與他距離最小的K個點

- 這K個點中那種顏色的點出現次數最多，則預測所求點是什麼顏色

（通常，我們把第三步稱作投票）

好的，我們想一下這樣的話會得出什麼樣的結果：

當K=1時，我們的這個方法與之前的方法沒有任何不同。當K=3時，對於上圖B點附近紅色區域中的點（注意我們是要討論這一區域裡面的點而不是B點），我們找出離他最近的三個點，會得出這樣的結果：兩黑一紅。選出出現次數最多的顏色——黑色，預測這一點的顏色是黑色的。搞定。

下圖時真正程序跑出來的分類結果。左邊起第一張是原始數據，第二張是我們的1NN，第三張是K=5時的情形。（白色區域表示有至少兩個顏色得票相同）

我們看到，相對於1NN，KNN演算法對於雜訊更加不敏感，我們稱這一特性為魯棒性。

至於超參數K值的確定，我們通常是通過交叉驗證來獲得。即在驗證集上嘗試不同的K值，使用錯誤率最低的那個。

二、加權KNN

考慮下圖中的預測問題：

顯然這點應該屬於紅色，但是比如說當K=6時，預測結果就容易出錯。這是因為KNN考慮了很多距離更遠的黑點。要解決這個問題，我們可以讓距離越近的點對於決策越重要。於是我們就有了加權KNN。

我們原來的KNN是在比較所求點與所有給定點之間的距離d，如果說加權KNN要比較的是關於d的函數f(d)，那麼只要這個函數關於d單調遞減，就能滿足要求。

最簡單地，我們有f(d)=1/d。但是，想到當d趨向於零時，該函數值 f(d)=d 趨向於正無窮。這相當於為距離很近的點分配了無限大的權重，假如恰巧有一個雜訊的點在離要預測的點非常近的位置，那麼這一噪音對於預測結果的干擾就非常大了。

考慮高斯函數 $f(d) = exp(-d^2/2)$

這個函數就很好地彌補了反比例函數的缺點，當d趨向於零時，函數值趨向於1。當d>0時，f(d)單調遞減（顯然距離d取正值）。同時高斯函數還有一個優點就是，當距離d很大時，函數值f(d)始終會保持正值，而不會跌入負值。

加權KNN做的事情就是，比較最近的K個點的距離d 的單調遞減函數f(d)的函數值

三、距離的選擇

我們之前一直在說，選擇距離最近的K個點，那麼這個距離是怎麼計算的呢？

我們知道，對於平面上的兩點的距離，是x, y軸坐標各自的平方差之和再開根號。一般地，對於n維空間中的點，有

$d (I1, I2) = sqrt{sum{p} left( I^p1 - I^p2 ight)^2}$ ，
其中 $I_1,I_2$ 是兩個點的坐標，p表示維度。我們通常稱他維L2距離

當然，還有L1距離 $d(I1, I2) = sum{p} left| I^p1 - I^p_2 ight|$

L1和L2距離都是常用的距離度量方法。他們之間的區別可以這樣來思考：在某一維度上，如果兩點相距較遠，則L2距離比L1距離要更大，而若兩點相距很近，則反之。這是由於平方的存在，可以參考 $y=x$ 和 $y=x^2$ 在第一象限內的圖像。

四、歸一化

在處理實際問題時，事情可能變得與處理平面時有些區別。

比如說我們要用KNN處理這樣一個問題：

我們手中有這樣一個數據集，河海大學100個學生的

- 每學期天在圖書館的總小時數

- 每學期使用電腦的總小時數

- 每學期交作業總次數

- 所屬院系

前三個是數值，每個學生有三個對應數值，相當於每一個學生是三維空間中的一個點，三個對應數值是這個點的坐標，而所屬院系則是類似於紅或黑的屬性。

我們要做的事情是根據數據集里沒有的一名學生的前三個數據，來判斷他的院系。

如果直接使用KNN的話，我們會發現，三個維度上的數據相差過大，即前兩個維度對於「距離」的影響要比第三個維度大得多。為了解決這個問題，我們要對數據進行預處理：歸一化。

如果我們能將三個維度上的數值都壓縮到同樣一個區間上（比如說0到1或者-1到1），這樣三個維度的數據對與最後決策的影響差距就會基本相等。

我們有：歸一化後數值 = （原數值 - 平均值）/ （最大值 - 平均值）

上式能將原數據壓縮至0到1的區間。

五、數據精簡

剔除雜訊

我們的KNN演算法，並沒有顯示的訓練過程（但我們仍把給定點集稱作「訓練集」），這是一種比較「懶惰」的機器學習方法。這也導致了在實際預測過程中，需要對訓練集的每一個點都進行距離計算，這是十分耗時的。如果我們能減少一部分冗餘的樣本，自然就能減少使用時計算的負擔。

首先，之前提到過的雜訊點是最應該被去掉的。我們來思考如何能判斷訓練集中的樣本（點）是否屬於雜訊。通常，雜訊樣本都有「孤軍深入」這樣的特點。那我們就可以這樣設計演算法：

只要某一個樣本的周圍都是與它屬性不同的點，那我們就判斷這個樣本屬於雜訊。

比較嚴謹地：

給定超參數K，取小於K的正整數R，若某樣本的「R近鄰」都是屬性不同的樣本，則刪除該樣本
這樣，我們就可以刪除一部分雜訊了，同時也精簡了數據集。

選擇原型

我們說，數據精簡的目的是：用留下的最少的部分數據，完成與完整訓練集差不多的分類性能。這一部分里，我們把那留下的最少的那部分數據稱作「原型」，接下來，我們來討論應該如何選擇這一訓練集的子集。

試想這樣一個情景，你坐在河海大學文體中心小劇場聽新生入學教育，劇場觀眾席的學生是按班級分布的。你覺得台上的演講十分無聊，便想要確定觀眾席中每個班級的具體位置以及邊界。

你可以這樣做：首先對於你附近的人，詢問他們的班級。如果他屬於一個沒見過的的班級，就那小本本把他的位置記下來。一小會之後，你的小本本上就會有幾個不同班的學生了。

然後對於在場的每一位學生：

詢問他的班級，再詢問離他最近的那個人的班級。

如果兩個不一樣，則拿出小本本把這位學生記下來；如果一樣，那麼我們說，你這位學生對於我確定邊界沒什麼用，不記下你了。

在遍歷一遍在場的所有同學之後，你就可以用你手中的小本本來做KNN分類啦。我們把這個小本本上的同學就稱作原型。

比較嚴謹地，我們有：

有原型（樣本集合）U遍歷所有樣本，對於當前樣本x：{ 如果他和他的最近鄰屬性不同：就將x加入U；如果他和他的最近鄰屬性相同：繼續循環，即捨棄該樣本；}

這樣，當我們完成遍歷，就得到了原型U，這時我們就可以用精簡後的U做1NN分類了。這一方法被稱為CNN(Condensed nearest neighbor)，有趣的是，他與卷積神經網路——convolutional neural networks, CNN重名。

邊界率

還有一個技術細節，就是我們要指定遍歷樣本的順序，來獲得更好的原型U。

定義邊界率 a(x)=||x-y||/||x-y||，我們要對於訓練集中的每一個樣本x，挨個計算邊界率a。

其中，x表示當前樣本；y表示離x最近的，不同屬性的樣本；x表示離y最近的，與x同屬性的樣本。

如圖所示，當前樣本是紅色的，y是與當前樣本不同的綠色，x是與當前樣本相同的紅色。

要指出，由於||x-y|| <= ||x-y||，邊界率a的值在0和1之間。

計算完所有邊界率a之後，我們對訓練集中的樣本，按邊界率a從大到小的順序進行排序，再按這個順序來進行遍歷。

這樣的順序有助於我們獲得更經濟且性能更好的原型U。

對於之前的例子：

進行了數據精簡後，我們得到

其中，標有x的點是去掉的噪音，標方框的點是原型U中的樣本，標圓圈的則是丟棄的冗餘樣本。

用這一原型U做1NN分類，我們得到如下結果：

與上面使用完整訓練集得1NN相比，原型U的分類性能並不差。同時，原型U中的樣本數只佔完整訓練集的15%-20%

六、簡單實現（python）

def KNN(input, dataSet, labels, k):# 計算距離 dataSetSize = dataSet.shape[0] # 計算每個維度上的坐標差 difference matrix diffMat = tile(input, (dataSetSize,1)) - dataSet # 這裡用L2距離, 計算平方後的各維度坐標差 squared difference matrix sqDiffMat = diffMat**2 #求和, squared distance sqDistances = sqDiffMat.sum(axis=1) #開根號, distance distances = sqDistances**0.5 # 排序 sortedDistIndicies = distances.argsort() classCount={} # 投票 for i in range(k): voteIlabel = labels[sortedDistIndicies[i]] classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0]

這段代碼使用L2距離

$d (I1, I2) = sqrt{sum{p} left( I^p1 - I^p_2 ight)^2}$

輸入為要判斷的點input、給定點dataSet，給定屬性labels，以及超參數K

輸出為經過投票後得票最高的屬性。

七、總結與討論

在本文中，我們討論了從最近鄰到K-最近鄰的升級、介紹了為了減少密集敵對樣本影響的加權KNN、淺談了距離度量方法的選擇，之後是數據預處理，包括歸一化和精簡數據，最後，我們給出了實現最簡單KNN的一段代碼。

KNN是機器學習中相對簡單的一個入門演算法，他原理相對簡單，但使用時需要存儲大量樣本（即使有數據精簡），而且計算成本很高。他沒有顯式的訓練過程，是一種「懶惰學習」。這個演算法最初由Cover和Hart於1968年提出，歷史久遠，但是仍能應用在當今的很多實際問題上，並且性能不差：他的泛化錯誤率不超過貝葉斯最優分類器錯誤率的兩倍。