knn演算法的優化之手肘法

『壹』 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演算法因其提出時間較早，隨著其他技術的不斷更新和完善，kNN演算法的諸多不足之處也逐漸顯露，因此許多kNN演算法的改進演算法也應運而生。
針對以上演算法的不足，演算法的改進方向主要分成了分類效率和分類效果兩方面。
分類效率：事先對樣本屬性進行約簡，刪除對分類結果影響較小的屬性，快速的得出待分類樣本的類別。該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。
分類效果：採用權值的方法（和該樣本距離小的鄰居權值大）來改進，Han等人於2002年嘗試利用貪心法，針對文件分類實做可調整權重的k最近鄰居法WAkNN (weighted adjusted k nearest neighbor)，以促進分類效果；而Li等人於2004年提出由於不同分類的文件本身有數量上有差異，因此也應該依照訓練集合中各種分類的文件數量，選取不同數目的最近鄰居，來參與分類。

『叄』 KNN演算法-4-演算法優化-KD樹

KNN演算法的重要步驟是對所有的實例點進行快速k近鄰搜索。如果採用線性掃描（linear scan），要計算輸入點與每一個點的距離，時間復雜度非常高。因此在查詢操作時，可以使用kd樹對查詢操作進行優化。

Kd-樹是K-dimension tree的縮寫，是對數據點在k維空間（如二維(x，y)，三維(x，y，z)，k維(x1，y，z..)）中劃分的一種數據結構，主要應用於多維空間關鍵數據的搜索（如：范圍搜索和最近鄰搜索）。本質上說，Kd-樹就是一種平衡二叉樹。

k-d tree是每個節點均為k維樣本點的二叉樹，其上的每個樣本點代表一個超平面，該超平面垂直於當前劃分維度的坐標軸，並在該維度上將空間劃分為兩部分，一部分在其左子樹，另一部分在其右子樹。即若當前節點的劃分維度為d，其左子樹上所有點在d維的坐標值均小於當前值，右子樹上所有點在d維的坐標值均大於等於當前值，本定義對其任意子節點均成立。

必須搞清楚的是，k-d樹是一種空間劃分樹，說白了，就是把整個空間劃分為特定的幾個部分，然後在特定空間的部分內進行相關搜索操作。想像一個三維(多維有點為難你的想像力了)空間，kd樹按照一定的劃分規則把這個三維空間劃分了多個空間，如下圖所示：

首先，邊框為紅色的豎直平面將整個空間劃分為兩部分，此兩部分又分別被邊框為綠色的水平平面劃分為上下兩部分。最後此4個子空間又分別被邊框為藍色的豎直平面分割為兩部分，變為8個子空間，此8個子空間即為葉子節點。

常規的k-d tree的構建過程為：

對於構建過程，有兩個優化點：

例子：採用常規的構建方式，以二維平面點(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 為例結合下圖來說明k-d tree的構建過程：

如上演算法所述，kd樹的構建是一個遞歸過程，我們對左子空間和右子空間內的數據重復根節點的過程就可以得到一級子節點（5,4）和（9,6），同時將空間和數據集進一步細分，如此往復直到空間中只包含一個數據點。

如之前所述，kd樹中，kd代表k-dimension，每個節點即為一個k維的點。每個非葉節點可以想像為一個分割超平面，用垂直於坐標軸的超平面將空間分為兩個部分，這樣遞歸的從根節點不停的劃分，直到沒有實例為止。經典的構造k-d tree的規則如下：

kd樹的檢索是KNN演算法至關重要的一步，給定點p，查詢數據集中與其距離最近點的過程即為最近鄰搜索。

如在構建好的k-d tree上搜索(3,5)的最近鄰時，對二維空間的最近鄰搜索過程作分析。

首先從根節點(7,2)出發，將當前最近鄰設為(7,2)，對該k-d tree作深度優先遍歷。

以(3,5)為圓心，其到(7,2)的距離為半徑畫圓（多維空間為超球面），可以看出(8,1)右側的區域與該圓不相交，所以(8,1)的右子樹全部忽略。

接著走到(7,2)左子樹根節點(5,4)，與原最近鄰對比距離後，更新當前最近鄰為(5,4)。

以(3,5)為圓心，其到(5,4)的距離為半徑畫圓，發現(7,2)右側的區域與該圓不相交，忽略該側所有節點，這樣(7,2)的整個右子樹被標記為已忽略。

遍歷完(5,4)的左右葉子節點，發現與當前最優距離相等，不更新最近鄰。所以(3,5)的最近鄰為(5,4)。

舉例：查詢點（2.1,3.1）

星號表示要查詢的點（2.1,3.1）。通過二叉搜索，順著搜索路徑很快就能找到最鄰近的近似點，也就是葉子節點（2,3）。而找到的葉子節點並不一定就是最鄰近的，最鄰近肯定距離查詢點更近，應該位於以查詢點為圓心且通過葉子節點的圓域內。為了找到真正的最近鄰，還需要進行相關的『回溯'操作。也就是說，演算法首先沿搜索路徑反向查找是否有距離查詢點更近的數據點。

舉例：查詢點（2，4.5）

一個復雜點了例子如查找點為（2，4.5），具體步驟依次如下：

上述兩次實例表明，當查詢點的鄰域與分割超平面兩側空間交割時，需要查找另一側子空間，導致檢索過程復雜，效率下降。

一般來講，最臨近搜索只需要檢測幾個葉子結點即可，如下圖所示：

但是，如果當實例點的分布比較糟糕時，幾乎要遍歷所有的結點，如下所示：

研究表明N個節點的K維k-d樹搜索過程時間復雜度為： 。

同時，以上為了介紹方便，討論的是二維或三維情形。但在實際的應用中，如SIFT特徵矢量128維，SURF特徵矢量64維，維度都比較大，直接利用k-d樹快速檢索（維數不超過20）的性能急劇下降，幾乎接近貪婪線性掃描。假設數據集的維數為D，一般來說要求數據的規模N滿足N»2D，才能達到高效的搜索。

Sklearn中有KDTree的實現，僅構建了一個二維空間的k-d tree，然後對其作k近鄰搜索及指定半徑的范圍搜索。多維空間的檢索，調用方式與此例相差無多。

『肆』 什麼叫做knn演算法

在模式識別領域中，最近鄰居法（KNN演算法，又譯K-近鄰演算法）是一種用於分類和回歸的非參數統計方法。

在這兩種情況下，輸入包含特徵空間（Feature Space）中的k個最接近的訓練樣本。

1、在k-NN分類中，輸出是一個分類族群。一個對象的分類是由其鄰居的「多數表決」確定的，k個最近鄰居（k為正整數，通常較小）中最常見的分類決定了賦予該對象的類別。若k=1，則該對象的類別直接由最近的一個節點賦予。

2、在k-NN回歸中，輸出是該對象的屬性值。該值是其k個最近鄰居的值的平均值。

最近鄰居法採用向量空間模型來分類，概念為相同類別的案例，彼此的相似度高，而可以藉由計算與已知類別案例之相似度，來評估未知類別案例可能的分類。

K-NN是一種基於實例的學習，或者是局部近似和將所有計算推遲到分類之後的惰性學習。k-近鄰演算法是所有的機器學習演算法中最簡單的之一。

無論是分類還是回歸，衡量鄰居的權重都非常有用，使較近鄰居的權重比較遠鄰居的權重大。例如，一種常見的加權方案是給每個鄰居權重賦值為1/ d，其中d是到鄰居的距離。

鄰居都取自一組已經正確分類（在回歸的情況下，指屬性值正確）的對象。雖然沒要求明確的訓練步驟，但這也可以當作是此演算法的一個訓練樣本集。

k-近鄰演算法的缺點是對數據的局部結構非常敏感。

K-均值演算法也是流行的機器學習技術，其名稱和k-近鄰演算法相近，但兩者沒有關系。數據標准化可以大大提高該演算法的准確性。

參數選擇

如何選擇一個最佳的K值取決於數據。一般情況下，在分類時較大的K值能夠減小雜訊的影響，但會使類別之間的界限變得模糊。一個較好的K值能通過各種啟發式技術（見超參數優化）來獲取。

雜訊和非相關性特徵的存在，或特徵尺度與它們的重要性不一致會使K近鄰演算法的准確性嚴重降低。對於選取和縮放特徵來改善分類已經作了很多研究。一個普遍的做法是利用進化演算法優化功能擴展，還有一種較普遍的方法是利用訓練樣本的互信息進行選擇特徵。

在二元（兩類）分類問題中，選取k為奇數有助於避免兩個分類平票的情形。在此問題下，選取最佳經驗k值的方法是自助法。

『伍』 聚類演算法--KMeans

    與分類、序列標注等任務不同，聚類是在事先並不知道任何樣本標簽的情況下，通過數據之間的內在關系把樣本劃分為若干類別，使得同類別樣本之間的相似度高，不同類別之間的樣本相似度低(即增大類內聚，減少類間距)。    

    聚類屬於非監督學習，K均值聚類是最基礎常用的聚類演算法。它的基本思想是，通過迭代尋找K個簇(Cluster)的一種劃分方案，使得聚類結果對應的損失函數最小。其中，損失函數可以定義為各個樣本距離所屬簇中心點的誤差平方和。

其中 代表第i個樣本， 是 所屬的簇，  代表簇對應的中心點，M是樣本總數。

相關概念：

    K值： 要得到的簇的個數。

    質心： 每個簇的均值向量。即向量各維取平均即可。

    距離量度： 常用歐幾里得距離和餘弦相似度(先標准化)。

    KMeans的主要思想是：在給定K值和K個初始類簇中心點的情況下，把每個點(亦即數據記錄)分到離其最近的類簇中心點所代表的類簇中，所有點分配完畢之後，根據一個類簇內的所有點重新計算該類簇的中心點(取平均值)，然後再迭代的進行分配點和更新類簇中心點的步驟，直至類簇中心點的變化很小，或者達到指定的迭代次數。

    KMeans的核心目標是將給定的數據集劃分成K個簇(K是超餐)，並給出每個樣本數據對應的中心點。具體步驟非常簡單：

    （1）首先確定一個K值，即我們希望將數據集經過聚類得到k個集合。

    （2）從數據集中隨機選擇K個數據點作為質心。

    （3）對數據集中每一個點，計算其與每一個質心的距離(如歐式距離)，離哪個質心近，就劃分到哪個質心所屬的集合。

    （4）把所有數據歸好集合後，一共有K個集合。然後重新計算每個集合的質心。

    （5）如果新計算出來的質心和原來的質心之間的距離小於某一個設置的閾值(表示重新計算的質心的位置變化不大，趨於穩定，或者說收斂)，我們可以認為聚類已經達到期望的結果，演算法終止。

    （6）如果新質心和原質心距離變化很大，需要迭代3-5步驟。

KMeans最核心的部分是先固定中心點，調整每個樣本所屬的類別來減少J；再固定每個樣本的類別，調整中心點繼續減小J。兩個過程交替循環，J單調遞減直到極小值，中心點和樣本劃分的類別同時收斂。

KMeans的優點 ：

 高效可伸縮，計算復雜度為O(NKt)接近於線性(N是數據量，K是聚類總數，t是迭代輪數)。

 收斂速度快，原理相對通俗易懂，可解釋性強。

當結果簇是密集的，而簇與簇之間區別是明顯時，他的效果較好。主要需要調參的參數僅僅是簇數K。

缺點 ：

 受初始值和異常點影響，聚類結果可能不是全局最優而是局部最優。K-Means演算法對初始選取的質心點是敏感的，不同的隨機種子點得到的聚類結果完全不同，對結果影響很大。

 K是超參數，一般需要按經驗選擇。

 對噪音和異常點比較的敏感，用來檢測異常值。

 只能發現球狀的簇。在K-Means中，我們用單個點對cluster進行建模，這實際上假設各個cluster的數據是呈高維球型分布的，但是在生活中出現這種情況的概率並不算高。例如，每一個cluster是一個一個的長條狀的，K-Means的則根本識別不出來這種類別( 這種情況可以用GMM )。實際上，K-Means是在做凸優化，因此處理不了非凸的分布。

根據以上特點，我們可以從下面幾個角度對演算法做調優。

（1）數據預處理：歸一化和異常點過濾

    KMeans本質是一種基於歐式距離度量的數據劃分方法，均值和方差大的維度將對數據的聚類結果產生決定性影響 。所以在聚類前對數據( 具體的說是每一個維度的特徵 )做歸一化和單位統一至關重要。此外，異常值會對均值計算產生較大影響，導致 中心偏移 ，這些雜訊點最好能提前過濾。

（2）合理選擇K值

    K值的選擇一般基於實驗和多次實驗結果。例如採用 手肘法 ，嘗試不同K值並將對應的損失函數畫成折線。手肘法認為圖上的 拐點就是K的最佳值 (k=3)。

為了將尋找最佳K值的過程自動化，研究人員提出了Gap Statistic方法。不需要人們用肉眼判斷，只需要找到最大的Gap Statistic對應的K即可。

       損失函數記為  ，當分為K類時，Gap Statistic定義為：  。 是 的期望 ，一般由蒙特卡洛模擬產生。我們在樣本所在的區域內按照均勻分布隨機地產生和原始樣本數一樣多的隨機樣本，並對這個隨機樣本做KMeans，得到一個 ，重復多次就可以計算出 的近似值。

       的物理含義是隨機樣本的損失與實際樣本的損失之差。Gap越大說明聚類的效果越好 。一種極端情況是，隨著K的變化 幾乎維持一條直線保持不變。說明這些樣本間沒有明顯的類別關系，數據分布幾乎和均勻分布一致，近似隨機。此時做聚類沒有意義。

（3）改進初始值的選擇

    之前我們採用隨機選擇K個中心的做法，可能導致不同的中心點距離很近，就需要更多的迭代次數才能收斂。如果在選擇初始中心點時能 讓不同的中心盡可能遠離 ，效果往往更好。這類演算法中，以K-Means++演算法最具影響力。

（4）採用核函數

    主要思想是通過一個非線性映射，將輸入空間中的數據點映射到高維的特徵空間中，並在新的空間進行聚類。非線性映射增加了數據點線性可分的概率(與SVM中使用核函數思想類似)對於非凸的數據分布可以達到更為准確的聚類結果。

 (1）初始的K個質心怎麼選？

    最常用的方法是隨機選，初始質心的選取對最終聚類結果有影響，因此演算法一定要多執行幾次，哪個結果更合理，就用哪個結果。當然也有一些優化的方法，第一種是選擇彼此距離最遠的點，具體來說就是先選第一個點，然後選離第一個點最遠的當第二個點，然後選第三個點，第三個點到第一、第二兩點的距離之和最小，以此類推。第二種是先根據其他聚類演算法(如層次聚類)得到聚類結果，從結果中每個分類選一個點

（2）關於離群值？

    離群值就是遠離整體的，非常異常、非常特殊的數據點，在聚類之前應該將這些"極大""極小"之類的離群數據都去掉，否則會對於聚類的結果有影響。但是，離散值往往自身就很有分析的價值，可以把離群值單獨作為一類來分析。

（3）單位要一致！

（4）標准化

    數據中X整體都比較小，比如都是1到10之間的數，Y很大，比如都是1000以上的數，那麼在計算距離的時候Y起到的作用就比X大很多，X對於距離的影響幾乎可以忽略，這也有問題。因此，如果K-Means聚類中選擇歐幾里得距離計算距離，數據集又出現了上面所述的情況，就一定要進行數據的標准化(normalization)，即將數據按比例縮放，使之落入一個小的特定區間。

    K-Means是無監督學習的聚類演算法，沒有樣本輸出；而KNN是監督學習的分類演算法，有對應的類別輸出 。KNN基本不需要訓練，對測試集裡面的點，只需要找到在訓練集中最近的K個點，用這最近的K個點的類別來決定測試點的類別。而K-Means則有明顯的訓練過程，找到K個類別的最佳質心，從而決定樣本的簇類別。當然，兩者也有一些相似點，兩個演算法都包含一個過程，即找出和某一個點最近的點。 兩周都利用了最近鄰的思想 。

『陸』 R語言-KNN演算法

1、K最近鄰(k-NearestNeighbor，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。

2、KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

3、KNN演算法不僅可以用於分類，還可以用於回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成正比。

簡言之，就是將未標記的案例歸類為與它們最近相似的、帶有標記的案例所在的類 。

原理及舉例

工作原理：我們知道樣本集中每一個數據與所屬分類的對應關系，輸入沒有標簽的新數據後，將新數據與訓練集的數據對應特徵進行比較，找出「距離」最近的k（通常k<20）數據，選擇這k個數據中出現最多的分類作為新數據的分類。

演算法描述

1、計算已知數據集中的點與當前點的距離

2、按距離遞增次序排序

3、選取與當前數據點距離最近的K個點

4、確定前K個點所在類別出現的頻率

5、返回頻率最高的類別作為當前類別的預測

距離計算方法有"euclidean"（歐氏距離）,」minkowski」（明科夫斯基距離）, "maximum"（切比雪夫距離）, "manhattan"（絕對值距離）,"canberra"（蘭式距離）, 或 "minkowski"（馬氏距離）等

Usage

knn(train, test, cl, k = 1, l = 0, prob =FALSE, use.all = TRUE)

Arguments

train

matrix or data frame of training set cases.

test

matrix or data frame of test set cases. A vector will  be interpreted as a row vector for a single case.

cl

factor of true classifications of training set

k

number of neighbours considered.

l

minimum vote for definite decision, otherwisedoubt. (More precisely, less thank-ldissenting votes are allowed, even

ifkis  increased by ties.)

prob

If this is true, the proportion of the votes for the

winning class are returned as attributeprob.

use.all

controls handling of ties. If true, all distances equal

to thekth largest are

included. If false, a random selection of distances equal to thekth is chosen to use exactlykneighbours.

kknn(formula = formula(train), train, test, na.action = na.omit(), k = 7, distance = 2, kernel = "optimal", ykernel = NULL, scale=TRUE, contrasts = c('unordered' = "contr.mmy", ordered = "contr.ordinal"))

參數：

formula                            A formula object.

train                                 Matrix or data frame of training set cases.

test                                   Matrix or data frame of test set cases.

na.action                         A function which indicates what should happen when the data contain 』NA』s.

k                                       Number of neighbors considered.

distance                          Parameter of Minkowski distance.

kernel                              Kernel to use. Possible choices are "rectangular" (which is standard unweighted knn), "triangular", "epanechnikov" (or beta(2,2)), "biweight" (or beta(3,3)), "triweight" (or beta(4,4)), "cos", "inv", "gaussian", "rank" and "optimal".

ykernel                            Window width of an y-kernel, especially for prediction of ordinal classes.

scale                                Logical, scale variable to have equal sd.

contrasts                         A vector containing the 』unordered』 and 』ordered』 contrasts to use

kknn的返回值如下：

fitted.values              Vector of predictions.

CL                              Matrix of classes of the k nearest neighbors.

W                                Matrix of weights of the k nearest neighbors.

D                                 Matrix of distances of the k nearest neighbors.

C                                 Matrix of indices of the k nearest neighbors.

prob                            Matrix of predicted class probabilities.

response                   Type of response variable, one of continuous, nominal or ordinal.

distance                     Parameter of Minkowski distance.

call                              The matched call.

terms                          The 』terms』 object used.

iris%>%ggvis(~Length,~Sepal.Width,fill=~Species)

library（kknn）
data（iris）

dim(iris)

m<-(dim(iris))[1]
val<-sample(1:m,size=round(m/3）,replace=FALSE,prob=rep(1/m,m))

建立訓練數據集

data.train<-iris[-val,]

建立測試數據集

data.test<-iris[val,]

調用kknn  之前首先定義公式

formula ： Species ~ Sepal.Length + Sepal.Width + Petal.Length + Petal.Width

iris.kknn<-kknn(Species~.,iris.train,iris.test,distance=1,kernel="triangular")

summary(iris.kknn)

# 獲取fitted.values

fit <- fitted(iris.kknn)

# 建立表格檢驗判類准確性

table(iris.valid$Species, fit)
# 繪畫散點圖，k-nearest neighbor用紅色高亮顯示

pcol <- as.character(as.numeric(iris.valid$Species))

pairs(iris.valid[1:4], pch = pcol, col = c("green3", "red")[(iris.valid$Species != fit)+1]

二、R語言knn演算法

install.packages("class")

library(class)

對於新的測試樣例基於距離相似度的法則，確定其K個最近的鄰居，在K個鄰居中少數服從多數

確定新測試樣例的類別

1、獲得數據

2、理解數據

對數據進行探索性分析，散點圖

如上例

3、確定問題類型，分類數據分析

4、機器學習演算法knn

5、數據處理，歸一化數據處理

normalize <- function(x){

num <- x - min(x)

denom <- max(x) - min(x)

return(num/denom)

}

iris_norm <-as.data.frame(lapply(iris[,1:4], normalize))

summary(iris_norm)

6、訓練集與測試集選取

一般按照3:1的比例選取

方法一、set.seed(1234)

ind <- sample(2,nrow(iris), replace=TRUE, prob=c(0.67, 0.33))

iris_train <-iris[ind==1, 1:4]

iris_test <-iris[ind==2, 1:4]

train_label <-iris[ind==1, 5]

test_label <-iris[ind==2, 5]

方法二、

ind<-sample(1:150,50)

iris_train<-iris[-ind,]

iris_test<-iris[ind,1:4]

iris_train<-iris[-ind,1:4]

train_label<-iris[-ind,5]

test_label<-iris[ind,5]

7、構建KNN模型

iris_pred<-knn(train=iris_train,test=iris_test,cl=train_label,k=3)

8、模型評價

交叉列聯表法

table（test_label,iris_pred)

實例二

數據集

http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data

導入數據

dir <-'http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data'wdbc.data <-read.csv(dir,header = F)

names(wdbc.data) <- c('ID','Diagnosis','radius_mean','texture_mean','perimeter_mean','area_mean','smoothness_mean','compactness_mean','concavity_mean','concave points_mean','symmetry_mean','fractal dimension_mean','radius_sd','texture_sd','perimeter_sd','area_sd','smoothness_sd','compactness_sd','concavity_sd','concave points_sd','symmetry_sd','fractal dimension_sd','radius_max_mean','texture_max_mean','perimeter_max_mean','area_max_mean','smoothness_max_mean','compactness_max_mean','concavity_max_mean','concave points_max_mean','symmetry_max_mean','fractal dimension_max_mean')

table(wdbc.data$Diagnosis)## M = malignant, B = benign

wdbc.data$Diagnosis <- factor(wdbc.data$Diagnosis,levels =c('B','M'),labels = c(B ='benign',M ='malignant'))

『柒』 kNN（k-NearestNeighbor）演算法

參考《數據挖掘10大演算法》對kNN演算法進行基本總結，附有一個Python3的簡例。

基本思想
從訓練集中找出 k 個最接近測試對象的訓練對象，再從這 k 個對象中找出居於主導的類別，將其賦給測試對象。

定位
由於這種總體占優的決策模式，對於類域的交叉、重疊較多的或者多模型、多標簽的待分樣本集來說，kNN方法較其他方法更為適合。kNN演算法屬於有監督學習的分類演算法。

避開了兩個問題
（1）分類時對象之間不可能完全匹配（kNN方法計算的是對象之間的距離）；
（2）具有相同屬性的對象有不同的類別（kNN方法依據總體占優的類別進行決策，而不是單一對象的類別進行決策）。

需要考慮幾個關鍵要素
（1）訓練集；
（2）用於計算對象之間臨近的程度或者其他相似的指標；
（3）最近鄰的個數 k；
（4）基於 k 個最近鄰及其類別對目標對象類別進行判定的方法。

kNN方法很容易理解和實現，在一定條件下，其分類錯誤率不會超過最優貝葉斯錯誤率的兩倍。一般情況下，kNN方法的錯誤率會逐漸收斂到最優貝葉斯錯誤率，可以用作後者的近似。

基本演算法

演算法的存儲復雜度為O(n)，時間復雜度為O(n)，其中 n 為訓練對象的數量。

影響kNN演算法性能的幾個關鍵因素
（1）k 值的選擇；
如果 k 值選得過小，結果就會對雜訊點特別敏感；k 值選得過大就會使得近鄰中包含太多別的類的點。最佳 k 值的估計可以使用交叉驗證的方法。通常，使用 k=1會有一個比較好的結果（特別是對於小數據集的情況）。但是，在樣本很充足的情況下，選擇較大的 k 值可以提高抗噪能力。

（2）類別決策時的綜合方法；
對目標對象的類別進行決策，最簡單的就是使用總體占優方法（簡單投票，票數最多的一類勝出）。稍微復雜一點，考慮近鄰中每個點與目標對象的距離不同，對決策的份量進行加權考慮。

（3）距離測量標準的選擇。
距離測量的標准一般選擇 歐幾里得距離 或者 曼哈頓距離 。

簡單例子