机器学习实战---KNN近邻算法

机器学习 评论

1. 近邻算法概述

　　简单说，k-近邻算法采用测量不同特征值之间的距离进行分类。
　　优点：精度高、对异常值不敏感、无数据输入假定
　　缺点：计算复杂度高、空间复杂度高
　　适用数据范围：数值型和标称型

　　工作原理：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道每项数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征月样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中K的出处。
　　一般流程：
　　１）收集数据：任何方法
　　２）准备数据：距离计算所需要的数值，最好是结构化的数据格式
　　３）分析数据：任何方法 4）该步骤不适用于k-近邻算法
　　４）测试算法：计算错误率
　　５）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

2. 准备：使用python导入数据

　　新建knn.py，添加以下代码，用来得到数据集和标签，其中group矩阵每行包含一个不同的数据（可看做某个日志文件中不同的测量点），label包含了每个数据点的标签信息，label包含的元素个数等于group矩阵行数。

1
2
3
4
5
6
7
from numpy import *
import operator

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

　　为了方便使用createDataSet()函数，它创建数据集和标签。在Python环境下执行下列命令查看该模块加载情况：

1
2
>>> import kNN
>>> group,labels=kNN.createDataSet()

2.1.2 文本文件解析数据

解析数据伪代码：
对未知类别属性的数据集中的每个点依次执行以下操作：
1）计算已知类别数据集中的点与当前点之间的距离；
2）按照距离递增次序排序；
3）选取与当前点距离最小的K个点
4）确定前K个点所在类别的出现频率；
5）返回前K个点出现频率最高的类别作为当前点的预测分类
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = 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]

classify0函数有4个输入参数：用于分类的输入向量inX，输入的训练样本集为dataSet，标签向量为labels，最后的参数k表示用于选择最近邻的数目，其中标签向量的元素数目和矩阵dataSet的行数相同。程序中使用的是欧式距离公式。计算两个向量点xA和xB之间距离。

"距离公式"

为了预测数据所在分类，在Python提示符中输入下列命令：

1
kNN.classify0([0,0], group, labels, 3)

输出结果为B，也可以改变输入的[0,0]为其他值，测试程序的运行结果。
到现在为止，我们已经构造了第一个分类器，使用这个分类器可以完成很多分类任务，从这个实例出发，构造使用多个分类算法将会更加容易。

2.2 使用k_近邻算法改进约会网站的配对效果

2.2.1 准备数据

收集到的约会数据存放在文本文件datingTestSet.txt中，每个样本数据占据一行，总共有1000行。样本主要包涵以下3种特征。

  • 每年获得的飞行常客里程数
  • 玩视频游戏所耗费时间百分百
  • 每周消费的冰淇淋公升数
  • 魅力程度
    形如：
  • 40920 8.326976 0.953952 largeDoses
  • 14488 7.153469 1.673904 smallDoses
  • 26052 1.441871 0.805124 didntLike
  • 75136 13.147394 0.428964 didntLike
    在将上述特征数据输入到分类器之前，需要格式化处理，下面函数的输入为文件名字符串，输出为训练样本矩阵和类标签向量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def file2matrix(filename):
	fr = open(filename)
	numberOfLines = len(fr.readlines())         #get the number of lines in the file
	returnMat = zeros((numberOfLines,3))        #prepare matrix to return
	classLabelVector = []                       #prepare labels return
	fr = open(filename)
	index = 0
	type={'largeDoses':3,'smallDoses':2,'didntLike':1}
	for line in fr.readlines():
		line = line.strip()
		listFromLine = line.split('\t')
		returnMat[index,:] = listFromLine[0:3]
		classLabelVector.append(type.get(listFromLine[-1],0))
		index += 1
	return returnMat,classLabelVector

解析文本记录，结果如下：

1
2
reload(kNN)
datingDataMat, datingLabels = kNN.file2matrix('datingTestSet.txt')

"返回数据内容"

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

首先使用使用Matplotlib制作原始数据的散点图。

1
2
3
4
5
6
import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.ad_subplot(111)
ax.scatter(datingDataMat[:,1], datingDataMat[:,2])
plt.show()

输出效果如下。散点图使用datingDataMat矩阵的第二、第三列数据，分别表示特征值“玩视频游戏所耗时间百分比”和“每周所消费的冰淇淋公升数”。

"散点图"

没有使用样本分类的特征值，很难从上图中看到任何有用的数据模式信息。matplotlib库提供的scatter函数支持个性化标记散点图上的点。重新输入上面的代码，调用scatter函数时使用下列参数：

1
ax.scatter(datingDataMat[:,1], datingDataMat[:,2], 15.0*array(datingLabels), 15.0*(datingLabels))
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
41
42
43
44
45
46
47
48
49
50
51
52
53
#!/usr/bin/python2.7
# _*_ coding: utf-8 _*_

from matplotlib import pyplot as plt
from matplotlib import font_manager

import file2matrix

matrix, labels = file2matrix.file2matrix('datingTestSet.txt')
print matrix
print labels
zhfont = matplotlib.font_manager.FontProperties(fname='/usr/share/fonts/truetype/arphic/ukai.ttc')

""" 比较好看的绘制方法 """

plt.figure(figsize=(8, 5), dpi=80)
axes = plt.subplot(111)
# 将三类数据分别取出来
# x轴代表飞行的里程数
# y轴代表玩视频游戏的百分比
type1_x = []
type1_y = []
type2_x = []
type2_y = []
type3_x = []
type3_y = []
print 'range(len(labels)):'
print range(len(labels))
for i in range(len(labels)):
    if labels[i] == 1:  # 不喜欢
        type1_x.append(matrix[i][0])
        type1_y.append(matrix[i][1])

    if labels[i] == 2:  # 魅力一般
        type2_x.append(matrix[i][0])
        type2_y.append(matrix[i][1])

    if labels[i] == 3:  # 极具魅力
        print i, '：', labels[i], ':', type(labels[i])
        type3_x.append(matrix[i][0])
        type3_y.append(matrix[i][1])

type1 = axes.scatter(type1_x, type1_y, s=20, c='red')
type2 = axes.scatter(type2_x, type2_y, s=40, c='green')
type3 = axes.scatter(type3_x, type3_y, s=50, c='blue')
# plt.scatter(matrix[:, 0], matrix[:, 1], s=20 * numpy.array(labels),
#             c=50 * numpy.array(labels), marker='o',
#             label='test')
plt.xlabel(u'每年获取的飞行里程数', fontproperties=zhfont)
plt.ylabel(u'玩视频游戏所消耗的事件百分比', fontproperties=zhfont)
axes.legend((type1, type2, type3), (u'不喜欢', u'魅力一般', u'极具魅力'), loc=2, prop=zhfont)

plt.show()

"彩色图"

2.2.3 准备数据：归一化数值

　　处理不同取值范围的特征值时，通常采用的方法是数值归一化，如将取值范围处理为0到1或者-1到1之间。下面的公式可以将任意取值范围的特征值转换为0到1之间内的值。

newValue = (oldValue - min) / (max - min)

归一化特征值代码：

1
2
3
4
5
6
7
8
9
def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m,1))
    normDataSet = normDataSet/tile(ranges, (m,1))   #element wise divide
return normDataSet, ranges, minVals

在Python命令提示符下，重新加载kNN.py模块

"数值归一化"

2.2.4 算法测试

　　机器学习算法一个很重要的工作就是评估算法的正确率，通常我们只提供已有数据的90%作为训练样本类训练分类器，而使用其余的10%数据去测试分类器，检测分类器的正确率。
　　分类器针对约会网站的测试代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def datingClassTest():
    hoRatio = 0.50      #hold out 10%
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')       #load data setfrom file
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio)
    errorCount = 0.0
    for i in range(numTestVecs):
        classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
        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))
print errorCount

"算法测试"

2.2.5 使用算法：构建完整可用系统

　　约会网站预测函数:

1
2
3
4
5
6
7
8
9
10
def clssifyPerson():
	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 fliter miles earned per year?"))
	iceCream = float(raw_input("liters of ice cream consumed per year?"))
	datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
	normMat,ranges,minVals = autoNorm(datingDataMat)
	inArr = array([ffMiles,percentTats,iceCream])
	classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels,3)
	print "you will probably like this person: " + resultList[classifierResult - 1]

"算法预测"

下一节，将会接着学习使用k-近邻算法实现的手写识别系统。

黄志远研发攻城狮

靡不有初 鲜克有终