1. 什么是 KNN
1.1 KNN 的通俗解释
何谓 K 近邻算法, 即 K-Nearest Neighbor algorithm, 简称 KNN 算法, 单从名字来猜想, 可以简单粗暴的认为是: K 个最近的邻居, 当 K=1 时, 算法便成了最近邻算法, 即寻找最近的那个邻居.
用官方的话来说, 所谓 K 近邻算法, 即是给定一个训练数据集, 对新的输入实例, 在训练数据集中找到与该实例最邻近的 K 个实例(也就是上面所说的 K 个邻居), 这 K 个实例的多数属于某个类, 就把该输入实例分类到这个类中.
如上图所示, 有两类不同的样本数据, 分别用蓝色的小正方形和红色的小三角形表示, 而图正中间的那个绿色的圆所标示的数据则是待分类的数据. 也就是说, 现在, 我们不知道中间那个绿色的数据是从属于哪一类(蓝色小正方形 or 红色小三角形),KNN 就是解决这个问题的.
如果 K=3, 绿色圆点的最近的 3 个邻居是 2 个红色小三角形和 1 个蓝色小正方形, 少数从属于多数, 基于统计的方法, 判定绿色的这个待分类点属于红色的三角形一类.
如果 K=5, 绿色圆点的最近的 5 个邻居是 2 个红色三角形和 3 个蓝色的正方形, 还是少数从属于多数, 基于统计的方法, 判定绿色的这个待分类点属于蓝色的正方形一类.
于此我们看到, 当无法判定当前待分类点是从属于已知分类中的哪一类时, 我们可以依据统计学的理论看它所处的位置特征, 衡量它周围邻居的权重, 而把它归为 (或分配) 到权重更大的那一类. 这就是 K 近邻算法的核心思想.
1.2 近邻的距离度量
我们看到, K 近邻算法的核心在于找到实例点的邻居, 这个时候, 问题就接踵而至了, 如何找到邻居, 邻居的判定标准是什么, 用什么来度量. 这一系列问题便是下面要讲的距离度量表示法.
有哪些距离度量的表示法(普及知识点, 可以跳过):
欧氏距离, 最常见的两点之间或多点之间的距离表示法, 又称之为欧几里得度量, 它定义于欧几里得空间中, 如点 x = (x1,...,xn) 和 y = (y1,...,yn) 之间的距离为:
\[d(x,y)=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+...+(x_n-y_n)^2}=\sqrt{\sum_{i=1}^{n}(x_i-y_i)^2}\]
二维平面上两点 a(x1,y1)与 b(x2,y2)间的欧氏距离:
\[d_{12}=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\]
三维空间两点 a(x1,y1,z1)与 b(x2,y2,z2)间的欧氏距离:
\[d_{12}=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}\]
两个 n 维向量 a(x11,x12,...,x1n)与 b(x21,x22,...,x2n)间的欧氏距离:
\[d_{12}=\sqrt{\sum_{k=1}^{n}(x_{1k}-x_{2k})^2}\]
也可以用表示成向量运算的形式:
\[d_{12}=\sqrt{(a-b)(a-b)^T}\]
曼哈顿距离, 我们可以定义曼哈顿距离的正式意义为 L1 - 距离或城市区块距离, 也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和. 例如在平面上, 坐标 (x1, y1) 的点 P1 与坐标 (x2, y2) 的点 P2 的曼哈顿距离为:\(|x_1-x_2|+|y_1-y_2|\), 要注意的是, 曼哈顿距离依赖座标系统的转度, 而非系统在座标轴上的平移或映射.
通俗来讲, 想象你在曼哈顿要从一个十字路口开车到另外一个十字路口, 驾驶距离是两点间的直线距离吗? 显然不是, 除非你能穿越大楼. 而实际驾驶距离就是这个 "曼哈顿距离", 此即曼哈顿距离名称的来源, 同时, 曼哈顿距离也称为城市街区距离(City Block distance).
二维平面两点 a(x1,y1)与 b(x2,y2)间的曼哈顿距离
\[d_{12}=|x_1-x_2|+|y_1-y_2|\]
两个 n 维向量 a(x11,x12,...,x1n)与 b(x21,x22,...,x2n)间的曼哈顿距离
\[d_{12}=\sum_{k=1}^{n}|x_{1k}-x_{2k}|\]
切比雪夫距离, 若二个向量或二个点 p ,and q, 其座标分别为 Pi 及 qi, 则两者之间的切比雪夫距离定义如下:
\[D_{Chebyshev}(p,q)=max_i(|p_i-q_i|)\]
这也等于以下 Lp 度量的极值:\(\lim_{x \to \infty}(\sum_{i=1}^{n}|p_i-q_i|^k)^{1/k}\), 因此切比雪夫距离也称为 L∞度量.
以数学的观点来看, 切比雪夫距离是由一致范数 (uniform norm)(或称为上确界范数) 所衍生的度量, 也是超凸度量 (injective metric space) 的一种.
在平面几何中, 若二点 p 及 q 的直角坐标系坐标为 (x1,y1) 及(x2,y2), 则切比雪夫距离为:
\[D_{Chess}=max(|x_2-x_1|,|y_2-y_1|)\]
玩过国际象棋的朋友或许知道, 国王走一步能够移动到相邻的 8 个方格中的任意一个. 那么国王从格子 (x1,y1) 走到格子 (x2,y2) 最少需要多少步?. 你会发现最少步数总是 max( | x2-x1 | , | y2-y1 | ) 步 . 有一种类似的一种距离度量方法叫切比雪夫距离.
二维平面两点 a(x1,y1)与 b(x2,y2)间的切比雪夫距离 :
\[d_{12}=max(|x_2-x_1|,|y_2-y_1|)\]
两个 n 维向量 a(x11,x12,...,x1n)与 b(x21,x22,...,x2n)间的切比雪夫距离:
\[d_{12}=max_i(|x_{1i}-x_{2i}|)\]
这个公式的另一种等价形式是
\[d_{12}=lim_{k\to\infin}(\sum_{i=1}^{n}|x_{1i}-x_{2i}|^k)^{1/k}\]
闵可夫斯基距离(Minkowski Distance), 闵氏距离不是一种距离, 而是一组距离的定义.
两个 n 维变量 a(x11,x12,...,x1n)与 b(x21,x22,...,x2n)间的闵可夫斯基距离定义为:
\[d_{12}=\sqrt[p]{\sum_{k=1}^{n}|x_{1k}-x_{2k}|^p}\]
其中 p 是一个变参数.
当 p=1 时, 就是曼哈顿距离
当 p=2 时, 就是欧氏距离
当 p→∞时, 就是切比雪夫距离
根据变参数的不同, 闵氏距离可以表示一类的距离.
标准化欧氏距离, 标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案. 标准欧氏距离的思路: 既然数据各维分量的分布不一样, 那先将各个分量都 "标准化" 到均值, 方差相等. 至于均值和方差标准化到多少, 先复习点统计学知识.
假设样本集 X 的数学期望或均值 (mean) 为 m, 标准差 (standard deviation, 方差开根) 为 s, 那么 X 的 "标准化变量"X * 表示为:(X-m)/s, 而且标准化变量的数学期望为 0, 方差为 1.
即, 样本集的标准化过程 (standardization) 用公式描述就是:
\[X^*=\frac{X-m}{s}\]
标准化后的值 = ( 标准化前的值 - 分量的均值 ) / 分量的标准差
经过简单的推导就可以得到两个 n 维向量 a(x11,x12,...,x1n)与 b(x21,x22,...,x2n)间的标准化欧氏距离的公式:
\[d_{12}=\sqrt{\sum_{k=1}^{n}(\frac{x_{1k}-x_{2k}}{s_k})^2}\]
马氏距离
有 M 个样本向量 X1~Xm, 协方差矩阵记为 S, 均值记为向量μ, 则其中样本向量 X 到 u 的马氏距离表示为:
\[D(X)=\sqrt{(X-u)^TS^{-1}(X_i-X_j)}\]
若协方差矩阵是单位矩阵(各个样本向量之间独立同分布), 则公式就成了, 也就是欧氏距离了:
\[D(X_i,X_j)=\sqrt{(X_i-X_j)^T(X_i-X_j)}\]
若协方差矩阵是对角矩阵, 公式变成了标准化欧氏距离.
马氏距离的优缺点: 量纲无关, 排除变量之间的相关性的干扰.
巴氏距离
在统计中, 巴氏距离距离测量两个离散或连续概率分布的相似性. 它与衡量两个统计样品或种群之间的重叠量的巴氏距离系数密切相关. 巴氏距离距离和巴氏距离系数以 20 世纪 30 年代曾在印度统计研究所工作的一个统计学家 A. Bhattacharya 命名. 同时, Bhattacharyya 系数可以被用来确定两个样本被认为相对接近的, 它是用来测量中的类分类的可分离性.
对于离散概率分布 p 和 q 在同一域 X, 它被定义为:
\[D_B(p,q)=-ln(BC(p,q))\]
其中:
\[BC(p,q)=\sum_{x\in_{}X}\sqrt{p(x)q(x)}\]
是 Bhattacharyya 系数.
汉明距离
两个等长字符串 s1 与 s2 之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数. 例如字符串 "1111" 与 "1001" 之间的汉明距离为 2. 应用: 信息编码(为了增强容错性, 应使得编码间的最小汉明距离尽可能大).
夹角余弦
几何中夹角余弦可用来衡量两个向量方向的差异, 机器学习中借用这一概念来衡量样本向量之间的差异.
在二维空间中向量 A(x1,y1)与向量 B(x2,y2)的夹角余弦公式:
\[cos\theta=\frac{x_1x_2+y_1y_2}{\sqrt{x_1^2+y_1^2}\sqrt{x_2^2+y_2^2}}\]
两个 n 维样本点 a(x11,x12,...,x1n)和 b(x21,x22,...,x2n)的夹角余弦:
\[cos\theta=\frac{a*b}{|a||b|}\]
夹角余弦取值范围为[-1,1]. 夹角余弦越大表示两个向量的夹角越小, 夹角余弦越小表示两向量的夹角越大. 当两个向量的方向重合时夹角余弦取最大值 1, 当两个向量的方向完全相反夹角余弦取最小值 - 1.
杰卡德相似系数
两个集合 A 和 B 的交集元素在 A,B 的并集中所占的比例, 称为两个集合的杰卡德相似系数, 用符号 J(A,B)表示. 杰卡德相似系数是衡量两个集合的相似度一种指标.
\[J(A,B)=\frac{|A\cap_{}B|}{|A\cup_{}B|}\]
与杰卡德相似系数相反的概念是杰卡德距离:
\[J_{\delta}(A,B)=1-J(A,B)=\frac{|A\cup_{}B|-|A\cap_{}B|}{|A\cup_{}B|}\]
皮尔逊系数
在统计学中, 皮尔逊积矩相关系数用于度量两个变量 X 和 Y 之间的相关(线性相关), 其值介于 - 1 与 1 之间. 通常情况下通过以下取值范围判断变量的相关强度:
0.8-1.0 极强相关
0.6-0.8 强相关
0.4-0.6 中等程度相关
0.2-0.4 弱相关
0.0-0.2 极弱相关或无相关
简单说来, 各种 "距离" 的应用场景简单概括为,
空间: 欧氏距离,
路径: 曼哈顿距离, 国际象棋国王: 切比雪夫距离,
以上三种的统一形式: 闵可夫斯基距离,
加权: 标准化欧氏距离,
排除量纲和依存: 马氏距离,
向量差距: 夹角余弦,
编码差别: 汉明距离,
集合近似度: 杰卡德类似系数与距离,
相关: 相关系数与相关距离.
1.3 K 值选择
如果选择较小的 K 值, 就相当于用较小的领域中的训练实例进行预测,"学习" 近似误差会减小, 只有与输入实例较近或相似的训练实例才会对预测结果起作用, 与此同时带来的问题是 "学习" 的估计误差会增大, 换句话说, K 值的减小就意味着整体模型变得复杂, 容易发生过拟合;
如果选择较大的 K 值, 就相当于用较大领域中的训练实例进行预测, 其优点是可以减少学习的估计误差, 但缺点是学习的近似误差会增大. 这时候, 与输入实例较远 (不相似的) 训练实例也会对预测器作用, 使预测发生错误, 且 K 值的增大就意味着整体的模型变得简单.
K=N, 则完全不足取, 因为此时无论输入实例是什么, 都只是简单的预测它属于在训练实例中最多的累, 模型过于简单, 忽略了训练实例中大量有用信息.
在实际应用中, K 值一般取一个比较小的数值, 例如采用交叉验证法 (简单来说, 就是一部分样本做训练集, 一部分做测试集) 来选择最优的 K 值.
1.4 KNN 最近邻分类算法的过程
计算测试样本和训练样本中每个样本点的距离(常见的距离度量有欧式距离, 马氏距离等);
对上面所有的距离值进行排序;
选前 k 个最小距离的样本;
根据这 k 个样本的标签进行投票, 得到最后的分类类别;
2. KDD 的实现: KD 树
Kd - 树是 K-dimension tree 的缩写, 是对数据点在 k 维空间 (如二维(x,y), 三维(x,y,z),k 维(x1,y,z..)) 中划分的一种数据结构, 主要应用于多维空间关键数据的搜索(如: 范围搜索和最近邻搜索). 本质上说, Kd - 树就是一种平衡二叉树.
首先必须搞清楚的是, k-d 树是一种空间划分树, 说白了, 就是把整个空间划分为特定的几个部分, 然后在特定空间的部分内进行相关搜索操作. 想像一个三维 (多维有点为难你的想象力了) 空间, kd 树按照一定的划分规则把这个三维空间划分了多个空间, 如下图所示:
2.1 构建 KD 树
kd 树构建的伪代码如下图所示:
再举一个简单直观的实例来介绍 k-d 树构建算法. 假设有 6 个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}, 数据点位于二维空间内, 如下图所示. 为了能有效的找到最近邻, k-d 树采用分而治之的思想, 即将整个空间划分为几个小部分, 首先, 粗黑线将空间一分为二, 然后在两个子空间中, 细黑直线又将整个空间划分为四部分, 最后虚黑直线将这四部分进一步划分.
6 个二维数据点 {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)} 构建 kd 树的具体步骤为:
确定: split 域 = x. 具体是: 6 个数据点在 x,y 维度上的数据方差分别为 39,28.63, 所以在 x 轴上方差更大, 故 split 域值为 x;
确定: Node-data = (7,2). 具体是: 根据 x 维上的值将数据排序, 6 个数据的中值 (所谓中值, 即中间大小的值) 为 7, 所以 Node-data 域位数据点 (7,2). 这样, 该节点的分割超平面就是通过(7,2) 并垂直于: split=x 轴的直线 x=7;
确定: 左子空间和右子空间. 具体是: 分割超平面 x=7 将整个空间分为两部分: x<=7 的部分为左子空间, 包含 3 个节点 ={(2,3),(5,4),(4,7)}; 另一部分为右子空间, 包含 2 个节点 ={(9,6),(8,1)};
如上算法所述, kd 树的构建是一个递归过程, 我们对左子空间和右子空间内的数据重复根节点的过程就可以得到一级子节点 (5,4) 和(9,6), 同时将空间和数据集进一步细分, 如此往复直到空间中只包含一个数据点.
与此同时, 经过对上面所示的空间划分之后, 我们可以看出, 点 (7,2) 可以为根结点, 从根结点出发的两条红粗斜线指向的 (5,4) 和(9,6)则为根结点的左右子结点, 而 (2,3),(4,7) 则为 (5,4) 的左右孩子 (通过两条细红斜线相连), 最后,(8,1) 为(9,6)的左孩子(通过细红斜线相连). 如此, 便形成了下面这样一棵 k-d 树:
对于 n 个实例的 k 维数据来说, 建立 kd-tree 的时间复杂度为 O(knlogn).
k-d 树算法可以分为两大部分, 除了上部分有关 k-d 树本身这种数据结构建立的算法, 另一部分是在建立的 k-d 树上各种诸如插入, 删除, 查找 (最邻近查找) 等操作涉及的算法. 下面, 咱们依次来看 kd 树的插入, 删除, 查找操作.
2.2 KD 树的插入
元素插入到一个 K-D 树的方法和二叉检索树类似. 本质上, 在偶数层比较 x 坐标值, 而在奇数层比较 y 坐标值. 当我们到达了树的底部,(也就是当一个空指针出现), 我们也就找到了结点将要插入的位置. 生成的 K-D 树的形状依赖于结点插入时的顺序. 给定 N 个点, 其中一个结点插入和检索的平均代价是 O(log2N).
插入的过程如下:
应该清楚, 这里描述的插入过程中, 每个结点将其所在的平面分割成两部分. 因比, Chicago 将平面上所有结点分成两部分, 一部分所有的结点 x 坐标值小于 35, 另一部分结点的 x 坐标值大于或等于 35. 同样 Mobile 将所有 x 坐标值大于 35 的结点以分成两部分, 一部分结点的 Y 坐标值是小于 10, 另一部分结点的 Y 坐标值大于或等于 10. 后面的 Toronto,Buffalo 也按照一分为二的规则继续划分.
2.3 KD 树的删除
KD 树的删除可以用递归程序来实现. 我们假设希望从 K-D 树中删除结点 (a,b). 如果(a,b) 的两个子树都为空, 则用空树来代替 (a,b). 否则, 在(a,b) 的子树中寻找一个合适的结点来代替它, 譬如 (c,d), 则递归地从 K-D 树中删除(c,d). 一旦(c,d) 已经被删除, 则用 (c,d) 代替 (a,b). 假设(a,b) 是一个 X 识别器, 那么, 它得替代节点要么是 (a,b) 左子树中的 X 坐标最大值的结点, 要么是 (a,b) 右子树中 x 坐标最小值的结点.
来源: https://www.cnblogs.com/mantch/p/11287075.html