機器學習2—KNN演算法(原理、實現、實例)

前置聲明:本專欄的所有文章皆為本人學習時所做筆記而整理成篇,轉載需授權且需註明文章來源,禁止商業用途,僅供學習交流.(歡迎大家提供寶貴的意見,共同進步)

從本篇開始講解機器學習的基礎演算法，篇章的結構大致為 概述 > 演算法原理 > 數學模型 > 演算法實現 > 實例的步驟進行講解。每周末更新一次。

正文:

眾所周知，我們每個人的長相千差萬別，但我們都有鼻子、耳朵、眼睛、臉蛋等，同時還有美醜之分，那麼我們的美醜如何定義呢? 沒有人敢說自己就是百分百的美女、美男，雖然如此，但我們確實又知道哪種五官令人舒服。如果說給我們每個人的長相進行分類打分的話，那我們應該依據什麼來進行分類呢? 是否有具有公共特徵使得被稱為美女或美男的人都十分類似呢? 這是當然的，比如高鼻樑、大眼睛的人肯定比塌鼻子、小眼睛的人評分高，因此判斷一個人是否到達美女、美男的要求，只需將他/她的五官與標準的精緻五官進行比較便可知道，越相似說明五官越精緻。那麼人可以通過觀察分辨，計算機如何分辨呢?

今天推出的第一個演算法便是最簡單的KNN(k-Nearest Neighbor)演算法，即K最近鄰演算法。它的原理十分簡單:存在一個訓練樣本集合，該集合中每行數據包含多個特徵和分類標籤，輸入沒有標籤但有多個特徵的新數據，將新數據的每個特徵與樣本中每條數據對應的特徵進行比較，然後提取出樣本中與新數據最相似的K條數據，統計該K條數據中各類標籤出現的次數，那麼出現次數最多的標籤即為新數據的分類標籤。

如圖所示，將新數據與訓練數據集中數據對應的特徵進行相似性比較是演算法中的核心，那麼我們通過什麼方法能夠得知其相似的程度呢?

在講解演算法實現前，我們需要回顧一點兒數學知識:兩點之間的距離。

初中數學課本里在講解坐標系時，我們得知，在二維平面內，若有 兩點，那麼A到B的距離D = ，若擴展到多維，則D =

通過公式，我們可以從側面看出，若D的值越小，那麼A和B的距離越近，則在坐標系中A和B位置越靠近，靠的越近正是因為A和B「相似」。

那麼我們如何將其應用到上述的分類例子中呢?

首先，我們可以將上述訓練集中的數據特徵用來對應A或B的坐標，即大眼睛、高鼻樑、細腰、... 對應 ，若字母A、B、C...代表人1，人2，人3，... 那麼數據人1，人2, ... 此時則為 [ 女神 ], [ 醜女] ，....，因此當判斷一條新數據 為那種類型的女生時，只需分別計算距離 ，距離 ，... ，再從中選取K條距離最近的訓練數據，最後統計K條訓練數據中出現次數最多的標籤則為Z的類別。

注意:數據中的特徵需要一 一對應，即特徵1表示眼睛，那麼每條數據中的第一個特徵的值都應是眼睛的大小取值。

當然這裡會人有問，數學公式中都是數字，而大眼睛、高鼻樑都是字元，這怎麼進行計算呢? 將字元型數據轉化為數值型數據以及其它對數據的預處理操作也是機器學習中的關鍵步驟。在機器學習中，一般情況下，我們是通過數學進行建模的，因此訓練數據都一般都會預處理為數值型數據。在上述例子中，我們可以將眼睛的大小級別設為1，2，3個等級，3表示為大眼睛，1表示為小眼睛，鼻樑、身高等特徵同理。因此數據預處理後就會是A(3,3,0.9,10...),因此這樣便可計算數據間的歐氏距離從而進行分類。

演算法實現(Python)

接下來我們利用Python中的科學計算包，實現這個演算法，並利用實例測試演算法的準確性。

首先新建 KNN.py

# -*- coding: utf-8 -*-nfrom numpy import * # 導入科學計算包nimport operator # 導入運算符模塊nimport jsonnn構造訓練數據集ndata:特徵值nlabels:每行數據對應的標籤nndef createDataSet():n data = array([[1, 1, 1, 1],n [0.5, 1, 1, 1],n [0.1, 0.1, 0.1, 0.1],n [0.5, 0.5, 0.5, 0.5],n [1, 0.8, 0.3, 1],n [0.6, 0.5, 0.7, 0.5],n [1, 1, 0.9, 0.5],n [1, 0.6, 0.5, 0.8],n [0.5, 0.5, 1, 1],n [0.9, 1, 1, 1],n [0.6, 0.6, 1, 0.1],n [1, 0.8, 0.5, 0.5],n [1, 0.1, 0.1, 1],n [1, 1, 0.7, 0.3],n [0.2, 0.3, 0.4, 0.5],n [0.5, 1, 0.6, 0.6]n ]);nn labels = [女神,n 淑女,n 醜女,n 一般型,n 淑女,n 一般型,n 女神,n 一般型,n 淑女,n 女神,n 醜女,n 可愛型,n 可愛型,n 淑女,n 醜女,n 可愛型n ]n return data,labelsnnKNN 分類器n參數說明:n inX:需要分類的新數據n data/labels:訓練數據集及其對應的標籤n k:選擇最近的訓練數據數目(一般不超過20) nnndef classify(inX,data,labels,k):n # shape[0] - 向量的行數 shape[1] - 向量的列數n #shape 返迴向量的行數和列數n dataSetSize = data.shape[0] # 計算共有多少條訓練數據nn # tile(array,reps)將數組array沿維度reps重複,構成新的數組n # a= [n # [1,2],n # [3,4]n # ]n # 如tile(a,2)表示a的第一個維度重複2遍,A = [[a],[a]]n # tile(a,(2,2))表示a的第一個維度重複2遍，第二個維度重複2遍n # 即tile(array,(rows,cols)) 將array看作單個向量再構造為rows行clos列n # tile(a,(2,2)) - >n # A = [n # [a,a],n # [a,a]n # ]nn # 歐式距離計算 [計算輸入向量與樣本集中各個點的距離]n #注意:不需要利用循環將輸入數據和樣本中的每條數據進行距離計算 利用矩陣運算便可一次性求出nn print 複製輸入向量 用於和樣本中的每條數據進行計算 [矩陣的加減乘除]n print tile(inX, (dataSetSize, 1))nn # 矩陣的減法 結果:每一項為輸入向量和各個樣本對應特徵點的差值構成的新矩陣n diffmat = tile(inX,(dataSetSize,1)) - datan print n相減後:n print diffmatnn sqDiffMat = diffmat**2 #平方 矩陣中每一項都平方n print n平方後:n print sqDiffMatn sqDistances = sqDiffMat.sum(axis=1) #axis=1 行向量相加 / axis=0 列向量相加n print n各個特徵點差值相加[即坐標差值相加]:n print sqDistancesnn distances = sqDistances**0.5 #開方n print n距離:n print distancesn sortedDistIndexes = distances.argsort() #從小到大將距離向量排序並返回其索引值nn # 選擇距離最小的K個點n classCount = {} # dict 保存對應標籤出現的次數n for i in range(k):n voteLabel = labels[sortedDistIndexes[i]] #獲得類別標籤nn # dict.get(key, default) 返回指定鍵的值，如果值不在字典中返回default值n # 對所屬的類別標籤個數進行統計n classCount[voteLabel] = classCount.get(voteLabel,0) + 1n print 標籤出現的次數:n print json.dumps(classCount, encoding="UTF-8", ensure_ascii=False)n #排序n #sorted(iterable, cmp=None, key=None, reverse=False)n #iterable：是可迭代類型;n #cmp：用於比較的函數，比較什麼由key決定,有默認值，迭代集合中的一項;n #key：用列表元素的某個屬性和函數進行作為關鍵字，有默認值，迭代集合中的一項;n #reverse：排序規則. reverse = True 倒序 / reverse = Falsen #operator.itemgetter(1) 利用第二個數據域進行排序n sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)nn print n排序後:n print json.dumps(sortedClassCount, encoding="UTF-8", ensure_ascii=False)n # 如: print sortedClassCount ———— [(A, 2), (B, 1)]nn return sortedClassCount[0][0] #返回次數出現次數最多的標籤n

測試:

# -*- coding: utf-8 -*-nimport KNNnfrom numpy import*ndata,labels = KNN.createDataSet()nnprint 測試模型分類樣本數據,結果是否和樣本中的分類一致ninput = [0.5, 1, 1, 1]nprint n分類結果:+KNN.classify(input, data, labels, 2)nnprint n測試新數據ninput = [1,1, 0.9, 1]nprint n分類結果:+KNN.classify(input, data, labels, 2)n

輸出結果:

測試模型分類樣本數據,結果是否和樣本中的分類一致n複製輸入向量 用於和樣本中的每條數據進行計算 [矩陣的加減乘除]n[[ 0.5 1. 1. 1. ]n [ 0.5 1. 1. 1. ]n [ 0.5 1. 1. 1. ]n [ 0.5 1. 1. 1. ]n [ 0.5 1. 1. 1. ]n [ 0.5 1. 1. 1. ]n [ 0.5 1. 1. 1. ]n [ 0.5 1. 1. 1. ]n [ 0.5 1. 1. 1. ]n [ 0.5 1. 1. 1. ]n [ 0.5 1. 1. 1. ]n [ 0.5 1. 1. 1. ]n [ 0.5 1. 1. 1. ]n [ 0.5 1. 1. 1. ]n [ 0.5 1. 1. 1. ]n [ 0.5 1. 1. 1. ]]nn相減後:n[[-0.5 0. 0. 0. ]n [ 0. 0. 0. 0. ]n [ 0.4 0.9 0.9 0.9]n [ 0. 0.5 0.5 0.5]n [-0.5 0.2 0.7 0. ]n [-0.1 0.5 0.3 0.5]n [-0.5 0. 0.1 0.5]n [-0.5 0.4 0.5 0.2]n [ 0. 0.5 0. 0. ]n [-0.4 0. 0. 0. ]n [-0.1 0.4 0. 0.9]n [-0.5 0.2 0.5 0.5]n [-0.5 0.9 0.9 0. ]n [-0.5 0. 0.3 0.7]n [ 0.3 0.7 0.6 0.5]n [ 0. 0. 0.4 0.4]]nn平方後:n[[ 0.25 0. 0. 0. ]n [ 0. 0. 0. 0. ]n [ 0.16 0.81 0.81 0.81]n [ 0. 0.25 0.25 0.25]n [ 0.25 0.04 0.49 0. ]n [ 0.01 0.25 0.09 0.25]n [ 0.25 0. 0.01 0.25]n [ 0.25 0.16 0.25 0.04]n [ 0. 0.25 0. 0. ]n [ 0.16 0. 0. 0. ]n [ 0.01 0.16 0. 0.81]n [ 0.25 0.04 0.25 0.25]n [ 0.25 0.81 0.81 0. ]n [ 0.25 0. 0.09 0.49]n [ 0.09 0.49 0.36 0.25]n [ 0. 0. 0.16 0.16]]nn各個特徵點差值相加[即坐標差值相加]:n[ 0.25 0. 2.59 0.75 0.78 0.6 0.51 0.7 0.25 0.16 0.98 0.79n 1.87 0.83 1.19 0.32]nn距離:n[ 0.5 0. 1.60934769 0.8660254 0.88317609 0.77459667n 0.71414284 0.83666003 0.5 0.4 0.98994949 0.88881944n 1.36747943 0.91104336 1.09087121 0.56568542]n標籤出現的次數:n{"淑女": 1, "女神": 1}nn排序後:n[["淑女", 1], ["女神", 1]]nn分類結果:淑女nn測試新數據n複製輸入向量 用於和樣本中的每條數據進行計算 [矩陣的加減乘除]n[[ 1. 1. 0.9 1. ]n [ 1. 1. 0.9 1. ]n [ 1. 1. 0.9 1. ]n [ 1. 1. 0.9 1. ]n [ 1. 1. 0.9 1. ]n [ 1. 1. 0.9 1. ]n [ 1. 1. 0.9 1. ]n [ 1. 1. 0.9 1. ]n [ 1. 1. 0.9 1. ]n [ 1. 1. 0.9 1. ]n [ 1. 1. 0.9 1. ]n [ 1. 1. 0.9 1. ]n [ 1. 1. 0.9 1. ]n [ 1. 1. 0.9 1. ]n [ 1. 1. 0.9 1. ]n [ 1. 1. 0.9 1. ]]nn相減後:n[[ 0. 0. -0.1 0. ]n [ 0.5 0. -0.1 0. ]n [ 0.9 0.9 0.8 0.9]n [ 0.5 0.5 0.4 0.5]n [ 0. 0.2 0.6 0. ]n [ 0.4 0.5 0.2 0.5]n [ 0. 0. 0. 0.5]n [ 0. 0.4 0.4 0.2]n [ 0.5 0.5 -0.1 0. ]n [ 0.1 0. -0.1 0. ]n [ 0.4 0.4 -0.1 0.9]n [ 0. 0.2 0.4 0.5]n [ 0. 0.9 0.8 0. ]n [ 0. 0. 0.2 0.7]n [ 0.8 0.7 0.5 0.5]n [ 0.5 0. 0.3 0.4]]nn平方後:n[[ 0. 0. 0.01 0. ]n [ 0.25 0. 0.01 0. ]n [ 0.81 0.81 0.64 0.81]n [ 0.25 0.25 0.16 0.25]n [ 0. 0.04 0.36 0. ]n [ 0.16 0.25 0.04 0.25]n [ 0. 0. 0. 0.25]n [ 0. 0.16 0.16 0.04]n [ 0.25 0.25 0.01 0. ]n [ 0.01 0. 0.01 0. ]n [ 0.16 0.16 0.01 0.81]n [ 0. 0.04 0.16 0.25]n [ 0. 0.81 0.64 0. ]n [ 0. 0. 0.04 0.49]n [ 0.64 0.49 0.25 0.25]n [ 0.25 0. 0.09 0.16]]nn各個特徵點差值相加[即坐標差值相加]:n[ 0.01 0.26 3.07 0.91 0.4 0.7 0.25 0.36 0.51 0.02 1.14 0.45n 1.45 0.53 1.63 0.5 ]nn距離:n[ 0.1 0.50990195 1.75214155 0.9539392 0.63245553 0.83666003n 0.5 0.6 0.71414284 0.14142136 1.06770783 0.67082039n 1.20415946 0.72801099 1.27671453 0.70710678]n標籤出現的次數:n{"女神": 2}nn排序後:n[["女神", 2]]nn分類結果:女神n

至此,KNN的演算法實現完成。

但是其中有幾個問題需要特別注意，這裡只是簡單的實現了KNN演算法，其中還要考慮K值的選取等問題。比如這裡由於是手動構造的樣本數據，數據量太少，K值便不能設太大，否則對模型進行檢驗時會有誤差。

當然，一般做開發我們並不會自己徒手實現演算法，因為已經有開源的演算法庫。比如scikit-learn和tensorflow.若Anaconda沒有安裝演算法包，請自行安裝。

如scikit-learn中的KNN演算法使用:

#coding:utf-8nfrom sklearn import datasets #sk-learn 內置資料庫nimport numpy as npnKNN演算法niris = datasets.load_iris() #內置的鳶尾花卉數據集n#數據集包含150個數據集，分為3類，每類50個數據,n#可通過花萼長度，花萼寬度，花瓣長度，花瓣寬度4個特徵預測鳶尾花卉屬於n#(Setosa，Versicolour，Virginica)三個種類中的哪一類niris_X,iris_y = iris.data,iris.target #數據集及其對應的分類標籤n# 將數據集隨機分為訓練數據集和測試數據集nnp.random.seed(0)nindices = np.random.permutation(len(iris_X))n#用於訓練模型niris_X_train = iris_X[indices[:-10]]niris_y_train = iris_y[indices[:-10]]n#用於測試模型niris_X_test = iris_X[indices[-10:]]niris_y_test = iris_y[indices[-10:]]nfrom sklearn.neighbors import KNeighborsClassifiernknn = KNeighborsClassifier()nknn.fit(iris_X_train,iris_y_train)nprediction = knn.predict(iris_X_test)nscore = knn.score(iris_X_test,iris_y_test)nnprint 真實分類標籤:+str(iris_y_test)nprint 模型分類結果:+str(prediction)+n演算法準確度:+str(score)n

輸出結果:

真實分類標籤:[1 1 1 0 0 0 2 1 2 0]n模型分類結果:[1 2 1 0 0 0 2 1 2 0]n演算法準確度:0.9n

至於scikit-learn和tensorflow的具體使用，講完機器學習的基本知識後會陸續講到,本專欄主要是機器學習的原理講解。其兩者的官方文檔十分詳盡,有興趣的讀者可以先行了解一下。