论文

电信保温杯笔记——《统计学习方法（第二版）——李航》

原论文：《Nearest neighbor pattern classification》

介绍

本文是对原书的精读，会有大量原书的截图，同时对书上不详尽的地方进行细致解读与改写。

1967年1月发表的文章，提出了k近邻法，一个分类模型。给定训练样本集，并且样本集中每个数据都存在标签，输入没有标签的新数据后，提取样本集中特征前k个最相似数据（最近邻）的分类标签，k个中出现次数最多的分类，作为新数据的分类，无需显示训练。

特点

模型结构

红色问号是未知标签的输入样本，蓝色点为已知标签的训练集样本。

模型三要素

1. 样本间距离的度量
2. k值的选择
3. 分类决策规则：这k个最近的样本以何种方式决策出输出分类

距离度量

要选出距离输入样本最近的k个训练样本，就需要一种距离度量的准则，距离反映了这2个点的相似程度。

实例

k值的选择

分类决策规则

这个区域一共k个样本，${\sum }_{i=1}^{k}I(y_i\ne c_j)$ 代表误分类次数。

k近邻算法

上式的意思是，寻找一个类别 $c_j$，使得多数样本都是这个分类，就是多数表决规则。

k近邻算法的实现：kd树

构造kd树

假设数据集有16个样本，每个样本拥有k维的特征，令k=3。
j为树的深度，根节点的层深度为0，那么树的深度应该为5，l作为第j层划分的特征维度，%为取模运算符，下面计算层深度与选择的特征维度：
$$\begin{gathered} l=j\%k+1 \\ j=0,l=0\%3+1=1,\text{选取}{x}^{(1)}; \\ j=1,l=1\%3+1=2,\text{选取}{x}^{(2)}; \\ j=2,l=2\%3+1=3,\text{选取}{x}^{(3)}; \\ j=3,l=3\%3+1=1,\text{选取}{x}^{(1)}; \\ j=4,l=4\%3+1=2,\text{选取}{x}^{(2)}. \end{gathered}$$

实例

这个例子的讲解可以参考学生视频-KD树

搜索kd树

第一次搜索时，结果是D，而真正最近的点是E。

疑问

具体怎么搜索还是不清楚，平均搜索复杂度为什么是$O(\log N)$。

相关视频

学生视频-KD树

相关的笔记

hktxt /Learn-Statistical-Learning-Method

相关代码

Dod-o /Statistical-Learning-Method_Code，用了最原始的方法，遍历所有样本点计算距离，没有使用kd树。

pytorch

tensorflow

keras

pytorch API:

tensorflow API