《Python机器学习实战》第一章读书笔记：k-近邻算法_ax.scatter(returnmat[:,1], classlabelvector[:,2],

第一章：k-近邻算法

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

下面介绍k-近邻算法准备工作、代码实现及实战应用

1. 使用python导入数据

导入数据函数代码：

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
1
2
3
4
5
6
7
8

这里导入了两个模块：

（1）科学计算包Numpy模块（2）运算符模块，用于提供排序操作的函数

进入终端，输入python进入Python开发环境
输入以下命令以导入程序模块：

import KNN
1

输入以下命令来创建变量group和labels：

group,labels = KNN.CreateDataSet()
1

在python命令提示符下，输入变量的名字来检验是否正确的定义变量。

2. 从文本文件中解析数据

k-近邻算法的伪代码：
对未知类别属性的DataSet的每个点依次执行以下操作：
（1）计算inX（当前点集）中的点到已知类别点集中的距离
（2）以递增序将距离排序
（3）选取与inX距离最小的k个点
（4）确定前k个点所在类别的出现频率
（5）返回前k个点出现频率最高的类别作为当前点的预测分类

k-近邻算法代码：

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]
1
2
3
4
5
6
7
8
9
10
11
12
13

算法中出现的python知识点简单介绍一下：
(1) shape[0]返回矩阵dataSet的行数
(2) tile函数：格式tile(A,reps) ，A是输入的数组，reps是A沿各个维度重复的个数
比如A=[1,2],tile(A,(2,2,3))
结果
[[[1,2,1,2,1,2], [1,2,1,2,1,2]],
[[1,2,1,2,1,2], [1,2,1,2,1,2]]]
沿第一个维度重复三遍，沿第二个维度重复两遍，沿第三个维度重复两遍
这里diffMat相当于将inX这个向量重复dataSize行构成矩阵，并与dataSet矩阵相减且得到结果矩阵。
(3) sqDiffMat.sum(axis = 1),将sqDiffMat的每一个行向量相加，返回一个nx1的向量后转置
Eg c = np.array([[0, 2, 1], [3, 5, 6], [0, 1, 1]])
print c.sum()
print c.sum(axis=0)
print c.sum(axis=1)
结果分别是：19, [3 8 8], [ 3 14 2]
(4) argsort()函数：argsort函数返回的是数组值从小到大的索引值
x = np.array([3, 1, 2])
np.argsort(x)
输出结果：array([1, 2, 0])
这个怎么解释呢……
3最大，其索引值为0，所以argsort数组的第三项（最大项）就是其索引值0
2其次大，其索引值为2，所以argsort数组的第二项（第二大项）就是其索引值2
1最小，其索引值为1，所以argsort数组的第一项（最小项）就是其索引值1
这里最后返回一个1xn的向量用来进行下面的操作
(5) classCount = {}:新建一个字典。字典就是PHP的关联数组，键值对罢了。
用的时候再学习它的内置函数。
.get()方法：dict.get(key,default = None)
返回指定键的值，比如这里返回voteIlabel，若voteIlabel不存在，则返回0（其实就是返回get的第二个参数）.
(6) sorted函数：
sorted(…)：sorted(iterable, cmp=None, key=None, reverse=False) –> new sorted list
第一个参数iterable:是一个可迭代类型
第二个参数cmp:是一个比较函数，比较什么由key来决定
第三个参数key: 用列表元素的某个属性或函数进行作为关键字，有默认值，迭代集合中的一项;
第四个参数reverse：排序规则。reverse = True降序或者reverse = False升序，有默认值。

 sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
1

以程序中这段代码为例，这里用operator函数来加快排序：
dict.iteritems()：获得字典的一个迭代器
key=operator.itemgetter(1)：去获取对象的第一个域的值
reverse = True ：倒序排序获得第一个值，从而使数组的[0][0]成为最大值。

代码实现的功能：
在前面计算完所有点的距离后，可以对数据按照从小到大的顺序排序。然后确定前k个距离最小元素所在的分类，将classCount字典分解为元组列表，按照第二个元素（第一个域）对元组逆序排序。最后返回频率最高的元素标签。

输入KNN.classify0([0,0],group,labels,3),返回发生频率最高的元素标签。

3. 从文本文件中解析数据代码：

def file2matrix(filename):
    fr = open(filename)
    arrayOLines = fr.readlines()
    numberOfLines = len(arrayOLines)
    returnMat = zeros((numberOfLines,3))
    classLabelVector = []
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

算法中出现的python知识点简单介绍一下：
(1) 有关readlines请看
http://www.cnblogs.com/qi09/archive/2012/02/10/2344964.html
主要是后面代码有用到readline但是那个时候是需要读一个文件包的文件
readlines用于读取文档内全部内容
(2) Python strip()方法用于移除字符串头尾指定的字符（默认为空格）。
(3) append()在列表末尾添加对象

代码实现的功能：
首先获得文件的行数，并且建立以零填充的矩阵。我们对文件进行处理后，将其前三列存到特征矩阵中，并且将最后一列存到向量classLabelVector，从而将文件中的数据储存到向量和矩阵中。

输入以下命令来检查数据内容：

reload(KNN)
datingDataMat,datingLabels = KNN.file2matrix('datingTestSet2.txt')
1
2

4. 使用Matplotlib创建散点图
在终端中输入如下命令：

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

得到结果如下：

5. 使用Matplotlib创建彩色的散点图

在终端中输入如下命令：

from numpy import array
import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))
plt.show()
1
2
3
4
5
6
7

得到结果如下：

可视化操作……没啥可说的。
scatter函数的应用不妨看官方文档。
http://matplotlib.org/api/pyplot_api.html?highlight=scatter#matplotlib.pyplot.scatter

6. 归一化特征值

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))
    return normDataSet,ranges,minVals
1
2
3
4
5
6
7
8
9

代码实现的功能：
用归一化方法处理不同取值范围的特殊值。其中，normDataSet是归一化后的矩阵，ranges是每一列的数据跨度，minVals是每一列的最小值。

7. 验证分类器的测试算法：

def datingClassTest():
    hoRatio = 0.10
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
    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))
1
2
3
4
5
6
7
8
9
10
11
12

验证分类器的时候使用已提供的90%的数据作为训练样本来训练分类器，而使用另外10%去测试分类器，检测分类器的正确率。
它首先使用了函数file2matrix()和autoNorm()从文件中读取数据并将其转换为归一化特征值。接着计算测试向量的数量，此步决定了normMat向量中哪些数据用于测试，哪些数据用于分类器的训练样本；然后将这两部分数据输人到原始KNN分类器函数 classify0( )。最后，函数计算错误率并输出结果注意此处我们使用原始分类器，主要重点是将数据改造为分类器可以使用的特征值。

由此可见，错误率5%左右。

8. 约会网站预测函数：

def classifyPerson():
    resultList = ['not at all','in small doses','in large doses']
    percentTats =  float(raw_input("percentage of time spend in playing video games?"))
    ffMiles = float(raw_input("frequent flier 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]
1
2
3
4
5
6
7
8
9
10

算法中出现的python知识点简单介绍一下：
（1）raw_input读取输入的内容，并且以字符串的形式返回

这里就可以交互并进行预测了……

9. 将32x32的矩阵转换成1x1024的向量

def img2vector(filename):
    returnVect = zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0,32*i+j] = int(lineStr[j])
    return returnVect
1
2
3
4
5
6
7
8

这里主要就是矩阵的转换，将32x32的矩阵转换成1x1024的向量，否则没有办法使用classify0()函数。

10. 手写识别系统：

使用k-近邻算法的手写识别系统

(1) 收集数据：提供文本文件。
(2) 准备数据：编写函数classify0(), 将图像格式转换为分类器使用的list格式。
(3) 分析数据：在Python命令提示符中检查数据，确保它符合要求。
(4) 训练算法：此步骤不适用于各近邻算法。
(5) 测试算法：编写函数使用提供的部分数据集作为测试样本，测试样本与非测试样本的区别在于测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。
(6) 使用算法：本例没有完成此步驟，若你感兴趣可以构建完整的应用程序，从图像中提取数字，并完成数字识别，美国的邮件分拣系统就是一个实际运行的类似系统。（未实现）

def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i,:] = img2vector('trainingDigits/%s'%fileNameStr)
    testFileList = listdir('testDigits')
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s'%fileNameStr)
        classifierResult = classify0(vectorUnderTest,trainingMat,hwLabels,3)
        print"the classifier came back with:%d,the real answer is %d"%(classifierResult,classNumStr)
        if (classifierResult != classNumStr):  errorCount += 1.0
    print "\nthe total number of errors is: %d" % errorCount
    print "\nthe total error rate is: %f" % (errorCount / float(mTest))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

算法中出现的python知识点简单介绍一下：
(1) listdir : os.listdir() 方法用于返回指定的文件夹包含的文件或文件夹的名字的列表。这个列表以字母顺序。 它不包括 ‘.’ 和’..’ 即使它在文件夹中。

代码实现的功能：
(1) 将trainingDigits目录中的文件内容储存在列表trainingFileList，然后可以得到目录中有多少文件，并将其储存在变量m中。
(2) 创建一个m行1024列的训练矩阵，该矩阵每行数据储存一个图像。
(3) 将类代码储存在hwLabels向量中，使用img2vector函数加载图像。
(4) 使用classify0()函数测试testDigits目录下的每个文件。
(5) 在Python命令提示符中输入KNN.handwritingClassTest(),测试该函数的输出结果。

(1)错误率为1.16%。改变变量 k 的值、修改函数handwritingClassTest()随机选取训练样本、改变训练样本的数目，都会对k-近邻算法的错误率产生影响。
(2)使用k决策树相当于k-近邻算法的优化版，可解决大量的计算开销。

代码

from numpy import *
from os import listdir
import operator

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]

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))
    return normDataSet,ranges,minVals

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

def datingClassTest():
    hoRatio = 0.10
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
    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))

def classifyPerson():
    resultList = ['not at all','in small doses','in large doses']
    percentTats =  float(raw_input("percentage of time spend in playing video games?"))
    ffMiles = float(raw_input("frequent flier 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]

def img2vector(filename):
    returnVect = zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0,32*i+j] = int(lineStr[j])
    return returnVect

def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i,:] = img2vector('trainingDigits/%s'%fileNameStr)
    testFileList = listdir('testDigits')
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s'%fileNameStr)
        classifierResult = classify0(vectorUnderTest,trainingMat,hwLabels,3)
        print"the classifier came back with:%d,the real answer is %d"%(classifierResult,classNumStr)
        if (classifierResult != classNumStr):  errorCount += 1.0
    print "\nthe total number of errors is: %d" % errorCount
    print "\nthe total error rate is: %f" % (errorCount / float(mTest))



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
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108