《Machine Learning in Action》—— 女同學(xué)問Taoye挽绩，KNN應(yīng)該怎么玩才能通關(guān)

女同學(xué)問Taoye膛壹，KNN應(yīng)該怎么玩才能通關(guān)？唉堪？模聋？某問得，給這位妮子安排上唠亚！

這篇是機(jī)器學(xué)習(xí)系列文章所涉及到的第六篇文章了链方，前面已經(jīng)介紹過了支持向量機(jī)SVM以及決策樹算法，一個(gè)躲在小房間里認(rèn)真閱讀過的讀者應(yīng)該對他們都有了一定的認(rèn)識灶搜，算法的過程和原理也都大致了解了祟蚀。

這篇文章我們來看看K-近鄰（KNN）算法，關(guān)于KNN算法割卖，由于比較的簡單前酿，沒有SVM那么復(fù)雜的公式和過程，所以會(huì)肝一篇文章來結(jié)束鹏溯。

更多機(jī)器學(xué)習(xí)系列文章罢维，歡迎各位朋友關(guān)注微信公眾號：玩世不恭的Coder

本篇文章主要包括以下幾個(gè)部分的內(nèi)容：

什么是K-近鄰算法（KNN），通過一個(gè)關(guān)于電影分類的小案例幫助大家快速認(rèn)識KNN
基于KNN實(shí)現(xiàn)約會(huì)網(wǎng)站的對象配對丙挽，通過KNN來找對象肺孵，豈不是美滋滋
基于KNN實(shí)現(xiàn)手寫數(shù)字識別系統(tǒng)匀借，機(jī)器學(xué)習(xí)/深度學(xué)習(xí)領(lǐng)域的Hello World

一、什么是K-近鄰算法（KNN）

簡單地說平窘，K-近鄰算法采用測量不同特征值之間的距離方法進(jìn)行分類吓肋。它的優(yōu)點(diǎn)是精度高、對異常值不敏感初婆、無數(shù)據(jù)輸入假定蓬坡。缺點(diǎn)是時(shí)間復(fù)雜度和空間復(fù)雜度高。主要適用于數(shù)值型和標(biāo)稱型數(shù)據(jù)范圍磅叛。

KNN算法的工作原理如下：存在一個(gè)樣本數(shù)據(jù)集合屑咳，也稱作訓(xùn)練樣本集，并且樣本集中每個(gè)數(shù)據(jù)都存在標(biāo)簽弊琴，即我們知道樣本集中每一個(gè)數(shù)據(jù)與所屬分類的對應(yīng)關(guān)系兆龙。輸入沒有標(biāo)簽的新數(shù)據(jù)后，將新數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)對應(yīng)的特征進(jìn)行比較敲董，然后算法提取樣本中特征最相似數(shù)據(jù)（最近鄰）的分類標(biāo)簽紫皇。一般來說，我們只選擇樣本數(shù)據(jù)集中前K個(gè)最相似的數(shù)據(jù)腋寨，這就是K-近鄰算法中K的出處聪铺，通常K是不大于20的整數(shù)。最后，選擇K個(gè)最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類，作為新數(shù)據(jù)的最終分類聪姿。

這是啥意思呢辣苏？腹缩？？通俗的解釋一哈吧

假如現(xiàn)在我有兩類數(shù)據(jù)集，數(shù)據(jù)集數(shù)目是總共100個(gè)。現(xiàn)在有一個(gè)新的數(shù)據(jù)集普气，我們應(yīng)該將其歸于哪一類呢？佃延？现诀？

是醬紫的，首先會(huì)將這個(gè)新的數(shù)據(jù)與這100個(gè)數(shù)據(jù)分別計(jì)算“距離”（這個(gè)距離后面詳細(xì)講）履肃，然后選取前K個(gè)最小的數(shù)據(jù)赶盔，在這K個(gè)中統(tǒng)計(jì)哪類數(shù)據(jù)樣本數(shù)最多，則將這個(gè)新的數(shù)據(jù)歸于哪一類榆浓。

我們來嘗試一下通過KNN來對電影類別進(jìn)行分類吧。例子來源：《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》

有人曾經(jīng)統(tǒng)計(jì)過很多電影的打斗鏡頭和接吻鏡頭數(shù)目撕攒，以此來判別該電影是動(dòng)作片還是愛情片陡鹃。（注意：該例中只存在這兩種電影類別烘浦，不存在其他類別，也不存在愛情動(dòng)作片）萍鲸。下圖顯示的是6部電影的打斗和接吻鏡頭數(shù)闷叉。假如有一部未看過的電影，如何確定它是動(dòng)作片還是愛情片呢脊阴？握侧？？

image

首先我們需要明確的是這六部電影的各個(gè)屬性特征值嘿期，也就是打斗鏡頭和接吻鏡頭的數(shù)目品擎，具體數(shù)據(jù)如下表所示：

image

根據(jù)我們上述所說的原理那樣，即使我們不知道未知電影的實(shí)際類別备徐，我們也可以通過某種方法計(jì)算出來萄传。

首先，計(jì)算未知電影與其他六部電影的“距離”蜜猾，該距離的計(jì)算有多種方式秀菱，它主要用來體現(xiàn)的是兩個(gè)樣本的之間的相似度。在這里蹭睡，我們主要采用的是歐式距離來表示衍菱，具體如下：

$L(x_i,x_j) = \sqrt{\sum_{l=1}^N|x_i^{(l)}-x_j^{(l)}|^2}$

當(dāng)然了，在機(jī)器學(xué)習(xí)的學(xué)習(xí)過程中肩豁，我們會(huì)與多種距離公式有邂逅的機(jī)會(huì)脊串，至于其他“距離”，我們用到了再來提及蓖救。對此洪规，我們對未知樣本與其他六個(gè)樣本之間分別計(jì)算歐式距離，得到的距離結(jié)果如下所示：

image

現(xiàn)在我們得到了樣本集中所有電影與未知電影的距離循捺，按照距離的遞增排序斩例，可以找到K個(gè)距離最近的電影。假設(shè)从橘，這里我們?nèi)=5念赶，則我們可以發(fā)現(xiàn)在這五個(gè)樣本中，有三個(gè)樣本的類別為愛情片恰力，有兩個(gè)類別為動(dòng)作片叉谜，所以我們理應(yīng)將這部未知電影歸類于愛情片。

以上內(nèi)容踩萎，就是K-近鄰算法的原理以及過程停局，想必讀者對KNN已經(jīng)有了一定的了解，下面我們不妨通過代碼來實(shí)現(xiàn)上述的KNN分類過程

首先第一步當(dāng)然是準(zhǔn)備數(shù)據(jù)集了，為此我們定義一個(gè)establish_data方法董栽，分別返回屬性特征和對應(yīng)的標(biāo)簽：

"""
    Author: Taoye
    微信公眾號: 玩世不恭的Coder
    Explain: 用于生成樣本的屬性特征以及對應(yīng)的標(biāo)簽
    Return:
        x_data: 數(shù)據(jù)樣本的屬性码倦，其中包括兩個(gè)屬性
        y_label: 樣本屬性所對應(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(["愛情片", "愛情片", "愛情片", "動(dòng)作片", "動(dòng)作片", "動(dòng)作片"])
    return x_data, y_label

其次，定義knn_classification方法通過KNN原理和思想來實(shí)現(xiàn)分類锭碳，這里簡單介紹幾個(gè)點(diǎn)：

np.sqrt(np.power((np.tile(in_data, [data_number, 1]) - x_data), 2).sum(axis=1))袁稽，該代碼就是根據(jù)公式來計(jì)算與各自樣本之間的距離，在操作過程中要熟練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ù)代表的是鳞尔，假如字典沒有這個(gè)key，那就默認(rèn)其value為0
sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)早直，前面我們不是已經(jīng)獲得了結(jié)果字典么寥假，但是我們最終需要的是數(shù)量的最多的，所以還需要通過sorted對其進(jìn)行排序

具體代碼如下：

"""
    Author: Taoye
    微信公眾號: 玩世不恭的Coder
    Explain: KNN的核心分類方法
    Parameters:
        in_data: 目標(biāo)分類樣本
        x_data: 已知標(biāo)簽的樣本屬性特征
        y_label：樣本標(biāo)簽
        k：K-近鄰當(dāng)中的k霞扬，也就是自定義的超參數(shù)
    Return:
        result: 最終的分類結(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("分類結(jié)果為：%s, 該類型數(shù)量為：%d喻圃，其中k=%d" % (sorted_class_count[0][0], sorted_class_count[0][1], k))
    return sorted_class_count[0][0]

代碼運(yùn)行結(jié)果如下所示：

image

程序運(yùn)行結(jié)果與我們手動(dòng)推導(dǎo)KNN的原理結(jié)果如出一轍萤彩，完美，哈哈哈８摹Ｈ阜觥！

完整代碼：

import numpy as np
import operator

"""
    Author: Taoye
    微信公眾號: 玩世不恭的Coder
    Explain: 用于生成樣本的屬性特征以及對應(yīng)的標(biāo)簽
    Return:
        x_data: 數(shù)據(jù)樣本的屬性肆汹，其中包括兩個(gè)屬性
        y_label: 樣本屬性所對應(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(["愛情片", "愛情片", "愛情片", "動(dòng)作片", "動(dòng)作片", "動(dòng)作片"])
    return x_data, y_label

"""
    Author: Taoye
    微信公眾號: 玩世不恭的Coder
    Explain: KNN的核心分類方法
    Parameters:
        in_data: 目標(biāo)分類樣本
        x_data: 已知標(biāo)簽的樣本屬性特征
        y_label：樣本標(biāo)簽
        k：K-近鄰當(dāng)中的k愚墓，也就是自定義的超參數(shù)
    Return:
        result: 最終的分類結(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("分類結(jié)果為：%s, 該類型數(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("分類結(jié)果為：", knn_classification(np.array([18, 90]), x_data, y_label, 5))

二、基于KNN實(shí)現(xiàn)約會(huì)網(wǎng)站的對象配對

上面我們已經(jīng)通過KNN實(shí)現(xiàn)了一個(gè)小小的案例岗照，接下來看看如何對約會(huì)網(wǎng)站實(shí)現(xiàn)對象配對的功能村象。

參考資料：《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》

海倫一直使用在線約會(huì)網(wǎng)站尋找適合自己的約會(huì)對象笆环，盡管約會(huì)網(wǎng)站會(huì)推薦不同的人選，但她并不是喜歡每一個(gè)人煞肾。經(jīng)過一番總結(jié)咧织。他發(fā)現(xiàn)曾交往過三種類型的人：

不喜歡的人
一般般、馬馬虎虎籍救、還行吧，這個(gè)人
哇撒渠抹，這個(gè)對象太帥了蝙昙，我一定要約出來

海倫為了邀約比較滿意的對象，也是煞費(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ù)如下圖所示：

image

搞不懂广鳍，真的搞不懂荆几。從以上三個(gè)海倫判別對象的屬性來看，海倫比較看重對象的飛行里程赊时、游戲時(shí)間吨铸、冰淇淋？祖秒？诞吱？

換句話說，海倫可能不是個(gè)花癡竭缝，而是個(gè)吃貨房维。

不管了，不管了抬纸，既然數(shù)據(jù)集給出的是這個(gè)咙俩，那就用這個(gè)數(shù)據(jù)集吧。

老規(guī)矩松却，首先需要準(zhǔn)備數(shù)據(jù)集暴浦。

我們定義一個(gè)establish_data方法來從txt文件中讀取數(shù)據(jù)并通過numpy進(jìn)行返回，方法的代碼如下：

"""
    Author: Taoye
    微信公眾號: 玩世不恭的Coder
    Explain: 用于生成樣本的屬性特征以及對應(yīng)的標(biāo)簽
    Parameters:
        file_name: 樣本數(shù)據(jù)所在的文件名稱
    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)

上述方法中的代碼還是挺簡單的晓锻，主要是從文件中讀取數(shù)據(jù)歌焦，然后將數(shù)據(jù)保存至ndarray中并返回，運(yùn)行的結(jié)果數(shù)據(jù)如下所示：

image

現(xiàn)在已經(jīng)從文本文件中導(dǎo)入了數(shù)據(jù)砚哆，并將其格式轉(zhuǎn)化為我們想要的格式独撇，接著我們需要了解數(shù)據(jù)表達(dá)的真實(shí)含義。當(dāng)然我們可以直接瀏覽文本文件，但是這種方法不是特別的友好纷铣，我們不妨對上述數(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
    微信公眾號: 玩世不恭的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é)果如下所示：

image

上述是三個(gè)屬性特征兩兩配對的散點(diǎn)圖以躯，其中紫色代表不喜歡，綠色代表一般般啄踊，而黃色代表超級喜歡忧设。從可視化的結(jié)果來看，我們大致可以做出如下推論：

海倫比較喜歡有生活質(zhì)量不錯(cuò)的對象颠通，但是也不能常年在外飛行址晕，畢竟對象的身體還是比較看重的嘛
海倫還比較喜歡玩游戲時(shí)間占比相對比較多的對象，游戲時(shí)間長 -> 對象可能是個(gè)王者 -> 可以帶帶海倫這個(gè)青銅顿锰，這不美滋滋嘛谨垃，從這可以看到海倫可能也是的個(gè)游戲癡狂者，但奈何游戲技術(shù)不咋地硼控，所以希望找個(gè)能帶她飛的對象刘陶。
至于冰淇淋，這個(gè)屬性特征嘛淀歇，感覺海倫對這個(gè)沒有特別高的要求易核，只要每天有的吃就行。

從歐氏距離的公式來看浪默，屬性特征中數(shù)字差值最大的屬性對計(jì)算結(jié)果的影響會(huì)比較大牡直，也就是說，每年獲取的飛行衬删觯客里程數(shù)對于計(jì)算結(jié)果的影響將遠(yuǎn)遠(yuǎn)大于其他兩個(gè)屬性特征對結(jié)果的影響碰逸，但對于海倫來講，這三個(gè)的屬性特征沒有什么大小之分阔加，因此我們需要對數(shù)據(jù)進(jìn)行一個(gè)歸一化處理饵史，盡可能減小屬性特征對分類結(jié)果的影響差距。我們通常采用的是數(shù)值歸一化胜榔，將數(shù)值區(qū)間轉(zhuǎn)換到0-1或-1-1之間胳喷，我們不妨通過以下公式來進(jìn)行歸一化處理：

$new\_value = \frac{old\_value-min\_value}{max\_value}$

對此，我們定義一個(gè)normaliza_data方法來實(shí)現(xiàn)歸一化功能：

"""
    Author: Taoye
    微信公眾號: 玩世不恭的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é)果如下所示：

image

一切準(zhǔn)備就緒夭织，接下來我們來看看knn的實(shí)際分類結(jié)果吭露，定義一個(gè)calc_error_info方法，用來對數(shù)據(jù)進(jìn)行預(yù)測并輸出相關(guān)錯(cuò)誤信息：

"""
    Author: Taoye
    微信公眾號: 玩世不恭的Coder
    Explain: 對數(shù)據(jù)進(jìn)行預(yù)測并輸出相關(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ù)測錯(cuò)誤的個(gè)數(shù)為：%d尊惰，錯(cuò)誤率為：%f" % (info_text, error_count, error_count / 1000))

運(yùn)行結(jié)果如下所示可讲竿，可見數(shù)據(jù)的歸一化體現(xiàn)出的效果還是不錯(cuò)的：

image

完整代碼：

import numpy as np
import operator

"""
    Author: Taoye
    微信公眾號: 玩世不恭的Coder
    Explain: 用于生成樣本的屬性特征以及對應(yīng)的標(biāo)簽
    Parameters:
        file_name: 樣本數(shù)據(jù)所在的文件名稱
    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
    微信公眾號: 玩世不恭的Coder
    Explain: KNN的核心分類方法
    Parameters:
        in_data: 目標(biāo)分類樣本
        x_data: 已知標(biāo)簽的樣本屬性特征
        y_label：樣本標(biāo)簽
        k：K-近鄰當(dāng)中的k泥兰，也就是自定義的超參數(shù)
    Return:
        result: 最終的分類結(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
    微信公眾號: 玩世不恭的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
    微信公眾號: 玩世不恭的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
    微信公眾號: 玩世不恭的Coder
    Explain: 對數(shù)據(jù)進(jìn)行預(yù)測并輸出相關(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ù)測錯(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)手寫數(shù)字識別系統(tǒng)

讀到這里，是不是可以感覺到KNN其實(shí)并沒有那么難迈嘹？削彬？？

還是挺簡單的秀仲，對吧吃警？？啄育？

接下來，我們再通過KNN實(shí)現(xiàn)一個(gè)手寫數(shù)字識別系統(tǒng)拌消。

我們都知道挑豌，在我們沒學(xué)習(xí)一門語言的時(shí)候，都會(huì)來一波print("Hello world!")墩崩，而在機(jī)器學(xué)習(xí)或者深度學(xué)習(xí)領(lǐng)域中氓英，手寫數(shù)字識別就相當(dāng)于Hello world!的存在。

在trainingDigits目錄下包含了大約2000個(gè)數(shù)字txt文本鹦筹，每個(gè)例子中的內(nèi)容如下圖醬紫铝阐，每個(gè)數(shù)字0-9大約有200個(gè)樣本；testDigits目錄下包含了900個(gè)測試數(shù)據(jù)铐拐，數(shù)據(jù)如同trainingDigits下的樣本徘键；我們使用trainingDigits中的數(shù)據(jù)作為數(shù)據(jù)訓(xùn)練分類器，使用testDigits目錄中的數(shù)據(jù)測試分類器的效果遍蟋，兩組數(shù)據(jù)沒有重疊吹害。

數(shù)據(jù)可來此處下載：https://pan.baidu.com/s/1o8qC6PqFGxuhRUbwUYHjQA 密碼：u4ac

image

老規(guī)矩，同樣的虚青，我們需要定義一個(gè)establish_data方法來準(zhǔn)備數(shù)據(jù)它呀，但是在此之前，我們需要對數(shù)據(jù)進(jìn)行一定處理棒厘，由于我們數(shù)字文本txt文件中的內(nèi)容是一個(gè)32x32的纵穿，而對于KNN來講，每一個(gè)樣本都應(yīng)該是一個(gè)特征向量的形式奢人，所以我們需要將32x32的數(shù)據(jù)轉(zhuǎn)化成1x1024的向量谓媒，也就是將其拉平，對此达传，定義一個(gè)flatten_digit_data方法來實(shí)現(xiàn)這個(gè)功能：

"""
    Author: Taoye
    微信公眾號: 玩世不恭的Coder
    Explain: 將數(shù)字txt文本文件內(nèi)容拉伸
    Parameters:
        file_name: 樣本數(shù)據(jù)所在的文件名稱
    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)

接下來定義establish_data方法來整合數(shù)據(jù)篙耗，將多個(gè)數(shù)字文件轉(zhuǎn)化為一個(gè)m x 1024的矩陣迫筑，矩陣中的每個(gè)行代表一個(gè)樣本，每個(gè)樣本1024個(gè)屬性特征宗弯，總共有m個(gè)樣本脯燃，這里我們需要導(dǎo)入os模塊以方便操作文件夾，establish_data具體代碼如下：

"""
    Author: Taoye
    微信公眾號: 玩世不恭的Coder
    Explain: 數(shù)據(jù)準(zhǔn)備方法蒙保，將所有數(shù)字文本轉(zhuǎn)換成矩陣形式
    Parameters:
        digit_file_name: 單個(gè)數(shù)字文本文件的名稱
    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)手寫數(shù)字識別的完整代碼如下：

import numpy as np

"""
    Author: Taoye
    微信公眾號: 玩世不恭的Coder
    Explain: 將數(shù)字txt文本文件內(nèi)容拉伸
    Parameters:
        digit_file_name: 單個(gè)數(shù)字文本文件的名稱
    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
    微信公眾號: 玩世不恭的Coder
    Explain: 數(shù)據(jù)準(zhǔn)備方法逝嚎，將所有數(shù)字文本轉(zhuǎn)換成矩陣形式
    Parameters:
        digit_file_name: 單個(gè)數(shù)字文本文件的名稱
    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
    微信公眾號: 玩世不恭的Coder
    Explain: KNN的核心分類方法
    Parameters:
        in_data: 目標(biāo)分類樣本
        x_data: 已知標(biāo)簽的樣本屬性特征
        y_label：樣本標(biāo)簽
        k：K-近鄰當(dāng)中的k，也就是自定義的超參數(shù)
    Return:
        result: 最終的分類結(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
    微信公眾號: 玩世不恭的Coder
    Explain: 對數(shù)據(jù)進(jìn)行預(yù)測并輸出相關(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ù)測錯(cuò)誤详恼，預(yù)測結(jié)果為：%d补君，真實(shí)結(jié)果為：%d" % (predict_result, test_y_label[index]))
    print("預(yù)測錯(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é)果如下所示：

image

可以看見昧互，該KNN實(shí)現(xiàn)手寫數(shù)字識別的效果還是可以的挽铁，測試數(shù)據(jù)總共有946個(gè)，其中預(yù)測錯(cuò)誤了26個(gè)敞掘，錯(cuò)誤率為2.7%叽掘，還行吧，這錯(cuò)誤率~~~ 只是時(shí)間復(fù)雜度有點(diǎn)高了

另外玖雁，該模型測試結(jié)果是在k=20的前提下的得到的更扁，讀者可自行修改K參數(shù)的值，來進(jìn)一步觀察模型預(yù)測的錯(cuò)誤率

KNN相關(guān)的內(nèi)容就寫到這里了赫冬，總體上來講浓镜，KNN算法還是挺簡單的，沒有太多花里胡哨的東西面殖，也沒有多么復(fù)雜的公式竖哩，認(rèn)真閱讀的讀者都能夠?qū)NN吸收到位。

手撕機(jī)器學(xué)習(xí)系列文章目前已經(jīng)更新了支持向量機(jī)SVM脊僚、決策樹相叁、K-近鄰（KNN），但從后臺數(shù)據(jù)上來看辽幌，受眾結(jié)果不是很理想增淹。的確，機(jī)器學(xué)習(xí)系列文章的受眾人群實(shí)屬有限乌企，大多比較的枯燥乏味虑润，沒有前后端開發(fā)那么的香。

說歸說加酵，鬧歸鬧拳喻。手撕機(jī)器學(xué)習(xí)系列文章哭当，Taoye還是會(huì)繼續(xù)肝下去的，下一篇算法應(yīng)該是樸素貝葉斯了吧冗澈，敬請期待钦勘。

感覺一直更新機(jī)器學(xué)習(xí)系列文章有點(diǎn)對不起讀者朋友，畢竟太枯燥了亚亲。本想寫一篇關(guān)于如何霸屏微信運(yùn)動(dòng)榜首的爬蟲文章彻采，感覺這個(gè)大家會(huì)更感興趣一點(diǎn)，但前幾天用Fiddler抓取數(shù)據(jù)包的時(shí)候遲遲無果（之前還是可以抓取到的）捌归，也就只好暫時(shí)擱置了肛响。11月1號抓取到的接口還是有效的，依然是可以正常修改步數(shù)的

這篇文章更不更惜索，再看吧特笋！

舍友小弟有點(diǎn)擔(dān)心Taoye的秀發(fā)了，不過學(xué)習(xí)還是會(huì)保持的巾兆，文章還是會(huì)更新的雹有，感謝每一位點(diǎn)進(jìn)來閱讀的朋友，

這篇文章就暫時(shí)寫到這里吧臼寄，希望每一位進(jìn)來的朋友都能夠有所收獲。（雖然粉絲不多）

我是Taoye溜宽，愛專研吉拳，愛分享，熱衷于各種技術(shù)适揉，學(xué)習(xí)之余喜歡下象棋留攒、聽音樂、聊動(dòng)漫嫉嘀，希望借此一畝三分地記錄自己的成長過程以及生活點(diǎn)滴炼邀，也希望能結(jié)實(shí)更多志同道合的圈內(nèi)朋友，更多內(nèi)容歡迎來訪微信公主號：玩世不恭的Coder

我們下期再見剪侮，拜拜~~~

參考資料：

<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>

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市胜茧，隨后出現(xiàn)的幾起案子粘优，更是在濱河造成了極大的恐慌，老刑警劉巖呻顽，帶你破解...
沈念sama閱讀 211,042評論 6贊 490
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件雹顺，死亡現(xiàn)場離奇詭異，居然都是意外死亡廊遍，警方通過查閱死者的電腦和手機(jī)嬉愧，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 89,996評論 2贊 384
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來喉前，“玉大人没酣，你說我怎么就攤上這事÷延兀” “怎么了裕便？”我有些...
開封第一講書人閱讀 156,674評論 0贊 345
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長见咒。經(jīng)常有香客問我偿衰，道長，這世上最難降的妖魔是什么改览？我笑而不...
開封第一講書人閱讀 56,340評論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任下翎，我火速辦了婚禮，結(jié)果婚禮上宝当，老公的妹妹穿的比我還像新娘视事。我一直安慰自己，他們只是感情好庆揩，可當(dāng)我...
茶點(diǎn)故事閱讀 65,404評論 5贊 384
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布俐东。她就那樣靜靜地躺著，像睡著了一般订晌。火紅的嫁衣襯著肌膚如雪犬性。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,749評論 1贊 289
城市分裂傳說
那天腾仅，我揣著相機(jī)與錄音乒裆，去河邊找鬼。笑死推励，一個(gè)胖子當(dāng)著我的面吹牛鹤耍，可吹牛的內(nèi)容都是我干的肉迫。我是一名探鬼主播，決...
沈念sama閱讀 38,902評論 3贊 405
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼稿黄，長吁一口氣：“原來是場噩夢啊……” “哼喊衫！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起杆怕，我...
開封第一講書人閱讀 37,662評論 0贊 266
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤族购，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后陵珍，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體寝杖，經(jīng)...
沈念sama閱讀 44,110評論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,451評論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年互纯，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了瑟幕。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,577評論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡留潦，死狀恐怖只盹，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情兔院，我是刑警寧澤殖卑，帶...
沈念sama閱讀 34,258評論 4贊 328
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站坊萝，受9級特大地震影響懦鼠，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜屹堰，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,848評論 3贊 312
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望街氢。院中可真熱鬧扯键，春花似錦、人聲如沸珊肃。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,726評論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽伦乔。三九已至厉亏，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間烈和，已是汗流浹背爱只。一陣腳步聲響...
開封第一講書人閱讀 31,952評論 1贊 264
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留招刹，地道東北人恬试。一個(gè)月前我還...
沈念sama閱讀 46,271評論 2贊 360
代替公主和親
正文我出身青樓窝趣，卻偏偏與公主長得像，于是被迫代替她去往敵國和親训柴。傳聞我的和親對象是個(gè)殘疾皇子哑舒，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,452評論 2贊 348

《Machine Learning in Action》—— 女同學(xué)問Taoye，KNN應(yīng)該怎么玩才能通關(guān)

《Machine Learning in Action》—— 女同學(xué)問Taoye挽绩，KNN應(yīng)該怎么玩才能通關(guān)

一、什么是K-近鄰算法（KNN）

二、基于KNN實(shí)現(xiàn)約會(huì)網(wǎng)站的對象配對

三鞋诗、基于KNN實(shí)現(xiàn)手寫數(shù)字識別系統(tǒng)

推薦閱讀更多精彩內(nèi)容