分类（2）：k-最近邻、贝叶斯分类器

一、k-最近邻

1、算法

积极学习方法（eager learner）：通过训练样本建立模型。
消极学习方法（lazy learner）：实例的学习，k-最近邻就属于这种。

k-最近邻算法：

令k是最近邻数目，D是训练样例集合
for z in 样例集合:
  计算 z 和每个样例 (x,y) 的距离 d
  选择离 z 前 k 个近距离的点，为集合 Dt
  z的标记 y 为 Dt 中类较多的

k-最近邻采用多数表决的方法，该算法对 k 敏感：

$$y’=argmax_{v}\sum_{(x_{i},y_{i})\in D_{t}} I(v=y_{i})$$
所以，需要降低 k 的影响，一种途径就是对距离的不同加权，如下，因为距离远的影响要弱一些，以距离平方的倒数为权值。
$$y’=argmax_{v}\sum_{(x_{i},y_{i})\in D_{t}}w_{i}\times I(v=y_{i}),w_{i}=\frac{1}{d(x’,x_{i})^{2}}$$

2、最近邻分类器特征：

（1）实例的学习，不需要建模，但分类测试的开销很大。
（2）当k比较小的时候，对噪声非常敏感。
（3）可以生成任意决策边界。

二、贝叶斯分类器

1、贝叶斯公式

$$P(Y_{j}|X)=\frac{P(X|Y_{j})P(Y_{j})}{P(X)}=\frac{P(X|Y_{j})P(Y_{j})}{\sum_{i=1}^{n}P(X|Y_{i})P(Y_{i})}$$

2、朴素贝叶斯

（1）条件独立性：

给定 Z，X 条件独立于 Y:

$$P(X|Y,Z)=P(X|Z)$$
则有：
$$P(X,Y|Z)=\frac{P(Z,Y,X)}{P(Z)}=\frac{P(Z,Y,X)}{P(Y,Z)}\frac{P(Y,Z)}{P(Z)}=P(X|Y,Z)P(Y|Z)=P(X|Z)P(Y|Z)$$

（2）朴素贝叶斯分类器：

$$P(Y|X)=\frac{P(X|Y)P(Y)}{P(X)}=\frac{P(X_{1},…,X_{d})P(Y)}{P(X)}=\frac{P(Y)\prod_{i=1}^{d}P(X_{i}|Y)}{P(X)}$$

（3）连续属性的条件概率：

<1>把每个连续属性离散化，用相应的区间去替代原来的属性，但若某一个区间的样本数目过少，不容易做出可靠的估计。

<2>可以假设连续变量服从正态分布，Xi的概率等于：

$$P(X_{i}=x_{i}|Y=y_{j})=\frac{1}{\sqrt{2\pi}\sigma_{ij}}e^{-\frac{(x_{i}-\mu_{ij})^{2}}{2\sigma_{ij}}}$$
其中 $\mu$ 用样本均值估计， $\sigma$ 用样本方差估计。

（4）朴素贝叶斯举例：

拖欠贷款为 Y 变量。

测试记录X=（有房=否，婚姻状况=已婚，年收入=120K），求后验概率P（No|X）、P（Yes|X）。
总的 Y 可以知道，P（Yes）=0.3，P（No）=0.7。则：

P（X | No）=P（有房=否 | No）x P（婚姻状况=已婚 | No）x P（年收入=120K | No）=0.0024
P（X | Yes）= P（有房=否 | Yes）x P（婚姻状况=已婚 | Yes）x P（年收入=120K | Yes）=0

因为P（No|X）>P（Yes|X），所以该测试分类为No，不拖欠贷款。
上例中，P（婚姻状况=已婚 | Yes）=0，可能会出现极端现象，为了防止出现0，朴素贝叶斯没法正确分类，可以使用 m 估计（m-estimate）：

$$P(x_{i}|y_{j})=\frac{n_{c}+mp}{n+m}$$
$n$ 为 $y_{i}$ 的实例总数，$n_{c}$ 为 $y_{i}$ 中 $x_{i}$ 的实例数目，p 是用户指定，m 为等价样本大小的参数。上面的计算：P（婚姻状况=已婚 | Yes）=(0+3 x 1/3)/(3+3)=1/6，而不是0。

（4）朴素贝叶斯特征：

对于噪声点，朴素贝叶斯是健壮的。也可以处理属性值遗漏问题。
无关属性，朴素贝叶斯是健壮的。对于相关属性，可能会降低分类性能。

3、贝叶斯置信网络（Bayesian belief networks，BBN）

（1）模型表示：

两个主要成分：

一个有向无环图（DAG），表示变量之间的关系；
一个概率表，把各个结点和它的直接父节点关联起来。

性质1：条件独立
贝叶斯网络中的一个结点，如果它的父母结点已知，则它条件独立于它的所有非后代结点。

如图（b），给定C，A 条件独立于 B 和 D。
除了网络拓扑结构要求的条件独立外，每个结点还关联一个概率表。

（1）如果结点 X 没有父母结点，则表中只包含先验概率P(X);
（2）如果结点 X 只有一个父母结点 Y，则表中包含先验概率P(X | Y);
（3）如果结点 X 有多个父母结点{Y1，Y2…，Yk}，则表中只包含先验概率P(X|Y1，Y2…，Yk);

下图是一个贝叶斯置信网络。

（2）建立模型：

贝叶斯网络拓扑结构的生成算法：

设T=（X1，X2，...Xd）表示变量的全序
for j=1 to d do
  令 XTj 表示 T 中第 j 个次序最高的变量
  令A（XTj）={XT1，XT2，...XTj-1} 表示排在 XTj 前面的变量的集合
  从A（XTj）中去掉对 Xj 没有影响的变量（使用先验知识）
  在 XTj 和 A（XTj） 中的剩余变量之间画弧

考虑到图5_03，经过循环后，得到的如下概率：

P（D | E）化简为 P（D）
P（HD | E,D）不能化简
P（Hb | E,D,HD）化简为 P（Hb | D）
P（CP | E,D,HD,Hb）化简为 P（CP | HD,Hb）
P（BP | E,D,HD,Hb,CP）化简为 P（BP | HD）

上面的算法，保证了不会生成环。
不同的变量排序会产生不同的拓扑结构，理论上需要 d！种排序才能找到最优的，开销很大。代替方法是把变量分成原因变量和结果变量，从原因到结果画弧。

（3）使用BNN进行推理：

根据上面的贝叶斯置信网络图，有下面情况：

（4）BNN的特点：

构造网络比较费时，但网络结构一旦确定下来，添加新变量就变得容易。
很适合处理不完整数据，对有属性遗漏的可以通过概率或求积分来加以处理。
数据和先验知识结合起来，该方法对于模型的过拟合问题是非常鲁棒的。