文章出處

kNN算法筆記

標簽（空格分隔）： 機器學習

kNN是什么

kNN算法是k-NearestNeighbor算法，也就是k鄰近算法。是監督學習的一種。所謂監督學習就是有訓練數據，訓練數據有label標好（也就是分類分好的）。kNN的思路是，對于需要測試的數據，把它和訓練集中的每個數據都進行距離計算，距離最近的前k個結果中，所對應的label出現次數最多的，就是這個測試數據所屬的label（類別）。

kNN一般步驟

按照《machine learning in action》一書中的通用步驟走一遍：

  1. 計算已知類別數據集中的點與當前點之間的距離
  2. 按照距離遞增次序排序
  3. 選取與當前點距離最小的k個點
  4. 確定前k個點所在類別的出現頻率
  5. 返回前k個點出現頻率最高的類別作為當前點的預測分類

不過按偏向程序編寫的角度來說，是：

  1. 準備訓練數據集，包括向量數據A和對應的標簽（也就是分類）
  2. 將待測數據構造成和訓練集同樣數量的一個矩陣，也就是自重復，得到B
  3. 計算A和B中每一個向量之間的距離：每一維對應相減，然后求平方和，在開根號，得到距離序列D。
  4. 從距離序列D中選取排序后的前k個，得到序列E
  5. 逐一掃描序列E，把每個元素對應的label作為key，label出現的次數作為value，邊掃描邊生成這樣的(key,value)構成的字典F
  6. 將字典F按照value排序，排序后的第一個元素value最大，表示對應的key也就是label（類別）出現次數最多，作為測試數據的預測歸類。

kNN代碼編寫

假設有四個點P1(1,1.1),P2(1,1),P3(0,0),P4(0,0.1)，分別屬于A、A類和B、B類。現在想測試Q(0,0)屬于哪個類別。畫出坐標圖，顯然是B類。使用kNN編寫程序計算，代碼如下：

#!/usr/bin/python
#coding:gbk

from numpy import *
import operator

def createDataSet():
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group, labels

def classify0(inX, dataSet, labels, k):
    """
    @param inX: 用于分類的輸入向量
    @param dataSet:訓練樣本集
    @param labels:標簽向量    len(labels)==len(dataSet)
    @param k:用于選擇最近鄰居的數目s
    """
    dataSetSize = dataSet.shape[0]      #矩陣的行數
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    #tile(inX, (dataSetSize, 1))：構造一個矩陣，行數和dataSet相同，每行都是1個inX構成
    #diffMat就是計算：構造出的矩陣與訓練集在每個維度上求差值（"距離"）  ==> 差值矩陣
    
    sqDiffMat = diffMat ** 2 #矩陣中每個元素都求平方
    
    sqDistances = sqDiffMat.sum(axis=1)  #計算每一行的sigma   axis=0:每一列   axis=1:每一行
    distances = sqDistances ** 0.5
    sortedDistIndicies = distances.argsort()  
    #np.argsort()得到的是排序后的數據原來位置的下標。
    #而distances本身并沒有被改變掉
    
    classCount={}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
        #D.get(k[,d]) -> D[k] if k in D, else d.  d defaults to None.
        #即：classCount.get(voteIlabel,0)在存在voteIlabel這個key的時候，得到classCount[voteIlabel)
        #當不存在這個key的時候，得到0。 也就是一個累加器
        
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    #itermitems():字典類型的數據所擁有的迭代器
    #operator.itemgetter(n):是定義了一個函數，通過該函數作用到對象上才能獲取值。  
    #這里itemgetter(1)取得第二列的值，也就是classCount這個字典的value。按照這個value來排序。
    #reverse=True:列表按照降序排列。
    
    return sortedClassCount[0][0]



if __name__ == '__main__':
    dataSet, labels = createDataSet()
    inX=[0,0]
    k=3
    result=classify0(inX, dataSet, labels, k)
    print result

簡單實踐：改進約會網站的配對效果

還是書上的例子，不過也算是簡單的實際應用了：每一個被邀請約會的人有四個參數(a,b,c,label)，前三個是三個維度的數據，最后一個參數是(a,b,c)組合得到的類別。現在有若干(a,b,c,label)數據，需要用kNN算法，對于給定的(a',b',c')，計算label'。

數據分布

(a,b,c)數據分布如圖所示，每一種顏色代表一個類別。
(a,b,c)數據分布如圖所示

數據歸一化

比如(a,b,c,label)序列中，a、b、c三者權重相同，而b這一維度數據的變化范圍遠遠大于a、c各自的變化范圍，此時算出的向量距離中b的權重過大。一個解決辦法是把a、b、c三個維度的數據都映射到同一個變化范圍，比如[0,1]。

def autoNorm(dataSet):
    """
    歸一化：將一系列的數值轉化為[0,1]之間的數據
    """
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    #min(0):將dataSet的列向量逐一求min，再構造為list。也就是：每一列分別求最小值，最后構成一個list
    #min(1):對行向量進行處理
    #類似于scheme中的(flatmap proc seq) = (flatmap min dataSet)，也就是map+accumulate的過程
    
    ranges = maxVals - minVals
    normDataSet = zeros((shape(dataSet)))
    m = dataSet.shape[0]   #數據行數，也就是數據條目數
    normDataSet = dataSet - tile(minVals, (m, 1))
    normDataSet = normDataSet / tile(ranges, (m, 1))
    
    return normDataSet, ranges, minVals

小插曲

用autoNorm函數計算的到的normDataSet正確運行結果如下（和書上不一樣，感覺書上結果是錯的）：

[[ 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]]

分類結果

好了，終于可以調用各函數，實現最終的計算了。這里采取前10%的數據作為測試數據，后90%的數據作為訓練數據。代碼如下：

def datingClassTest():
    """
    分類器針對約會網站的測試代碼
    """
    hoRatio = 0.10
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    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 "分類器計算出的分類為: %d, 實際分類為 is: %d"%(classifierResult, datingLabels[i])
        
        if classifierResult!=datingLabels[i]:
            errorCount += 1.0
    print "總體錯誤率為： %f"%(errorCount/float(numTestVecs))
    
if __name__ == '__main__':
    datingClassTest()

運行結果：

分類器計算出的分類為: 2, 實際分類為 is: 2
分類器計算出的分類為: 1, 實際分類為 is: 1
分類器計算出的分類為: 3, 實際分類為 is: 3
分類器計算出的分類為: 3, 實際分類為 is: 3
分類器計算出的分類為: 2, 實際分類為 is: 2
分類器計算出的分類為: 1, 實際分類為 is: 1
分類器計算出的分類為: 3, 實際分類為 is: 1
總體錯誤率為： 0.050000

總結

通過kNN算法的學習知道，算法實際步驟如下：

  1. 準備數據，包括數據本身和label（類別）標記
  2. 數據整形：讀入數據并調整為向量格式
  3. 切分數據塊。比如10%為測試數據，90%為訓練數據。
  4. 數據權重調整。如果每個維度權重相同，則可以使用歸一化方法
  5. 計算測試數據和訓練數據之間的距離
  6. 選取距離最小的k個結果，遍歷這些結果，統計對應的label頻數
  7. 將上一步得到的結果按照頻數排序，排序后第一個結果的label就是計算出的label
  8. 每一個測試數據在計算時，可同時統計錯誤率

另一個實踐：手寫識別過程

這里檢測各位數字，即0~9。手寫識別過程，經過圖像預處理，得到32*32的矩陣表示的數字，其中數字形狀區域用1表示，非數字的空白區域用0表示。訓練數據和測試數據分屬兩個文件夾下，每個文件都是只有一個數字的txt文件，文件命名有規律：文件對應的數字+不重復的序號。

首先是將32*32的二維數組轉換為一維的數組，也就是1024維的一個行向量。同時從文件名中取出當前向量對應的類別。這樣就完成了訓練集的操作。

對于測試集，用同樣的方式先構造1024維的向量，然后每一個都通過kNN的分類器函數classify0()來計算其label（分類），并統計誤差。

def img2vector(filename):
    vector=zeros(1024)
    fr = open(filename)
    for i in xrange(32):
        lineStr = fr.readline()
        for j in xrange(32):
            vector[32*i+j] = int(lineStr[j])
    return vector

def simple_img2vector_test():
    testVector = img2vector('testDigits/0_13.txt')
    print testVector[0:31]
    
def handwritingClassTest():
    hwLabels=[]
    trainingFileList=listdir('trainingDigits')
    m=len(trainingFileList)
    trainingMat=zeros((m, 1024))
    for i in xrange(m):
        fileNameStr=trainingFileList[i]
        fileStr=fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i,:]=img2vector('trainingDigits/%s'%fileNameStr)
    testFileList=listdir('testDigits')
    errorCount=0.0
    mTest=len(testFileList)
    for i in xrange(mTest):
        fileNameStr=testFileList[i]
        fileStr=fileNameStr.split('.')[0]
        classNumStr=int(fileStr.split('_')[0])
        vectorUnderTest=img2vector('testDigits/%s'%fileNameStr)
        classifierResult=classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print "分類器計算出的類別為： %d, 實際類別為： %d" % (classifierResult, classNumStr)
        if classifierResult!=classNumStr:
            errorCount += 1.0
    print "\n計算錯誤的總次數為: %d"%errorCount
    print "\n總錯誤率為： %f"%(errorCount/float(mTest))
        
    
if __name__ == '__main__':
    handwritingClassTest()

運行結果：

分類器計算出的類別為： 9, 實際類別為： 9
分類器計算出的類別為： 9, 實際類別為： 9
分類器計算出的類別為： 9, 實際類別為： 9
分類器計算出的類別為： 9, 實際類別為： 9
分類器計算出的類別為： 9, 實際類別為： 9
分類器計算出的類別為： 9, 實際類別為： 9
分類器計算出的類別為： 9, 實際類別為： 9
分類器計算出的類別為： 9, 實際類別為： 9

計算錯誤的總次數為: 11

總錯誤率為： 0.011628

文章列表


不含病毒。www.avast.com
arrow
arrow
    全站熱搜
    創作者介紹
    創作者 大師兄 的頭像
    大師兄

    IT工程師數位筆記本

    大師兄 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄