【统计学习方法】学习笔记——第三章：K近邻法
统计学习方法学习笔记——K近邻法
-
1. k近邻算法
-
2. k近邻模型
-
- 2.1模型
- 2.2距离度量
- 2.3 k值的选择
- 2.4 分类决策规则
-
3. 估计误差与近似误差
-
- 3.1 估计误差
- 3.2 近似误差
- 3.3 两者区别与联系
-
4. k近邻法的实现：kd树
-
- 4.1 构造kd树
- 4.2 搜索kd树
-
5. 补充
-
5.1
K近邻算法与K-means聚类算法的区别：- 5.2 k-d树的若干改进方案
- 5.2.1 BF树方法
- 5.2.2 球形数据组织技术
- 5.2.3 其他相关技术
-
6. 总结
-
参考资料
-
k-近邻算法（k-nearest neighbor, k-NN algorithm）是一种基础性的分类与回归方法。在本节中我们仅探讨其用于分类问题的应用场景。**算法的核心在于：**其输入为实例的特征向量（亦即特征空间中的点），输出则对应于实例所属类别（可取多类）。该算法基于给定的训练数据集，在学习阶段即完成模型构建过程。当面对新的待测实例时，在训练数据集中找到距离其最近的k个邻居，并依据这些邻居所属类别的多数投票结果进行预测判断。因此可以看出：该算法并不包含显式的训练学习过程（即无需显式地学习参数）。实际上k-近邻算法通过将待测样本与训练集中存储的所有已知样本进行比较来实现经验知识的有效积累与应用——这使得它本质上也是一种基于经验风险最小化的学习策略。其中选择合适的k值、采用适当的距离度量方法以及确定合理的分类决策规则被视为该算法的关键因素之一。
1. k近邻算法
基于训练数据集T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}, 针对新的输入实例x, 依据选定的距离度量, 在训练集T中确定与x最近的k个样本. 这些样本所属类别的 majority 决定了实例x的类别标签y. 具体来说, 算法执行以下步骤: 第一步, 根据距离度量计算x与其他所有样本的距离, 并按从小到大的顺序选择前k个样本构成邻域集合N_k(x); 第二步, 通过分类决策规则（如多数投票法）来确定实例x所属类别y: y = \arg\max_{c_j}\sum_{x_i\in N_k(x)} I(y_i=c_j), j=1,2,...,K, 其中I(\cdot)为指示函数
该方法的一个特殊情形是当k等于1时被称为最近邻居算法。
在输入实例点（特征向量）x的情况下，在训练数据集中的与之最接近的样本类别将被确定为该实例所属类别。
值得注意的是，在k近邻方法中并不存在显式的训练阶段。
2. k近邻模型
基于k近邻的方法主要依据某种距离测度来识别出与目标实例相距最近的前k个实例，并通过预设的分类判定准则对目标实例进行类别归属判定。由此可见，在这种方法下所使用的模型实际上等价于在特征空间中进行区域划分的过程。该模型由三个关键要素构成：首先采用某种距离测度来表征不同样本之间的相似性；其次合理选择参数k以控制判别面 granularity；最后设定相应的分类判定准则来进行最终归属判定。
2.1模型
在特征空间中为每一个训练样本x_i分配了一个决策区域（cell），该区域由与之距离最近的所有样本共同构成，并覆盖整个数据分布范围内的某一特定区域范围。这些决策区域将整个特征空间划分为一个个互不重叠且相互排斥的空间块体，在每一个这样的块体内所包含的数据样本都具有相同的分类标签（class label）。基于此，在每一个决策区域内所属的数据样本都可被归入单一类别范畴，并通过这种划分方式实现了对新输入样本进行分类的目的
2.2距离度量
在特征空间中，两个实例点之间的关系可以通过它们之间的几何位置来衡量。
在k近邻模型中进行分类的任务可以被建模为n维实数向量空间中的问题。
通常来说，在特征空间中进行分类的任务可以被建模为n维实数向量空间中的问题。
其中一种更为通用的距离度量方法被称为Lp范式（Lp distance）或Minkowski范式（Minkowski distance）。
其中最常见的是L2范式（即欧氏范式），也称为欧几里得范式。
另一种常用的曼哈顿范式则是基于L1计算得到。
设特征空间χ为n维实数向量空间R^n，在其中任意两个元素x_i, x_j都属于χ，并且每个向量由n个分数组成：
x_i = (x_i^{(1)}, x_i^{(2)}, ..., x_i{(n)})T，
x_j = (x_j^{(1)}, x_j^{(2)}, ..., x_j{(n)})T。
它们之间的L_p范数距离定义如下：
对于任意p ≥ 1，
L_p(x_i, x_j) = (\sum_{l=1}^N |x_i^{(l)} - x_j{(l)}|p)^{1/p}。
当取p=2时，
我们得到欧氏距离（Euclidean distance），其计算公式为：
L_2(x_i, x_j) = (\sum_{l=1}^N |x_i^{(l)} - x_j{(l)}|2)^{1/2}。
而当p=1时，
称为城市街区距离（Manhattan distance），其计算方式为：
L_1(x_i, x_j) = \sum_{l=1}^N |x_i^{(l)} - x_j^{(l)}|。
此外，在p趋向于无穷大时，
我们得到棋盘距离（Chebyshev distance），其计算方法为：
L_∞ (x_i, x_j) = \max_l |x_i^{(l)} - x_j^{(l)}|。
2.3 k值的选择
选择合适的k值对于提升k近邻算法的效果具有重要意义。具体而言，在实际应用中需要根据数据特性和需求合理确定k值的大小：当k值较小时（即选择较小的数值），算法在训练阶段可能表现得更为高效；然而相应的分类精度可能会有所下降。相反地，在这种情况下容易导致模型过于复杂从而出现过拟合的风险；而当k值较大时（即选择较大的数值），尽管这可能会增加计算复杂度但能够有效降低模型的泛化能力从而提高分类结果的稳定性与可靠性。这一问题将在后续讨论‘近似误差与估计误差’时进行详细阐述。
在实际应用中, k值通常选择一个较小的数值. 常用交叉验证法来确定较佳的k值参数.
2.4 分类决策规则
基于最邻近法的传统决策机制通常是多数投票机制。即取自最近K个样本的数据，在这些数据中具有最高数量标签的那一类，则被作为目标数据所属类别。具体而言，在数学上可以证明，在误分率最低的情况下必然是多数投票机制所作出的结果。值得注意的是，在实际应用中无论是全同意见机制（单一票决模式）还是绝对过半数模式都是永远无法实现精准预测的目标结论。相比之下小部分人主导的观点更是站不住脚
实际上除了权重加权的多数表决之外对于K个最近点我们还可以按照它们的距离远近程度对每个邻居点赋予不同的权重值然后进行加权统计计算最终得到一个折中结果
3. 估计误差与近似误差
3.1 估计误差
估计的误差
就K-近邻法而言，在选择较小的K值时（如例子所示），噪声数据、错误的数据以及不恰当的距离测量标准等因素都可能显著影响预测结果的质量（即导致较大程度的影响）。相反，在选择较大的K值时（如例子所示），这些因素的影响会尽量得到平衡（从而最小化对预测结果质量的影响程度）。
3.2 近似误差
在描述对象上存在差异的情况下，估计误差主要衡量的是预测结果与最优解之间的相似程度；相比之下，近似误差则关注两者之间的关联程度。对于K近邻法而言，在选择较小的K值时（即选择较少数量的邻居），这些邻近样本标签对目标点的影响也随之增强，并且这种影响会使得标签的一致性得到加强。因此，在这种情况下（即当K值较小时），我们可以预期会降低相应的近似误差水平。
3.3 两者区别与联系
总体来说，在分类算法中存在两种基本的误差类型：近似误差与估计误差。近似误差衡量的是目标点对原始样本点的信任程度，在这种情况下若近似误差较小，则目标点对原样本点的信任度较高；换句话说，在这种情况下目标点仅需确认最近的几个数据即可确定自己的标签归属，并不需要依赖其他所有相关的目标点进行确认。相比之下估计误差则反映了模型本身的分类能力即该模型所展现出来的分类特性与其真实情况之间的偏离程度这可能受到噪声干扰错误数据记录或者数据分布不均匀等因素的影响而通过增加验证对象的数量则能有效降低这些偏差对结果的影响就像你向别人征求意见时如果自己对于别人意见的采纳率越高那么别人的意见对于你的决策带来的偏差就会越小；同样地如果别人的意见越符合实际情况那么这种偏差也会相应减小
这就是一种从经验中学习的方法当你在决定是否采纳他人的意见时如果自己对于他人意见的接受程度较高那么这种情况下他人的意见带来的近似偏差就会相对较小；反之如果观察到更多的不同意见却仍然坚持自己的判断那么这些不同的声音可能会引入较大的估计偏差从而影响最终的结果理解得通吗
4. k近邻法的实现：kd树
在实现k近邻法的过程中，核心关注点在于怎样处理快速k近邻搜索的问题 。
该算法最基础的方法采用线性扫描策略，在这种情况下需要计算输入实例与每个训练实例之间的距离。
然而，在实际应用中发现当训练数据规模较大时，这种直接比较的方式会导致较高的时间复杂度。
为了提升搜索效率，在处理大规模数据时通常会采用更高效的组织结构来优化这个过程。
其中一种常用的方法就是kd树（kd tree）策略。
4.1 构造kd树
KD-Tree是一种特殊的用于存储并便于快速检索k维空间实例点的树形数据结构。其主要应用于多维空间中关键数据项的关键字搜索操作。值得注意的是，KD-Tree作为**Binary Space Partitioning Tree（BSP Tree）的一种特殊情况，在其结构特征上与Binary Tree（二叉树）具有相同性质。即其结构特征与Binary Tree（二叉树）**具有相同性质即其结构特征与 Binary Tree 具有相同性质。构建 KD-Tree 的过程等同于通过一系列垂直于坐标轴方向上的超平面不断划分 k 维空间，并最终形成一系列互不相交且充满整个 k 维空间范围内的 k 维超矩形区域集合。其中每个节点都代表一个 k 维的空间超矩形区域。
在索引架构中进行相似性查询主要采用的两种方法：其中一种是基于范围的检索方式；另一种则是基于K近邻的技术。
- 范围查询即为给定一个数据集，并设定一个特定的距离阈值d，在该数据集中检索出所有满足条件dist(x_i, x_q) < d的数据项；
- 对于K近邻查询而言，在给定的数据集中寻找与目标点具有最小距离的前k个记录；特别地，在这种情况下（即k=1），就等价于执行最近邻搜索。
而对于这类问题，解决办法有两类：
- 首先是直线扫描法（即直接扫描法），它是指将查询点依次与数据集中每一个单独的数据点进行距离计算和比较的过程。这种方法等同于穷举搜索，在处理大数据量时明显缺乏针对性和效率。
- 另一种方法是构建一个高效的数据索引系统并配合快速检索算法使用（即快速匹配技术）。由于实际应用中遇到的数据通常呈现明显的簇状分布特征（即簇态聚类形态），因此通过科学设计索引结构能够大幅提高检索速度。
索引树属于第二类算法，在信息组织领域具有重要地位。该方法的核心思想是对搜索空间进行层次化分割以实现高效的查询操作。基于所划分的空间是否存在重叠区域可将此类方法分为两类：一类是在空间划分子区域时无交集的策略（Clipping），其中典型的实例是kd树算法；另一类是在构建空间分割时允许区域间的交集（Overlapping），其中典型的方法是R-tree结构。
基于不同的决策规则, 构建kd树的方式多种多样. 但最终都是\boxed{平衡二叉树}结构. 构造kd树的方法如下:
- 构建初始节点：使根节点对应于k维空间中包含所有实例点的超矩形区域；
- 递归划分过程：通过以下步骤持续对k维空间进行分割生成子节点：
a. 在当前超矩形区域（父节点）选择一个坐标轴及其切分点来确定一个超平面；
b. 将选定的坐标轴作为分割方向，并在该方向上设置切分位置形成垂直于该坐标的超平面；
c. 这一超平面将当前区域沿着选定方向分割为左右两个子区域（子节点）； - 实例分类完成：经过上述划分后，在左、右两子区域内分别完成对实例的分类归属
该过程在子区域内存在实例时即停止（此时对应的节点为叶子节点）。在这一过程中，实例被保存在相应的节点中。
在该方法中, 可以调节的因素有两个: 首先是指标的选择顺序, 其次是划分依据.
- 在第一段中, 我们可以选择"按序列采样"的方式, 即从第一维开始一直到分割结束. 此外, 还可以选择具有最大方差的维度, 或者按照主次排列等其他方法.
- 在第二段中, 可以采用"该维的中间值"作为划分点, 同时也可以选择"中间数值"作为划分依据. 以上方法均可根据具体需求灵活运用.
在本研究中所采用的方法属于最基本的方法。研究采用了按顺序采样的策略来确定维度。具体来说，在构建KD树的过程中，在每一步中选择一个坐标轴，并按照该坐标轴将空间进行划分。在每一步操作中计算训练数据集在选定坐标的均值或中位数值作为分割依据。从而生成的是一个高度均衡的空间划分结构。需要注意的是，在这种情况下搜索效率可能并非最优。
算法2：平衡kd树构建算法
4.2 搜索kd树
假设给定一个目标点，则需要寻找其最近邻居。为此，请先定位包含该目标点的叶子节点；接着逐步回溯至各父节点，在此过程中持续比较与目标点最近的节点，并在无法找到比当前记录更近的情况时停止。这种做法将搜索局限于局部区域附近，并显著提升了效率。
算法3：用kd树的最近邻搜索
输入：已构造的kd树，目标点x;
输出：x的最近邻
确定包含目标数据样本x的所有叶子节点：
从根部出发进行遍历搜索，在k-d树中按照以下步骤逐步缩小搜索范围：
首先根据查询数据样本在各个维度上的坐标值与切分轴的数据样本坐标值之间的关系，
选择相应的子树方向（即当查询数据样本在当前维度上的值小于切分轴的数据时，
进入左支；反之进入右支），直到达到叶子节点为止。
然后将此叶子节点作为初始候选最近邻居。
接着开始反向回溯父层结构：
对于每一个中间层内部保存的数据样本，
如果它比当前候选最近邻居更为接近查询数据样本，
则更新候选最近邻居为该内部保存的数据样本。
在此过程中，
必须先确定候选最近邻居所在的区域是否存在其他可能成为近邻的竞争者，
为此需要先判断另一棵相邻分支的空间是否与以查询数据为中心、具有半径等于两者之间距离的新超球体有交集。
如果存在重叠区域，
则需继续深入相邻分支寻找潜在的竞争者；
若无交集则无需深入探索其他分支。
- 当回退到根节点时，搜索结束。最后的“当前最近点”即为x的最近邻点。
其实掌握这几个关键点：首先是当前最近点的初始判定，其次是追溯比较过程，最后是搜索潜在解。
总体而言，在均匀分布的数据集中进行kd树搜索具有较高的效率。具体来说，在解决训练数据规模远超空间维度的K近邻问题上，kd树方法表现出显著优势。通常适用于空间维度低于等于20的情况。
5. 补充
5.1K近邻算法与K-means聚类算法的区别：
| KNN | K-Means |
|---|---|
| KNN是分类算法 | K-Means是聚类算法 |
| KNN是监督学习 | K-Means非监督学习 |
| 没有明显的前期训练过程 | 有明显的前期训练过程 |
| K的含义指的是判断依据来源个数 | K的含义是集合的分类数目 |
而这两者都用到了NN算法，一般使用kd树来实现。
5.2 kd树的若干改进算法
5.2.1 BBF算法
BBF（Best-Bin-First）查询算法是一种高效的数据检索方法。由David Lowe在1997年提出的一种近似算法旨在解决高维数据检索的问题。该方法通过优先搜索那些潜在包含最近邻点的空间区域来提高效率，并设置了运行时间限制以避免长时间未响应。通过采用BBF机制优化后的kd树结构能够有效地扩展至高维数据集。
对于BBF算法的改进思路而言，在处理过程中需要对位于查询路径上的节点进行排序处理。具体而言，在构建索引树时，默认情况下会按照分割超平面（即bin）与查询点之间的距离进行排列，并且在执行回溯检查时，默认会优先考虑具有最高优先级（Best Bin）的树节点。
5.2.2 球树
在K-d树的基础上对BF算法进行优化是一种常见的技术手段,然而这种改进方式仍然无法完美解决结构本身存在的不足之处.当面对具有明显不均匀分布的数据集时会出现一个根本性矛盾:即要求构建的高度平衡树,同时又要求查询区域呈现较为规则化的形状.无论选择何种形状,无论是近似方形还是矩形,甚至是正方形,它们都存在明显的角部特性,因此都不构成最理想的选择.
其实这个问题的核心原因在于，在计算数据间的相似性时我们采用了圆形作为基准来衡量距离即使用欧氏距离作为度量工具。然而如果我们采用类似于切比雪夫距离这种方框形的方式可能会有效缓解这一问题。进一步分析可知由于无论是模板还是样本其衡量基准保持一致因此在选择合适的度量方法时需要确保两者遵循相同的几何形状规则这样才能避免产生不必要的差异。
改写说明
球树以层层递进的方式构建出由质心C和半径r定义的节点结构。每个节点内的所有数据点都被包裹在以质心C为中心、半径为r的超球体内。该方法通过利用三角不等式有效优化潜在邻居的数量。
例如下面这个就是球树：
如图所示，在数据集中先构造一个超球体S，该超球体是能够容纳所有样本的最小超球体。选取距离中心最远的一个点P_1；接着选择第二个点P_2使其与P_1之间的距离最大；然后将数据集中的所有点根据其到这两个聚类中心的距离进行分类分配；随后分别计算这两个子超球体S_1和S_2的中心位置及其所需最小半径值r_1和r_2。通过递归操作最终构建了一个KD树结构。
通过球树结构实现目标点最近邻的查找方法如下所述：首先从根节点开始遍历整个树结构以定位包含目标点的具体叶子节点，并在此处设置一个初始上限值（即该目标点与其所在叶子中心之间的最小距离）。随后的操作与KD树的操作相似：接着检查其兄弟节点。如果该目标点到其兄弟节点中心的距离大于该兄弟节点半径与当前上限值之和，则无需深入探索该兄弟节点及其子树；反之，则必须继续探索位于这些兄弟子树中的潜在近邻候选者。完成对所有兄弟子树的搜索后，在返回至父级的过程中继续寻找可能存在的更优近邻候选者。当回溯至根节点时，则可获得最终确定的目标最近邻结果。
下面是sklearn的代码示例：
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from sklearn import neighbors, datasets
n_neighbors = 15
# import some data to play with
iris = datasets.load_iris()
# we only take the first two features. We could avoid this ugly
# slicing by using a two-dim dataset
X = iris.data[:, :2]
y = iris.target
h = .02 # step size in the mesh
# Create color maps
cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF'])
cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])
for weights in ['uniform', 'distance']:
# we create an instance of Neighbours Classifier and fit the data.
clf = neighbors.KNeighborsClassifier(n_neighbors, weights=weights)
clf.fit(X, y)
# Plot the decision boundary. For that, we will assign a color to each
# point in the mesh [x_min, x_max]x[y_min, y_max].
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
np.arange(y_min, y_max, h))
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
# Put the result into a color plot
Z = Z.reshape(xx.shape)
plt.figure()
plt.pcolormesh(xx, yy, Z, cmap=cmap_light)
# Plot also the training points
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold,
edgecolor='k', s=20)
plt.xlim(xx.min(), xx.max())
plt.ylim(yy.min(), yy.max())
plt.title("3-Class classification (k = %i, weights = '%s')"
% (n_neighbors, weights))
plt.show()
代码解读
5.2.3 其他方法
半径最近邻算法通过确定特定半径内的最邻近k个数据点来实现预测;质心最近邻方法则通过计算各维度特征值的均值来确定质心位置。
具体而言,对于某一个类别而言,将各类别在各个维度上的均值计算出来即可得到其对应的质心位置。
对于训练集中所有可能存在的类别,系统会分别计算并存储其对应的质心位置。
在进行分类预测时,只需要将待测样本与各类别的质心位置进行距离比较,距离最小的那一类即为待测样本所属的类别。
需要注意的是,这一算法特别适用于解决文本分类问题。
6. 总结
KNN的主要优点
KNN的主要缺陷 列举如下：
- 计算开销较大，在处理高维度数据时尤为明显
- 当类别分布失衡时，对罕见类别判别能力较弱
- 基于 KD 树、球树等的数据构建过程占用内存极大
- 采用惰性学习策略，在预测阶段效率较低的同时牺牲了一定的分类精度（尤其与其如逻辑回归等 eager 学习算法相比）
- 相较于决策树等基于规则的分类器而言，在可解释性方面存在一定欠缺
参考资料
《统计学习方法》一书由李航著述而成。
该文章详细探讨了"统计学习方法"中的核心概念及其应用。
其中一项重要研究即为"基于K近邻的分类与识别技术"。
进一步深入分析则可发现"基于Ball树结构的优化算法研究（第三部分）"等创新性成果。