作者 | Japson

來(lái)源 | 木東居士

0x00 前言

在上一篇文章《機(jī)器學(xué)習(xí)的敲門磚：kNN算法（中）》中，我們借助kNN分類算法，學(xué)習(xí)了如下知識(shí)點(diǎn)：

• 將數(shù)據(jù)集劃分為訓(xùn)練數(shù)據(jù)集和測(cè)試數(shù)據(jù)集，以此驗(yàn)證模型好壞。
• 在我們得到了分類結(jié)果之后，計(jì)算出accuracy分類精準(zhǔn)度。
• 了解了超參數(shù)對(duì)模型的影響，并使用網(wǎng)格搜索算法搜索出最佳超參數(shù)組。

但是在前面的實(shí)驗(yàn)中，我們都忽略了相當(dāng)關(guān)鍵的一步，數(shù)據(jù)歸一化。本篇文章，我們可以學(xué)習(xí)數(shù)據(jù)歸一化對(duì)算法的影響及其實(shí)現(xiàn)。最后，作為kNN算法的收尾，我們會(huì)總結(jié)算法的優(yōu)缺點(diǎn)以及優(yōu)化思路。

0x01 數(shù)據(jù)歸一化

1.1 為什么要數(shù)據(jù)歸一化

在實(shí)際應(yīng)用中，樣本的不同特征的單位不同，會(huì)在求距離時(shí)造成很大的影響。比如：在兩個(gè)樣本中腫瘤大小的分別為1cm和5cm，發(fā)現(xiàn)時(shí)間分別為100天和200天，那么在求距離時(shí)，時(shí)間差為100、大小差為4，那么其結(jié)果會(huì)被時(shí)間所主導(dǎo)，因?yàn)槟[瘤大小的差距太小了。但是如果我們把時(shí)間用年做單位，0.27年與0.55年的差距又遠(yuǎn)小于腫瘤大小的差距，結(jié)果又會(huì)被大小主導(dǎo)了。

我們發(fā)現(xiàn)，在量綱不同的情況下，以上的情況，不能反映樣本中每一個(gè)特征的重要程度。這就需要數(shù)據(jù)歸一化了。

一般來(lái)說(shuō)，我們的解決方案是：把所有的數(shù)據(jù)都映射到同一個(gè)尺度（量綱）上。

一般來(lái)說(shuō)，常用的數(shù)據(jù)歸一化有兩種：

• 最值歸一化(normalization)： 把所有數(shù)據(jù)映射到0-1之間。
• 最值歸一化的使用范圍是特征的分布具有明顯邊界的(分?jǐn)?shù)0～100分、灰度0～255)，受outlier的影響比較大

x_{scale} = \frac {x - x_{min}} {x_{max} - x_{min}}

• 均值方差歸一化(standardization)： 把所有數(shù)據(jù)歸一到均值為0方差為1的分布中。
• 適用于數(shù)據(jù)中沒有明顯的邊界，有可能存在極端數(shù)據(jù)值的情況.

x_{scale} = \frac {x - x_{mean}} {S}

1.2 最值歸一化實(shí)現(xiàn)

為了了解最值歸一化的代碼實(shí)現(xiàn)，我們可以創(chuàng)建100個(gè)隨機(jī)數(shù)，然后對(duì)其進(jìn)行最值歸一化。

import numpy as np# 創(chuàng)建100個(gè)隨機(jī)數(shù)x = np.random.randint(0,100,size=100)# 最值歸一化（向量）# 最值歸一化公式，映射到0，1之間(x - np.min(x)) / (np.max(x) - np.min(x))# 最值歸一化（矩陣）# 0～100范圍內(nèi)的50*2的矩陣X = np.random.randint(0,100,(50,2))# 將矩陣改為浮點(diǎn)型X = np.array(X, dtype=float)# 最值歸一化公式，對(duì)于每一個(gè)維度（列方向）進(jìn)行歸一化。# X[:,0]第一列，第一個(gè)特征X[:,0] = (X[:,0] - np.min(X[:,0])) / (np.max(X[:,0]) - np.min(X[:,0]))# X[:,1]第二列，第二個(gè)特征X[:,1] = (X[:,1] - np.min(X[:,1])) / (np.max(X[:,1]) - np.min(X[:,1]))# 如果有n個(gè)特征，可以寫個(gè)循環(huán)：for i in range(0,2):
 X[:,i] = (X[:,i]-np.min(X[:,i])) / (np.max(X[:,i] - np.min(X[:,i])))

下面我們可以簡(jiǎn)單地繪制樣本，并使用np.mean()/np.std()來(lái)計(jì)算其均值和方差

import matplotlib.pyplot as plt# 簡(jiǎn)單繪制樣本，看橫縱坐標(biāo)plt.scatter(X[:,0],X[:,1])
plt.show()

1.3 均值方差歸一化實(shí)現(xiàn)

同樣地，為了了解均值方差歸一化的代碼實(shí)現(xiàn)，我們可以創(chuàng)建100個(gè)隨機(jī)數(shù)，然后對(duì)其進(jìn)行均值方差歸一化。

X2 = np.array(np.random.randint(0,100,(50,2)),dtype=float)# 套用公式，對(duì)每一列做均值方差歸一化for i in range(0,2):
 X2[:,i]=(X2[:,i]-np.mean(X2[:,i])) / np.std(X2[:,i])

下面我們可以簡(jiǎn)單地繪制樣本

plt.scatter(X2[:,0],X2[:,1])
plt.show()

計(jì)算其均值/方差

np.mean(X2[:,0])
np.std(X2[:,1])

1.4 Sklearn中的歸一化

首先我們來(lái)看一個(gè)在實(shí)際使用歸一化時(shí)的一個(gè)小陷阱。

我們?cè)诮r(shí)要將數(shù)據(jù)集劃分為訓(xùn)練數(shù)據(jù)集&測(cè)試數(shù)據(jù)集。

訓(xùn)練數(shù)據(jù)集進(jìn)行歸一化處理，需要計(jì)算出訓(xùn)練數(shù)據(jù)集的均值mean_train和方差std_train。

問(wèn)題是：我們?cè)趯?duì)測(cè)試數(shù)據(jù)集進(jìn)行歸一化時(shí)，要計(jì)算測(cè)試數(shù)據(jù)的均值和方差么？

答案是否定的。在對(duì)測(cè)試數(shù)據(jù)集進(jìn)行歸一化時(shí)，仍然要使用訓(xùn)練數(shù)據(jù)集的均值train_mean和方差std_train。這是因?yàn)闇y(cè)試數(shù)據(jù)是模擬的真實(shí)環(huán)境，真實(shí)環(huán)境中可能無(wú)法得到均值和方差，對(duì)數(shù)據(jù)進(jìn)行歸一化。只能夠使用公式(x_test - mean_train) / std_train

并且，數(shù)據(jù)歸一化也是算法的一部分，針對(duì)后面所有的數(shù)據(jù)，也應(yīng)該做同樣的處理.

因此我們要保存訓(xùn)練數(shù)據(jù)集中得到的均值和方差。

在sklearn中專門的用來(lái)數(shù)據(jù)歸一化的方法：StandardScaler。

下面我們加載鳶尾花數(shù)據(jù)集

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)

使用數(shù)據(jù)歸一化的方法：

from sklearn.preprocessing import StandardScaler
standardScaler = StandardScaler()# 歸一化的過(guò)程跟訓(xùn)練模型一樣standardScaler.fit(X_train)
standardScaler.mean_
standardScaler.scale_ # 表述數(shù)據(jù)分布范圍的變量，替代std_# 使用transformX_train_standard = standardScaler.transform(X_train)
X_test_standard = standardScaler.transform(X_test)

如此就能輸出歸一化后的數(shù)據(jù)了。

1.5 自己實(shí)現(xiàn)均值方差歸一化

同樣地，我們仿照sklearn的風(fēng)格，可以自己實(shí)現(xiàn)一下均值方差歸一化的方法。

我們?cè)谥暗墓こ讨袆?chuàng)建processing.py：

import numpy as npclass StandardScaler:
 def __init__(self):
 self.mean_ = None
 self.scale_ = None
 def fit(self, X):
 """根據(jù)訓(xùn)練數(shù)據(jù)集X獲得數(shù)據(jù)的均值和方差"""
 assert X.ndim == 2, "The dimension of X must be 2"
 # 求出每個(gè)列的均值
 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根據(jù)StandardScaler進(jìn)行均值方差歸一化處理"""
 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_"
 # 創(chuàng)建一個(gè)空的浮點(diǎn)型矩陣，大小和X相同
 resX = np.empty(shape=X.shape, dtype=float) # 對(duì)于每一列（維度）都計(jì)算
 for col in range(X.shape[1]):
 resX[:,col] = (X[:,col] - self.mean_[col]) / self.scale_[col] return resX

0x02 kNN優(yōu)缺點(diǎn)

KNN的主要優(yōu)點(diǎn)有：

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

KNN的主要缺點(diǎn)有：

1. 計(jì)算量大，效率低。
2. 即使優(yōu)化算法，效率也不高。
3. 高度數(shù)據(jù)相關(guān)，樣本不平衡的時(shí)候，對(duì)稀有類別的預(yù)測(cè)準(zhǔn)確率低
4. 相比決策樹模型，KNN模型可解釋性不強(qiáng)
5. 維數(shù)災(zāi)難：
6. 隨著維度的增加，“看似相近”的兩個(gè)點(diǎn)之間的距離越來(lái)越大，而knn非常依賴距離

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

以上就是關(guān)于kNN算法的總結(jié)。

你是不是以為這一篇就兩節(jié)內(nèi)容就結(jié)束了？沒想到吧！下面還有一波干貨：kNN優(yōu)化之KD樹。

0x03 KD樹

K近鄰法的重要步驟是對(duì)所有的實(shí)例點(diǎn)進(jìn)行快速k近鄰搜索。如果采用線性掃描（linear scan），要計(jì)算輸入點(diǎn)與每一個(gè)點(diǎn)的距離，時(shí)間復(fù)雜度非常高。因此在查詢操作是，使用kd樹。

3.1 kd樹的原理

kd樹是一種對(duì)k維空間中的實(shí)例點(diǎn)進(jìn)行存儲(chǔ)以便對(duì)其進(jìn)行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)，且kd樹是一種二叉樹，表示對(duì)k維空間的一個(gè)劃分。

k-d tree是每個(gè)節(jié)點(diǎn)均為k維樣本點(diǎn)的二叉樹，其上的每個(gè)樣本點(diǎn)代表一個(gè)超平面，該超平面垂直于當(dāng)前劃分維度的坐標(biāo)軸，并在該維度上將空間劃分為兩部分，一部分在其左子樹，另一部分在其右子樹。即若當(dāng)前節(jié)點(diǎn)的劃分維度為d，其左子樹上所有點(diǎn)在d維的坐標(biāo)值均小于當(dāng)前值，右子樹上所有點(diǎn)在d維的坐標(biāo)值均大于等于當(dāng)前值，本定義對(duì)其任意子節(jié)點(diǎn)均成立。

3.2 kd樹的構(gòu)建

常規(guī)的k-d tree的構(gòu)建過(guò)程為：

1. 循環(huán)依序取數(shù)據(jù)點(diǎn)的各維度來(lái)作為切分維度，
2. 取數(shù)據(jù)點(diǎn)在該維度的中值作為切分超平面，
3. 將中值左側(cè)的數(shù)據(jù)點(diǎn)掛在其左子樹，將中值右側(cè)的數(shù)據(jù)點(diǎn)掛在其右子樹，
4. 遞歸處理其子樹，直至所有數(shù)據(jù)點(diǎn)掛載完畢。

對(duì)于構(gòu)建過(guò)程，有兩個(gè)優(yōu)化點(diǎn)：

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

例子：

采用常規(guī)的構(gòu)建方式，以二維平面點(diǎn)(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 為例結(jié)合下圖來(lái)說(shuō)明k-d tree的構(gòu)建過(guò)程：

1. 構(gòu)建根節(jié)點(diǎn)時(shí)，此時(shí)的切分維度為x，如上點(diǎn)集合在x維從小到大排序?yàn)?2,3)，(4,7)，(5,4)，(7,2)，(8,1)，(9,6)；
2. 其中值為(7,2)。
3. （注：
4. 2,4,5,7,8,9在數(shù)學(xué)中的中值為(5 + 7)/2=6，但因該算法的中值需在點(diǎn)集合之內(nèi)，所以本文中值計(jì)算用的是len(points)//2=3, points[3]=(7,2)）
5. (2,3)，(4,7)，(5,4)掛在(7,2)節(jié)點(diǎn)的左子樹，(8,1)，(9,6)掛在(7,2)節(jié)點(diǎn)的右子樹。
6. 構(gòu)建(7,2)節(jié)點(diǎn)的左子樹時(shí)，點(diǎn)集合(2,3)，(4,7)，(5,4)此時(shí)的切分維度為y，中值為(5,4)作為分割平面，(2,3)掛在其左子樹，(4,7)掛在其右子樹。
7. 構(gòu)建(7,2)節(jié)點(diǎn)的右子樹時(shí)，點(diǎn)集合(8,1)，(9,6)此時(shí)的切分維度也為y，中值為(9,6)作為分割平面，(8,1)掛在其左子樹。
8. 至此k-d tree構(gòu)建完成。

上述的構(gòu)建過(guò)程結(jié)合下圖可以看出，構(gòu)建一個(gè)k-d tree即是將一個(gè)二維平面逐步劃分的過(guò)程。

需要注意的是，對(duì)于每次切分，都是循環(huán)順序選擇維度的，二維是：x->y->x…；三維則是：x->y->z->x…。

下面從三維空間來(lái)看一下k-d tree的構(gòu)建及空間劃分過(guò)程。首先，邊框?yàn)榧t色的豎直平面將整個(gè)空間劃分為兩部分，此兩部分又分別被邊框?yàn)榫G色的水平平面劃分為上下兩部分。最后此4個(gè)子空間又分別被邊框?yàn)樗{(lán)色的豎直平面分割為兩部分，變?yōu)?個(gè)子空間，此8個(gè)子空間即為葉子節(jié)點(diǎn)。

# points為實(shí)例點(diǎn)集合，depth深度，為用來(lái)確定取維度的參數(shù)def kd_tree(points, depth): 
 if 0 == len(points): return None
 # 指定切分維度，len(points[0])是數(shù)據(jù)的實(shí)際維度，這樣計(jì)算可以保證循環(huán)
 cutting_dim = depth % len(points[0]) # 切分點(diǎn)初始化
 medium_index = len(points) # 對(duì)所有的實(shí)例點(diǎn)按照指定維度進(jìn)行排序，itemgetter用于獲取對(duì)象哪些維度上的數(shù)據(jù)，參數(shù)為需要獲取的數(shù)據(jù)在對(duì)象中的序號(hào)
 points.sort(key=itemgetter(cutting_dim))
 # 將該維度的中值點(diǎn)作為根節(jié)點(diǎn)
 node = Node(points[medium_index])
 # 對(duì)于左子樹，重復(fù)構(gòu)建（depth+1）
 node.left = kd_tree(points[:medium_index], depth + 1)
 # 對(duì)于右子樹，重復(fù)構(gòu)建（depth+1）
 node.right = kd_tree(points[medium_index + 1:], depth + 1)
 return node

3.3 kd樹的檢索

kd樹的檢索是KNN算法至關(guān)重要的一步，給定點(diǎn)p，查詢數(shù)據(jù)集中與其距離最近點(diǎn)的過(guò)程即為最近鄰搜索。

如在構(gòu)建好的k-d tree上搜索(3,5)的最近鄰時(shí)，對(duì)二維空間的最近鄰搜索過(guò)程作分析。首先從根節(jié)點(diǎn)(7,2)出發(fā)，將當(dāng)前最近鄰設(shè)為(7,2)，對(duì)該k-d tree作深度優(yōu)先遍歷。以(3,5)為圓心，其到(7,2)的距離為半徑畫圓（多維空間為超球面），可以看出(8,1)右側(cè)的區(qū)域與該圓不相交，所以(8,1)的右子樹全部忽略。接著走到(7,2)左子樹根節(jié)點(diǎn)(5,4)，與原最近鄰對(duì)比距離后，更新當(dāng)前最近鄰為(5,4)。以(3,5)為圓心，其到(5,4)的距離為半徑畫圓，發(fā)現(xiàn)(7,2)右側(cè)的區(qū)域與該圓不相交，忽略該側(cè)所有節(jié)點(diǎn)，這樣(7,2)的整個(gè)右子樹被標(biāo)記為已忽略。遍歷完(5,4)的左右葉子節(jié)點(diǎn)，發(fā)現(xiàn)與當(dāng)前最優(yōu)距離相等，不更新最近鄰。所以(3,5)的最近鄰為(5,4)。

3.4 sklearn中的KDTree

Sklearn中有KDTree的實(shí)現(xiàn)，僅構(gòu)建了一個(gè)二維空間的k-d tree，然后對(duì)其作k近鄰搜索及指定半徑的范圍搜索。多維空間的檢索，調(diào)用方式與此例相差無(wú)多。

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 總結(jié)

到這里，我們kNN算法就算告一段落了。我們回顧一下：

在《機(jī)器學(xué)習(xí)的敲門磚：kNN算法（上）》中，我們了解了非常適合入門機(jī)器學(xué)習(xí)的算法：k近鄰算法。

我們學(xué)習(xí)了kNN算法的流程，并且在jupyter notebook上手動(dòng)實(shí)現(xiàn)了代碼，并且在外部也進(jìn)行了封裝。最后我們學(xué)習(xí)了sklearn中的kNN算法。

由此我們引出了疑問(wèn)：即如何評(píng)價(jià)模型的好壞。

在《機(jī)器學(xué)習(xí)的敲門磚：kNN算法（中）》中，我們使用訓(xùn)練數(shù)據(jù)集和測(cè)試數(shù)據(jù)集來(lái)判斷模型的好壞，給出并實(shí)現(xiàn)accurcay這一分類問(wèn)題常用指標(biāo)，計(jì)算出accuracy分類精準(zhǔn)度。最后我們?cè)偬綄こ瑓?shù)的選擇對(duì)模型的影響。并使用網(wǎng)格搜索算法搜索出最佳超參數(shù)組。

在本篇中，我們學(xué)習(xí)了數(shù)據(jù)歸一化對(duì)算法的影響及其實(shí)現(xiàn)。作為kNN算法系列的收尾，我們總結(jié)算法的優(yōu)缺點(diǎn)。并在最后詳細(xì)闡述了kNN優(yōu)化算法之一的“KDTree”。

相信大家通過(guò)這三篇的學(xué)習(xí)，已經(jīng)初步了解了機(jī)器學(xué)習(xí)中最簡(jiǎn)單樸素的算法?，F(xiàn)在有很多機(jī)器學(xué)習(xí)的文章筆記，開篇都是玄之又玄的損失函數(shù)、梯度下降、L1正則L2正則云云，實(shí)屬勸退最佳法寶。但是我們也發(fā)現(xiàn)，其實(shí)機(jī)器學(xué)習(xí)并沒有想象中的那么抽象，我們也可以通過(guò)代碼的方式來(lái)對(duì)其中的概念進(jìn)行理解。

當(dāng)然，此三篇文章，包括以后的系列文章，為本人的學(xué)習(xí)筆記，或稱之為“集注”，是在各位老師前輩基礎(chǔ)上總結(jié)歸納而來(lái)，拾人牙慧矣。因參考甚多，故不能一一標(biāo)注出處，還請(qǐng)見諒。