本渣渣（WordZzzz直接被舍友叫成了“我的渣”，所以以后我在博客中就以此自居了！），最近在学习Peter Harrington的Machine Learning in Action，一边看书一边用Python3.6实现课本中的算法（原书中使用的是Python2.x）。好记性不如烂笔头，奈何本渣渣连烂笔头都买不起，所以就来这不费笔墨的地方费尽心思写博客。本渣渣记性不是一般的差，在此记下每个算法的学习要点及Python代码实现，一方面方便自己以后复习，另一方面贴出来和大家一起学习，共同进步~~~
注意：python3.x与python2.x的部分函数库有较大差异，针对这个问题，本渣渣会将代码版本升级中遇到的问题在每篇博文的最后列出来，并加以解释说明，帮助大家区分理解。
原著代码（python2.x）地址：https://www.manning.com/books/machine-learning-in-action 本渣渣代码（python3.x）地址：https://github.com/WordZzzz/ML/tree/master/Ch02
博客中的代码都会在本渣渣的GitHub上贴出，欢迎Watch、Star、Fork。
k-近邻算法（kNN）的工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法的中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。 简单的说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。
书上有个电影分类的例子，使用k-近邻算法分类爱情片和工作片。书中给出了6部电影的打斗镜头数和接吻镜头数，如图2-1所示。
假如有一部未看过的电影，如何确定它是爱情片还是动作片呢？下面我们将使用kNN来解决这个问题。
首先，我们需要数据，即这个未知电影存在多少个打斗镜头和接吻镜头，图2-1中间问号位置是该电影出现的镜头数图像化的结果，具体数字参见表2-1。
电影名称打斗镜头接吻镜头电影类型California Man3104爱情片He is Not Really into Dudes2100爱情片Beautiful Woman181爱情片Kevin Longblade10110动作片Robo Slayer 3000995动作片Amped Ⅱ982动作片？1890未知型[表2-1 每部电影的镜头统计及电影评估类型]
计算未知电影和样本集中其他电影的距离，如表2-2所示。我们暂且不关心如何计算得到这些距离值，后面会提供具体的计算方法。
电影名称与未知电影的距离California Man20.5He is Not Really into Dudes18.7Beautiful Woman19.2Kevin Longblade115.3Robo Slayer 3000117.4Amped Ⅱ9118.9[表2-2 已知电影与未知电影的距离]
现在我们得到了样本集中所有电影与未知电影的距离，按照距离递增排序，可以找到k个距离最近的电影。假定k = 3，则三个最靠近的电影依次是He is Not Really into Dudes、Beautiful Woman、California Man。k-近邻算法按照距离最近的三部电影的类型，决定位置电影的类型，而这三部电影全是爱情片，所以我们判定未知电影为爱情片。
首先，创建名为kNN.py的Python模块。所有代码都已做出详细注释，所以不再赘述，如有疑问可以在下方评论哦~
2.1 创建数据集和标签：
代码实现：
# -*- coding: UTF-8 -*- """ Created on Aug 18, 2017 kNN: k Nearest Neighbors Input: inX: vector to compare to existing dataset (1xN) dataSet: size m data set of known vectors (NxM) labels: data set labels (1xM vector) k: number of neighbors to use for comparison (should be an odd number) Output: the most popular class label @author: wordzzzz """ from numpy import * import operator def createDataSet(): """ Function： 创建数据集和标签 Args： 无 Returns： group：创建的数据集 labels：创建的标签 """ #创建数据集 group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]]) #创建标签 labels = ['A', 'A', 'B', 'B'] #返回创建的数据集和标签 return group, labels保存编写好的kNN.py模块，在Windows下打开命令提示符。如果不想在终端通过命令行一步一步敲到当前目录，可以直接在当前文件夹按住shift+右键，这个时候便会出现命令提示符的选项，单击后终端内直接显示当前文件夹。然后输入python，进入python编译开发环境。
输出结果：
>>> import kNN >>> group,labels = kNN.createDataSet() >>> group array([[ 1. , 1.1], [ 1. , 1. ], [ 0. , 0. ], [ 0. , 0.1]]) >>> labels ['A', 'A', 'B', 'B']向量labels包含了每个数据点的标签信息，labels包含的元素个数等于group矩阵行数。这里我们将数据点(1, 1.1)定义为类A，数据点(0, 0.1)定义为类B。为了说明方便，例子中的数值是任意选择的，并没有给出轴标签，图2-2是带有标签信息的四个数据点。
2.2 实施kNN分类算法：
伪代码： 对未知类别属性的数据集中的每个点依次执行以下操作：
(1).计算已知类别数据集中的点与当前点之间的距离；(2).按照距离递增次序排序；(3).选取与当前点距离最小的k个点；(4).确定前k个点所在类别的出现频率；(5).返回前k个点出现频率最高的类别作为当前点的预测分类。这里我们使用欧氏距离公式，计算两个向量点xA和xB之间的距离：
d=(xA0−xB0)2+(xA1−xB1)2−−−−−−−−−−−−−−−−−−−−−−−√如果特征值有多个，那公式就变成了这个样子：
d=∑i=0N(xAi−xBi)2−−−−−−−−−−−−−⎷代码实现：
def classify0(inX, dataSet, labels, k): """ Function： 创建数据集和标签 Args： inX：用于分类的输入向量 (1xN) dataSet：输入的训练样本集 (NxM) labels：标签向量 (1xM vector) k：用于比较的近邻数量 (should be an odd number) Returns： sortedClassCount[0][0]：分类结果 """ #dataSet.shape[0]：求dataSet矩阵的行数 #dataSet.shape[1]：求dataSet矩阵的列数 #dataSet.shape：元组形式输出矩阵行数、列数 dataSetSize = dataSet.shape[0] #tile(A, B)：将A重复B次，其中B可以是int类型也可以是元组类型 #这句话相当于向量inX与矩阵dataSet里面的每组数据做差 diffMat = tile(inX, (dataSetSize, 1)) - dataSet #对求差后的矩阵求平方 sqDiffMat = diffMat**2 #sqDiffMat.sum(axis=0)：对矩阵的每一列求和 #sqDiffMat.sum(axis=1)：对矩阵的每一行求和 #sqDiffMat.sum()：对整个矩阵求和 sqDistances = sqDiffMat.sum(axis=1) #求平方根 distances = sqDistances**0.5 #对上式结果进行排序 sortedDistIndicies = distances.argsort() #创建字典 classCount = {} #给字典赋值 for i in range(k): #字典的key voteIlabel = labels[sortedDistIndicies[i]] #classCount.get(voteIlabel,0)：如果字典键的值中有voteIlabel，则返回0（第二个参数的值） classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #对classCount进行排序，sroted、items以及itermgetter随后讲解@1 sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) #返回分类结果 return sortedClassCount[0][0]保存编写好的kNN.py模块，此时如果你不重新加载模块，你的命令提示符里面已经加载过的模块是不会自动更新的。所以我们需要调用imp模块中的reload来重新加载新保存的模块。我们输入两个不同的例子[0.9, 0.9][0.1, 0.1]，得到相应的分类结果并输出。
输出结果：
>>> from imp import reload >>> reload(kNN) >>> kNN.classify0([0.9,0.9], group, labels, 3) 'A' >>> kNN.classify0([0.1,0.1], group, labels, 3) 'B'详解： 1.sorted,sort以及argsort：
http://blog.csdn.net/u011475210/article/details/77769245
http://blog.csdn.net/u011475210/article/details/77770751
2.items等：
http://blog.csdn.net/u011475210/article/details/77770145
3.itemgetter等：
http://blog.csdn.net/u011475210/article/details/77770772
系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～
完的汪(∪｡∪)｡｡｡zzz
