非参数估计—Parzen窗法与近邻法

非参数估计基本原理

在极大似然估计与贝叶斯估计 中我们提到了参数估计与非参数估计的区别

• 参数估计先假设概率密度函数的形式，再根据样本估计该概率密度函数的参数
• 非参数估计不对分布函数做具体的假设，而是直接根据样本估计各区域的概率密度

非参数估计的思想与直方图类似，即将样本空间划分为若干相同大小的区间，统计每个区间包含的的样本数并用柱状图画出，得到对真实概率密度的近似

设$R$是样本空间中的一个小区域，$p(x)$为分布的概率密度函数，则样本$x$落在$R$中的概率为

$$P=\int_{R}p(x) \text{d}x$$

假设$n$个样本独立同分布地根据$p(x)$抽取，显然落入区域$R$的样本数$k$服从二项分布，即有$E(k)=nP$

因此$P=\frac{k}{n}$是对$P$的一个很好的估计

当$R$足够小时，我们可以认为这个区间内$p(x)$没有变化，即有

$$P = \int_{R}p(x) \text{d}x = p(x)V$$

其中$V$是区域$R$的体积，综上可得$p(x)$在区域$R$的估计

$$p(x)\approx \frac{k/n}{V}$$

当$n$固定时，区域$R$的选定和体积$V$对估计效果影响很大
若$V$过大，则显然$\int_{R}p(x) \textbf{d}x = p(x)V$会过渡平滑，使估计不准确
若$V$过小，很可能其中不包含任何样本，此时$p(x)=0$，或只含1，2个样本，此时$p(x)$的估计值会无穷大

在样本数量无限的理想情况下，我们可以通过如下方法来试图找到一个合适的$R$

为了估计点$x$处的概率密度，可以构造一系列包含$x$的区域$R_1,R_2,…$，其中$R_n$包含$k_n$个样本，则有

$$p_n(x)=\frac{k_n/n}{V_n}$$

当满足如下条件时$p_n(x)$收敛于$p(x)$

• $\lim_{n\to \infty} V_n = 0$
• $\lim_{n\to \infty}k_n \to \infty$
• $\lim_{n\to \infty}\frac{k_n}{n}=0$

其中最后一个条件限制$k$的增长速度小于$n$

然而实际中样本数量当然不可能无限，但我们仍可以构造这样的区域序列来尽可能准的估计$p(x)$
具体来说就是接下里的Parzen窗法和K近邻法

Parzen窗法

以下均假设样本空间为$d$维

Parzen窗法的关键是设计窗函数$\varphi(u)$，我们先看一个简单的窗函数

$$\varphi(u)= \begin{cases} 1, & |u_j|\leq \frac{1}{2},\quad j=1,2,...,d \\ 0, & 其他 \end{cases}$$

这个窗函数定义了一个中心在原点，边长为1的超立方体，超立方体内部函数值为1，否则为0

利用$\varphi(u)$可以定义一个中心位于样本$x$，边长为$h_n$的超立方体

$$\varphi(\frac{x_i-x}{h_n})= \begin{cases} 1, & |{x_{i}}_j-x_j|\leq h_n,\quad j=1,2,...,d \\ 0, & 其他 \end{cases}$$

即若样本$x_i$落入以$x$为中心的超立方体中，则窗函数值为1，因此以$x$为中心的超立方体中包含样本数为

$$k_n=\sum_{i=1}^n \varphi(\frac{x_i-x}{h_n})$$

令$V_n=h_n^d$，则$p(x)$估计值为

$$p(x)=\frac{1}{n}\sum_{i=1}^m \frac{1}{V_n}\varphi(\frac{x_i-x}{h_n})$$

实际上窗函数可以是各种形状，满足 $\varphi(u)\geq 0$ 和 $\int \varphi(u) \text{d}u=0$ 的函数都可以作为窗函数

最常用的窗函数是高斯窗函数

$$\varphi(x)=\frac{1}{(\sqrt{2\pi}h_n)^d}\exp\left(-\frac{\|x-x_i\|^2}{2h_n^2}\right)$$

显然Parzen窗法的估计结果主要受窗函数的宽度$h_n$影响

若$h_n$过大，则得到的密度曲线抖动过大，若$h_n$过小，则曲线将过于平滑

一般情况下，可以令$h_n=\frac{h_1}{\sqrt n}$，其中$h_1$为选定的初值

K近邻法

上述Parzen窗法实质上是定义了一个关于$n$的体积函数，通过逐渐收缩体积达到收敛

而K近邻法的思想是定义$k_n$为关于$n$的函数，每次对一个确定的$k_n$，逐渐扩大体积$V_n$直到以$x$为中心的区域包含$k_n$个样本为止

一般情况下，可以令$k_n=k_1\sqrt n$，其中$k_1$为选定的初值

非参数估计与贝叶斯分类

贝叶斯分类中需要根据贝叶斯公式计算后验概率 $P(c|x)=\frac{P(x|c)P(c)}{P(x)}$

对于其中的类条件概率$P(x|c)$，我们可以用Parzen窗法估计，即

$$P(x|c)=\frac{1}{n_c}\sum_{x_c}\frac{1}{V_n}\varphi(\frac{x-x_c}{h_n})$$

其中$n_c$为类别$c$的样本数，$x_c$为属于类别$c$的样本

我们也可以使用K近邻法直接估计后验概率$P(c|x)$

选取距离样本$x$最近的$k$个样本，其中有$k_c$个样本属于类别$c$，则$P(c|x)=\frac{k_c}{k}$