《機器學習實戰》—— KNN(K近鄰算法)

《機器學習實戰》可以說是學習ML的必備書籍，連載本書中的重點算法。重點在算法和思想，避免涉及數學和理論推導。

由于現在已經有現成的庫，不管是Sklearn還是keras，是以算法基本不需要我們自己去寫，調用庫就可以，但是必須要知道如何要去調參，也就是每個算法涉及到的參數，如何調整，能效果更好。

1.基本概念：

k近鄰作為監督學習的入門算法，是資料分析不可缺少的一部分。

适用情況：對于一系列有标簽的資料D1，我們想對某個或某些資料D2進行分類。我們首先，分别計算D2與D1各個資料的距離（此處多種度量方法），計算得出距離，然後對這些資料按距離遠近排序，距離小在前面。然後，選擇排在前k（即KNN中的k）個的資料，作為參考對象。對于前k個資料，統計每個類别出現的頻率，頻率大的（也就是出現次數多的）作為該資料D2的預測類别。

2.算法僞代碼：

算法-對未知類型的資料集中的點執行下列操作：
    1>分别計算改點與已經類型資料集中的每個點之間的距離；
    2>按距離遞增排序；
    3>選取距離最小的前k個點；
    4>統計這k個點，對應類别，每個類别出現的頻率；
    5>這k個點，對應類别，出現頻率最高的作為目前點的預測分類；
           

3. 算法注意點：

3.1 歸一化數值：

在使用knn對資料進行預測之前，我們首先要對資料做歸一化，因為每個特征的大小差很多，例如有的特征值1000多，有的個位數，如果不歸一化，不同特征的權重會差很多。同時會影響到收斂速度。當然在進行資料分析的時候，并不是每個特征對分類的貢獻完全相同。我們可以分析特征，對特征賦予不同的特征值。

3.2 算法優缺點：

優點：

簡單好用，容易了解，精度高，理論成熟，既可以用來做分類也可以用來做回歸；

可用于數值型資料和離散型資料；

訓練時間複雜度為O(n)；無資料輸入假定；

對異常值不敏感。

缺點：

計算複雜性高；空間複雜性高；

樣本不平衡問題（即有些類别的樣本數量很多，而其它樣本的數量很少）；

一般數值很大的時候不用這個，計算量太大。但是單個樣本又不能太少，否則容易發生誤分。

最大的缺點是無法給出資料的内在含義，即沒有顯式的訓練過程，我們不知道式根據哪些特征，如何做出的預測。

4.算法實戰

接下來的每個算法，我們都會說明如何調用Sklearn來實作，說明sklearn各個參數的含義。括号内的均為預設值。

4.1 參數：

• n_neighbors：預設為5，就是k-NN的k的值，選取最近的k個點。
• weights：預設是uniform，參數可以是uniform、distance，也可以是使用者自己定義的函數。uniform是均等的權重，就說所有的鄰近點的權重都是相等的。distance是不均等的權重，距離近的點比距離遠的點的影響大。使用者自定義的函數，接收距離的數組，傳回一組維數相同的權重。
• algorithm：快速k近鄰搜尋算法，預設參數為auto，可以了解為算法自己決定合适的搜尋算法。除此之外，使用者也可以自己指定搜尋算法ball_tree、kd_tree、brute方法進行搜尋，brute是蠻力搜尋，也就是線性掃描，當訓練集很大時，計算非常耗時。kd_tree，構造kd樹存儲資料以便對其進行快速檢索的樹形資料結構，kd樹也就是資料結構中的二叉樹。以中值切分構造的樹，每個結點是一個超矩形，在維數小于20時效率高。ball tree是為了克服kd樹高緯失效而發明的，其構造過程是以質心C和半徑r分割樣本空間，每個節點是一個超球體。
• leaf_size：預設是30，這個是構造的kd樹和ball樹的大小。這個值的設定會影響樹建構的速度和搜尋速度，同樣也影響着存儲樹所需的記憶體大小。需要根據問題的性質選擇最優的大小。
• metric：用于距離度量，預設度量是minkowski，也就是p=2的歐氏距離(歐幾裡德度量)。
• p：距離度量公式。在上小結，我們使用歐氏距離公式進行距離度量。除此之外，還有其他的度量方法，例如曼哈頓距離。這個參數預設為2，也就是預設使用歐式距離公式進行距離度量。也可以設定為1，使用曼哈頓距離公式進行距離度量。
• metric_params：距離公式的其他關鍵參數，這個可以不管，使用預設的None即可。
• n_jobs：并行處理設定。預設為1，臨近點搜尋并行工作數。如果為-1，那麼CPU的所有cores都用于并行工作。

4.2 方法：

• fit(X, y)：使用X作為訓練資料，y作為訓練标簽（目标值）來拟合模型（分類器）
• get_params([deep])：得到分類器的參數
• kneighbors([X, n_neighbors, return_distanced])：傳回一個點的k近鄰
• kneighbors_graph([X, neighbors, mode])：
• predict(X)：預測類别未知資料X的類别
• predict_proba(X)：傳回資料X預測的各類别的機率
• score(X,y[,sample_weight])：對于測試資料，傳回預測的得分結果

• set_params( **params):設定分類器的參數

  用到最多的便是，fit、predict、score

參考資料：

1。《機器學習實戰》

2。《機器學習》-周志華

3。http://blog.csdn.net/c406495762/article/details/75172850#41-knn算法的優缺點

建議閱讀大神的部落格，《機器學習實戰》中代碼有些過時，而且講解不夠明白，他的部落格給出了詳細的過程和解釋，再參閱西瓜書和《機器學習實戰》可以事半功倍。