Skip to content
Navigation Menu
{{ message }}
forked from apachecn/ailearning
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathkNN.py
More file actions
294 lines (257 loc) · 11.9 KB
/
Copy pathkNN.py
File metadata and controls
294 lines (257 loc) · 11.9 KB
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
#!/usr/bin/env python
# coding: utf-8
'''
Created on Sep 16, 2010
Update on 2017-05-18
@author: Peter Harrington/羊三/小瑶
《机器学习实战》更新地址：https://github.com/apachecn/MachineLearning
'''
from numpy import *
# 导入科学计算包numpy和运算符模块operator
import operator
from os import listdir
from collections import Counter
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
def classify0(inX, dataSet, labels, k):
"""
inx[1,2,3]
DS=[[1,2,3],[1,2,0]]
inX: 用于分类的输入向量
dataSet: 输入的训练样本集
labels: 标签向量
k: 选择最近邻居的数目
注意：labels元素数目和dataSet行数相同；程序使用欧式距离公式.
预测数据所在分类可在输入下列命令
kNN.classify0([0,0], group, labels, 3)
"""
# -----------实现 classify0() 方法的第一种方式----------------------------------------------------------------------------------------------------------------------------
# 1. 距离计算
dataSetSize = dataSet.shape[0]
# tile生成和训练样本对应的矩阵，并与训练样本求差
"""
tile: 列-3表示复制的行数， 行-1／2表示对inx的重复的次数
In [8]: tile(inx, (3, 1))
Out[8]:
array([[1, 2, 3],
[1, 2, 3],
[1, 2, 3]])
In [9]: tile(inx, (3, 2))
Out[9]:
array([[1, 2, 3, 1, 2, 3],
[1, 2, 3, 1, 2, 3],
[1, 2, 3, 1, 2, 3]])
"""
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
"""
欧氏距离： 点到点之间的距离
第一行： 同一个点 到 dataSet的第一个点的距离。
第二行： 同一个点 到 dataSet的第二个点的距离。
...
第N行： 同一个点 到 dataSet的第N个点的距离。
[[1,2,3],[1,2,3]]-[[1,2,3],[1,2,0]]
(A1-A2)^2+(B1-B2)^2+(c1-c2)^2
"""
# 取平方
sqDiffMat = diffMat ** 2
# 将矩阵的每一行相加
sqDistances = sqDiffMat.sum(axis=1)
# 开方
distances = sqDistances ** 0.5
# 根据距离排序从小到大的排序，返回对应的索引位置
# argsort() 是将x中的元素从小到大排列，提取其对应的index（索引），然后输出到y。
# 例如：y=array([3,0,2,1,4,5]) 则，x[3]=-1最小，所以y[0]=3,x[5]=9最大，所以y[5]=5。
# print 'distances=', distances
sortedDistIndicies = distances.argsort()
# print 'distances.argsort()=', sortedDistIndicies
# 2. 选择距离最小的k个点
classCount = {}
for i in range(k):
# 找到该样本的类型
voteIlabel = labels[sortedDistIndicies[i]]
# 在字典中将该类型加一
# 字典的get方法
# 如：list.get(k,d) 其中 get相当于一条if...else...语句,参数k在字典中，字典将返回list[k];如果参数k不在字典中则返回参数d,如果K在字典中则返回k对应的value值
# l = {5:2,3:4}
# print l.get(3,0)返回的值是4；
# Print l.get（1,0）返回值是0；
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
# 3. 排序并返回出现最多的那个类型
# 字典的 items() 方法，以列表返回可遍历的(键，值)元组数组。
# 例如：dict = {'Name': 'Zara', 'Age': 7} print "Value : %s" % dict.items() Value : [('Age', 7), ('Name', 'Zara')]
# sorted 中的第2个参数 key=operator.itemgetter(1) 这个参数的意思是先比较第几个元素
# 例如：a=[('b',2),('a',1),('c',0)] b=sorted(a,key=operator.itemgetter(1)) >>>b=[('c',0),('a',1),('b',2)] 可以看到排序是按照后边的0,1,2进行排序的，而不是a,b,c
# b=sorted(a,key=operator.itemgetter(0)) >>>b=[('a',1),('b',2),('c',0)] 这次比较的是前边的a,b,c而不是0,1,2
# b=sorted(a,key=opertator.itemgetter(1,0)) >>>b=[('c',0),('a',1),('b',2)] 这个是先比较第2个元素，然后对第一个元素进行排序，形成多级排序。
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
# ------------------------------------------------------------------------------------------------------------------------------------------
# 实现 classify0() 方法的第二种方式
# """
# 1. 计算距离
# 欧氏距离： 点到点之间的距离
# 第一行： 同一个点 到 dataSet的第一个点的距离。
# 第二行： 同一个点 到 dataSet的第二个点的距离。
# ...
# 第N行： 同一个点 到 dataSet的第N个点的距离。
# [[1,2,3],[1,2,3]]-[[1,2,3],[1,2,0]]
# (A1-A2)^2+(B1-B2)^2+(c1-c2)^2
# inx - dataset 使用了numpy broadcasting，见 https://docs.scipy.org/doc/numpy-1.13.0/user/basics.broadcasting.html
# np.sum() 函数的使用见 https://docs.scipy.org/doc/numpy-1.13.0/reference/generated/numpy.sum.html
# """
# dist = np.sum((inx - dataset)**2, axis=1)**0.5
# """
# 2. k个最近的标签
# 对距离排序使用numpy中的argsort函数， 见 https://docs.scipy.org/doc/numpy-1.13.0/reference/generated/numpy.sort.html#numpy.sort
# 函数返回的是索引，因此取前k个索引使用[0 : k]
# 将这k个标签存在列表k_labels中
# """
# k_labels = [labels[index] for index in dist.argsort()[0 : k]]
# """
# 3. 出现次数最多的标签即为最终类别
# 使用collections.Counter可以统计各个标签的出现次数，most_common返回出现次数最多的标签tuple，例如[('lable1', 2)]，因此[0][0]可以取出标签值
# """
# label = Counter(k_labels).most_common(1)[0][0]
# return label
# ------------------------------------------------------------------------------------------------------------------------------------------
def test1():
"""
第一个例子演示
"""
group, labels = createDataSet()
print str(group)
print str(labels)
print classify0([0.1, 0.1], group, labels, 3)
# ----------------------------------------------------------------------------------------
def file2matrix(filename):
"""
导入训练数据
:param filename: 数据文件路径
:return: 数据矩阵returnMat和对应的类别classLabelVector
"""
fr = open(filename)
# 获得文件中的数据行的行数
numberOfLines = len(fr.readlines())
# 生成对应的空矩阵
# 例如：zeros(2，3)就是生成一个 2*3的矩阵，各个位置上全是 0
returnMat = zeros((numberOfLines, 3)) # prepare matrix to return
classLabelVector = [] # prepare labels return
fr = open(filename)
index = 0
for line in fr.readlines():
# str.strip([chars]) --返回移除字符串头尾指定的字符生成的新字符串
line = line.strip()
# 以 '\t' 切割字符串
listFromLine = line.split('\t')
# 每列的属性数据
returnMat[index, :] = listFromLine[0:3]
# 每列的类别数据，就是 label 标签数据
classLabelVector.append(int(listFromLine[-1]))
index += 1
# 返回数据矩阵returnMat和对应的类别classLabelVector
return returnMat, classLabelVector
def autoNorm(dataSet):
"""
归一化特征值，消除属性之间量级不同导致的影响
:param dataSet: 数据集
:return: 归一化后的数据集normDataSet,ranges和minVals即最小值与范围，并没有用到
归一化公式：
Y = (X-Xmin)/(Xmax-Xmin)
其中的 min 和 max 分别是数据集中的最小特征值和最大特征值。该函数可以自动将数字特征值转化为0到1的区间。
"""
# 计算每种属性的最大值、最小值、范围
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
# 极差
ranges = maxVals - minVals
# -------第一种实现方式---start-------------------------
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
# 生成与最小值之差组成的矩阵
normDataSet = dataSet - tile(minVals, (m, 1))
# 将最小值之差除以范围组成矩阵
normDataSet = normDataSet / tile(ranges, (m, 1)) # element wise divide
# -------第二种实现方式---end---------------------------------------------
# # -------第二种实现方式---start---------------------------------------
# norm_dataset = (dataset - minvalue) / ranges
# # -------第二种实现方式---end---------------------------------------------
return normDataSet, ranges, minVals
def datingClassTest():
"""
对约会网站的测试方法
:return: 错误数
"""
# 设置测试数据的的一个比例（训练数据集比例=1-hoRatio）
hoRatio = 0.1 # 测试范围,一部分测试一部分作为样本
# 从文件中加载数据
datingDataMat, datingLabels = file2matrix('input/2.KNN/datingTestSet2.txt') # load data setfrom file
# 归一化数据
normMat, ranges, minVals = autoNorm(datingDataMat)
# m 表示数据的行数，即矩阵的第一维
m = normMat.shape[0]
# 设置测试的样本数量， numTestVecs:m表示训练样本的数量
numTestVecs = int(m * hoRatio)
print 'numTestVecs=', numTestVecs
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
def img2vector(filename):
"""
将图像数据转换为向量
:param filename: 图片文件 因为我们的输入数据的图片格式是 32 * 32的
:return: 一维矩阵
该函数将图像转换为向量：该函数创建 1 * 1024 的NumPy数组，然后打开给定的文件，
循环读出文件的前32行，并将每行的头32个字符值存储在NumPy数组中，最后返回数组。
"""
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():
# 1. 导入数据
hwLabels = []
trainingFileList = listdir('input/2.KNN/trainingDigits') # load the training set
m = len(trainingFileList)
trainingMat = zeros((m, 1024))
# hwLabels存储0～9对应的index位置， trainingMat存放的每个位置对应的图片向量
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0] # take off .txt
classNumStr = int(fileStr.split('_')[0])
hwLabels.append(classNumStr)
# 将 32*32的矩阵->1*1024的矩阵
trainingMat[i, :] = img2vector('input/2.KNN/trainingDigits/%s' % fileNameStr)
# 2. 导入测试数据
testFileList = listdir('input/2.KNN/testDigits') # iterate through the test set
errorCount = 0.0
mTest = len(testFileList)
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[0] # take off .txt
classNumStr = int(fileStr.split('_')[0])
vectorUnderTest = img2vector('input/2.KNN/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))
if __name__ == '__main__':
# test1()
# datingClassTest()
handwritingClassTest()
You can’t perform that action at this time.