机器学习之knn算法保姆级教学
K-近邻算法
学习⽬标：
掌握K-近邻算法实现过程
知道K-近邻算法的距离公式
知道K-近邻算法的超参数K值以及取值问题
知道kd树实现搜索的过程
应⽤KNeighborsClassifier实现分类
知道K-近邻算法的优缺点
知道交叉验证实现过程
知道超参数搜索过程
应⽤GridSearchCV实现算法参数的调优
一. K-近邻算法(KNN)概念
K Nearest Neighbor算法⼜叫KNN算法，这个算法是机器学习⾥⾯⼀个⽐较经典的算法， 总体来说KNN算法是相对⽐较容易理解的算法
定义:如果⼀个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的⼤多数属于某⼀个类别，则该样本也属于这个类别。
距离公式:两个样本的距离可以通过如下公式计算，⼜叫欧式距离 ，关于距离公式会在后⾯进⾏讨论
1. KNN算法流程总结
1）计算已知类别数据集中的点与当前点之间的距离
2）按距离递增次序排序
3）选取与当前点距离最⼩的k个点
4）统计前k个点所在的类别出现的频率
5）返回前k个点出现频率最⾼的类别作为当前点的预测分
K-近邻算法简介 定义:就是通过你的"邻居"来判断你属于哪个类别 如何计算你到你的"邻居"的距离：⼀般时候,都是使⽤欧⽒距离
二.k近邻算法api初步使⽤
1 Scikit-learn⼯具介
1.1 安装
pip3 install scikit-learn==1.0.2安装好之后可以通过以下命令查看是否安装成功
import sklearn注：安装scikit-learn需要Numpy, Scipy等库
2. Scikit-learn包含的内容
分类、聚类、回归，特征⼯程，模型选择、调优
sklearn.neighbors.KNeighborsClassifier(n_neighbors=5)
n_neighbors：int,可选（默认= 5），k_neighbors查询默认使⽤的邻居
3. k值的选择
K值过⼩：容易受到异常点的影响
k值过⼤：受到样本均衡的问题
K值选择问题，李航博⼠的⼀书「统计学习⽅法」上所说：
1) 选择较⼩的K值，就相当于⽤较⼩的领域中的训练实例进⾏预测，“学习”近似误差会减⼩，只有与输⼊实例较近或相似的训练实例才会对预测结果起作⽤，与此同时带来的问题是“学习”的估计误差会增⼤，换句话说，K值的减⼩就意味着整体模型变得复杂，容易发⽣过拟合；
2) 选择较⼤的K值，就相当于⽤较⼤领域中的训练实例进⾏预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增⼤。这时候，与输⼊实例较远（不相似的）训练实例也会对预测器作⽤，使预测发⽣错误。且K值的增⼤就意味着整体的模型变得简单。
3) K=N（N为训练样本个数），则完全不⾜取，因为此时⽆论输⼊实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单，忽略了训练实例中⼤量有⽤信息。在实际应⽤中，K值⼀般取⼀个⽐较⼩的数值，例如采⽤交叉验证法（简单来说，就是把训练数据在分成两组:训集和验证集）来选择最优的K值。
4.kd树
1.1 什么是kd树
根据KNN每次需要预测⼀个点时，我们都需要计算训练数据集⾥每个点到这个点的距离，然后选出距离最近的k个点进⾏投票。当数据集很⼤时，这个计算成本⾮常⾼，针对N个样本，D个特征的数据集，其算法复杂度为O（DN² ）。
kd树：为了避免每次都重新计算⼀遍距离，算法会把距离信息保存在⼀棵树⾥，这样在计算之前从树⾥查询距离信息，尽量避免重新计算。其基本原理是，如果A和B距离很远，B和C距离很近，那么A和C的距离也很远。有了这个信息，就可以在合适的时候跳过距离远的点。
这样优化后的算法复杂度可降低到O（DNlog（N））。感兴趣的读者可参阅论⽂：Bentley，J.L.，Communications of the ACM（1975）。1989年，另外⼀种称为Ball Tree的算法，在kd Tree的基础上对性能进⼀步进⾏了优化。感兴趣的读者可以搜索Five balltree construction algorithms来了解详细的算法信息。
kd树的构建过程：
1.构造根节点
2.通过递归的⽅法，不断地对k维空间进⾏切分，⽣成⼦节点
3.重复第⼆步骤，直到⼦区域中没有示例时终⽌
需要关注细节：a.选择向量的哪⼀维进⾏划分；b.如何划分数据
kd树的搜索过程：
1.⼆叉树搜索⽐较待查询节点和分裂节点的分裂维的值，（⼩于等于就进⼊左⼦树分⽀，⼤于就进⼊右⼦树分⽀直到叶⼦结点）
2.顺着“搜索路径”找到最近邻的近似点
3.回溯搜索路径，并判断搜索路径上的结点的其他⼦结点空间中是否可能有距离查询点更近的数据点，如果有可能，则需要跳到其他⼦结点空间中去搜索
4.重复这个过程直到搜索路径为空
三. 案例：鸢尾花种类预测--数据集介绍
import pandas as pd
from sklearn.neighbors import KNeighborsClassifier
test_data=pd.read_excel('鸢尾花测试数据.xlsx')
train_data=pd.read_excel('鸢尾花训练数据.xlsx')
train_x=train_data[['萼片长(cm)','萼片宽(cm)','花瓣长(cm)','花瓣宽(cm)']]
train_y=train_data[['类型_num']]
knn=KNeighborsClassifier(n_neighbors=5)
knn.fit(train_x,train_y)
train_predicted=knn.predict(train_x)
score=knn.score(train_x,train_y)
print(score)
test_x=test_data[['萼片长(cm)','萼片宽(cm)','花瓣长(cm)','花瓣宽(cm)']]
test_y=test_data[['类型_num']]
train_predicted=knn.predict(test_x)
score=knn.score(test_x,test_y)
print(score)
第一，二行代码：导入pandas库和从 scikit-learn 库导入 K 近邻分类器
第三，四行：读取测试集和训练集
第五行：提取训练数据的特征（四个花的形态特征）
第六行：提取训练数据的标签（花的类别）
第七，八行：创建 KNN 分类器，设置近邻数为 5，使用训练数据拟合模型，即训练模型
第九到十一行：用训练好的模型预测训练集，计算模型在训练集上的准确率并输出
11-12行：提取测试数据的特征，提取测试数据的标签
13-16行：用训练好的模型预测测试集，计算模型在测试集上的准确率，输出测试集准确率
四.KNN算法总结
优点：1.简单有效
2.重新训练的代价低
3.适合类域交叉样本
4.KNN⽅法主要靠周围有限的邻近的样本,⽽不是靠判别类域的⽅法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN⽅法较其他⽅法更为适合。
5.适合⼤样本⾃动分类，该算法⽐较适⽤于样本容量⽐较⼤的类域的⾃动分类，⽽那些样本容量较⼩的类域采⽤这种算法⽐较容易产⽣误分。
缺点：
1.惰性学习KNN算法是懒散学习⽅法（lazy learning,基本上不学习），⼀些积极学习的算法要快很多
2.类别评分不是规格化，不像⼀些通过概率评分的分类
3.输出可解释性不强例如决策树的输出可解释性就较强
4.对不均衡的样本不擅⻓
当样本不平衡时，如⼀个类的样本容量很⼤，⽽其他类样本容量很⼩时，有可能导致当输⼊⼀个新样本时，该样本的K个邻居中⼤容量类的样本占多数。该算法只计算“最近的”邻居样本，某⼀类的样本数量很⼤，那么或者这类样本并不接近⽬标样本，或者这类样本很靠近⽬标样本。⽆论怎样，数量并不能影响运⾏结果。可以采⽤权值的⽅法（和该样本距离⼩的邻居权值⼤）来改进。
5.计算量较⼤
⽬前常⽤的解决⽅法是事先对已知样本点进⾏剪辑，事先去除对分类作⽤不⼤的样本