文章原創(chuàng),最近更新：2018-08-7

本章節(jié)的主要內容是:
重點介紹項目案例1: 優(yōu)化約會網站的配對效果中的 KNN算法。

1.KNN項目案例介紹:

項目案例1:

優(yōu)化約會網站的配對效果

項目概述:

1）海倫使用約會網站尋找約會對象。經過一段時間之后，她發(fā)現曾交往過三種類型的人: 不喜歡的人、魅力一般的人、 極具魅力的人。
2）她希望： 1. 工作日與魅力一般的人約會 2. 周末與極具魅力的人約會 3. 不喜歡的人則直接排除掉。現在她收集到了一些約會網站未曾記錄的數據信息，這更有助于匹配對象的歸類。

開發(fā)流程：

• 收集數據：提供文本文件
• 準備數據：使用 Python 解析文本文件
• 分析數據：使用 Matplotlib 畫二維散點圖
• 訓練算法：此步驟不適用于 k-近鄰算法
• 測試算法：使用海倫提供的部分數據作為測試樣本。
  測試樣本和非測試樣本的區(qū)別在于：測試樣本是已經完成分類的數據，如果預測分類與實際類別不同，則標記為一個錯誤。
• 使用算法：產生簡單的命令行程序，然后海倫可以輸入一些特征數據以判斷對方是否為自己喜歡的類型。

數據集介紹

海倫把這些約會對象的數據存放在文本文件 datingTestSet2.txt (數據來源于《機器學習實戰(zhàn)》第二章 k鄰近算法)中，總共有 1000 行。

本文使用的數據主要包含以下三種特征：每年獲得的飛行常客里程數，玩視頻游戲所耗時間百分比，每周消費的冰淇淋公升數。其中分類結果作為文件的第四列，并且只有3、2、1三種分類值。datingTestSet2.csv文件格式如下所示：

數據在datingTestSet2.txt文件中的格式如下所示：

2.KNN算法代碼

首先創(chuàng)建一個名為kNN.py的文件,再創(chuàng)建一個函數，這個函數返回一個矩陣和標簽列表，以方便我們后續(xù)對K近鄰(KNN)算法進行檢驗。

def createDataSet():
    """
    創(chuàng)建數據集和標簽

     調用方式
     import kNN
     group, labels = kNN.createDataSet()
    """
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels

下面這段代碼就是kNN算法，目的就是為了找最近的距離

def classify0(inX,dataSet,labels,k):
    """
    inX:用于分類的輸入向量
    dataSet:輸入的訓練樣本集
    lables:標簽向量
    k:表示用于選擇最近鄰居的數目
    
    預測數據所在分類可在輸入下列命令
    kNN.classify0([0,0], group, labels, 3)
    """
    # array的shape函數返回指定維度的大小，如dataset為n*m的矩陣，
    # 則dataset.shape[0]返回n,dataset.shape[1]返回m,dataset.shape返回n,m
    dataSetSize = dataSet.shape[0]
    # tile函數簡單的理解，它的功能是重復某個數組。比如tile(A,n)，功能是將數組A重復n次，構成一個新的數組
    # 所以此處tile(inX,(dataSetSize,1))的作用是將inX重復復制dataSetSize次，以便與訓練樣本集的樣本個數一致
    # 減去dataSet就是求出其差值，所以diffMat為一個差值矩陣
    diffmat=np.tile(inX,(dataSetSize,1))-dataSet
    #距離度量,度量公式為歐氏距離
    sqdiffmat=diffmat**2
    # 將矩陣的每一行相加,axis用于控制是行相加還是列相加
    sqdistances=sqdiffmat.sum(axis=1)
    #開方
    distances=sqdistances**0.5
    # 根據距離排序從小到大的排序，返回對應的索引位置
    sortedDistIndicies=distances.argsort()
    # 選擇距離最小的k個點
    classcount={}
   
    for i in range(k):
        # 找到該樣本標簽的類型
        voteIlabel=labels[sortedDistIndicies[i]]
        # 字典的get方法,list.get(k,d) 其中 get相當于一條if...else...語句,參數k在字典中，字典將返回list[k];如果參數k不在字典中則返回參數d
        classcount[voteIlabel]=classcount.get(voteIlabel,0)+1
        # 字典的 items() 方法，以列表返回可遍歷的(鍵，值)元組數組。
        # sorted 中的第2個參數 key=operator.itemgetter(1) 這個參數的意思是先比較第幾個元素
        sortedClasscount = sorted(classcount.items(),key=operator.itemgetter(1),reverse=True)
        # 返回最符合的標簽
        return sortedClasscount[0][0]

測試代碼及其結果如下:

>import kNN
>group,labels=kNN.createDataSet()
>kNN.classify0([0,0],group,labels,3)

'B'

3.KNN算法相關知識點

知識點1:歐氏距離

計算兩個向量點xA和xB之間的距離,叫做歐氏距離公式,具體如下:
d=\sqrt{(xA_{0}-xB_{0})^{2}+(xA_{1}-xB_{1})^{2}}
例如，點(0,0)與(1,2)之間的距離計算為：
\sqrt{(0-1)^{2}+(1-2)^{2}}
舉個小案例,首先求點與點之間的距離,具體如下

• 第一行： 同一個點 到 dataSet的第一個點的距離。
• 第二行： 同一個點 到 dataSet的第二個點的距離。
• ...
• 第N行： 同一個點 到 dataSet的第N個點的距離。
  
  
  由此可以得到截圖的歐氏距離是:
  a_{1}=\sqrt{(x-1)^{2}+(y-1)^{2}}
  a_{2}=\sqrt{(x-1.1)^{2}+(y-1)^{2}}
  a_{3}=\sqrt{(x-0)^{2}+(y-0)^{2}}
  a_{4}=\sqrt{(x-0)^{2}+(y-0.1)^{2}}

知識點2:關于operator模塊的運用

operator模塊是python中內置的操作符函數接口，它定義了一些算術和比較內置操作的函數。operator模塊是用c實現的，所以執(zhí)行速度比python代碼快。

知識點3:numpy中c.shape[0]的理解

建立一個4×2的矩陣c, c.shape[0] 為第一維的長度4(相當于行)，c.shape[1] 為第二維的長度2(相當于列)。

import numpy as np
group = np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])

group
Out[21]: 
array([[ 1. ,  1.1],
       [ 1. ,  1. ],
       [ 0. ,  0. ],
       [ 0. ,  0.1]])

group.shape
Out[22]: (4, 2)

group.shape[0]
Out[23]: 4

group.shape[1]
Out[24]: 2

知識點4:numpy中的tile函數

numpy.tile(A,B)函數,作用使數組A重復B次，這里的B可以時int類型也可以是元組類型。

import numpy as np

np.tile([0,1],2)#在列方向上重復[0,1]2次，默認行1次
Out[26]: array([0, 1, 0, 1])

np.tile([0,1],(1,1))#在列方向上重復[0,1]1次，行1次
Out[27]: array([[0, 1]])

np.tile([0,1],(2,1))#在列方向上重復[0,1]1次，行2次
Out[28]: 
array([[0, 1],
       [0, 1]])

np.tile([0,1],(2,2)))#在列方向上重復[0,1]2次，行2次
Out[29]: 
array([[0, 1, 0, 1],
       [0, 1, 0, 1]])

np.tile([0,1],(3,2)))#在列方向上重復[0,1]2次，行3次
Out[30]: 
array([[0, 1, 0, 1],
       [0, 1, 0, 1],
       [0, 1, 0, 1]])

知識點5:關于diffMat=np.tile(inX,(dataSetSize,1))-dataSet這段代碼的理解

舉了一個小案例,具體可以參見如下案例:

import numpy as np

dataSet = np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])

dataSet
Out[47]: 
array([[ 1. ,  1.1],
       [ 1. ,  1. ],
       [ 0. ,  0. ],
       [ 0. ,  0.1]])

inX=np.array([0,1])

inX
Out[49]: array([0, 1])

dataSetSize=dataSet.shape[0]

dataSetSize
Out[51]: 4

tile(inX, (dataSetSize,1))
Out[53]: 
array([[0, 1],
       [0, 1],
       [0, 1],
       [0, 1]])

diffMat=tile(inX, (dataSetSize,1))-group

diffMat
Out[55]: 
array([[-1. , -0.1],
       [-1. ,  0. ],
       [ 0. ,  1. ],
       [ 0. ,  0.9]])

相當于截圖,如下:

知識點6:python中的sum函數.sum(axis=1)

我們平時用的sum應該是默認的矩陣所有的值相加;axis=1表示按列求和，即把每一行的元素加起來;axis=0表示按行求和，即把每一列的元素加起來

• axis = 0代表行相加
• axis = 1 代表列相加

import numpy as np
a=np.array([[0,2,1],[5,4,2]])

a
Out[59]: 
array([[0, 2, 1],
       [5, 4, 2]])

a.sum()
Out[60]: 14

a.sum(axis=0)
Out[61]: array([5, 6, 3])

a.sum(axis=1)
Out[62]: array([ 3, 11])

知識點7:numpy.argsort函數

返回值為從小到大的數字對應的index, 其中 axis = 0沿著行比較，即第一行和第二行的數比較，axis = 1 為沿著列比較，即第一列和第二列的比較。通過參數sort 還可以選擇排序方法.

a=np.array([5,4,7])

a
Out[64]: array([5, 4, 7])

np.argsort(a)
Out[65]: array([1, 0, 2], dtype=int64)

a
Out[68]: 
array([[1, 5],
       [3, 2]])

np.argsort(a,axis=0)
Out[69]: 
array([[0, 1],
       [1, 0]], dtype=int64)

np.argsort(a,axis=1)
Out[70]: 
array([[0, 1],
       [1, 0]], dtype=int64)

知識點8:classCount = {}

其中{}表示生成的是字典，在字典這個類中，有方法get，對classCount元素賦值，其實是個計數器

知識點9:字典的 get 函數

d.get（k，< default>）,表示鍵k存在，則返回相應值，不在則返回< default>值

在這里主要是利用dictionary的get( ) 方法做計數統(tǒng)計,具體小案例如下:
案例1
假設統(tǒng)計 s="aabbccc"中，每個字符出現的次數：
結果應當為："a":2, "b":2, "c":3

s="aabbccc"
dic={}
for ch in s:
    dic[ch]=1+dic.get(ch,0)
    
print(dic)
{'a': 2, 'b': 2, 'c': 3}

案例2

a={5:2,3:4}

a.get(3,0)
Out[35]: 4

a.get(1,0)
Out[36]: 0

知識點10:字典的items函數

d.items()以列表返回可遍歷的(鍵, 值) 元組數組

dict = {'Name': 'Runoob', 'Age': 7}

print ("Value : %s" %  dict.items())
Value : dict_items([('Name', 'Runoob'), ('Age', 7)])

知識點11:Python sorted() 函數

sorted() 函數對所有可迭代的對象進行排序操作。

具體sorted 語法,如下:

sorted(iterable[, cmp[, key[, reverse]]])

參數說明：

• iterable -- 可迭代對象。
• cmp -- 比較的函數，這個具有兩個參數，參數的值都是從可迭代對象中取出，此函數必須遵守的規(guī)則為，大于則返回1，小于則返回-1，等于則返回0。
• key -- 主要是用來進行比較的元素，只有一個參數，具體的函數的參數就是取自于可迭代對象中，指定可迭代對象中的一個元素來進行排序。
• reverse -- 排序規(guī)則，reverse = True 降序 ， reverse = False 升序（默認）。

具體可參見:菜鳥教程之Python sorted() 函數

具體用法如下:

>>>a = [5,7,6,3,4,1,2]
>>> b = sorted(a)       # 保留原列表
>>> a 
[5, 7, 6, 3, 4, 1, 2]
>>> b
[1, 2, 3, 4, 5, 6, 7]
 
>>> L=[('b',2),('a',1),('c',3),('d',4)]
>>> sorted(L, cmp=lambda x,y:cmp(x[1],y[1]))   # 利用cmp函數
[('a', 1), ('b', 2), ('c', 3), ('d', 4)]
>>> sorted(L, key=lambda x:x[1])               # 利用key
[('a', 1), ('b', 2), ('c', 3), ('d', 4)]
 
 
>>> students = [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
>>> sorted(students, key=lambda s: s[2])            # 按年齡排序
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
 
>>> sorted(students, key=lambda s: s[2], reverse=True)       # 按降序
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
>>>

而這里所涉及到的知識點,具體用法可以有以下兩種:
key為函數，指定取待排序元素的哪一項進行排序，函數用上面的例子來說明，代碼如下：
方法一

sorted(classcount.items(),key=lambda classcount.item :classcount.item[1],reverse=True)

key指定的lambda函數功能是去元素classcount.item的第二個域（即：classcount.item[1],），因此sorted排序時，會以classcount.items所有元素的第二個域來進行排序。

方法二
有了下面的operator.itemgetter函數，也可以用該函數來實現，例如要通過student的第三個域排序，可以這么寫：

sorted(classcount.items(),key=operator.itemgetter(1),reverse=True)

知識點12:operator.itemgetter函數

operator模塊提供的itemgetter函數用于獲取對象的哪些維的數據，參數為一些序號（即需要獲取的數據在對象中的序號），下面看例子。
案例1

import operator
a=[1,2,3,4]
b=operator.itemgetter(0)

b(a)
Out[82]: 1

b=operator.itemgetter(1)

b(a)
Out[84]: 2

案例2

a=[('b',2),('a',1),('c',0)]
b=sorted(a,key=operator.itemgetter(1))

b
Out[39]: [('c', 0), ('a', 1), ('b', 2)]
#可以看到排序是按照后邊的0,1,2進行排序的，而不是a,b,c

b=sorted(a,key=operator.itemgetter(0))

b
Out[41]: [('a', 1), ('b', 2), ('c', 0)]
#這次比較的是前邊的a,b,c而不是0,1,2

b=sorted(a,key=operator.itemgetter(1,0))

b
Out[44]: [('c', 0), ('a', 1), ('b', 2)]
#這個是先比較第2個元素，然后對第一個元素進行排序，形成多級排序。