❶ KNN演算法，結果報錯，幫忙怎麼改
knn演算法(k-Nearest Neighbor algorithm).是一種經典的分類演算法.
注意,不是聚類演算法.所以這種分類演算法必然包括了訓練過程.
然而和一般性的分類演算法不同,knn演算法是一種 懶惰演算法 .它並非
像其他的分類演算法先通過訓練建立分類模型.,而是一種被動的分類
過程.它是邊測試邊訓練建立分類模型.
演算法的一般描述過程如下:
1.首先計算每個測試樣本點到其他每個點的距離.
這個距離可以是歐氏距離,餘弦距離等.
❷ 01 KNN演算法 - 概述
KNN演算法 全稱是K近鄰演算法 （K-nearst neighbors，KNN）
KNN是一種基本的機器學習演算法，所謂K近鄰，就是k個最近的鄰居。即每個樣本都可以用和它 最接近的k個鄰近位置的樣本 來代替。
KNN是個相對比較簡單的演算法，比起之前提過的回歸演算法和分類演算法更容易。如果一個人從來沒有接觸過機器學習的演算法，拿到數據後最容易想到的分類方式就是K近鄰。打個比方：你們想了解我是個怎樣的人，然後你們發現我的身邊關系最密切的朋友是一群逗逼，所以你們可以默認我也是一個逗逼。
KNN演算法即可以應用於 分類演算法 中，也可以應用於 回歸演算法 中。
KNN在做回歸和分類的主要區別，在於最後做預測時候的決策不同。在分類預測時，一般採用 多數表決法 。在做回歸預測時，一般使用 平均值法 。
多數表決法： 分類時，哪些樣本離我的目標樣本比較近，即目標樣本離哪個分類的樣本更接近。
平均值法： 預測一個樣本的平均身高，觀察目標樣本周圍的其他樣本的平均身高，我們認為平均身高是目標樣本的身高。
再舉個例子：
分別根據甜度和脆度兩個特徵來判斷食物的種類。
根據樣本我們普遍發現：
比較甜，比較脆的食物都是水果。
不甜，不太脆的食物是蛋白質。
不甜，比較脆的食物是蔬菜。
於是根據目標的樣本甜度和脆度兩個特徵，我們可以對其進行分類了。
k值的選擇:
先選一個較小的值，然後通過交叉驗證選擇一個合適的最終值。
k越小，即使用較小的領域中的樣本進行預測，訓練誤差會減小，但模型會很復雜，以至於過擬合。
k越大，即使用交大的領域中的樣本進行預測，訓練誤差會增大，模型會變得簡單，容易導致欠擬合。
距離的度量:
使用歐幾里得距離：歐幾里得度量（euclidean metric）（也稱歐氏距離）是一個通常採用的距離定義，指在m維空間中兩個點之間的真實距離，或者向量的自然長度（即該點到原點的距離）。在二維和三維空間中的歐氏距離就是兩點之間的實際距離。
決策規劃:
分類：多數表決法、加權多數表決法。
回歸：平均值法、加權平均值法。
加權多數表決法：
平均值法和加權平均值法：
同樣看上面的圖，上方的三個樣本值為3，下面兩個樣本值為2，預測？的值。
如果不考慮加權，直接計算平均值：
(3 * 3 + 2 * 2) / 5 = 2.6
加權平均值：權重分別為1/7和2/7。計算加權平均值：
(3 * 3* 1/7 + 2 * 2 * 2/7) / 5 = 2.43
1、蠻力實現(brute)：
計算預測樣本到所有訓練集樣本的距離，然後選擇最小的k個距離，即可得到k個最鄰近點。
缺點：當特徵數多、樣本數多時，演算法的效率比較低。
2、KD樹 (kd_tree)：
首先對訓練數據進行建模，構建KD樹，然後根據建好的模型來獲取鄰近樣本數據。
後續內容會介紹KD樹搜索最小值的方式，讓大家直觀感受到KD樹比蠻力實現要少檢索多少數據。
❸ 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一樣，如果結點包含的觀測點到達了預先設定的最小值，這個頂點就可以不再分割了。
❹ KNN-分類演算法
KNN，K-NearestNeighbor，即K個最近的鄰居的意思。對於一個輸入樣本，用特徵上最接近它的K個臨近值大多數屬於的標簽來對它進行分類。KNN是最簡單的機器學習演算法之一，可以用於分類和回歸，是一種監督學習演算法。
具體實現過程如下：
①准備數據，對數據進行預處理
在已經分好類的情況下，我們需要對沒有分類的物品進行分類 。
②計算測試樣本點（也就是待分類點）到其他每個樣本點的距離。
其實就是計算（x1,y1）和（x2,y2）的距離。拓展到多維空間，則公式變成這樣：
k值是KNN演算法的一個參數，K的含義即參考」鄰居「標簽值的個數。
如果當K的取值過小時，一旦有雜訊得成分存在們將會對預測產生比較大影響，例如取K值為1時，一旦最近的一個點是雜訊，那麼就會出現偏差，K值的減小就意味著整體模型變得復雜，容易發生過擬合；
如果K的值取的過大時，就相當於用較大鄰域中的訓練實例進行預測，學習的近似誤差會增大。這時與輸入目標點較遠實例也會對預測起作用，使預測發生錯誤。K值的增大就意味著整體的模型變得簡單；
如果K==N的時候，那麼就是取全部的實例，即為取實例中某分類下最多的點，就對預測沒有什麼實際的意義了
在劃分好數據集後，我們可以通過交叉驗證法來得到最佳的K值
優點：
1.無數據輸入假定，在分類完的情況下進行測試
2.預測精度高
3.對異常值不敏感
缺點：
1.時間復雜度和空間復雜度高，計算到每一個點的距離，計算量較大
2.當樣本不平衡的時候，比如一個類的樣本容量大，另一個類的樣本容量很小，對於測試識別的樣本來說，投票結果更容易靠近樣本容量大的類，從而導致分類錯誤
❺ KNN 演算法-理論篇-如何給電影進行分類
KNN 演算法 的全稱是 K-Nearest Neighbor ，中文為 K 近鄰 演算法，它是基於 距離 的一種演算法，簡單有效。
KNN 演算法 即可用於分類問題，也可用於回歸問題。
假如我們統計了一些 電影數據，包括電影名稱，打鬥次數，接吻次數，電影類型 ，如下：
可以看到，電影分成了兩類，分別是動作片和愛情片。
如果現在有一部新的電影A，它的打鬥和接吻次數分別是80 和7，那如何用KNN 演算法對齊進行分類呢？
我們可以將打鬥次數作為 X 軸 ，接吻次數作為 Y 軸 ，將上述電影數據畫在一個坐標系中，如下：
通過上圖可以直觀的看出，動作電影與愛情電影的分布范圍是不同的。
KNN 演算法 基於距離，它的原理是： 選擇與待分類數據最近的K 個點，這K 個點屬於哪個分類最多，那麼待分類數據就屬於哪個分類 。
所以，要判斷電影A 屬於哪一類電影，就要從已知的電影樣本中，選出距離電影A 最近的K 個點：
比如，我們從樣本中選出三個點（即 K 為 3），那麼距離電影A 最近的三個點是《功夫》，《黑客帝國》和《戰狼》，而這三部電影都是動作電影。因此，可以判斷電影A 也是動作電影。
另外，我們還要處理兩個問題：
關於點之間的距離判斷，可以參考文章 《計算機如何理解事物的相關性》 。
至於K 值的選擇，K 值較大或者較小都會對模型的訓練造成負面影響，K 值較小會造成 過擬合 ，K 值較大 欠擬合 。
因此，K 值的選擇，一般採用 交叉驗證 的方式。
交叉驗證的思路是，把樣本集中的大部分樣本作為訓練集，剩餘部分用於預測，來驗證分類模型的准確度。一般會把 K 值選取在較小范圍內，逐一嘗試K 的值，當模型准確度最高時，就是最合適的K 值。
可以總結出， KNN 演算法 用於分類問題時，一般的步驟是：
如果，我們現在有一部電影B，知道該電影屬於動作電影，並且知道該電影的接吻次數是 7 ，現在想預測該電影的打鬥次數是多少？
這個問題就屬於 回歸問題 。
首先看下，根據已知數據，如何判斷出距離電影B 最近的K 個點。
我們依然設置K 為3，已知數據為：
根據已知數據可以畫出下圖：
圖中我畫出了一條水平線，這條線代表所有接吻次數是7 的電影，接下來就是要找到距離 這條線 最近的三部（K 為 3）動作電影。
可以看到，距離這條水平線最近的三部動作電影是《功夫》，《黑客帝國》和《戰狼》，那麼這三部電影的打鬥次數的平均值，就是我們預測的電影B 的打鬥次數。
所以，電影B 的打鬥次數是：
本篇文章主要介紹了 KNN 演算法 的基本原理，它簡單易懂，即可處理分類問題，又可處理回歸問題。
KNN 演算法 是基於 距離 的一種機器學習演算法，需要計算測試點與樣本點之間的距離。因此，當數據量大的時候，計算量就會非常龐大，需要大量的存儲空間和計算時間。
另外，如果樣本數據分類不均衡，比如有些分類的樣本非常少，那麼該類別的分類准確率就會很低。因此，在實際應用中，要特別注意這一點。
（本節完。）
推薦閱讀：
決策樹演算法-理論篇-如何計算信息純度
決策樹演算法-實戰篇-鳶尾花及波士頓房價預測
樸素貝葉斯分類-理論篇-如何通過概率解決分類問題
樸素貝葉斯分類-實戰篇-如何進行文本分類
計算機如何理解事物的相關性-文檔的相似度判斷
❻ knn演算法如何選擇一個最佳k值
K最近鄰(k-Nearest Neighbor，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
KNN演算法不僅可以用於分類，還可以用於回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成正比。該演算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本佔多數。 該演算法只計算「最近的」鄰居樣本，某一類的樣本數量很大，那麼或者這類樣本並不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量並不能影響運行結果。可以採用權值的方法（和該樣本距離小的鄰居權值大）來改進。
該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。
❼ 02 KNN演算法 - KD Tree
KD Tree 是KNN演算法中用於計算最近鄰的快速簡便的構建方式。
當樣本量少的時候，用 brute 直接搜索最近鄰的方式是可行的。即計算到所有樣本的距離。但當樣本量龐大時，直接計算所有樣本距離的工作量很大，這種情況使用 KD Tree 可以節約大量時間成本。
KD樹採用從m個樣本的n維特徵中，分別計算n個特徵取值的方差，用 方差最大 的第k維特徵n k 作為 根節點 。對於這個特徵，選擇取值中的 中位數 n kv 作為樣本的劃分點，對於小於該值的樣本劃分到 左子樹 ，對於大於等於該值的樣本劃分到 右子樹 ，對左右子樹採用同樣的方式找 方差最大的特徵 作為 根節點 ，遞歸產生KD Tree。
為什麼要選擇方差最大的進行劃分？
構建樹的目的是加快我的搜索過程。
既然我想加快我的搜索過程，要就意味著我最終的數據落在某個葉子節點上。我希望只需搜索整個二叉樹的某一些列即可，那麼最好的劃分方式，就是讓我的每個分支上數據的差異性最大化。
那麼衡量數據差異性的最基礎的數學指標是什麼？
是方差。方差越大，意味著數據的離散程度就越大，我將離散程度由大到小的數據一分為二，方差小意味著數據更集中到了一起。
現在有一個二維樣本: {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}
1、計算x1和x2每一列對應的方差
a、通過pandas計算出的是 樣本方差:
/ (n-1)
0| 6.966667
1| 5.366667
dtype: float64
b、通過numpy計算出的是 總體方差:
/ n
[[2 3]
[5 4]
[9 6]
[4 7]
[8 1]
[7 2]]
[ 5.80555556 4.47222222]
[ 5.80555556 4.47222222]
第一個樹的劃分：基於x 1 進行劃分
[2,4,5,7,8,9]的中位數是5和7的平均值6。
雖然嚴格意義上說中位數是6，但是在計算機中我們人為得定義x 1 的中位數是7。
左側：（2,3）（5,4）（4,7） （7,2）
右側: （9,6）（8,1）
第二個樹的劃分：根據右側（9,6）（8,1）的x 2 進行劃分
下側：x 2 ≤ 6；上側x 2 ＞6
第二個樹的劃分：根據左側（2,3）（5,4）（4,7） （7,2）的x 2 進行劃分
尋找2、3、4、7的中位數 4 進行劃分
....
注意：每次生成的劃分都是一個矩形。當葉子節點無法被繼續劃分的時候，KD樹的構建完成，遞歸結束。
我們生成了KD Tree後，現在就可以去預測測試集裡面的樣本目標點了。
1、對於一個目標點，先在KD樹里找到包含目標點的葉子節點。
2、以目標點為圓心，以 目標點 到 葉子節點樣本實例 的距離為半徑，得到一個超球體，最近鄰的點一定在這個超球體內部。
3、然後返回葉子節點的父節點，檢查另一個子節點包含的超矩形體是否和超球體相交。
4、如果相交就倒這個子節點尋找著是否有更加近的近鄰，有的話就更新最近鄰。
5、如果不相交，直接返回父節點中的父節點，在另一個子樹繼續搜索最近鄰。當回溯到根節點時，演算法結束。
6、此時保存的最近鄰節點就是最終的最近鄰。
如果現在想找(2,4.5)這點的最近鄰，該如何操作？
1、畫出二叉樹：
2、尋找(2,4.5)這點：
一個比較好的理解方式：首先找到第一個最近鄰，然後畫出一個圓。然後逐漸收縮圓的半徑，查看每次縮小後的圓是否能夠和矩形相交於一個更小的最近鄰點，如果有則更新。直到回到根節點。
❽ 為什麼k臨近演算法不能處理特徵很多的數據集
機器學習中常常要用到分類演算法，在諸多的分類演算法中有一種演算法名為k-近鄰演算法，也稱為kNN演算法。
一、kNN演算法的工作原理
二、適用情況
三、演算法實例及講解
---1.收集數據
---2.准備數據
---3.設計演算法分析數據
---4.測試演算法
一、kNN演算法的工作原理
官方解釋：存在一個樣本數據集，也稱作訓練樣本集，並且樣本中每個數據都存在標簽，即我們知道樣本集中每一數據與所屬分類的對應關系，輸入沒有標簽的新數據後，將新數據的每個特徵與樣本集中的數據對應的特徵進行比較，然後演算法提取樣本集中特徵最相似的數據（最近鄰）的分類標簽。一般來說，我們只選擇樣本集中前k個最相似的數據，這就是k-近鄰演算法中k的出處，通常k是不大於20的整數，最後，選擇k個最相似的數據中出現次數最多的分類，作為新數據的分類。
我的理解：k-近鄰演算法就是根據「新數據的分類取決於它的鄰居」進行的，比如鄰居中大多數都是退伍軍人，那麼這個人也極有可能是退伍軍人。而演算法的目的就是先找出它的鄰居，然後分析這幾位鄰居大多數的分類，極有可能就是它本省的分類。
二、適用情況
優點：精度高，對異常數據不敏感（你的類別是由鄰居中的大多數決定的，一個異常鄰居並不能影響太大），無數據輸入假定；
缺點：計算發雜度高（需要計算新的數據點與樣本集中每個數據的「距離」，以判斷是否是前k個鄰居），空間復雜度高（巨大的矩陣）；
適用數據范圍：數值型（目標變數可以從無限的數值集合中取值）和標稱型（目標變數只有在有限目標集中取值）。
❾ 模型效果評價
目錄：
數據拆分：訓練數據集&測試數據集
分類模型評價指標：精準度、混淆矩陣、精準率、召回率、F1 Score、ROC曲線等
回歸模型評價指標：MSE、RMSE、MAE、R Squared
聚類模型評價指標：蘭德指數、互信息、輪廓系數
數據拆分
目的：訓練數據和測試數據分別用來訓練模型和測試模型預測效果。
拆分原則：一般按照8:2的比例進行拆分，80%的數據用於訓練，20%的數據用來預測；
將規則排列的數據先shuffle打散之後再分割；
超參數：在機器學習演算法模型執行之前需要指定的參數。（調參調的就是超參數） 如kNN演算法中的k。
模型參數：演算法過程中學習的屬於這個模型的參數（kNN中沒有模型參數，回歸演算法有很多模型參數）。
如何選擇最佳的超參數，這是機器學習中的一個永恆的問題。在實際業務場景中，調參的難度大很多，一般我們會業務領域知識、經驗數值、實驗搜索等方面獲得最佳參數。
評價分類結果：精準度、混淆矩陣、精準率、召回率、F1 Score、ROC曲線、AUC、PR曲線。
1、混淆矩陣
混淆矩陣是監督學習中的一種可視化工具，主要用於比較分類結果和實例的真實信息。矩陣中的每一行代表實例的預測類別，每一列代表實例的真實類別。
真正(True Positive , TP)：被模型預測為正的正樣本。
假正(False Positive , FP)：被模型預測為正的負樣本。
假負(False Negative , FN)：被模型預測為負的正樣本。
真負(True Negative , TN)：被模型預測為負的負樣本。
真正率(True Positive Rate,TPR)：TPR=TP/(TP+FN)，即被預測為正的正樣本數 /正樣本實際數。
假正率(False Positive Rate,FPR) ：FPR=FP/(FP+TN)，即被預測為正的負樣本數 /負樣本實際數。
假負率(False Negative Rate,FNR) ：FNR=FN/(TP+FN)，即被預測為負的正樣本數 /正樣本實際數。
真負率(True Negative Rate,TNR)：TNR=TN/(TN+FP)，即被預測為負的負樣本數 /負樣本實際數/2
2、准確率（Accuracy）
准確率是最常用的分類性能指標。
Accuracy = (TP+TN)/(TP+FN+FP+TN)
即正確預測的正反例數 /總數
3、精確率（Precision）
精確率容易和准確率被混為一談。其實，精確率只是針對預測正確的正樣本而不是所有預測正確的樣本。表現為預測出是正的裡面有多少真正是正的。可理解為查准率。
Precision = TP/(TP+FP)
即正確預測的正例數 /預測正例總數
4、召回率（Recall）
召回率表現出在實際正樣本中，分類器能預測出多少。與真正率相等，可理解為查全率。
Recall = TP/(TP+FN)，即正確預測的正例數 /實際正例總數
5、F1 score
F值是精確率和召回率的調和值，更接近於兩個數較小的那個，所以精確率和召回率接近時，F值最大。很多推薦系統的評測指標就是用F值的。
2/F1 = 1/Precision + 1/Recall
6、ROC曲線
邏輯回歸裡面，對於正負例的界定，通常會設一個閾值，大於閾值的為正類，小於閾值為負類。如果我們減小這個閥值，更多的樣本會被識別為正類，提高正類的識別率，但同時也會使得更多的負類被錯誤識別為正類。為了直觀表示這一現象，引入ROC。根據分類結果計算得到ROC空間中相應的點，連接這些點就形成ROC curve，橫坐標為False Positive Rate(FPR假正率)，縱坐標為True Positive Rate(TPR真正率)。一般情況下，這個曲線都應該處於(0,0)和(1,1)連線的上方
ROC曲線中的四個點和一條線:
點(0,1)：即FPR=0, TPR=1，意味著FN＝0且FP＝0，將所有的樣本都正確分類。
點(1,0)：即FPR=1，TPR=0，最差分類器，避開了所有正確答案。
點(0,0)：即FPR=TPR=0，FP＝TP＝0，分類器把每個實例都預測為負類。
點(1,1)：分類器把每個實例都預測為正類。
總之：ROC曲線越接近左上角，該分類器的性能越好。而且一般來說，如果ROC是光滑的，那麼基本可以判斷沒有太大的overfitting
7、AUC
AUC（Area Under Curve）被定義為ROC曲線下的面積(ROC的積分)，通常大於0.5小於1。隨機挑選一個正樣本以及一個負樣本，分類器判定正樣本的值高於負樣本的概率就是 AUC 值。AUC值(面積)越大的分類器，性能越好。
8、PR曲線
PR曲線的橫坐標是精確率P，縱坐標是召回率R。評價標准和ROC一樣，先看平滑不平滑（藍線明顯好些）。一般來說，在同一測試集，上面的比下面的好（綠線比紅線好）。當P和R的值接近時，F1值最大，此時畫連接(0,0)和(1,1)的線，線和PRC重合的地方的F1是這條線最大的F1（光滑的情況下），此時的F1對於PRC就好像AUC對於ROC一樣。一個數字比一條線更方便調型。
有時候模型沒有單純的誰比誰好（比如圖二的藍線和青線），所以選擇模型還是要結合具體的使用場景。下面是兩個場景：1，地震的預測 對於地震的預測，我們希望的是RECALL非常高，也就是說每次地震我們都希望預測出來。這個時候我們可以犧牲PRECISION。情願發出1000次警報，把10次地震都預測正確了，也不要預測100次對了8次漏了兩次。2，嫌疑人定罪 基於不錯怪一個好人的原則，對於嫌疑人的定罪我們希望是非常准確的。即時有時候放過了一些罪犯（recall低），但也是值得的。
對於分類器來說，本質上是給一個概率，此時，我們再選擇一個CUTOFF點（閥值），高於這個點的判正，低於的判負。那麼這個點的選擇就需要結合你的具體場景去選擇。反過來，場景會決定訓練模型時的標准，比如第一個場景中，我們就只看RECALL=99.9999%（地震全中）時的PRECISION，其他指標就變得沒有了意義。
當正負樣本數量差距不大的情況下，ROC和PR的趨勢是差不多的，但是在正負樣本分布極不均衡的情況下，PRC比ROC更能真實的反映出實際情況，因為此時ROC曲線看起來似乎很好，但是卻在PR上效果一般。
評價回歸結果：MSE、RMSE、MAE、R Squared。
回歸問題用到的衡量指標相對直觀。假設yiyi是第ii個樣本的真實值，ŷiy^i是對第ii個樣本的預測值。
1. 平均絕對誤差（MAE）
平均絕對誤差MAE（Mean Absolute Error）又被稱為l1范數損失（l1-norm loss）：
2. 平均平方誤差（MSE）
平均平方誤差MSE（Mean Squared Error）又被稱為l2范數損失（l2-norm loss）：
3、均方根誤差（RMSE）
RMSE雖然廣為使用，但是其存在一些缺點，因為它是使用平均誤差，而平均值對異常點（outliers）較敏感，如果回歸器對某個點的回歸值很不理性，那麼它的誤差則較大，從而會對RMSE的值有較大影響，即平均值是非魯棒的。
4、解釋變異
解釋變異（ Explained variance）是根據誤差的方差計算得到的：
5、決定系數
決定系數（Coefficient of determination）又被稱為R2分數：
三、聚類模型評價
1 . 蘭德指數
蘭德指數（Rand index）需要給定實際類別信息C，假設K是聚類結果，a表示在C與K中都是同類別的元素對數，b表示在C與K中都是不同類別的元素對數，則蘭德指數為：
其中數據集中可以組成的總元素對數，RI取值范圍為[0,1]，值越大意味著聚類結果與真實情況越吻合。
對於隨機結果，RI並不能保證分數接近零。為了實現「在聚類結果隨機產生的情況下，指標應該接近零」，調整蘭德系數（Adjusted rand index）被提出，它具有更高的區分度：
ARI取值范圍為[−1,1]，值越大意味著聚類結果與真實情況越吻合。從廣義的角度來講，ARI衡量的是兩個數據分布的吻合程度。
2. 互信息
互信息（Mutual Information）也是用來衡量兩個數據分布的吻合程度。假設UU與VV是對NN個樣本標簽的分配情況，則兩種分布的熵（熵表示的是不確定程度）分別為：
利用基於互信息的方法來衡量聚類效果需要實際類別信息，MI與NMI取值范圍為[0,1]，AMI取值范圍為[−1,1]，它們都是值越大意味著聚類結果與真實情況越吻合。
3. 輪廓系數
輪廓系數（Silhouette coefficient）適用於實際類別信息未知的情況。對於單個樣本，設aa是與它同類別中其他樣本的平均距離，bb是與它距離最近不同類別中樣本的平均距離，輪廓系數為：
對於一個樣本集合，它的輪廓系數是所有樣本輪廓系數的平均值。
輪廓系數取值范圍是[−1,1]
❿ python網格搜索支持向量回歸得分低，為0.003，偶爾還會出現負數，該怎麼處理
使用Python編程可以快速遷移代碼並進行改動，無須花費過多的精力在修改代碼與代碼規范上。開發者在Python中封裝了很多優秀的依賴庫，可以直接拿來使用，常見的機器學習庫如下：1、Scikit-LearnScikit-Learn基於Numpy和Scipy，是專門為機器學習建造的一個Python模塊，提供了大量用於數據挖掘和分析的工具，包括數據預處理、交叉驗證、演算法與可視化演算法等一系列介面。Scikit-Learn基本功能可分為六個部分：分類、回歸、聚類、數據降維、模型選擇、數據預處理。其中集成了大量分類、回歸、聚類功能，包括支持向量機、邏輯回歸、隨機森林、樸素貝葉斯等。2、Orange3Orange3是一個基於組件的數據挖掘和機器學習軟體套裝，支持Python進行腳本開發。它包含一系列的數據可視化、檢索、預處理和建模技術，具有一個良好的用戶界面，同時也可以作為Python的一個模塊使用。用戶可通過數據可視化進行數據分析，包含統計分布圖、柱狀圖、散點圖，以及更深層次的決策樹、分層聚簇、熱點圖、MDS等，並可使用它自帶的各類附加功能組件進行NLP、文本挖掘、構建網路分析等。3、XGBoostXGBoost是專注於梯度提升演算法的機器學習函數庫，因其優良的學習效果及高效的訓練速度而獲得廣泛的關注。XGBoost支持並行處理，比起同樣實現了梯度提升演算法的Scikit-Learn庫，其性能提升10倍以上。XGBoost可以處理回歸、分類和排序等多種任務。4、NuPICNuPIC是專注於時間序列的一個機器學習平台，其核心演算法為HTM演算法，相比於深度學習，其更為接近人類大腦的運行結構。HTM演算法的理論依據主要是人腦中處理高級認知功能的新皮質部分的運行原理。NuPIC可用於預測以及異常檢測，使用面非常廣，僅要求輸入時間序列即可。5、MilkMilk是Python中的一個機器學習工具包。Milk注重提升運行速度與降低內存佔用，因此大部分對性能敏感的代碼都是使用C++編寫的，為了便利性在此基礎上提供Python介面。重點提供監督分類方法，如SVMs、KNN、隨機森林和決策樹等。