本文主要是PRML一书2.5节的笔记。

核密度估计与近邻算法是两种简单的非参数密度估计算法。与参数方法相比，非参数方法对真实分布做更少的假设。比如数据是多峰的，那么我们用单峰的正态分布去拟合效果一定不好，但非参数方法却可以取得不错的效果。
非参数方法并不是指模型不含参数，而是说参数并不控制分布的类型，常常控制着模型的复杂程度。

假设样本是从在 $D$ 维欧氏空间的未知分布 $p(\mathbf{x})$ 中取出来的，我们想要估计 $p(\mathbf{x})$ 的值。考虑包含 $\mathbf{x}$ 的一个小区域 $\mathcal{R}$，它对应的概率（probability mass）为$$P=\int_{\mathcal{R}}p(\mathbf{x})\mathrm{d}\mathbf{x}\tag{1}$$假设现在有一个从 $p(\mathbf{x})$ 中取出的含 $N$ 个样本的数据集，由于每个样本落在区域 $\mathcal{R}$ 内的概率为 $P$，落在区域 $\mathcal{R}$ 里的样本总数 $K$ 服从二项分布$$\text{Bin}(K|N,P)=\cfrac{N!}{K!(N-K)!}P^K(1-P)^{1-K}\tag{2}$$我们知道该分布的均值为 $\mathbb{E}[K/N]=P$，方差为 $\text{var}[K/N]=P(1-P)/N$。对于很大的 $N$，方差趋近于0，则分布在均值处有一个高峰，故而近似有$$K\simeq NP\tag{3}$$另一方面，如果区域 $\mathcal{R}$ 足够小，那么概率 $p(\mathbf{x})$ 在这个区域里就大致不变，则有$$P=p(\mathbf{x})V\tag{4}$$其中 $V$ 是区域 $R$ 的体积。结合(3)，(4)式，可以得到下面的密度估计公式$$p(\mathbf{x})=\cfrac{K}{NV}\tag{5}$$然而，上式的正确性却依赖于两个相抵触的假设。一方面假设 $\mathcal{R}$ 足够小使得概率密度在区域内近似不变，另一方面又需要 $\mathcal{R}$ 充足大使得 $K$ 足以能够让分布在均值处形成高峰。

不过，我们可以从两方面来利用(5)式的结果：

固定 $K$ 的值，利用数据确定 $V$ 的值，这引出了K近邻算法。
固定 $V$ 的值，利用数据确定 $K$ 的值，这引出了核密度估计方法。

1. 核密度估计法（Kernel density estimators）

取 $\mathcal{R}$ 为以 $\mathbf{x}$ 为中心的超立方。为了统计落在这个区域中样本的个数 $K$，定义下面这个方程$$k(\mathbf{u})=\begin{cases}1,\quad &|u_i|\le 1/2,\qquad i=1,…,D \\ 0,\quad &\text{otherwise}\end{cases}\tag{6}$$其中，函数 $k(\mathbf{u})$ 是核函数，在这个问题中，也称为Parzen窗口。选取 $\mathbf{u}=(\mathbf{x}-\mathbf{x}_n)/h$，则 $\mathbf{x}_n$ 在边长为 $h$ 的超立方中时函数值为1，否则为0。那么$$K=\sum_{n=1}^Nk(\cfrac{\mathbf{x}-\mathbf{x}_n}{h})\tag{7}$$代入到(5)式中，可以得到$$p(\mathbf{x})=\cfrac{1}{N}\sum_{n=1}^N\cfrac{1}{h^D}k\left(\cfrac{\mathbf{x}-\mathbf{x}_n}{h}\right)\tag{8}$$其中 $V$ 用 $h^D$ 替代。由于 $k(\mathbf{u})$ 的对称性，我们可以将上式重新阐述为以 $N$ 个样本 $\mathbf{x}$ 为中心的 $N$ 个立方的和，而不是一个以 $\mathbf{x}$ 为中心的立方。
然而，(8)式的模型仍然有不连续的问题，出现在立方边界上。可以选取一个较平滑的核函数来解决，通常的选择是高斯核函数，对应的概率密度模型为$$p(\mathbf{x})=\cfrac{1}{N}\sum_{n=1}^{N}\cfrac{1}{(2\pi h^2)^{1/2}}\exp\left\{-\cfrac{||\mathbf{x}-\mathbf{x}_n||^2}{2h^2}\right\}\tag{9}$$其中 $h$ 是标准差。一个例子如下图所示

可见，$h$ 不能过大，也不能过小。过小会产生太多噪声，过大则不能捕捉到分布的特征。

当然，我们也可以用其它核函数 $k(\mathbf{u})$，只要满足以下两点$$k(\mathbf{u})\ge 0$$ $$\int k(\mathbf{u})\mathrm{d}\mathbf{u}=1$$核方法的优点是“训练”阶段不需要计算，只需要存储训练集；同时，这也反映出这种方法的缺点，即计算概率密度值时的开销随数据集大小线性增长。

2. 近邻算法（Nearest-neighbour methods）

核密度估计方法存在的一个问题是 $h$ 对所有核都是固定的。在数据比较集中的区域，较大的 $h$ 值可能造成过度平滑；而在数据比较稀疏的区域，减小 $h$ 值可能会带来更多噪声。最优的选择是 $h$ 随数据空间的位置不同而变化，近邻算法就能实现这一点。
先选取以 $\mathbf{x}$ 为中心的一个很小的球面，然后逐渐增大半径直到球面包含了恰好 $K$ 个数据点为止，此时球面所围城的体积即为所求的 $V$。这种方法称为 $K$ 近邻法。

K-近邻用于分类

K-近邻方法也可以拓展到分类问题，对每一类别用K-近邻法进行密度估计，然后应用贝叶斯理论得到后验概率。
假设总共有 $N$ 个样本，其中每一类的样本有 $N_k$ 个。如果想分类新的样本 $\mathbf{x}$，就以 $\mathbf{x}$ 为中心画一个刚好能包含 $K$ 个数据点的球面，球面围成的体积为 $V$，含有每一类 $C_k$ 的数据点为 $K$ 个。则用K-近邻法求出每一类的概率密度为$$p(\mathbf{x}|\mathcal{C}_k)=\cfrac{K_k}{N_kV}\tag{10}$$类似地，非条件概率密度为$$p(\mathbf{x})=\cfrac{K}{NV}\tag{11}$$类的先验概率为$$p(\mathcal{C}_k)=\cfrac{N_k}{N}\tag{12}$$利用(10)，(11)，(12)式，结合贝叶斯定理，我们可以得到后验概率为$$p(\mathcal{C}_k|\mathbf{x})=\cfrac{p(\mathbf{x}|\mathcal{C}_k)p(\mathcal{C}_k)}{p(\mathbf{x})}=\cfrac{K_k}{K}\tag{13}$$要分类一个新的点，我们从数据集中找出距它最近的 $K$ 个点，然后将它分到 $K$ 个点中数量最多的那一类（平衡随机打破）。当 $K=1$ 时，称为最近邻方法，即将新数据点分类到离它最近的数据点所在的那一类。一个分类的例子如下图

可见，$K$ 也控制着平滑程度。小的 $K$ 值会产生许多小区域，大的 $K$ 值则会产生较少的大区域。
K近邻方法和核方法都需要把整个数据集存储下来，如果数据集太大，计算开销就会随之增大。可以使用一些额外的一次计算方法来抵消一定的计算量，比如使用KD树来存储近邻信息，就不需要在每次计算时穷举搜索整个数据集。尽管这样，非参数方法依然比较局限。

参考资料

Pattern Recognition and Machine Learning (PRML)