2-1节 k-近邻算法-KNN算法|优化约会网站的配对效果项目|

文章原创,最近更新：2018-08-7

本章节的主要内容是:
重点介绍项目案例1: 优化约会网站的配对效果中的 KNN算法。

1.KNN项目案例介绍:

项目案例1:

优化约会网站的配对效果

项目概述:

1）海伦使用约会网站寻找约会对象。经过一段时间之后，她发现曾交往过三种类型的人: 不喜欢的人、魅力一般的人、 极具魅力的人。
2）她希望： 1. 工作日与魅力一般的人约会 2. 周末与极具魅力的人约会 3. 不喜欢的人则直接排除掉。现在她收集到了一些约会网站未曾记录的数据信息，这更有助于匹配对象的归类。

开发流程：

• 收集数据：提供文本文件
• 准备数据：使用 Python 解析文本文件
• 分析数据：使用 Matplotlib 画二维散点图
• 训练算法：此步骤不适用于 k-近邻算法
• 测试算法：使用海伦提供的部分数据作为测试样本。
  测试样本和非测试样本的区别在于：测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。
• 使用算法：产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。

数据集介绍

海伦把这些约会对象的数据存放在文本文件 datingTestSet2.txt (数据来源于《机器学习实战》第二章 k邻近算法)中，总共有 1000 行。

本文使用的数据主要包含以下三种特征：每年获得的飞行常客里程数，玩视频游戏所耗时间百分比，每周消费的冰淇淋公升数。其中分类结果作为文件的第四列，并且只有3、2、1三种分类值。datingTestSet2.csv文件格式如下所示：

飞行里程数	游戏耗时百分比	冰淇淋公升数	分类结果
40920	8.326976	0.953952	3
14488	7.153469	1.673904	2
26052	1.441871	0.805124	1

数据在datingTestSet2.txt文件中的格式如下所示：

2.KNN算法代码

首先创建一个名为kNN.py的文件,再创建一个函数，这个函数返回一个矩阵和标签列表，以方便我们后续对K近邻(KNN)算法进行检验。

def createDataSet():
    """
    创建数据集和标签

     调用方式
     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实现的，所以执行速度比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( ) 方法做计数统计,具体小案例如下:
案例1
假设统计 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 -- 比较的函数，这个具有两个参数，参数的值都是从可迭代对象中取出，此函数必须遵守的规则为，大于则返回1，小于则返回-1，等于则返回0。
• key -- 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。
• reverse -- 排序规则，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个元素，然后对第一个元素进行排序，形成多级排序。