數據挖掘十大算法--K近鄰算法

k-近鄰算法是基于實例的學習方法中最基本的，先介紹基于實例學習的相關概念。

一、基于實例的學習。

1、已知一系列的訓練樣例，很多學習方法為目標函數建立起明確的一般化描述；但與此不同，基于實例的學習方法只是簡單地把訓練樣例存儲起來。

從這些實例中泛化的工作被推遲到必須分類新的實例時。每當學習器遇到一個新的查詢實例，它分析這個新實例與以前存儲的實例的關系，并據此把一個目標函數值賦給新實例。

2、基于實例的方法可以為不同的待分類查詢實例建立不同的目標函數逼近。事實上，很多技術只建立目標函數的局部逼近，將其應用于與新查詢實例鄰近的實例，而從不建立在整個實例空間上都表現良好的逼近。當目標函數很復雜，但它可用不太復雜的局部逼近描述時，這樣做有顯著的優勢。

3、基于實例方法的不足：

     （1）分類新實例的開銷可能很大。這是因為幾乎所有的計算都發生在分類時，而不是在第一次遇到訓練樣例時。所以，如何有效地索引訓練樣例，以減少查詢時所需計算是一個重要的實踐問題。

    （2）當從存儲器中檢索相似的訓練樣例時，它們一般考慮實例的所有屬性。如果目標概念僅依賴于很多屬性中的幾個時，那么真正最“相似”的實例之間很可能相距甚遠。

二、k-近鄰法

基于實例的學習方法中最基本的是k-近鄰算法。這個算法假定所有的實例對應于n維歐氏空間?ⁿ中的點。一個實例的最近鄰是根據標準歐氏距離定義的。更精確地講，把任意的實例x表示為下面的特征向量：

                                               <a₁(x)，a₂(x)，...，a_n(x)>

其中a_r(x)表示實例x的第r個屬性值。那么兩個實例x_i和x_j間的距離定義為d(x_i,x_j)，其中：

說明：

1、在最近鄰學習中，目標函數值可以為離散值也可以為實值。

2、我們先考慮學習以下形式的離散目標函數。其中V是有限集合{v_1，...v_s}。下表給出了逼近離散目標函數的k-近鄰算法。

3、正如下表中所指出的，這個算法的返回值f'(x_q)為對f(x_q)的估計，它就是距離x_q最近的k個訓練樣例中最普遍的f值。

4、如果我們選擇k=1，那么“1-近鄰算法”就把f(x_i)賦給(x_q)，其中x_i是最靠近x_q的訓練實例。對于較大的k值，這個算法返回前k個最靠近的訓練實例中最普遍的f值。

逼近離散值函數f: ?^n_V的k-近鄰算法

下圖圖解了一種簡單情況下的k-近鄰算法，在這里實例是二維空間中的點，目標函數具有布爾值。正反訓練樣例用“+”和“-”分別表示。圖中也畫出了一個查詢點x_q。注意在這幅圖中，1-近鄰算法把x_q分類為正例，然而5-近鄰算法把x_q分類為反例。

圖解說明：左圖畫出了一系列的正反訓練樣例和一個要分類的查詢實例x_q。1-近鄰算法把x_q分類為正例，然而5-近鄰算法把x_q分類為反例。

                    右圖是對于一個典型的訓練樣例集合1-近鄰算法導致的決策面。圍繞每個訓練樣例的凸多邊形表示最靠近這個點的實例空間（即這個空間中的實例會被1-近鄰算法賦予該訓練樣例所屬的分類）。

對前面的k-近鄰算法作簡單的修改后，它就可被用于逼近連續值的目標函數。為了實現這一點，我們讓算法計算k個最接近樣例的平均值，而不是計算其中的最普遍的值。更精確地講，為了逼近一個實值目標函數，我們只要把算法中的公式替換為：

三、距離加權最近鄰算法

對k-近鄰算法的一個顯而易見的改進是對k個近鄰的貢獻加權，根據它們相對查詢點x_q的距離，將較大的權值賦給較近的近鄰。

例如，在上表逼近離散目標函數的算法中，我們可以根據每個近鄰與x_q的距離平方的倒數加權這個近鄰的“選舉權”。

方法是通過用下式取代上表算法中的公式來實現：

其中

為了處理查詢點x_q恰好匹配某個訓練樣例x_i，從而導致分母為0的情況，我們令這種情況下的f '(x_q)等于f(x_i)。如果有多個這樣的訓練樣例，我們使用它們中占多數的分類。

我們也可以用類似的方式對實值目標函數進行距離加權，只要用下式替換上表的公式：

其中w_i的定義與之前公式中相同。

注意這個公式中的分母是一個常量，它將不同權值的貢獻歸一化（例如，它保證如果對所有的訓練樣例x_i，f(x_i)=c，那么(x_q)<--c）。

注意以上k-近鄰算法的所有變體都只考慮k個近鄰以分類查詢點。如果使用按距離加權，那么允許所有的訓練樣例影響x_q的分類事實上沒有壞處，因為非常遠的實例對(x_q)的影響很小。考慮所有樣例的惟一不足是會使分類運行得更慢。如果分類一個新的查詢實例時考慮所有的訓練樣例，我們稱此為全局（global）法。如果僅考慮最靠近的訓練樣例，我們稱此為局部（local）法。

四、對k-近鄰算法的說明

按距離加權的k-近鄰算法是一種非常有效的歸納推理方法。它對訓練數據中的噪聲有很好的魯棒性，而且當給定足夠大的訓練集合時它也非常有效。注意通過取k個近鄰的加權平均，可以消除孤立的噪聲樣例的影響。

1、問題一：近鄰間的距離會被大量的不相關屬性所支配。

          應用k-近鄰算法的一個實踐問題是，實例間的距離是根據實例的所有屬性（也就是包含實例的歐氏空間的所有坐標軸）計算的。這與那些只選擇全部實例屬性的一個子集的方法不同，例如決策樹學習系統。

          比如這樣一個問題：每個實例由20個屬性描述，但在這些屬性中僅有2個與它的分類是有關。在這種情況下，這兩個相關屬性的值一致的實例可能在這個20維的實例空間中相距很遠。結果，依賴這20個屬性的相似性度量會誤導k-近鄰算法的分類。近鄰間的距離會被大量的不相關屬性所支配。這種由于存在很多不相關屬性所導致的難題，有時被稱為維度災難（curse of dimensionality）。最近鄰方法對這個問題特別敏感。

2、解決方法：當計算兩個實例間的距離時對每個屬性加權。

      這相當于按比例縮放歐氏空間中的坐標軸，縮短對應于不太相關屬性的坐標軸，拉長對應于更相關的屬性的坐標軸。每個坐標軸應伸展的數量可以通過交叉驗證的方法自動決定。

3、問題二：應用k-近鄰算法的另外一個實踐問題是如何建立高效的索引。因為這個算法推遲所有的處理，直到接收到一個新的查詢，所以處理每個新查詢可能需要大量的計算。

4、解決方法：目前已經開發了很多方法用來對存儲的訓練樣例進行索引，以便在增加一定存儲開銷情況下更高效地確定最近鄰。一種索引方法是kd-tree（Bentley 1975；Friedman et al. 1977），它把實例存儲在樹的葉結點內，鄰近的實例存儲在同一個或附近的結點內。通過測試新查詢x_q的選定屬性，樹的內部結點把查詢x_q排列到相關的葉結點。

python和java版本代碼講解和下載

來自： http://blog.csdn.net//u011067360/article/details/23941577