總結演算法

⑴ KNN演算法常見問題總結

給定測試實例，基於某種距離度量找出訓練集中與其最靠近的k個實例點，然後基於這k個最近鄰的信息來進行預測。

通常，在分類任務中可使用「投票法」，即選擇這k個實例中出現最多的標記類別作為預測結果；在回歸任務中可使用「平均法」，即將這k個實例的實值輸出標記的平均值作為預測結果；還可基於距離遠近進行加權平均或加權投票，距離越近的實例權重越大。

k近鄰法不具有顯式的學習過程，事實上，它是懶惰學習（lazy learning）的著名代表，此類學習技術在訓練階段僅僅是把樣本保存起來，訓練時間開銷為零，待收到測試樣本後再進行處理。

KNN一般採用歐氏距離，也可採用其他距離度量，一般的Lp距離：

KNN中的K值選取對K近鄰演算法的結果會產生重大影響。如果選擇較小的K值，就相當於用較小的領域中的訓練實例進行預測，「學習」近似誤差（近似誤差：可以理解為對現有訓練集的訓練誤差）會減小，只有與輸入實例較近或相似的訓練實例才會對預測結果起作用，與此同時帶來的問題是「學習」的估計誤差會增大，換句話說，K值的減小就意味著整體模型變得復雜，容易發生過擬合；

如果選擇較大的K值，就相當於用較大領域中的訓練實例進行預測，其優點是可以減少學習的估計誤差，但缺點是學習的近似誤差會增大。這時候，與輸入實例較遠（不相似的）訓練實例也會對預測器作用，使預測發生錯誤，螞肢且K值的增大就意味著整體的模型變得簡單。

在實際螞嘩應用中，K值一般取一個比較小的數值，例如採用交叉驗證法來選擇最優的K值。經驗規則：k一般低於訓練樣本數的平方根

1、計算測試對象到訓練集中每個對象的距離

2、按照距離的遠近排序

3、選取與當前測試對象最近的k的訓練對象，作為該測試對象的鄰居

4、統計這k個鄰居的類別頻率

5、k個鄰悶物行居里頻率最高的類別，即為測試對象的類別

輸入X可以採用BallTree或KDTree兩種數據結構，優化計算效率，可以在實例化KNeighborsClassifier的時候指定。

KDTree

基本思想是，若A點距離B點非常遠，B點距離C點非常近， 可知A點與C點很遙遠，不需要明確計算它們的距離。 通過這樣的方式，近鄰搜索的計算成本可以降低為O[DNlog(N)]或更低。 這是對於暴力搜索在大樣本數N中表現的顯著改善。KD 樹的構造非常快，對於低維度 (D<20) 近鄰搜索也非常快, 當D增長到很大時，效率變低： 這就是所謂的 「維度災難」 的一種體現。

KD 樹是一個二叉樹結構，它沿著數據軸遞歸地劃分參數空間，將其劃分為嵌入數據點的嵌套的各向異性區域。 KD 樹的構造非常快：因為只需沿數據軸執行分區, 無需計算D-dimensional 距離。 一旦構建完成, 查詢點的最近鄰距離計算復雜度僅為O[log(N)]。 雖然 KD 樹的方法對於低維度 (D<20) 近鄰搜索非常快, 當D增長到很大時, 效率變低。

KD樹的特性適合使用歐氏距離。

BallTree

BallTree解決了KDTree在高維上效率低下的問題，這種方法構建的樹要比 KD 樹消耗更多的時間，但是這種數據結構對於高結構化的數據是非常有效的， 即使在高維度上也是一樣。

KD樹是依次對K維坐標軸，以中值切分構造的樹；ball tree 是以質心C和半徑r分割樣本空間，每一個節點是一個超球體。換句簡單的話來說，對於目標空間(q, r)，所有被該超球體截斷的子超球體內的所有子空間都將被遍歷搜索。

BallTree通過使用三角不等式減少近鄰搜索的候選點數:|x+y|<=|x|+|y|通過這種設置, 測試點和質心之間的單一距離計算足以確定距節點內所有點的距離的下限和上限. 由於 ball 樹節點的球形幾何, 它在高維度上的性能超出 KD-tree, 盡管實際的性能高度依賴於訓練數據的結構。

BallTree適用於更一般的距離。

1、優點

非常簡單的分類演算法沒有之一，人性化，易於理解，易於實現

適合處理多分類問題，比如推薦用戶

可用於數值型數據和離散型數據，既可以用來做分類也可以用來做回歸

對異常值不敏感

2、缺點

屬於懶惰演算法，時間復雜度較高，因為需要計算未知樣本到所有已知樣本的距離

樣本平衡度依賴高，當出現極端情況樣本不平衡時，分類絕對會出現偏差，可以調整樣本權值改善

可解釋性差，無法給出類似決策樹那樣的規則

向量的維度越高，歐式距離的區分能力就越弱

樣本空間太大不適合，因為計算量太大，預測緩慢

文本分類

用戶推薦

回歸問題

1）所有的觀測實例中隨機抽取出k個觀測點，作為聚類中心點，然後遍歷其餘的觀測點找到距離各自最近的聚類中心點，將其加入到該聚類中。這樣，我們就有了一個初始的聚類結果，這是一次迭代的過程。

2）我們每個聚類中心都至少有一個觀測實例，這樣，我們可以求出每個聚類的中心點（means），作為新的聚類中心，然後再遍歷所有的觀測點，找到距離其最近的中心點，加入到該聚類中。然後繼續運行2）。

3）如此往復2），直到前後兩次迭代得到的聚類中心點一模一樣。

本演算法的時間復雜度：O(tkmn)，其中，t為迭代次數，k為簇的數目，m為記錄數，n為維數；

空間復雜度：O((m+k)n)，其中，k為簇的數目，m為記錄數，n為維數。

適用范圍：

K-menas演算法試圖找到使平凡誤差准則函數最小的簇。當潛在的簇形狀是凸面的，簇與簇之間區別較明顯，且簇大小相近時，其聚類結果較理想。前面提到，該演算法時間復雜度為O(tkmn)，與樣本數量線性相關，所以，對於處理大數據集合，該演算法非常高效，且伸縮性較好。但該演算法除了要事先確定簇數K和對初始聚類中心敏感外，經常以局部最優結束，同時對「雜訊」和孤立點敏感，並且該方法不適於發現非凸面形狀的簇或大小差別很大的簇。

1）首先，演算法只能找到局部最優的聚類，而不是全局最優的聚類。而且演算法的結果非常依賴於初始隨機選擇的聚類中心的位置。我們通過多次運行演算法，使用不同的隨機生成的聚類中心點運行演算法，然後對各自結果C通過evaluate(C)函數進行評估，選擇多次結果中evaluate(C)值最小的那一個。k-means++演算法選擇初始seeds的基本思想就是：初始的聚類中心之間的相互距離要盡可能的遠

2）關於初始k值選擇的問題。首先的想法是，從一個起始值開始，到一個最大值，每一個值運行k-means演算法聚類，通過一個評價函數計算出最好的一次聚類結果，這個k就是最優的k。我們首先想到了上面用到的evaluate(C)。然而，k越大，聚類中心越多，顯然每個觀測點距離其中心的距離的平方和會越小，這在實踐中也得到了驗證。第四節中的實驗結果分析中將詳細討論這個問題。

3）關於性能問題。原始的演算法，每一次迭代都要計算每一個觀測點與所有聚類中心的距離。有沒有方法能夠提高效率呢？是有的，可以使用k-d tree或者ball tree這種數據結構來提高演算法的效率。特定條件下，對於一定區域內的觀測點，無需遍歷每一個觀測點，就可以把這個區域內所有的點放到距離最近的一個聚類中去。這將在第三節中詳細地介紹。

相似點：都包含這樣的過程，給定一個點，在數據集中找離它最近的點。即二者都用到了NN(Nears Neighbor)演算法，一般用KD樹來實現NN。

k-d tree 與 ball tree

1）k-d tree[5]

把n維特徵的觀測實例放到n維空間中，k-d tree每次通過某種演算法選擇一個特徵(坐標軸)，以它的某一個值作為分界做超平面，把當前所有觀測點分為兩部分，然後對每一個部分使用同樣的方法，直到達到某個條件為止。

上面的表述中，有幾個地方下面將會詳細說明：（1）選擇特徵（坐標軸）的方法 （2）以該特徵的哪一個為界 （3）達到什麼條件演算法結束。

(1)選擇特徵的方法

計算當前觀測點集合中每個特徵的方差，選擇方差最大的一個特徵，然後畫一個垂直於這個特徵的超平面將所有觀測點分為兩個集合。

（2)以該特徵的哪一個值為界 即垂直選擇坐標軸的超平面的具體位置。

第一種是以各個點的方差的中值（median）為界。這樣會使建好的樹非常地平衡，會均勻地分開一個集合。這樣做的問題是，如果點的分布非常不好地偏斜的，選擇中值會造成連續相同方向的分割，形成細長的超矩形(hyperrectangles)。

替代的方法是計算這些點該坐標軸的平均值，選擇距離這個平均值最近的點作為超平面與這個坐標軸的交點。這樣這個樹不會完美地平衡，但區域會傾向於正方地被劃分，連續的分割更有可能在不同方向上發生。

（3）達到什麼條件演算法結束

實際中，不用指導葉子結點只包含兩個點時才結束演算法。你可以設定一個預先設定的最小值，當這個最小值達到時結束演算法。

圖6中，星號標注的是目標點，我們在k-d tree中找到這個點所處的區域後，依次計算此區域包含的點的距離，找出最近的一個點（黑色點），如果在其他region中還包含更近的點則一定在以這兩個點為半徑的圓中。假設這個圓如圖中所示包含其他區域。先看這個區域兄弟結點對應區域，與圓不重疊；再看其雙親結點的兄弟結點對應區域。從它的子結點對應區域中尋找（圖中確實與這個雙親結點的兄弟結點的子結點對應區域重疊了）。在其中找是否有更近的結點。

k-d tree的優勢是可以遞增更新。新的觀測點可以不斷地加入進來。找到新觀測點應該在的區域，如果它是空的，就把它添加進去，否則，沿著最長的邊分割這個區域來保持接近正方形的性質。這樣會破壞樹的平衡性，同時讓區域不利於找最近鄰。我們可以當樹的深度到達一定值時重建這棵樹。

然而，k-d tree也有問題。矩形並不是用到這里最好的方式。偏斜的數據集會造成我們想要保持樹的平衡與保持區域的正方形特性的沖突。另外，矩形甚至是正方形並不是用在這里最完美的形狀，由於它的角。如果圖6中的圓再大一些，即黑點距離目標點點再遠一些，圓就會與左上角的矩形相交，需要多檢查一個區域的點，而且那個區域是當前區域雙親結點的兄弟結點的子結點。

為了解決上面的問題，我們引入了ball tree。

2）ball tree[4]

解決上面問題的方案就是使用超球面而不是超矩形劃分區域。使用球面可能會造成球面間的重疊，但卻沒有關系。ball tree就是一個k維超球面來覆蓋這些觀測點，把它們放到樹裡面。圖7（a)顯示了一個2維平麵包含16個觀測實例的圖,圖7（b）是其對應的ball tree，其中結點中的數字表示包含的觀測點數。

不同層次的圓被用不同的風格畫出。樹中的每個結點對應一個圓，結點的數字表示該區域保含的觀測點數，但不一定就是圖中該區域囊括的點數，因為有重疊的情況，並且一個觀測點只能屬於一個區域。實際的ball tree的結點保存圓心和半徑。葉子結點保存它包含的觀測點。

使用ball tree時，先自上而下找到包含target的葉子結點，從此結點中找到離它最近的觀測點。這個距離就是最近鄰的距離的上界。檢查它的兄弟結點中是否包含比這個上界更小的觀測點。方法是：如果目標點距離兄弟結點的圓心的距離大於這個圓的圓心加上前面的上界的值，則這個兄弟結點不可能包含所要的觀測點。（如圖8）否則，檢查這個兄弟結點是否包含符合條件的觀測點。

那麼，ball tree的分割演算法是什麼呢？

選擇一個距離當前圓心最遠的觀測點i1，和距離i1最遠的觀測點 i2，將圓中所有離這兩個點最近的觀測點都賦給這兩個簇的中心，然後計算每一個簇的中心點和包含所有其所屬觀測點的最小半徑。對包含n個觀測點的超圓進行分割，只需要線性的時間。

與k-d tree一樣，如果結點包含的觀測點到達了預先設定的最小值，這個頂點就可以不再分割了。