《机器学习实战》之k近邻算法（1）算法概述

发表于 | 更新于: | 分类于 | 阅读次数:
字数统计: 2,449 | 阅读时长 ≈ 10

前言：

  本渣渣（WordZzzz直接被舍友叫成了“我的渣”，所以以后我在博客中就以此自居了！），最近在学习Peter Harrington的Machine Learning in Action，一边看书一边用Python3.6实现课本中的算法（原书中使用的是Python2.x）。好记性不如烂笔头，奈何本渣渣连烂笔头都买不起，所以就来这不费笔墨的地方费尽心思写博客。本渣渣记性不是一般的差，在此记下每个算法的学习要点及Python代码实现，一方面方便自己以后复习，另一方面贴出来和大家一起学习，共同进步~~~

注意：python3.x与python2.x的部分函数库有较大差异，针对这个问题，本渣渣会将代码版本升级中遇到的问题在每篇博文的最后列出来，并加以解释说明，帮助大家区分理解。

原著代码（python2.x）地址：https://www.manning.com/books/machine-learning-in-action
本渣渣代码（python3.x）地址：https://github.com/WordZzzz/ML/tree/master/Ch02

  博客中的代码都会在本渣渣的GitHub上贴出，欢迎Watch、Star、Fork。

一、算法介绍：

  k-近邻算法（kNN）的工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法的中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
  简单的说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。

k-近邻算法：

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

  书上有个电影分类的例子，使用k-近邻算法分类爱情片和工作片。书中给出了6部电影的打斗镜头数和接吻镜头数，如图2-1所示。



  假如有一部未看过的电影，如何确定它是爱情片还是动作片呢？下面我们将使用kNN来解决这个问题。

  首先，我们需要数据，即这个未知电影存在多少个打斗镜头和接吻镜头，图2-1中间问号位置是该电影出现的镜头数图像化的结果，具体数字参见表2-1。

电影名称 打斗镜头 接吻镜头 电影类型
California Man 3 104 爱情片
He is Not Really into Dudes 2 100 爱情片
Beautiful Woman 1 81 爱情片
Kevin Longblade 101 10 动作片
Robo Slayer 3000 99 5 动作片
Amped Ⅱ 98 2 动作片
？ 18 90 未知型

[表2-1 每部电影的镜头统计及电影评估类型]

  计算未知电影和样本集中其他电影的距离，如表2-2所示。我们暂且不关心如何计算得到这些距离值，后面会提供具体的计算方法。

电影名称 与未知电影的距离
California Man 20.5
He is Not Really into Dudes 18.7
Beautiful Woman 19.2
Kevin Longblade 115.3
Robo Slayer 3000 117.4
Amped Ⅱ 9118.9

[表2-2 已知电影与未知电影的距离]

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

一般流程：

  • 收集数据：可以使用任何方法。
  • 准备数据：距离计算所需要的数值，最好是结构化的数据格式。
  • 分析数据：可以使用任何方法。
  • 训练算法：此步骤不适用于k-近邻算法。
  • 测试算法：计算错误率。
  • 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续处理。

二、代码实现与详解：

  首先，创建名为kNN.py的Python模块。所有代码都已做出详细注释，所以不再赘述，如有疑问可以在下方评论哦~

2.1 创建数据集和标签：

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# -*- coding: UTF-8 -*-
"""
Created on Aug 18, 2017
kNN: k Nearest Neighbors

Input:      inX: vector to compare to existing dataset (1xN)
            dataSet: size m data set of known vectors (NxM)
            labels: data set labels (1xM vector)
            k: number of neighbors to use for comparison (should be an odd number)
            
Output:     the most popular class label

@author: wordzzzz
"""

from numpy import *
import operator

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

	Args：		无

	Returns：	group：创建的数据集
				labels：创建的标签
	"""

	#创建数据集
	group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
	#创建标签
	labels = ['A', 'A', 'B', 'B']
	#返回创建的数据集和标签						
	return group, labels

  保存编写好的kNN.py模块，在Windows下打开命令提示符。如果不想在终端通过命令行一步一步敲到当前目录，可以直接在当前文件夹按住shift+右键，这个时候便会出现命令提示符的选项，单击后终端内直接显示当前文件夹。然后输入python，进入python编译开发环境。

输出结果：

1
2
3
4
5
6
7
8
9
>>> import kNN
>>> group,labels = kNN.createDataSet()
>>> group
array([[ 1. ,  1.1],
       [ 1. ,  1. ],
       [ 0. ,  0. ],
       [ 0. ,  0.1]])
>>> labels
['A', 'A', 'B', 'B']

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



2.2 实施kNN分类算法：

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

  • (1).计算已知类别数据集中的点与当前点之间的距离；
  • (2).按照距离递增次序排序；
  • (3).选取与当前点距离最小的k个点；
  • (4).确定前k个点所在类别的出现频率；
  • (5).返回前k个点出现频率最高的类别作为当前点的预测分类。

  这里我们使用欧氏距离公式，计算两个向量点xA和xB之间的距离：
$$ d = \sqrt{(xA_0-xB_0)^2+(xA_1-xB_1)^2} $$

  如果特征值有多个，那公式就变成了这个样子：
$$ d = \sqrt{\sum_{i=0}^N{(xA_i-xB_i)^2}} $$

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def classify0(inX, dataSet, labels, k):
	"""
	Function：	创建数据集和标签

	Args：		inX：用于分类的输入向量 (1xN)
            	dataSet：输入的训练样本集 (NxM)
            	labels：标签向量 (1xM vector)
            	k：用于比较的近邻数量 (should be an odd number)

	Returns：	sortedClassCount[0][0]：分类结果
	"""
	#dataSet.shape[0]：求dataSet矩阵的行数
	#dataSet.shape[1]：求dataSet矩阵的列数
	#dataSet.shape：元组形式输出矩阵行数、列数
	dataSetSize = dataSet.shape[0]
	#tile(A, B)：将A重复B次，其中B可以是int类型也可以是元组类型
	#这句话相当于向量inX与矩阵dataSet里面的每组数据做差
	diffMat = tile(inX, (dataSetSize, 1)) - dataSet
	#对求差后的矩阵求平方
	sqDiffMat = diffMat**2
	#sqDiffMat.sum(axis=0)：对矩阵的每一列求和
	#sqDiffMat.sum(axis=1)：对矩阵的每一行求和
	#sqDiffMat.sum()：对整个矩阵求和
	sqDistances = sqDiffMat.sum(axis=1)
	#求平方根
	distances = sqDistances**0.5
	#对上式结果进行排序
	sortedDistIndicies = distances.argsort()
	#创建字典
	classCount = {}
	#给字典赋值
	for i in range(k):
		#字典的key
		voteIlabel = labels[sortedDistIndicies[i]]
		#classCount.get(voteIlabel,0)：如果字典键的值中有voteIlabel，则返回0（第二个参数的值）
		classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
	#对classCount进行排序，sroted、items以及itermgetter随后讲解@1
	sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
	#返回分类结果
	return sortedClassCount[0][0]

  保存编写好的kNN.py模块，此时如果你不重新加载模块，你的命令提示符里面已经加载过的模块是不会自动更新的。所以我们需要调用imp模块中的reload来重新加载新保存的模块。我们输入两个不同的例子[0.9, 0.9][0.1, 0.1]，得到相应的分类结果并输出。

输出结果：

1
2
3
4
5
6
7
>>> from imp import reload
>>> reload(kNN)

>>> kNN.classify0([0.9,0.9], group, labels, 3)
'A'
>>> kNN.classify0([0.1,0.1], group, labels, 3)
'B'

三、主要区分函数：

详解：
1.sorted,sort以及argsort：

http://blog.csdn.net/u011475210/article/details/77769245

http://blog.csdn.net/u011475210/article/details/77770751

2.items等：

http://blog.csdn.net/u011475210/article/details/77770145

3.itemgetter等：

http://blog.csdn.net/u011475210/article/details/77770772

系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～

完的汪(∪｡∪)｡｡｡zzz

0%