[模式分类]非参数方法

本文对应《模式分类》的第 4 章。

核心思想

给定样本集 $D=\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_n\}$，假定这些样本独立采样自 $p(\mathbf{x})$，我们希望得到 $p(\mathbf{x})$ 的一个估计。

考虑样本空间中的一个小区域 $R$。一方面，若 $p(\mathbf{x})$ 是连续的，且 $R$ 足够小使得 $p(\mathbf{x})$ 在 $R$ 中几乎不变，那么向量 $\mathbf{x}$ 落入 $R$ 的概率为： $$P={\int }_{R}p({\mathbf{x}}^{\prime })\mathrm{d}{\mathbf{x}}^{\prime }\approx p(\mathbf{x})V$$ 其中 $V$ 是区域 $R$ 的体积。另一方面，当数据量足够大时，如果有 $k$ 个样本落入 $R$，那么： $$P\approx k/n$$ 因此，联立上述两式，得： $$p(\mathbf{x})\approx \frac{k/n}{V}$$ 然而，为了让这个“约等于”尽可能准确，$V$ 需要趋近于零，$n$ 需要趋近于无穷。但是在现实中我们能获得的样本量肯定是有限的。因此，如果 $V$ 设置得太小，那么落入 $R$ 的样本太少，甚至没有，导致对 $p(\mathbf{x})$ 的估计不连续；如果 $V$ 设置得太大，那么对 $p(\mathbf{x})$ 的估计将太平滑。

为了解决这个问题，我们考虑如下过程：为了估计 $\mathbf{x}$ 处的概率密度，构造一系列包含点 $\mathbf{x}$ 的区域 $R_1,R_2,\dots$，其中 $R_n$ 将使用 $n$ 个样本做密度估计。记 $V_n$ 为 $R_n$ 的体积，$k_n$ 为落入 $R_n$ 的样本数，那么可以得到序列： $$\begin{array}{}\text{(1)}& p_n(\mathbf{x})=\frac{k_n/n}{V_n},n=1,2,\dots \end{array}$$ 当以下三个条件满足时，$p_n(\mathbf{x})$ 能收敛到 $p(\mathbf{x})$：

1. $\underset{n\to \mathrm{\infty }}{lim}{V}_n=0$
2. $\underset{n\to \mathrm{\infty }}{lim}{k}_n=\mathrm{\infty }$
3. $\underset{n\to \mathrm{\infty }}{lim}{k}_n/n=0$

为了构造这样的序列，我们有两种方法——Parzen 窗和 k 近邻。前者取 $V_n$ 为某个关于 $n$ 的函数（例如 $V_n=1/\sqrt{n}$）、$k_n$ 随之变化；而后者取 $k_n$ 为某个关于 $n$ 的函数（例如 $k_n=\sqrt{n}$）、$V_n$ 随之变化。两种方法在 $n\to \mathrm{\infty }$ 时都能够收敛，但在实际情形中由于样本量有限，并不能保证它们的效果。

Parzen 窗

基本原理

为了方便，首先假设区域 $$ 是以 $$（待求密度处）为中心、边长为 $$ 的 $$ 维超立方体，则其体积为： $$ 为了解析地表达 $$，定义窗函数如下： $$ 即一个以原点为中心、边长为 $$ 的超立方体。那么： $$ 代入 $$ 式得： $$ 可以验证这的确是一个概率分布。

非负性显然，只需验证归一性： $$ 因此 $$ 式的确是一个概率分布。

核函数角度

从核函数的角度理解，定义： $$ 满足： $$ 那么 $$ 式可以写作： $$ 因此 Parzen 窗方法也被称作核密度估计 (KDE)。$$ 式意味着 Parzen 窗估计也可以视作用核函数对样本在取值空间中进行插值。

窗函数/核函数的选择

上面为了推导方便，我们假定了窗函数是单位超立方体，但这只是一种选择而已，我们还可以使用其他形式：

正态窗： $$ 球窗： $$ 其中 $$ 是超球体的半径，$$ 是超球体的体积。

窗宽的影响

显然，如果 $$（或 $$）选取太大，那么估计不够精确，可以理解为欠拟合；如果太小，那么不够稳定，可以理解为过拟合。下图展示了不同情况下用正态窗做估计的例子，窗宽设置为 $$，其中 $$ 是可以调整的参数。

k 近邻

基本原理

Parzen 窗方法是人为设置 $$，再计算 $$；k 近邻方法则相反——人为设置 $$，再调整 $$ 使得区域内正好落入 $$ 个样本。这样窗宽将与训练样本有关，避免了如何选取合适窗宽的问题。

值得注意的是，尽管 k 近邻估计出的 $$ 是连续的，但其往往不可导，会有非常多的尖峰，且这些不可导点与原数据点几乎都是不同的，如下图所示：

另外，与 Parzen 窗不同的是，k 近邻得到的概率密度估计并不是一个合法的概率密度函数。例如，在一维情形下，记第 $$ 个正好落入区域内的样本为 $$，那么 $$，于是代入 $$ 式得： $$ 由于 $$ 的积分是发散的，所以 $$ 的积分是无穷大，如下图所示：

虽然积分是发散的，但 k 近邻密度估计的一个优点是 $$ 永远不会为零，这在高维情况下非常有用。

用于估计后验概率

我们可以用 k 近邻方法估计每一个类别的概率分布，然后使用最大后验准则进行分类。具体而言，设 $$ 周围包含 $$ 个样本的区域中，有 $$ 个样本属于 $$ 类，那么： $$ 其中 $$ 表示属于 $$ 类的样本数量。于是对后验概率的估计为： $$ 即区域中属于 $$ 类的样本数量占区域中所有样本数量的比例。

根据最大后验准则，有了后验概率，就可以得到一个分类器： $$

可以看见这就是 k 近邻分类器。

最近邻分类器

上面提到我们用 k 近邻方法估计后验概率，再根据最大后验准则分类，就得到了 k 近邻分类器。但事实上，我们只依赖最近邻就能达到足够好的性能。

最近邻分类器的基本思想非常简单，即对于一个新样本，将其与已知样本逐一比较，找出距离最近的已知样本，以该样本的类别作为新样本的类别。如此，特征空间可以被分成一个个小单元（称作 Voronoi 网格），如图所示：

最近邻分类器有多好呢？可以证明，在无限训练样本的情形下，其误差率最多不会超过贝叶斯误差率的两倍。具体而言，设 $$ 为 $$ 个样本下最近邻分类器的误差率，当 $$ 趋近无穷时该误差收敛到 $$，记 $$ 为贝叶斯分类器的误差率，$$ 为类别数量，那么有： $$

证明比较复杂，暂时略去，以后有时间再看。

k 近邻分类器及其改进

将最近邻分类器进行推广，选择前若干个离测试样本最近的样本，取其中出现最多的类别作为新样本的类别，这就是 k 近邻分类器。对 k 近邻分类器的分析比最近邻更加复杂，这里略去。结论是，当样本量无限时，随着 $$ 的增加，k 近邻分类器的误差率逐渐逼近下界贝叶斯误差率；当 $$ 趋近无穷大时二者相等。

一些改进方法：

• 剪辑近邻法。考虑到分类时最容易分类错误的地方就是交界区域处，因此可以设法将交界区域的样本去掉。因此我们需要识别出那些位于交界区域的样本。一种做法是：将已知样本集划分为训练集和测试集，采用近邻法利用训练集中的样本对测试样本进行分类，从中去掉被错分类的样本，剩余样本构成剪辑样本集，用于对新来的样本进行分类。

  多重剪辑：

  1. 划分。将样本集随机划分为 $$ 个子集 $$；
  2. 分类。轮流地以其中一个作为训练样本集，对其邻近编号的样本进行测试；
  3. 剪辑。从各个子集中去掉在步骤 2 中被分错的样本；
  4. 混合。将剩下的样本合在一起，形成新的样本集；
  5. 迭代。转步骤 1，如果没有新的样本被剪辑掉，则停止迭代。

• 压缩近邻法。考虑近邻法的分类原理，那些远离分类边界的样本对于最后的分类决策没有贡献，因此可以去掉。

  将样本集为两个活动的子集：储存集 $$ 和备选集 $$.

  首先，在算法开始时，$$ 中只有一个样本，其余样本均在 $$ 中；

  然后，考查 $$ 中的每一个样本，如果采用 $$ 中的样本能够对其正确分类，则该样本仍然保留在 $$ 中， 否则移动到 $$ 中，从而扩大代表集合。依次重复进行上述操作，直到没有样本需要搬移为止。

  最后，用 $$ 中的样本作为代表样本，对新来的样本进行分类。

距离度量

合法的距离度量应满足：

1. 非负性：$$
2. 自反性：$$
3. 对称性：$$
4. 三角不等式：$$

常见距离度量：

• Minkowski 距离： $$

• Manhattan 距离： $$

• Euclidean 距离： $$

• Chebyshev 距离： $$

• Mahalanobis 距离： $$ 其中 $$ 为半正定矩阵。