機器學習-KNN演演算法

1. 演演算法原理（K-Nearest Neighbor）

本質是通過距離判斷兩個樣本是否相似，如果距離夠近就認為他們足夠相似屬於同一類別
找到離其最近的 k 個樣本，並將這些樣本稱之為「近鄰」(nearest neighbor)。
對這 k 個近鄰，檢視它們的都屬於何種類別（這些類別我們稱作「標籤」 (labels)）。
然後根據「少數服從多數，一點算一票」原則進行判斷，數量最多的的標籤類別就是新樣本的標籤類別。
其中涉及到的原理是「越相近越相似」，這也是KNN的基本假設。

2. 實現過程和距離的確定

1）實現過程

假設 X_test 待標記的資料樣本，X_train 為已標記的資料集。
- 遍歷已標記資料集中所有的樣本，計算每個樣本與待標記點的距離，並把距離儲存在 Distance 陣列中。
- 對 Distance 陣列進行排序，取距離最近的 k 個點，記為 X_knn.
- 在 X_knn 中統計每個類別的個數，即 class0 在 X_knn 中有幾個樣本，class1 在 X_knn 中有幾個樣本等。
- 待標記樣本的類別，就是在 X_knn 中樣本個數最多的那個類別。

2）距離的確定

該演演算法的「距離」在二維座標軸就表示兩點之間的距離，計算距離的公式有很多。
我們常用尤拉公式，即「歐氏距離」。(x₁、x₂、x₃為特徵)
$$
\sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2 + (x_3 - y_3)^2+...+(x_n - y_n)^2} =\sqrt{ \sum_{i=1}^{{n}{(x_i-y_i)}2}}
$$

3. 演演算法優缺點

演演算法超引數是 k（人為設定的引數為超引數），k 可以理解為標記資料周圍幾個數作為參考物件，引數選擇需要根據資料來決定。（通過學習曲線找最優的k）

k 值越大，模型的偏差越大，對噪聲資料越不敏感。
k 值很大時，可能造成模型欠擬合。
k 值越小，模型的方差就會越大。
但是 k 值太小，容易過擬合

4. 演演算法的變種

變種一：預設情況下，在計算距離時，權重都是相同的，但實際上我們可以針對不同的鄰居指定不同的距離權重，比如距離越近權重越高。

這個可以通過指定演演算法的 weights 引數來實現。

變種二：使用一定半徑內的點取代距離最近的 k 個點

在 scikit-learn 中，RadiusNeighborsClassifier 實現了這種演演算法的變種。
當資料取樣不均勻時，該演演算法變種可以取得更好的效能。

5. Python程式碼實現KNN

紅酒案例

# 紅酒引數
rowdata = {'顏色深度':[14.13,13.2,13.16,14.27,13.24,12.07,12.43,11.79,12.37,12.04],
'酒精濃度': [5.64,4.28,5.68,4.80,4.22,2.76,3.94,3.1,2.12,2.6],
'品種': [0,0,0,0,0,1,1,1,1,1]}
# 0 代表 「黑皮諾」，1 代表 「赤霞珠」
wine_data = pd.DataFrame(rowdata)

   def KNN(x):  #x是輸入的點  返回類別
       # 1.把10個訓練資料提取到data中
       data = wine_data.iloc[:,:2].values #將前兩列提取出來----data
   
       # 2. 新資料點與10個一維陣列的歐式距離
       # 資料點第一個特徵與10個點的歐式距離
       a = ((x-data) ** 2)[:,0] #第一列抽取出來
       # 資料點第二個特徵與10個點的歐式距離
       b = ((x-data) ** 2)[:,1] #第二列抽取出來
       # 得到資料點與10個點的歐氏距離
       Distance = np.sqrt(a+b)
       np.sort(Distance)
       # 3.排序找出最近的K個點   K=3
       K3 = np.argsort(Distance)[:3] #得到開始表的索引值     6 1 4
   
       # 4.判斷類別
       y = wine_data.品種
       # 根據頻數統計判斷屬於哪一類
       return pd.Series([y[i] for i in K3]).value_counts().idxmax()

   KNN([[12.3,4.1]])
   # OUT：0

6. SCIKIT-LEARN演演算法庫實現KNN（見WineSortKNN.ipynb）

scikit-learn，簡稱 sklearn，支援了包括分類、迴歸、降維和聚類四大機器學習演演算法，以及特徵提取、資料預處理和模型評估三大模組。
主要設計原則：
1）一致性

所有物件共用一個簡單一致的介面(介面)。
- 估算器：fit()方法。基於資料估算引數的任意物件，使用的引數是一個資料集(對應 X, 有監督演演算法
  還需要一個 y)，引導估算過程的任意其他引數稱為超引數，必須被設定為範例變數。
- 轉換器：transform()方法。使用估算器轉換資料集，轉換過程依賴於學習引數。可以使用便捷方
  式: fit_transform()，相當於先 fit()再 transform()。(fit_transform 有時被優化過，速度更快)
- 預測器：predict()方法。使用估算器預測新資料，返回包含預測結果的資料，還有score()方法:用
  於度量給定測試集的預測效果的好壞。(連續 y 使用 R 方,分類 y 使用準確率 accuracy)
2）監控
- 檢查所有引數，所有估算器的超引數可以通過公共範例變數存取，所有估算器的學習引數都可以通過有下劃線字尾的公共範例變數存取。
3）防止類擴散
- 物件型別固定，資料集被表示為 Numpy 陣列或 Scipy 稀疏矩陣，超參是普通的 Python 字元或數位。
4）合成
- 現有的構件儘可能重用，可以輕鬆建立一個流水線 Pipeline。
5）合理預設值
- 大多數引數提供合理預設值，可以輕鬆搭建一個基本的工作系統
6）SKlearn KNN 實現
```
class sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, *, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=None)[source]
```

引數名	形式	意義
n_neighbors	int, default=5	近鄰個數
weights	{‘uniform’, ‘distance’}, callable or None, default=’uniform’	• 'uniform'：預設引數，不管遠近權重都一樣，就是最普通的 KNN 演演算法的形式。 • 'distance'：權重和距離成反比，距離預測目標越近具有越高的權重。 • 自定義函數：自定義一個函數，根據輸入的座標值返回對應的權重，達到自定義權重的目的。
algorithm	{‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’}, default=’auto’	•'brute' ：蠻力實現 • 'kd_tree'：KD 樹實現 KNN • 'ball_tree'：球樹實現 KNN • 'auto'：預設引數，自動選擇合適的方法構建模型
leaf_size	int, default=30	當使用KD樹或球樹，它就是是停止建子樹的葉子節點數量的閾值
p	int, default=2	p=1為曼哈頓距離 p=2為歐式距離
metric	str or callable, default=’minkowski‘	• 'euclidean' ：歐式距離 • 'manhattan'：曼哈頓距離 • 'chebyshev'：切比雪夫距離 • 'minkowski'：閔可夫斯基距離，預設引數
n_jobs	int, default=None	指定多少個CPU進行運算，-1表示全部都算

紅酒案例

from sklearn.neighbors import KNeighborsClassifier

clf = KNeighborsClassifier(n_neighbors=3)
clf = clf.fit(wine_data.iloc[:,0:2].values,wine_data.iloc[:,-1].values)

#測試單個點
clf.predict([[12.3,4.1]])

# OUT: array([0]) 屬於「黑皮諾」紅酒