使用python實(shí)現(xiàn)kNN分類算法

更新時(shí)間：2019年10月16日 11:41:30 作者：stridehuan

這篇文章主要為大家詳細(xì)介紹了使用python實(shí)現(xiàn)kNN分類算法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

k-近鄰算法是基本的機(jī)器學(xué)習(xí)算法，算法的原理非常簡(jiǎn)單：

輸入樣本數(shù)據(jù)后，計(jì)算輸入樣本和參考樣本之間的距離，找出離輸入樣本距離最近的k個(gè)樣本，找出這k個(gè)樣本中出現(xiàn)頻率最高的類標(biāo)簽作為輸入樣本的類標(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è)類標(biāo)簽，包含兩類（RB和NRB）。我選取800條樣本作為參考樣本，剩下的作為測(cè)試樣本。

下面是分類器的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：類標(biāo)簽的在整個(gè)樣本向量中的下標(biāo)
numOfClSamples:選出來(lái)進(jìn)行投票的樣本個(gè)數(shù)
返回值：
類標(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è)類標(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ù)組（距離和類標(biāo)簽），而refSamples數(shù)組用于保存離輸入樣本最近的numOfRefSamples個(gè)參考樣本。當(dāng)所有樣本都讀完之后，就找出了離輸入樣本最近的numOfRefSamples個(gè)參考樣本。其中kNNFunction.insertItem函數(shù)實(shí)現(xiàn)的是將得到的新樣本插入到refSamples數(shù)組中，主要采用類似冒泡排序的方法，實(shí)現(xiàn)代碼如下：

'''
insertItem(refSamples, numOfRefSamples, disAndLabel)函數(shù)
功能：
在參考樣本集中插入新樣本，這里的樣本是一個(gè)包含兩個(gè)數(shù)值的list，第一個(gè)是距離，第二個(gè)是類標(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

至此為止，分類器算是完成，接下去就是用剩下的測(cè)試集進(jìn)行測(cè)試，計(jì)算分類的準(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 '分類準(zhǔn)確率為：',accuracy

輸出結(jié)果為：

分類準(zhǔn)確率為： 0.847058823529

可見(jiàn)用kNN這種分類器的對(duì)這個(gè)數(shù)據(jù)集的分類效果其實(shí)還是比較一般的，而且根據(jù)我的測(cè)試，分類函數(shù)kNNClassify中numOfRefSamples（其實(shí)就是k-近鄰中k）的取值對(duì)分類準(zhǔn)確度也有明顯的影響，大概在k取5的時(shí)候，分類效果比較理想，并不是越大越好。下面談?wù)勎覍?duì)這個(gè)問(wèn)題的理解：

首先，kNN算法是一種簡(jiǎn)單的分類算法，不需要任何訓(xùn)練過(guò)程，在樣本數(shù)據(jù)的結(jié)構(gòu)比較簡(jiǎn)單邊界比較明顯的時(shí)候，它的分類效果是比較理想的，比如:

當(dāng)k的取值比較大的時(shí)候，在某些復(fù)雜的邊界下會(huì)出現(xiàn)很差的分類效果，比如下面的情況下很多藍(lán)色的類會(huì)被分到紅色中，所以要用比較小的k才會(huì)有相對(duì)較好的分類效果：

但是當(dāng)k取得太小也會(huì)使分類效果變差，比如當(dāng)不同類的樣本數(shù)據(jù)之間邊界不明顯，存在交叉的時(shí)候，比如：

總的來(lái)說(shuō)，kNN分類算法是一種比較原始直觀的分類算法，對(duì)某些簡(jiǎn)單的情況有比較好的分類效果，并且不需要訓(xùn)練模型。但是它的缺點(diǎn)是分類過(guò)程的運(yùn)算復(fù)雜度很高，而且當(dāng)樣本數(shù)據(jù)的結(jié)構(gòu)比較復(fù)雜的時(shí)候，它的分類效果不理想。用kNN算法對(duì)本次實(shí)驗(yàn)中的數(shù)據(jù)集的分類效果也比較一般，不過(guò)我試過(guò)其它更簡(jiǎn)單一些的數(shù)據(jù)集，確實(shí)還是會(huì)有不錯(cuò)的分類準(zhǔn)確性的，這里就不贅述了。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: