數(shù)據(jù)挖掘十大經(jīng)典算法之K最近鄰算法

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

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

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

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

    # 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
    函數(shù)loadDDataSet：加載整個數(shù)據(jù)庫

    # 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
    函數(shù)kNNClassify:實現(xiàn)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
    函數(shù)testHandWritingClass:測試函數(shù)

    # 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）

    似性度量
    相似性一般用空間內(nèi)兩個點的距離來度量。距離越大，表示兩個越不相似。
    作為相似性度量的距離函數(shù)一般滿足下列性質(zhì)：

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

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

    d（X,Y）≧0;

    d（X,Y）=0,當(dāng)且僅當(dāng)X=Y;

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

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

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

    1. 明考斯基（Minkowsky）距離

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

    1.曼哈頓（Manhattan）距離

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

    2.Cityblock距離

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