機器學(xué)習(xí)入門:K-近鄰算法

先來一個簡單的例子，我們?nèi)绾蝸韰^(qū)分動作類電影與愛情類電影呢？動作片中存在很多的打斗鏡頭，愛情片中可能更多的是親吻鏡頭，所以我們姑且通過這兩種鏡頭的數(shù)量來預(yù)測這部電影的主題。簡單的說， k-近鄰算法 采用了測量不同特征值之間的距離方法進行分類。
優(yōu)點：精度高、對異常值不敏感、無數(shù)據(jù)輸入假定 缺點：計算復(fù)雜度高、控件復(fù)雜度高 適用數(shù)據(jù)范圍：數(shù)值型和標(biāo)稱型
首先我們來理解它的工作原理：
存在一個樣本數(shù)據(jù)集（訓(xùn)練集），并且我們知道每一數(shù)據(jù)與目標(biāo)變量的對應(yīng)關(guān)系，輸入沒有標(biāo)簽的新數(shù)據(jù)后，將新數(shù)據(jù)的每個特征與樣本集中數(shù)據(jù)對應(yīng)的特征進行比較，然后算法提取樣本集中最相近的分類標(biāo)簽，一般來說，我們只選擇樣本集中前k個最相似的數(shù)據(jù)，通常k為不大于20的整數(shù)，最后，選擇k個最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類，作為新數(shù)據(jù)的分類。
現(xiàn)在我們回到文章開頭所提到的電影的例子，根據(jù)下表如何確定未知的電影類型呢？
電影名稱    打斗鏡頭    接吻鏡頭    電影類型
電影1    3    104    愛情
電影2    2    100    愛情
電影3    1    81    愛情
電影4    101    10    動作
電影5    99    5    動作
電影6    98    2    動作
電影7    18    90    未知？
該如何計算電影7的電影類型呢？計算電影7與樣本集中其他電影的距離，然后我們假定k=3，看一下最近的3部電影是什么類型即可預(yù)測出電影7的電影類型。
流程介紹
收集數(shù)據(jù)
準(zhǔn)備數(shù)據(jù)：距離計算所需要的值，最好是結(jié)構(gòu)化的數(shù)據(jù)格式
分析數(shù)據(jù)
測試算法：計算錯誤率
使用算法
開始工作
使用python導(dǎo)入數(shù)據(jù)
首先，創(chuàng)建名為kNN.py的Python模塊，在構(gòu)造算法之前，我們還需要編寫一些通用的函數(shù)等，我們先寫入一些簡單的代碼：
from numpy import *
import operator

def createDataSet():
    group = array([
      [1.0, 1.1],
      [1.0, 1.0],
      [0, 0],
      [0, 0.1]
    ])

    labels = ["A", "A", "B", "B"]

    return group, labels
然后將終端改變到代碼文件目錄，輸入命令python進入到交互界面：
>>> import kNN

>>> group, labels = kNN.createDataSet()

>>> group
array([[ 1. ,  1.1],
       [ 1. ,  1. ],
       [ 0. ,  0. ],
       [ 0. ,  0.1]])
>>> labels
['A', 'A', 'B', 'B']
這里有4組數(shù)據(jù)，每組數(shù)據(jù)有2個我們已知的特征值，上面的group矩陣每行為一條數(shù)據(jù)，對于每個數(shù)據(jù)點我們通常使用2個特征（所以特征的選擇很重要），向量labels包含了每個數(shù)據(jù)點的標(biāo)簽信息，labels的維度等于矩陣的行數(shù)，這里我們將 [1, 1,1] 定為類A， [0, 0.1] 定為類B，接下來我們進行算法的編寫：
計算已知數(shù)據(jù)集中點到當(dāng)前點之間的距離
按照距離遞增次序排序
選取與當(dāng)前點距離最小的k個點
確定前k個點所在類別的出現(xiàn)頻率
返回前k個點中頻次最高的類別作為預(yù)測類別
接著定義函數(shù)：
# inX: 用于分類的輸入向量
# dataSet：輸入的訓(xùn)練集
# labels：標(biāo)簽向量
# k：選擇近鄰項目的個數(shù)
def classify0(inX, dataSet, labels, k) :
    dataSetSize = dataSet.shape[0]
    # 距離計算
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2 # python中, **2 代表2平方，**0.5代表開方
    sqDistances = sqDiffMat.sum(axis=1) # 加入axis=1以后就是將一個矩陣的每一行向量相加
    distances = sqDistances ** 0.5
    sortedDistIndicies = distances.argsort()
    classCount = {}

    # 選擇距離最小的k個點
    for i in range(k) :
        voteILabel = labels[sortedDistIndicies[i]]
        classCount[voteILabel] = classCount.get(voteILabel, 0) + 1

    # 排序
    sortedClassCount = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]
然后我們進行測試，重新打開python編譯環(huán)境：
>>> import kNN
>>> group, labels = kNN.createDataSet()
>>> kNN.classify0([0, 0], group, labels, 3)
'B'
>>> kNN.classify0([0.3, 0], group, labels, 3)
'B'
>>> kNN.classify0([0.8, 0.9], group, labels, 3)
'A'
我們看到，一個簡單的分類器就這樣搞定了。這時，我們來將電影數(shù)據(jù)進行樣本寫入：
def createDataSet():
    group = array([
      [3, 104],
      [2, 100],
      [1, 81],
      [101, 10],
      [99, 5],
      [98, 2]
    ])

    labels = ["love", "love", "love", "action", "action", "action"]

    return group, labels
>>> import kNN
>>> group, labels = kNN.createDataSet()
>>> kNN.classify0([18, 90], group, labels, 3)
'love'
我們看到預(yù)測結(jié)果為愛情片。這是一個簡單的分類器，當(dāng)然，我們應(yīng)該通過大量的測試，看預(yù)測結(jié)果與預(yù)期結(jié)果是否相同，進而得出錯誤率，完美的分類器錯誤率為0，最差的錯誤率為1，上邊電影分類的例子已經(jīng)可以使用了，但是貌似沒有太大的作用，下邊我們來看一個生活中的實例，使用k-近鄰算法改進約會網(wǎng)站的效果，然后使用k-近鄰算法改進手寫識別系統(tǒng)。
改進約會網(wǎng)站的配對效果
有個姑娘，一直在使用某交友網(wǎng)站，但是推薦來的人總是不盡人意，她總結(jié)了一番，曾交往過3中類型的人：
不喜歡的人
魅力一般的人
極具魅力的人
她覺得自己可以在周一~周五約會那些魅力一般的人，周末與那些極具魅力的人約會，因為她希望我們可以更好的幫助她將匹配的對象劃分到確切的分類中，她還收集了一些約會網(wǎng)站未曾記錄過的數(shù)據(jù)信息，她認為這些數(shù)據(jù)信息會有幫助。這些數(shù)據(jù)存放在代碼文件夾下 datingTestSet2.txt 中，總共有1000行數(shù)據(jù)（妹的約了1000個人），主要包含以下特征：
每年獲得的飛行?？屠锍虜?shù)
玩視頻游戲所消耗的時間百分比
每周消費的冰激凌公升數(shù)
我們看到，統(tǒng)計的東西都比較奇葩，我們先從文件中把這些數(shù)值解析出來，輸出訓(xùn)練樣本矩陣和分類標(biāo)簽向量。在kNN.py中繼續(xù)書寫代碼：
從文本中讀入數(shù)據(jù)
def file2matrix(filename) :
    fr = open(filename)
    arrayOfLines = fr.readlines()
    numberOfLines = len(arrayOfLines) # 得到文件行數(shù)
    returnMat = zeros((numberOfLines, 3)) # 創(chuàng)建用0填充的矩陣，這里為了簡化處理，我們將矩陣的另一個緯度設(shè)置為3，可以按照自己的需求增加數(shù)量。

    classLabelVector = []
    index = 0
    # 解析文件
    for line in arrayOfLines :
        line = line.strip() # 截取掉所有的回車字符
        listFromLine = line.split('\t')
        returnMat[index, :] = listFromLine[0: 3] # range
        classLabelVector.append(int(listFromLine[-1]))
        index += 1

    return returnMat, classLabelVector
>>> import kNN
>>> mat, vector = kNN.file2matrix('datingTestSet2.txt')

>>> mat, vector = kNN.file2matrix('datingTestSet2.txt')
>>> mat
array([[  4.09200000e+04,   8.32697600e+00,   9.53952000e-01],
       [  1.44880000e+04,   7.15346900e+00,   1.67390400e+00],
       [  2.60520000e+04,   1.44187100e+00,   8.05124000e-01],
       ...,
       [  2.65750000e+04,   1.06501020e+01,   8.66627000e-01],
       [  4.81110000e+04,   9.13452800e+00,   7.28045000e-01],
       [  4.37570000e+04,   7.88260100e+00,   1.33244600e+00]])
>>> vec
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'vec' is not defined
>>> vector
[3 ... 2]
現(xiàn)在我們已經(jīng)從文文件中導(dǎo)入了數(shù)據(jù)，并將其格式化為想要的格式，接著我們需要了解數(shù)據(jù)的真是含義，我們可以直觀的瀏覽文本文件，但是這種方法非常不友好，一般來說，我們會采用圖形化的方式直觀的展示數(shù)據(jù)。下面我們就用Python圖形化工具來圖形化展示數(shù)據(jù)內(nèi)容，以便辨識出一些數(shù)據(jù)模式。
分析數(shù)據(jù)，使用 Matplotlib 創(chuàng)建散點圖
pip install matplotlib
接下來打開python命令行，我們對剛才讀入的內(nèi)容進行測試的展示
>>> from matplotlib import *
>>> import matplotlib.pyplot as plt
>>> import kNN
>>> import numpy as np
>>> mat, vec = kNN.file2matrix('datingTestSet2.txt')
>>> fig = plt.figure()
>>> ax = fig.add_subplot(111)
>>> ax.scatter(mat[:, 1], mat[:, 2], 15.0*np.array(vec), 15.0*np.array(vec))
<matplotlib.collections.PathCollection object at 0x1087cf0d0>
>>> plt.show()

這個時候，我們展示的是數(shù)據(jù)集的第一列與第二列所繪制的圖，這里我們很難看出來什么端倪，所以我們嘗試使用第一列和第二列作為特征來繪圖，重新書寫上邊代碼：
ax.scatter(mat[:, 0], mat[:, 1], 15.0*np.array(vec), 15.0*np.array(vec))
然后我們得到了以下數(shù)據(jù)圖：

這次，我們可以看到，圖中清晰的標(biāo)識了3個不同的樣本分類區(qū)域。
準(zhǔn)備數(shù)據(jù)，歸一化數(shù)值
我們隨便的抽取了4組差異比較大的數(shù)據(jù)
玩游戲所消耗時間    里程數(shù)    冰激凌公升數(shù)    樣本分類
1    0.8    400    0.5    1
2    12    13400    0.9    3
3    0    20000    1.1    2
4    67    32000    0.1    2
我們很容易發(fā)現(xiàn)，如果我們計算樣本3和樣本4之間的距離，可以使用下邊的方法
$\sqrt{(0-67)^2 + (20000 + 32000)^2 + (1.1-0.1)^2}$
但是這些大的值堆結(jié)果的影響比較大，因此，作為比較重要的特征屬性，不應(yīng)該如此的影響計算結(jié)果，所以在處理數(shù)據(jù)的時候，我們對數(shù)據(jù)進行歸一化處理，將取值的范圍處理到0 - 1或者-1 ~ -1之間，下面的公事，可以將任意范圍內(nèi)的特征值轉(zhuǎn)換為0-1區(qū)間內(nèi)的值：
$newValue = (oldValue - min)/(max - min)$
其中，min和max分別為特征值中最大和最小值，雖然改變數(shù)值范圍增加了分類器的復(fù)雜度，但是為了得到準(zhǔn)確的結(jié)果，必須這樣做，所以我們在kNN.py中新增一個函數(shù) autoNorm() ，用來將數(shù)字特征值轉(zhuǎn)化為0-1的區(qū)間：
def autoNorm(dataSet) :
    minvals = dataSet.min(0) # 存放每列的最小值
    maxVals = dataSet.max(0) # 存放每列的最大值

    ranges = maxVals - minvals
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minvals, (m, 1))
    # 特征值相除
    normDataSet = normDataSet / tile(ranges, (m, 1))
    return normDataSet, ranges, minvals
運行結(jié)果：
>>> import kNN
>>> mat, vec = kNN.file2matrix('datingTestSet2.txt')
>>> a, b, c = kNN.autoNorm(mat)
>>> a
array([[ 0.44832535,  0.39805139,  0.56233353],
       [ 0.15873259,  0.34195467,  0.98724416],
       [ 0.28542943,  0.06892523,  0.47449629],
       ...,
       [ 0.29115949,  0.50910294,  0.51079493],
       [ 0.52711097,  0.43665451,  0.4290048 ],
       [ 0.47940793,  0.3768091 ,  0.78571804]])
這樣一來，我們把值處理成了我們預(yù)期的范偉內(nèi)的值。
測試算法
通常我們把數(shù)據(jù)集的90%的數(shù)據(jù)當(dāng)做訓(xùn)練集，余下的10%作為測試集，著10%的數(shù)據(jù)是隨機選擇的。 下面，我們來書寫測試程序，并通過 datingTestSet.txt 來測試程序：
def datingClassTest() :
    hoRatio = 0.10 # 設(shè)置抽取多少數(shù)據(jù)進行測試集
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt') # 讀入數(shù)據(jù)集
    normMat, ranges, minVals = autoNorm(datingDataMat) # 轉(zhuǎn)化特征值至 0 - 1 區(qū)間內(nèi)
    m = normMat.shape[0]
    numTestVecs = int( m * hoRatio ) # 計算測試向量的數(shù)量
    errorCount = 0.0

    for i in range(numTestVecs) :
        classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs: m], 3) # 使用近鄰算法得出結(jié)果

        print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])
        if (classifierResult != datingLabels[i]) : errorCount += 1.0 # 錯誤記錄與處理等

    print "the total error rate is: %f" % (errorCount / float(numTestVecs))
然后我們在python環(huán)境中通過
reload(kNN)
來重新加載kNN.py模塊，然后調(diào)用
kNN.datingClassTest()
得到結(jié)果:
the classifier came back with: 3, the real answer is: 3
the classifier came back with: 2, the real answer is: 2
the classifier came back with: 1, the real answer is: 1
the classifier came back with: 1, the real answer is: 1
the classifier came back with: 1, the real answer is: 1
...
the classifier came back with: 3, the real answer is: 3
the classifier came back with: 3, the real answer is: 3
the classifier came back with: 2, the real answer is: 2
the classifier came back with: 1, the real answer is: 1
the classifier came back with: 3, the real answer is: 1
the total error rate is: 0.050000
所以我們看到，數(shù)據(jù)集的錯誤率是5%，這里會有一定的偏差，因為我們隨機選取的數(shù)據(jù)可能會不同。
使用算法
我們使用上面建立好的分類器構(gòu)建一個可用的系統(tǒng)，通過輸入這些特征值幫她預(yù)測喜歡程度。我們來編寫代碼：
def classifyPerson() :
    resultList = ['not', 'small doses', 'large does']
    percentTats = float(raw_input("percent of time spent on video games?"))
    miles = float(raw_input("flier miles per year?"))
    ice = float(raw_input("liters of ice-cream?"))

    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)

    inArr = array([miles, percentTats, ice])
    classifierResult = classify0((inArr - minVals) / ranges, normMat, datingLabels, 3)
    print "you will like this person: ", resultList[classifierResult - 1]
這里的代碼大家比較熟悉了，就是加入了raw_input用于輸入，我們來看結(jié)果：
>>> reload(kNN)
<module 'kNN' from 'kNN.py'>
>>> kNN.classifyPerson()
percent of time spent on video games?10
flier miles per year?10000
liters of ice-cream?0.5
you will like this person:  small doses
我們在做近鄰算法的時候也發(fā)現(xiàn)，并沒有做 訓(xùn)練算法 這一環(huán)節(jié)，因為我們不需要訓(xùn)練，直接計算就好了。
同時我們也發(fā)現(xiàn)一個問題，k-近鄰算法特別慢，它需要對每一個向量進行距離的計算，這該怎么優(yōu)化呢？