機器學習實戰(zhàn)――K近鄰算法

本博客基于機器學習實戰(zhàn)這本書，主要是對機器學習的算法原理及Python實現(xiàn)進行詳細解釋，若是有些沒有闡述清楚的，看到的請指出。

第二章的K近鄰算法是一個簡單的機器學習算法。

K近鄰算法：

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

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

1. 導入數(shù)據(jù)

#-*- coding: utf-8 -*- #表示使用這個編碼

from numpy import * #導入科學計算包NumPy，沒安裝趕緊百度安裝

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

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

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

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

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

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

按照距離遞增次序排序;

選取與當前點距離最小的k個點;

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

返回前k個點出現(xiàn)頻率最高的類別作為當前點的預測分類。

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

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

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

sqDiffMat = diffMat**2 #各個元素分別平方

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

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

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

classCount={}#構造一個字典，針對前k個近鄰的標簽進行分類計數(shù)。

for i in range(k):

voteIlabel = labels[sortedDistIndicies[i]]

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

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

return sortedClassCount[0][0]

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

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

測試kNN算法

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

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

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

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

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

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]#選取前三個元素存儲到特征矩陣中

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

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 #返回數(shù)據(jù)矩陣和標簽向量

可以使用reload(kNN)

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

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

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ù)據(jù)歸一化，每一列的數(shù)據(jù)取值范圍處理為0-1之間，這樣每一列的數(shù)據(jù)對結果影響都一樣。

歸一化特征值：

def autoNorm(dataSet):

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

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

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

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

m = dataSet.shape[0]#獲得列的長度

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

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

return normDataSet,ranges,minVals

將數(shù)據(jù)集分為測試數(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]#新矩陣列的長度

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

errorCount = 0.0#錯誤率

for i in range(numTestVecs):

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

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

構建預測函數(shù)，輸入信息得到預測標簽

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

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') #讀入樣本文件，其實不算是樣本，是一個標準文件

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

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

# pdb.set_trace()#可debug

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

# return test_vec_g,normMat,datingLabels

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

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

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

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

def img2vector(filename):

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

fr = open(filename)#打開文件

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ù)據(jù)輸入到分類器，檢測分類器的執(zhí)行效果。

def handwritingClassTest():

hwLabels = []

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

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

trainingMat = zeros((m,1024))

for i in range(m):

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

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

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

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

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

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)#得到一個向量

classifierResult = classify0(vectorUnderTest,trainingMat,hwLabels,3)#對向量進行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()測試該函數(shù)的輸出結果，依次測試每個文件，輸出結果，計算錯誤率，因為分類算法不是絕對的，只是一個概率問題，所以對每一組數(shù)據(jù)都有錯誤率。

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

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

缺點：nisan復雜度高，空間復雜度高。

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