k近邻算法原理以及改进约会网站的配对效果

云计算 waitig 455℃ 百度已收录 0评论
  • k近邻分类算法
  • 从文本文件中解析和导入数据
  • 使用Matplotlib创建扩散图
  • 归一化数值

原理

众所周知,电影可以按照题材分类,然而题材本身是如何定义的?由谁来判定某部电影属于哪个题材?也就是说同一题材的电影具有哪些公共特征?这些都是在进行电影分类时必须要考虑的问题。没有哪个电影人会说自己制作的电影和以前的某部电影类似,但我们确实知道每部电影在风格上的确有可能会和同题材的电影相近。那么动作片具有哪些共有特征,使得动作片之间非常类似,而与爱情片存在着明显的差别呢?动作片中也会存在接吻镜头,爱情片中也会存在打斗场景,我们不能单纯依靠是否存在打斗或者亲吻来判断影片的类型。但是爱情片中的亲吻镜头更多,动作片中的打斗场景也更频繁,基于此类场景在某部电影中出现的次数可以用来进行电影分类。本章第一节基于电影中出现的亲吻、打斗出现的次数,使用k近邻算法构造程序,自动划分电影的题材类型。我们首先使用电影分类讲解k近邻算法的基本概念,然后学习如何在其他系统上使用k近邻算法。

本章介绍第一个机器学习算法:k近邻算法,它非常有效而且易于掌握。首先,我们将探讨k近邻算法的基本理论,以及如何使用距离测量的方法分类物品;接着,我们将使用Python从文本文件中导入并解析数据;然后,本书讨论了当存在许多数据来源时,如何避免计算距离时可能碰到的一些常见错误;最后,利用实际的例子讲解如何使用k近邻算法完成手写数字识别系统。

k-近邻算法概述

简单地说,k近邻算法采用测量不同特征值之间的距离方法进行分类。

k-近邻算法

  • 优点:精度高、对异常值不敏感、无数据输入假定。
  • 缺点:计算复杂度高、空间复杂度高。 适用数据范围:数值型和标称型。

    它的工作原理是:存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似数据(最近邻)的分类标签。一般来说,我们只选择样本数据集中前k个最相似的数据,这就是k-近邻算法中k的出处,通常k是不大于20的整数。最后,选择k个最相似数据中出现次数最多的分类,作为新数据的分类。

    现在我们回到前面电影分类的例子,使用k近邻算法分类爱情片和动作片。有人曾经统计过很多电影的打斗镜头和接吻镜头,图2-1显示了6部电影的打斗和接吻镜头数。假如有一部未看过的电影,如何确定它是爱情片还是动作片呢?我们可以使用kNN来解决这个问题。

此处输入图片的描述

首先我们需要知道这个未知电影存在多少个打斗镜头和接吻镜头,图2-1中问号位置是该未知电影出现的镜头数图形化展示,具体数字参见表2-1。

电影名称打斗镜头接吻镜头电影类型
California Man3104爱情片
He’s Not Really into Dudes2100爱情片
Beautiful Woman181爱情片
Kevin Longblade10110动作片
Robo Slayer 3000995动作片
Amped II982动作片
?1890未知

即使不知道未知电影属于哪种类型,我们也可以通过某种方法计算出来。首先计算未知电影与样本集中其他电影的距离,如表2-2所示。此处暂时不要关心如何计算得到这些距离值,使用Python实现电影分类应用时,会提供具体的计算方法。

电影名称与未知电影的距离
California Man20.5
He’s Not Really into Dudes18.7
Beautiful Woman19.2
Kevin Longblade115.3
Robo Slayer 3000117.4
Amped II118.9

现在我们得到了样本集中所有电影与未知电影的距离,按照距离递增排序,可以找到k个距离最近的电影。假定k=3,则三个最靠近的电影依次是He’s Not Really into Dudes、Beautiful Woman和California Man。k近邻算法按照距离最近的三部电影的类型,决定未知电影的类型,而这三部电影全是爱情片,因此我们判定未知电影是爱情片。

本章主要讲解如何在实际环境中应用k近邻算法,同时涉及如何使用Python工具和相关的机器学习术语。按照1.5节开发机器学习应用的通用步骤,我们使用Python语言开发k近邻算法的简单应用,以检验算法使用的正确性。

k近邻算法的一般流程

  1. 收集数据:可以使用任何方法。
  2. 准备数据:距离计算所需要的数值,最好是结构化的数据格式。
  3. 分析数据:可以使用任何方法。
  4. 训练算法:此步骤不适用于k近邻算法。
  5. 测试算法:计算错误率。
  6. 使用算法:首先需要输入样本数据和结构化的输出结果,然后运行k近邻算法判定输入数据分别属于哪个分类,最后应用对计算出的分类执行后续的处理。
准备:使用Python导入数据
  • 首先创建文件夹Practice-KNN作为主文件夹,在其下创建子文件夹knn并于其中创建__init__.py
  • 接着在knn下创建createDataSet文件,其内容如下:
# -*- coding:utf-8 -*-

import numpy as np

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

在文件夹Practice-KNN下打开ipython

In [2]: from knn.createDataSet import createDataSet

上述命令导入kNN模块。为了确保输入相同的数据集,kNN模块中定义了函数createDataSet,在Python命令提示符下输入下列命令:

In [3]: groups, labels = createDataSet()

上述命令创建了变量grouplabels,在Python命令提示符下输入下列命令,输入变量的名字以检验是否正确地定义变量:

In [4]: groups
Out[4]:
array([[ 1. ,  1.1],
       [ 1. ,  1. ],
       [ 0. ,  0. ],
       [ 0. ,  0.1]])

In [5]: labels
Out[5]: ['A', 'A', 'B', 'B']

这里有4组数据,每组数据有两个我们已知的属性或者特征值。上面的group矩阵每行包含一个不同的数据,我们可以把它想象为某个日志文件中不同的测量点或者入口。由于人类大脑的限制,我们通常只能可视化处理三维以下的事务。因此为了简单地实现数据可视化,对于每个数据点我们通常只使用两个特征。

向量labels包含了每个数据点的标签信息,labels包含的元素个数等于group矩阵行数。这里我们将数据点(1, 1.1)定义为类A,数据点(0, 0.1)定义为类B。为了说明方便,例子中的数值是任意选择的,并没有给出轴标签,图2-2是带有类标签信息的四个数据点。

此处输入图片的描述

现在我们已经知道Python如何解析数据,如何加载数据,以及kNN算法的工作原理,接下来我们将使用这些方法完成分类任务。

从文本文件中解析数据

这里给出k近邻算法的伪代码和实际的Python代码,然后详细地解释每行代码的含义。该函数的功能是使用K-近邻算法将 每组数据划分到某个类中,其伪代码如下:

对未知类别属性的数据集中的每个点依次执行以下操作:

(1) 计算已知类别数据集中的点与当前点之间的距离;

(2) 按照距离递增次序排序;

(3) 选取与当前点距离最小的K个点;

(4) 确定前K个点所在类别的出现频率;

(5) 返回前K个点出现频率最高的类别作为当前点的预测分类。

在目录knn之下创建classify0程序实现如下:

# -*- coding:utf-8 -*-

import numpy as np
import operator


def classify0(inX, dataSet, labels, k):
    '''
    :inX,       用于分类的输出向量
    :dataSet,   训练样本集
    :labels,    标签向量
    :k,         用于选择最近邻居的数目
    '''
    # 获取训练集的向量数目
    dataSetSize = dataSet.shape[0]
    # 先对向量进行广播至与训练集相同的维度,接着求两者的Hamming距离矩阵
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    # 对每个维度差进行平方
    sqDiffMat = diffMat ** 2
    # 求每一行的和
    sqDistances = sqDiffMat.sum(axis=1)
    # 开方即得到欧氏距离
    distances = sqDistances ** 0.5
    # 得到依据原先大小升序排序后的索引
    sortedDistIndicies = distances.argsort()
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        # 类别计数加一
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    # 降序排列后的类别排序,元组
    sortedClassCount = sorted(classCount.iteritems(),
                              key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

计算完所有点之间的欧氏距离后,可以对数据按照从小到大的次序排序。然后,确定前K个距离 最小元素所在的主要分类;最后,将classCount字典分解为元组列表,然后 使用程序第二行导入运算符模块的itemgetter方法,按照第二个元素的次序对元组进行排序 此处的排序为逆序,即按照从最大到最小次序排序,最后返回发生频率最高的元素标签。

如何测试分类器

在上文中我们提到使用kNN 算法能够判断出一个电影是动作片还是爱情片,即我们使用 kNN 算法能够实现一个分类器。我们需要检验分类器给出的答案是否符合我们的预期。读者可能会问:“分类器何种情况下会出错?”或者“答案是否总是正确的?”答案是否定的,分类器并不会得到百分百正确的结果,我们可以使用多种方法检测分类器的正确率。此外分类器的性能也会受到多种因素的影响,如分类器设置和数据集等。不同的算法在不同数据集上的表现可能完全不同,这也是本部分的6章都在讨论分类算法的原因所在。

为了测试分类器的效果,我们可以使用已知答案的数据,当然答案不能告诉分类器,检验分类器给出的结果是否符合预期结果。通过大量的测试数据,我们可以得到分类器的错误率——分类器给出错误结果的次数除以测试执行的总数。错误率是常用的评估方法,主要用于评估分类器在某个数据集上的执行效果。完美分类器的错误率为0,最差分类器的错误率是1.0,在这种情况下,分类器根本就无法找到一个正确答案。读者可以在后面章节看到实际的数据例子。

上一节介绍的例子已经可以正常运转了,但是并没有太大的实际用处,本章的后两节将在现 实世界中使用K-近邻算法。首先,我们将使用K-近邻算法改进约会网站的效果,然后使用K-近邻算法改进手写识别系统。本书将使用手写识别系统的测试程序检测”近邻算法的效果

示例:使用K-近邻算法改进约会网站的配对效果

示例:在约会网站上使用卜近邻算法

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

海伦收集约会数据已经有了一段时间,她把这些数据存放在文本文件datingTestSet.txt之中,每 个样本数据占据一行,总共有1000行。海伦的样本主要包含以下3种特征:

  • 每年获得的飞行常客里程数
  • 玩视频游戏所耗时间百分比
  • 每周消费的冰淇淋公升数

在目录knn之下创建file2matrix用于将文本数据转换成矩阵,文件内容如下:

# -*- coding:utf-8 -*-


import numpy as np


def file2matrix(filename):
    with open(filename) as fr:
        arrayOLines = fr.readlines()
    numberOfLines = len(arrayOLines)
    returnMat = np.zeros((numberOfLines, 3))
    classLabelVector = {}
    index = 0
    for line in arrayOLines:
        line = line.strip()
        listFromLine = line.split()
        returnMat[index, :] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat, classLabelVector

从上面的代码可以看到,Python处理文本文件非常容易。首先我们需要知道文本文件包含多少行。打开文件,得到文件的行数0。然后创建以零填充的矩阵NumPy (实际上,NumPy是一 个二维数组,这里暂时不用考虑其用途)。为了简化处理,我们将该矩阵的另一维度设置为固定 值3,你可以按照自己的实际需求增加相应的代码以适应变化的输人值。循环处理文件中的每行数据,首先使用函数line.strip截取掉所有的回车字符,然后使用tab字符\t将上一步得 到的整行数据分割成一个元素列表。接着,我们选取前3个元素,将它们存储到特征矩阵中。Python 语言可以使用索引值-1表示列表中的最后一列元素,利用这种负索引,我们可以很方便地将列表 的最后一列存储到向量classLabelVector中。需要注意的是,我们必须明确地通知解释器,告诉它列表中存储的元素值为整型,否则Python语言会将这些元素当作字符串处理。以前我们必须自己处理这些变量值类型问题,现在这些细节问题完全可以交给NumPy函数库来处理。

ipython命令提示符下输人下面命令:

In [7]: datingDataMat, datingLabels = file2matrix('data/datingTestSet2.txt')

成功导人datingTestSet2.txt文件中的数据之后,可以简单检查一下数据内容。Python的输出结 果大致如下:

In [8]: datingDataMat
Out[8]:
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]])

In [9]: datingLabels[:20]
Out[9]: [3, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 2, 3]

现在已经从文本文件中导人了数据,并将其格式化为想要的格式,接着我们需要了解数据的真实含义。当然我们可以直接浏览文本文件,但是这种方法非常不友好,一般来说,我们会采用 图形化的方式直观地展示数据。下面就用Python工具来图形化展示数据内容,以便辨识出一些数据模式。

分析数据:使用Matplotlib创建散点图

ipython中输入如下代码:

'''
Created on Oct 6, 2017

@author: 1/inf
'''
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
from file2matrix import file2matrix

matplotlib.rcParams['font.family'] = 'SimHei'

datingDataMat, datingLabels = file2matrix('../datingTestSet2.txt')
datingLabels0 = np.asarray(datingLabels, dtype=float)

class1 = (datingLabels0 == 1)
class2 = (datingLabels0 == 2)
class3 = (datingLabels0 == 3)

fig = plt.figure()
ax = fig.add_subplot(111)

type1 = ax.scatter(datingDataMat[:, 1][class1], datingDataMat[:, 2][class1])
type2 = ax.scatter(datingDataMat[:, 1][class2], datingDataMat[:, 2][class2])
type3 = ax.scatter(datingDataMat[:, 1][class3], datingDataMat[:, 2][class3])
ax.legend([type1, type2, type3], ["极具魅力", "魅力一般", "不喜欢"], loc=1)

plt.xlabel('玩视频游戏所耗时间百分比', fontproperties='SimHei', fontsize='14')
plt.ylabel('每周消费的冰淇淋公升数', fontproperties='SimHei', fontsize='14')
plt.show()

显示如下:

ipython中输入如下代码:

'''
Created on Oct 6, 2017

@author: 1/inf
'''
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
from file2matrix import file2matrix

matplotlib.rcParams['font.family'] = 'SimHei'

datingDataMat, datingLabels = file2matrix('../datingTestSet2.txt')
datingLabels0 = np.asarray(datingLabels, dtype=float)

class1 = (datingLabels0 == 1)
class2 = (datingLabels0 == 2)
class3 = (datingLabels0 == 3)

# print(datingDataMat[:, 1][class1])

fig = plt.figure()
ax = fig.add_subplot(111)

type1 = ax.scatter(datingDataMat[:, 0][class1], datingDataMat[:, 1][class1])
type2 = ax.scatter(datingDataMat[:, 0][class2], datingDataMat[:, 1][class2])
type3 = ax.scatter(datingDataMat[:, 0][class3], datingDataMat[:, 1][class3])
ax.legend([type1, type2, type3], ["不喜欢", "魅力一般", "极具魅力"], loc=1)

plt.xlabel('每年获取的飞行常客里程数', fontproperties='SimHei', fontsize='14')
plt.ylabel('玩视频游戏所耗时间百分比', fontproperties='SimHei', fontsize='14')
plt.show()

准备数据:归一化数值

下表给出了提取的四组数据,如果想要计算样本3和样本4之间的距离,可以使用下面的方法:

(067)2+(2000032000)2+(1.10.1)2

我们很容易发现,上面方程中数字差值最大的属性对计算结果的影响最大,也就是说,每年获取的飞行常客里程数对于计算结果的影响将远远大于表2-3中其他两个特征——玩视频游戏的和每周消费冰洪淋公升数——的影响。而产生这种现象的唯一原因,仅仅是因为飞行常客里程数 远大于其他特征值。但海伦认为这三种特征是同等重要的,因此作为三个等权重的特征之一,飞行常客里程数并不应该如此严重地影响到计算结果。

玩视频游戏所耗时间百分比毎年获得的飞行常客里程数毎周消费的冰淇淋公升数样本分类
10.84000.5
212134 0000.9
3020 0001.1
46732 0000,1

在处理这种不同取值范围的特征值时,我们通常采用的方法是将数值归一化,如将取值范围处理为01或者-11之间。下面的公式可以将任意取值范围的特征值转化为01区间内的值:

newValue=oldValueminmaxmin

归一化代码:

# -*- coding:utf- -*-


import numpy as np


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

在函数autoNorm中,我们将每列的最小值放在变量minVals中,将最大值放在变量maxVals中,其中dataSet.mirKO)中的参数0使得函数可以从列中选取最小值,而不是选取当前行的最小值。然后,函数计算可能的取值范围,并创建新的返回矩阵。正如前面给出的公式,为了归一化特征值,我们必须使用当前值减去最小值,然后除以取值范围。需要注意的是,特征值矩阵有1000x3个值,而minValsrange的值都为1x3。为了解决这个冋题,我们使用NumPy库中tile ()函数将变量内容复制成输人矩阵同样大小的矩阵,注意这是具体特征值相除,而 对于某些数值处理软件包,/可能意味着矩阵除法,但在NumPy库中,矩阵除法需要使用函数linalg. solve (matA^matB)

检测函数的执行结果:

In [17]: normMat, ranges, minVals = autoNorm(datingDataMat)

In [18]: normMat
Out[18]:
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]])

In [19]: ranges
Out[19]: array([  9.12730000e+04,   2.09193490e+01,   1.69436100e+00])

In [20]: minVals
Out[20]: array([ 0.      ,  0.      ,  0.001156])
测试算法:作为完整程序验证分类器
  • 将已有数据的90%作为训练样本来训练分类器,而使用其余的10%数据去测试分类器,检测分类器的正确率。
  • 10%的测试数据应该 是随机选择的

对于分类器来说,错误率就是分类 器给出错误结果的次数除以测试数据的总数,完美分类器的错误率为0,而错误率为1.0的分类器 不会给出任何正确的分类结果。代码里我们定义一个计数器变量,每次分类器错误地分类数据, 计数器就加1,程序执行完成之后计数器的结果除以数据点总数即是错误率。

分类器针对约会网站的测试代码:

# -*- coding:utf-8 -*-


def datingClassTest():
    from knn.file2matrix import file2matrix
    from knn.autoNorm import autoNorm
    from knn.classify0 import classify0
    import numpy as np
    import random
    hoRatio = 0.10
    datingDataMat, datingLabels = file2matrix('data/datingTestSet2.txt')
    datingLabels0 = np.asarray(datingLabels)
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    # 随机抽取10%的样本作为测试集
    numTestVecs = set(random.sample(range(int(m)), int(m * hoRatio)))
    # 剩下90%的样本作为训练集
    numTrainVecs = list(set(range(m)) - numTestVecs)

    errorCount = 0.0
    for i in numTestVecs:
        classfierResult = classify0(normMat[i, :], normMat[numTrainVecs, :],
                                    datingLabels0[numTrainVecs], 3)
        print('the classifier came back with: %d, the real answer is: %d'
              % (classfierResult, datingLabels0[i]))
        if (classfierResult != datingLabels0[i]):
            errorCount += 1.0

    print('the total error rate is: %f' % (errorCount / float(len(numTestVecs))))

运行100次测试一下

# -*- coding:utf-8 -*-


import knn.datingClassTest as DT


errorRatios = 0.0

for i in range(100):
    errorRatios = errorRatios + DT.datingClassTest()

print('the average error rate is %f' % (errorRatios / 100))

结果如下:

平均的错误率为0.0472 ,算不上好的结果。

使用算法:构建完整可用系统

上面我们已经在数据上对分类器进行了测试,现在终于可以使用这个分类器为海伦来对人们分类。我们会给海伦一小段程序,通过该程序海伦会在约会网站上找到某个人并输入他的信息。 程序会给出她对对方喜欢程度的预测值。

# -*- coding:utf-8 -*-


def classifyPerson():
    from knn.file2matrix import file2matrix
    from knn.autoNorm import autoNorm
    from knn.classify0 import classify0
    import numpy as np
    resultList = ['not at all', 'in small doses', 'in large doses']
    percentTats = float(raw_input('percentage of time for video games\n'))
    ffMiles = float(raw_input('frequent flier miles earned per year\n'))
    iceCream = float(raw_input('liters of ice cream consumed per year\n'))
    datingDataMat, datingLabels = file2matrix('data/datingTestSet2.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = np.array([ffMiles, percentTats, iceCream])
    classifierResult = classify0((inArr - minVals) / ranges, normMat, datingLabels, 3)
    print('You willl probably like this person %s' % (resultList[classifierResult - 1]))

测试如下:

In [1]: from classifyPerson import classifyPerson

In [2]: classifyPerson()
percentage of time for video games
20
frequent flier miles earned per year
10000
liters of ice cream consumed per year
100
You willl probably like this person in large doses

In [3]: classifyPerson()
percentage of time for video games
10
frequent flier miles earned per year
10000
liters of ice cream consumed per year
0.5
You willl probably like this person in small doses

好吧这姑娘喜欢玩游戏时间玩得长!


本文由【waitig】发表在等英博客
本文固定链接:k近邻算法原理以及改进约会网站的配对效果
欢迎关注本站官方公众号,每日都有干货分享!
等英博客官方公众号
点赞 (0)分享 (0)