作者 | Japson

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

0x00 前言

天下苦數(shù)學(xué)久矣！

對(duì)于很多想要入門(mén)機(jī)器學(xué)習(xí)的工程師來(lái)說(shuō)，數(shù)學(xué)是通往AI道路上的第一支攔路虎。一些已經(jīng)工作的同學(xué)不得不撿起早已還給老師的數(shù)學(xué)知識(shí)，勉強(qiáng)拿起《統(tǒng)計(jì)學(xué)習(xí)方法》、《西瓜書(shū)》等入門(mén)書(shū)籍鉆研?；虮灰粋€(gè)個(gè)復(fù)雜的機(jī)公式勸退，或記下一堆公式定理之后卻不知道和代碼有什么關(guān)系，茫然不知所措。

其實(shí)對(duì)于工程師來(lái)說(shuō)，最直接的入門(mén)方法就是coding。

本系列從最簡(jiǎn)單的機(jī)器學(xué)習(xí)算法“K-近鄰算法”開(kāi)始，通過(guò)代碼走進(jìn)機(jī)器學(xué)習(xí)的大門(mén)，搞定傳統(tǒng)機(jī)器學(xué)習(xí)算法。

首先會(huì)介紹算法的基本原理，然后依據(jù)原理手動(dòng)實(shí)現(xiàn)算法，最后使用sklearn中提供的機(jī)器學(xué)習(xí)庫(kù)完成一些小demo。不用擔(dān)心，相關(guān)的機(jī)器學(xué)習(xí)概念以及算法原理也會(huì)穿插其中，幫助你以“代碼->原理->代碼”這種迭代的方式完成學(xué)習(xí)。

需要：

掌握Python語(yǔ)言，能夠使用Numpy、Pandas等工具庫(kù)。

安裝Anaconda

不要求對(duì)機(jī)器學(xué)習(xí)算法以及相關(guān)概念有很深刻的了解，因?yàn)樵谖恼轮袝?huì)對(duì)首次出現(xiàn)的概念進(jìn)行介紹。

子曰：“先行其言而后從之”。行動(dòng)永遠(yuǎn)是引發(fā)改變的第一步，話(huà)不多說(shuō)，先讓我們碼起來(lái)吧！

0x01 初探kNN算法

為什么選擇kNN

為什么說(shuō)KNN算法是機(jī)器學(xué)習(xí)的敲門(mén)磚？

首先KNN算法思想簡(jiǎn)單樸素，容易理解，幾乎不需要任何數(shù)學(xué)知識(shí)。這一點(diǎn)使得KNN算法非常適合入門(mén)。

其次，KNN算法也很好用，理論成熟，簡(jiǎn)單粗暴，既可以用來(lái)做分類(lèi)（天然支持多分類(lèi)），也可以用來(lái)做回歸。并且與樸素貝葉斯之類(lèi)的算法相比，由于其對(duì)數(shù)據(jù)沒(méi)有假設(shè)，因此準(zhǔn)確度高，對(duì)異常點(diǎn)不敏感。

最后，kNN算法簡(jiǎn)單，但是可以解釋機(jī)器學(xué)習(xí)算法過(guò)程中的很多細(xì)節(jié)問(wèn)題，能夠完整的刻畫(huà)機(jī)器學(xué)習(xí)應(yīng)用的流程。

當(dāng)然KNN算法也有缺點(diǎn)，我們會(huì)在最后進(jìn)行總結(jié)。

kNN思想簡(jiǎn)介

魯迅曾經(jīng)說(shuō)過(guò)：“想要了解一個(gè)人，就去看看他的朋友”。因此，KNN算法是魯迅發(fā)明的。

kNN(k-NearestNeighbor)，也就是k最近鄰算法。顧名思義，所謂K最近鄰，就是k個(gè)最近的鄰居的意思。也就是在數(shù)據(jù)集中，認(rèn)為每個(gè)樣本可以用離他最距離近的k個(gè)鄰居來(lái)代表。

貼出一張從百度百科上找的一張圖，我們可以直觀地感受到這樸素的思想：我們要判斷Xu 是什么顏色的，找到與其距離最近的5個(gè)點(diǎn)，有4個(gè)是紅色的，有1個(gè)是綠色的。因此我們認(rèn)為Xu是屬于紅色的集合

因此我們說(shuō)：

在一個(gè)給定的類(lèi)別已知的訓(xùn)練樣本集中，已知樣本集中每一個(gè)數(shù)據(jù)與所屬分類(lèi)的對(duì)應(yīng)關(guān)系（標(biāo)簽）。在輸入不含有標(biāo)簽的新樣本后，將新的數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)對(duì)應(yīng)的特征進(jìn)行比較，然后算法提取樣本最相似的k個(gè)數(shù)據(jù)(最近鄰)的分類(lèi)標(biāo)簽。通過(guò)多數(shù)表決等方式進(jìn)行預(yù)測(cè)。即選擇k個(gè)最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類(lèi)，作為新數(shù)據(jù)的分類(lèi)。

K近鄰法不具有顯式的學(xué)習(xí)過(guò)程，而是利用訓(xùn)練數(shù)據(jù)集對(duì)特征向量空間進(jìn)行劃分，并作為其分類(lèi)的“模型”。

kNN算法流程

通過(guò)理解算法思想，可以將其簡(jiǎn)化為“找鄰居+投票”。K近鄰法使用的模型，實(shí)際上是特征空間的劃分。模型由三個(gè)基本要素決定：

• 距離度量
• k值
• 分類(lèi)決策規(guī)則

其中兩個(gè)實(shí)例點(diǎn)之間的距離反映了相似程度。一般來(lái)說(shuō)使用歐氏距離來(lái)計(jì)算。

梳理kNN算法流程如下：

1. 計(jì)算測(cè)試對(duì)象到訓(xùn)練集中每個(gè)對(duì)象的距離
2. 按照距離的遠(yuǎn)近排序
3. 選取與當(dāng)前測(cè)試對(duì)象最近的k的訓(xùn)練對(duì)象，作為該測(cè)試對(duì)象的鄰居
4. 統(tǒng)計(jì)這k個(gè)鄰居的類(lèi)別頻率
5. k個(gè)鄰居里頻率最高的類(lèi)別，即為測(cè)試對(duì)象的類(lèi)別

0x02 算法實(shí)現(xiàn)

kNN算法自實(shí)現(xiàn)

打開(kāi)Jupyter Notebook，創(chuàng)建Python3文件。

準(zhǔn)備數(shù)據(jù)

首先我們準(zhǔn)備一組數(shù)據(jù)：

import numpy as npimport matplotlib.pyplot as plt# raw_data_x是特征，raw_data_y是標(biāo)簽，0為良性，1為惡性raw_data_X = [[3.393533211, 2.331273381],
 [3.110073483, 1.781539638],
 [1.343853454, 3.368312451],
 [3.582294121, 4.679917921],
 [2.280362211, 2.866990212],
 [7.423436752, 4.685324231],
 [5.745231231, 3.532131321],
 [9.172112222, 2.511113104],
 [7.927841231, 3.421455345],
 [7.939831414, 0.791631213]
 ]
raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]# 設(shè)置訓(xùn)練組X_train = np.array(raw_data_X)
y_train = np.array(raw_data_y)# 將數(shù)據(jù)可視化plt.scatter(X_train[y_train==0,0],X_train[y_train==0,1], color='g', label = 'Tumor Size')
plt.scatter(X_train[y_train==1,0],X_train[y_train==1,1], color='r', label = 'Time')
plt.xlabel('Tumor Size')
plt.ylabel('Time')
plt.axis([0,10,0,5])
plt.show()

數(shù)據(jù)可視化后生成的圖片如下圖所示。其中橫軸是腫塊大小，縱軸是發(fā)現(xiàn)時(shí)間。每個(gè)病人的腫塊大小和發(fā)病時(shí)間構(gòu)成了二維平面特征中的一個(gè)點(diǎn)。對(duì)于每個(gè)點(diǎn)，我們通過(guò)label明確是惡性腫瘤（綠色）、良性腫瘤（紅色）。

那么現(xiàn)在給出一個(gè)腫瘤患者的數(shù)據(jù)（樣本點(diǎn)）x：[8.90933607318, 3.365731514]，是良性腫瘤還是惡性腫瘤

求距離

我們要做的是：求點(diǎn)x到數(shù)據(jù)集中每個(gè)點(diǎn)的距離，首先計(jì)算距離，使用歐氏距離

下面寫(xiě)代碼：

from math import sqrt
distances = [] # 用來(lái)記錄x到樣本數(shù)據(jù)集中每個(gè)點(diǎn)的距離for x_train in X_train:
 d = sqrt(np.sum((x_train - x) ** 2))
 distances.append(d)# 使用列表生成器，一行就能搞定，對(duì)于X_train中的每一個(gè)元素x_train都進(jìn)行前面的運(yùn)算，把結(jié)果生成一個(gè)列表distances = [sqrt(np.sum((x_train - x) ** 2)) for x_train in X_train]
distances
輸出：[5.611968000921151, 6.011747706769277, 7.565483059418645, 5.486753308891268, 6.647709180746875, 1.9872648870854204, 3.168477291709152, 0.8941051007010301, 0.9830754144862234, 2.7506238644678445]

在求出距離列表之后，我們要找到最小的距離，需要進(jìn)行一次排序操作。其實(shí)不是簡(jiǎn)單的排序，因?yàn)槲覀儼阎粚⒕嚯x排大小是沒(méi)有意義的，我們要知道距離最小的k個(gè)點(diǎn)是在樣本集中的位置。

這里我們使用函數(shù)：np.argsort(array) 對(duì)一個(gè)數(shù)組進(jìn)行排序，返回的是相應(yīng)的排序后結(jié)果的索引

nearest = np.argsort(distances)
nearest
輸出：array([7, 8, 5, 9, 6, 3, 0, 1, 4, 2])
結(jié)果的含義是：距離最小的點(diǎn)在distances數(shù)組中的索引是7，第二小的點(diǎn)索引是8... 近到遠(yuǎn)是哪些點(diǎn)

選k值

然后我們選擇k值，這里暫定為6，那就找出最近的6個(gè)點(diǎn)（top 6），并記錄他們的標(biāo)簽值（y）

k = 6topK_y = [y_train[i] for i in nearest[:k]]
topK_y
輸出：[1, 1, 1, 1, 1, 0]

決策規(guī)則

下面進(jìn)入投票環(huán)節(jié)。找到與測(cè)試樣本點(diǎn)最近的6個(gè)訓(xùn)練樣本點(diǎn)的標(biāo)簽y是什么。可以查不同類(lèi)別的點(diǎn)有多少個(gè)。

將數(shù)組中的元素和元素出現(xiàn)的頻次進(jìn)行統(tǒng)計(jì)

from collections import Counter
votes = Counter(topK_y)
votes
輸出：一個(gè)字典，原數(shù)組中值為0的個(gè)數(shù)為1，值為1的個(gè)數(shù)有為5Counter({0:1, 1:5})
# Counter.most_common(n) 找出票數(shù)最多的n個(gè)元素，返回的是一個(gè)列表，列表中的每個(gè)元素是一個(gè)元組，元組中第一個(gè)元素是對(duì)應(yīng)的元素是誰(shuí)，第二個(gè)元素是頻次votes.most_common(1)
輸出：[(1,5)]
predict_y = votes.most_common(1)[0][0]
predict_y
輸出：1

得到預(yù)測(cè)的y值是1

自實(shí)現(xiàn)完整工程代碼

我們已經(jīng)在jupyter notebook中寫(xiě)好了kNN算法，下面我們?cè)谕獠窟M(jìn)行封裝。

相關(guān)代碼可以在 https://github.com/japsonzbz/ML_Algorithms 中看到

import numpy as npimport math as sqrtfrom collections import Counterclass kNNClassifier:
 def __init__(self, k):
 """初始化分類(lèi)器"""
 assert k >= 1, "k must be valid"
 self.k = k
 self._X_train = None
 self._y_train = None
 def fit(self, X_train, y_train):
 """根據(jù)訓(xùn)練數(shù)據(jù)集X_train和y_train訓(xùn)練kNN分類(lèi)器"""
 assert X_train.shape[0] == y_train.shape[0], \ "the size of X_train must be equal to the size of y_train"
 assert self.k <= X_train.shape[0], \ "the size of X_train must be at least k"
 self._X_train = X_train
 self._y_train = y_train return self def predict(self,X_predict):
 """給定待預(yù)測(cè)數(shù)據(jù)集X_predict，返回表示X_predict結(jié)果的向量"""
 assert self._X_train is not None and self._y_train is not None, \ "must fit before predict!"
 assert X_predict.shape[1] == self._X_train.shape[1], \ "the feature number of X_predict must be equal to X_train"
 y_predict = [self._predict(x) for x in X_predict] return np.array(y_predict) def _predict(self, x):
 distances = [sqrt(np.sum((x_train - x) ** 2)) for x_train in self._X_train]
 nearest = np.argsort(distances)
 topK_y = [self._y_train[i] for i in nearest]
 votes = Counter(topK_y) return votes.most_common(1)[0][0] def __repr__(self):
 return "kNN(k=%d)" % self.k

當(dāng)我們寫(xiě)完定義好自己的kNN代碼之后，可以在jupyter notebook中使用魔法命令進(jìn)行調(diào)用：

%run myAlgorithm/kNN.py
knn_clf = kNNClassifier(k=6)
knn_clf.fit(X_train, y_train)
X_predict = x.reshape(1,-1)
y_predict = knn_clf.predict(X_predict)
y_predict
輸出：array([1])

現(xiàn)在我們就完成了一個(gè)sklearn風(fēng)格的kNN算法，但是實(shí)際上，sklearn封裝的算法比我們實(shí)現(xiàn)的要復(fù)雜得多。

sklearn中的kNN

代碼

對(duì)于機(jī)器學(xué)習(xí)來(lái)說(shuō)，其流程是：訓(xùn)練數(shù)據(jù)集 -> 機(jī)器學(xué)習(xí)算法 -fit-> 模型 輸入樣例 -> 模型 -predict-> 輸出結(jié)果

我們之前說(shuō)過(guò)，kNN算法沒(méi)有模型，模型其實(shí)就是訓(xùn)練數(shù)據(jù)集，predict的過(guò)程就是求k近鄰的過(guò)程。

我們使用sklearn中已經(jīng)封裝好的kNN庫(kù)。你可以看到使用有多么簡(jiǎn)單。

from sklearn.neighbors import KNeighborsClassifier# 創(chuàng)建kNN_classifier實(shí)例kNN_classifier = KNeighborsClassifier(n_neighbors=6)# kNN_classifier做一遍fit(擬合)的過(guò)程，沒(méi)有返回值，模型就存儲(chǔ)在kNN_classifier實(shí)例中kNN_classifier.fit(X_train, y_train)# kNN進(jìn)行預(yù)測(cè)predict，需要傳入一個(gè)矩陣，而不能是一個(gè)數(shù)組。reshape()成一個(gè)二維數(shù)組，第一個(gè)參數(shù)是1表示只有一個(gè)數(shù)據(jù)，第二個(gè)參數(shù)-1，numpy自動(dòng)決定第二維度有多少y_predict = kNN_classifier.predict(x.reshape(1,-1))
y_predict
輸出：array([1])

在kNN_classifier.fit(X_train, y_train)這行代碼后其實(shí)會(huì)有一個(gè)輸出：

KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
 metric_params=None, n_jobs=1, n_neighbors=6, p=2,
 weights='uniform')

參數(shù)

class
sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2, metric=’minkowski’, metric_params=None, n_jobs=None, **kwargs)

我們研究一下參數(shù)：

• n_neighbors: int, 可選參數(shù)(默認(rèn)為 5)。用于kneighbors查詢(xún)的默認(rèn)鄰居的數(shù)量
• weights（權(quán)重）: str or callable(自定義類(lèi)型), 可選參數(shù)(默認(rèn)為 ‘uniform’)。用于預(yù)測(cè)的權(quán)重參數(shù)，可選參數(shù)如下：
• uniform : 統(tǒng)一的權(quán)重. 在每一個(gè)鄰居區(qū)域里的點(diǎn)的權(quán)重都是一樣的。
• distance : 權(quán)重點(diǎn)等于他們距離的倒數(shù)。
• 使用此函數(shù)，更近的鄰居對(duì)于所預(yù)測(cè)的點(diǎn)的影響更大。
• [callable] : 一個(gè)用戶(hù)自定義的方法，此方法接收一個(gè)距離的數(shù)組，然后返回一個(gè)相同形狀并且包含權(quán)重的數(shù)組。
• algorithm（算法）: {‘a(chǎn)uto’, ‘ball_tree’, ‘kd_tree’, ‘brute’}, 可選參數(shù)（默認(rèn)為 ‘a(chǎn)uto’）。計(jì)算最近鄰居用的算法：
• ball_tree 使用算法BallTree
• kd_tree 使用算法KDTree
• brute 使用暴力搜索
• auto 會(huì)基于傳入fit方法的內(nèi)容，選擇最合適的算法。
• 注意 : 如果傳入fit方法的輸入是稀疏的，將會(huì)重載參數(shù)設(shè)置，直接使用暴力搜索。
• leaf_size（葉子數(shù)量）: int, 可選參數(shù)(默認(rèn)為 30)。傳入BallTree或者KDTree算法的葉子數(shù)量。此參數(shù)會(huì)影響構(gòu)建、查詢(xún)BallTree或者KDTree的速度，以及存儲(chǔ)BallTree或者KDTree所需要的內(nèi)存大小。此可選參數(shù)根據(jù)是否是問(wèn)題所需選擇性使用。
• p: integer, 可選參數(shù)(默認(rèn)為 2)。用于Minkowski metric（閔可夫斯基空間）的超參數(shù)。p = 1, 相當(dāng)于使用曼哈頓距離，p = 2, 相當(dāng)于使用歐幾里得距離]，對(duì)于任何 p ，使用的是閔可夫斯基空間。
• metric（矩陣）: string or callable, 默認(rèn)為 ‘minkowski’。用于樹(shù)的距離矩陣。默認(rèn)為閔可夫斯基空間，如果和p=2一塊使用相當(dāng)于使用標(biāo)準(zhǔn)歐幾里得矩陣. 所有可用的矩陣列表請(qǐng)查詢(xún) DistanceMetric 的文檔。
• metric_params（矩陣參數(shù)）: dict, 可選參數(shù)(默認(rèn)為 None)。給矩陣方法使用的其他的關(guān)鍵詞參數(shù)。
• n_jobs: int, 可選參數(shù)(默認(rèn)為 1)。用于搜索鄰居的，可并行運(yùn)行的任務(wù)數(shù)量。如果為-1, 任務(wù)數(shù)量設(shè)置為CPU核的數(shù)量。不會(huì)影響fit

方法

對(duì)于KNeighborsClassifier的方法：

方法名含義fit(X, y)使用X作為訓(xùn)練數(shù)據(jù)，y作為目標(biāo)值（類(lèi)似于標(biāo)簽）來(lái)擬合模型。get_params([deep])獲取估值器的參數(shù)。neighbors([X, n_neighbors, return_distance])查找一個(gè)或幾個(gè)點(diǎn)的K個(gè)鄰居。kneighbors_graph([X, n_neighbors, mode])計(jì)算在X數(shù)組中每個(gè)點(diǎn)的k鄰居的（權(quán)重）圖。predict(X)給提供的數(shù)據(jù)預(yù)測(cè)對(duì)應(yīng)的標(biāo)簽。predict_proba(X)返回測(cè)試數(shù)據(jù)X的概率估值。score(X, y[, sample_weight])返回給定測(cè)試數(shù)據(jù)和標(biāo)簽的平均準(zhǔn)確值。set_params(**params)設(shè)置估值器的參數(shù)。

0xFF 總結(jié)

在本文中我們了解了第一個(gè)ML算法kNN，kNN憑借著自己樸素成熟的特點(diǎn)成為機(jī)器學(xué)習(xí)的敲門(mén)磚。

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

雖然我們自己實(shí)現(xiàn)了一個(gè)機(jī)器學(xué)習(xí)算法，但是它的效果怎樣樣？預(yù)測(cè)準(zhǔn)確率高不高？我們?cè)?a href='/map/jiqixuexi/' style='color:#000;font-size:inherit;'>機(jī)器學(xué)習(xí)過(guò)程中還有哪些需要注意的問(wèn)題呢？

且聽(tīng)下回分解。