機器學習--手寫識別（k-NearestNeighbor）

01-31

No.1 什麼是KNN

k-NearestNeighbor也叫做最近鄰居演算法，就是經常說knn分類機器學習演算法。

作為最簡單的機器學習演算法，他的演算法思想也很好理解，就是說從你的訓練樣本中拿來k個和你測試樣本距離最近的樣本。然後在這k個樣本里找出現頻率最高的，那就是測試樣本的類別。這裡的距離一般使用歐氏距離或曼哈頓距離。

歐式距離：歐幾里得度量（euclidean metric）（也稱歐氏距離）是一個通常採用的距離定義，指在m維空間中兩個點之間的真實距離，或者向量的自然長度（即該點到原點的距離）。在二維和三維空間中的歐氏距離就是兩點之間的實際距離。

曼哈頓距離：用以標明兩個點在標準坐標繫上的絕對軸距總和，曼哈頓距離的命名原因是從規劃為方型建築區塊的城市（如曼哈頓）間，最短的行車路徑而來。

下圖中紅線代表曼哈頓距離，綠色代表歐式距離，也就是直線距離，而藍色和黃色代表等價的曼哈頓距離。

那麼根據以上其實可以實現一下歐氏距離或者曼哈頓距離的函數了，以歐氏距離為為本次項目實現的距離標準

from numpy import *n# 歐氏距離公式ndef euclidean_distance(x, y):n # 首先求平方n sq = (x - y)**2n # 再對平方結果求和並且開方n distance = (sq.sum(axis=1))**0.5n return distancen

No.2 KNN分類過程

我們以wiki上的一張圖開始

我們看到圖中紅色三角形和藍色矩形是已經知道的類別，現在我們想要知道那個綠色的圓形是什麼類型的。那我們要利用藍色矩形和紅色三角形這兩個已經知道的類型對綠色圓形進行分類。

1、首先我們要確定KNN演算法的K值的大小，這個K其實就是表示i我們綠色圓形他的鄰居的個數，當然這個鄰居的個數K有我們來定。

2、那麼這個K（鄰居個數）是怎麼定的呢？比如上圖中，我們要計算綠色圓形，我們需要根據距離度量公式（如：歐氏距離）計算出綠色圓形和藍色矩形類中以及紅色三角形類中距離最近的K個鄰居。

3、如上圖，K如果為3，那麼我們看實線範圍內，有兩個紅色三角形和一個藍色矩形，那麼我們就把這個綠色圓形歸為紅色三角形類中。K如果為5，那麼我們看虛線範圍內，有三個藍色矩形和兩個紅色三角形，那麼我們就把綠色圓形歸為藍色矩形類中。也就是說根據K個鄰居類別，數量最多的鄰居樣本是什麼類別，我們就把這個綠色圓形歸為什麼類別。

No.3 手寫數字識別（相關項目數據下載在文末）

項目準備工作：安裝Anaconda並配置虛擬環境，需要用到numpy

kNN演算法主要被應用於文本分類、相似推薦，這裡我們就用python以及相關的包進行識別。

手寫盡然是手寫數字識別，顧名思義就是人用筆寫出來不具備字體格式的數字，我們要做的就是把用筆寫的筆跡信息轉化為具體字碼。

手寫識別包括太多太多了，除了數字還有語言以及各種不規則字元。數字只是一個小小小部分，所以重點是學習下knn而不是糾結於其他，我們用到的數據是簡單的0～9這十個數字

1、數據格式

每個手寫數字已經處理成32*32的二進位文本，存儲為txt文件。0～9每個數字都有10個訓練樣本，5個測試樣本。如圖

2、將訓練集圖片合併為100*1024的矩陣並對所有訓練文件做處理

首先使用os模塊中的listdir(str)讀取出所有的訓練集文件，並返回所有文件名的字元串列表，並且使用len()求得所有文件個數，再以文件個數為行，1024為列生成矩陣。

以矩陣行數為遍歷計數，遍歷每一個訓練文件並做出相應處理。

將訓練文件轉換為特徵向量的函數featurevector

# 轉化為1*1024的特徵向量ndef featurevector(file):n feature_vector = zeros((1, 1024))n img_file = open(file)n for i in range(32):n read_line = img_file.readline()n # print(read_line)n for j in range(32):n # print("i:%s" % i)n # print("j:%s" % j)n feature_vector[0, 32*i+j] = int(read_line[j])n # print(feature_vector)n return feature_vectorn

我們可以測試一下，用featurevector處理後的圖片

# 轉換成特徵向量之後測試轉換後的圖片ndef test_featurevector(feature_vector):n for value in feature_vector:n for count in range(32):n test = list(value[32*count:32*count+32])n print(test)nfile = "/你放項目文件的路徑下的測試或者訓練集中的任意一個文件/3_9.txt"ntest_featurevector(featurevector(file))n

看看測試結果啥樣的

是一個3，離遠一點看，還是看得出來的。再看看沒處理之前的這個3_9.txt文件

3、逐一讀取測試圖片，將其分類並最終得到三個最近鄰居的出現頻率，然後挑選出頻率最高的。

首先讀取測試集文件，並且拿到測試集個數

以測試集個數為遍歷計數，遍歷所有的測試文件，同樣的對所有的測試文件做相應處理，並且將每一個遍歷的測試文件轉換成特徵向量。最終將測試集矩陣、訓練集矩陣、訓練集文件列表、K值一起傳遞進分類函數classify中得出最後結果

def handwriting_guess():n # 載入訓練集到矩陣中n handwriting_labels = []n # os模塊中的listdir(str)可以讀取目錄str下的所有文件名，返回一個字元串列表n training_file_list = listdir(trainingfile)n print("所有訓練集文件 : %s" % training_file_list)n # 矩陣的行數就是trainingfile文件的個數n row = len(training_file_list)n print("所有訓練集文件的個數 : %s" % row)n trainingfile_matrix = zeros((row, 1024))n print("生成訓練集矩陣 : %s" % trainingfile_matrix)nn for i in range(row):n # 遍歷訓練集中所有訓練文件：1_120.txtn training_file_name = training_file_list[i]n # 去除.txt後綴, 1_120.txt --> 1_120n training_file = training_file_name.split(.)[0]n # 以_切片，得到1，1_120 --> 1n training_digit = int(training_file.split(_)[0])n # 把處理好的文件名放進列表handwriting_labels中待後用n handwriting_labels.append(training_digit)n # 將遍歷的每一個訓練文件轉換為特徵向量n trainingfile_matrix[i, :] = featurevector(trainingfile/%s % training_file_name)n print("處理訓練集文件名handwriting_Labels : %s" % handwriting_labels)n print("將所有訓練文件轉換為特徵向量trainingfile_matrix : %s" % trainingfile_matrix)nn # 逐一讀取測試圖片，同時將其分類n testfile_list = listdir(testfile)n print("測試集 : %s" % testfile_list)n error_count = 0.0n testfile_nums = len(testfile_list)n print(" 測試集個數 : %s" % testfile_nums)nn for i in range(testfile_nums):n testfile_name = testfile_list[i]n testfile = testfile_name.split(.)[0]n test_digit = int(testfile.split(_)[0])n # 將遍歷的每一個測試文件轉換為特徵向量n testfile_matrix = featurevector(testfile/%s % testfile_name)n print("將每一個測試集文件准換成特徵向量testfile_matrix: %s" % testfile_matrix)n knn_result = classify(testfile_matrix, trainingfile_matrix, handwriting_labels, 3)n print("KNN識別的結果: %d, 真實的結果: %d" % (knn_result, test_digit))n if knn_result != test_digit:n error_count += 1.0n print("n識別出錯數量: %d" % error_count)n print("n識別錯誤率: %f" % (error_count / float(testfile_nums)))n# 運行KNN演算法識別手寫數字nhandwriting_guess()n

分類函數classify的實現，這個時候我們前面寫好的歐氏距離函數euclidean_distance就派上用場了。

def classify(testfile_matrix, trainingfile_matrix, handwriting_labels, k):n print("所要測試的向量testfile_matrix : %s" % testfile_matrix)n print("訓練樣本集trainingfile_matrix : %s" % trainingfile_matrix)n print("訓練樣本集對應的文件標籤（0, 1, 2, 3.....9）handwriting_Labels : %s" % handwriting_labels)n print("最近鄰居數目 : %s" % k)n trainingfile_matrix_size = trainingfile_matrix.shape[0]n print("1、訓練樣本集的行數（即樣本個數）: %s" % trainingfile_matrix_size)n testfile_array = tile(testfile_matrix, (trainingfile_matrix_size, 1))n print("2、將所要測試的向量作為元素構造以樣本個數為行，1列的數組testfile_array : %s" % testfile_array)n distance = euclidean_distance(testfile_array, trainingfile_matrix)n # array.argsort()，得到每個元素的排序序號n sort_euclidean_distance = distance.argsort()n print("得到每個元素的排序序號集合（距離按照從小到大排序） : %s" % sort_euclidean_distance)n knn_dict={}n for i in range(k):n """n k若等於3，那麼就拿出sort_euclidean_distance的前三個下標元素（距離最小的前三個元素）n 並且按照這前三個下標找到在handwriting_Labels中對應下標的手寫數字，這個數字就是NearestNeighbor，最近鄰居，當然一共有3個n """n nearest_neighbor = handwriting_labels[sort_euclidean_distance[i]]n print("NearestNeighbor : %s" % nearest_neighbor)n """n KNN_dict就是用來計數的，三個鄰居誰出現頻率高就確定測試數字是和哪個鄰居一個類別，即同一個數字n """n knn_dict[nearest_neighbor] = knn_dict.get(nearest_neighbor, 0) + 1n print("KNN_dict : %s" % knn_dict)n # sorted()函數，按照第二個元素即value的次序逆向（reverse=True）排序n sorted_knn_dict = sorted(knn_dict.items(), key=operator.itemgetter(1), reverse=True)n print("最近鄰居出現頻率sorted_KNN_dict : %s" % sorted_knn_dict)n return sorted_knn_dict[0][0]n

4、代碼整合以及項目目錄

# -*- coding:utf-8 -*-nfrom numpy import *nimport operatornfrom os import listdirnnn# 轉化為1*1024的特徵向量ndef featurevector(file):n feature_vector = zeros((1, 1024))n img_file = open(file)n for i in range(32):n read_line = img_file.readline()n # print(read_line)n for j in range(32):n # print("i:%s" % i)n # print("j:%s" % j)n feature_vector[0, 32*i+j] = int(read_line[j])n # print(feature_vector)n return feature_vectornnn# file = "/Users/chandler/Documents/Projects/machine-learning/data_analysis/anaysize/trainingfile/3_9.txt"n# print(featurevector(file))nnn# 轉換成特徵向量之後測試轉換後的圖片ndef test_featurevector(feature_vector):n for value in feature_vector:n for count in range(32):n test = list(value[32*count:32*count+32])n print(test)n# test_featurevector(featurevector(file))nnn# 歐氏距離公式ndef euclidean_distance(x, y):n # 首先求平方n sq = (x - y)**2n # 再對平方結果求和並且開方n distance = (sq.sum(axis=1))**0.5n return distancennndef classify(testfile_matrix, trainingfile_matrix, handwriting_labels, k):n print("所要測試的向量testfile_matrix : %s" % testfile_matrix)n print("訓練樣本集trainingfile_matrix : %s" % trainingfile_matrix)n print("訓練樣本集對應的文件標籤（0, 1, 2, 3.....9）handwriting_Labels : %s" % handwriting_labels)n print("最近鄰居數目 : %s" % k)n trainingfile_matrix_size = trainingfile_matrix.shape[0]n print("1、訓練樣本集的行數（即樣本個數）: %s" % trainingfile_matrix_size)n testfile_array = tile(testfile_matrix, (trainingfile_matrix_size, 1))n print("2、將所要測試的向量作為元素構造以樣本個數為行，1列的數組testfile_array : %s" % testfile_array)n distance = euclidean_distance(testfile_array, trainingfile_matrix)n # array.argsort()，得到每個元素的排序序號n sort_euclidean_distance = distance.argsort()n print("得到每個元素的排序序號集合（距離按照從小到大排序） : %s" % sort_euclidean_distance)n knn_dict={}n for i in range(k):n """n k若等於3，那麼就拿出sort_euclidean_distance的前三個下標元素（距離最小的前三個元素）n 並且按照這前三個下標找到在handwriting_Labels中對應下標的手寫數字沒，這個數字就是NearestNeighbor，最近鄰居，當然一共有3個n """n nearest_neighbor = handwriting_labels[sort_euclidean_distance[i]]n print("NearestNeighbor : %s" % nearest_neighbor)n """n KNN_dict就是用來計數的，三個鄰居誰出現頻率高就確定測試數字是和哪個鄰居一個類別，即同一個數字n """n knn_dict[nearest_neighbor] = knn_dict.get(nearest_neighbor, 0) + 1n print("KNN_dict : %s" % knn_dict)n # sorted()函數，按照第二個元素即value的次序逆向（reverse=True）排序n sorted_knn_dict = sorted(knn_dict.items(), key=operator.itemgetter(1), reverse=True)n print("最近鄰居出現頻率sorted_KNN_dict : %s" % sorted_knn_dict)n return sorted_knn_dict[0][0]nnndef handwriting_guess():n # 載入訓練集到矩陣中n handwriting_labels = []n # os模塊中的listdir(str)可以讀取目錄str下的所有文件名，返回一個字元串列表n training_file_list = listdir(trainingfile)n print("所有訓練集文件 : %s" % training_file_list)n # 矩陣的行數就是trainingfile文件的個數n row = len(training_file_list)n print("所有訓練集文件的個數 : %s" % row)n trainingfile_matrix = zeros((row, 1024))n print("生成訓練集矩陣 : %s" % trainingfile_matrix)nn for i in range(row):n # 遍歷訓練集中所有訓練文件：1_120.txtn training_file_name = training_file_list[i]n # 去除.txt後綴, 1_120.txt --> 1_120n training_file = training_file_name.split(.)[0]n # 以_切片，得到1，1_120 --> 1n training_digit = int(training_file.split(_)[0])n # 把處理好的文件名放進列表handwriting_labels中待後用n handwriting_labels.append(training_digit)n # 將遍歷的每一個訓練文件轉換為特徵向量n trainingfile_matrix[i, :] = featurevector(trainingfile/%s % training_file_name)n print("處理訓練集文件名handwriting_Labels : %s" % handwriting_labels)n print("將所有訓練文件轉換為特徵向量trainingfile_matrix : %s" % trainingfile_matrix)nn # 逐一讀取測試圖片，同時將其分類n testfile_list = listdir(testfile)n print("測試集 : %s" % testfile_list)n error_count = 0.0n testfile_nums = len(testfile_list)n print(" 測試集個數 : %s" % testfile_nums)nn for i in range(testfile_nums):n testfile_name = testfile_list[i]n testfile = testfile_name.split(.)[0]n test_digit = int(testfile.split(_)[0])n # 將遍歷的每一個測試文件轉換為特徵向量n testfile_matrix = featurevector(testfile/%s % testfile_name)n print("將每一個測試集文件准換成特徵向量testfile_matrix: %s" % testfile_matrix)n knn_result = classify(testfile_matrix, trainingfile_matrix, handwriting_labels, 3)n print("KNN識別的結果: %d, 真實的結果: %d" % (knn_result, test_digit))n if knn_result != test_digit:n error_count += 1.0n print("n識別出錯數量: %d" % error_count)n print("n識別錯誤率: %f" % (error_count / float(testfile_nums)))n# 運行KNN演算法識別手寫數字nhandwriting_guess()n

我們來看看執行是什麼樣子的

由於為了執行的時候更加清楚的看到步驟，所以放了很多print，那麼把print去掉的話看看直觀的結果。

至此，項目結束。

其實識別手寫數字是很簡單的，還有很多可以做的項目，比如識別圖片，比如識別漢字等等，後面有空再做一個識別圖片的小項目吧。

項目下載地址：鏈接:http://pan.baidu.com/s/1nuPOUwh 密碼:0d1l