之前學習了k-近鄰算法的實作後,參考《機器學習實戰》中的例子進行了k-近鄰算法的測驗,主要測試了針對約會網站和手寫識别系統的資料分類,這兩個測試使用的是《機器學習實戰》提供的資料集。
在編寫函數前,需在.py檔案中添加以下内容:
from numpy import *
import numpy as np
import operator
from os import listdir
第一部分是針對約會網站的資料分類,用于改進約會網站的配對效果。該執行個體的簡介如下:
-
海倫一直使用線上約會網站尋找合适自己的約會對象。盡管約會網站會推薦不同的人選,但她沒有從中找到喜歡的人。經過一番總結,她發現曾交往過三種類型的人:
1.不喜歡的人( 以下簡稱1 );
2.魅力一般的人( 以下簡稱2 );
3.極具魅力的人( 以下簡稱3 )
- 盡管發現了上述規律,但海倫依然無法将約會網站推薦的比對對象歸入恰當的分類。她覺得可以在周一到周五約會哪些魅力一般的人,而周末則更喜歡與那些極具魅力的人為伴。海倫希望我們的分類軟體可以更好的幫助她将比對對象劃分到确切的分類中。此外海倫還收集了一些約會網站未曾記錄的資料資訊,她認為這些資料更有助于比對對象的歸類。
- 這裡提取一下這個案例的目标:根據一些資料資訊,對指定人選進行分類(1或2或3)。為了使用kNN算法達到這個目标,我們需要哪些資訊?前面提到過,就是需要樣本資料,仔細閱讀我們發現,這些樣本資料就是“海倫還收集了一些約會網站未曾記錄的資料資訊 ”。
針對以上的描述,需要進行以下步驟:
- 收集資料
- 準備資料
- 設計算法分析資料
- 測試算法
1.收集資料
海倫收集的資料是記錄一個人的三個特征:每年獲得的飛行常客裡程數;玩視訊遊戲所消耗的時間百分比;每周消費的冰淇淋公升數。資料是txt格式檔案,如下圖,前三列依次是三個特征,第四列是分類(1:代表不喜歡的人,2:代表魅力一般的人,3:代表極具魅力的人),每一行資料代表一個人。
2.準備資料
計算機需要對資料檔案txt讀取資料,是以需要把資料進行格式化,對于數學運算,計算機擅長把資料存放在矩陣中。以下代碼中
file2matrix(filename)
函數完成了這一工作,該函數輸入資料檔案名(字元串),輸出訓練樣本矩陣和類标簽向量。
這一過程傳回兩個矩陣:一個矩陣用于存放每個人的三個特征資料,一個矩陣存放每個人對應的分類。
3.設計算法分析資料
k-近鄰算法的思想是尋找測試資料的前k個距離最近的樣本,然後根據這k個樣本的分類來确定該資料的分類,遵循“多數占優”原則。是以,如何尋找樣本成為主要的問題,在信号處理和模式識别領域中,常常使用“距離”來度量信号或特征的相似度。在這裡,我們假定可以使用三個特征資料來代替每個人,比如第一個人的屬性我們用[40920, 8.326976, 0.953952]來代替,并且他的分類是3。那麼此時的距離就是點的距離。
求出測試樣本與訓練樣本中每個點的距離,然後進行從小到大排序,前k位的就是k-近鄰,然後看看這k位近鄰中占得最多的分類是什麼,也就獲得了最終的答案。這一部分是k-近鄰算法的核心,代碼中
classify()
函數就實作了k-近鄰算法的核心部分。
一個優化算法效果的步驟——歸一化資料:
打開資料檔案我們可用發現第一列代表的特征數值遠遠大于其他兩項特征,這樣在求距離的公式中就會占很大的比重,緻使兩個樣本的距離很大程度上取決于這個特征,其他特征的特性變得可有可無,這顯然有悖于實際情況。是以通常我們可用使用歸一化這一數學工具對資料進行預處理,這一處理過後的各個特征既不影響相對大小又可以不失公平。
Normalize(data)
函數實作了這一功能。
4.測試算法
經過了對資料進行預處理後、歸一化數值,可用驗證kNN算法有效性,測試代碼為:
WebClassTest()
由于資料有1000條,我們設定一個比率
ratio = 0.1
也就是令
1000 * ratio = 100
條作為測試樣本,其餘
900
條作為訓練樣本,當然,
ratio
的值可用改變,對算法效果是有影響的。
實作代碼:
def classify(data, sample, label, k):
SampleSize = sample.shape[]
DataMat = tile(data, (SampleSize, ))
delta = (DataMat - sample)**
distance = (delta.sum(axis = ))** #
sortedDist = distance.argsort()
classCount = {}
for i in range(k):
votedLabel = label[sortedDist[i]]
classCount[votedLabel] = classCount.get(votedLabel, ) +
result = sorted(classCount.iteritems(), key = operator.itemgetter(), reverse = True)
return result[][]
#print classify([10,0], sample, label, 3)
def file2matrix(filename):
fil = open(filename)
fileLines = fil.readlines() # Convert the contents of a file into a list
lenOfLines = len(fileLines)
Mat = zeros((lenOfLines, ))
classLabel = []
index =
for line in fileLines:
line = line.strip()
listFromLine = line.split('\t')
Mat[index,: ] = listFromLine[:]
classLabel.append(int(listFromLine[-])) # the last one of listFromLine is Label
index +=
return Mat, classLabel
mat,label = file2matrix('datingTestSet2.txt')
#print mat
# draw
import matplotlib
import matplotlib.pyplot as plt
fil = open('datingTestSet2.txt')
fileLines = fil.readlines() # Convert the contents of a file into a list
lenOfLines = len(fileLines)
figure = plt.figure()
axis = figure.add_subplot()
lab = ['didntLike', 'smallDoses', 'largeDoses']
for i in range():
n = []
l = []
for j in range(lenOfLines):
if label[j] == i + :
n.append(list(mat[j,:]))
l.append(label[j])
n = np.array(n) # list to numpy.adarray
#reshape(n, (3,k))
axis.scatter(n[:,], n[:,], *array(l), *array(l), label = lab[i])
print type(mat)
print type(n)
plt.legend()
plt.show()
def Normalize(data):
minValue = data.min()
maxValue = data.max()
ValueRange = maxValue - minValue
norm_data = zeros(shape(data))
k = data.shape[]
norm_data = data - tile(minValue, (k, ))
norm_data = norm_data / tile(ValueRange, (k, ))
return norm_data, ValueRange, minValue
def WebClassTest():
ratio =
dataMat, dataLabels = file2matrix('datingTestSet2.txt')
normMat, ValueRange, minValue = Normalize(dataMat)
k = normMat.shape[]
num = int(k * ratio) # test sample : 10%
errorCount =
for i in range(num):
result = classify(normMat[i,:], normMat[num:k,:],\
dataLabels[num:k], ) # k = 3
print "The classifier came back with: %d, the real answer is %d"\
% (result, dataLabels[i])
if (result != dataLabels[i]): errorCount +=
print "The total error rate is %f " % (errorCount / float(num))
WebClassTest()
在程式設計過程中,需要注意list、array、adarray等資料結構的使用,numpy.ndarray和标準Python庫類array.array功能是不相同的。以上代碼中
print type(mat)
和
print type(n)
就是為了觀察各變量的類型。允許以上代碼,可用畫出散點圖如下:
以上散點使用資料集中第二維和第三維資料繪制而出,當然,你可用選擇其他次元的資料畫二維散點圖,或者使用所有次元的資料畫高維圖(未實作),如下圖所示:
對約會網站分類的測試,由于分類效果依賴于參數k和測試樣本占樣本數目的比例,開始測試按照書中的參數進行,取
k=3
,測試樣本占總樣本比例為
0.1
進行測試,結果如下:
理論上來說,增大k的取值可以提高準确率,但實際上若k值太大,也會造成準确率下降,而且運算複雜度增大。
k = 7:
k = 17:
另一方面,降低ratio值(即增大訓練樣本集的比率)也可以提高算法的準确率,但由于每次算法需要比較更多的樣本,是以算法複雜度也會增加。
第二部分是手寫數字識别:
首先來看看書本給出的資料集:
def img2vector(filename):
returnVect = zeros((,))
fr = open(filename)
for i in range():
lineStr = fr.readline()
for j in range():
returnVect[,*i+j] = int(lineStr[j])
return returnVect
def handwritingClassTest():
hwLabels = []
trainingFileList = listdir('trainingDigits') #load the training set
m = len(trainingFileList)
trainingMat = zeros((m,))
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[] # take off .txt
classNumStr = int(fileStr.split('_')[])
hwLabels.append(classNumStr)
trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
testFileList = listdir('testDigits') # iterate through the test set
errorCount =
mTest = len(testFileList)
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[] # take off .txt
classNumStr = int(fileStr.split('_')[])
vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
classifierResult = classify(vectorUnderTest, trainingMat, hwLabels, ) # k = 3
print "The classifier came back with: %d, the real answer is: %d"\
% (classifierResult, classNumStr)
if (classifierResult != classNumStr): errorCount = errorCount +
print "\nThe total number of errors is: %d" % errorCount
print "\nThe total error rate is: %f" % (errorCount/float(mTest))
handwritingClassTest()
一個結果(
k = 3
):
k = 7
時的結果,正确率并不比
k = 3
時要好:
在手寫數字識别過程中,随着k值得增大,準确率反而降低了。k的取值并不是越大越好。
至此,完成了k-近鄰算法的學習和執行個體驗證。比起其他機器學習方法,k-近鄰算法是最簡單最有效的分類資料算法,使用算法時必須有接近實際資料的訓練樣本資料。但是如前一節所說的,該算法的缺點也很多,最大的一點是無法給出資料的内在含義。事實上k決策樹是k-近鄰算法的優化版本,比起前者,決策樹有效減少了儲存空間和計算空間的開銷,後期需繼續深入學習!