第2章 k-近鄰算法
k-近鄰算法首頁
KNN 概述
k-近鄰（kNN, k-NearestNeighbor）算法主要是用來進行分類的.
KNN 場景
電影可以按照題材分類瑟曲，那么如何區(qū)分 動作片 和 愛情片 呢太防？
- 動作片：打斗次數(shù)更多
- 愛情片：親吻次數(shù)更多
基于電影中的親吻、打斗出現(xiàn)的次數(shù)，使用 k-近鄰算法構造程序虱咧，就可以自動劃分電影的題材類型叉庐。
電影按照題材分類
現(xiàn)在根據(jù)上面我們得到的樣本集中所有電影與未知電影的距離，按照距離遞增排序儿惫，可以找到 k 個距離最近的電影。
假定 k=3伸但，則三個最靠近的電影依次是肾请， He's Not Really into Dudes 、 Beautiful Woman 和 California Man更胖。
knn 算法按照距離最近的三部電影的類型铛铁，決定未知電影的類型，而這三部電影全是愛情片却妨，因此我們判定未知電影是愛情片饵逐。
KNN 原理
KNN 工作原理
- 假設有一個帶有標簽的樣本數(shù)據(jù)集（訓練樣本集），其中包含每條數(shù)據(jù)與所屬分類的對應關系彪标。
- 輸入沒有標簽的新數(shù)據(jù)后倍权，將新數(shù)據(jù)的每個特征與樣本集中數(shù)據(jù)對應的特征進行比較。
- 計算新數(shù)據(jù)與樣本數(shù)據(jù)集中每條數(shù)據(jù)的距離捞烟。
- 對求得的所有距離進行排序（從小到大薄声，越小表示越相似）当船。
- 取前 k （k 一般小于等于 20 ）個樣本數(shù)據(jù)對應的分類標簽。
- 求 k 個數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類標簽作為新數(shù)據(jù)的分類默辨。
KNN 開發(fā)流程
收集數(shù)據(jù)：任何方法
準備數(shù)據(jù)：距離計算所需要的數(shù)值德频，最好是結構化的數(shù)據(jù)格式
分析數(shù)據(jù)：任何方法
訓練算法：此步驟不適用于 k-近鄰算法
測試算法：計算錯誤率
使用算法：輸入樣本數(shù)據(jù)和結構化的輸出結果，然后運行 k-近鄰算法判斷輸入數(shù)據(jù)分類屬于哪個分類缩幸，最后對計算出的分類執(zhí)行后續(xù)處理
KNN 算法特點
優(yōu)點：精度高壹置、對異常值不敏感、無數(shù)據(jù)輸入假定
缺點：計算復雜度高表谊、空間復雜度高
適用數(shù)據(jù)范圍：數(shù)值型和標稱型
KNN 項目案例
項目案例1: 優(yōu)化約會網站的配對效果
項目概述
海倫使用約會網站尋找約會對象钞护。經過一段時間之后，她發(fā)現(xiàn)曾交往過三種類型的人:
- 不喜歡的人
- 魅力一般的人
- 極具魅力的人
她希望：
- 工作日與魅力一般的人約會
- 周末與極具魅力的人約會
- 不喜歡的人則直接排除掉
現(xiàn)在她收集到了一些約會網站未曾記錄的數(shù)據(jù)信息铃肯，這更有助于匹配對象的歸類患亿。
開發(fā)流程
收集數(shù)據(jù)：提供文本文件
準備數(shù)據(jù)：使用 Python 解析文本文件
分析數(shù)據(jù)：使用 Matplotlib 畫二維散點圖
訓練算法：此步驟不適用于 k-近鄰算法
測試算法：使用海倫提供的部分數(shù)據(jù)作為測試樣本传蹈。
測試樣本和非測試樣本的區(qū)別在于：
測試樣本是已經完成分類的數(shù)據(jù)押逼，如果預測分類與實際類別不同，則標記為一個錯誤惦界。
使用算法：產生簡單的命令行程序挑格，然后海倫可以輸入一些特征數(shù)據(jù)以判斷對方是否為自己喜歡的類型。
收集數(shù)據(jù)：提供文本文件
海倫把這些約會對象的數(shù)據(jù)存放在文本文件 datingTestSet2.txt 中沾歪，總共有 1000 行漂彤。海倫約會的對象主要包含以下 3 種特征：
- 每年獲得的飛行常客里程數(shù)
- 玩視頻游戲所耗時間百分比
- 每周消費的冰淇淋公升數(shù)
文本文件數(shù)據(jù)格式如下：
40920 8.326976 0.953952 3
14488 7.153469 1.673904 2
26052 1.441871 0.805124 1
75136 13.147394 0.428964 1
38344 1.669788 0.134296 1
準備數(shù)據(jù)：使用 Python 解析文本文件
將文本記錄轉換為 NumPy 的解析程序
def file2matrix(filename):
"""
Desc:
導入訓練數(shù)據(jù)
parameters:
filename: 數(shù)據(jù)文件路徑
return:
數(shù)據(jù)矩陣 returnMat 和對應的類別 classLabelVector
"""
fr = open(filename)
# 獲得文件中的數(shù)據(jù)行的行數(shù)
numberOfLines = len(fr.readlines())
# 生成對應的空矩陣
# 例如：zeros(2灾搏，3)就是生成一個 2*3的矩陣挫望，各個位置上全是 0
returnMat = zeros((numberOfLines, 3)) # prepare matrix to return
classLabelVector = [] # prepare labels return
fr = open(filename)
index = 0
for line in fr.readlines():
# str.strip([chars]) --返回移除字符串頭尾指定的字符生成的新字符串
line = line.strip()
# 以 '\t' 切割字符串
listFromLine = line.split('\t')
# 每列的屬性數(shù)據(jù)
returnMat[index, :] = listFromLine[0:3]
# 每列的類別數(shù)據(jù)，就是 label 標簽數(shù)據(jù)
classLabelVector.append(int(listFromLine[-1]))
index += 1
# 返回數(shù)據(jù)矩陣returnMat和對應的類別classLabelVector
return returnMat, classLabelVector
分析數(shù)據(jù)：使用 Matplotlib 畫二維散點圖
import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2], 15.0*array(datingLabels), 15.0*array(datingLabels))
plt.show()
下圖中采用矩陣的第一和第三列屬性得到很好的展示效果狂窑，清晰地標識了三個不同的樣本分類區(qū)域媳板，具有不同愛好的人其類別區(qū)域也不同。
KNN散點圖
- 歸一化數(shù)據(jù) （歸一化是一個讓權重變?yōu)榻y(tǒng)一的過程泉哈，更多細節(jié)請參考： https://www.zhihu.com/question/19951858）
| 序號 | 玩視頻游戲所耗時間百分比 | 每年獲得的飛行瞅刃遥客里程數(shù) | 每周消費的冰淇淋公升數(shù) | 樣本分類 |
|---|---|---|---|---|
| 1 | 0.8 | 400 | 0.5 | 1 |
| 2 | 12 | 134 000 | 0.9 | 3 |
| 3 | 0 | 20 000 | 1.1 | 2 |
| 4 | 67 | 32 000 | 0.1 | 2 |
樣本3和樣本4的距離：
計算樣本3 和 樣本4 的距離
歸一化特征值，消除特征之間量級不同導致的影響
def autoNorm(dataSet):
"""
Desc:
歸一化特征值丛晦，消除特征之間量級不同導致的影響
parameter:
dataSet: 數(shù)據(jù)集
return:
歸一化后的數(shù)據(jù)集 normDataSet. ranges和minVals即最小值與范圍奕纫，并沒有用到
歸一化公式：
Y = (X-Xmin)/(Xmax-Xmin)
其中的 min 和 max 分別是數(shù)據(jù)集中的最小特征值和最大特征值。該函數(shù)可以自動將數(shù)字特征值轉化為0到1的區(qū)間烫沙。
"""
# 計算每種屬性的最大值匹层、最小值、范圍
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
# 極差
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
# 生成與最小值之差組成的矩陣
normDataSet = dataSet - tile(minVals, (m, 1))
# 將最小值之差除以范圍組成矩陣
normDataSet = normDataSet / tile(ranges, (m, 1)) # element wise divide
return normDataSet, ranges, minVals
訓練算法：此步驟不適用于 k-近鄰算法
因為測試數(shù)據(jù)每一次都要與全量的訓練數(shù)據(jù)進行比較锌蓄，所以這個過程是沒有必要的升筏。
測試算法：使用海倫提供的部分數(shù)據(jù)作為測試樣本仲器。如果預測分類與實際類別不同，則標記為一個錯誤仰冠。
kNN 分類器針對約會網站的測試代碼
def datingClassTest():
"""
Desc:
對約會網站的測試方法
parameters:
none
return:
錯誤數(shù)
"""
# 設置測試數(shù)據(jù)的的一個比例（訓練數(shù)據(jù)集比例=1-hoRatio）
hoRatio = 0.1 # 測試范圍,一部分測試一部分作為樣本
# 從文件中加載數(shù)據(jù)
datingDataMat, datingLabels = file2matrix('input/2.KNN/datingTestSet2.txt') # load data setfrom file
# 歸一化數(shù)據(jù)
normMat, ranges, minVals = autoNorm(datingDataMat)
# m 表示數(shù)據(jù)的行數(shù)乏冀，即矩陣的第一維
m = normMat.shape[0]
# 設置測試的樣本數(shù)量， numTestVecs:m表示訓練樣本的數(shù)量
numTestVecs = int(m * hoRatio)
print 'numTestVecs=', numTestVecs
errorCount = 0.0
for i in range(numTestVecs):
# 對數(shù)據(jù)測試
classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)
print "the classifier 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))
print errorCount
使用算法：產生簡單的命令行程序洋只，然后海倫可以輸入一些特征數(shù)據(jù)以判斷對方是否為自己喜歡的類型辆沦。
約會網站預測函數(shù)
def clasdifyPerson():
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 filer miles earned per year?"))
iceCream = float(raw_input("liters of ice cream consumed per year?"))
datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
normMat, ranges, minVals = autoNorm(datingDataMat)
inArr = array([ffMils, percentTats, iceCream])
classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels, 3)
print "You will probably like this person: ", resultList[classifierResult - 1]
實際運行效果如下:
>>> kNN.classifyPerson()
percentage of time spent playing video games?10
frequent flier miles earned per year?10000
liters of ice cream consumed per year?0.5
You will probably like this person: in small doses
完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/2.KNN/kNN.py
項目案例2: 手寫數(shù)字識別系統(tǒng)
項目概述
構造一個能識別數(shù)字 0 到 9 的基于 KNN 分類器的手寫數(shù)字識別系統(tǒng)。
需要識別的數(shù)字是存儲在文本文件中的具有相同的色彩和大惺缎椤：寬高是 32 像素 * 32 像素的黑白圖像肢扯。
開發(fā)流程
收集數(shù)據(jù)：提供文本文件。
準備數(shù)據(jù)：編寫函數(shù) img2vector(), 將圖像格式轉換為分類器使用的向量格式
分析數(shù)據(jù)：在 Python 命令提示符中檢查數(shù)據(jù)担锤，確保它符合要求
訓練算法：此步驟不適用于 KNN
測試算法：編寫函數(shù)使用提供的部分數(shù)據(jù)集作為測試樣本蔚晨，測試樣本與非測試樣本的
區(qū)別在于測試樣本是已經完成分類的數(shù)據(jù)，如果預測分類與實際類別不同肛循，
則標記為一個錯誤
使用算法：本例沒有完成此步驟铭腕，若你感興趣可以構建完整的應用程序，從圖像中提取
數(shù)字多糠，并完成數(shù)字識別累舷，美國的郵件分揀系統(tǒng)就是一個實際運行的類似系統(tǒng)
收集數(shù)據(jù): 提供文本文件
目錄 trainingDigits 中包含了大約 2000 個例子，每個例子內容如下圖所示夹孔，每個數(shù)字大約有 200 個樣本被盈；目錄 testDigits 中包含了大約 900 個測試數(shù)據(jù)。
KNN 手寫數(shù)字識別示例
準備數(shù)據(jù): 編寫函數(shù) img2vector(), 將圖像文本數(shù)據(jù)轉換為分類器使用的向量
將圖像文本數(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ù)：在 Python 命令提示符中檢查數(shù)據(jù)搭伤，確保它符合要求
在 Python 命令行中輸入下列命令測試 img2vector 函數(shù)只怎，然后與文本編輯器打開的文件進行比較:
>>> testVector = kNN.img2vector('testDigits/0_13.txt')
>>> testVector[0,0:31]
array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.])
>>> testVector[0,31:63]
array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 1., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.])
訓練算法：此步驟不適用于 KNN
因為測試數(shù)據(jù)每一次都要與全量的訓練數(shù)據(jù)進行比較，所以這個過程是沒有必要的怜俐。
測試算法：編寫函數(shù)使用提供的部分數(shù)據(jù)集作為測試樣本身堡，如果預測分類與實際類別不同，則標記為一個錯誤
def handwritingClassTest():
# 1. 導入訓練數(shù)據(jù)
hwLabels = []
trainingFileList = listdir('input/2.KNN/trainingDigits') # load the training set
m = len(trainingFileList)
trainingMat = zeros((m, 1024))
# hwLabels存儲0～9對應的index位置佑菩， trainingMat存放的每個位置對應的圖片向量
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0] # take off .txt
classNumStr = int(fileStr.split('_')[0])
hwLabels.append(classNumStr)
# 將 32*32的矩陣->1*1024的矩陣
trainingMat[i, :] = img2vector('input/2.KNN/trainingDigits/%s' % fileNameStr)
# 2. 導入測試數(shù)據(jù)
testFileList = listdir('input/2.KNN/testDigits') # iterate through the test set
errorCount = 0.0
mTest = len(testFileList)
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[0] # take off .txt
classNumStr = int(fileStr.split('_')[0])
vectorUnderTest = img2vector('input/2.KNN/testDigits/%s' % fileNameStr)
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
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))
使用算法：本例沒有完成此步驟盾沫，若你感興趣可以構建完整的應用程序，從圖像中提取數(shù)字殿漠，并完成數(shù)字識別赴精，美國的郵件分揀系統(tǒng)就是一個實際運行的類似系統(tǒng)
完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/2.KNN/kNN.py
- 作者：羊三 小瑤
- GitHub地址: https://github.com/apachecn/MachineLearning
- 版權聲明：歡迎轉載學習 => 請標注信息來源于 ApacheCN
