机器学习第七天 K-NN算法的简单实现
数据包下载地址：
https://www.xiehaoo.com/media/record/pinke/2018/08/2.KNN.zip
KNN使用场景
电影可以按照题材分类，那么如何区分 动作片 和 爱情片 呢？
动作片：打斗次数更多
爱情片：亲吻次数更多
基于电影中的亲吻、打斗出现的次数，使用 k-近邻算法构造程序，就可以自动划分电影的题材类型。
现在根据上面我们得到的样本集中所有电影与未知电影的距离，按照距离递增排序，可以找到 k 个距离最近的电影。
假定 k=3，则三个最靠近的电影依次是， He's Not Really into Dudes 、 Beautiful Woman 和 California Man。
knn 算法按照距离最近的三部电影的类型，决定未知电影的类型，而这三部电影全是爱情片，因此我们判定未知电影是爱情片。
KNN开发流程
收集数据：任何方法
准备数据：距离计算所需要的数值，最好是结构化的数据格式
分析数据：任何方法
训练算法：此步骤不适用于KNN
测试算法：计算错误率
使用算法：输入样本数据和结构化的输出结果，然后运行KNN算法判断输入数据分类属于哪个分类，最后对计算出的分类执行后续处理
KNN算法特点
优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
适用数据范围：数值型和标称型
KNN是最简单的机器学习算法，没有之一
KNN算法伪代码：
"""
对于每一个在数据集中的数据点：
计算目标的数据点（需要分类的数据点）与该数据点的距离
将距离排序：从小到大
选取前K个最短距离
选取这K个中最多的分类类别
返回该类别来作为目标数据点的预测值
"""
def classify0(inX, dataSet, labels, k):
"""
距离度量 度量公式为欧氏距离
inX 图像文本转化的向量
dataSet <class 'numpy.ndarray'> 矩阵的长度
labels 存储0～9对应的index位置
k
"""
# >>print(type(dataSet))
# <class 'numpy.ndarray'>
# shape函数是numpy.core.fromnumeric中的函数，它的功能是读取矩阵的长度，比如shape[0]就是读取矩阵第一维度的长度。
dataSetSize = dataSet.shape[0]
# 原型：numpy.tile(A,reps)
# tile共有2个参数，A指待输入数组，reps则决定A重复的次数。整个函数用于重复数组A来构建新的数组。
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances ** 0.5
# 将距离排序：从小到大
sortedDistIndicies = distances.argsort()
# 选取前K个最短距离， 选取这K个中最多的分类类别
classCount = {}
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
KNN项目案例：手写数字识别系统
项目概述
构造一个能识别数字 0 到 9 的基于 KNN 分类器的手写数字识别系统。
需要识别的数字是存储在文本文件中的具有相同的色彩和大小：宽高是 32 像素 * 32 像素的黑白图像。
开发流程
收集数据：提供文本文件
准备数据：编写函数 img2vector，将图像格式转换为分类器使用的向量格式
分析数据：在python命令提示符中检查数据，确保它符合要求
训练算法：此步骤不适用于KNN
测试算法：编写函数使用提供的部分数据集作为测试样本，测试样本与非测试样本的区别在于测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误
第一步：收集数据：提供文本文件
第二步：准备数据,导入依赖包
#将图像文本数据转为向量
from numpy import zeros
from os import listdir
from numpy import zeros, tile
import operator
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
在python命令行中输入下列命令测试img2vector函数，然后与文本编辑器打开的文件进行比较：
testVector = img2vector('/Users/xiehao/Desktop/MachineLearning-master/input/2.KNN/testDigits/0_0.txt')
>>print(testVector[0,0:32])
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
>>print(testVector[0,32:64])
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
文本原件
0_0.txt
训练算法：此步骤不适用于KNN
因为测试数据每一次都要与全量的训练数据进行比较，所以这个过程是没有必要的。
测试算法：编写函数使用提供的部分数据集作为测试样本，如果预测分类与实际类别不同，则标记为一个错误
def handwritingClassTest():
# 1. 导入训练数据
hwLabels = []
trainingFileList = listdir(
'/Users/xiehao/Desktop/MachineLearning-master/input/2.KNN/trainingDigits/') # load the training set
m = len(trainingFileList)
print(m)
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(
'/Users/xiehao/Desktop/MachineLearning-master/input/2.KNN/trainingDigits/%s' % fileNameStr)
# 2. 导入测试数据
testFileList = listdir(
'/Users/xiehao/Desktop/MachineLearning-master/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(
'/Users/xiehao/Desktop/MachineLearning-master/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)))
执行handwritingClassTest()
the classifier came back with: 4, the real answer is: 4
the classifier came back with: 4, the real answer is: 4
the classifier came back with: 3, the real answer is: 3
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 0, the real answer is: 0
........
the classifier came back with: 3, the real answer is: 3
the classifier came back with: 3, the real answer is: 3
the total number of errors is: 11
the total error rate is: 0.011628
可以看到1934个样本只有11个错误，分类准确率99.43%，还是很可以的
Github原项目地址https://github.com/apachecn/MachineLearning
原是用python2写的，我用python3做了一些修改，明天一步一步解析识别的实现，同时实现另一个分类项目
