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

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

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

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

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

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

    # 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:實(shí)現(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:測(cè)試函數(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)兩個(gè)點(diǎn)的距離來(lái)度量。距離越大，表示兩個(gè)越不相似。
    作為相似性度量的距離函數(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是對(duì)應(yīng)特征空間中的三個(gè)點(diǎn)。

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

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

    1. 明考斯基（Minkowsky）距離

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

    1.曼哈頓（Manhattan）距離

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

    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時(shí)的特例

    4.Canberra距離

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