機(jī)器學(xué)習(xí)實(shí)戰(zhàn)――K近鄰算法

本博客基于機(jī)器學(xué)習(xí)實(shí)戰(zhàn)這本書，主要是對(duì)機(jī)器學(xué)習(xí)的算法原理及Python實(shí)現(xiàn)進(jìn)行詳細(xì)解釋，若是有些沒(méi)有闡述清楚的，看到的請(qǐng)指出。

第二章的K近鄰算法是一個(gè)簡(jiǎn)單的機(jī)器學(xué)習(xí)算法。

K近鄰算法：

原理：收集一個(gè)樣本數(shù)據(jù)集合，并且樣本集中每個(gè)數(shù)據(jù)都存在標(biāo)簽。輸入沒(méi)有標(biāo)簽的新數(shù)據(jù)后，將新數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)對(duì)應(yīng)的特征進(jìn)行比較，然后算法提取樣本集中特征最相似數(shù)據(jù)(最近鄰)的分類標(biāo)簽。選擇樣本數(shù)據(jù)集中前K個(gè)最相似的數(shù)據(jù)，這就是K近鄰算法中K的出處，通常k是不大于20的整數(shù)。選擇k個(gè)最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類，作為新數(shù)據(jù)的分類。

算法實(shí)現(xiàn)：新建一個(gè)kNN.py文件

1. 導(dǎo)入數(shù)據(jù)

#-*- coding: utf-8 -*- #表示使用這個(gè)編碼

from numpy import * #導(dǎo)入科學(xué)計(jì)算包NumPy，沒(méi)安裝趕緊百度安裝

import operator #運(yùn)算符模塊，k近鄰算法執(zhí)行排序操作時(shí)將使用這個(gè)模塊提供的函數(shù)

import pdb #在Python交互環(huán)境中啟用調(diào)試

from os import listdir # os 模塊包含了許多對(duì)目錄操作的函數(shù) listdir 函數(shù)返回給定目錄下的所有文件

def createDataSet():#定義一個(gè)函數(shù)，創(chuàng)建數(shù)據(jù)集和標(biāo)簽

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

labels = ['A','A','B','B']

return group,labels

保存后import kNN

group,labels = kNN.createDataSet()，然后就可以得到group，labels

具體的kNN算法：

思想：計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)和當(dāng)前點(diǎn)之間的距離;

按照距離遞增次序排序;

選取與當(dāng)前點(diǎn)距離最小的k個(gè)點(diǎn);

確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率;

返回前k個(gè)點(diǎn)出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測(cè)分類。

def classify0(inX,dataSet,labels,k):#inX是測(cè)試向量，dataSet是樣本向量，labels是樣本標(biāo)簽向量，k用于選擇最近鄰居的數(shù)目

dataSetSize = dataSet.shape[0] #得到數(shù)組的行數(shù)。即知道有幾個(gè)訓(xùn)練數(shù)據(jù)，0是行，1是列

diffMat = tile(inX,(dataSetSize,1)) - dataSet #tile將原來(lái)的一個(gè)數(shù)組，擴(kuò)充成了dataSetSize個(gè)一樣的數(shù)組。diffMat得到了目標(biāo)與訓(xùn)練數(shù)值之間的差值。

sqDiffMat = diffMat**2 #各個(gè)元素分別平方

sqDistances = sqDiffMat.sum(axis=1) #就是一行中的元素相加

distances = sqDistances**0.5#開(kāi)平方，以上是求出測(cè)試向量到樣本向量每一行向量的距離

sortedDistIndicies = distances.argsort()#對(duì)距離進(jìn)行排序，從小到大

classCount={}#構(gòu)造一個(gè)字典，針對(duì)前k個(gè)近鄰的標(biāo)簽進(jìn)行分類計(jì)數(shù)。

for i in range(k):

voteIlabel = labels[sortedDistIndicies[i]]

classCount[voteIlabel] = classCount.get(voteIlabel,0)+1#得到距離最小的前k個(gè)點(diǎn)的分類標(biāo)簽

sortedClassCount = sorted(classCount.iteritems(),key = operator.itemgetter(1),reverse = True)#對(duì)classCount字典分解為元素列表，使用itemgetter方法按照第二個(gè)元素的次序?qū)υM進(jìn)行排序，返回頻率最高的元素標(biāo)簽，計(jì)數(shù)前k個(gè)標(biāo)簽的分類，返回頻率最高的那個(gè)標(biāo)簽

return sortedClassCount[0][0]

這樣就可以使用該程序進(jìn)行數(shù)據(jù)預(yù)測(cè)了。

kNN.classify0([0,0],group,labels,3)輸出結(jié)果為B。

測(cè)試kNN算法

這個(gè)測(cè)試是作者提供的文本文件，先解析文本，畫二維擴(kuò)散圖，kNN不用進(jìn)行訓(xùn)練，直接調(diào)用文本數(shù)據(jù)計(jì)算k近鄰就可以。

將文本記錄轉(zhuǎn)換為NumPy的解析程序

def file2matrix(filename):#將文本記錄轉(zhuǎn)換成numpy的解析程序

fr = open(filename) #這是python打開(kāi)文件的方式

arrayOLines = fr.readlines()#自動(dòng)將文件內(nèi)容分析成一個(gè)行的列表

numberOfLines = len(arrayOLines)#得到文件的行數(shù)

returnMat = zeros((numberOfLines,3))

classLabelVector = []

enumLabelVector = []

index = 0

for line in arrayOLines:

line = line.strip()#截掉所有的回車符

listFromLine = line.split('t')#使用tab字符t將上一步得到的整行數(shù)據(jù)分割成元素列表

returnMat[index,:] = listFromLine[0:3]#選取前三個(gè)元素存儲(chǔ)到特征矩陣中

classLabelVector.append(listFromLine[-1])#用-1表示最后一列元素，把標(biāo)簽放入這個(gè)向量中

if cmp(listFromLine[-1],'didntLike')==0:

enumLabelVector.append(1)

elif cmp(listFromLine[-1],'smallDoses')==0:

enumLabelVector.append(2)

elif cmp(listFromLine[-1],'largeDoses')==0:

enumLabelVector.append(3)

index += 1

return returnMat,enumLabelVector #返回?cái)?shù)據(jù)矩陣和標(biāo)簽向量

可以使用reload(kNN)

datingDataMat,datingLabels = kNN.file2matrix(‘datingTestSet.txt’)得到數(shù)據(jù)矩陣和標(biāo)簽向量。

使用Matplotlib制作原始數(shù)據(jù)的散點(diǎn)圖

fig = plt.figure()

ax = fig.add_subplot(131)

ax.scatter(datingDataMat[:,1],datingDataMat[:,2])

ax = fig.add_subplot(132)

ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(vector),15.0*array(vector))

ax = fig.add_subplot(133)

ax.scatter(datingDataMat[:,0],datingDataMat[:,1],15.0*array(vector),15.0*array(vector))

plt.show()

在計(jì)算KNN距離時(shí)，若某一列的數(shù)值遠(yuǎn)大于其他列， 那這一列對(duì)計(jì)算距離時(shí)的影響最大。將數(shù)據(jù)歸一化，每一列的數(shù)據(jù)取值范圍處理為0-1之間，這樣每一列的數(shù)據(jù)對(duì)結(jié)果影響都一樣。

歸一化特征值：

def autoNorm(dataSet):

minVals = dataSet.min(0)#獲得最小值，(0)是從列中獲取最小值，而不是當(dāng)前行，就是每列都取一個(gè)最小值

maxVals = dataSet.max(0)#獲得最大值

ranges = maxVals - minVals#獲得取值范圍

normDataSet = zeros(shape(dataSet))#初始化新矩陣

m = dataSet.shape[0]#獲得列的長(zhǎng)度

normDataSet = dataSet - tile(minVals,(m,1))#特征值是1000×3,而最小值和范圍都是1×3,用tile函數(shù)將變量?jī)?nèi)容復(fù)制成輸入矩陣一樣大小的矩陣

normDataSet = normDataSet/tile(ranges,(m,1))#/可能是除法，在numpy中，矩陣除法要用linalg.solve(matA,matB).

return normDataSet,ranges,minVals

將數(shù)據(jù)集分為測(cè)試數(shù)據(jù)和樣本數(shù)據(jù)

def datingClassTest():

hoRatio = 0.10

datingDataMat,datingLabels = file2matrix('datingTestSet.txt')#讀取文件中的數(shù)據(jù)并歸一化

normMat,ranges,minVals = autoNorm(datingDataMat)

m = normMat.shape[0]#新矩陣列的長(zhǎng)度

numTestVecs = int(m*hoRatio)#代表樣本中哪些數(shù)據(jù)用于測(cè)試

errorCount = 0.0#錯(cuò)誤率

for i in range(numTestVecs):

classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)#前m×hoRatio個(gè)數(shù)據(jù)是測(cè)試的，后面的是樣本

print the calssifier 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))#最后打印出測(cè)試錯(cuò)誤率

構(gòu)建預(yù)測(cè)函數(shù)，輸入信息得到預(yù)測(cè)標(biāo)簽

#輸入某人的信息，便得出對(duì)對(duì)方喜歡程度的預(yù)測(cè)值

def classifyPerson():

resultList = ['not at all', 'in small doses', 'in large doses']

percentTats = float(raw_input(percentage of time spent playing video games?))#輸入

ffMiles = float(raw_input(frequent flier miles earned per year?))

iceCream = float(raw_input(liters of ice cream consumed per year?))

datingDataMat, datingLabels = file2matrix('datingTestSet.txt') #讀入樣本文件，其實(shí)不算是樣本，是一個(gè)標(biāo)準(zhǔn)文件

normMat, ranges, minVals = autoNorm(datingDataMat)#歸一化

inArr = array([ffMiles, percentTats, iceCream])#組成測(cè)試向量

# pdb.set_trace()#可debug

classifierResult = classify0((inArr-minVals)/ranges, normMat, datingLabels,3)#進(jìn)行分類

# return test_vec_g,normMat,datingLabels

print 'You will probably like this person:', resultList[classifierResult - 1]#打印結(jié)果

在python下輸入kNN.classifyPerson()，輸入某人的信息，就可以得到該人的標(biāo)簽。

8.手寫識(shí)別系統(tǒng)的示例：

收集數(shù)據(jù)時(shí)，要將手寫的字符圖像轉(zhuǎn)換成向量。

def img2vector(filename):

returnVect = zeros((1,1024))#初始化一個(gè)向量

fr = open(filename)#打開(kāi)文件

for i in range(32):

lineStr = fr.readline()#讀入每行向量

for j in range(32):

returnVect[0,32*i+j] = int(lineStr[j])#把每行的向量分別賦值給初始化向量

return returnVect#返回向量

將數(shù)據(jù)處理成分類器可以識(shí)別的格式后，將這些數(shù)據(jù)輸入到分類器，檢測(cè)分類器的執(zhí)行效果。

def handwritingClassTest():

hwLabels = []

trainingFileList = listdir('trainingDigits')# 得到目錄下所有文件的文件名

m = len(trainingFileList)#得到目錄下文件個(gè)數(shù)

trainingMat = zeros((m,1024))

for i in range(m):

fileNameStr = trainingFileList[i]#對(duì)文件名進(jìn)行分解可以得到文件指的數(shù)字

fileStr = fileNameStr.split('.')[0]

classNumStr = int(fileStr.split('_')[0])

hwLabels.append(classNumStr)#把標(biāo)簽添加進(jìn)list

trainingMat[i,:] = img2vector('trainingDigits/%s' %fileNameStr)#把所有文件都放在一個(gè)矩陣?yán)锩?/p>

testFileList = listdir('testDigits')

errorCount = 0.0

mTest = len(testFileList)

for i in range(mTest):

fileNameStr = testFileList[i]

fileStr = fileNameStr.split('.')[0]

classNumStr = int(fileStr.split('_')[0])

vectorUnderTest = img2vector('testDigits/%s' %fileNameStr)#得到一個(gè)向量

classifierResult = classify0(vectorUnderTest,trainingMat,hwLabels,3)#對(duì)向量進(jìn)行k近鄰測(cè)試

print the classifier came back with: %d the real answer is %d %(classifierResult,classNumStr)

if(classifierResult != classNumStr):errorCount += 1.0

print nthe total number of errors is: %d %errorCount#得到錯(cuò)誤率

print nthe total error rate is: %f %(errorCount/float(mTest))

使用kNN.handwritingClassTest()測(cè)試該函數(shù)的輸出結(jié)果，依次測(cè)試每個(gè)文件，輸出結(jié)果，計(jì)算錯(cuò)誤率，因?yàn)榉诸愃惴ú皇墙^對(duì)的，只是一個(gè)概率問(wèn)題，所以對(duì)每一組數(shù)據(jù)都有錯(cuò)誤率。

至此，第二章基本闡述完畢，k近鄰算法是分類數(shù)據(jù)最簡(jiǎn)單有效的算法，使用算法時(shí)，我們必須有接近實(shí)際數(shù)據(jù)的訓(xùn)練樣本數(shù)據(jù)。k近鄰算法必須保存全部數(shù)據(jù)集，如果訓(xùn)練數(shù)據(jù)集很大的話，必須使用大量的存儲(chǔ)空間。

優(yōu)點(diǎn)：精度高，對(duì)異常值不敏感，無(wú)數(shù)據(jù)輸入假定

缺點(diǎn)：nisan復(fù)雜度高，空間復(fù)雜度高。

適用數(shù)據(jù)范圍：數(shù)值型和標(biāo)稱型。