機器學(xué)習實(shí)戰――K近鄰算法

本博客基于機器學(xué)習實(shí)戰這本書(shū)，主要是對機器學(xué)習的算法原理及Python實(shí)現進(jìn)行詳細解釋?zhuān)羰怯行](méi)有闡述清楚的，看到的請指出。

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

K近鄰算法：

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

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

1. 導入數據

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

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

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

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

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

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

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算法：

思想：計算已知類(lèi)別數據集中的點(diǎn)和當前點(diǎn)之間的距離;

按照距離遞增次序排序;

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

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

返回前k個(gè)點(diǎn)出現頻率最高的類(lèi)別作為當前點(diǎn)的預測分類(lèi)。

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

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

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

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

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

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

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

classCount={}#構造一個(gè)字典，針對前k個(gè)近鄰的標簽進(jìn)行分類(lèi)計數。

for i in range(k):

voteIlabel = labels[sortedDistIndicies[i]]

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

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

return sortedClassCount[0][0]

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

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

測試kNN算法

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

將文本記錄轉換為NumPy的解析程序

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

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

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

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

returnMat = zeros((numberOfLines,3))

classLabelVector = []

enumLabelVector = []

index = 0

for line in arrayOLines:

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

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

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

classLabelVector.append(listFromLine[-1])#用-1表示最后一列元素，把標簽放入這個(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 #返回數據矩陣和標簽向量

可以使用reload(kNN)

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

使用Matplotlib制作原始數據的散點(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()

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

歸一化特征值：

def autoNorm(dataSet):

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

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

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

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

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

normDataSet = dataSet - tile(minVals,(m,1))#特征值是1000×3,而最小值和范圍都是1×3,用tile函數將變量?jì)热輳椭瞥奢斎刖仃囈粯哟笮〉木仃?/p>

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

return normDataSet,ranges,minVals

將數據集分為測試數據和樣本數據

def datingClassTest():

hoRatio = 0.10

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

normMat,ranges,minVals = autoNorm(datingDataMat)

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

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

errorCount = 0.0#錯誤率

for i in range(numTestVecs):

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

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))#最后打印出測試錯誤率

構建預測函數，輸入信息得到預測標簽

#輸入某人的信息，便得出對對方喜歡程度的預測值

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è)標準文件

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

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

# pdb.set_trace()#可debug

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

# return test_vec_g,normMat,datingLabels

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

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

8.手寫(xiě)識別系統的示例：

收集數據時(shí)，要將手寫(xiě)的字符圖像轉換成向量。

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#返回向量

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

def handwritingClassTest():

hwLabels = []

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

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

trainingMat = zeros((m,1024))

for i in range(m):

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

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

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

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

trainingMat[i,:] = img2vector('trainingDigits/%s' %fileNameStr)#把所有文件都放在一個(gè)矩陣里面

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)#對向量進(jìn)行k近鄰測試

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#得到錯誤率

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

使用kNN.handwritingClassTest()測試該函數的輸出結果，依次測試每個(gè)文件，輸出結果，計算錯誤率，因為分類(lèi)算法不是絕對的，只是一個(gè)概率問(wèn)題，所以對每一組數據都有錯誤率。

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

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

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

適用數據范圍：數值型和標稱(chēng)型。