[利用KNN算法改進約會網站的配對效果](http://blog.csdn.net/geekmanong/article/details/50523331) ### 一、案例背景 我的朋友海倫一直使用在線約會網站尋找合適自己的約會對象。盡管約會網站會推薦不同的人選，但她并不是喜歡每一個人。經過一番總結，她發現曾交往過三種類型的人： （1）不喜歡的人； （2）魅力一般的人； （3）極具魅力的人； 盡管發現了上述規律，但海倫依然無法將約會網站推薦的匹配對象歸入恰當的分類，她覺得可以在周一到周五約會那些魅力一般的人，而周末則更喜歡與那些極具魅力的人為伴。海倫希望我們的分類軟件可以更好地幫助她將匹配對象劃分到確切的分類中。此外，海倫還收集了一些約會網站未曾記錄的數據信息，她認為這些數據更助于匹配對象的歸類。 ### 二、案例分析 （1）收集數據：提供文本文件； （2）準備數據：使用Python解析文本文件； （3）分析數據：使用Matplotlib畫二維擴散圖； （4）訓練算法：此步驟不適用于K-近鄰算法； （5）測試算法：使用海倫提供的部分數據作為測試樣本， ? ? ? ? ?測試樣本和非測試樣本的區別在于：測試樣本是已經完成分類的數據，如果預測分類與實際類別不同，則標記為一個錯誤。 （6）使用算法：產生簡單的命令行程序，然后海倫可以輸入一些特征數據以判斷對方是否為自己喜歡的類型。 ### 三、準備數據：從文本文件中解析數據 海倫收集約會數據已經有了一段時間，她把這些數據存放在文本文件datingTestSet.txt中，每個樣本數據占據一行，總共有1000行。海倫的樣本主要包括以下3種特征： 1.每年獲得的飛行常客里程數； 2.玩視頻游戲所耗時間百分比； 3.每周消費的冰淇淋公升數； 在將上述特征數據輸入到分類器之前，必須將待處理數據的格式改變為分類器可以接受的格式。在kNN.py中創建名為file2matrix的函數，以此來處理輸入格式問題。該函數的輸入為文本文件名字符串，輸出為訓練樣本矩陣和類標簽向量。 將下面的代碼增加到kNN.py中：  ### 四、分析數據：使用Matplotlib創建散點圖 首先我們使用Matplotlib制作原始數據的散點圖，在Python命令行環境中，輸入下列命令： ~~~ #!/usr/bin/python278 # _*_ coding: utf-8 _*_ import kNN reload(kNN) datingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt') import matplotlib import matplotlib.pyplot as plt zhfont = matplotlib.font_manager.FontProperties(fname='C:\Windows\Fonts\ukai.ttc') fig=plt.figure() ax=fig.add_subplot(111) from numpy import * ax.scatter(datingDataMat[:,1],datingDataMat[:,2]) plt.xlabel(u'玩游戲所耗時間百分比', fontproperties=zhfont) plt.ylabel(u'每周消費的冰淇淋公升數', fontproperties=zhfont) plt.show() ~~~  上圖是沒有樣本標簽的約會數據散點圖，難以辨識圖中的點究竟屬于哪個樣本分類，我們可以利用Matplotlib庫提供的scatter函數來用彩色標記散點圖上的點。重新輸入上面的代碼，調用scatter函數： ~~~ #!/usr/bin/python278 # _*_ coding: utf-8 _*_ import kNN reload(kNN) datingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt') import matplotlib import matplotlib.pyplot as plt zhfont = matplotlib.font_manager.FontProperties(fname='C:\Windows\Fonts\ukai.ttc') fig=plt.figure() ax=fig.add_subplot(111) from numpy import * ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels)) plt.xlabel(u'玩游戲所耗時間百分比', fontproperties=zhfont) plt.ylabel(u'每周消費的冰淇淋公升數', fontproperties=zhfont) plt.show() ~~~  上圖是帶有樣本分類標簽的約會數據散點圖，雖然能夠比較容易地區分數據點從屬類別，但依然很難根據這張圖得出結論信息。 上圖使用了datingDataMat矩陣屬性列2和列3展示數據，雖然也可以區別，但下圖采用列1和列2的屬性值卻可以得到更好的效果： ~~~ #!/usr/bin/env python # _*_ coding: utf-8 _*_ import kNN reload(kNN) import matplotlib import matplotlib.pyplot as plt matrix, labels = kNN.file2matrix('datingTestSet2.txt') print matrix print labels zhfont = matplotlib.font_manager.FontProperties(fname='C:\Windows\Fonts\ukai.ttc') plt.figure(figsize=(8, 5), dpi=80) axes = plt.subplot(111) # 將三類數據分別取出來 # x軸代表飛行的里程數 # y軸代表玩視頻游戲的百分比 type1_x = [] type1_y = [] type2_x = [] type2_y = [] type3_x = [] type3_y = [] print 'range(len(labels)):' print range(len(labels)) for i in range(len(labels)): if labels[i] == 1: # 不喜歡 type1_x.append(matrix[i][0]) type1_y.append(matrix[i][1]) if labels[i] == 2: # 魅力一般 type2_x.append(matrix[i][0]) type2_y.append(matrix[i][1]) if labels[i] == 3: # 極具魅力 print i, '：', labels[i], ':', type(labels[i]) type3_x.append(matrix[i][0]) type3_y.append(matrix[i][1]) type1 = axes.scatter(type1_x, type1_y, s=20, c='red') type2 = axes.scatter(type2_x, type2_y, s=40, c='green') type3 = axes.scatter(type3_x, type3_y, s=50, c='blue') # plt.scatter(matrix[:, 0], matrix[:, 1], s=20 * numpy.array(labels), # c=50 * numpy.array(labels), marker='o', # label='test') plt.xlabel(u'每年獲取的飛行里程數', fontproperties=zhfont) plt.ylabel(u'玩視頻游戲所消耗的事件百分比', fontproperties=zhfont) axes.legend((type1, type2, type3), (u'不喜歡', u'魅力一般', u'極具魅力'), loc=2, prop=zhfont) plt.show() ~~~  圖中清晰的標識了三個不同的樣本分類區域，具有不同愛好的人其類別區域也不同，可以看出用圖中展示的“每年獲取飛行常客里程數”和“玩視頻游戲所耗時間百分比”兩個特征更容易區分數據點從屬的類別。 ### 五、準備數據：歸一化數值 為了防止特征值數量上的差異對預測結果的影響，比如計算距離時，量值較大的特征值對結果影響較大，所以我們對數據所有的特征值會進行歸一化到[0,1]的預處理。 ~~~ def autoNorm(dataSet): 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 ~~~ 代碼講解：函數autoNorm()中，每列的最小值放在變量minVals中，最大值放在maxVals中，其中dataSet.min(0)中的參數0使得函數可以從列中選取最小值，而不是選取當前行的最小值。因為特征值矩陣dataSet是1000X3，而minVals和range都是1X3，所以需要利用tile()函數將minVals和range的內容復制成輸入矩陣同樣大小的矩陣。 ~~~ >>> import kNN >>> reload(kNN) <module 'kNN' from 'kNN.pyc'> >>> datingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt') >>> normMat,ranges,minVals=kNN.autoNorm(datingDataMat) >>> normMat array([[ 0.44832535, 0.39805139, 0.56233353], [ 0.15873259, 0.34195467, 0.98724416], [ 0.28542943, 0.06892523, 0.47449629], ..., [ 0.29115949, 0.50910294, 0.51079493], [ 0.52711097, 0.43665451, 0.4290048 ], [ 0.47940793, 0.3768091 , 0.78571804]]) >>> ranges array([ 9.12730000e+04, 2.09193490e+01, 1.69436100e+00]) >>> minVals array([ 0. , 0. , 0.001156]) ~~~ ### 六、測試算法 機器學習算法中一個很重要的工作就是評估算法的正確率，通常我們會將已有數據的90%作為訓練樣本來訓練分類器，而使用其余10%的數據去測試分類器，檢測分類器的正確率。 1.分類器對約會網站的測試代碼： ~~~ def datingClassTest(): hoRatio = 0.50 #hold out 10% datingDataMat,datingLabels = file2matrix('datingTestSet2.txt') #load data setfrom file 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 "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 ~~~ ~~~ >>> kNN.datingClassTest() the classifier came back with: 3, the real answer is: 3 the classifier came back with: 2, the real answer is: 2 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 3, the real answer is: 3 the classifier came back with: 3, the real answer is: 3 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 3, the real answer is: 3 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 ~~~ ~~~ the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 3, the real answer is: 3 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 2, the real answer is: 1 the classifier came back with: 2, the real answer is: 2 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 2, the real answer is: 2 the total error rate is: 0.064000 ~~~ ### 七、使用算法 輸入某人信息，預測出海倫對對方喜歡程度： ~~~ 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('datingTestSet2.txt') normMat,ranges,minVals=autoNorm(datingDataMat) inArr=array([ffMiles,percentTats,iceCream]) classifierResult=classify0((inArr-minVals)/ranges,normMat,datingLabels,3) print "You will probably like this person:",resultList[classifierResult-1] ~~~ 代碼講解：Python中的raw_input()允許用戶輸入文本行命令并返回用戶所輸入的命令 ~~~ >>> import kNN >>> reload(kNN) <module 'kNN' from 'kNN.py'> >>> 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 ~~~