機器學習的敲門磚：kNN演算法（下）
- 2019 年 10 月 7 日
- 筆記
機器學習的敲門磚：kNN演算法（下）
本文為數據茶水間群友原創，經授權在本公眾號發表。
關於作者：Japson。某人工智慧公司AI平台研發工程師，專註於AI工程化及場景落地。持續學習中，期望與大家多多交流技術以及職業規劃。
0x00 前言
在上一篇文章《機器學習的敲門磚：kNN演算法（中）》中，我們藉助kNN分類演算法，學習了如下知識點：
- 將數據集劃分為訓練數據集和測試數據集，以此驗證模型好壞。
- 在我們得到了分類結果之後，計算出accuracy分類精準度。
- 了解了超參數對模型的影響，並使用網格搜索演算法搜索出最佳超參數組。
但是在前面的實驗中，我們都忽略了相當關鍵的一步，數據歸一化。本篇文章，我們可以學習數據歸一化對演算法的影響及其實現。最後，作為kNN演算法的收尾，我們會總結演算法的優缺點以及優化思路。
0x01 數據歸一化
1.1 為什麼要數據歸一化
在實際應用中，樣本的不同特徵的單位不同，會在求距離時造成很大的影響。比如：在兩個樣本中腫瘤大小的分別為1cm和5cm，發現時間分別為100天和200天，那麼在求距離時，時間差為100、大小差為4，那麼其結果會被時間所主導，因為腫瘤大小的差距太小了。但是如果我們把時間用年做單位，0.27年與0.55年的差距又遠小於腫瘤大小的差距，結果又會被大小主導了。
我們發現，在量綱不同的情況下，以上的情況，不能反映樣本中每一個特徵的重要程度。這就需要數據歸一化了。
一般來說，我們的解決方案是：把所有的數據都映射到同一個尺度（量綱）上。
一般來說，常用的數據歸一化有兩種：
- 最值歸一化(normalization)： 把所有數據映射到0-1之間。 最值歸一化的使用範圍是特徵的分布具有明顯邊界的(分數0～100分、灰度0～255)，受outlier的影響比較大
x_{scale} = frac {x - x_{min}} {x_{max} - x_{min}}
- 均值方差歸一化(standardization)： 把所有數據歸一到均值為0方差為1的分布中。 適用於數據中沒有明顯的邊界，有可能存在極端數據值的情況.
x_{scale} = frac {x - x_{mean}} {S}
1.2 最值歸一化實現
為了了解最值歸一化的程式碼實現，我們可以創建100個隨機數，然後對其進行最值歸一化。
import numpy as np# 創建100個隨機數x = np.random.randint(0,100,size=100)# 最值歸一化（向量）# 最值歸一化公式，映射到0，1之間(x - np.min(x)) / (np.max(x) - np.min(x))# 最值歸一化（矩陣）# 0～100範圍內的50*2的矩陣X = np.random.randint(0,100,(50,2))# 將矩陣改為浮點型X = np.array(X, dtype=float)# 最值歸一化公式，對於每一個維度（列方向）進行歸一化。# X[:,0]第一列，第一個特徵X[:,0] = (X[:,0] - np.min(X[:,0])) / (np.max(X[:,0]) - np.min(X[:,0]))# X[:,1]第二列，第二個特徵X[:,1] = (X[:,1] - np.min(X[:,1])) / (np.max(X[:,1]) - np.min(X[:,1]))# 如果有n個特徵，可以寫個循環：for i in range(0,2): X[:,i] = (X[:,i]-np.min(X[:,i])) / (np.max(X[:,i] - np.min(X[:,i])))
下面我們可以簡單地繪製樣本，並使用np.mean()/np.std()來計算其均值和方差
import matplotlib.pyplot as plt# 簡單繪製樣本，看橫縱坐標plt.scatter(X[:,0],X[:,1]) plt.show()
1.3 均值方差歸一化實現
同樣地，為了了解均值方差歸一化的程式碼實現，我們可以創建100個隨機數，然後對其進行均值方差歸一化。
X2 = np.array(np.random.randint(0,100,(50,2)),dtype=float)# 套用公式，對每一列做均值方差歸一化for i in range(0,2): X2[:,i]=(X2[:,i]-np.mean(X2[:,i])) / np.std(X2[:,i])
下面我們可以簡單地繪製樣本
plt.scatter(X2[:,0],X2[:,1]) plt.show()
計算其均值/方差
np.mean(X2[:,0]) np.std(X2[:,1])
1.4 Sklearn中的歸一化
首先我們來看一個在實際使用歸一化時的一個小陷阱。
我們在建模時要將數據集劃分為訓練數據集&測試數據集。
訓練數據集進行歸一化處理，需要計算出訓練數據集的均值mean_train和方差std_train。
問題是：我們在對測試數據集進行歸一化時，要計算測試數據的均值和方差么？
答案是否定的。在對測試數據集進行歸一化時，仍然要使用訓練數據集的均值train_mean和方差std_train。這是因為測試數據是模擬的真實環境，真實環境中可能無法得到均值和方差，對數據進行歸一化。只能夠使用公式(x_test - mean_train) / std_train 並且，數據歸一化也是演算法的一部分，針對後面所有的數據，也應該做同樣的處理.
因此我們要保存訓練數據集中得到的均值和方差。
在sklearn中專門的用來數據歸一化的方法：StandardScaler。
下面我們載入鳶尾花數據集
import numpy as npfrom sklearn import datasetsfrom sklearn.model_selection import train_test_split iris = datasets.load_iris() X = iris.data y = iris.target X_train,X_test,y_train,y_test = train_test_split(iris.data,iris.target,test_size=0.2,random_state=666)
使用數據歸一化的方法：
from sklearn.preprocessing import StandardScaler standardScaler = StandardScaler()# 歸一化的過程跟訓練模型一樣standardScaler.fit(X_train) standardScaler.mean_ standardScaler.scale_ # 表述數據分布範圍的變數，替代std_# 使用transformX_train_standard = standardScaler.transform(X_train) X_test_standard = standardScaler.transform(X_test)
如此就能輸出歸一化後的數據了。
1.5 自己實現均值方差歸一化
同樣地，我們仿照sklearn的風格，可以自己實現一下均值方差歸一化的方法。
我們在之前的工程中創建processing.py：
import numpy as npclass StandardScaler: def __init__(self): self.mean_ = None self.scale_ = None def fit(self, X): """根據訓練數據集X獲得數據的均值和方差""" assert X.ndim == 2, "The dimension of X must be 2" # 求出每個列的均值 self.mean_ = np.array([np.mean(X[:,i] for i in range(X.shape[1]))]) self.scale_ = np.array([np.std(X[:, i] for i in range(X.shape[1]))]) return self def tranform(self, X): """將X根據StandardScaler進行均值方差歸一化處理""" assert X.ndim == 2, "The dimension of X must be 2" assert self.mean_ is not None and self.scale_ is not None, "must fit before transform" assert X.shape[1] == len(self.mean_), "the feature number of X must be equal to mean_ and std_" # 創建一個空的浮點型矩陣，大小和X相同 resX = np.empty(shape=X.shape, dtype=float) # 對於每一列（維度）都計算 for col in range(X.shape[1]): resX[:,col] = (X[:,col] - self.mean_[col]) / self.scale_[col] return resX
0x02 kNN優缺點
KNN的主要優點有：
- 理論成熟，思想簡單，既可以用來做分類也可以用來做回歸
- 天然解決多分類問題，也可用於回歸問題
- 和樸素貝葉斯之類的演算法比，對數據沒有假設，準確度高，對異常點不敏感
- 由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合
KNN的主要缺點有：
- 計算量大，效率低。 即使優化演算法，效率也不高。
- 高度數據相關，樣本不平衡的時候，對稀有類別的預測準確率低
- 相比決策樹模型，KNN模型可解釋性不強
- 維數災難： 隨著維度的增加，「看似相近」的兩個點之間的距離越來越大，而knn非常依賴距離
|
維數 |
點到點 |
距離 |
|---|---|---|
|
1維 |
0到1的距離 |
1 |
|
2維 |
(0,0)到(1,1)的距離 |
1.414 |
|
3維 |
(0,0,0)到(1,1,1)的距離 |
1.73 |
|
64維 |
(0,0,…0)到(1,1,…1) |
8 |
|
10000維 |
(0,0,…0)到(1,1,…1) |
100 |
大家感覺一萬維貌似很多，但實際上就是100*100像素的黑白灰圖片。
以上就是關於kNN演算法的總結。
你是不是以為這一篇就兩節內容就結束了？沒想到吧！下面還有一波乾貨：kNN優化之KD樹。
3 KD樹
K近鄰法的重要步驟是對所有的實例點進行快速k近鄰搜索。如果採用線性掃描（linear scan），要計算輸入點與每一個點的距離，時間複雜度非常高。因此在查詢操作是，使用kd樹。
3.1 kd樹的原理
kd樹是一種對k維空間中的實例點進行存儲以便對其進行快速檢索的樹形數據結構，且kd樹是一種二叉樹，表示對k維空間的一個劃分。
k-d tree是每個節點均為k維樣本點的二叉樹，其上的每個樣本點代表一個超平面，該超平面垂直於當前劃分維度的坐標軸，並在該維度上將空間劃分為兩部分，一部分在其左子樹，另一部分在其右子樹。即若當前節點的劃分維度為d，其左子樹上所有點在d維的坐標值均小於當前值，右子樹上所有點在d維的坐標值均大於等於當前值，本定義對其任意子節點均成立。
3.2 kd樹的構建
常規的k-d tree的構建過程為：
- 循環依序取數據點的各維度來作為切分維度，
- 取數據點在該維度的中值作為切分超平面，
- 將中值左側的數據點掛在其左子樹，將中值右側的數據點掛在其右子樹，
- 遞歸處理其子樹，直至所有數據點掛載完畢。
對於構建過程，有兩個優化點：
- 選擇切分維度：根據數據點在各維度上的分布情況，方差越大，分布越分散，從方差大的維度開始切分，有較好的切分效果和平衡性。
- 確定中值點：預先對原始數據點在所有維度進行一次排序，存儲下來，然後在後續的中值選擇中，無須每次都對其子集進行排序，提升了性能。也可以從原始數據點中隨機選擇固定數目的點，然後對其進行排序，每次從這些樣本點中取中值，來作為分割超平面。該方式在實踐中被證明可以取得很好性能及很好的平衡性。
例子： 採用常規的構建方式，以二維平面點(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 為例結合下圖來說明k-d tree的構建過程：
- 構建根節點時，此時的切分維度為x，如上點集合在x維從小到大排序為(2,3)，(4,7)，(5,4)，(7,2)，(8,1)，(9,6)； 其中值為(7,2)。 （註： 2,4,5,7,8,9在數學中的中值為(5 + 7)/2=6，但因該演算法的中值需在點集合之內，所以本文中值計算用的是len(points)//2=3, points[3]=(7,2)）
- (2,3)，(4,7)，(5,4)掛在(7,2)節點的左子樹，(8,1)，(9,6)掛在(7,2)節點的右子樹。
- 構建(7,2)節點的左子樹時，點集合(2,3)，(4,7)，(5,4)此時的切分維度為y，中值為(5,4)作為分割平面，(2,3)掛在其左子樹，(4,7)掛在其右子樹。
- 構建(7,2)節點的右子樹時，點集合(8,1)，(9,6)此時的切分維度也為y，中值為(9,6)作為分割平面，(8,1)掛在其左子樹。 至此k-d tree構建完成。
上述的構建過程結合下圖可以看出，構建一個k-d tree即是將一個二維平面逐步劃分的過程。
需要注意的是，對於每次切分，都是循環順序選擇維度的，二維是：x->y->x…；三維則是：x->y->z->x…。
下面從三維空間來看一下k-d tree的構建及空間劃分過程。首先，邊框為紅色的豎直平面將整個空間劃分為兩部分，此兩部分又分別被邊框為綠色的水平平面劃分為上下兩部分。最後此4個子空間又分別被邊框為藍色的豎直平面分割為兩部分，變為8個子空間，此8個子空間即為葉子節點。
# points為實例點集合，depth深度，為用來確定取維度的參數def kd_tree(points, depth): if 0 == len(points): return None # 指定切分維度，len(points[0])是數據的實際維度，這樣計算可以保證循環 cutting_dim = depth % len(points[0]) # 切分點初始化 medium_index = len(points) # 對所有的實例點按照指定維度進行排序，itemgetter用於獲取對象哪些維度上的數據，參數為需要獲取的數據在對象中的序號 points.sort(key=itemgetter(cutting_dim)) # 將該維度的中值點作為根節點 node = Node(points[medium_index]) # 對於左子樹，重複構建（depth+1） node.left = kd_tree(points[:medium_index], depth + 1) # 對於右子樹，重複構建（depth+1） node.right = kd_tree(points[medium_index + 1:], depth + 1) return node
3.3 kd樹的檢索
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)。
3.4 sklearn中的KDTree
Sklearn中有KDTree的實現，僅構建了一個二維空間的k-d tree，然後對其作k近鄰搜索及指定半徑的範圍搜索。多維空間的檢索，調用方式與此例相差無多。
import numpy as npfrom matplotlib import pyplot as pltfrom matplotlib.patches import Circlefrom sklearn.neighbors import KDTree np.random.seed(0) points = np.random.random((100, 2)) tree = KDTree(points) point = points[0]# kNNdists, indices = tree.query([point], k=3) print(dists, indices)# query radiusindices = tree.query_radius([point], r=0.2) print(indices) fig = plt.figure() ax = fig.add_subplot(111, aspect='equal') ax.add_patch(Circle(point, 0.2, color='r', fill=False)) X, Y = [p[0] for p in points], [p[1] for p in points] plt.scatter(X, Y) plt.scatter([point[0]], [point[1]], c='r') plt.show()
影像化展示：
0xFF 總結
到這裡，我們kNN演算法就算告一段落了。我們回顧一下：
在《機器學習的敲門磚：kNN演算法（上）》中，我們了解了非常適合入門機器學習的演算法：k近鄰演算法。
我們學習了kNN演算法的流程，並且在jupyter notebook上手動實現了程式碼，並且在外部也進行了封裝。最後我們學習了sklearn中的kNN演算法。
由此我們引出了疑問：即如何評價模型的好壞。
在《機器學習的敲門磚：kNN演算法（中）》中，我們使用訓練數據集和測試數據集來判斷模型的好壞，給出並實現accurcay這一分類問題常用指標，計算出accuracy分類精準度。最後我們再探尋超參數的選擇對模型的影響。並使用網格搜索演算法搜索出最佳超參數組。
在本篇中，我們學習了數據歸一化對演算法的影響及其實現。作為kNN演算法系列的收尾，我們總結演算法的優缺點。並在最後詳細闡述了kNN優化演算法之一的「KDTree」。
相信大家通過這三篇的學習，已經初步了解了機器學習中最簡單樸素的演算法。現在有很多機器學習的文章筆記，開篇都是玄之又玄的損失函數、梯度下降、L1正則L2正則云云，實屬勸退最佳法寶。但是我們也發現，其實機器學習並沒有想像中的那麼抽象，我們也可以通過程式碼的方式來對其中的概念進行理解。
當然，此三篇文章，包括以後的系列文章，為本人的學習筆記，或稱之為「集注」，是在各位老師前輩基礎上總結歸納而來，拾人牙慧矣。因參考甚多，故不能一一標註出處，還請見諒。
