使用python實(shí)現(xiàn)kNN分類(lèi)算法
k-近鄰算法是基本的機(jī)器學(xué)習(xí)算法，算法的原理非常簡(jiǎn)單：
輸入樣本數(shù)據(jù)后，計(jì)算輸入樣本和參考樣本之間的距離，找出離輸入樣本距離最近的k個(gè)樣本，找出這k個(gè)樣本中出現(xiàn)頻率最高的類(lèi)標(biāo)簽作為輸入樣本的類(lèi)標(biāo)簽，很直觀也很簡(jiǎn)單，就是和參考樣本集中的樣本做對(duì)比。下面講一講用python實(shí)現(xiàn)kNN算法的方法，這里主要用了python中常用的numpy模塊，采用的數(shù)據(jù)集是來(lái)自UCI的一個(gè)數(shù)據(jù)集，總共包含1055個(gè)樣本，每個(gè)樣本有41個(gè)real的屬性和一個(gè)類(lèi)標(biāo)簽，包含兩類(lèi)（RB和NRB）。我選取800條樣本作為參考樣本，剩下的作為測(cè)試樣本。
下面是分類(lèi)器的python代碼：
'''
kNNClassify(inputAttr, trainSetPath = '', lenOfInstance = 42, startAttr = 0, stopAttr = 40, posOfClass = 41, numOfRefSamples = 5)函數(shù)
參數(shù)：
inputAttr：輸入的屬性向量
trainSetPath：字符串，保存訓(xùn)練樣本的路徑
lenOfInstance：樣本向量的維數(shù)
startAttr：屬性向量在整個(gè)樣本向量中的起始下標(biāo)
stopAttr：屬性向量在整個(gè)樣本向量中的終止下標(biāo)
posOfClass：類(lèi)標(biāo)簽的在整個(gè)樣本向量中的下標(biāo)
numOfClSamples:選出來(lái)進(jìn)行投票的樣本個(gè)數(shù)
返回值：
類(lèi)標(biāo)簽
'''
def kNNClassify(inputAttr, trainSetPath = '', lenOfInstance = 42, startAttr = 0, stopAttr = 40, posOfClass = 41, numOfRefSamples = 5):
fr = open(trainSetPath)
strOfLine = fr.readline()
arrayOfLine = numpy.array([0.] * lenOfInstance)
refSamples = numpy.array([[-1., 0.]] * numOfRefSamples)
#找出屬性中的最大值和最小值，用于歸一化
maxAttr, minAttr = kNNFunction.dataNorm(trainSetPath = trainSetPath, lenOfInstance = lenOfInstance)
maxAttr = maxAttr[(numpy.array(range(stopAttr - startAttr + 1))
+ numpy.array([startAttr] * (stopAttr - startAttr + 1)))]
minAttr = minAttr[(numpy.array(range(stopAttr - startAttr + 1))
+ numpy.array([startAttr] * (stopAttr - startAttr + 1)))]
attrRanges = maxAttr - minAttr
inputAttr = inputAttr[(numpy.array(range(stopAttr - startAttr + 1))
+ numpy.array([startAttr] * (stopAttr - startAttr + 1)))]
inputAttr = (inputAttr - minAttr) / attrRanges #歸一化
#將字符串轉(zhuǎn)換為向量并進(jìn)行計(jì)算找出離輸入樣本距離最近的numOfRefSamples個(gè)參考樣本
while strOfLine != '' :
strOfLine = strOfLine.strip()
strOfLine = strOfLine.split(';')
abandonOrNot = False
for i in range(lenOfInstance) :
if strOfLine[i] == 'RB' :
arrayOfLine[i] = 1.0
elif strOfLine[i] == 'NRB' :
arrayOfLine[i] = 0.0
elif strOfLine[i] != '?' : #沒(méi)有發(fā)現(xiàn)缺失值
arrayOfLine[i] = float(strOfLine[i])
abandonOrNot = False
else : #發(fā)現(xiàn)缺失值
abandonOrNot = True
break
if abandonOrNot == True :
strOfLine = fr.readline()
continue
else :
attr = arrayOfLine[(numpy.array(range(stopAttr - startAttr + 1))
+ numpy.array([startAttr] * (stopAttr - startAttr + 1)))]
attr = (attr - minAttr) / attrRanges #歸一化
classLabel = arrayOfLine[posOfClass]
distance = (attr - inputAttr) ** 2
distance = distance.sum(axis = 0)
distance = distance ** 0.5
disAndLabel = numpy.array([distance, classLabel])
refSamples = kNNFunction.insertItem(refSamples, numOfRefSamples, disAndLabel)
strOfLine = fr.readline()
continue
#統(tǒng)計(jì)每個(gè)類(lèi)標(biāo)簽出現(xiàn)的次數(shù)
classCount = {}
for i in range(numOfRefSamples) :
voteLabel = refSamples[i][1]
classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
sortedClassCount = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse = True)
return int(sortedClassCount[0][0])
實(shí)現(xiàn)步驟為：讀取一條樣本，轉(zhuǎn)換為向量，計(jì)算這條樣本與輸入樣本的距離，將樣本插入到refSamples數(shù)組中，當(dāng)然這里的樣本只是一個(gè)包含兩個(gè)元素的數(shù)組（距離和類(lèi)標(biāo)簽），而refSamples數(shù)組用于保存離輸入樣本最近的numOfRefSamples個(gè)參考樣本。當(dāng)所有樣本都讀完之后，就找出了離輸入樣本最近的numOfRefSamples個(gè)參考樣本。其中kNNFunction.insertItem函數(shù)實(shí)現(xiàn)的是將得到的新樣本插入到refSamples數(shù)組中，主要采用類(lèi)似冒泡排序的方法，實(shí)現(xiàn)代碼如下：
'''
insertItem(refSamples, numOfRefSamples, disAndLabel)函數(shù)
功能：
在參考樣本集中插入新樣本，這里的樣本是一個(gè)包含兩個(gè)數(shù)值的list，第一個(gè)是距離，第二個(gè)是類(lèi)標(biāo)簽
在參考樣本集中按照距離從小到大排列
參數(shù)：
refSamples：參考樣本集
numOfRefSamples：參考樣本集中的樣本總數(shù)
disAndLabel：需要插入的樣本數(shù)
'''
def insertItem(refSamples, numOfRefSamples, disAndLabel):
if (disAndLabel[0] < refSamples[numOfRefSamples - 1][0]) or (refSamples[numOfRefSamples - 1][0] < 0) :
refSamples[numOfRefSamples - 1] = disAndLabel
for i in (numpy.array([numOfRefSamples - 2] * (numOfRefSamples - 1)) - numpy.array(range(numOfRefSamples -1))) :
if (refSamples[i][0] > refSamples[i + 1][0]) or (refSamples[i][0] < 0) :
tempSample = list(refSamples[i])
refSamples[i] = refSamples[i + 1]
refSamples[i + 1] = tempSample
else :
break
return refSamples
else :
return refSamples
另外，需要注意的一點(diǎn)是要對(duì)輸入樣本的各條屬性進(jìn)行歸一化處理。畢竟不同的屬性的取值范圍不一樣，取值范圍大的屬性在計(jì)算距離的過(guò)程中所起到的作用自然就要大一些，所以有必要把所有屬性映射到0和1之間。這就需要計(jì)算每個(gè)屬性的最大值和最小值，方法就是遍歷整個(gè)參考樣本集，找出最大值和最小樣本，這里用dataNorm函數(shù)是實(shí)現(xiàn)：
'''
歸一化函數(shù)，返回歸一化向量
'''
def dataNorm(trainSetPath = '', lenOfInstance = 42):
fr = open(trainSetPath)
strOfLine = fr.readline() #從文件中讀取的一行字符串
arrayOfLine = numpy.array([0.] * lenOfInstance) #用來(lái)保存與字符串對(duì)應(yīng)的數(shù)組
maxAttr = numpy.array(['NULL'] * lenOfInstance) #用來(lái)保存每條屬性的最大值
minAttr = numpy.array(['NULL'] * lenOfInstance) #用來(lái)保存每條屬性的最小值
while strOfLine != '' :
strOfLine = strOfLine.strip() #去掉字符串末尾的換行符
strOfLine = strOfLine.split(';') #將字符串按逗號(hào)分割成字符串?dāng)?shù)組
abandonOrNot = False
for i in range(lenOfInstance) :
if strOfLine[i] == 'RB' :
arrayOfLine[i] = 1.0
elif strOfLine[i] == 'NRB' :
arrayOfLine[i] = 0.0
elif strOfLine[i] != '?' : #沒(méi)有發(fā)現(xiàn)缺失值
arrayOfLine[i] = float(strOfLine[i])
abandonOrNot = False
else : #發(fā)現(xiàn)缺失值
abandonOrNot = True
break
if abandonOrNot == True : #存在缺失值，丟棄
strOfLine = fr.readline()
continue
else : #沒(méi)有缺失值，保留
if maxAttr[0] == 'NULL' or minAttr[0] == 'NULL' : #maxAttr和minAttr矩陣是空的
maxAttr = numpy.array(arrayOfLine)
minAttr = numpy.array(arrayOfLine)
strOfLine = fr.readline()
continue
for i in range(lenOfInstance) :
if maxAttr[i] < arrayOfLine[i] :
maxAttr[i] = float(arrayOfLine[i])
if minAttr[i] > arrayOfLine[i] :
minAttr[i] = float(arrayOfLine[i])
strOfLine = fr.readline()
continue
return maxAttr, minAttr
至此為止，分類(lèi)器算是完成，接下去就是用剩下的測(cè)試集進(jìn)行測(cè)試，計(jì)算分類(lèi)的準(zhǔn)確度，用kNNTest函數(shù)實(shí)現(xiàn)：
def kNNTest(testSetPath = '', trainSetPath = '', lenOfInstance = 42, startAttr = 0, stopAttr = 40, posOfClass = 41):
fr = open(testSetPath)
strOfLine = fr.readline()
arrayOfLine = numpy.array([0.] * lenOfInstance)
succeedClassify = 0.0
failedClassify = 0.0
while strOfLine != '' :
strOfLine = strOfLine.strip()
strOfLine = strOfLine.split(';')
abandonOrNot = False
for i in range(lenOfInstance) :
if strOfLine[i] == 'RB' :
arrayOfLine[i] = 1.0
elif strOfLine[i] == 'NRB' :
arrayOfLine[i] = 0.0
elif strOfLine[i] != '?' : #沒(méi)有發(fā)現(xiàn)缺失值
arrayOfLine[i] = float(strOfLine[i])
abandonOrNot = False
else : #發(fā)現(xiàn)缺失值
abandonOrNot = True
break
if abandonOrNot == True :
strOfLine = fr.readline()
continue
else :
inputAttr = numpy.array(arrayOfLine)
classLabel = kNNClassify(inputAttr, trainSetPath = trainSetPath, lenOfInstance = 42, startAttr = startAttr,
stopAttr = stopAttr, posOfClass = posOfClass)
if classLabel == arrayOfLine[posOfClass] :
succeedClassify = succeedClassify + 1.0
else :
failedClassify = failedClassify + 1.0
strOfLine = fr.readline()
accuracy = succeedClassify / (succeedClassify + failedClassify)
return accuracy
最后，進(jìn)行測(cè)試：
accuracy = kNN.kNNTest(testSetPath = 'D:\\python_project\\test_data\\QSAR-biodegradation-Data-Set\\biodeg-test.csv',
trainSetPath = 'D:\\python_project\\test_data\\QSAR-biodegradation-Data-Set\\biodeg-train.csv',
startAttr = 0, stopAttr = 40)
print '分類(lèi)準(zhǔn)確率為：',accuracy
輸出結(jié)果為：
分類(lèi)準(zhǔn)確率為： 0.847058823529
可見(jiàn)用kNN這種分類(lèi)器的對(duì)這個(gè)數(shù)據(jù)集的分類(lèi)效果其實(shí)還是比較一般的，而且根據(jù)我的測(cè)試，分類(lèi)函數(shù)kNNClassify中numOfRefSamples（其實(shí)就是k-近鄰中k）的取值對(duì)分類(lèi)準(zhǔn)確度也有明顯的影響，大概在k取5的時(shí)候，分類(lèi)效果比較理想，并不是越大越好。下面談?wù)勎覍?duì)這個(gè)問(wèn)題的理解：
首先，kNN算法是一種簡(jiǎn)單的分類(lèi)算法，不需要任何訓(xùn)練過(guò)程，在樣本數(shù)據(jù)的結(jié)構(gòu)比較簡(jiǎn)單邊界比較明顯的時(shí)候，它的分類(lèi)效果是比較理想的，比如:
當(dāng)k的取值比較大的時(shí)候，在某些復(fù)雜的邊界下會(huì)出現(xiàn)很差的分類(lèi)效果，比如下面的情況下很多藍(lán)色的類(lèi)會(huì)被分到紅色中，所以要用比較小的k才會(huì)有相對(duì)較好的分類(lèi)效果：
但是當(dāng)k取得太小也會(huì)使分類(lèi)效果變差，比如當(dāng)不同類(lèi)的樣本數(shù)據(jù)之間邊界不明顯，存在交叉的時(shí)候，比如：
總的來(lái)說(shuō)，kNN分類(lèi)算法是一種比較原始直觀的分類(lèi)算法，對(duì)某些簡(jiǎn)單的情況有比較好的分類(lèi)效果，并且不需要訓(xùn)練模型。但是它的缺點(diǎn)是分類(lèi)過(guò)程的運(yùn)算復(fù)雜度很高，而且當(dāng)樣本數(shù)據(jù)的結(jié)構(gòu)比較復(fù)雜的時(shí)候，它的分類(lèi)效果不理想。用kNN算法對(duì)本次實(shí)驗(yàn)中的數(shù)據(jù)集的分類(lèi)效果也比較一般，不過(guò)我試過(guò)其它更簡(jiǎn)單一些的數(shù)據(jù)集，確實(shí)還是會(huì)有不錯(cuò)的分類(lèi)準(zhǔn)確性的，這里就不贅述了。
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于Python中常用utils庫(kù)的相關(guān)資料,Utils是一個(gè)Python庫(kù),它提供了一系列的工具,可以幫助你更輕松地管理你的Python環(huán)境,文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-03-03
細(xì)數(shù)nn.BCELoss與nn.CrossEntropyLoss的區(qū)別
今天小編就為大家整理了一篇細(xì)數(shù)nn.BCELoss與nn.CrossEntropyLoss的區(qū)別，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-02-02
Django中使用haystack+whoosh實(shí)現(xiàn)搜索功能
這篇文章主要介紹了Django之使用haystack+whoosh實(shí)現(xiàn)搜索功能,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2019-10-10
我們?cè)诿嬖囍泻芸赡苡龅浇o定一個(gè)含有重復(fù)元素的列表,刪除其中重復(fù)的元素,下面這篇文章主要給大家介紹了關(guān)于Python刪除列表中重復(fù)元素的七種方法,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-03-03
Python實(shí)現(xiàn)讀取.nc數(shù)據(jù)并提取指定時(shí)間與經(jīng)緯度維度對(duì)應(yīng)的變量數(shù)值
這篇文章主要為大家詳細(xì)介紹了如何使用Python語(yǔ)言的netCDF4庫(kù)實(shí)現(xiàn)讀取.nc格式的數(shù)據(jù)文件,并提取指定維（時(shí)間、經(jīng)度與緯度）下的變量數(shù)據(jù),需要的可以了解下2024-02-02
OpenCV視頻流Python多線程處理方法詳細(xì)分析
為OpenCV是搞計(jì)算機(jī)視覺(jué)必須要掌握的基礎(chǔ),這篇文章主要給大家介紹了關(guān)于OpenCV視頻流多線程處理的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-11-11
PyQt5使用mimeData實(shí)現(xiàn)拖拽事件教程示例解析上
這篇文章主要為大家介紹了PyQt中如何使用mimeData實(shí)現(xiàn)拖拽事件的示例解析過(guò)程，有需要的朋友可以借鑒參考下希望能夠有所幫助，祝大家多多進(jìn)步2021-10-10
這篇文章主要介紹了python繪制分布折線圖的示例代碼，幫助大家更好的利用python繪制圖像，感興趣的朋友可以了解下2020-09-09
這篇文章主要介紹了Python格式化壓縮后的JS文件的方法,實(shí)例分析了Python格式化文件的技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-03-03
plt.title()中文無(wú)法顯示的問(wèn)題解決
本文主要介紹了plt.title()中文無(wú)法顯示的問(wèn)題解決，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04