第一个机器学习算法：K-近邻算法实现手写数字识别系统
一、前提知识点：
1、参考Linux命令大全：http://man.linuxde.net/wget
命令wget：
用来从指定的URL下载文件；wget非常稳定，它在带宽很窄的情况下和不稳定网络中有很强的适应性，如果是由于网络的原因下载失败，wget会不断的尝试，直到整个文件下载完毕。如果是服务器打断下载过程，它会再次联到服务器上从停止的地方继续下载。这对从那些限定了链接时间的服务器上下载大文件非常有用。
使用wget下载单个文件
wget http://www.linuxde.net/testfile.zip
以下的例子是从网络下载一个文件并保存在当前目录，在下载的过程中会显示进度条，包含（下载完成百分比，已经下载的字节，当前下载速度，剩余下载时间）。
命令！：
2、Numpy教程：https://www.yiibai.com/numpy/numpy_matrix_library.html
https://docs.scipy.org/doc/numpy/reference/generated/numpy.tile.html
ndarray.shape：这一数组属性返回一个包含数组维度的元组，它也可以用于调整数组大小。
numpy.ndim:
下面的是摘自：https://blog.csdn.net/xiahei_d/article/details/52749395
在讲tile方法之前，先要讲一下Numpy数组中的几个概念。
在NumPy中，数组这一类又被称为ndarray。
2.1、ndarray.ndim
指数组的维度，即数组轴（axes）的个数，其数量等于秩（rank）。通俗地讲，我们平时印象中的数组就是一维数组，维度为1、轴的个数为1、秩也等于1；最常见的矩阵就是二维数组，维度为2、轴的个数为2（可以理解为由x轴、y轴组成）、秩等于2；我们所知的空间就相当于三维数组，维度为3、轴的个数为3（x、y、z轴）、秩等于3；以此类推。
2.2、ndarray.shape
按教程的话翻译过来是数组的维度，这样就很容易和ndim的概念混淆。所以可以这样理解，shape的返回值是一个元组，元组的长度就是数组的维数，即ndim。而元组中每个整数分别代表数组在其相应维度（/轴）上的大小。以最常见的矩阵为例，print shape后返回（2,3），说明这是一个2行3列的矩阵。
2.3、下面说一下tile函数，其原型如下。
原型：numpy.tile(A,reps)
tile共有2个参数，A指待输入数组，reps则决定A重复的次数。整个函数用于重复数组A来构建新的数组。
假设reps的维度为d，那么新数组的维度为max（d，A.ndim）。下面分三种情况进行讨论：
（1）A.dim < d
则向A中添加新轴扩充A的维度。维度大小可以从shape中看出，一般通过向shape对应的元组中添加1完成对A维度的扩充。扩充完成后，则可根据reps的值对A中相应维度的值进行重复。
例如，一维数组shape为（3，），扩充至2维则shape值为（1,3），扩充至3维则shape值为（1,1,3）
（2）A.dim > d
将reps扩充至与A相同的维度。扩充方法同上，也是向shape对应元组中添1，然后再进行重复。
例如，4维数组A的shape为（2,3,4,5），而reps为（2,2）只有2维，那么就要对reps添维进行扩充，得到（1,1,2,2）
（3）A.dim = d
不需要扩充，直接按reps的值对相应维度的值进行重复。
- >>>from numpy import *
- >>> a = array([1,2,3])
- >>>print a.shape
- (3.)
- >>>print a.ndim
- 1
- >>>b = tile(a,2)
- >>>print b
- [1 2 3 1 2 3]
- >>>print b.shape
- (6,)
- >>>print b.ndim
- 1
- >>>c = tile(a,(2,3))
- >>>print c
- [[1 2 3 1 2 3 1 2 3]
- [1 2 3 1 2 3 1 2 3]]
- >>>print c.shape
- (2,9)
- >>>print c.ndim
- 2
2.4、Numpy的tile函数（摘自：http://blog.sina.com.cn/s/blog_6bd0612b0101cr3u.html）
1.函数的定义与说明
tile函数是模板numpy.lib.shape_base中的函数。
函数的形式是tile(A,reps)
函数参数说明中提到A和reps都是array_like的，什么是array_like的parameter呢？在网上查了一下，始终搞不明白，便把熟悉的python数据类型都试了一下，得出以下结论。
A的类型众多，几乎所有类型都可以：array, list, tuple, dict, matrix以及基本数据类型int, string, float以及bool类型。
reps的类型也很多，可以是tuple，list, dict, array, int,bool.但不可以是float, string, matrix类型。
假定A的维度为d,reps的长度为len
当d>=len时，将reps长度补足为d，即在reps前面加上d-len个1。
这里的意思是，假设A为k维数组，每一维都有一定长度，构成的向量为D。
Numpy的tile函数
而长度为len的reps有len个数，进行tile函数运算时补足d位，前面加d-len个1，如下图所示：
Numpy的tile函数
经过tile运算，生成新的A，A的各维维度为：Numpy的tile函数
其中相乘的意思为，将原来A中每一维度的元素进行copy，生成的A中此元素出现次数为新的reps对应维度的数目。操作从低维度向高维进行。
当d
2.函数操作示例
首先给几个示例：
>>> tile(1.3,2)
array([ 1.3, 1.3])
array([1, 2, 1, 2, 1, 2])
>>> tile((1,2,3),2)
array([1, 2, 3, 1, 2, 3])
>>> a=[[1,2,3],[4,5,5]]
>>> tile(a,2)
array([[1, 2, 3, 1, 2, 3],
[4, 5, 5, 4, 5, 5]])
>>> tile([1,2,3],[2,2,2,2])
array([[[[1, 2, 3, 1, 2, 3],
[1, 2, 3, 1, 2, 3]],
[[1, 2, 3, 1, 2, 3],
[1, 2, 3, 1, 2, 3]]],
[[[1, 2, 3, 1, 2, 3],
[1, 2, 3, 1, 2, 3]],
[[1, 2, 3, 1, 2, 3],
[1, 2, 3, 1, 2, 3]]]])
拿其中一个例子进行说明：
>>> a=[[1,2],[2,3]]
>>> tile(a,2)
array([[1, 2, 1, 2],
[2, 3, 2, 3]])
这里a的维度为2，reps长度为1（仅仅是1个int类型数据）
则将reps长度补足为2，结果为reps = [1,2](这里也可以写成reps=(1,2)，都无妨的)
进行copy操作，从低维进行.数组a为a[2][2]
一维copy操作：copy两次。a[0]变为[1,2,1,2],a[1]变为[2,3,2,3]
二维copy操作，copy1次。a变为[[1,2,1,2],[2,3,2,3]]
a数组为a[2][4]
如此则不难理解下面的结果：
>>> tile(a,[1,2])
array([[1, 2, 1, 2],
[2, 3, 2, 3]])
>>> tile(a,[2,2])
array([[1, 2, 1, 2],
[2, 3, 2, 3],
[1, 2, 1, 2],
[2, 3, 2, 3]])
tile(a,[2,2])中是将上述第二步的对a的第二维的copy次数变成了两次，a[0]copy两次，a[1]copy两次：[a[0],a[0],a[1],a[1]]结果如上所示。
3.函数其他注意事项
①当reps为bool类型或者是bool list类型的时候，与int类型相对应，即True对应为1，False对应为0.如：
>>> tile([1,2],[True,False])
array([], shape=(1, 0), dtype=int32)
>>> tile([1,2],[True,True])
array([[1, 2]])
>>> tile([1,2],[True,True,True])
array([[[1, 2]]])
>>> tile([1,2],True)
array([1, 2])
②当reps为dict类型时，实则取的是key值列表，且key值列表为升序排列如下所示：
>>> tile([1,2,3],{1:2,3:4})
array([[1, 2, 3, 1, 2, 3, 1, 2, 3]])
>>> tile([1,2,3],{3:4,1:2})
array([[1, 2, 3, 1, 2, 3, 1, 2, 3]])
>>> a={1:2,3:4}
>>> tile([1,2,3],a.keys())
array([[1, 2, 3, 1, 2, 3, 1, 2, 3]])
③当A为int,string,float,bool,dict等类型的时候，操作大体相似，都是讲A视为一个整体，生成一个与reps的长度相同维度的数组。如下所示：
>>> tile({1:2,3:4,5:6},3)
array([{1: 2, 3: 4, 5: 6}, {1: 2, 3: 4, 5: 6}, {1: 2, 3: 4, 5: 6}], dtype=object)
>>> tile({1:2,3:4,5:6},[2,2])
array([[{1: 2, 3: 4, 5: 6}, {1: 2, 3: 4, 5: 6}],
[{1: 2, 3: 4, 5: 6}, {1: 2, 3: 4, 5: 6}]], dtype=object)
>>> tile('abc',3)
array(['abc', 'abc', 'abc'],
dtype='|S3')
>>> tile('abc',[3,3])
array([['abc', 'abc', 'abc'],
['abc', 'abc', 'abc'],
['abc', 'abc', 'abc']],
dtype='|S3')
>>> tile(2,3)
array([2, 2, 2])
>>> tile(2,[3,3])
array([[2, 2, 2],
[2, 2, 2],
[2, 2, 2]])
不过有所不同的是，当A为string类型以及dict类型的时候，array数组最后多了一个信息，即dtype，原因为何，即便看了一些源码，也不晓得是怎么回事，好像由array到ndarray，一大堆C的东西，搞不明白，索性作罢。另外，当对list类型进行mat操作然后作为参数A传入tile时也可以，不过结果类型不是array类型，而是matrix类型了，原因几何，我也无法解答。
看了tile的源码以后以上内容差不多都可以理解。例如之所以reps的类型有限制，在于代码一开始对reps进行了以下操作：
tuple(reps)，无法进行该操作的reps参数就会报错。而且dict类型的reps进行tuple化以后，key值以升序出现，这也是注意事项中2的原因，而list和tuple类型的数值顺序不变。
大概就是以上了。我对numpy这里了解的不是很多，还希望向内行多多讨教呢，所以有问题不妨留言~
2.5、operator.itemgetter(1)
（摘自：https://blog.csdn.net/u012005313/article/details/49154683
参考：http://www.cnblogs.com/100thMountain/p/4719503.html
http://blog.163.com/zhuandi_h/blog/static/1802702882012111284632184/）
operator模块提供的itemgetter函数用于获取对象的哪些维的数据，参数为一些序号（即需要获取的数据在对象中的序号）
注意：operator.itemgetter函数获取的不是值，而是定义了一个函数，通过该函数作用到对象上才能获取值。
sorted函数是内建函数
- help(sorted)
参数解释：
iterable：指定为要排序的list或iterable对象
cmp：接受一个函数(有两个参数)，指定排序时进行比较的函数，可以指定一个函数或lambda表达式，如：
- stu=[('jhon', 'a', 15), ('jane', 'b', 12), ('save', 'b', 10)]
- def f(a,b):
- return a-b
- sorted(stu, cmp=f)
key：接受一个函数(只有一个参数)，指定待排序元素的哪一项进行排序：
- sorted(stu, key=lambda student:student[2])
#####################################################################################
sorted函数和operator.itemgetter函数的使用
- stu=[('jhon', 'a', 15), ('jane', 'b', 12), ('save', 'b', 10)]
- sorted(students, key=operator.itemgetter(2))
- sorted(students, key=operator.itemgetter(1,2))
二、K-近邻算法：
思路：
首先：将每个文本文件中的数据转成个向量，准备个类别list、初始化（训练）样本数据矩阵、初始化错误率变量；
然后：将所有训练样本数据存入矩阵，同时将每行训练样本数据（每个文件的）对应的标签放入下标与其训练样本数据相同的类
别list中，针对每个文件的测试数据进行分类；
其中：分类器的实现--->计算测试数据与每个样本数据对应数据项的差值，然后按照距离从低到高排序（得索引数组），依次取出最近的样本数据，记录该测试样本数据所属的类别；对类别出现的频次进行排序，从高到底；最后返回出现频次最高的类别。
inX：用于分类的输入向量，（测试）数据向量：一次调用赋一个文件的。
dataSet：输入的训练样本集，（训练数据矩阵）：所有文件的训练数据。labels：样本数据的类标签向量
k：用于选择最近邻居的数目
最后：# 判断KNN算法结果是否准确，拿返回出现频次最高的类别跟已知结果的测试样本类别比较；对每个测试样本的分类错误进行累计计数，错误率=错误个数/所有的测试数据个数
代码：
def img2vector(filename):
# 创建向量
returnVect = np.zeros((1,1024))#[[ 0. 0. 0. ..., 0. 0. 0.]]
# 打开数据文件，读取每行内容
fr = open(filename)
for i in range(32):
# 读取每一行
lineStr = fr.readline()
# 将每行前 32 字符转成 int 存入向量
for j in range(32):
returnVect[0,32*i+j] = int(lineStr[j])
return returnVectimport operator
'''
inX：用于分类的输入向量，（测试）数据向量：一次调用赋一个文件的。
dataSet：输入的训练样本集，（训练数据矩阵）：所有文件的训练数据。
labels：样本数据的类标签向量
k：用于选择最近邻居的数目
'''
def classify0(inX, dataSet, labels, k):
# 获取（训练）样本数据数量(数组的行，每一行是一个数据点，每一行的每一列是该数据的特征。数组名.shape:数组的维数)
dataSetSize = dataSet.shape[0]
# 矩阵运算，计算测试数据与每个样本数据对应数据项的差值
#(tile共有2个参数，A指待输入数组，reps则决定A重复的次数。整个函数用于重复数组A来构建新的数组。)
diffMat = np.tile(inX, (dataSetSize,1)) - dataSet
# sqDistances 上一步骤结果平方和
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1)
# 取平方根，得到距离向量
distances = sqDistances**0.5
# 按照距离从低到高排序
#Returns:index_array(索引数组) : ndarray, int
#Array of indices that sort a along the specified axis.
#If a is one-dimensional, a[index_array] yields a sorted a.
sortedDistIndicies = distances.argsort()
classCount={}
# 依次取出最近的样本数据
for i in range(k):
# 记录该样本数据所属的类别
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1#类别出现的频次
# 对类别出现的频次进行排序，从高到低
#Python 字典(Dictionary) items() 函数以列表返回可遍历的(键, 值) 元组数组。
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
# 返回出现频次最高的类别
return sortedClassCount[0][0]
from os import listdir
def handwritingClassTest():
# 样本数据的类标签列表
hwLabels = []
# （训练）样本数据文件列表,列表元素都是文件名.后缀
trainingFileList = listdir('digits/trainingDigits')
m = len(trainingFileList)
# 初始化（训练）样本数据矩阵（M*1024）,每行代表每个文件，每列代表每个文件中的数据
trainingMat = np.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('digits/trainingDigits/%s' % fileNameStr)
# 循环读取测试数据
testFileList = listdir('digits/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('digits/testDigits/%s' % fileNameStr)
# 对数据文件进行分类，返回值：分类器返回的类别
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
# 打印KNN算法分类结果和真实的分类
print ("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))
# 判断KNN算法结果是否准确
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)))