要点：模型、策略(误分类率最小)、算法(构建kd树)

一、模型

1. 定义

K Nearest Neighbor算法又叫KNN算法；俗语形容：近朱者赤，近墨者黑
如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别；

2. 距离度量

欧式距离(欧几里得)
Lp距离定义(闵可夫斯基距离)
其他距离(了解)
- 标准化欧式距离
- 余旋距离
- 汉明距离
- 杰卡德距离
- 马氏距离

二、策略

1. K值如何选择

K值选择对模型的影响：
- K值过小
  - 模型变得复杂
  - 容易收到异常点的影响
  - 容易过拟合
- K值过大
  - 模型变得简单
  - 收到样本均衡的问题
  - 容易欠拟合
误差分类：
- 近似误差
  - 对现有训练集的训练误差，关注训练集，
  - 如果近似误差过小可能会出现过拟合的现象，对现有的训练集能有很好的预测，但是对未知的测试样本将会出现较大偏差的预测。
  - 模型本身不是最接近最佳模型。
- 估计误差
  - 可以理解为对测试集的测试误差，关注测试集；
  - 估计误差小说明对未知数据的预测能力好；
  - 模型本身最接近最佳模型。
K值一般取奇数、较小的数值

2. 分类决策规则

在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法(简单来说，就是把训练数据在分成两组:训练集和验证集)来选择最优的K值。

三、算法

kd树(K-dimension tree)是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。
kd树是一种二叉树，表示对k维空间的一个划分，构造kd树相当于不断地用垂直于坐标轴的超平面将K维空间切分，构成一系列的K维超矩形区域。
kd树的每个结点对应于一个k维超矩形区域。
利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

1. 构造kd树

1.构造根节点
2.通过递归的方法，不断地对k维空间进行切分，生成子节点
3.重复第二步骤，直到子区域中没有示例时终止
需要关注细节:a.选择向量的哪一维进行划分;b.如何划分数据

2. 搜索kd树

1.二叉树搜索比较待查询节点和分裂节点的分裂维的值 (小于等于就进入左子树分支，大于就进入右子树分支直到叶子结点)
2.顺着“搜索路径”找到最近邻的近似点
3.回溯搜索路径，并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点，如果有可能，则需要跳到其他子结点空间中去搜索
4.重复这个过程直到搜索路径为空

四、鸢尾花种类预测

Scikit-learn

 # 安装Scikit-learn

 pip3 install scikit-learn==0.19.1

API介绍
- sklearn.neighbors.KNeighborsClassifier(n_neighbors=5)
  - n_neighbors:int,可选(默认= 5)，k_neighbors查询默认使用的邻居数

鸢尾花种类预测—代码实现

 from sklearn.datasets import load_iris
 from sklearn.model_selection import train_test_split
 from sklearn.preprocessing import StandardScaler
 from sklearn.neighbors import KNeighborsClassifier

 # 1 获取数据集

 iris = load_iris()

 # 2 数据基本处理: 对鸢尾花数据集进行分割

 # 训练集的特征值x_train 测试集的特征值x_test 训练集的目标值y_train 测试集的目标值y_test

 # random_state  随机数种子, 的作用是保证每次切分的数据不变，控制变量法

 x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, random_state=22)

 # 3 特征预处理：标准化（一是取消量纲的影响，二是消除某些异常值的影响，增强鲁棒性）

 transfer = StandardScaler()
 # 计算mean, std, 返回均值为0 标准差为1的数据

 x_train = transfer.fit_transform(x_train)
 # 使用x_train的mean, std

 x_test = transfer.transform(x_test)

 # 4、KNN预估器流程

 # 4.1 实例化预估器类

 estimator = KNeighborsClassifier()
 # 4.2 模型选择与调优——网格搜索和交叉验证

 # 准备要调的超参数

 param_dict = {"n_neighbors": [1, 3, 5]}
 estimator = GridSearchCV(estimator, param_grid=param_dict, cv=3) 
 # 4.3 fit数据进行训练

 estimator.fit(x_train, y_train)

 # 5、评估模型效果

 # 方法a:比对预测结果和真实值

 y_predict = estimator.predict(x_test) 
 print("比对预测结果和真实值:\n", y_predict == y_test) 
 # 方法b:直接计算准确率

 score = estimator.score(x_test, y_test) 
 print("直接计算准确率:\n", score)

五、模型调优

1. 交叉验证

交叉验证就是同一个训练集多次不同位置训练取平均值，来判断当前的参数组合是否为优；
如果没有交叉验证，K值取值的好坏或者准确值得不到，没有验证集去验证。
交叉验证目的:为了让被评估的模型更加准确可信

2. 网格搜索

通常情况下，有很多参数是需要手动指定的(如k-近邻算法中的K值)，这种叫超参数。
但是手动过程繁杂，所以需要对模型预设几种超参数组合。
每组超参数都采用交叉验证来进行评估。最后选出最优参数组合建立模型。

3. 交叉验证，网格搜索(模型选择与调优) API

sklearn.model_selection.GridSearchCV(estimator, param_grid=None,cv=None)
- 对估计器的指定参数值进行详尽搜索
- estimator:估计器对象
- param_grid:估计器参数(dict){“n_neighbors”:[1,3,5]}
- cv:指定几折交叉验证
- fit:输入训练数据
- score:准确率
- n_job:指定核心数量
- 结果分析:
  - bestscore__:在交叉验证中验证的最好结果
  - bestestimator:最好的参数模型
  - cvresults:每次交叉验证后的验证集准确率结果和训练集准确率结果

4. 代码实现

参考上述鸢尾花案例

六、KNN算法总结

1. 优点:

简单有效
重新训练的代价低
适合类域交叉样本
- KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
适合大样本自动分类
- 该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
适用于小数据场景，包含几千～几万样本量的数据集

2. 缺点：

惰性学习
- KNN算法是懒散学习方法(lazy learning,基本上不学习)，一些积极学习的算法要快很多
类别评分不是规格化
- 不像一些通过概率评分的分类
输出可解释性不强
- 例如决策树的输出可解释性就较强
对不均衡的样本不擅长
- 当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法(和该样本距离小的邻居权值大)来改进。
计算量较大
- 目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。

K-近邻算法

K值选择、距离度量、分类决策

一、模型

1. 定义

2. 距离度量

二、策略

1. K值如何选择

2. 分类决策规则

三、算法

1. 构造kd树

2. 搜索kd树

四、鸢尾花种类预测

五、模型调优

1. 交叉验证

2. 网格搜索

3. 交叉验证，网格搜索(模型选择与调优) API

4. 代码实现

六、KNN算法总结

1. 优点:

2. 缺点：

CATALOG

FEATURED TAGS

FRIENDS