第 2 章 k-近鄰算法
[TOC]
本章內(nèi)容：
- k-近鄰分類算法
- 從文本文件中解析和導(dǎo)入數(shù)據(jù)
- 使用 Matplotlib 創(chuàng)建擴(kuò)散圖
- 歸一化數(shù)值
1. k-近鄰算法概述
簡單地說当辐，k-近鄰算法 采用測量不同特征值之間的距離方法進(jìn)行分類懦铺。
- 優(yōu)點：精度高、對異常值部敏感、無數(shù)據(jù)輸入假定
- 缺點：計算復(fù)雜度高儡湾、空間復(fù)雜度高
- 適用數(shù)據(jù)范圍：數(shù)值型和標(biāo)稱型
k-近鄰算法（kNN）：它的工作原理是存在一個樣本數(shù)據(jù)集合（訓(xùn)練樣本集），并且樣本集中每個數(shù)據(jù)都存在標(biāo)簽，即我們知道樣本集中每一數(shù)據(jù)域所屬分類的對應(yīng)關(guān)系。輸入每一標(biāo)簽的新數(shù)據(jù)后谤民，將新數(shù)據(jù)的每個特征與樣本集中數(shù)據(jù)對應(yīng)的特征進(jìn)行比較，然后算法提取樣本集中特征最相似數(shù)據(jù)（最近鄰）的分類標(biāo)簽疾宏。一般來說张足，我們只選擇樣本數(shù)據(jù)集中前 k 個最相似的數(shù)據(jù)，這就是 k-近鄰算法中 k 的出處坎藐，通常 k 是不大于 20 的整數(shù)为牍。最后，選擇 k 個最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類岩馍，作為新數(shù)據(jù)的分類碉咆。
示例：基于電影中出現(xiàn)的親吻、打斗出現(xiàn)的次數(shù)蛀恩，使用 k-近鄰算法構(gòu)造程序疫铜，自動劃分電影的題材類型。有人統(tǒng)計過很多電影的打斗鏡頭和接吻鏡頭双谆，圖2-1 顯示了 6 部電影的打斗和接吻鏡頭數(shù)块攒。假如有一部未看過的電影励稳，如何確定的它是愛情片還是動作片呢？可以使用 kNN 來解決這個問題：
首先我們需要知道這個未知電影存在多少個打斗鏡頭和接吻鏡頭囱井，圖2-1 問號位置是該未知電影出現(xiàn)的鏡頭數(shù)圖形化展示，具體數(shù)字參見表2-1：
計算未知電影與樣本集中其他電影的距離趣避，如表2-2 所示：
現(xiàn)在得到了樣本集中所有電影與未知電影的距離庞呕，按照距離遞增排序，可以找到 k 個距離最近的電影程帕。假定 k=3 住练，則三個最近的電影依次是He...、Bea...愁拭、Cal...讲逛。k-近鄰算法按照距離最近的三部電影的類型，決定未知電影的類型岭埠，而這三部電影都是愛情片盏混，因此判定未知電影是愛情片。
k-近鄰算法的一般流程：
- 收集數(shù)據(jù)：可以使用任何方法惜论；
- 準(zhǔn)備數(shù)據(jù)：距離計算所需要的數(shù)值许赃，最好是結(jié)構(gòu)化的數(shù)據(jù)格式；
- 分析數(shù)據(jù)：可以使用任何方法馆类；
- 訓(xùn)練算法：此步驟不適用于 k-近鄰算法混聊；
- 測試算法：計算錯誤率；
- 使用算法：首先需要輸入樣本數(shù)據(jù)和結(jié)構(gòu)化的輸出結(jié)果乾巧，然后運行 k-近鄰算法判定輸入數(shù)據(jù)分別屬于哪個分類句喜，最后應(yīng)用對計算出的分類執(zhí)行后續(xù)的處理。
1.1 準(zhǔn)備：使用 Python 導(dǎo)入數(shù)據(jù)
s_1_kNN.py文件（創(chuàng)建數(shù)據(jù)集和標(biāo)簽）：
import numpy as np
import operator
def createDataSet():
group = np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
print(group)
labels = ['A','A','B','B']
print(labels)
return group, labels
圖2-2 是帶有類標(biāo)簽信息的四個數(shù)據(jù)點：
現(xiàn)在我們已經(jīng)知道 Python 如何解析數(shù)據(jù)沟于，如何加載數(shù)據(jù)咳胃，以及 kNN 算法的工作原理，接下來將使用這些方法完成分類任務(wù)社裆。
1.2 從文本文件中解析數(shù)據(jù)
本節(jié)使用程序中的 classify0() 函數(shù)運行 kNN 算法拙绊，為每組數(shù)據(jù)分類。該函數(shù)的功能是使用 k-近鄰算法將每組數(shù)據(jù)劃分到某個類中泳秀，其偽代碼如下：
對未知類別屬性的數(shù)據(jù)集中的每個點依次執(zhí)行以下的操作：
- 計算已知類別數(shù)據(jù)集中的點與當(dāng)前點之間的距離
- 按照距離遞增次序排序
- 選取與當(dāng)前點距離最小的 k 個點
- 確定前 k 個點所在類別的出現(xiàn)頻率
- 返回前 k 個點出現(xiàn)頻率最高的類別作為當(dāng)前點的預(yù)測分類
classify0() 如下：
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0] # dataSet 的長度
diffMat = np.tile(inX, (dataSetSize,1)) - dataSet # 分別求出 測試數(shù)據(jù)的向量減去訓(xùn)練數(shù)據(jù)的向量
sqDiffMat = diffMat ** 2 # 求平方
sqDistances = sqDiffMat.sum(axis=1) # 求和
distances = sqDistances ** 0.5 # 求出距離
sortedDistIndicies = np.argsort(distances) # 升序的索引值
classCount = {} # 記錄近鄰標(biāo)簽
for i in range(k):
voteilabel = labels[sortedDistIndicies[i]] # 近鄰標(biāo)簽值
classCount[voteilabel] = classCount.get(voteilabel,0) + 1 # 記錄近鄰標(biāo)簽值得數(shù)量
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) # 按近鄰標(biāo)簽數(shù)量排序
return sortedClassCount[0][0]
classify0() 護(hù)士中有 4 個輸入?yún)?shù)：用于分類的輸入向量是 inX标沪，輸入訓(xùn)練樣本集是 dataSet，標(biāo)簽向量是 labels嗜傅，最后的參數(shù) k 表示用于選擇最近鄰居的數(shù)目金句，其中標(biāo)簽向量的元素數(shù)目和矩陣 dataSet 的行數(shù)相同。通過使用歐式距離公式吕嘀，計算兩個向量點 xA 和 xB 之間的距離：
計算完所有點之間的距離后违寞，可以對數(shù)據(jù)按照從小到大的次序排序贞瞒。然后確定前 k 個距離最小元素所在的主要分類，輸入 k 總是正整數(shù)趁曼；最后军浆，將 classCount 字典分解為元組列表，然后使用工程需第二行導(dǎo)入運算符模塊的 itemgetter 方法挡闰，按照第二個元素的次序?qū)υM進(jìn)行排序乒融。此處的排序為逆序，即按照從最大到最小次序排序摄悯，最后返回發(fā)生頻率最高的元素標(biāo)簽赞季。
進(jìn)行預(yù)測：
group, labels = createDataSet()
result = classify0([0.4,0.2], group, labels, 3)
print(result) # B
1.3 如何測試分類器
通過大量的測試數(shù)據(jù)，我們可以得到分類器的 錯誤率 ：分類器給出錯誤結(jié)果的次數(shù)除以測試執(zhí)行的總數(shù)奢驯。錯誤率是常用的評估方法申钩，主要用于評估分類器在某個數(shù)據(jù)集上的執(zhí)行效果
2. 示例：使用 k-近鄰算法改進(jìn)約會網(wǎng)站的配對效果
將約會網(wǎng)站上的人選進(jìn)行分類：不喜歡的人、魅力一般的人瘪阁、極具魅力的人
示例：在約會網(wǎng)站上使用 k-近鄰算法：
- 收集數(shù)據(jù)：提供文本文件
- 準(zhǔn)備數(shù)據(jù)：使用 pyhton 解析文本文件
- 分析數(shù)據(jù)：使用 Matplotlib 畫二維擴(kuò)散圖
- 訓(xùn)練算法：使用部分?jǐn)?shù)據(jù)作為測試樣本撒遣。測試樣本和非測試樣本的區(qū)別在于：測試樣本是一件完成分類的數(shù)據(jù)，如果預(yù)測分類與實際類別不同罗洗，則標(biāo)記為一個錯誤
- 使用算法：產(chǎn)生簡單的命令行程序愉舔，然后可以輸入一些特征數(shù)據(jù)以判斷對方是否為自己喜歡的類型
2.1 準(zhǔn)備數(shù)據(jù)：從文本文件中解析數(shù)據(jù)
樣本主要包含以下3種特征：
- 每年獲得的飛行常客里程數(shù)
- 玩視頻游戲所耗時間百分比
- 每周消費的冰淇淋公升數(shù)
在將特征數(shù)據(jù)輸入到分類器之前伙菜，必須將待處理數(shù)據(jù)的格式改變?yōu)榉诸惼骺山邮艿母袷健?/p>
file2matrix 函數(shù)用來處理輸入數(shù)據(jù)的格式轩缤。該函數(shù)的輸入為文本文件名字符串，輸出為訓(xùn)練樣本矩陣和類標(biāo)簽向量贩绕。
def file2matrix(filename):
fr = open(filename)
arrayOLines = fr.readlines() # 讀取文件
numberOfLines = len(arrayOLines) # 行數(shù)
returnMat = np.zeros((numberOfLines,3)) # 特征矩陣
classLabelVector = [] # 標(biāo)簽值
index = 0
for line in arrayOLines: # 解析文件數(shù)據(jù)到列表
line = line.strip()
listFromLine = line.split('\t') # 分割
returnMat[index,:] = listFromLine[0:3]
classLabelVector.append(int(listFromLine[-1]))
index += 1
return returnMat,classLabelVector
2.2 分析數(shù)據(jù)：使用 Matplotlib 創(chuàng)建散點圖
scatter 函數(shù)支持個性化標(biāo)記散點圖上的點
filename = 'datingTestSet2.txt'
datingDataMat, datingLabels = file2matrix(filename)
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0 * np.array(datingLabels),15.0 * np.array(datingLabels))
plt.show()
2.3 準(zhǔn)備數(shù)據(jù)：歸一化數(shù)值
在處理不同取值范圍的特征值時火的，通常采用的方法是將數(shù)值歸一化，如將取值范圍處理為 0 到 1 或者 -1 到 1 之間淑倾。下面的公式可以將任意取值范圍的特征值轉(zhuǎn)化為 0 到 1 區(qū)間內(nèi)的值：
? newValue = (oldValue - min) / (max - min)
其中 min 和 max 分別是數(shù)據(jù)集中的最小特征值和最大特征值馏鹤。
添加 autoNorm 函數(shù)，來自動將數(shù)字特征值轉(zhuǎn)化為 0 到 1 的區(qū)間：
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals # 差值
normDataSet = np.zeros(np.shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - np.tile(minVals, (m,1)) # 數(shù)據(jù) - 最小值
normDataSet = normDataSet / np.tile(ranges, (m,1)) # 上面的值 / 最小值
# normDataSet = np.linalg.solve(normDataSet,np.tile(ranges, (m,1)))
return normDataSet,ranges,minVals
2.4 測試算法：作為完整程序驗證分類器
添加 ditingClassTest 函數(shù)：
def datingClassTest():
hoRatio = 0.10
filename = 'datingTestSet2.txt'
datingDataMat, datingLabels = file2matrix(filename)
normMat, ranges, minVals = autoNorm(datingDataMat)
m = normMat.shape[0]
numTestVecs = int(m*hoRatio)
errorCount = 0.0
for i in range(numTestVecs):
classifierResult = classify0(normMat[i,:], normMat[numTestVecs:m,:],datingLabels[numTestVecs:m], 3)
print("classifierResult:" , classifierResult)
print('datingLabels[i]:',datingLabels[i])
if(classifierResult != datingLabels[i]):
errorCount += 1.0
print('the total error rate is: %f' % (errorCount / float(numTestVecs)))
可以改變函數(shù) datingClassTest 內(nèi)變量 hoRatio 和變量 k 的值娇哆，檢測錯誤率是否隨著變量值得變化而增加湃累。依賴于分類算法、數(shù)據(jù)集和程序設(shè)置碍讨，分類器的輸出結(jié)果可能有很大的不同治力。
2.5 使用算法：構(gòu)建完整可用系統(tǒng)
添加 classifyPerson 函數(shù)，來輸入個人信息勃黍，判斷分類：
def classifyPerson():
resultList = ['not at all', 'in small doses', 'in large doses']
percenTats = float(input('percentage of time spent playing video games?'))
ffMiles = float(input('freguent flier miles earned per year?'))
iceCream = float(input('liters of ice cream consumed per year?'))
filename = 'datingTestSet2.txt'
datingDataMat, datingLabels = file2matrix(filename)
normMat, ranges, minVals = autoNorm(datingDataMat)
inArr = np.array([ffMiles, percenTats, iceCream])
classifierResult = classify0((inArr - minVals) / ranges,normMat, datingLabels, 3)
print('you will probably like this person:',resultList[classifierResult - 1])
3. 示例：手寫識別系統(tǒng)
示例說明：構(gòu)造使用 k-近鄰分類器的手寫識別系統(tǒng)宵统，來識別數(shù)字 0 到 9.需要識別的數(shù)字已經(jīng)使用圖形處理軟件，處理成具有相同的色彩和大小的黑白圖像覆获。
示例：使用 k-近鄰算法的手寫識別系統(tǒng)
- 收集數(shù)據(jù)：提供文本文件马澈；
- 準(zhǔn)備數(shù)據(jù)：編寫函數(shù) classify()瓢省，將圖像格式轉(zhuǎn)換為分類器使用的 list 格式；
- 分析數(shù)據(jù)：在 python 命令提示符中檢查數(shù)據(jù)痊班，確保它符合要求勤婚；
- 訓(xùn)練算法：此步驟不適用 k-近鄰算法；
- 測試算法：編寫函數(shù)使用提供的部分?jǐn)?shù)據(jù)集作為測試樣本辩块，測試樣本與非測試樣本的區(qū)別在于測試樣本是已經(jīng)完成分類的數(shù)據(jù)蛔六，如果預(yù)測分類與實際類別不同，則標(biāo)記為一個錯誤废亭；
- 使用算法：本例沒有完成此步驟。
3.1 準(zhǔn)備數(shù)據(jù)：將圖像轉(zhuǎn)換為測試向量
添加 img2vector 函數(shù)具钥，將圖像轉(zhuǎn)換為向量：該函數(shù)創(chuàng)建 1 X 1024 的 numpy 數(shù)組豆村，然后打開給定的文件，循環(huán)獨處文件的前 32 行骂删，并將每行的頭 32 個字符值存儲在 numpy 數(shù)組中掌动，最后返回數(shù)組：
def img2vector(filename):
returnVect = np.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
3.2 測試算法：使用 k-近鄰算法識別手寫數(shù)字
添加 handwritingClassTest 函數(shù)，來測試分類器：
def handwritingClassTest():
hwLabels = []
trainingFileList = listdir('trainingDigits')
m = len(trainingFileList)
trainingMat = np.zeros((m,1024))
# 訓(xùn)練
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0]
classNumStr = int(fileStr.split('_')[0])
hwLabels.append(classNumStr) # 訓(xùn)練集標(biāo)簽
trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr) # 訓(xùn)練集
# 測試
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]) # 實際標(biāo)簽
vectorUnderTest = img2vector('testDigits/%s' % fileNameStr) # 測試集
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) # 預(yù)測標(biāo)簽
print('classifierResult:',classifierResult)
print('classNumStr:',classNumStr)
if(classifierResult != classNumStr):
errorCount += 1.0
print('errorCount:',errorCount)
print('rate:',errorCount/float(mTest))
改變變量 k 的值宁玫、修改函數(shù) handwritingClassTest 隨機(jī)選取訓(xùn)練樣本粗恢、改變訓(xùn)練樣本的數(shù)目，都會對 k-近鄰算法的錯誤率產(chǎn)生影響欧瘪。
4. 本章小結(jié)
k-近鄰算法是分類數(shù)據(jù)最簡單最有效的算法眷射。k-近鄰算法是基于實例的學(xué)習(xí)，使用算法時我們必須有接近實際數(shù)據(jù)上的訓(xùn)練樣本數(shù)據(jù)佛掖。k-近鄰算法必須保存全部數(shù)據(jù)集妖碉，如果訓(xùn)練數(shù)據(jù)集很大，必須使用大量的存儲空間芥被。此外欧宜，由于必須對數(shù)據(jù)集中的每個數(shù)據(jù)計算距離值，實際使用時可能非常耗時拴魄。
另一個缺陷是它無法給出任何數(shù)據(jù)的基礎(chǔ)結(jié)構(gòu)信息冗茸，因此我們也無法知曉平均實例樣本具有什么特征。
- 機(jī)器學(xué)習(xí)實戰(zhàn)（筆記）：第 1 章 機(jī)器學(xué)習(xí)基礎(chǔ)
- 機(jī)器學(xué)習(xí)實戰(zhàn)（筆記）：第 2 章 k-近鄰算法
- 機(jī)器學(xué)習(xí)實戰(zhàn)（筆記）：第 3 章 決策樹
- 機(jī)器學(xué)習(xí)實戰(zhàn)（筆記）：第 4 章 基于概率論的分類方法：樸素貝葉斯
- 機(jī)器學(xué)習(xí)實戰(zhàn)（筆記）：第 5 章 Logistic 回歸
- 機(jī)器學(xué)習(xí)實戰(zhàn)（筆記）：第 6 章 支持向量機(jī)（未完）
- 機(jī)器學(xué)習(xí)實戰(zhàn)（筆記）：第 7 章 利用 AdaBoost 元算法提高分類性能（未完）
- 機(jī)器學(xué)習(xí)實戰(zhàn)（筆記）：第 8 章 預(yù)測數(shù)值型數(shù)據(jù)：回歸
