機器學習1k近鄰

自己一直學習計算機視覺方面的東西，現在想學習一下數據挖掘跟搜索引擎，自己基礎也有點薄弱，看朱明的那本數據挖掘，只能片面的了解這個數據挖掘。不過最近有一本書 機器學習實戰，于是乎通過實戰的形式了解一下基本的算法的執行過程。
在算法當中，很多都是相通的，模式識別、機器學習、數據挖掘、自然語言處理等等這些算法歸結起來其實差不了多少，題外話不多說了，好好學習。

k近鄰算法

對于這個算法，我用自己的話來描述一下，就是把一個未知數與所有已有的數據樣本求距離，對距離進行排序，取前k個數，這k這個數中，那個類別多，那這個未知數就屬于哪個類別。

不用說，大家也知道這個k的選取還是很重要的。先用書上最簡單的例子表述一下。

# -*- coding: utf-8 -*
from numpy import *
import operatordef createDataSet():group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])labels = ['A','A','B','B']return group, labelsdef classify0(inX, dataSet, labels, k):#行的個數也就是訓練集的個數dataSetSize = dataSet.shape[0]print ('dataSetSize:',dataSetSize)#tile表示將輸入向量inX在行方向上重復dataSetSize次，在列的方向上重復1次，具體就是構建一個跟訓練集對應的數組大小，相減就是為了求距離diffMat = tile(inX,(dataSetSize,1)) - dataSetprint('diffMat:',diffMat)sqDiffMat = diffMat**2print('sqDiffMat:',sqDiffMat)#sum默認axis=0為普通相加，axis=1為矩陣的每一個行向量相加sqDistances = sqDiffMat.sum(axis=1)print('sqDistances:',sqDistances)distances = sqDistances**0.5print('distances:',distances)sortedDistIndicies = distances.argsort()print('sortedDistIndicies:',sortedDistIndicies)#定義一個詞典classCount={}#range(k) 為[0,1,2....k-1]print('labels:',labels)for i in range(k):       voteIlabel = labels[sortedDistIndicies[i]]#獲得最小的k個長度#get 返回鍵值key對應的值；如果key沒有在字典里，則返回default參數的值，這邊default是0，功能計算每個標簽類別的個數classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1#sorted 排序是產生一個新的列表，sort是在原有基礎上排序，key按第一個域進行排序，Ture為逆序print('classCount:',classCount)sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)print('sortedClassCount:',sortedClassCount)return sortedClassCount[0][0]

這邊我已經將要解釋的地方標識了。

下面就是運行，運行結果如下：

>>> import kNN
>>> group,labels = kNN.createDataSet()
>>> kNN.classify0([0,0],group,labels,3)
('dataSetSize:', 4L)
('diffMat:', array([[-1. , -1.1],
       [-1. , -1. ],
       [ 0. ,  0. ],
       [ 0. , -0.1]]))
('sqDiffMat:', array([[ 1.  ,  1.21],
       [ 1.  ,  1.  ],
       [ 0.  ,  0.  ],
       [ 0.  ,  0.01]]))
('sqDistances:', array([ 2.21,  2.  ,  0.  ,  0.01]))
('distances:', array([ 1.48660687,  1.41421356,  0.        ,  0.1       ]))
('sortedDistIndicies:', array([2, 3, 1, 0], dtype=int64))
('labels:', ['A', 'A', 'B', 'B'])
('classCount:', {'A': 1, 'B': 2})
('sortedClassCount:', [('B', 2), ('A', 1)])
'B'

對照這個結果看上面的代碼應該都能夠看懂。

好，跟書上說得一樣，這個例子沒有實際的用處，于是書上給出了兩個實際的例子。一個是使用k-近鄰算法改進約會網站的配對效果。

算法過程，如書中：

這個例子給出了機器學習的一般過程

首先我們要知道我們要做什么，知道要做什么之后，我們要采集數據，數據采集完了之后，我們要將數據進行預處理。

1、因為我們采集過來的數據，可能面臨雜亂、重復、不完整等等原因，常見處理方法有數據集成、數據清洗、數據變換、數據歸約。

對于本例，認為數據是有效的，我們處理是數據變換，將數據變成分類器可以識別的格式。數據歸約將數據同一化，不然數據值大的就相當于權重大了，對處理有影響。

定義一個函數將文本轉換為數組

def file2matrix(filename):
    fr = open(filename)
    arrayOLines = fr.readlines()
    numberOfLines = len(arrayOLines)
    print('numberOfLines:',numberOfLines)
    returnMat = zeros((numberOfLines,3))
    print('returnMat:',returnMat)
    classLabelVector = []
    index = 0
    for line in arrayOLines:
        #沒有傳入參數時，是默認去除首尾空格
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    print('returnMat:',returnMat)
    print('classLabelVector:',classLabelVector[0:20])
    return returnMat,classLabelVector

運行結果如下：

>>> reload(kNN)
<module 'kNN' from 'E:\Machine Learning\exercise\ch02\kNN.py'>
>>> datingDataMat,datingLabels = kNN.file2matrix('datingTestSet.txt')
('numberOfLines:', 1000)
('returnMat:', array([[ 0.,  0.,  0.],
       [ 0.,  0.,  0.],
       [ 0.,  0.,  0.],
       ...,
       [ 0.,  0.,  0.],
       [ 0.,  0.,  0.],
       [ 0.,  0.,  0.]]))
('returnMat:', array([[  4.09200000e+04,   8.32697600e+00,   9.53952000e-01],
       [  1.44880000e+04,   7.15346900e+00,   1.67390400e+00],
       [  2.60520000e+04,   1.44187100e+00,   8.05124000e-01],
       ...,
       [  2.65750000e+04,   1.06501020e+01,   8.66627000e-01],
       [  4.81110000e+04,   9.13452800e+00,   7.28045000e-01],
       [  4.37570000e+04,   7.88260100e+00,   1.33244600e+00]]))
('classLabelVector:', [3, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 2, 3])

在我們進行模型選擇的時候，我們可以通過圖形化數據的方式，這樣我們可以根據一定的經驗就知道應該使用什么樣的模型。

我們通過Matplotlib來顯示圖像，這個包的安裝，直接下載這個包就可以了，如果提示你缺少什么包，補齊就好了。

根據作者使用，我們畫出玩視頻游戲所消耗的時間百分比 與每周所消費的冰淇淋公升數

>>> import matplotlib
>>> import matplotlib.pyplot as plt
>>> fig = plt.figure()
>>> ax = fig.add_subplot(111)//這邊111表示把繪圖區域分成1行*1列共1個區域，然后在區域1上創建一個軸對象
>>> ax.scatter(datingDataMat[:,1],datingDataMat[:,2])//scatter表示散點圖
<matplotlib.collections.PathCollection object at 0x00000000064DD128>
>>> plt.show()

對于這個圖很難看出有用的東西，用顏色進行標識，如下圖：

ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))

換一下屬性，x軸用每年獲取的飛行常客里程數表示，則三類分的就比較明顯了。

下面就是歸一化，不歸一化，值大的相當于權重就大，而權重的大小是應該我們去添加的，不是由值的大小來

對于歸一化，我們一般有三種處理方法。

1、[（原值-最小值）/（最大值-最小值）]*（新的最大值-新的最小值）+新的最小值。

2、（原值-均值）/標準差

3、小數的規范化，就是移動小數點位，歸化到0-1之間

我們就采用的是第一種方式，這邊我們新的最大值是1，最小值是0.我們的歸一化就是：

[（原值-最小值）/（最大值-最小值）]

def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    print('minVals:',minVals)
    print('maxVals:',maxVals)
    ranges = maxVals - minVals
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    print('m:',m)
    normDataSet = dataSet - tile(minVals,(m,1))
    normDataSet = normDataSet/tile(ranges,(m,1))
    return normDataSet,ranges,minVals

執行結果

>>> reload(kNN)
<module 'kNN' from 'E:\Machine Learning\exercise\ch02\kNN.py'>
>>> normMat,ranges,minVals = kNN.autoNorm(datingDataMat)
('minVals:', array([ 0.      ,  0.      ,  0.001156]))
('maxVals:', array([  9.12730000e+04,   2.09193490e+01,   1.69551700e+00]))
('m:', 1000L)
>>> normMat
array([[ 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]])
>>> ranges
array([  9.12730000e+04,   2.09193490e+01,   1.69436100e+00])
>>> minVals
array([ 0.      ,  0.      ,  0.001156])

為了評估算法，我們將數據分成訓練集和測試集，通常用70%的數據作為訓練集，用剩下30%的數據作為測試集。很重要的一點是訓練集和測試集均要含有各種類型的數據，通常我們要對數據進行“洗牌”，然后再分成訓練集和測試集。

下面進行測試

def datingClassTest():
    hoRatio = 0.10
    datingDataMat,datingLabels = file2matrix('datingTestSet.txt')
    normMat,ranges,minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio)
    errorCount = 0.0
    for i in range(numTestVecs):
        #這邊的意思是拿前10%的數據作為測試，后90%的數據是訓練樣本
        classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],5)
        print "the classifier came back with:%d,the real answer is: %d" %(classifierResult,datingLabels[i])
        if(classifierResult !=datingLabels[i]):
            errorCount +=1.0
    print "the total error rate is :%f" %(errorCount/float(numTestVecs))

得到的結果

>>> import kNN
>>> kNN.datingClassTest()
the classifier came back with:3,the real answer is: 3
the classifier came back with:2,the real answer is: 2
the classifier came back with:1,the real answer is: 1
。。。。。。
the classifier came back with:3,the real answer is: 3
the classifier came back with:3,the real answer is: 3
the classifier came back with:2,the real answer is: 2
the classifier came back with:2,the real answer is: 1
the classifier came back with:1,the real answer is: 1
the total error rate is :0.040000

這個結果還好，我這邊設置的k為5，k的變化結果也會變化，所有怎么選擇這個k也是值得研究的。

最后為了適合系統的使用變得直觀一點，寫下如下函數：

def classifyPerson():
    resultList = ['not at all','in small doses','in large doses']
    percentTats = float(raw_input("percentage of time spent playing video games?"))
    ffMiles = float(raw_input("frequent flier miles earned per year?"))
    iceCream = float(raw_input("liters of ice cream consumed per year?"))
    datingDataMat,datingLabels = file2matrix('datingTestSet.txt')
    normMat,ranges,minVals = autoNorm(datingDataMat)
    inArr = array([ffMiles,percentTats,iceCream])
    classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels,3)
    #這邊減1是由于最后分類的數據是1，2，3對應到數組中是0，1，2
    print "You will probably like this person: ",resultList[classifierResult -1]

運行結果如下：

>>> import kNN
>>> kNN.classifyPerson()
percentage of time spent playing video games?11
frequent flier miles earned per year?11111
liters of ice cream consumed per year?0.6
You will probably like this person:  in large doses
>>> kNN.classifyPerson()
percentage of time spent playing video games?10
frequent flier miles earned per year?10000
liters of ice cream consumed per year?0.5
You will probably like this person:  in small doses

下一個demo是手寫識別系統，書中為了簡化只設別0-9的數字。

作者這邊是將圖像數據轉化成向量

寫下如下函數：

#把圖像文本數據存入returnVect
def img2vector(filename):
    #圖像像素是32*32
    returnVect = zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0,32*i+j] = int(lineStr[j])
    return returnVect

運行查看如下：

>>> import kNN
>>> kNN.img2vector('testDigits/0_13.txt')
array([[ 0.,  0.,  0., ...,  0.,  0.,  0.]])
>>> testVector  = kNN.img2vector('testDigits/0_13.txt')
>>> testVector[0,0:31]
array([ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,
        0.,  1.,  1.,  1.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,
        0.,  0.,  0.,  0.,  0.])

分類函數已經有，下面就是測試模型

def handwritingClassTest():
    hwLabels = []
    #獲取文件目錄
    trainingFileList = listdir('trainingDigits')
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        #得到數組如[0_12,txt],[0]是第一個數據0_12
        fileStr = fileNameStr.split('.')[0]
        #得到數組如[0,12]獲得第一個數[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 range(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 "the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr)
        if (classifierResult != classNumStr): errorCount += 1.0
    print "\nthe total number of errors is: %d" % errorCount
    print "\nthe total error rate is: %f" % (errorCount/float(mTest))

最后得到的結果

>>> import kNN
>>> kNN.handwritingClassTest()
the classifier came back with: 0, the real answer is: 0
the classifier came back with: 0, the real answer is: 0
。。。。。。
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
?
the total number of errors is: 11
?
the total error rate is: 0.011628

錯誤率還是很低的，這個模型是可行的。最后作者給出k近鄰算法的不足。k近鄰算法必須保存全部數據集，訓練集大的話，占用存儲空間大，由于要對每個數據計算距離是浮點型計算，計算量大。

另外相似性的判斷是根據歐式距離來的，這樣如果計算歐式距離的屬性中如果有無關屬性或者噪音數據比較多的話，那這個測量的距離就不是真正的距離，誤差較大。解決辦法有給重要屬性的權重加大。

剛學習Python，主要以看代碼，自己照著敲代碼，思考了一下整個思路，了解了基本的Python語法。

下面繼續學習決策樹。