女同學(xué)問(wèn)Taoye，KNN應(yīng)該怎么玩才能通關(guān)？？？某問(wèn)得，給這位妮子安排上！
這篇是機(jī)器學(xué)習(xí)系列文章所涉及到的第六篇文章了，前面已經(jīng)介紹過(guò)了支持向量機(jī)SVM以及決策樹(shù)算法，一個(gè)躲在小房間里認(rèn)真閱讀過(guò)的讀者應(yīng)該對(duì)他們都有了一定的認(rèn)識(shí)，算法的過(guò)程和原理也都大致了解了。
這篇文章我們來(lái)看看K-近鄰（KNN）算法，關(guān)于KNN算法，由于比較的簡(jiǎn)單，沒(méi)有SVM那么復(fù)雜的公式和過(guò)程，所以會(huì)肝一篇文章來(lái)結(jié)束。
更多機(jī)器學(xué)習(xí)系列文章，歡迎各位朋友關(guān)注微信公眾號(hào)：玩世不恭的Coder
本篇文章主要包括以下幾個(gè)部分的內(nèi)容：
- 什么是K-近鄰算法（KNN），通過(guò)一個(gè)關(guān)于電影分類(lèi)的小案例幫助大家快速認(rèn)識(shí)KNN
- 基于KNN實(shí)現(xiàn)約會(huì)網(wǎng)站的對(duì)象配對(duì)，通過(guò)KNN來(lái)找對(duì)象，豈不是美滋滋
- 基于KNN實(shí)現(xiàn)手寫(xiě)數(shù)字識(shí)別系統(tǒng)，機(jī)器學(xué)習(xí)/深度學(xué)習(xí)領(lǐng)域的Hello World
一、什么是K-近鄰算法（KNN）
簡(jiǎn)單地說(shuō)，K-近鄰算法采用測(cè)量不同特征值之間的距離方法進(jìn)行分類(lèi)。它的優(yōu)點(diǎn)是精度高、對(duì)異常值不敏感、無(wú)數(shù)據(jù)輸入假定。缺點(diǎn)是時(shí)間復(fù)雜度和空間復(fù)雜度高。主要適用于數(shù)值型和標(biāo)稱(chēng)型數(shù)據(jù)范圍。
KNN算法的工作原理如下：存在一個(gè)樣本數(shù)據(jù)集合，也稱(chēng)作訓(xùn)練樣本集，并且樣本集中每個(gè)數(shù)據(jù)都存在標(biāo)簽，即我們知道樣本集中每一個(gè)數(shù)據(jù)與所屬分類(lèi)的對(duì)應(yīng)關(guān)系。輸入沒(méi)有標(biāo)簽的新數(shù)據(jù)后，將新數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)對(duì)應(yīng)的特征進(jìn)行比較，然后算法提取樣本中特征最相似數(shù)據(jù)（最近鄰）的分類(lèi)標(biāo)簽。一般來(lái)說(shuō)，我們只選擇樣本數(shù)據(jù)集中前K個(gè)最相似的數(shù)據(jù)，這就是K-近鄰算法中K的出處，通常K是不大于20的整數(shù)。最后，選擇K個(gè)最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類(lèi)，作為新數(shù)據(jù)的最終分類(lèi)。
這是啥意思呢？？？通俗的解釋一哈吧
假如現(xiàn)在我有兩類(lèi)數(shù)據(jù)集，數(shù)據(jù)集數(shù)目是總共100個(gè)?，F(xiàn)在有一個(gè)新的數(shù)據(jù)集，我們應(yīng)該將其歸于哪一類(lèi)呢？？？
是醬紫的，首先會(huì)將這個(gè)新的數(shù)據(jù)與這100個(gè)數(shù)據(jù)分別計(jì)算“距離”（這個(gè)距離后面詳細(xì)講），然后選取前K個(gè)最小的數(shù)據(jù)，在這K個(gè)中統(tǒng)計(jì)哪類(lèi)數(shù)據(jù)樣本數(shù)最多，則將這個(gè)新的數(shù)據(jù)歸于哪一類(lèi)。
我們來(lái)嘗試一下通過(guò)KNN來(lái)對(duì)電影類(lèi)別進(jìn)行分類(lèi)吧。例子來(lái)源：《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》
有人曾經(jīng)統(tǒng)計(jì)過(guò)很多電影的打斗鏡頭和接吻鏡頭數(shù)目，以此來(lái)判別該電影是動(dòng)作片還是愛(ài)情片。（注意：該例中只存在這兩種電影類(lèi)別，不存在其他類(lèi)別，也不存在愛(ài)情動(dòng)作片）。下圖顯示的是6部電影的打斗和接吻鏡頭數(shù)。假如有一部未看過(guò)的電影，如何確定它是動(dòng)作片還是愛(ài)情片呢？？？
首先我們需要明確的是這六部電影的各個(gè)屬性特征值，也就是打斗鏡頭和接吻鏡頭的數(shù)目，具體數(shù)據(jù)如下表所示：
根據(jù)我們上述所說(shuō)的原理那樣，即使我們不知道未知電影的實(shí)際類(lèi)別，我們也可以通過(guò)某種方法計(jì)算出來(lái)。
首先，計(jì)算未知電影與其他六部電影的“距離”，該距離的計(jì)算有多種方式，它主要用來(lái)體現(xiàn)的是兩個(gè)樣本的之間的相似度。在這里，我們主要采用的是歐式距離來(lái)表示，具體如下：
當(dāng)然了，在機(jī)器學(xué)習(xí)的學(xué)習(xí)過(guò)程中，我們會(huì)與多種距離公式有邂逅的機(jī)會(huì)，至于其他“距離”，我們用到了再來(lái)提及。對(duì)此，我們對(duì)未知樣本與其他六個(gè)樣本之間分別計(jì)算歐式距離，得到的距離結(jié)果如下所示：
現(xiàn)在我們得到了樣本集中所有電影與未知電影的距離，按照距離的遞增排序，可以找到K個(gè)距離最近的電影。假設(shè)，這里我們?nèi)=5，則我們可以發(fā)現(xiàn)在這五個(gè)樣本中，有三個(gè)樣本的類(lèi)別為愛(ài)情片，有兩個(gè)類(lèi)別為動(dòng)作片，所以我們理應(yīng)將這部未知電影歸類(lèi)于愛(ài)情片。
以上內(nèi)容，就是K-近鄰算法的原理以及過(guò)程，想必讀者對(duì)KNN已經(jīng)有了一定的了解，下面我們不妨通過(guò)代碼來(lái)實(shí)現(xiàn)上述的KNN分類(lèi)過(guò)程
首先第一步當(dāng)然是準(zhǔn)備數(shù)據(jù)集了，為此我們定義一個(gè)establish_data方法，分別返回屬性特征和對(duì)應(yīng)的標(biāo)簽：
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: 用于生成樣本的屬性特征以及對(duì)應(yīng)的標(biāo)簽
Return:
x_data: 數(shù)據(jù)樣本的屬性，其中包括兩個(gè)屬性
y_label: 樣本屬性所對(duì)應(yīng)的標(biāo)簽
"""
def establish_data():
x_data = np.array([[3, 104], [2, 100], [1, 81],
[101, 10], [99, 5], [98, 2]])
y_label = np.array(["愛(ài)情片", "愛(ài)情片", "愛(ài)情片", "動(dòng)作片", "動(dòng)作片", "動(dòng)作片"])
return x_data, y_label
其次，定義knn_classification方法通過(guò)KNN原理和思想來(lái)實(shí)現(xiàn)分類(lèi)，這里簡(jiǎn)單介紹幾個(gè)點(diǎn)：
-
np.sqrt(np.power((np.tile(in_data, [data_number, 1]) - x_data), 2).sum(axis=1))，該代碼就是根據(jù)公式來(lái)計(jì)算與各自樣本之間的距離，在操作過(guò)程中要熟練Numpy的使用，具體可參考之前Taoye整理出的一篇文章：print( "Hello，NumPy！" ) -
distance.argsort()，該代碼中的argsort()返回時(shí)數(shù)組從小到大的索引，比如在這里返回的結(jié)果是[1, 2, 0, 3, 4, 5]，意思是最小值的索引為1，其次索引為2。這個(gè)方法要尤其注意。 -
class_count.get(label, 0)，字典的get方法傳入第二個(gè)參數(shù)代表的是，假如字典沒(méi)有這個(gè)key，那就默認(rèn)其value為0 -
sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)，前面我們不是已經(jīng)獲得了結(jié)果字典么，但是我們最終需要的是數(shù)量的最多的，所以還需要通過(guò)sorted對(duì)其進(jìn)行排序
具體代碼如下：
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: KNN的核心分類(lèi)方法
Parameters:
in_data: 目標(biāo)分類(lèi)樣本
x_data: 已知標(biāo)簽的樣本屬性特征
y_label：樣本標(biāo)簽
k：K-近鄰當(dāng)中的k，也就是自定義的超參數(shù)
Return:
result: 最終的分類(lèi)結(jié)果
"""
def knn_classification(in_data, x_data, y_label, k):
data_number, _ = x_data.shape
distance = np.sqrt(np.power((np.tile(in_data, [data_number, 1]) - x_data), 2).sum(axis=1))
print("計(jì)算出的距離為：", distance)
distance = distance.argsort() # 返回的是[1, 2, 0, 3, 4, 5]，意思是最小的在索引為1，其次索引為2
class_count = dict()
for index in range(k):
label = y_label[distance[index]]
class_count[label] = class_count.get(label, 0) + 1
sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
print("分類(lèi)結(jié)果為：%s, 該類(lèi)型數(shù)量為：%d，其中k=%d" % (sorted_class_count[0][0], sorted_class_count[0][1], k))
return sorted_class_count[0][0]
代碼運(yùn)行結(jié)果如下所示：
程序運(yùn)行結(jié)果與我們手動(dòng)推導(dǎo)KNN的原理結(jié)果如出一轍，完美，哈哈哈！??！
完整代碼：
import numpy as np
import operator
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: 用于生成樣本的屬性特征以及對(duì)應(yīng)的標(biāo)簽
Return:
x_data: 數(shù)據(jù)樣本的屬性，其中包括兩個(gè)屬性
y_label: 樣本屬性所對(duì)應(yīng)的標(biāo)簽
"""
def establish_data():
x_data = np.array([[3, 104], [2, 100], [1, 81],
[101, 10], [99, 5], [98, 2]])
y_label = np.array(["愛(ài)情片", "愛(ài)情片", "愛(ài)情片", "動(dòng)作片", "動(dòng)作片", "動(dòng)作片"])
return x_data, y_label
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: KNN的核心分類(lèi)方法
Parameters:
in_data: 目標(biāo)分類(lèi)樣本
x_data: 已知標(biāo)簽的樣本屬性特征
y_label：樣本標(biāo)簽
k：K-近鄰當(dāng)中的k，也就是自定義的超參數(shù)
Return:
result: 最終的分類(lèi)結(jié)果
"""
def knn_classification(in_data, x_data, y_label, k):
data_number, _ = x_data.shape
distance = np.sqrt(np.power((np.tile(in_data, [data_number, 1]) - x_data), 2).sum(axis=1))
print("計(jì)算出的距離為：", distance)
distance = distance.argsort() # 返回的是[1, 2, 0, 3, 4, 5]，意思是最小的在索引為1，其次索引為2
class_count = dict()
for index in range(k):
label = y_label[distance[index]]
class_count[label] = class_count.get(label, 0) + 1
sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
print("分類(lèi)結(jié)果為：%s, 該類(lèi)型數(shù)量為：%d，其中k=%d" % (sorted_class_count[0][0], sorted_class_count[0][1], k))
return sorted_class_count[0][0]
if __name__ == "__main__":
x_data, y_label = establish_data()
print("分類(lèi)結(jié)果為：", knn_classification(np.array([18, 90]), x_data, y_label, 5))
二、基于KNN實(shí)現(xiàn)約會(huì)網(wǎng)站的對(duì)象配對(duì)
上面我們已經(jīng)通過(guò)KNN實(shí)現(xiàn)了一個(gè)小小的案例，接下來(lái)看看如何對(duì)約會(huì)網(wǎng)站實(shí)現(xiàn)對(duì)象配對(duì)的功能。
參考資料：《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》
海倫一直使用在線約會(huì)網(wǎng)站尋找適合自己的約會(huì)對(duì)象，盡管約會(huì)網(wǎng)站會(huì)推薦不同的人選，但她并不是喜歡每一個(gè)人。經(jīng)過(guò)一番總結(jié)。他發(fā)現(xiàn)曾交往過(guò)三種類(lèi)型的人：
- 不喜歡的人
- 一般般、馬馬虎虎、還行吧，這個(gè)人
- 哇撒，這個(gè)對(duì)象太帥了，我一定要約出來(lái)
海倫為了邀約比較滿(mǎn)意的對(duì)象，也是煞費(fèi)苦心啊。她收集數(shù)據(jù)已經(jīng)有了一段時(shí)間，她把這些數(shù)據(jù)存放在文本文件 datingTestSet2.txt中，每個(gè)樣本數(shù)據(jù)占據(jù)一行，總共有1000行。海倫收集的樣本主要包含以下3中特征：
- 每年獲得的飛行常客里程數(shù)
- 玩視頻游戲所耗時(shí)間百分比
- 每周消費(fèi)的冰淇淋公升數(shù)
部分?jǐn)?shù)據(jù)如下圖所示：
搞不懂，真的搞不懂。從以上三個(gè)海倫判別對(duì)象的屬性來(lái)看，海倫比較看重對(duì)象的飛行里程、游戲時(shí)間、冰淇淋？？？
換句話說(shuō)，海倫可能不是個(gè)花癡，而是個(gè)吃貨。
不管了，不管了，既然數(shù)據(jù)集給出的是這個(gè)，那就用這個(gè)數(shù)據(jù)集吧。
老規(guī)矩，首先需要準(zhǔn)備數(shù)據(jù)集。
我們定義一個(gè)establish_data方法來(lái)從txt文件中讀取數(shù)據(jù)并通過(guò)numpy進(jìn)行返回，方法的代碼如下：
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: 用于生成樣本的屬性特征以及對(duì)應(yīng)的標(biāo)簽
Parameters:
file_name: 樣本數(shù)據(jù)所在的文件名稱(chēng)
Return:
x_data：屬性特征
y_label：標(biāo)簽
"""
def establish_data(file_name):
f = open(file_name)
line_datas = f.readlines(); data_number = len(line_datas)
x_data, y_label = list(), list()
for line_data in line_datas:
line_data_list = line_data.split("\t")
x_data.append(line_data_list[:-1])
y_label.append(line_data_list[-1].strip())
return np.array(x_data, dtype = np.float32), np.array(y_label, dtype = np.float32)
上述方法中的代碼還是挺簡(jiǎn)單的，主要是從文件中讀取數(shù)據(jù)，然后將數(shù)據(jù)保存至ndarray中并返回，運(yùn)行的結(jié)果數(shù)據(jù)如下所示：
現(xiàn)在已經(jīng)從文本文件中導(dǎo)入了數(shù)據(jù)，并將其格式轉(zhuǎn)化為我們想要的格式，接著我們需要了解數(shù)據(jù)表達(dá)的真實(shí)含義。當(dāng)然我們可以直接瀏覽文本文件，但是這種方法不是特別的友好，我們不妨對(duì)上述數(shù)據(jù)進(jìn)行一定的可視化，以便更好的觀察數(shù)據(jù)屬性特征與結(jié)果之間的關(guān)系。
上述數(shù)據(jù)可視化代碼如下：
from matplotlib import pyplot as plt
from matplotlib.font_manager import FontProperties
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: 數(shù)據(jù)可視化
"""
def show_result(x_data, y_label, axis, scatter_index):
plt.subplot(2, 2, scatter_index)
plt.scatter(x_data[:, axis[0]], x_data[:, axis[1]], c = y_label)
font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)
label_list = ["每年獲得的飛行常客里程數(shù)", "玩視頻游戲所耗時(shí)間百分比", "每周所消耗的冰淇淋公升數(shù)"]
plt.xlabel(label_list[axis[0]], FontProperties = font); plt.ylabel(label_list[axis[1]], FontProperties = font)
if __name__ == "__main__":
x_data, y_label = establish_data("./datingTestSet2.txt")
show_result(x_data, y_label, [0, 1], 1)
show_result(x_data, y_label, [0, 2], 2)
show_result(x_data, y_label, [1, 2], 3)
plt.show()
可視化結(jié)果如下所示：
上述是三個(gè)屬性特征兩兩配對(duì)的散點(diǎn)圖，其中紫色代表不喜歡，綠色代表一般般，而黃色代表超級(jí)喜歡。從可視化的結(jié)果來(lái)看，我們大致可以做出如下推論：
- 海倫比較喜歡有生活質(zhì)量不錯(cuò)的對(duì)象，但是也不能常年在外飛行，畢竟對(duì)象的身體還是比較看重的嘛
- 海倫還比較喜歡玩游戲時(shí)間占比相對(duì)比較多的對(duì)象，游戲時(shí)間長(zhǎng) -> 對(duì)象可能是個(gè)王者 -> 可以帶帶海倫這個(gè)青銅，這不美滋滋嘛，從這可以看到海倫可能也是的個(gè)游戲癡狂者，但奈何游戲技術(shù)不咋地，所以希望找個(gè)能帶她飛的對(duì)象。
- 至于冰淇淋，這個(gè)屬性特征嘛，感覺(jué)海倫對(duì)這個(gè)沒(méi)有特別高的要求，只要每天有的吃就行。
從歐氏距離的公式來(lái)看，屬性特征中數(shù)字差值最大的屬性對(duì)計(jì)算結(jié)果的影響會(huì)比較大，也就是說(shuō)，每年獲取的飛行?？屠锍虜?shù)對(duì)于計(jì)算結(jié)果的影響將遠(yuǎn)遠(yuǎn)大于其他兩個(gè)屬性特征對(duì)結(jié)果的影響，但對(duì)于海倫來(lái)講，這三個(gè)的屬性特征沒(méi)有什么大小之分，因此我們需要對(duì)數(shù)據(jù)進(jìn)行一個(gè)歸一化處理，盡可能減小屬性特征對(duì)分類(lèi)結(jié)果的影響差距。我們通常采用的是數(shù)值歸一化，將數(shù)值區(qū)間轉(zhuǎn)換到0-1或-1-1之間，我們不妨通過(guò)以下公式來(lái)進(jìn)行歸一化處理：
對(duì)此，我們定義一個(gè)normaliza_data方法來(lái)實(shí)現(xiàn)歸一化功能：
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: 數(shù)據(jù)歸一化
"""
def normalize_data(x_data, y_data):
data_number, _ = x_data.shape
min_data, max_data = np.tile(x_data.min(axis = 0), [data_number, 1]), np.tile(x_data.max(axis = 0), [data_number, 1])
new_x_data = (x_data - min_data) / (max_data - min_data)
return new_x_data, y_label
歸一化結(jié)果如下所示：
一切準(zhǔn)備就緒，接下來(lái)我們來(lái)看看knn的實(shí)際分類(lèi)結(jié)果，定義一個(gè)calc_error_info方法，用來(lái)對(duì)數(shù)據(jù)進(jìn)行預(yù)測(cè)并輸出相關(guān)錯(cuò)誤信息：
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: 對(duì)數(shù)據(jù)進(jìn)行預(yù)測(cè)并輸出相關(guān)錯(cuò)誤信息
"""
def calc_error_info(x_data, y_data, info_text):
error_count = 0
for index in range(x_data.shape[0]):
predict_result = knn_classification(x_data[index], x_data, y_label, 20)
if (int(predict_result) != y_label[index]): error_count += 1
print("%s預(yù)測(cè)錯(cuò)誤的個(gè)數(shù)為：%d，錯(cuò)誤率為：%f" % (info_text, error_count, error_count / 1000))
運(yùn)行結(jié)果如下所示可，可見(jiàn)數(shù)據(jù)的歸一化體現(xiàn)出的效果還是不錯(cuò)的：
完整代碼：
import numpy as np
import operator
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: 用于生成樣本的屬性特征以及對(duì)應(yīng)的標(biāo)簽
Parameters:
file_name: 樣本數(shù)據(jù)所在的文件名稱(chēng)
Return:
x_data：屬性特征
y_label：標(biāo)簽
"""
def establish_data(file_name):
f = open(file_name)
line_datas = f.readlines(); data_number = len(line_datas)
x_data, y_label = list(), list()
for line_data in line_datas:
line_data_list = line_data.split("\t")
x_data.append(line_data_list[:-1])
y_label.append(line_data_list[-1].strip())
return np.array(x_data, dtype = np.float32), np.array(y_label, dtype = np.float32)
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: KNN的核心分類(lèi)方法
Parameters:
in_data: 目標(biāo)分類(lèi)樣本
x_data: 已知標(biāo)簽的樣本屬性特征
y_label：樣本標(biāo)簽
k：K-近鄰當(dāng)中的k，也就是自定義的超參數(shù)
Return:
result: 最終的分類(lèi)結(jié)果
"""
def knn_classification(in_data, x_data, y_label, k):
data_number, _ = x_data.shape
distance = np.sqrt(np.power((np.tile(in_data, [data_number, 1]) - x_data), 2).sum(axis=1))
distance = distance.argsort()
class_count = dict()
for index in range(k):
label = y_label[distance[index]]
class_count[label] = class_count.get(label, 0) + 1
sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
return sorted_class_count[0][0]
from matplotlib import pyplot as plt
from matplotlib.font_manager import FontProperties
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: 數(shù)據(jù)可視化
"""
def show_result(x_data, y_label, axis, scatter_index):
plt.subplot(2, 2, scatter_index)
plt.scatter(x_data[:, axis[0]], x_data[:, axis[1]], c = y_label)
font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)
label_list = ["每年獲得的飛行?？屠锍虜?shù)", "玩視頻游戲所耗時(shí)間百分比", "每周所消耗的冰淇淋公升數(shù)"]
plt.xlabel(label_list[axis[0]], FontProperties = font); plt.ylabel(label_list[axis[1]], FontProperties = font)
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: 數(shù)據(jù)歸一化
"""
def normalize_data(x_data, y_data):
data_number, _ = x_data.shape
min_data, max_data = np.tile(x_data.min(axis = 0), [data_number, 1]), np.tile(x_data.max(axis = 0), [data_number, 1])
new_x_data = (x_data - min_data) / (max_data - min_data)
return new_x_data, y_label
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: 對(duì)數(shù)據(jù)進(jìn)行預(yù)測(cè)并輸出相關(guān)錯(cuò)誤信息
"""
def calc_error_info(x_data, y_data, info_text):
error_count = 0
for index in range(x_data.shape[0]):
predict_result = knn_classification(x_data[index], x_data, y_label, 20)
if (int(predict_result) != y_label[index]): error_count += 1
print("%s預(yù)測(cè)錯(cuò)誤的個(gè)數(shù)為：%d，錯(cuò)誤率為：%f" % (info_text, error_count, error_count / 1000))
if __name__ == "__main__":
x_data, y_label = establish_data("./datingTestSet2.txt")
norm_x_data, norm_y_label = normalize_data(x_data, y_label)
calc_error_info(x_data, y_label, "歸一化數(shù)據(jù)之前：")
calc_error_info(norm_x_data, norm_y_label, "歸一化數(shù)據(jù)之后：")
三、基于KNN實(shí)現(xiàn)手寫(xiě)數(shù)字識(shí)別系統(tǒng)
讀到這里，是不是可以感覺(jué)到KNN其實(shí)并沒(méi)有那么難？？？
還是挺簡(jiǎn)單的，對(duì)吧？？？
接下來(lái)，我們?cè)偻ㄟ^(guò)KNN實(shí)現(xiàn)一個(gè)手寫(xiě)數(shù)字識(shí)別系統(tǒng)。
我們都知道，在我們沒(méi)學(xué)習(xí)一門(mén)語(yǔ)言的時(shí)候，都會(huì)來(lái)一波print("Hello world!")，而在機(jī)器學(xué)習(xí)或者深度學(xué)習(xí)領(lǐng)域中，手寫(xiě)數(shù)字識(shí)別就相當(dāng)于Hello world!的存在。
在trainingDigits目錄下包含了大約2000個(gè)數(shù)字txt文本，每個(gè)例子中的內(nèi)容如下圖醬紫，每個(gè)數(shù)字0-9大約有200個(gè)樣本；testDigits目錄下包含了900個(gè)測(cè)試數(shù)據(jù)，數(shù)據(jù)如同trainingDigits下的樣本；我們使用trainingDigits中的數(shù)據(jù)作為數(shù)據(jù)訓(xùn)練分類(lèi)器，使用testDigits目錄中的數(shù)據(jù)測(cè)試分類(lèi)器的效果，兩組數(shù)據(jù)沒(méi)有重疊。
數(shù)據(jù)可來(lái)此處下載：https://pan.baidu.com/s/1o8qC6PqFGxuhRUbwUYHjQA 密碼：u4ac
老規(guī)矩，同樣的，我們需要定義一個(gè)establish_data方法來(lái)準(zhǔn)備數(shù)據(jù)，但是在此之前，我們需要對(duì)數(shù)據(jù)進(jìn)行一定處理，由于我們數(shù)字文本txt文件中的內(nèi)容是一個(gè)32x32的，而對(duì)于KNN來(lái)講，每一個(gè)樣本都應(yīng)該是一個(gè)特征向量的形式，所以我們需要將32x32的數(shù)據(jù)轉(zhuǎn)化成1x1024的向量，也就是將其拉平，對(duì)此，定義一個(gè)flatten_digit_data方法來(lái)實(shí)現(xiàn)這個(gè)功能：
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: 將數(shù)字txt文本文件內(nèi)容拉伸
Parameters:
file_name: 樣本數(shù)據(jù)所在的文件名稱(chēng)
Return:
x_data：屬性特征
y_label：標(biāo)簽
"""
def flatten_digit_data(digit_file_name):
flatten_digit = list(); f = open(digit_file_name)
for index in range(32):
for j in range(32): flatten_digit.extend(list(f.readline())[:-1])
return np.array(flatten_digit, dtype = np.int32)
接下來(lái)定義establish_data方法來(lái)整合數(shù)據(jù)，將多個(gè)數(shù)字文件轉(zhuǎn)化為一個(gè)m x 1024的矩陣，矩陣中的每個(gè)行代表一個(gè)樣本，每個(gè)樣本1024個(gè)屬性特征，總共有m個(gè)樣本，這里我們需要導(dǎo)入os模塊以方便操作文件夾，establish_data具體代碼如下：
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: 數(shù)據(jù)準(zhǔn)備方法，將所有數(shù)字文本轉(zhuǎn)換成矩陣形式
Parameters:
digit_file_name: 單個(gè)數(shù)字文本文件的名稱(chēng)
Return:
flatten_digiy：轉(zhuǎn)換成行向量之后的樣本
"""
def establish_data(folder_name):
import os
y_label = list(); file_names = os.listdir(folder_name)
x_data = np.zeros([len(file_names), 1024])
for index, file_name in enumerate(file_names):
y_label.append(file_name.split("_")[0])
x_data[index] = flatten_digit_data(folder_name + file_name)
return x_data, np.array(y_label, dtype = np.int32)
后面就是實(shí)現(xiàn)knn_classification和calc_error_info方法了，方法具體代碼內(nèi)容與前面的大體相同，只需稍作修改即可，KNN實(shí)現(xiàn)手寫(xiě)數(shù)字識(shí)別的完整代碼如下：
import numpy as np
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: 將數(shù)字txt文本文件內(nèi)容拉伸
Parameters:
digit_file_name: 單個(gè)數(shù)字文本文件的名稱(chēng)
Return:
flatten_digiy：轉(zhuǎn)換成行向量之后的樣本
"""
def flatten_digit_data(digit_file_name):
flatten_digit = list(); f = open(digit_file_name)
for index in range(32):
for j in range(32): flatten_digit.extend(list(f.readline())[:-1])
return np.array(flatten_digit, dtype = np.int32)
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: 數(shù)據(jù)準(zhǔn)備方法，將所有數(shù)字文本轉(zhuǎn)換成矩陣形式
Parameters:
digit_file_name: 單個(gè)數(shù)字文本文件的名稱(chēng)
Return:
flatten_digiy：轉(zhuǎn)換成行向量之后的樣本
"""
def establish_data(folder_name):
import os
y_label = list(); file_names = os.listdir(folder_name)
x_data = np.zeros([len(file_names), 1024])
for index, file_name in enumerate(file_names):
y_label.append(file_name.split("_")[0])
x_data[index] = flatten_digit_data(folder_name + file_name)
return x_data, np.array(y_label, dtype = np.int32)
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: KNN的核心分類(lèi)方法
Parameters:
in_data: 目標(biāo)分類(lèi)樣本
x_data: 已知標(biāo)簽的樣本屬性特征
y_label：樣本標(biāo)簽
k：K-近鄰當(dāng)中的k，也就是自定義的超參數(shù)
Return:
result: 最終的分類(lèi)結(jié)果
"""
def knn_classification(in_data, x_data, y_label, k):
data_number, _ = x_data.shape
distance = np.sqrt(np.power((np.tile(in_data, [data_number, 1]) - x_data), 2).sum(axis=1))
distance = distance.argsort()
class_count = dict()
for index in range(k):
label = y_label[distance[index]]
class_count[label] = class_count.get(label, 0) + 1
sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
return sorted_class_count[0][0]
"""
Author: Taoye
微信公眾號(hào): 玩世不恭的Coder
Explain: 對(duì)數(shù)據(jù)進(jìn)行預(yù)測(cè)并輸出相關(guān)錯(cuò)誤信息
"""
def calc_error_info(x_data, y_data, test_x_data, test_y_label, k):
error_count = 0
for index in range(test_y_label.shape[0]):
predict_result = knn_classification(test_x_data[index], x_data, y_label, k)
if (int(predict_result) != test_y_label[index]):
error_count += 1
print("KNN預(yù)測(cè)錯(cuò)誤，預(yù)測(cè)結(jié)果為：%d，真實(shí)結(jié)果為：%d" % (predict_result, test_y_label[index]))
print("預(yù)測(cè)錯(cuò)誤的個(gè)數(shù)為：%d，錯(cuò)誤率為：%f" % (error_count, error_count / test_y_label.shape[0]))
if __name__ == "__main__":
x_data, y_label = establish_data("./digits/trainingDigits/")
test_x_data, test_y_label = establish_data("./digits/testDigits/")
calc_error_info(x_data, y_label, test_x_data, test_y_label, 20)
完整代碼運(yùn)行結(jié)果如下所示：
可以看見(jiàn)，該KNN實(shí)現(xiàn)手寫(xiě)數(shù)字識(shí)別的效果還是可以的，測(cè)試數(shù)據(jù)總共有946個(gè)，其中預(yù)測(cè)錯(cuò)誤了26個(gè)，錯(cuò)誤率為2.7%，還行吧，這錯(cuò)誤率~~~ 只是時(shí)間復(fù)雜度有點(diǎn)高了
另外，該模型測(cè)試結(jié)果是在k=20的前提下的得到的，讀者可自行修改K參數(shù)的值，來(lái)進(jìn)一步觀察模型預(yù)測(cè)的錯(cuò)誤率
KNN相關(guān)的內(nèi)容就寫(xiě)到這里了，總體上來(lái)講，KNN算法還是挺簡(jiǎn)單的，沒(méi)有太多花里胡哨的東西，也沒(méi)有多么復(fù)雜的公式，認(rèn)真閱讀的讀者都能夠?qū)NN吸收到位。
手撕機(jī)器學(xué)習(xí)系列文章目前已經(jīng)更新了支持向量機(jī)SVM、決策樹(shù)、K-近鄰（KNN），但從后臺(tái)數(shù)據(jù)上來(lái)看，受眾結(jié)果不是很理想。的確，機(jī)器學(xué)習(xí)系列文章的受眾人群實(shí)屬有限，大多比較的枯燥乏味，沒(méi)有前后端開(kāi)發(fā)那么的香。
說(shuō)歸說(shuō)，鬧歸鬧。手撕機(jī)器學(xué)習(xí)系列文章，Taoye還是會(huì)繼續(xù)肝下去的，下一篇算法應(yīng)該是樸素貝葉斯了吧，敬請(qǐng)期待。
感覺(jué)一直更新機(jī)器學(xué)習(xí)系列文章有點(diǎn)對(duì)不起讀者朋友，畢竟太枯燥了。本想寫(xiě)一篇關(guān)于如何霸屏微信運(yùn)動(dòng)榜首的爬蟲(chóng)文章，感覺(jué)這個(gè)大家會(huì)更感興趣一點(diǎn)，但前幾天用Fiddler抓取數(shù)據(jù)包的時(shí)候遲遲無(wú)果（之前還是可以抓取到的），也就只好暫時(shí)擱置了。11月1號(hào)抓取到的接口還是有效的，依然是可以正常修改步數(shù)的
<img src="https://gitee.com/tianxingjian123/my-images-repository/raw/master/img/knn_12.png" width="200">
這篇文章更不更，再看吧！
舍友小弟有點(diǎn)擔(dān)心Taoye的秀發(fā)了，不過(guò)學(xué)習(xí)還是會(huì)保持的，文章還是會(huì)更新的，感謝每一位點(diǎn)進(jìn)來(lái)閱讀的朋友，
<img src="https://gitee.com/tianxingjian123/my-images-repository/raw/master/img/knn_13.png" width="300">
這篇文章就暫時(shí)寫(xiě)到這里吧，希望每一位進(jìn)來(lái)的朋友都能夠有所收獲。（雖然粉絲不多）
我是Taoye，愛(ài)專(zhuān)研，愛(ài)分享，熱衷于各種技術(shù)，學(xué)習(xí)之余喜歡下象棋、聽(tīng)音樂(lè)、聊動(dòng)漫，希望借此一畝三分地記錄自己的成長(zhǎng)過(guò)程以及生活點(diǎn)滴，也希望能結(jié)實(shí)更多志同道合的圈內(nèi)朋友，更多內(nèi)容歡迎來(lái)訪微信公主號(hào)：玩世不恭的Coder
我們下期再見(jiàn)，拜拜~~~
參考資料：
<font style="font-size:13px;opacity:0.7">[1] 《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》：Peter Harrington 人民郵電出版社</font>
<font style="font-size:13px;opacity:0.7">[2] 《統(tǒng)計(jì)學(xué)習(xí)方法》：李航 第二版 清華大學(xué)出版社</font>
推薦閱讀
《Machine Learning in Action》—— 懂的都懂，不懂的也能懂。非線性支持向量機(jī)
《Machine Learning in Action》—— hao朋友，快來(lái)玩啊，決策樹(shù)呦
《Machine Learning in Action》—— Taoye給你講講決策樹(shù)到底是支什么“鬼”
《Machine Learning in Action》—— 剖析支持向量機(jī)，優(yōu)化SMO
《Machine Learning in Action》—— 剖析支持向量機(jī)，單手狂撕線性SVM
print( "Hello，NumPy！" )
干啥啥不行，吃飯第一名
Taoye滲透到一家黑平臺(tái)總部，背后的真相細(xì)思極恐
《大話數(shù)據(jù)庫(kù)》-SQL語(yǔ)句執(zhí)行時(shí)，底層究竟做了什么小動(dòng)作？
那些年，我們玩過(guò)的Git，真香
基于Ubuntu+Python+Tensorflow+Jupyter notebook搭建深度學(xué)習(xí)環(huán)境
