分类规则挖掘（三）

四、贝叶斯分类方法

  贝叶斯 (Bayes) 分类方法是以贝叶斯定理为基础的一系列分类算法的总称。贝叶斯定理就是以研究者Thomas Bayes的姓氏命名的，他是一位英国牧师，也是18世纪概率论和决策论的早期研究者之一。

1. 朴素贝叶斯 (Naive Bayes, NB) 分类器
2. 树扩展的朴素贝叶斯 (Tree-Augmented Naive Bayes,TANB) 分类器
3. 贝氏增强网络朴素贝叶斯 (Bayesian network-Augmented Naive Bayes, BAN) 分类器
4. 贝叶斯多网 (Bayesian Multi-Net，BMN) 分类器
5. 一般贝叶斯网络 (General Bayesian Network) 分类器

（一）贝叶斯定理

  设 $Z$ 是类标号未知的样本点，$H$ 表示 “样本$Z$属于类别$C$” 的假设，则分类问题就是计算概率 $p(H|Z)$ 值的问题。

1、先验概率 (prior probability)

  指人们可以根据历史数据统计或历史经验分析得到的概率，其值一般通过对历史数据的分析和统计得到，或由专家根据专业知识人为的指定。用 $p(H)$ 表示假设 $H$ 的先验概率，用 $p(Z)$ 表示没有类别标号的样本点 $Z$ 的先验概率。

2、后验概率 (posterior probability)

  指一个随机变量在另一个随机变量取值已知的情况下取某一个特定值的概率，因此， 也称为条件概率：

• $p(H=h|Z=z)$ 是指在已知变量 $Z$ 取值 $z$ 的情况下，变量 $H$ 取值 $h$ 的概率，记作 $p(H|Z)$，称为在已知 $Z$ 取某个值的条件下，$H$ 成立的后验概率。
• $p(Z=z|H=h)$ 是已知变量 $H$ 取值 $h$ 的情况下，变量 $Z$ 取值 $z$ 的概率，记作 $P(Z|H)$，称为假设 $H$ 成立的条件下，样本 $Z$ 取某个值的后验概率。

例9-4 假设某证券营业部存有100个顾客的样本集 $S$ (表9-16)，条件属性为性别和年龄段，类别属性为 “是否买了基金”。

设随机变量 $H$ 表示顾客购买了基金，即 “是否买了基金=‘是’” 这个假设，用 $Z$ 表示一个新顾客：性别=“男”且年龄段=“30~39”，但类别标号未知，不知道它是否会买股票。

（1）$p(H)$ 表示顾客买了基金的先验概率，则可用样本集 $S$ 中类别属性 “是否买了基金=‘是’” 的顾客数 $\lambda$ 再除以顾客总数 $|S|$ 作为其估计值，即 $p(H)=\lambda ÷|S|$。为了后续例子使用，假设 $p(H)=0.60$。

（2）$Z$ 是一个没有类别标号的新样本，因此 $p(Z)$ 其实是无法计算的，但可以用 $S$ 中 “性别='男’且年龄段=‘30~39’” 的顾客数 $\tau$ 与 $|S|$ 的比值作为其估计值，即 $p(Z)=\tau ÷|S|$。为方便假设 $p(Z)=0.30$。

（3）$p(Z|H)$ 表示在已经购买了基金的顾客中，其性别=‘男’且年龄段=‘30~39’的条件概率。类似地统计 $S$ 中买了基金的顾客数 $\alpha$，再统计这些买了基金的顾客中性别=‘男’且年龄段=‘30~39’的顾客数 $\beta$，则 $p(Z|H)=\beta ÷\alpha$，这里假设 $p(Z|H)=0.20$。

（4）$p(H|Z)$ 表示已知顾客性别=‘男’和年龄段=‘30~39’条件下，该顾客可能购买基金的概率，即预测新顾客将来可能购买基金的概率。贝叶斯定理就是在已知先验概率 $p(H)$，$p(Z)$ 和后验概率 $p(Z|H)$ 的情况下，计算后验概率 $p(H|Z)$ 的方法。

定理9-1（贝叶斯定理），假设 $Z$ 和 $H$ 是两个随机变量，则 $$p(Z|X)=\frac{p(X|H)p(H)}{p(Z)}$$

（二）朴素贝叶斯分类器

贝叶斯分类器根据训练样本集 $S$ 估算样本 $Z$ 属于某个类的概率。

1、训练集的要求

（1）训练集 S = { X 1 , X 2 , ⋯   , X n } S=\{X_1 ,X_2, \cdots,X_n\} S={X1​,X2​,⋯,Xn​} 由表9-1给出，其中 X i = { x i 1 , x i 2 , ⋯   , x i d } X_i=\{x_{i1},x_{i2},\cdots,x_{id}\} Xi​={xi1​,xi2​,⋯,xid​} 为 $d$ 维向量，$A_1,A_2,\cdots ,A_d$ 为样本集的 $d$ 个条件属性。
（2）训练集 $S$ 的类别属性 C = { C 1 , C 2 , ⋯   , C k } C=\{C_1, C_2, \cdots, C_k\} C={C1​,C2​,⋯,Ck​}，其中 $C_j$ 为类别属性的属性值或类别标号，它也表示训练集 $S$ 中属于该类别的样本集合。

2、贝叶斯分类器

对没有类别标号的数据样本 $Z$，称公式 (9-11) 和 (9-12) 为朴素贝叶斯分类器，且它们将类别标号 $C_i$ 赋予 $Z$，其中 $C_i$ 满足 p ( C i ∣ Z ) = m a x { p ( C 1 ∣ Z ) , p ( C 2 ∣ Z ) , ⋯   , p ( C k ∣ Z ) } (9-11) p(C_i|Z) =max\{p(C_1|Z), p(C_2|Z), \cdots, p(C_k|Z)\}\tag{9-11} p(Ci​∣Z)=max{p(C1​∣Z),p(C2​∣Z),⋯,p(Ck​∣Z)}(9-11) 且称 $p(C_i|Z)$ 对应的类 $C_i$ 为最大后验假定，而 $p(C_j|Z)$ 是已知 $Z$ 的条件下，$Z$ 属于类 $C_j$ 的条件概率。$$p(C_j|Z)=\frac{p(Z|C_j)p(C_j)}{p(Z)}\text{\hspace{1em}(9-12)}$$ 因此，贝叶斯分类器是最小错误率意义上的分类方法。

3、进一步说明

（1）从公式 (9-12) 可知，$p(Z)$ 对于所有的类 $C_j(j=1,2,\cdots ,k)$ 均为同一个值，因此，$C_i$ 满足公式 (9-11) 的条件可以变成 $C_i$ 满足公式 (9-13)。 p ( Z ∣ C i ) p ( C i ) = m a x { p ( Z ∣ C 1 ) p ( C 1 ) , p ( Z ∣ C 2 ) P ( C 2 ) , ⋯   , p ( Z ∣ C k ) p ( C k ) } (9-13) p(Z|C_i)p(C_i)=max\{p(Z|C_1)p(C_1), p(Z|C_2)P(C_2), \cdots, p(Z|C_k)p(C_k)\}\tag{9-13} p(Z∣Ci​)p(Ci​)=max{p(Z∣C1​)p(C1​),p(Z∣C2​)P(C2​),⋯,p(Z∣Ck​)p(Ck​)}(9-13)

（2）若类 $C_j(j=1,2,\cdots ,k)$ 的先验概率未知，则假设都是等概率的，即 $p(C_1)=p(C_2)=\cdots =p(C_k)=1/k$，则 (9-13) 转换为对 $p(Z|C_j)$ 的最大化。

（3）如果类 $C_j(j=1,2,\cdots ,k)$ 的先验概率未知，又不是等概率的，那么类 $C_j$ 的先验概率可以通过训练集 $S$ 来估算，即 $$p(C_j)=\frac{|C_j|}{|S|}\text{\hspace{1em}(9-14)}$$ 其中是 $|C_j|$ 类 $C_j$ 中的训练样本数，而 $|S|$ 是训练样本总数。

（4）若样本集具有许多属性，则计算 $p(Z|C_j)$ 的开销可能非常大。为降低计算 $p(Z|C_j)$ 的开销，可以假设，对于任意给定类标号，条件属性之间是相互独立的，即在属性间不存在任何依赖联系的情况下，$$p(Z|C_j)=p(z_1,z_2,\cdots ,z_d|C_j)=\prod _{r=1}^{d}p(z_r|C_j)\text{\hspace{1em}(9-15)}$$ 其中 $z_r$ 为 $Z$ 在属性 $A_r$ 上的取值，概率 $p(z_r|C_j)(r=1,2,\cdots ,d)$ 可以由训练集 $S$ 按以下方式进行估值。

① 如果 $A_r$ 是离散属性，令 $S_{jr}$ 是 $S$ 中在属性 $A_r$ 上取值为 $z_r$ 且属于类 $C_j$ 的训练样本集，则 $$p(z_r|C_j)=\frac{|S_{jr}|}{|C_j|}\text{\hspace{1em}(9-16)}$$ ② 如果 $A_r$ 是连续值属性，则通常假定该属性服从高斯分布，即 $$p(z_r|C_j)=g(z_r,{\mu }_{C_j},{\sigma }_{C_j})=\frac{1}{\sqrt{2\pi {\sigma }_{C_j}}}{e}^{\frac{(z_r-{\mu }_{C_j}{)}^2}{2{\sigma }_{C_j}^2}}\text{\hspace{1em}(9-17)}$$

从以上分析可知，要利用贝叶斯分类器对一个没有类别标号的样本 $Z$ 进行分类，对每个类 $C_j$ 计算 $p(Z|C_j)$，将样本 $Z$ 指派为类 $C_i\iff p(Z|C_i)p(C_i)\ge p(Z|C_j)p(C_j)$，其中 $1\le j\le k$ 且 $j\ne i$，即 $Z$ 被指派到 $p(Z|C_i)p(C_i)$ 值最大的类 $C_i$。

（三）朴素贝叶斯分类方法的改进

1、条件概率的修正

  在公式 (9-14) 和 (9-15) 的后验概率计算过程中，当有一个属性的条件概率等于0，将导致整个类的后验概率等于0。

  为避免出现条件属性后验概率等于0这类问题，一般采用拉普拉斯 (Laplace) 估计对属性的条件概率进行修正，因此拉普拉斯估计又称为拉普拉斯校准或拉普拉斯估计法，它是用法国数学家Pierre Laplace的姓氏命名的。

  拉普拉斯估计法的思想比较简单，即在训练集中认为地增加一些训练样本来实现。

  设属性 $A$ 取 $v$ 个不同值 { a 1 , a 2 , ⋯   , a v } \{a_1,a_2,\cdots,a_v\} {a1​,a2​,⋯,av​}，则属性 $A$ 划分 $C_j$ 所得子集为 { S 1 , S 2 , … ⋯   , S v } \{S_1,S_2,…\cdots,S_v\} {S1​,S2​,…⋯,Sv​}，设 $C_j$ 中在属性 $A$ 上取值为 $a_i$ 的样本为0个，即 $p(a_i|C_j)=0$。为此，在 $S_i$ 中增加 $r>0$ 个样本，即它们在属性 $A$ 上取值为 $a_i$。为了平衡，同时在其它的 $S_t(t=1,2,\cdots ,v,t\ne i)$ 中也增加 $r$ 个样本，这相当于在类 $C_j$ 中增加了 $r\times v$ 个样本，因此，其后验概率修正为 $$p(a_i|C_j)=\frac{|S_i|+r}{|C_j|+r\times v},(i=1,2,\cdots ,v)\text{\hspace{1em}(9-18)}$$ 因此，即使 $|S_i|=0$，由于$r>0$，其后验概率也不会为0。

2、概率乘积转换为对数求和

  对于概率值，即使每个乘积因子都不为零，但当 $d$ 较大时，$p(Z|C_j)$ 也可能几乎为零，这在多个类别的条件概率进行比较时，将难以区分它们大小，即不利于选择最大 $p(A|C_j)p(C_j)(j=1,2,\cdots ,k)$。$$p(Z|C_j)p(C_j)=p(C_j)\prod _{r=1}^{d}p(z_r|C_j)\text{\hspace{1em}(9-19)}$$ $${\log }_{2}p(Z|C_j)p(C_j)={\log }_{2}p(C_j)\prod _{r=1}^{d}p(z_r|C_j)={\log }_{2}p(C_j)+\sum _{k=1}^d{\log }_{2}p(z_r|C_j)\text{\hspace{1em}(9-20)}$$ 两式取极大值是一一对应的。因此，可以将 (9-19) 的乘积计算问题转化为 (9-20) 的加法计算问题，这样就可以避免所谓的 “溢出” 现象。

五、其它分类方法

1、粗糙集方法

  粗糙集 (Rough Set, RS) 理论是建立在分类机制的基础上的，它将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分。粗糙集能够在缺少关于数据先验知识的情况下，只以考察数据的分类能力为基础，解决模糊或不确定数据的分析和处理问题。

2、支持向量机方法

  支持向量机 (Support Vector Machine, SVM) 一种对线性和非线性数据进行分类的方法。SVM是一种算法，它使用一种非线性映射，将向量映射到一个更高维的空间，在这个空间里建立一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。平行超平面间的距离或差距越大，分类器的总误差越小。

3、神经网络方法

  神经网络，即人工神经网络 (Artificial Neural Network, ANN) 是模拟人脑思维方式的数学模型，是在现代生物学研究人脑组织成果的基础上提出的。神经网络是以大量简单神经元按一定规则连接构成的网络系统，从物理结构上模拟人类大脑的结构和功能，通过某种学习算法从训练样本中学习，并将获取的知识存储在网络各单元之间的连接权中。