Machine Learning In Action 第二章學習筆記: kNN算法

2023-10-18 阅读 18 评论 0

摘要：本文主要記錄《Machine Learning In Action》中第二章的內容。書中以兩個具體實例來介紹kNN（k nearest neighbors)，分別是：約會對象預測手寫數字識別通過“約會對象”功能，基本能夠了解到kNN算法的工作原理。“手寫數字識別”與“約會對象預測”

本文主要記錄《Machine Learning In Action》中第二章的內容。書中以兩個具體實例來介紹kNN（k nearest neighbors)，分別是：

約會對象預測
手寫數字識別

通過“約會對象”功能，基本能夠了解到kNN算法的工作原理。“手寫數字識別”與“約會對象預測”使用完全一樣的算法代碼，僅僅是數據集有變化。

約會對象預測

1 約會對象預測功能需求

主人公“張三”喜歡結交新朋友。“系統A”上面注冊了很多類似于“張三”的用戶，大家都想結交心朋友。“張三”最開始通過自己篩選的方式在“系統A”上面挑選感覺不錯的人，然后約出來吃飯，但結果不總是如“張三”所愿，他自己篩選出來的對象中，有些是真的跟他志趣相投，而有些則完全跟他不是一路人。“張三”希望“系統A”能自動給他推薦一些跟他志趣相投的朋友，提高他能約到“志趣相投”的朋友的概率。

2 分析需求

系統不能憑空為“張三”推薦朋友，必須拿一些“已有東西”作為依據和參考。這個“已有”的東西就是“張三”約會的歷史紀錄。

每次約會的對象，使用三個屬性來標記：

每年的飛行里程數量
每周打游戲所花的時間
每周能吃多少冰激凌

相當于使用這三個屬性，代表一個人。不同的人，三個屬性值各不相同。使用向量[feature1, feature2, feature3]來表示一個約會對象。約會的結果，有三種可能：不滿意，還可以，很滿意。使用class來表示約會結果。這樣一來，每條歷史約會紀錄可以表示為向量[feature1, feature2, feature3, class]，其中：

feature1:每天飛行里程數
feature2:每周打游戲所花時間
feature3:每周能吃多少冰激凌
class:約會結果

目前為止，“張三”有很多條類似于[feature1, feature2, feature3, class]這樣的約會紀錄，系統要實現的功能就是：對于一個“張三”沒有約會過的對象[feature1, feature2, feature3]，結合張三的歷史約會紀錄[feature1, feature2, feature3, class]，系統預測一個約會結果，如果預測結果是“很滿意”，就可以將這個“陌生人”推薦給“張三”。

明確了需求，就可以使用machine learning的大致套路來實現。

3 收集數據

拿到“張三”的歷史約會數據[feature1, feature2, feature3, class]。《Machine Learning In Action》的作者已經為我們準備好了數據，git地址:

https://github.com/pbharrin/machinelearninginaction/tree/master/Ch02

datingTestSet.txt和datingTestSet2.txt就是數據文件。主要區別是，兩個數據文件中，對約會結果的表示形式不同。datingTestSet.txt中使用字符串，datingTestSet2.txt中使用數字，本質上是一樣的。例如在datingTestSet2.txt中，數據為：

9868	2.694977	0.432818	2
18333	3.951256	0.333300	2
3780	9.856183	0.329181	2
18190	2.068962	0.429927	2
11145	3.410627	0.631838	2
68846	9.974715	0.669787	1
26575	10.650102	0.866627	3
48111	9.134528	0.728045	3
43757	7.882601	1.332446	3

第一列：年飛行里程數
第二列：玩游戲的時間
第三列：冰激凌的數量？
第四列：約會結果（1:不滿意 2:還可以 3:很滿意）

4 數據準備

有了數據，需要把數據都到計算機程序里面，才能繼續處理

將文件轉換為程序需要的數據結構：

def file2matrix(filename):fr = open(filename)numberOfLines = len(fr.readlines())returnMat = zeros((numberOfLines, 3))classLabelVector = []fr = open(filename)index = 0for line in fr.readlines():line = line.strip()listFromLine = line.split('\t')returnMat[index, :] = listFromLine[0:3]classLabelVector.append(int(listFromLine[-1]))index += 1return returnMat, classLabelVector

里面使用了numpy的Array來保存數據

5預處理數據

文件的前三列，每列數據對應一個屬性，而屬性的取值范圍各不相同，這將導致后面計算“距離”的時候，取值范圍大的屬性，對結果影響度較大。假設所有屬性的重要性是相同的，因此需要對屬性進行歸一化處理。代碼如下：

def autoNorm(dataSet):minVals = dataSet.min(0)maxVals = dataSet.max(0)ranges = maxVals - minValsnormDataSet = zeros(shape(dataSet))m = dataSet.shape[0]normDataSet = dataSet - tile(minVals, (m, 1))normDataSet = normDataSet / tile(ranges, (m, 1))return normDataSet, ranges, minVals

書中沒有講到當各個屬性的重要性不同時，該如果處理，感覺可以在這步，返回normDataSet之前，乘以一個系數來代表影響因子。

6 分析數據

這步主要通過pyplot將數據畫出來，通過圖形，可以對數據有一個直觀的感覺，可以大致判斷最開始選擇的三個feature跟class之間是否有一定的規律性的聯系。畫圖的代碼：

def plotDatingData():datingDataMat, datingLabels = file2matrix("datingTestSet2.txt")normMat, ranges, minVals = autoNorm(datingDataMat)datingDataMat = normMatfig = plt.figure()ax = fig.add_subplot(111)ax.scatter(datingDataMat[:, 0], datingDataMat[:, 1], 15.0*array(datingLabels), 10.0*array(datingLabels))plt.xlabel("Flyier Miles Earned Per Year")plt.ylabel("Time Spend Playing Video Games")plt.title("Dating History")plt.legend()plt.show()

效果圖：

上面代碼只使用了“飛行里程數”和“打游戲的時間”兩個feature。其中：

紅色：很滿意
綠色：還可以
藍色：不滿意

從圖中可以看出，3個結果都有一個大致的分配區域，說明可以使用這兩個feature來做預測。

7 kNN算法

對于給定的一個向量，與已有數據集中的所有向量計算“向量距離”，距離越近，表示兩個向量越相似。從已有數據集中，找出與給定向量距離最近的前k個向量。這前k個向量，每個都對應一個結果class，采用少數服從多數的方式，出現次數最多的class，就是預測的結果class。

代碼如下：

def classify0(inX, dataSet, labels, k):dataSetSize = dataSet.shape[0]diffMat = tile(inX, (dataSetSize, 1)) - dataSetsqDiffMat = diffMat**2sqDistances = sqDiffMat.sum(axis=1)distances = sqDistances**0.5sortedDistIndicies = distances.argsort()classCount = {}for i in range(k):voteIlabel = labels[sortedDistIndicies[i]]classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)return sortedClassCount[0][0]

8 算法測試

上面使用的“約會歷史數據”，相當于訓練數據。基于訓練數據集，產生了上面的預測方法。檢測這個預測方法到底好不好，可以使用“歷史數據”中的前10%作為測試數據集，只使用后90%作為訓練數據集。用測試數據集中的數據，在上面的預測方法中跑出結果后，跟實際的結果進行比較，如果一樣，就說明預測對了，否則，說明預測錯誤。最后可以得出一個錯誤率，錯誤率越低，說明預測方法越好。代碼如下：

def datingClassTest():hoRatio = 0.10datingDataMat, datingLabels = file2matrix("datingTestSet2.txt")normMat, ranges, minVals = autoNorm(datingDataMat)m = normMat.shape[0]numTestVecs = int(m * hoRatio)errorCount = 0.0for i in range(numTestVecs):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.0print "the total error rate is: %f" % (errorCount / float(numTestVecs))

9 實際運用

到現在為止，就可以使用上面完成的預測方法進行“約會對象預測”了。代碼如下：

def classifyPerson():resultMap = {1: 'not at all',2: 'in small doses',3: 'in large doses'}flierMiles = float(raw_input("flier miles earned per year?"))playGameTime = float(raw_input("time spent playing video games?"))iceCream = float(raw_input("liters of ice cream consumed per year?"))datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')normMat, ranges, minVals = autoNorm(datingDataMat)inAttr = array([flierMiles, playGameTime, iceCream])classifierResult = classify0((inAttr - minVals) / ranges, normMat, datingLabels, 3)print "You will probably like this person: ", resultMap[classifierResult]

手寫數字識別

這個例子與“約會對象預測”本質上是一樣的，僅僅是數據集不同。數據集位于zip打包文件中，git地址：
https://github.com/pbharrin/machinelearninginaction/tree/master/Ch02

1 將單個文件轉成向量

代碼：

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, i*32 + j] = int(lineStr[j])return returnVect

2 算法測試

代碼：

def handwritingClassTest():hwLabels = []trainingFileList = os.listdir("trainingDigits")m = len(trainingFileList)trainingMat = zeros((m, 1024))for i in range(m):fileNameStr = trainingFileList[i]fileStr = fileNameStr.split(".")[0]classNumStr = int(fileStr.split('_')[0])hwLabels.append(classNumStr)trainingMat[i, :] = img2vector(os.path.join("trainingDigits", fileNameStr))testFileList = os.listdir("testDigits")errorCount = 0.0mTest = len(testFileList)for i in range(mTest):fileNameStr = testFileList[i]fileStr = fileNameStr.split(".")[0]classNumStr = int(fileStr.split("_")[0])vectorUnderTest = img2vector(os.path.join("testDigits", testFileList[i]))classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)print "the classifier came back with: %d, the real anwser is: %d" % (classifierResult, classNumStr)if (classifierResult != classNumStr):errorCount += 1.0print "\nthe total number of errors is: %d" % errorCountprint "\nthe total error rate is: %f" % (errorCount / float(mTest))