統計學習方法|K近鄰原理剖析及實作

歡迎直接到我的部落格檢視最近文章：www.pkudodo.com。更新會比較快，評論回複我也能比較快看見，排版也會更好一點。

原始blog連結： http://www.pkudodo.com/2018/11/19/1-2/

前言

《統計學習方法》一書在前幾天正式看完，由于這本書在一定程度上對于初學者是有一些難度的，趁着熱乎勁把自己走過的彎路都寫出來，後人也能走得更順暢一點。

以下是我的github位址，其中有《統計學習方法》書中所有涉及到的算法的實作，也是在寫部落格的同時編寫的。在編寫宗旨上是希望所有人看完書以後，按照程式的思路再配合書中的公式，能知道怎麼講所學的都應用上。（有點自戀地講）程式中的注釋可能比大部分的部落格内容都多。希望大家能夠多多捧場，如果可以的話，為我的github打顆星，也能讓更多的人看到。

github：

GitHub|手寫實作李航《統計學習方法》書中全部算法

相關博文：

1. 統計學習方法|感覺機原理剖析及實作
2. 統計學習方法|K近鄰原理剖析及實作
3. 統計學習方法|樸素貝葉斯原理剖析及實作
4. 統計學習方法|決策樹原理剖析及實作
5. 統計學習方法|邏輯斯蒂原理剖析及實作

正文

K近鄰的直覺了解

我們先看一張圖：

在感覺機一節中我們看過這張圖，當時使用劃分超平面的方式來劃分資料。那麼除了劃線，還有别的方式來劃分資料嗎？

觀察一下，黃點和藍點代表了兩種标簽，比如每個藍點都是一個合格的産品，黃點是劣質的産品。事實上在圖中可以看到，相同标記的樣本點通常是成團的形式聚在一起，因為合格的産品在屬性上一定是相同或相似的（合格的産品在屬性上不太可能會跑到不合格的一類中去）。

那麼我們預測過程中，檢視被預測的樣本x是屬于哪一堆來判斷它是黃豆還是藍豆是不是可行呢？

當然可以啦，K近鄰就是一種基于該原理的算法。從名字裡就可以看到，K近鄰樣本的預測上，是看被預測樣本x離哪一團最近，那它就是屬于哪一類的。

接下來我們正兒八經地來看一下K近鄰，看下面這張圖。

圖裡有兩種标記，就叫它黃豆、綠豆、紫豆好了（這裡也能看到，K近鄰不像感覺機隻能劃分兩種類，K近鄰是一種多類劃分的模型）。當我們要預測一個樣本x時，将x的特征轉換為在圖中的坐标點，分别計算和綠豆、黃豆、紫豆的舉例，比如說距離分别為1， 1.5， 0.8。選擇其中距離最小的紫豆作為樣本x的預測類别。

那啥是樣本x和一團豆的距離？

1.找到樣本x最近的點，該點的類就是樣本的預測類：這是一種方法，但是如果有噪音呢（同一塊區域又有黃點又有綠點）？比如說x實際上是黃豆，但是它的位置在黃豆和綠豆的邊界上（例如上圖黃點和綠點的交叉處），很可能它最近的點是一個綠點，是以....不太好

2.與每一團的中心點進行距離計算：分别計算綠色、黃色、紫色的中心點，判斷距離最小的類即為預測輸出類。這樣會不會有問題嗎？我們看一下上圖中綠色和紫色交叉的地方，很明顯在這個交叉位置離綠色很近，與紫色中心點較遠，但實際上紫色的。是以.....不太好

3.找到樣本點周圍的K個點，其中占數目最多的類即預測輸出的類：克服了前兩種方法的弊端，實際上這就是K近鄰所使用的算法

感覺機的數學角度（配合《統計學習方法》食用更佳）

算法剖析

K近鄰并沒有顯式的學習過程，也就是不需要對訓練集進行學習。預測過程中直接周遊預測點與所有點的距離，并找到最近的K個點即可。找到K個最近點後，使用多數表決（即投票）的方式确定預測點的類别。式3.1I(yi=ci)中的I為訓示函數，當括号内條件為真時I(true)=1，I(false)=0。argmax表示令後式數值最大時的參數，例如argmax(-X^2 + 1)的結果為0，因為x=0時-X^2 + 1結果為1，為最大值。

式3.1表示對于每一個類Cj，進行I(yi=cj)進行求和，就是計算這K個點中有多少個标記為Cj的點，例如K=25，一共有四個類分别為C1、C2、C3、C4，25個點中他們的個數分别有10、5、1、9個，那麼最多數目的類别C1就是樣本點的預測類别。

距離度量

在多元空間中有很多種方式可以計算點與點之間的舉例，通常采用歐氏距離作為K近鄰的度量機關（大部分模型中歐氏距離都是一種不錯的選擇）。其實就是樣本A、B中每一個特征都互相相減，再平方、再求和。與二維中兩點之間距離計算方式相同，隻是擴充到了多元。

曼哈頓與P=無窮可以不用深究，在本文中使用曼哈頓準确度極差（僅針對Mnist資料集使用K近鄰的情況），這兩種方式目前僅作了解即可。

K近鄰算法缺點：

1、在預測樣本類别時，待預測樣本需要與訓練集中所有樣本計算距離，當訓練集數量過高時（例如Mnsit訓練集有60000個樣本），每預測一個樣本都要計算60000個距離，計算代價過高，尤其當測試集數目也較大時（Mnist測試集有10000個）。

1、K近鄰在高維情況下時（高維在機器學習中并不少見），待預測樣本需要與依次與所有樣本求距離。向量次元過高時使得歐式距離的計算變得不太迅速了。本文在60000訓練集的情況下，将10000個測試集縮減為200個，整個過程仍然需要308秒（曼哈頓距離為246秒，但準确度大幅下降）。

使用歐氏距離還是曼哈頓距離，性能上的差别相對來說不是很大，說明歐式距離并不是制約計算速度的主要方式。最主要的是訓練集的大小，每次預測都需要與60000個樣本進行比對，同時選出距離最近的K項。

為了解決這一問題，前人提出了KD樹算法。

KD樹

KD樹将整個特征空間劃分成多個區域，直覺上來看，首先将整個空間分成A、B區域，待測樣本判斷在A區的時候，那B區過遠，内部的點就不需要再判斷了，大幅度減少需要比較的樣本數量。

但遺憾的是作者暫時沒有對KD樹進行實作，僅僅在理論層面上講解并不是我所希望的。是以各位同學請耐心等待，等我将其實作後，寫出來的内容可能會更有深度一些。

貼代碼：（建議去本文最上方的github連結下載下傳，有書中所有算法的實作以及詳細注釋）

#coding=utf-8
#Author:Dodo
#Date:2018-11-16
#Email:[email protected]

'''
資料集：Mnist
訓練集數量：60000
測試集數量：10000（實際使用：200）
------------------------------
運作結果：（鄰近k數量：25）
向量距離使用算法——歐式距離
    正确率：97%
    運作時長：308s
向量距離使用算法——曼哈頓距離
    正确率：14%
    運作時長：246s
'''

import numpy as np
import time

def loadData(fileName):
    '''
    加載檔案
    :param fileName:要加載的檔案路徑
    :return: 資料集和标簽集
    '''
    print('start read file')
    #存放資料及标記
    dataArr = []; labelArr = []
    #讀取檔案
    fr = open(fileName)
    #周遊檔案中的每一行
    for line in fr.readlines():
        #擷取目前行，并按“，”切割成字段放入清單中
        #strip：去掉每行字元串首尾指定的字元（預設空格或換行符）
        #split：按照指定的字元将字元串切割成每個字段，傳回清單形式
        curLine = line.strip().split(',')
        #将每行中除标記外的資料放入資料集中（curLine[0]為标記資訊）
        #在放入的同時将原先字元串形式的資料轉換為整型
        dataArr.append([int(num) for num in curLine[1:]])
        #将标記資訊放入标記集中
        #放入的同時将标記轉換為整型
        labelArr.append(int(curLine[0]))
    #傳回資料集和标記
    return dataArr, labelArr

def calcDist(x1, x2):
    '''
    計算兩個樣本點向量之間的距離
    使用的是歐氏距離，即 樣本點每個元素相減的平方  再求和  再開方
    歐式舉例公式這裡不友善寫，可以百度或谷歌歐式距離（也稱歐幾裡得距離）
    :param x1:向量1
    :param x2:向量2
    :return:向量之間的歐式距離
    '''
    return np.sqrt(np.sum(np.square(x1 - x2)))

    #馬哈頓距離計算公式
    # return np.sum(x1 - x2)




def getClosest(trainDataMat, trainLabelMat, x, topK):
    '''
    預測樣本x的标記。
    擷取方式通過找到與樣本x最近的topK個點，并檢視它們的标簽。
    查找裡面占某類标簽最多的那類标簽
    （書中3.1 3.2節）
    :param trainDataMat:訓練集資料集
    :param trainLabelMat:訓練集标簽集
    :param x:要預測的樣本x
    :param topK:選擇參考最鄰近樣本的數目（樣本數目的選擇關系到正确率，詳看3.2.3 K值的選擇）
    :return:預測的标記
    '''
    #建立一個存放向量x與每個訓練集中樣本距離的清單
    #清單的長度為訓練集的長度，distList[i]表示x與訓練集中第
    ## i個樣本的距離
    distList = [0] * len(trainLabelMat)
    #周遊訓練集中所有的樣本點，計算與x的距離
    for i in range(len(trainDataMat)):
        #擷取訓練集中目前樣本的向量
        x1 = trainDataMat[i]
        #計算向量x與訓練集樣本x的距離
        curDist = calcDist(x1, x)
        #将距離放入對應的清單位置中
        distList[i] = curDist

    #對距離清單進行排序
    #argsort：函數将數組的值從小到大排序後，并按照其相對應的索引值輸出
    #例如：
    #   >>> x = np.array([3, 1, 2])
    #   >>> np.argsort(x)
    #   array([1, 2, 0])
    #傳回的是清單中從小到大的元素索引值，對于我們這種需要查找最小距離的情況來說很合适
    #array傳回的是整個索引值清單，我們通過[:topK]取清單中前topL個放入list中。
    #----------------優化點-------------------
    #由于我們隻取topK小的元素索引值，是以其實不需要對整個清單進行排序，而argsort是對整個
    #清單進行排序的，存在時間上的浪費。字典有現成的方法可以隻排序top大或top小，可以自行查閱
    #對代碼進行稍稍修改即可
    #這裡沒有對其進行優化主要原因是KNN的時間耗費大頭在計算向量與向量之間的距離上，由于向量高維
    #是以計算時間需要很長，是以如果要提升時間，在這裡優化的意義不大。（當然不是說就可以不優化了，
    #主要是我太懶了）
    topKList = np.argsort(np.array(distList))[:topK]        #升序排序
    #建立一個長度時的清單，用于選擇數量最多的标記
    #3.2.4提到了分類決策使用的是投票表決，topK個标記每人有一票，在數組中每個标記代表的位置中投入
    #自己對應的地方，随後進行唱票選擇最高票的标記
    labelList = [0] * 10
    #對topK個索引進行周遊
    for index in topKList:
        #trainLabelMat[index]：在訓練集标簽中尋找topK元素索引對應的标記
        #int(trainLabelMat[index])：将标記轉換為int（實際上已經是int了，但是不int的話，報錯）
        #labelList[int(trainLabelMat[index])]：找到标記在labelList中對應的位置
        #最後加1，表示投了一票
        labelList[int(trainLabelMat[index])] += 1
    #max(labelList)：找到選票箱中票數最多的票數值
    #labelList.index(max(labelList))：再根據最大值在清單中找到該值對應的索引，等同于預測的标記
    return labelList.index(max(labelList))


def test(trainDataArr, trainLabelArr, testDataArr, testLabelArr, topK):
    '''
    測試正确率
    :param trainDataArr:訓練集資料集
    :param trainLabelArr: 訓練集标記
    :param testDataArr: 測試集資料集
    :param testLabelArr: 測試集标記
    :param topK: 選擇多少個鄰近點參考
    :return: 正确率
    '''
    print('start test')
    #将所有清單轉換為矩陣形式，友善運算
    trainDataMat = np.mat(trainDataArr); trainLabelMat = np.mat(trainLabelArr).T
    testDataMat = np.mat(testDataArr); testLabelMat = np.mat(testLabelArr).T

    #錯誤值技術
    errorCnt = 0
    #周遊測試集，對每個測試集樣本進行測試
    #由于計算向量與向量之間的時間耗費太大，測試集有6000個樣本，是以這裡人為改成了
    #測試200個樣本點，如果要全跑，将行注釋取消，再下一行for注釋即可，同時下面的print
    #和return也要相應的更換注釋行
    # for i in range(len(testDataMat)):
    for i in range(200):
        # print('test %d:%d'%(i, len(trainDataArr)))
        print('test %d:%d' % (i, 200))
        #讀取測試集目前測試樣本的向量
        x = testDataMat[i]
        #擷取預測的标記
        y = getClosest(trainDataMat, trainLabelMat, x, topK)
        #如果預測标記與實際标記不符，錯誤值計數加1
        if y != testLabelMat[i]: errorCnt += 1

    #傳回正确率
    # return 1 - (errorCnt / len(testDataMat))
    return 1 - (errorCnt / 200)



if __name__ == "__main__":
    start = time.time()

    #擷取訓練集
    trainDataArr, trainLabelArr = loadData('../Mnist/mnist_train.csv')
    #擷取測試集
    testDataArr, testLabelArr = loadData('../Mnist/mnist_test.csv')
    #計算測試集正确率
    accur = test(trainDataArr, trainLabelArr, testDataArr, testLabelArr, 25)
    #列印正确率
    print('accur is:%d'%(accur * 100), '%')

    end = time.time()
    #顯示花費時間
print('time span:', end - start)