數據挖掘十大經典算法之K最近鄰算法

k-最近鄰算法是基于實例的學習方法中最基本的，先介紹基于實例學習的相關概念。
    基于實例的學習
    1.已知一系列的訓練樣例，很多學習方法為目標函數建立起明確的一般化描述；但與此不同，基于實例的學習方法只是簡單地把訓練樣例存儲起來。
    從這些實例中泛化的工作被推遲到必須分類新的實例時。每當學習器遇到一個新的查詢實例，它分析這個新實例與以前存儲的實例的關系，并據此把一個目標函數值賦給新實例。
    2.基于實例的方法可以為不同的待分類查詢實例建立不同的目標函數逼近。事實上，很多技術只建立目標函數的局部逼近，將其應用于與新查詢實例鄰近的實 例，而從 不建立在整個實例空間上都表現良好的逼近。當目標函數很復雜，但它可用不太復雜的局部逼近描述時，這樣做有顯著的優勢。
    3.基于實例方法的不足
    分類新實例的開銷可能很大。這是因為幾乎所有的計算都發生在分類時，而不是在第一次遇到訓練樣例時。所以，如何有效地索引訓練樣例，以減少查詢時所需計算是一個重要的實踐問題。
    當從存儲器中檢索相似的訓練樣例時，它們一般考慮實例的所有屬性。如果目標概念僅依賴于很多屬性中的幾個時，那么真正最“相似”的實例之間很可能相距甚遠。
    k-最近鄰法
    算法概述
    K最近鄰（K-Nearest Neighbor,KNN）算法，是著名的模式識別統計學方法，在機器學習分類算法中占有相當大的地位。它是一個理論上比較成熟的方法。既是最簡單的機器學習算法之一，也是基于實例的學習方法中最基本的，又是最好的文本分類算法之一。
    基本思想
    如果一個實例在特征空間中的K個最相似（即特征空間中最近鄰）的實例中的大多數屬于某一個類別，則該實例也屬于這個類別。所選擇的鄰居都是已經正確分類的實例。
    該算法假定所有的實例對應于N維歐式空間？n中的點。通過計算一個點與其他所有點之間的距離，取出與該點最近的K個點，然后統計這K個點里面所屬分類比例最大的，則這個點屬于該分類。
    該算法涉及3個主要因素：實例集、距離或相似的衡量、k的大小。
    一個實例的最近鄰是根據標準歐氏距離定義的。更精確地講，把任意的實例x表示為下面的特征向量：
    <a1（x），a2（x），…，an（x）>
    其中ar（x）表示實例x的第r個屬性值。那么兩個實例xi和xj間的距離定義為d（xi,xj），其中：
    d（xi,xj）=∑r=1n（ar（xi）？ar（xj））2?????????????????√

有關KNN算法的幾點說明：
    1.在最近鄰學習中，目標函數值可以為離散值也可以為實值。
    2.我們先考慮學習以下形式的離散目標函數。其中V是有限集合{v1,…，vs}。下表給出了逼近離散目標函數的k-近鄰算法。
    3.正如下表中所指出的，這個算法的返回值f′（xq）為對f（xq）的估計，它就是距離xq最近的k個訓練樣例中最普遍的f值。
    4.如果我們選擇k=1，那么“1-近鄰算法”就把f（xi）賦給（xq），其中xi是最靠近xq的訓練實例。對于較大的k值，這個算法返回前k個最靠近的訓練實例中最普遍的f值。
    逼近離散值函數f:?n?V的k-近鄰算法
    訓練算法：
    對于每個訓練樣例<x,f（x）>，把這個樣例加入列表training_examples
    分類算法：
    給定一個要分類的查詢實例xq
    在training_examples中選出最靠近xq的k個實例，并用x1,…，xk表示
    返回
    其中如果a=b那么d（a,b）=1，否則d（a,b）=0
    簡單來說，KNN可以看成：有那么一堆你已經知道分類的數據，然后當一個新數據進入的時候，就開始跟訓練數據里的每個點求距離，然后挑離這個訓練數據最近的K個點看看這幾個點屬于什么類型，然后用少數服從多數的原則，給新數據歸類。

KNN算法的決策過程
    下圖中有兩種類型的樣本數據，一類是藍色的正方形，另一類是紅色的三角形，中間那個綠色的圓形是待分類數據：
    如果K=3，那么離綠色點最近的有2個紅色的三角形和1個藍色的正方形，這三個點進行投票，于是綠色的待分類點就屬于紅色的三角形。而如果K=5，那么離綠色點最近的有2個紅色的三角形和3個藍色的正方形，這五個點進行投票，于是綠色的待分類點就屬于藍色的正方形。
    下圖則圖解了一種簡單情況下的k-最近鄰算法，在這里實例是二維空間中的點，目標函數具有布爾值。正反訓練樣例用“+”和“-”分別表示。圖中也畫出了一個查詢點xq。注意在這幅圖中，1-近鄰算法把xq分類為正例，然而5-近鄰算法把xq分類為反例。

圖解說明：左圖畫出了一系列的正反訓練樣例和一個要分類的查詢實例xq。1-近鄰算法把xq分類為正例，然而5-近鄰算法把xq分類為反例。
    右圖是對于一個典型的訓練樣例集合1-近鄰算法導致的決策面。圍繞每個訓練樣例的凸多邊形表示最靠近這個點的實例空間（即這個空間中的實例會被1-近鄰算法賦予該訓練樣例所屬的分類）。
    對前面的k-近鄰算法作簡單的修改后，它就可被用于逼近連續值的目標函數。為了實現這一點，我們讓算法計算k個最接近樣例的平均值，而不是計算其中的最普遍的值。更精確地講，為了逼近一個實值目標函數f:Rn?R，我們只要把算法中的公式替換為：
    f（xq）？∑ki=1f（xi）k
    針對傳統KNN算法的改進
    1.快速KNN算法。參考FKNN論述文獻（實際應用中結合lucene）
    2.加權歐氏距離公式。在傳統的歐氏距離中，各特征的權重相同，也就是認定各個特征對于分類的貢獻是相同的，顯然這是不符合實際情況的。同等的權重使 得特征向量之間相似度計算不夠準確， 進而影響分類精度。加權歐氏距離公式，特征權重通過靈敏度方法獲得（根據業務需求調整，例如關鍵字加權、詞性加權等）
    距離加權最近鄰算法
    對k-最近鄰算法的一個顯而易見的改進是對k個近鄰的貢獻加權，根據它們相對查詢點xq的距離，將較大的權值賦給較近的近鄰。
    例如，在上表逼近離散目標函數的算法中，我們可以根據每個近鄰與xq的距離平方的倒數加權這個近鄰的“選舉權”。
    方法是通過用下式取代上表算法中的公式來實現：
    f（xq）？argmaxv∈V∑i=1kwiδ（v,f（xi））
    其中
    wi≡1d（xq,xi）2
    為了處理查詢點xq恰好匹配某個訓練樣例xi，從而導致分母為0的情況，我們令這種情況下的f′（xq）等于f（xi）。如果有多個這樣的訓練樣例，我們使用它們中占多數的分類。
    我們也可以用類似的方式對實值目標函數進行距離加權，只要用下式替換上表的公式：
    f（xq）？∑ki=1wif（xi）∑ki=1wi
    其中wi的定義與之前公式中相同。
    注意這個公式中的分母是一個常量，它將不同權值的貢獻歸一化（例如，它保證如果對所有的訓練樣例xi，f（xi）=c，那么（xq）←c）。
    注意以上k-近鄰算法的所有變體都只考慮k個近鄰以分類查詢點。如果使用按距離加權，那么允許所有的訓練樣例影響xq的分類事實上沒有壞處，因為非常遠的實例對（xq）的影響很小?？紤]所有樣例的惟一不足是會使分類運行得更慢。如果分類一個新的查詢實例時考慮所有的訓練樣例，我們稱此為全局（global）法。如果僅考慮最靠近的訓練樣例，我們稱此為局部（local）法。
    四、KNN的優缺點
    （1）優點
    ①簡單，易于理解，易于實現，無需參數估計，無需訓練；
    ②精度高，對異常值不敏感（個別噪音數據對結果的影響不是很大）；
    ③適合對稀有事件進行分類；
    ④特別適合于多分類問題（multi-modal,對象具有多個類別標簽），KNN要比SVM表現要好。
    （2）缺點
    ①對測試樣本分類時的計算量大，空間開銷大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本；
    ②可解釋性差，無法給出決策樹那樣的規則；
    ③最大的缺點是當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多 數。該算法只計算“最近的”鄰居樣本，某一類的樣本數量很大，那么或者這類樣本并不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量并不能影響 運行結果?？梢圆捎脵嘀档姆椒ǎê驮摌颖揪嚯x小的鄰居權值大）來改進；
    ④消極學習方法。
    五、對k-近鄰算法的說明
    按距離加權的k-近鄰算法是一種非常有效的歸納推理方法。它對訓練數據中的噪聲有很好的魯棒性，而且當給定足夠大的訓練集合時它也非常有效。注意通過取k個近鄰的加權平均，可以消除孤立的噪聲樣例的影響。
    問題一：近鄰間的距離會被大量的不相關屬性所支配。
    應用k-近鄰算法的一個實踐問題是，實例間的距離是根據實例的所有屬性（也就是包含實例的歐氏空間的所有坐標軸）計算的。這與那些只選擇全部實例屬性的一個子集的方法不同，例如決策樹學習系統。
    比如這樣一個問題：每個實例由20個屬性描述，但在這些屬性中僅有2個與它的分類是有關。在這種情況下，這兩個相關屬性的值一致的實例可能在這個20維的 實例空間中相距很遠。結果，依賴這20個屬性的相似性度量會誤導k-近鄰算法的分類。近鄰間的距離會被大量的不相關屬性所支配。這種由于存在很多不相關屬 性所導致的難題，有時被稱為維度災難（curse of dimensionality）。最近鄰方法對這個問題特別敏感。
    解決方法：當計算兩個實例間的距離時對每個屬性加權。
    這相當于按比例縮放歐氏空間中的坐標軸，縮短對應于不太相關屬性的坐標軸，拉長對應于更相關的屬性的坐標軸。每個坐標軸應伸展的數量可以通過交叉驗證的方法自動決定。
    問題二：應用k-近鄰算法的另外一個實踐問題是如何建立高效的索引。因為這個算法推遲所有的處理，直到接收到一個新的查詢，所以處理每個新查詢可能需要大量的計算。
    解決方法：目前已經開發了很多方法用來對存儲的訓練樣例進行索引，以便在增加一定存儲開銷情況下更高效地確定最近鄰。 一種索引方法是kd-tree（Bentley 1975；Friedman et al. 1977），它把實例存儲在樹的葉結點內，鄰近的實例存儲在同一個或附近的結點內。通過測試新查詢xq的選定屬性，樹的內部結點把查詢xq排列到相關的葉 結點。
    Python實現KNN算法
    這里實現一個手寫識別算法，這里只簡單識別0~9數字。
    輸入：每個手寫數字已經事先處理成32*32的二進制文本，存儲為txt文件。每個數字大約有200個樣本。每個樣本保持在一個txt文件中。手寫體圖像 本身的大小是32x32的二值圖，轉換到txt文件保存后，內容也是32x32個數字，如下圖所示。目錄trainingDigits存放的是大約 2000個訓練數據，testDigits存放大約900個測試數據。
    函數img2vector：用來生成將每個樣本的txt文件轉換為對應的一個向量

    # convert image to vector

    def  img2vector（filename）：

    rows = 32

    cols = 32

    imgVector = zeros（（1, rows * cols））

    fileIn = open（filename）

    for row in xrange（rows）：

    lineStr = fileIn.readline（）

    for col in xrange（cols）：

    imgVector[0, row * 32 + col] = int（lineStr[col]）

    return imgVector
    函數loadDDataSet：加載整個數據庫

    # load dataSet

    def loadDataSet（）：

    ## step 1: Getting training set

    print "---Getting training set…"

    dataSetDir = './'

    trainingFileList = os.listdir（dataSetDir + 'trainingDigits'） # load the training set

    numSamples = len（trainingFileList）

    train_x = zeros（（numSamples, 1024））

    train_y = []

    for i in xrange（numSamples）：

    filename = trainingFileList[i]

    # get train_x

    train_x[i, :] = img2vector（dataSetDir + 'trainingDigits/%s' % filename）

    # get label from file name such as "1_18.txt"

    label = int（filename.split（'_'）[0]） # return 1

    train_y.append（label）

    ## step 2: Getting testing set

    print "---Getting testing set…"

    testingFileList = os.listdir（dataSetDir + 'testDigits'） # load the testing set

    numSamples = len（testingFileList）

    test_x = zeros（（numSamples, 1024））

    test_y = []

    for i in xrange（numSamples）：

    filename = testingFileList[i]

    # get train_x

    test_x[i, :] = img2vector（dataSetDir + 'testDigits/%s' % filename）

    # get label from file name such as "1_18.txt"

    label = int（filename.split（'_'）[0]） # return 1

    test_y.append（label）

    return train_x, train_y, test_x, test_y
    函數kNNClassify:實現kNN分類算法

    # classify using kNN

    def kNNClassify（newInput, dataSet, labels, k）：

    numSamples = dataSet.shape[0] # shape[0] stands for the num of row

    ## step 1: calculate Euclidean distance

    # tile（A, reps）： Construct an array by repeating A reps times

    # the following copy numSamples rows for dataSet

    diff = tile（newInput, （numSamples, 1）） - dataSet # Subtract element-wise

    squaredDiff = diff ** 2 # squared for the subtract

    squaredDist = sum（squaredDiff, axis = 1） # sum is performed by row

    distance = squaredDist ** 0.5

    ## step 2: sort the distance

    # argsort（） returns the indices that would sort an array in a ascending order

    sortedDistIndices = argsort（distance）

    classCount = {} # define a dictionary （can be append element）

    for i in xrange（k）：

    ## step 3: choose the min k distance

    voteLabel = labels[sortedDistIndices[i]]

    ## step 4: count the times labels occur

    # when the key voteLabel is not in dictionary classCount, get（）

    # will return 0

    classCount[voteLabel] = classCount.get（voteLabel, 0） + 1

    ## step 5: the max voted class will return

    maxCount = 0

    for key, value in classCount.items（）：

    if value > maxCount:

    maxCount = value

    maxIndex = key

    return maxIndex
    函數testHandWritingClass:測試函數

    # test hand writing class

    def testHandWritingClass（）：

    ## step 1: load data

    print "step 1: load data…"

    train_x, train_y, test_x, test_y = loadDataSet（）

    ## step 2: training…

    print "step 2: training…"

    pass

    ## step 3: testing

    print "step 3: testing…"

    numTestSamples = test_x.shape[0]

    matchCount = 0

    for i in xrange（numTestSamples）：

    predict = kNNClassify（test_x[i], train_x, train_y, 3）

    if predict == test_y[i]:

    matchCount += 1

    accuracy = float（matchCount） / numTestSamples

    ## step 4: show the result

    print "step 4: show the result…"

    print 'The classify accuracy is: %.2f%%' % （accuracy * 100）

    似性度量
    相似性一般用空間內兩個點的距離來度量。距離越大，表示兩個越不相似。
    作為相似性度量的距離函數一般滿足下列性質：

    d（X,Y）=d（Y,X）；

    d（X,Y）≦d（X,Z）+d（Z,Y）；

    d（X,Y）≧0;

    d（X,Y）=0,當且僅當X=Y;

    這里，X,Y和Z是對應特征空間中的三個點。

    假設X,Y分別是N維特征空間中的一個點，其中X=（x1,x2,…，xn）T,Y=（y1,y2,…，yn）T,d（X,Y）表示相應的距離函數，它給出了X和Y之間的距離測度。

    距離的選擇有很多種，常用的距離函數如下：

    1. 明考斯基（Minkowsky）距離

    d（X,Y）=[∑i=1n∣xi?yi∣λ]1λ，λ一般取整數值，不同的λ取值對應于不同的距離

    1.曼哈頓（Manhattan）距離

    d（X,Y）=∑i=1n∣xi?yi∣，該距離是Minkowsky距離在λ=1時的一個特例

    2.Cityblock距離

    d（X,Y）=∑i=1nwi∣xi?yi∣，該距離是Manhattan距離的加權修正，其中wi,i=1,2,…，n是權重因子

    3.歐幾里德（Euclidean）距離（歐式距離）

    d（X,Y）=[∑i=1n∣xi?yi∣2]12=（X?Y）（X?Y）T??????????????√，是Minkowsky距離在λ=2時的特例

    4.Canberra距離

    d（X,Y）=∑i=1nxi?yixi+yi
    （6）Mahalanobis距離（馬式距離）
    d（X,M）=（X?M）TΣ？1（X?M）？？？？？？？？？？？？？？？？？？√
    d（X,M）給出了特征空間中的點X和M之間的一種距離測度，其中M為某一個模式類別的均值向量，∑為相應模式類別的協方差矩陣。
    該距離測度考慮了以M為代表的模式類別在特征空間中的總體分布，能夠緩解由于屬性的線性組合帶來的距離失真。易見，到M的馬式距離為常數的點組成特征空間中的一個超橢球面。
    1.切比雪夫（Chebyshev）距離
    d（X,Y）=maxi（∣xi?yi∣）
    L∞=limk→∞（∑i=1k∣xi?yi∣k）1k
    切比雪夫距離或是L∞度量是向量空間中的一種度量，二個點之間的距離定義為其各坐標數值差的最大值。在二維空間中。以（x1,y1）和（x2,y2）二點為例，其切比雪夫距離為
    d=max（∣x2?x1∣，∣y2?y1∣）
    切比雪夫距離或是L∞度量是向量空間中的一種度量，二個點之間的距離定義為其各坐標數值差的最大值。在二維空間中。以（x1,y1）和（x2,y2）二點為例，其切比雪夫距離為
    d=max（|x2?x1|,|y2?y1|）
    2.平均距離
    daverage=[1n∑i=1n（xi?yi）2]12
    消極學習與積極學習
    1.積極學習（Eager Learning）
    這種學習方式是指在進行某種判斷（例如，確定一個點的分類或者回歸中確定某個點對應的函數值）之前，先利用訓練數據進行訓練得到一個目標函數，待需要時就只利用訓練好的函數進行決策，顯然這是一種一勞永逸的方法，SVM就屬于這種學習方式。
    2.消極學習（Lazy Learning）
    這種學習方式指不是根據樣本建立一般化的目標函數并確定其參數，而是簡單地把訓練樣本存儲起來，直到需要分類新的實例時才分析其與所存儲樣例的關系，據此 確定新實例的目標函數值。也就是說這種學習方式只有到了需要決策時才會利用已有數據進行決策，而在這之前不會經歷 Eager Learning所擁有的訓練過程。KNN就屬于這種學習方式。
    3.比較
    Eager Learning考慮到了所有訓練樣本，說明它是一個全局的近似，雖然它需要耗費訓練時間，但它的決策時間基本為0.
    Lazy Learning在決策時雖然需要計算所有樣本與查詢點的距離，但是在真正做決策時卻只用了局部的幾個訓練數據，所以它是一個局部的近似，然而雖然不需要 訓練，它的復雜度還是需要 O（n），n 是訓練樣本的個數。由于每次決策都需要與每一個訓練樣本求距離，這引出了Lazy Learning的缺點：（1）需要的存儲空間比較大 （2）決策過程比較慢。
    4.典型算法
    積極學習方法：SVM;Find-S算法；候選消除算法；決策樹；人工神經網絡；貝葉斯方法；
    消極學習方法：KNN;局部加權回歸；基于案例的推理；