K-近邻算法（K-Nearest Neighbors，简称KNN算法）是一种用于分类和回归的监督学习算法。其工作原理：给定测试样本，基于某种距离度量找出练集中 与其最靠近的个训练样本，然后基于这个"邻居"的信息来进行预测在分类任务中可使用"投票法" ，即选择这个样本中出现最多的类别标记作为预测结果；在回归任务中时使用"平均法" ，即将这个样本的实值输出标记平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。
基本原理
为了更直观的理解KNN算法的逻辑，下面用KNN算法通过1~9个样本来预测样本10的电影的电影类型：
序号 | 电影名称 | 搞笑镜头 | 拥抱镜头 | 打斗镜头 | 电影类型 | 距离 | k=5时 |
1 | 功夫熊猫 | 39 | 0 | 31 | 喜剧片 | 21.47 | ✓ |
2 | 叶问3 | 3 | 2 | 65 | 动作片 | 52.01 | ㅤ |
3 | 伦敦陷落 | 2 | 3 | 55 | 动作片 | 43.42 | ㅤ |
4 | 代理情人 | 9 | 38 | 2 | 爱情片 | 40.57 | ㅤ |
5 | 新步步惊心 | 8 | 34 | 17 | 爱情片 | 34.44 | ✓ |
6 | 谍影重重 | 5 | 2 | 57 | 动作片 | 43.87 | ㅤ |
7 | 功夫熊猫 | 39 | 0 | 31 | 喜剧片 | 21.47 | ✓ |
8 | 美人鱼 | 21 | 17 | 5 | 喜剧片 | 18.55 | ✓ |
9 | 宝贝当家 | 45 | 2 | 9 | 喜剧片 | 23.43 | ✓ |
10 | 唐人街探案 | 23 | 3 | 17 | ？ | —— | ？ |
为了预测样本10的电影类型，需要将其和其他9个样本的”距离“（相似度）分别计算出来，让后将结果按照从小到大排列，选取k个”距离“较小的邻近样本，然后样本10的电影类型即为这k个邻近样本中票数最多的电影类型。那么，问题来了，如何计算两个样本之间的”距离“呢？
两点之间的直线距离（欧式距离）公式为：
那么同样可以根据这个公式类推，通过两个样本的对应特征值来计算样本间距离。那么唐人街探案和伦敦陷落的“距离”为。
同上上述方法获得样本10和其他样本的距离之后，设定参数k=5，则从样本集中选取5个距离较小的样本，其中三个是喜剧片，两个为爱情片，那么样本10预测的电影类型为喜剧片。
K值分析
- K值过小：用较小的邻域中的训练实例进行预测，容易受到异常点影响，导致可能发生过拟合。
- K值过大：用较大邻域中的训练实例进行预测，容易受到样本均衡的影响，K值的增大意味着整体的模型变得简单，导致可能发生欠拟合。
- 如何对K超参数进行调优？（这将在后面的内容讲解）
- 交叉验证
- 网格搜索
KNN应用
- 算法思想：若一个样本在特征空间中的 k 个最相似的样本大多数属于某一个类别，则该样本也属于这个类别
- 相似性：欧式距离
- 解决问题：分类问题、回归问题
- 分类：
- 计算未知样本到每一个训练样本的距离
- 将训练样本根据距离大小升序排列
- 取出距离最近的 K 个训练样本
- 进行多数表决，统计 K 个样本中哪个类别的样本个数最多
- 将未知的样本归属到出现次数最多的类别
- 回归：
- 计算未知样本到每一个训练样本的距离
- 将训练样本根据距离大小升序排列
- 取出距离最近的 K 个训练样本
- 把这个 K 个样本的目标值计算其平均值
- 作为将未知的样本预测的值
KNN算法API使用
KNN算法用于分类和回归两个问题，两者导入的类有所不同。
分类问题
- sklearn.neighbors.KNeighborsClassifier(n_neighbors=5)
- n_neighbors：int,可选（默认= 5），n_neighbors查询默认使用的邻居数K
回归问题
- sklearn.neighbors.KNeighborsRegressor(n_neighbors=5)
距离度量（了解）
在KNeighborsRegressor回归算法函数中，有两个参数：p=2, metric='minkowski', 用于表示回归算法函数具体使用什么距离度量方法作为KNN算法的相似性指标，默认为欧式距离（Euclidean Distance）
欧式距离
直观的距离度量方法，两个点在空间中的直线距离。
二维平面上点与间的欧式距离：
n维平面上点与间的欧式距离：
曼哈顿距离
曼哈顿距离(Manhattan Distance)也称为“城市街区距离”(City Block distance)，曼哈顿城市特点：横平竖直
二维平面上点与间的曼哈顿距离：
n维平面上点与间的曼哈顿距离：
切比雪夫距离 Chebyshev Distance
国际象棋中，国王可以直行、横行、斜行，所以国王走一步可以移动到相邻8个方格中的任意一个。国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？这个距离就叫切比雪夫距离。
二维平面上点与间的切比雪夫距离：
n维平面上点与间的切比雪夫距离：
例子：
ABCD四点 X=[ [1,1], [2,2], [3,3], [4,4] ] ，计算AB AC AD BC BD曼哈顿距离，经计算得: AB =max(|2−1|, |2−1|) = 1， d = 1 2 3 1 2 1
闵可夫斯基距离 Minkowski Distance
闵氏距离不是一种新的距离的度量方式，而是对多个距离度量公式的概括性的表述。
n维平面上点与间的闵可夫斯基距离定义为
其中p是一个变参数：
- 当 p=1 时，就是曼哈顿距离；
- 当 p=2 时，就是欧氏距离；
- 当 p→∞ 时，就是切比雪夫距离
根据p的不同，闵氏距离可表示某一类种的距离。
特征预处理（归一化和标准化）
归一化和标准化是特征工程中的一个重要环节。主要应用于：
- 涉及多个特征一起进行计算, 比如计算欧式距离
- 特征的取值范围, 差异较大 (量纲不统一)
请看下面例子：
编
号 | 身高
cm | 体重
kg | 视力
0.2-2.0 | 健康
状况 |
1 | 170 | 67 | 1.5 | 1 |
2 | 171 | 80 | 0.8 | 2 |
3 | 175 | 70 | 1.5 | 1 |
4 | 176 | 68 | 1.2 | 1 |
5 | 180 | 80 | 1.8 | 1 |
6 | 181 | 90 | 0.6 | 2 |
7 | 175 | 75 | 0.8 | ？ |
现有6个样本数据，需要通过6个样本的特征向量(身高, 体重, 视力)来对样本7的健康状况进行评估（1表示健康，2表示不健康）。那么按照上节内容通过KNN算法来预测样本7的目标值的时候，视力项的特征值相对于身高和体重显然不在一个数量级，计算的结果中视力的特征值对结果的影响微乎其微。
为了避免多个特征值间的数量级不在同一个水平，需要使用到归一化或者标准化。
归一化
通过对原始数据进行变换把数据映射到【mi,mx】区间(默认为[0,1])之间
代码实现：
- sklearn.preprocessing.MinMaxScaler (feature_range=(0,1)… )
- feature_range: 缩放区间,默认为(0, 1)
- fit_transform(X) 将特征进行归一化缩放
- 如果出现异常点，影响了最大值和最小值，那么结果显然会发生改变
- 应用场景：最大值与最小值非常容易受异常点影响， 鲁棒性较差，只适合传统精确小数据场景
标准化
通过对原始数据进行标准化，转换为均值为0标准差为1的标准正态分布的数据.
其中, mean为特征值的平均值； 为特征值的标准差
代码实现：
- sklearn.preprocessing.StandardScaler()
- fit_transform(X) 将特征进行归一化缩放
- 如果出现异常点，由于具有一定数据量，少量的异常点对于平均值的影响并不大
- 应用场景：适合现代嘈杂大数据场景。(以后就是用你了）
案例：利用KNN算法对鸢尾花分类
超参数选择及验证
交叉验证
上面鸢尾花的案例中，我们只使用了一份测试集对模型进行测试，这样的操作方式数据集并没有得到充分利用，训练出的模型也并不是充分可信的。
交叉验证是一种数据集的分割方法，将训练集划分为 n 份，分别拿其中一份做验证集（测试集）、其他n-1份做训练集。例如当数据集划分为cv = 4份时：
- 第一次：把第一份数据做验证集，其他数据做训练
- 第二次：把第二份数据做验证集，其他数据做训练
- ... 以此类推，总共训练4次，评估4次。
网格搜索
同样在鸢尾花案例中，可调整的参数包括：k（领居的个数）和p（距离测量的方式），对于给定不同的参数组合，训练得出来的模型准确率可能有所不同，能否将的所有可能组合都验证一下，得出最佳的组合，以提高模型的准确率？
网格搜索就是把所有要尝试的参数组合, 都遍历一圈, 使用数据来训练对应模型, 通过测试集表现来找到最佳的参数组合。
交叉验证和网格搜索通常强有力的组合在一起使用
- 交叉验证解决模型的数据输入问题(数据集划分)得到更可靠的模型
- 网格搜索解决超参数的组合
- 两个组合再一起形成一个模型参数调优的解决方案
交叉验证网格搜索API使用
- sklearn.model_selection.GridSearchCV(estimator, para_grid=None, cv=None)
- estimator：学习器对象
- param_grid：学习器对象中的参数，字典形式传惨；例如：{'n_neighbors':[4,5,7,9]}
- cv：int，指定几折交叉验证
鸢尾花案例 — 交叉验证网格搜索
利用KNN算法实现手写数字识别
- 已知数据
- MNIST手写数字识别
- 1999年发布，成为分类算法基准测试的基础
- MNIST仍然是研究人员和学习者的可靠资源
- 需求
- 从数万个手写图像的数据集中正确识别数字
- 数据介绍
- 数据文件 train.csv 和 test.csv 包含从 0 到 9 的手绘数字的灰度图像。
- 每个图像高 28 像素，宽28 像素，共784个像素。
- 每个像素取值范围[0,255]，取值越大意味着该像素颜色越深
- 训练数据集（train.csv）共785列。第一列为 "标签"，为该图片对应的手写数字。其余784列为该图像的像素值
- 训练集中的特征名称均有pixel前缀，后面的数字（[0,783])代表了像素的序号
