《统计学习方法（第二版）》李航 读书笔记 （6）

k-近邻算法，习题3

k-nearest neighbor k-NN是一种基本分类与回归方法。输入为实例的特征向量，对应特征空间中的点；输出为实例的类别，可以取多类。K近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测。K近邻法没有显式的学习过程

算法3.1 k近邻法

1. 根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这k个点的x的邻域记作Nk(x);
2. 在Nk(x)中根据分类决策规则（如多数表决）决定x的类别y

特征空间中，对每个训练实例点xi，距离该点比其他点更近的所有点组成一个区域，叫作单元（cell）。最近邻法将实例xi的类yi作为其单元中所有点的类标记（class label）

距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映。

• Lp距离：
• 欧式距离（Euclidean distance）：
• 曼哈顿距离（p=1）
• L∞距离（p=无穷）

除此之外还有Minkowski距离

还有马氏距离（Mahalanobis Distance）基于样本分布的一种距离测量；考虑到各种特性之间的联系（如身高和体重），可以消除样本间的相关性，广泛用于分类和聚类分析

                                 

identity matrix 恒等矩阵  diagonal matrix 对角矩阵

 

如果选择较小的K值

• • “学 习”的近似误差（approximation error)会减小，但 “学习”的估计误差（estimation error) 会增大，
  • 噪声敏感
  • K值的减小就意味着整体模型变得复杂，容易发生过 拟合.

如果选择较大的K值，

• • 减少学习的估计误差，但缺点是学习的近似误差会增大.
  • K值的增大 就意味着整体的模型变得简单.

多数表决规则等价于经验风险最小化

Kd树                                                                                                                                           

一种对于k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。是二叉树，表示对k维空间的一个划分（partition），构造kd树相当于不断用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。

构造方法：构造根节点，使根节点对应于k维空间中包含所有实例点的超矩形区域；在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，再将超矩形区域切分成左右两个子区域（子结点）；实例被分到子区域，直到子区域内没有实例时终止。

平衡kd树，以各实例点各维度上的中位数作为结点来切分。

 

算法3.3 使用kd树的最近邻搜索

由根结点出发，递归向下访问kd树，目标当前维度的坐标在切分点的左右，然后移动到下一个结点；

直到子结点为叶结点，以此叶结点为“当前最近点”；

递归向上回退，如果该结点保存的实例点，比当前最近点距离目标点更近，则定义它为“当前最近点”；

检查父结点的另一子结点对应的区域是否有更近的点。（方法是检查超球体是否与另一子结点相交）

不断回退，到根结点时，搜索结束

 

平均计算复杂度是O（logN），适用于训练实例数远大于空间维数时的k近邻搜索。空间维数接近训练实例数时，效率会迅速下降，接近线性扫描。