k-近邻算法
先来一个简单的例子，我们如何来区分动作类电影与爱情类电影呢？动作片中存在很多的打斗镜头，爱情片中可能更多的是亲吻镜头，所以我们姑且通过这两种镜头的数量来预测这部电影的主题。简单的说，k-近邻算法采用了测量不同特征值之间的距离方法进行分类。
优点：精度高、对异常值不敏感、无数据输入假定 缺点：计算复杂度高、控件复杂度高 适用数据范围：数值型和标称型
首先我们来理解它的工作原理：
存在一个样本数据集（训练集），并且我们知道每一数据与目标变量的对应关系，输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中最相近的分类标签，一般来说，我们只选择样本集中前k个最相似的数据，通常k为不大于20的整数，最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
现在我们回到文章开头所提到的电影的例子，根据下表如何确定未知的电影类型呢？
电影名称打斗镜头接吻镜头电影类型电影13104爱情电影22100爱情电影3181爱情电影410110动作电影5995动作电影6982动作电影71890未知？该如何计算电影7的电影类型呢？计算电影7与样本集中其他电影的距离，然后我们假定k=3，看一下最近的3部电影是什么类型即可预测出电影7的电影类型。
流程介绍
- 收集数据
- 准备数据：距离计算所需要的值，最好是结构化的数据格式
- 分析数据
- 测试算法：计算错误率
- 使用算法
开始工作
使用python导入数据
首先，创建名为kNN.py的Python模块，在构造算法之前，我们还需要编写一些通用的函数等，我们先写入一些简单的代码：
from numpy import *import operatordef createDataSet(): group = array([ [1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1] ]) labels = ["A", "A", "B", "B"] return group, labels
然后将终端改变到代码文件目录，输入命令python进入到交互界面：
>>> import kNN>>> group, labels = kNN.createDataSet()>>> grouparray([[ 1. , 1.1], [ 1. , 1. ], [ 0. , 0. ], [ 0. , 0.1]])>>> labels['A', 'A', 'B', 'B']
这里有4组数据，每组数据有2个我们已知的特征值，上面的group矩阵每行为一条数据，对于每个数据点我们通常使用2个特征（所以特征的选择很重要），向量labels包含了每个数据点的标签信息，labels的维度等于矩阵的行数，这里我们将[1, 1,1]定为类A，[0, 0.1]定为类B，接下来我们进行算法的编写：
- 计算已知数据集中点到当前点之间的距离
- 按照距离递增次序排序
- 选取与当前点距离最小的k个点
- 确定前k个点所在类别的出现频率
- 返回前k个点中频次最高的类别作为预测类别
接着定义函数：