KNN邻近算法

一、KNN简介

KNN的基本思想简单直观：在处理某些问题时，我们认为两个实例在特征空间中的距离反映了它们之间的相似程度，距离越近则越相似。那么，对于一个输入实例 x 的类别或目标值，可根据训练集中与其距离最近的一些实例(最相似的实例)的类别或目标值进行推断。

假设数据集 D 为训练集，KNN对输入实例 x 进行预测的算法可描述为：
（1）根据某种距离度量方法（通常为欧式距离），找到 D 中与 x 距离最近的 k 个实例。
（2）根据最近的 k 个实例的类别或目标值，对 x 的类别或目标值进行预测：

• 对于分类问题使用“投票法”，即取 k 个实例中出现最多的类标记作为 x 的预测结果。
• 对于回归问题使用“平均法”，即取 k 个实例的目标值的平均值作为 x 的预测结果。

下面通过一个简单的例子说明

当 k 的值设为1时，样本周围有1个红矩形和0个蓝三角形，所以该样例判定为 class2
当 k 的值设为5时，样本周围有2个红矩形和3个蓝三角形，所以该样例判定为 class1

二、距离的计算

可以使用欧氏距离或者曼哈顿距离

（一）首先计算当前点和数据集中的点之间的距离
（二）按照距离从小到大进行排序
（三）选取与当前点距离最小的 k 个点
（四）统计这 k 个点中类别出现频率
（五）返回频率最高的类别作为当前点的类别

优点：
1、思想简单，理论成熟，既可以用来做分类也可以用来做回归；
2、可用于非线性分类；
3、训练时间复杂度为O(n)；
4、准确度高，对数据没有假设，对outlier不敏感；

缺点：
1、计算量大；
2、样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
3、需要大量的内存；

其中计算的地方可以通过kd树来减少计算量

书\用户	用户1	用户2	用户3
书1	8	10	0
书2	0	2	10
书3	1	4	9
书4	5	3	0

给用户3推荐一本书


totaltance = distance1 + distance2 = 29.98

用户一的权重w1 = distance1/totaltance = 53.07%
用户二的权重w2 = distance2/totaltance = 46.93%

其中书2和书3， 用户3评论过，所以不计

所以预测用户3
对书1的评价v1：(用户一对书1的评价) * w1 + (用户二对书1的评价) * w2 = 8 * w1 + 10 * w2

对书4的评价v2：(用户一对书4的评价) * w1 + (用户二对书4的评价) * w2 = 5 * w1 + 3 * w2

若 v1 > v2，则推荐书1
若 v1 < v2，则推荐书2

三、KNN算法的应用

（一）分类
（二）回归
（三）One-class 识别
One-class 分类/识别又称为：异常点/离群点检测，这个非常有用。假设我们的 app 需要识别 5 种不同的用户手势，一般的分类器只会告诉你某个动作属于 1-5 哪个类型，但是如果是用户进行一些非手势的普通操作，我们需要识别出来“不属于任何类型”，然后需要在手势模块中不进行任何处理直接忽略掉。

这个事情用传统分类器非常困难，因为负样本是无穷多，多到没法列举所有额外的手势，我们只能收集正样本。这和 0-9 数字手写识别是一样的，比如用户写了个 A 字母，我们需要判断某个输入图像不是 0-9 中任何一个，但是我们除了 0-9 的样本外没法枚举所有例外的可能。