最近在看機(jī)器學(xué)習(xí)實(shí)戰(zhàn)這本書。剛開始看kNN算法，并寫了些程序，分享下一些感悟和細(xì)節(jié)。

什么是kNN

kNN中文又稱為k-近鄰算法，其基本思想是通過計(jì)算輸入樣本點(diǎn) 和 訓(xùn)練集樣本點(diǎn)之前的這兩個(gè)向量之前的距離，距離越近的話，說明其特征越靠近，通過取出其k個(gè)距離最近的樣本點(diǎn)，然后計(jì)算這k個(gè)樣本點(diǎn)中類別占比最大的類比以此來預(yù)測輸入樣本點(diǎn)(被測樣本點(diǎn))的類別。

kNN的優(yōu)勢

• kNN是ML里最簡單，最基本的算法。
• kNN不會(huì)受到差別特別大的樣本中的特征元素的影響(對異常值不敏感)。因?yàn)椴捎昧藲w一化技術(shù)
• kNN的精度高

kNN的劣勢

• kNN算法時(shí)間復(fù)雜度較高，需要計(jì)算被測樣本點(diǎn)和訓(xùn)練集中所有樣本點(diǎn)的距離

kNN算法的實(shí)現(xiàn)

from numpy import *
import operator
# 該分類器模型，只需要輸入向量， 訓(xùn)練數(shù)據(jù)集矩陣dataSet，每一行是一個(gè)樣本。labels(每一行的樣本標(biāo)簽)。k取前幾個(gè)
def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()     
    classCount={}          
    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]

• 這里的dataSet是numpy模塊里的數(shù)組(也可以看成矩陣)，不是python中內(nèi)置的數(shù)組，shape屬性會(huì)返回這個(gè)數(shù)組的緯度.(比如是2 * 3的二維數(shù)組，則會(huì)返回(2, 3)表示這是一個(gè)2緯數(shù)組，每個(gè)緯度的大小分別是2，3)
• tile函數(shù)用來創(chuàng)建矩陣，其中(dataSetSize， 1)表示沿著inX向量的行方向(inX是一個(gè)行向量)，賦值dataSetSize次，沿著列方向復(fù)制1次(既列不變)。
• diffMat矩陣計(jì)算出了各個(gè)向量之前的距離的平方值。其中2表示平方，0.5表示開平方

使用kNN來改進(jìn)婚戀網(wǎng)站的匹配

這里的數(shù)據(jù)集如下

image.png

datingTestSet.txt存放了該網(wǎng)站關(guān)于個(gè)人信息的集合。每一行代表一個(gè)人，一共有三個(gè)特征屬性，和一個(gè)標(biāo)簽屬性用來標(biāo)識(shí)是哪一類人。
datingTestSet2.txt 存放的是處理過的datingTestSet數(shù)據(jù)，將類別標(biāo)簽處理成數(shù)字

• 三個(gè)特征屬性分別是: 每年航班的行程公里數(shù)，玩游戲的時(shí)間所占的時(shí)間百分比，每周消費(fèi)的冰淇淋公升數(shù)
• 人一共分為三類(不喜歡的、魅力一般、極具魅力)

兩個(gè)文件的內(nèi)容如下

image.png

目的

現(xiàn)在的需求是，我們必須根據(jù)提供的數(shù)據(jù)，來準(zhǔn)確的劃分出這三類人。才能精確的從數(shù)據(jù)中挑選出的人是用戶感興趣的。

分析

• 根據(jù)之前總結(jié)的kNN分類器模型，我們需要將數(shù)據(jù)進(jìn)行處理。分別分離出訓(xùn)練數(shù)據(jù)集、測試數(shù)據(jù)集、數(shù)據(jù)集對應(yīng)的標(biāo)簽。其實(shí)最重要的是準(zhǔn)本和分析數(shù)據(jù)集，然后進(jìn)行建模，但是由于這里數(shù)據(jù)集已經(jīng)是現(xiàn)有的，直接用就行。
• 接著我們編寫測試程序，將測試數(shù)據(jù)集、訓(xùn)練數(shù)據(jù)集、標(biāo)簽丟入改模型進(jìn)行計(jì)算
• 統(tǒng)計(jì)識(shí)別的錯(cuò)誤率，如果錯(cuò)誤率很低。那基本上可以使用。如果錯(cuò)誤率高，那就要改進(jìn)數(shù)據(jù)集，進(jìn)行其他特征點(diǎn)的抽取。

步驟

處理數(shù)據(jù)(提取數(shù)據(jù)，歸一化)

改函數(shù)用來讀取訓(xùn)練集數(shù)據(jù)將其轉(zhuǎn)化為矩陣，并提取出標(biāo)簽集合。具體代碼看下面

from numpy import *
def file2matrix(filename):
    file = open(filename)
    arrayOfLines = file.readlines()
    numberOfLines = len(arrayOfLines)
    returnMat = zeros((numberOfLines,3))
    classLabelVector = []
    index = 0
    for line in arrayOfLines:
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))  # 這邊要十分小心，必須強(qiáng)制轉(zhuǎn)換為整形，不然編譯器會(huì)當(dāng)做字符串處理
        index += 1
    return returnMat, classLabelVector

將特征數(shù)據(jù)都歸一化
因?yàn)楹匠烫卣鞯臄?shù)字太大，對其他兩個(gè)影響太大，但是又不能忽略，為了減少這種影響。將數(shù)據(jù)進(jìn)行歸一行，既處理層0到1之前的小數(shù)。利用了如下原理
newValue = oldValue - minValue/(maxValue - minValue)

# 數(shù)據(jù)歸一化 newValue = oldValue - minValue/(maxValue - minValue)
def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normaMat = zeros(shape(dataSet))
    m = dataSet.shape[0]
    normaMat = dataSet - tile(minVals, (m, 1))
    normaMat = normaMat / tile(ranges, (m, 1))
    return normaMat, ranges, minVals

通過圖形分析數(shù)據(jù)

• (x軸為游戲時(shí)間占比，y軸為每周吃冰淇淋的公斤數(shù))

# 列2和列1的比較
datingDataMat,datingDataLabels = file2matrix('/Users/sixleaves/Dropbox/DeepLearning/machinelearninginaction/Ch02/datingTestSet2.txt')
print datingDataLabels
import matplotlib
import matplotlib.pyplot as plt
from numpy import *
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2], 15.0 * array(datingDataLabels), 15.0 * array(datingDataLabels))
plt.show()

image.png

• (x軸為航班占比，y軸為游戲時(shí)間耗時(shí)占比)

# 列2和列1的比較
datingDataMat,datingDataLabels = file2matrix('/Users/sixleaves/Dropbox/DeepLearning/machinelearninginaction/Ch02/datingTestSet2.txt')
print datingDataLabels
import matplotlib
import matplotlib.pyplot as plt
from numpy import *
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:, 0], datingDataMat[:, 1], 15.0 * array(datingDataLabels), 15.0 * array(datingDataLabels))
plt.show()

image.png

通過上面的分析，可以很明顯的發(fā)現(xiàn)，使用前兩個(gè)特征，我們就可以將這三類人比較精確的分離出來。但如果只使用第二個(gè)和第三個(gè)特征難以分離出該三類。

編寫測試用例，測試kNN分類器的效果

# 針對約會(huì)網(wǎng)站的測試代碼,測試分類器的效果
def datingClassTest():
    hoRatio = 0.10
    datingDataMat, datingDataLabels = file2matrix('/Users/sixleaves/Dropbox/DeepLearning/machinelearninginaction/Ch02/datingTestSet2.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]   # 獲取訓(xùn)練集行數(shù)
    numTestVecs = int(m * hoRatio)  # 取10%的行數(shù)作為測試集  
    errorCount = 0.0
    for i in range(numTestVecs):  
        classifierResult = classify0(normMat[i,:], normMat[numTestVecs:m,], datingDataLabels[numTestVecs:m], 3)  # 取從小到的前三個(gè)
        print "分類的結(jié)果是: %d, 目標(biāo)結(jié)果是: %d" % (int(classifierResult), int(datingDataLabels[i]))
        if (classifierResult != datingDataLabels[i]): errorCount += 1.0
    print "總的錯(cuò)誤率為: %f%%" %(errorCount / float(numTestVecs) * 100.0)

運(yùn)行datingClassTest()方法我們可以看到如下結(jié)果(其中1，2，3分別代表三類人的標(biāo)簽映射。)，改分類器的錯(cuò)誤率為5%，也就是說95%的情況下匹配都是準(zhǔn)確的，算是還不錯(cuò)的分類器。

image.png

使用KNN實(shí)現(xiàn)識(shí)別手寫數(shù)字

具體思路和上面的例子一樣。這邊有個(gè)比較不一樣的步驟是我們需要對圖片進(jìn)行處理，這里我們統(tǒng)一對圖片做了以下處理。

• 將圖片的大小處理層一樣的黑白圖。

• 對于每張圖片，我們使用 正確的對應(yīng)數(shù)字_樣本索引.txt來命名。(之所以處理成文本是為了在這里比較直觀)

  
  
  image.png
  
  
  image.png

分析

1.為了使用kNN模型，我們需要將圖片轉(zhuǎn)化為一個(gè)行向量。由于圖片大小事32*32，我們需要一個(gè)1024大小的行向量即可存儲(chǔ)。

from numpy import *
def img2vector(filename):
    fr = open(filename)
    returnVect = zeros((1, 1024))
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVec[0, 32 * i + j] = int(lineStr[j])
    return returnVect

2.使用kNN模型進(jìn)行測試

from os import listdir
from numpy import *
def handwritingClassTest():
# 遍歷訓(xùn)練數(shù)據(jù)集，將數(shù)據(jù)集裝載進(jìn)矩陣。
    trainingFilesPath = "/Users/sixleaves/Dropbox/DeepLearning/machinelearninginaction/Ch02/digits/trainingDigits/"
    arrayOfTrainingFiles = listdir(trainingFilesPath)
    m = len(arrayOfTrainingFiles)
    trainingMat = zeros((m, 1024))
    classLabels = []
    for i in range(m):
        fileNameStr = arrayOfTrainingFiles[i]
        fileStr = fileNameStr.split('.')[0]
        classNum = int(fileStr.split('_')[0])
        classLabels.append(classNum)
        trainingMat[i,:] = img2vector(trainingFilesPath + fileNameStr)
    
    testFilePath = "/Users/sixleaves/Dropbox/DeepLearning/machinelearninginaction/Ch02/digits/testDigits/"
    arrayOfTestFiles =  listdir(testFilePath)
    mTest = len(arrayOfTestFiles)
    errorCount = 0.0;
    for j in range(mTest):
        testFileNameStr = arrayOfTestFiles[j]
        testFile = testFileNameStr.split('.')[0]
        testNum = testFile.split('_')[0]
        testImageVec = img2vector(testFilePath + testFileNameStr)
        classifierResult = classify0(testImageVec, trainingMat, classLabels, 3)
        print "識(shí)別結(jié)果為: %d, 正確結(jié)果為: %d" % (int(classifierResult), int(testNum))
        if classifierResult != int(testNum): errorCount += 1.0
    print "識(shí)別錯(cuò)誤個(gè)數(shù)為: %d" % (int(errorCount))
    print "識(shí)別錯(cuò)誤率為: %f%%" % (errorCount / float(mTest) * 100.0)    

image.png

效果還是相當(dāng)不錯(cuò)，基本達(dá)到了99%識(shí)別效率

總結(jié):

• 一般機(jī)器學(xué)習(xí)解決問題需要以下步驟(準(zhǔn)備數(shù)據(jù)，分析數(shù)據(jù)，訓(xùn)練算法(kNN不適用，kNN無需訓(xùn)練)，測試算法，使用算法)。
• 對于kNN算法模型來說，分析數(shù)據(jù)過程由于重要，只有有價(jià)值的數(shù)據(jù)使用kNN才能有精確的結(jié)果。
• kNN算法比較簡單，穩(wěn)定。但是效率低。其思想主要是計(jì)算相似度(通過計(jì)算向量距離)，并使用概率來得出分類結(jié)果。

by sixleaves 20170726 FuZhou