《机器学习实战》第二章 k-近邻算法 详细注释
考研结束，算起来有半年没写程序啦，基础函数都有些记不清了，所以代码基本上每一行都写上了注释，帮助理解记忆。
疫情严重，不能出门，那就宅在家里一起学习吧~ 争取日更！
章节内容
- k-近邻算法的基本理论;
- 如何使用距离测量的方法分类物品；
- 使用Python从文本文件中导入并解析数据；
- 当存在许多数据来源时，如何避免计算距离时可能碰到的一些常见错误；
- 使用k-近邻算法改进约会网站和手写数字识别系统。
k-近邻算法概述工作原理
训练样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，只选择样本数据集中前k个最相似的数据，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
例如电影分类，使用kNN确定它是爱情片还是动作片。
表2-1 每部电影的打斗镜头数、接吻镜头数以及电影评估类型
开发机器学习应用的通用步骤
1. 收集数据
2. 准备输入数据， 确保数据格式符合要求，本书采用的格式是Python语言的List。
3. 分析输入数据，确保数据中没有垃圾数据。
4. 训练算法（kNN不需要此步）
5. 测试算法，评估算法，计算错误率。
6. 使用算法
使用k-近邻算法将每组数据划分到某个类中，伪代码如下：
对未知类别属性的数据集中的每个点依次执行以下操作：
(1) 计算已知类别数据集中的点与当前点之间的距离；
(2) 按照距离递增次序排序；
(3) 选取与当前点距离最小的k个点；
(4) 确定前k个点所在类别的出现频率；
(5) 返回前k个点出现频率最高的类别作为当前点的预测分类。
构建分类器——
def classify0(inX, dataSet, labels, k):
#用于分类的输入向量是inX，输入的训练样本集为dataSet，标签向量为labels，最后的参数k表示用于选择最近邻居的数目
dataSetSize = dataSet.shape[0] # shape[0]是读取矩阵第一维度的长度，即数据的条数
# 计算距离
diffMat = tile(inX, (dataSetSize,1)) - dataSet #将目标复制成n行，计算得目标与每个训练数值之间的数值之差。
sqDiffMat = diffMat**2 #各个元素分别平方
sqDistances = sqDiffMat.sum(axis=1) #对应行的平方相加，即得到了距离的平方和
distances = sqDistances**0.5 #开根号，得到距离
#排序，确定前k个距离最小元素所在的主要分类
sortedDistIndicies = distances.argsort() #argsort函数返回的是数组值从小到大的索引值
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分类器
'''
from numpy import *
import operator #运算符模块
# 创建数据集和标签
group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
labels = ['A','A','B','B']
def classify0(inX, dataSet, labels, k):
#用于分类的输入向量是inX，输入的训练样本集为dataSet，标签向量为labels，最后的参数k表示用于选择最近邻居的数目
dataSetSize = dataSet.shape[0] # shape[0]是读取矩阵第一维度的长度，即数据的条数
# 计算距离
diffMat = tile(inX, (dataSetSize,1)) - dataSet #将目标复制成n行，计算得目标与每个训练数值之间的数值之差。
sqDiffMat = diffMat**2 #各个元素分别平方
sqDistances = sqDiffMat.sum(axis=1) #对应行的平方相加，即得到了距离的平方和
distances = sqDistances**0.5 #开根号，得到距离
#排序，确定前k个距离最小元素所在的主要分类
sortedDistIndicies = distances.argsort() #argsort函数返回的是数组值从小到大的索引值
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]
print("该数据的类别是" + classify0([0, 0],group, labels, 3))
以下是本代码中的一些（可能小白都知道的）细节——
.pyc文件
py文件作为模块被import时，python编译后产生pyc文件，目的是提高解析速度。当有别的程序再次import此模块时，python读入pyc文件即可，无需重新解析py文件。
shape函数
是numpy中的函数，功能是读取矩阵的长度。
shape[0] 读取矩阵第一维度的长度
tile函数
是numpy中的函数，将原矩阵横向、纵向地复制。tile 是瓷砖的意思，顾名思义，这个函数就是把数组像瓷砖一样铺展开来。
tile(mat, (3, 4)) 将矩阵mat复制成3*4块
** 代表乘方，开根号就是 **0.5
axis=1
第0轴沿着行的垂直往下，第1轴沿着列的方向水平延伸。
a = np.sum([[1, 1, 1], [2, 2, 2]], axis=0)
输出[3 3 3]，每列之和
a = np.sum([[1, 1, 1], [2, 2, 2]], axis=1)
输出[3 6]，每行之和
argsort()
argsort函数返回的是数组值从小到大的索引值。
range()
range()是python的内置函数， 语法：range(start, stop[, step])
range(5)即前5个数， range（0,5）实际上就是索引从0开始到4结束的5个整数。step是步长，默认步长为1。
itemgetter函数
根据某个或某几个字典字段来排序Python列表。
报错 ‘dict’ object has no attribute 'iteritems’
在python3报错，将iteritems改为items即可。iteritems是为python2环境中dict的函数。