# K近鄰算法 ### 1.1、什么是K近鄰算法 何謂K近鄰算法，即K-Nearest Neighbor algorithm，簡稱KNN算法，單從名字來猜想，可以簡單粗暴的認為是：K個最近的鄰居，當K=1時，算法便成了最近鄰算法，即尋找最近的那個鄰居。為何要找鄰居？打個比方來說，假設你來到一個陌生的村莊，現在你要找到與你有著相似特征的人群融入他們，所謂入伙。 用官方的話來說，所謂K近鄰算法，即是給定一個訓練數據集，對新的輸入實例，在訓練數據集中找到與該實例最鄰近的K個實例（也就是上面所說的K個鄰居），這K個實例的多數屬于某個類，就把該輸入實例分類到這個類中。根據這個說法，咱們來看下引自維基百科上的一幅圖：  如上圖所示，有兩類不同的樣本數據，分別用藍色的小正方形和紅色的小三角形表示，而圖正中間的那個綠色的圓所標示的數據則是待分類的數據。也就是說，現在，我們不知道中間那個綠色的數據是從屬于哪一類（藍色小正方形or紅色小三角形），下面，我們就要解決這個問題：給這個綠色的圓分類。 * 我們常說，物以類聚，人以群分，判別一個人是一個什么樣品質特征的人，常常可以從他/她身邊的朋友入手，所謂觀其友，而識其人。我們不是要判別上圖中那個綠色的圓是屬于哪一類數據么，好說，從它的鄰居下手。但一次性看多少個鄰居呢？從上圖中，你還能看到： * 如果K=3，綠色圓點的最近的3個鄰居是2個紅色小三角形和1個藍色小正方形，少數從屬于多數，基于統計的方法，判定綠色的這個待分類點屬于紅色的三角形一類。 如果K=5，綠色圓點的最近的5個鄰居是2個紅色三角形和3個藍色的正方形，還是少數從屬于多數，基于統計的方法，判定綠色的這個待分類點屬于藍色的正方形一類。 于此我們看到，當無法判定當前待分類點是從屬于已知分類中的哪一類時，我們可以依據統計學的理論看它所處的位置特征，衡量它周圍鄰居的權重，而把它歸為(或分配)到權重更大的那一類。這就是K近鄰算法的核心思想。 ### 1.2、近鄰的距離度量表示法 上文第一節，我們看到，K近鄰算法的核心在于找到實例點的鄰居，這個時候，問題就接踵而至了，如何找到鄰居，鄰居的判定標準是什么，用什么來度量。這一系列問題便是下面要講的距離度量表示法。但有的讀者可能就有疑問了，我是要找鄰居，找相似性，怎么又跟距離扯上關系了？ 這是因為特征空間中兩個實例點的距離和反應出兩個實例點之間的相似性程度。K近鄰模型的特征空間一般是n維實數向量空間，使用的距離可以使歐式距離，也是可以是其它距離，既然扯到了距離，下面就來具體闡述下都有哪些距離度量的表示法，權當擴展。 1.**歐氏距離**，最常見的兩點之間或多點之間的距離表示法，又稱之為歐幾里得度量，它定義于歐幾里得空間中，如點 x = (x1,...,xn) 和 y = (y1,...,yn) 之間的距離為：  (1)二維平面上兩點a(x1,y1)與b(x2,y2)間的歐氏距離：  (2)三維空間兩點a(x1,y1,z1)與b(x2,y2,z2)間的歐氏距離：  (3)兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的歐氏距離：  也可以用表示成向量運算的形式：  其上，二維平面上兩點歐式距離，代碼可以如下編寫： ```cpp //unixfy：計算歐氏距離 double euclideanDistance(const vector<double>& v1, const vector<double>& v2) { assert(v1.size() == v2.size()); double ret = 0.0; for (vector<double>::size_type i = 0; i != v1.size(); ++i) { ret += (v1[i] - v2[i]) * (v1[i] - v2[i]); } return sqrt(ret); } ``` 2.**曼哈頓距離**，我們可以定義曼哈頓距離的正式意義為L1-距離或城市區塊距離，也就是在歐幾里得空間的固定直角坐標系上兩點所形成的線段對軸產生的投影的距離總和。例如在平面上，坐標（x1, y1）的點P1與坐標（x2, y2）的點P2的曼哈頓距離為：，要注意的是，曼哈頓距離依賴座標系統的轉度，而非系統在座標軸上的平移或映射。 通俗來講，想象你在曼哈頓要從一個十字路口開車到另外一個十字路口，駕駛距離是兩點間的直線距離嗎？顯然不是，除非你能穿越大樓。而實際駕駛距離就是這個“曼哈頓距離”，此即曼哈頓距離名稱的來源， 同時，曼哈頓距離也稱為城市街區距離(City Block distance)。 (1)二維平面兩點a(x1,y1)與b(x2,y2)間的曼哈頓距離  (2)兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的曼哈頓距離  3.**切比雪夫距離**，若二個向量或二個點p 、and q，其座標分別為及，則兩者之間的切比雪夫距離定義如下：， 這也等于以下Lp度量的極值：，因此切比雪夫距離也稱為L∞度量。 以數學的觀點來看，切比雪夫距離是由一致范數（uniform norm）（或稱為上確界范數）所衍生的度量，也是超凸度量（injective metric space）的一種。 在平面幾何中，若二點p及q的直角坐標系坐標為及，則切比雪夫距離為：。 玩過國際象棋的朋友或許知道，國王走一步能夠移動到相鄰的8個方格中的任意一個。那么國王從格子(x1,y1)走到格子(x2,y2)最少需要多少步？。你會發現最少步數總是max( | x2-x1 | , | y2-y1 | ) 步 。有一種類似的一種距離度量方法叫切比雪夫距離。 (1)二維平面兩點a(x1,y1)與b(x2,y2)間的切比雪夫距離  (2)兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的切比雪夫距離 　　  這個公式的另一種等價形式是  4.**閔可夫斯基距離(Minkowski Distance)**，閔氏距離不是一種距離，而是一組距離的定義。 (1) 閔氏距離的定義 兩個n維變量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的閔可夫斯基距離定義為：  其中p是一個變參數。 當p=1時，就是曼哈頓距離 當p=2時，就是歐氏距離 當p→∞時，就是切比雪夫距離 根據變參數的不同，閔氏距離可以表示一類的距離。 5.**標準化歐氏距離 (Standardized Euclidean distance)**，標準化歐氏距離是針對簡單歐氏距離的缺點而作的一種改進方案。標準歐氏距離的思路：既然數據各維分量的分布不一樣，那先將各個分量都“標準化”到均值、方差相等。至于均值和方差標準化到多少，先復習點統計學知識。 假設樣本集X的數學期望或均值(mean)為m，標準差(standard deviation，方差開根)為s，那么X的“標準化變量”X*表示為：(X-m）/s，而且標準化變量的數學期望為0，方差為1。 即，樣本集的標準化過程(standardization)用公式描述就是：  標準化后的值 = ( 標準化前的值 － 分量的均值 ) /分量的標準差　　 經過簡單的推導就可以得到兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的標準化歐氏距離的公式：  如果將方差的倒數看成是一個權重，這個公式可以看成是一種加權歐氏距離(Weighted Euclidean distance)。 6.**馬氏距離(Mahalanobis Distance)** （1）馬氏距離定義 有M個樣本向量X1~Xm，[協方差矩陣](http://zh.wikipedia.org/wiki/%E5%8D%8F%E6%96%B9%E5%B7%AE%E7%9F%A9%E9%98%B5)記為S，均值記為向量μ，則其中樣本向量X到u的馬氏距離表示為：  （協方差矩陣中每個元素是各個矢量元素之間的協方差Cov(X,Y)，Cov(X,Y) = E{ [X-E(X)] [Y-E(Y)]}，其中E為數學期望） 而其中向量Xi與Xj之間的馬氏距離定義為：  若協方差矩陣是單位矩陣（各個樣本向量之間獨立同分布）,則公式就成了：  也就是歐氏距離了。 若協方差矩陣是對角矩陣，公式變成了標準化歐氏距離。 (2)馬氏距離的優缺點：量綱無關，排除變量之間的相關性的干擾。 「微博上的seafood高清版點評道：原來馬氏距離是根據協方差矩陣演變，一直被老師誤導了，怪不得看Killian在05年NIPS發表的LMNN論文時候老是看到協方差矩陣和半正定，原來是這回事」 7.**巴氏距離（Bhattacharyya Distance）**，在統計中，Bhattacharyya距離測量兩個離散或連續概率分布的相似性。它與衡量兩個統計樣品或種群之間的重疊量的Bhattacharyya系數密切相關。Bhattacharyya距離和Bhattacharyya系數以20世紀30年代曾在印度統計研究所工作的一個統計學家A. Bhattacharya命名。同時，Bhattacharyya系數可以被用來確定兩個樣本被認為相對接近的，它是用來測量中的類分類的可分離性。 （1）巴氏距離的定義 對于離散概率分布 p和q在同一域 X，它被定義為：  其中：  是Bhattacharyya系數。 對于連續概率分布，Bhattacharyya系數被定義為：  在這兩種情況下，巴氏距離并沒有服從三角不等式.（值得一提的是，Hellinger距離不服從三角不等式）。 對于多變量的高斯分布，， 和是手段和協方差的分布。 需要注意的是，在這種情況下，第一項中的Bhattacharyya距離與馬氏距離有關聯。 （2）Bhattacharyya系數 Bhattacharyya系數是兩個統計樣本之間的重疊量的近似測量，可以被用于確定被考慮的兩個樣本的相對接近。 計算Bhattacharyya系數涉及集成的基本形式的兩個樣本的重疊的時間間隔的值的兩個樣本被分裂成一個選定的分區數，并且在每個分區中的每個樣品的成員的數量，在下面的公式中使用  考慮樣品a 和 b ，n是的分區數，并且，被一個 和 b i的日分區中的樣本數量的成員。更多介紹請參看：<http://en.wikipedia.org/wiki/Bhattacharyya_coefficient>。 8.**漢明距離(Hamming distance)**， 兩個等長字符串s1與s2之間的漢明距離定義為將其中一個變為另外一個所需要作的最小替換次數。例如字符串“1111”與“1001”之間的漢明距離為2。應用：信息編碼（為了增強容錯性，應使得編碼間的最小漢明距離盡可能大）。 或許，你還沒明白我再說什么，不急，看下上篇blog中第78題的第3小題整理的一道面試題目，便一目了然了。如下圖所示：  ``` cpp //動態規劃： //f[i,j]表示s[0...i]與t[0...j]的最小編輯距離。 f[i,j] = min { f[i-1,j]+1, f[i,j-1]+1, f[i-1,j-1]+(s[i]==t[j]?0:1) } //分別表示：添加1個，刪除1個，替換1個（相同就不用替換）。 ``` 與此同時，面試官還可以繼續問下去：那么，請問，如何設計一個比較兩篇文章相似性的算法？（這個問題的討論可以看看這里：<http://t.cn/zl82CAH>，及這里關于simhash算法的介紹：<http://www.cnblogs.com/linecong/archive/2010/08/28/simhash.html>），接下來，便引出了下文關于夾角余弦的討論。 *（[上篇blog](http://blog.csdn.net/v_july_v/article/details/7974418)中第78題的第3小題給出了多種方法，讀者可以參看之。同時，程序員編程藝術系列第二十八章將詳細闡述這個問題）* 9.**夾角余弦(Cosine)** ，幾何中夾角余弦可用來衡量兩個向量方向的差異，機器學習中借用這一概念來衡量樣本向量之間的差異。 (1)在二維空間中向量A(x1,y1)與向量B(x2,y2)的夾角余弦公式：  (2) 兩個n維樣本點a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夾角余弦  類似的，對于兩個n維樣本點a(x11,x12,…,x1n)和b(x21,x22,…,x2n)，可以使用類似于夾角余弦的概念來衡量它們間的相似程度，即：  夾角余弦取值范圍為[-1,1]。夾角余弦越大表示兩個向量的夾角越小，夾角余弦越小表示兩向量的夾角越大。當兩個向量的方向重合時夾角余弦取最大值1，當兩個向量的方向完全相反夾角余弦取最小值-1。 10.**杰卡德相似系數(Jaccard similarity coefficient)** (1) 杰卡德相似系數 兩個集合A和B的交集元素在A，B的并集中所占的比例，稱為兩個集合的杰卡德相似系數，用符號J(A,B)表示。  杰卡德相似系數是衡量兩個集合的相似度一種指標。 (2) 杰卡德距離 與杰卡德相似系數相反的概念是杰卡德距離(Jaccard distance)。 杰卡德距離可用如下公式表示：  杰卡德距離用兩個集合中不同元素占所有元素的比例來衡量兩個集合的區分度。 (3) 杰卡德相似系數與杰卡德距離的應用 可將杰卡德相似系數用在衡量樣本的相似度上。 舉例：樣本A與樣本B是兩個n維向量，而且所有維度的取值都是0或1，例如：A(0111)和B(1011)。我們將樣本看成是一個集合，1表示集合包含該元素，0表示集合不包含該元素。 M11 ：樣本A與B都是1的維度的個數 M01：樣本A是0，樣本B是1的維度的個數 M10：樣本A是1，樣本B是0 的維度的個數 M00：樣本A與B都是0的維度的個數 依據上文給的杰卡德相似系數及杰卡德距離的相關定義，樣本A與B的杰卡德相似系數J可以表示為：  這里M11+M01+M10可理解為A與B的并集的元素個數，而M11是A與B的交集的元素個數。而樣本A與B的杰卡德距離表示為J'：  11.**皮爾遜系數(Pearson Correlation Coefficient)** 在具體闡述皮爾遜相關系數之前，有必要解釋下什么是相關系數 ( Correlation coefficient )與相關距離(Correlation distance)。 相關系數 ( Correlation coefficient )的定義是：  (其中，E為數學期望或均值，D為方差，D開根號為標準差，E{ [X-E(X)] [Y-E(Y)]}稱為隨機變量X與Y的協方差，記為Cov(X,Y)，即Cov(X,Y) = E{ [X-E(X)] [Y-E(Y)]}，而兩個變量之間的協方差和標準差的商則稱為隨機變量X與Y的相關系數，記為) 相關系數衡量隨機變量X與Y相關程度的一種方法，相關系數的取值范圍是[-1,1]。相關系數的絕對值越大，則表明X與Y相關度越高。當X與Y線性相關時，相關系數取值為1（正線性相關）或-1（負線性相關）。 具體的，如果有兩個變量：X、Y，最終計算出的相關系數的含義可以有如下理解： 當相關系數為0時，X和Y兩變量無關系。 當X的值增大（減小），Y值增大（減小），兩個變量為正相關，相關系數在0.00與1.00之間。 當X的值增大（減小），Y值減小（增大），兩個變量為負相關，相關系數在-1.00與0.00之間。 相關距離的定義是：  OK，接下來，咱們來重點了解下皮爾遜相關系數。 在統計學中，皮爾遜積矩相關系數（英語：Pearson product-moment correlation coefficient，又稱作 PPMCC或PCCs, 用r表示）用于度量兩個變量X和Y之間的相關（線性相關），其值介于-1與1之間。 通常情況下通過以下取值范圍判斷變量的相關強度： 相關系數 0.8-1.0 極強相關 0.6-0.8 強相關 0.4-0.6 中等程度相關 0.2-0.4 弱相關 0.0-0.2 極弱相關或無相關 在自然科學領域中，該系數廣泛用于度量兩個變量之間的相關程度。它是由卡爾·皮爾遜從弗朗西斯·高爾頓在19世紀80年代提出的一個相似卻又稍有不同的想法演變而來的。這個相關系數也稱作“皮爾森相關系數r”。 **(1)皮爾遜系數的定義**： 兩個變量之間的皮爾遜相關系數定義為兩個變量之間的協方差和標準差的商：  以上方程定義了總體相關系數, 一般表示成希臘字母ρ(rho)。基于樣本對協方差和方差進行估計，可以得到樣本標準差, 一般表示成r：  一種等價表達式的是表示成標準分的均值。基于(Xi, Yi)的樣本點，樣本皮爾遜系數是  其中、及，分別是標準分、樣本平均值和樣本標準差。 或許上面的講解令你頭腦混亂不堪，沒關系，我換一種方式講解，如下： 假設有兩個變量X、Y，那么兩變量間的皮爾遜相關系數可通過以下公式計算： * 公式一： 注：勿忘了上面說過，“皮爾遜相關系數定義為兩個變量之間的協方差和標準差的商”，其中標準差的計算公式為： * 公式二： * 公式三： * 公式四： 以上列出的四個公式等價，其中E是[數學期望](http://zh.wikipedia.org/wiki/%E6%95%B0%E5%AD%A6%E6%9C%9F%E6%9C%9B)，cov表示[協方差](http://zh.wikipedia.org/wiki/%E5%8D%8F%E6%96%B9%E5%B7%AE)，N表示變量取值的個數。 **(2)皮爾遜相關系數的適用范圍** 當兩個變量的標準差都不為零時，相關系數才有定義，皮爾遜相關系數適用于： 1. 兩個變量之間是線性關系，都是連續數據。 2. 兩個變量的總體是正態分布，或接近正態的單峰分布。 3. 兩個變量的觀測值是成對的，每對觀測值之間相互獨立。 **(3)如何理解皮爾遜相關系數** rubyist：皮爾遜相關系數理解有兩個角度 其一, 按照高中數學水平來理解, 它很簡單, 可以看做將兩組數據首先做Z分數處理之后, 然后兩組數據的乘積和除以樣本數，Z分數一般代表正態分布中, 數據偏離中心點的距離.等于變量減掉平均數再除以標準差.(就是高考的標準分類似的處理) 樣本標準差則等于變量減掉平均數的平方和，再除以樣本數，最后再開方，也就是說，方差開方即為標準差，樣本標準差計算公式為：  所以, 根據這個最樸素的理解,我們可以將公式依次精簡為:  其二, 按照大學的線性數學水平來理解, 它比較復雜一點,可以看做是兩組數據的向量夾角的余弦。下面是關于此皮爾遜系數的幾何學的解釋，先來看一幅圖，如下所示：  回歸直線： y=gx(x) [紅色] 和 x=gy(y) [藍色] 如上圖，對于沒有中心化的數據, 相關系數與兩條可能的回歸線y=gx(x) 和 x=gy(y) 夾角的余弦值一致。 對于沒有中心化的數據 (也就是說, 數據移動一個樣本平均值以使其均值為0), 相關系數也可以被視作由兩個隨機變量 向量 夾角 的 余弦值（見下方）。 舉個例子，例如，有5個國家的國民生產總值分別為 10, 20, 30, 50 和 80 億美元。 假設這5個國家 (順序相同) 的貧困百分比分別為 11%, 12%, 13%, 15%, and 18% 。 令 x 和 y 分別為包含上述5個數據的向量: x = (1, 2, 3, 5, 8) 和 y = (0.11, 0.12, 0.13, 0.15, 0.18)。 利用通常的方法計算兩個向量之間的夾角 (參見 數量積), 未中心化 的相關系數是:  我們發現以上的數據特意選定為完全相關: y = 0.10 + 0.01 x。 于是，皮爾遜相關系數應該等于1。將數據中心化 (通過E(x) = 3.8移動 x 和通過 E(y) = 0.138 移動 y ) 得到 x = (?2.8, ?1.8, ?0.8, 1.2, 4.2) 和 y = (?0.028, ?0.018, ?0.008, 0.012, 0.042), 從中  **(4)皮爾遜相關的約束條件** 從以上解釋, 也可以理解皮爾遜相關的約束條件: 1. 兩個變量間有線性關系 2. 變量是連續變量 3. 變量均符合正態分布,且二元分布也符合正態分布 4. 兩變量獨立 在實踐統計中,一般只輸出兩個系數,一個是相關系數,也就是計算出來的相關系數大小,在-1到1之間;另一個是獨立樣本檢驗系數,用來檢驗樣本一致性。 簡單說來，各種“距離”的應用場景簡單概括為，空間：歐氏距離，路徑：曼哈頓距離，國際象棋國王：切比雪夫距離，以上三種的統一形式:閔可夫斯基距離，加權：標準化歐氏距離，排除量綱和依存：馬氏距離，向量差距：夾角余弦，編碼差別：漢明距離，集合近似度：杰卡德類似系數與距離，相關：相關系數與相關距離。 ### 1.3、K值的選擇 除了上述1.2節如何定義鄰居的問題之外，還有一個選擇多少個鄰居，即K值定義為多大的問題。不要小看了這個K值選擇問題，因為它對K近鄰算法的結果會產生重大影響。如李航博士的一書「統計學習方法」上所說： 1. 如果選擇較小的K值，就相當于用較小的領域中的訓練實例進行預測，“學習”近似誤差會減小，只有與輸入實例較近或相似的訓練實例才會對預測結果起作用，與此同時帶來的問題是“學習”的估計誤差會增大，換句話說，K值的減小就意味著整體模型變得復雜，容易發生過擬合； 2. 如果選擇較大的K值，就相當于用較大領域中的訓練實例進行預測，其優點是可以減少學習的估計誤差，但缺點是學習的近似誤差會增大。這時候，與輸入實例較遠（不相似的）訓練實例也會對預測器作用，使預測發生錯誤，且K值的增大就意味著整體的模型變得簡單。 3. K=N，則完全不足取，因為此時無論輸入實例是什么，都只是簡單的預測它屬于在訓練實例中最多的累，模型過于簡單，忽略了訓練實例中大量有用信息。 在實際應用中，K值一般取一個比較小的數值，例如采用[交叉驗證](http://zh.wikipedia.org/zh/%E4%BA%A4%E5%8F%89%E9%A9%97%E8%AD%89)法（簡單來說，就是一部分樣本做訓練集，一部分做測試集）來選擇最優的K值。