K近邻算法(KNN)
KNN算法原理
k近邻法(k-nearest neighbor, k-NN)一种基本分类与回归方法。它的工作原理是：存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
距离度量
我们已经知道k-近邻算法根据特征比较，然后提取样本集中特征最相似数据（最近邻）的分类标签，那么如何进行比较？KNN算法通过距离（欧式距离）度量进行判断。
Note:距离度量方法还有切比雪夫距离、马氏距离、巴氏距离等；
简单k-近邻算法步骤
1.计算已知类别数据集中的点与当前点的距离
2.按照距离递增次序排序
3.选取与当前点距离最小的k个点
4.确定前k个点所在类别的出现频率
5.返回前k个点所出现频率最高的类别作为当前点的预测分类
KNN的一般流程
1.收集数据：爬虫/第三方提供的免费/收费数据。一般来讲，数据放在txt文本文件中，按照一定的格式进行存储，便于解析和处理。
2.准备数据：使用python解析、预处理数据
3.分析数据：可以使用很多方法对数据进行分析。例如使用Matplotlib将数据可视化
4.测试算法：计算错误率
5.使用算法：错误率在可接受范围内，就可以使用k-近邻算法进行分类
KNN的优缺点
优点
1.简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归
2.可用于数值型数据和离散型数据
3.训练时间复杂度为O(n);无数据输入假定；
4.对异常值不敏感
缺点
1.计算复杂性高；空间复杂性高
2.样本不平衡问题（即有些类别的样本数量很多，而其他样本的数量很少）
3.一般数值很大的时候不用这个，计算量太大。但是单个样本也不能太少，否则容易发生误分。
4.最大的缺点是无法给出数据的内在含义