機器學習之KNN算法原理及Python實現(xiàn)方法詳解
本文實例講述了機器學習之KNN算法原理及Python實現(xiàn)方法。分享給大家供大家參考,具體如下:
文中代碼出自《機器學習實戰(zhàn)》CH02,可參考本站:
機器學習實戰(zhàn) (Peter Harrington著) 中文版
機器學習實戰(zhàn) (Peter Harrington著) 英文原版 [附源代碼]
KNN算法介紹
KNN是一種監(jiān)督學習算法,通過計算新數(shù)據(jù)與訓練數(shù)據(jù)特征值之間的距離,然后選取K(K>=1)個距離最近的鄰居進行分類判(投票法)或者回歸。若K=1,新數(shù)據(jù)被簡單分配給其近鄰的類。
KNN算法實現(xiàn)過程
(1)選擇一種距離計算方式, 通過數(shù)據(jù)所有的特征計算新數(shù)據(jù)與已知類別數(shù)據(jù)集中的數(shù)據(jù)點的距離;
(2)按照距離遞增次序進行排序,選取與當前距離最小的k個點;
(3)對于離散分類,返回k個點出現(xiàn)頻率最多的類別作預測分類;對于回歸則返回k個點的加權值作為預測值;
算法關鍵
(1)數(shù)據(jù)的所有特征都要做可比較的量化
若是數(shù)據(jù)特征中存在非數(shù)值的類型,必須采取手段將其量化為數(shù)值。例如樣本特征中包含顏色,可通過將顏色轉換為灰度值來實現(xiàn)距離計算。
(2)樣本特征要做歸一化處理
樣本有多個參數(shù),每一個參數(shù)都有自己的定義域和取值范圍,他們對距離計算的影響不一樣,如取值較大的影響力會蓋過取值較小的參數(shù)。所以樣本參數(shù)必須做一些scale處理,最簡單的方式就是所有特征的數(shù)值都采取歸一化處置。
(3)需要一個距離函數(shù)以計算兩個樣本之間的距離
距離的定義:歐氏距離、余弦距離、漢明距離、曼哈頓距離等,一般選歐氏距離作為距離度量,但是這是只適用于連續(xù)變量。在文本分類這種非連續(xù)變量情況下,漢明距離可以用來作為度量。通常情況下,如果運用一些特殊的算法來計算度量的話,K近鄰分類精度可顯著提高,如運用大邊緣最近鄰法或者近鄰成分分析法。
(4)確定K的值
K值選的太大易引起欠擬合,太小容易過擬合。交叉驗證確定K值。
KNN分類
分類算法常采用多數(shù)表決決定。一個缺點是出現(xiàn)頻率較多的樣本將會主導測試點的預測結果。解決這個缺點的方法之一是在進行分類時將K個鄰居到測試點的距離考慮進去。若樣本到測試點距離d,則選1/d為該鄰居的權重,統(tǒng)計k個鄰居所有類標簽的權重和,值最大的就是新數(shù)據(jù)點的預測類標簽。
KNN回歸
KNN回歸是取K個鄰居類標簽值得加權作為新數(shù)據(jù)點的預測值。
優(yōu)缺點
(1)KNN算法的優(yōu)點
- 1.簡單、有效。
- 2.重新訓練的代價較低(類別體系的變化和訓練集的變化,在Web環(huán)境和電子商務應用中是很常見的)。
- 3.計算時間和空間線性于訓練集的規(guī)模(在一些場合不算太大)。
- 4.由于KNN方法主要靠周圍有限的鄰近的樣本,而不是靠判別類域的方法來確定所屬類別的,因此對于類域的交叉或重疊較多的待分樣本集來說,KNN方法較其他方法更為適合。
- 5.該算法比較適用于樣本容量比較大的類域的自動分類,而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。
(2)KNN算法缺點
- 1.KNN算法是懶散學習方法(lazy learning,基本上不學習),一些積極學習的算法要快很多。
- 2.類別評分不是規(guī)格化的(不像概率評分)(???)。
- 3.輸出的可解釋性不強,例如決策樹的可解釋性較強。
- 4.該算法在分類時有個主要的不足是,當樣本不平衡時,如一個類的樣本容量很大,而其他類樣本容量很小時,有可能導致當輸入一個新樣本時,該樣本的K個鄰居中大容量類的樣本占多數(shù)。該算法只計算最近的鄰居樣本,某一類的樣本數(shù)量很大,那么或者這類樣本并不接近目標樣本,或者這類樣本很靠近目標樣本。無論怎樣,數(shù)量并不能影響運行結果。可以采用權值的方法(和該樣本距離小的鄰居權值大)來改進。
- 5.計算量較大。目前常用的解決方法是事先對已知樣本點進行剪輯,事先去除對分類作用不大的樣本。
KNN實現(xiàn)
import numpy as np import operator import matplotlib import matplotlib.pyplot as plt from os import listdir def Create_DataSet(): group = np.array([[1.0, 1.1],[1.0,1.0],[0,0],[0,0.1]]) labels = ['A','A','B','B'] return group,labels
函數(shù)Create_DataSet創(chuàng)建一個數(shù)據(jù)集,坐標軸左下角分類為B,右上角分類為A。
下面函數(shù)classify0,計算向量inX與數(shù)據(jù)集中各點的距離,計算n_estimators個近鄰中l(wèi)abel頻率最高的分類號并返回作為向量inX的分類號。
def classify0(inX, dataSet, labels, n_estimators=3): dataSetSize = dataSet.shape[0] #print 'in classify0,dataSetSize = \n',dataSetSize #轉變向量inx格式為datasize行,1列;并計算與dataset元素距離 diffMat = np.tile(inX, (dataSetSize,1)) - dataSet #計算歐氏距離((x0-x1)^2 + (y0-y1)^2 )^(1/2) sqDiffMat = diffMat**2 #diffMat每個元素取平方 sqDistances = sqDiffMat.sum(axis=1) distances = sqDistances**0.5 #排序,將值從小到大排列,返回索引 sortedDistIndicies = distances.argsort() #print 'in classify0,sortedDistIndicies:\n',sortedDistIndicies #求與距離最近的k個點的label統(tǒng)計 classCount={} for i in range(n_estimators): voteIlabel = labels[sortedDistIndicies[i]] #獲取對應label號 classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #對字典排序,按value值降序排列 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) #print 'sortedClassCount[0][0]:\n',sortedClassCount[0][0] return sortedClassCount[0][0]
dataSet.shape()
函數(shù)用于獲取矩陣dataSet的大小,shape[0]
返回對應行數(shù),shape[1]
返回對應列數(shù)。
因為需要對每列屬性做距離運算,所以需要將輸入inX轉換為和dataSet相同行數(shù)和列數(shù)的矩陣,因為inX列數(shù)與dataSet中每個元素列數(shù)相同,所以需要將其行數(shù)進行擴展,np.tile(inX, (dataSetSize,1))將inX行數(shù)拓展為dataSetSize行,1表示縱向復制1次,即列不變。
距離公式采用歐式距離計算,得到的距離值為一維列表,分別對應dataSet中每個元素和inX的距離。distances.argsort() 將距離按從小到大排列,并返回索引。例如distance = [0.1,0.5,0.3],distance.argsort()返回[1,3,2] 。返回索引是為了找到對應的label值,并進行統(tǒng)計。
下面for循環(huán)用于建立字典并統(tǒng)計前n_estimators個label的個數(shù)。key對應label,key_value對應個數(shù)。
operator.itemgetter
函數(shù),operator模塊提供的itemgetter函數(shù)用于獲取對象的哪些維的數(shù)據(jù),參數(shù)為一些序號,即需要獲取的數(shù)據(jù)在對象中的序號;例如a = [1,2,3] ,定義函數(shù)b=operator.itemgetter(1),獲取對象的第1個域的值,則 b(a)=2;若定義函數(shù)b,獲取對象的第1個域和第0個的值b=operator.itemgetter(1,0),則b(a)=(2, 1) 。注意operator.itemgetter函數(shù)獲取的不是值,而是定義了一個函數(shù),通過該函數(shù)作用到對象上才能獲取值;
sorted
函數(shù):Python內(nèi)置的排序函數(shù)sorted可以對list或者iterator進行排序;第一個參數(shù)iterable指定要排序的list或者iterable,第二個參數(shù)指定排序時進行比較的函數(shù),可以指定一個函數(shù)或者lambda函數(shù)。例如students為類對象的list,每個成員有三個域,用sorted進行比較時可以自己定cmp函數(shù),例如這里要通過比較第三個數(shù)據(jù)成員來排序,students = [(‘john', ‘A', 15), (‘jane', ‘B', 12), (‘dave', ‘B', 10)],sorted(students, key=lambda student : student[2]),key為函數(shù),指定取待排序元素的哪一項進行排序,key指定的lambda函數(shù)功能是去元素student的第三個域(student[2]),因此sorted排序時會以students所有元素的第三個域來進行排序;也可以這么寫sorted(students, key=operator.itemgetter(2)) ,sorted函數(shù)也可以進行多級排序,例如要根據(jù)第二個域和第三個域進行排序;sorted(students, key=operator.itemgetter(1,2))即先跟句第二個域排序,再根據(jù)第三個域排序;第三個參數(shù)reverse是一個bool變量,表示升序還是降序排列,默認為false升序排列,定義為True時將按降序排列。
此處sort
函數(shù)用于對字典進行排序。按key_value降序排列,即對應label個數(shù)從大到小排列。返回值為列表,列表元素為元組,元組第一個元素對應label,第二個元素對應label個數(shù)。sortedClassCount[0][0]即返回label次數(shù)最多的類標號,為inX的label。
下面測試一個簡單的向量:
group,labels = Create_DataSet() sortedClassCount = classify0([0,0.5],group,labels,3)
輸出為
sortedClassCount:[(‘B', 2), (‘A', 1)]
sortedClassCount[0][0]:
B
下面函數(shù)file2matrix用于從txt中讀取原始數(shù)據(jù)并轉化為矩陣。
test.txt格式為
40920 8.326976 0.953952 largeDoses
14488 7.153469 1.673904 smallDoses
26052 1.441871 0.805124 didntLike
75136 13.147394 0.428964 didntLike
……
最后一列為label,值為largeDoses、smallDoses或didntLike。每行元素用\t隔開。轉換后label分別對應3、2、1。
轉換函數(shù)如下:
def file2matrix(filename): fr = open(filename) numberOfLines = len(fr.readlines()) print 'in file2matrix,numberOfLines:\n',numberOfLines returnMat = np.zeros((numberOfLines,3)) classLabelVector = [] fr = open(filename) index = 0 for line in fr.readlines(): #遍歷每一行 line = line.strip() #strip用于刪除字符,此處刪除空白字符,回車 listFromLine = line.split('\t') #獲取每行的元素列表,元素用\t分開 returnMat[index,:] = listFromLine[0:3]#取前3個元素,對應屬性集 if(listFromLine[-1] == 'largeDoses'):#有什么有效的方法 將屬性值和類標號分開,相互對應 classLabelVector.append(3) elif(listFromLine[-1] == 'smallDoses'): classLabelVector.append(2) elif(listFromLine[-1] == 'didntLike'): classLabelVector.append(1) elif(listFromLine[-1] == 3): classLabelVector.append(3) elif(listFromLine[-1] == 2): classLabelVector.append(2) elif(listFromLine[-1] == 1): classLabelVector.append(1) index += 1 #print 'returnMat = ',returnMat #print 'classLabelVector = ',classLabelVector return returnMat,classLabelVector #得到屬性集和類標號
首先打開文件并獲取行數(shù),建立一個相同大小的空矩陣,用于存儲轉換后的屬性集,并新建一個一維列表,用于存放類標號。fr.readlines()讀取所有行,得到一個行列表,列表元素為每行內(nèi)容;readline只讀取1行,獲取該行元素的列表。
上述函數(shù)即返回屬性集矩陣和類標號列表。
因為屬性值差距較大,為了減少值太大的屬性對值小的屬性的影響,分類之前還需要進行歸一化。歸一化方程為(datain-min_val) / (max_val - min_val),輸出值都介于0-1。
def autoNorm(dataSet): minVals = dataSet.min(0) #獲取每列最大值與最小值,(0)指定列,而不是行 print 'in autoNorm,minVals:',minVals maxVals = dataSet.max(0) print 'in autoNorm,maxVals:',maxVals ranges = maxVals - minVals print 'in autoNorm,ranges:',ranges normDataSet = np.zeros(np.shape(dataSet)) m = dataSet.shape[0] #獲取行數(shù) #特征值矩陣為1000x3,minVals值為1x3,使用tile函數(shù)擴展為相同大小的矩陣 #np.tile(minVals, (m,1))矩陣minval,橫向復制m次,縱向復制1次 normDataSet = dataSet - np.tile(minVals, (m,1)) # (data - minval)/(maxval - minval) normDataSet = normDataSet/np.tile(ranges, (m,1)) #element wise divide print 'in autoNorm,normDataSet = ',normDataSet return normDataSet, ranges, minVals
返回歸一化以后的屬性集。即可進行距離運算并分類。
下面函數(shù)即對文件中所有輸入的行向量屬性進行分類
def datingClassTest(n_estimators=3): hoRatio = 0.50 #(1)讀取文件 datingDataMat,datingLabels = file2matrix('datingTestSet.txt') #(2)歸一化 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],n_estimators=n_estimators) if (classifierResult != datingLabels[i]): errorCount += 1.0 print "in datingClassTest,the total error rate is: %f" % (errorCount/float(numTestVecs)) print 'in datingClassTest,errorCount:',errorCount
將測試文件分為數(shù)據(jù)集和用于測試的向量2部分。前一半用于測試,后一半作為數(shù)據(jù)集,并定義errorCount用于統(tǒng)計出錯個數(shù)。經(jīng)過歸一化以后的數(shù)據(jù)集和驗證通過for循環(huán)計算分類結果,并與實際結果進行對比,得到總出錯數(shù)和出錯率。
執(zhí)行該函數(shù),結果顯示:
in datingClassTest,the total error rate is: 0.064000
in datingClassTest,errorCount: 32.0
更多關于Python相關內(nèi)容感興趣的讀者可查看本站專題:《Python數(shù)學運算技巧總結》、《Python數(shù)據(jù)結構與算法教程》、《Python函數(shù)使用技巧總結》、《Python字符串操作技巧匯總》、《Python入門與進階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》
希望本文所述對大家Python程序設計有所幫助。
相關文章
python實現(xiàn)支持目錄FTP上傳下載文件的方法
這篇文章主要介紹了python實現(xiàn)支持目錄FTP上傳下載文件的方法,適用于windows及Linux平臺FTP傳輸文件及文件夾,需要的朋友可以參考下2015-06-06windows系統(tǒng)下Python環(huán)境搭建教程
這篇文章主要為大家詳細介紹了windows系統(tǒng)下Python環(huán)境搭建教程,具有一定的參考價值,感興趣的小伙伴們可以參考一下2017-03-03基于python-opencv3實現(xiàn)圖像顯示和保存操作
這篇文章主要介紹了基于python opencv3的圖像顯示和保存操作方法,本文給大家介紹的非常詳細,具有一定的參考借鑒價值 ,需要的朋友可以參考下2019-06-06