作者 | Japson

來源 | 木東居士

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的主要優點有：

1. 理論成熟，思想簡單，既可以用來做分類也可以用來做回歸
2. 天然解決多分類問題，也可用于回歸問題
3. 和樸素貝葉斯之類的算法比，對數據沒有假設，準確度高，對異常點不敏感
4. 由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合

KNN的主要缺點有：

1. 計算量大，效率低。
2. 即使優化算法，效率也不高。
3. 高度數據相關，樣本不平衡的時候，對稀有類別的預測準確率低
4. 相比決策樹模型，KNN模型可解釋性不強
5. 維數災難：
6. 隨著維度的增加，“看似相近”的兩個點之間的距離越來越大，而knn非常依賴距離

大家感覺一萬維貌似很多，但實際上就是100*100像素的黑白灰圖片。

以上就是關于kNN算法的總結。

你是不是以為這一篇就兩節內容就結束了？沒想到吧！下面還有一波干貨：kNN優化之KD樹。

0x03 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的構建過程為：

1. 循環依序取數據點的各維度來作為切分維度，
2. 取數據點在該維度的中值作為切分超平面，
3. 將中值左側的數據點掛在其左子樹，將中值右側的數據點掛在其右子樹，
4. 遞歸處理其子樹，直至所有數據點掛載完畢。

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

• 選擇切分維度：根據數據點在各維度上的分布情況，方差越大，分布越分散，從方差大的維度開始切分，有較好的切分效果和平衡性。
• 確定中值點：預先對原始數據點在所有維度進行一次排序，存儲下來，然后在后續的中值選擇中，無須每次都對其子集進行排序，提升了性能。也可以從原始數據點中隨機選擇固定數目的點，然后對其進行排序，每次從這些樣本點中取中值，來作為分割超平面。該方式在實踐中被證明可以取得很好性能及很好的平衡性。

例子：

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

1. 構建根節點時，此時的切分維度為x，如上點集合在x維從小到大排序為(2,3)，(4,7)，(5,4)，(7,2)，(8,1)，(9,6)；
2. 其中值為(7,2)。
3. （注：
4. 2,4,5,7,8,9在數學中的中值為(5 + 7)/2=6，但因該算法的中值需在點集合之內，所以本文中值計算用的是len(points)//2=3, points[3]=(7,2)）
5. (2,3)，(4,7)，(5,4)掛在(7,2)節點的左子樹，(8,1)，(9,6)掛在(7,2)節點的右子樹。
6. 構建(7,2)節點的左子樹時，點集合(2,3)，(4,7)，(5,4)此時的切分維度為y，中值為(5,4)作為分割平面，(2,3)掛在其左子樹，(4,7)掛在其右子樹。
7. 構建(7,2)節點的右子樹時，點集合(8,1)，(9,6)此時的切分維度也為y，中值為(9,6)作為分割平面，(8,1)掛在其左子樹。
8. 至此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”。

相信大家通過這三篇的學習，已經初步了解了機器學習中最簡單樸素的算法?，F在有很多機器學習的文章筆記，開篇都是玄之又玄的損失函數、梯度下降、L1正則L2正則云云，實屬勸退最佳法寶。但是我們也發現，其實機器學習并沒有想象中的那么抽象，我們也可以通過代碼的方式來對其中的概念進行理解。

當然，此三篇文章，包括以后的系列文章，為本人的學習筆記，或稱之為“集注”，是在各位老師前輩基礎上總結歸納而來，拾人牙慧矣。因參考甚多，故不能一一標注出處，還請見諒。