k－近邻算法
一、算法原理
算法原理是什么？允许我不严谨的说一下：首先有一堆有标签的样本，比如有一堆各种各样的鸟（样本集），我知道各种鸟的不同外貌（特征），比如羽毛颜色、有无脚蹼、身体重量、身体长度以及最重要的它属于哪一种鸟（类别/标签）；然后给我一只不是这堆鸟中的一只鸟（测试样本），让我观察了它的羽毛颜色等后，让我说出它属于哪一种鸟？我的做法是：遍历之前的一堆鸟，分别比较每一只鸟的羽毛颜色、身体重量等特征与给定鸟的相应特征，并给出这两只鸟的相似度。最终，从那一堆鸟中找出相似度最大的前k只，然后统计这k只鸟的分类，最后把分类数量最多的那只鸟的类别作为给定鸟的类别。虽然结果不一定准确，但是是有理论支持的，那就是概率论，哈哈。
下面来看一下书上对这个算法的原理介绍：存在一个训练样本集，并且每个样本都存在标签（有监督学习）。输入没有标签的新样本数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取出与样本集中特征最相似的数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，而且k通常不大于20。最后选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
二、如何解决问题
没接触过的同学应该能懂了吧。书中的举例是对电影的题材进行分类：爱情片or动作片。依据电影中打斗镜头和接吻镜头的数量。下面来看一下如何用kNN来解决这个问题。
要解决给定一部电影，判断其属于哪一种电影这个问题，就需要知道这个未知电影存在多少个打斗镜头和接吻镜头，如上图所示，问号位置所代表的两种镜头次数分别是多少？
下面我们来看一下图中电影的特征值，如下表：
相信看过数据以后，即使不知道未知电影（?）属于哪一种类型，但是可以通过某个计算方法计算出来。
第一步：首先计算未知电影与已知电影的相似度（抽象距离--相似度越小，距离越远）。具体如何计算暂且不考虑。下面看一下相似度列表：
第二步：再将相似度列表排序，选出前k个最相似的样本。此处我们假设k=3，将上表中的相似度进行排序后前3分别是：He’s Not Really into Dudes，Beautiful Woman，California Man。
第三步：统计最相似样本的分类。此处很容易知道这3个样本均为爱情片。
第四步：将分类最多的类别作为未知电影的分类。那么我们就得出结论，未知电影属于爱情片。
下面贴一下书上总结的k近邻算法的一般流程：
#coding=UTF8
from numpy import *
import operator
def createDataSet():
"""
函数作用：构建一组训练数据（训练样本），共4个样本
同时给出了这4个样本的标签，及labels
"""
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 是输入的测试样本，是一个[x, y]样式的
dataset 是训练样本集
labels 是训练样本标签
k 是top k最相近的
"""
# shape返回矩阵的[行数，列数]，
# 那么shape[0]获取数据集的行数，
# 行数就是样本的数量
dataSetSize = dataset.shape[0]
"""
下面的求距离过程就是按照欧氏距离的公式计算的。
即 根号(x^2+y^2)
"""
# tile属于numpy模块下边的函数
# tile（A, reps）返回一个shape=reps的矩阵，矩阵的每个元素是A
# 比如 A=[0,1,2] 那么，tile(A, 2)= [0, 1, 2, 0, 1, 2]
# tile(A,(2,2)) = [[0, 1, 2, 0, 1, 2],
# [0, 1, 2, 0, 1, 2]]
# tile(A,(2,1,2)) = [[[0, 1, 2, 0, 1, 2]],
# [[0, 1, 2, 0, 1, 2]]]
# 上边那个结果的分开理解就是：
# 最外层是2个元素，即最外边的[]中包含2个元素，类似于[C,D],而此处的C=D，因为是复制出来的
# 然后C包含1个元素，即C=[E],同理D=[E]
# 最后E包含2个元素，即E=[F,G],此处F=G，因为是复制出来的
# F就是A了，基础元素
# 综合起来就是(2,1,2)= [C, C] = [[E], [E]] = [[[F, F]], [[F, F]]] = [[[A, A]], [[A, A]]]
# 这个地方就是为了把输入的测试样本扩展为和dataset的shape一样，然后就可以直接做矩阵减法了。
# 比如，dataset有4个样本，就是4*2的矩阵，输入测试样本肯定是一个了，就是1*2，为了计算输入样本与训练样本的距离
# 那么，需要对这个数据进行作差。这是一次比较，因为训练样本有n个，那么就要进行n次比较；
# 为了方便计算，把输入样本复制n次，然后直接与训练样本作矩阵差运算，就可以一次性比较了n个样本。
# 比如inX = [0,1],dataset就用函数返回的结果，那么
# tile(inX, (4,1))= [[ 0.0, 1.0],
# [ 0.0, 1.0],
# [ 0.0, 1.0],
# [ 0.0, 1.0]]
# 作差之后
# diffMat = [[-1.0,-0.1],
# [-1.0, 0.0],
# [ 0.0, 1.0],
# [ 0.0, 0.9]]
diffMat = tile(inX, (dataSetSize, 1)) - dataset
# diffMat就是输入样本与每个训练样本的差值，然后对其每个x和y的差值进行平方运算。
# diffMat是一个矩阵，矩阵**2表示对矩阵中的每个元素进行**2操作，即平方。
# sqDiffMat = [[1.0, 0.01],
# [1.0, 0.0 ],
# [0.0, 1.0 ],
# [0.0, 0.81]]
sqDiffMat = diffMat ** 2
# axis=1表示按照横轴，sum表示累加，即按照行进行累加。
# sqDistance = [[1.01],
# [1.0 ],
# [1.0 ],
# [0.81]]
sqDistance = sqDiffMat.sum(axis=1)
# 对平方和进行开根号
distance = sqDistance ** 0.5
# 按照升序进行快速排序，返回的是原数组的下标。
# 比如，x = [30, 10, 20, 40]
# 升序排序后应该是[10,20,30,40],他们的原下标是[1,2,0,3]
# 那么，numpy.argsort(x) = [1, 2, 0, 3]
sortedDistIndicies = distance.argsort()
# 存放最终的分类结果及相应的结果投票数
classCount = {}
# 投票过程，就是统计前k个最近的样本所属类别包含的样本个数
for i in range(k):
# index = sortedDistIndicies[i]是第i个最相近的样本下标
# voteIlabel = labels[index]是样本index对应的分类结果('A' or 'B')
voteIlabel = labels[sortedDistIndicies[i]]
# classCount.get(voteIlabel, 0)返回voteIlabel的值，如果不存在，则返回0
# 然后将票数增1
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
# 把分类结果进行排序，然后返回得票数最多的分类结果
# classCount.items():迭代器，获得每一个对象
# operator.itemgetter(1):表示获取函数一维数据进行排序，即按照其投票数进行排序
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
