基于信息几何构建朴素贝叶斯分类器.doc

基于信息几何构建朴素贝叶斯分类器
基于信息几何构建朴素贝叶斯分类器
黄友平黄友平，男，博士研究生，主要研究方向为Bayesian网络、信息几何。E-mail: huangyp@.
, 史忠植史忠植，男，研究员，博士生导师，主要研究领域为智能科学、数据挖掘、智能主体。E-mail: shizz@

（1 中科院研究生院, 北京 100080）
（1,2 中科院计算所智能信息处理重点实验室, 北京 100080）

摘 要：朴素贝叶斯分类器是机器学习中一种简单而又有效的分类方法。但是由于它的属性条件独立性假设在实际应用中经常不成立，这影响了它的分类性能。本文基于信息几何和Fisher分，提出了一种新的创建属性集的方法。把原有属性经过Fisher分映射成新的属性集，并在新属性集上构建贝叶斯分类器。我们在理论上探讨了新属性间的条件依赖关系，证明了在一定条件下新属性间是条件独立的。试验结果表明，该方法较好地提高了朴素贝叶斯分类器的性能。
关键词：朴素贝叶斯分类器；信息几何；Fisher分；条件独立

6

1. 引言
朴素贝叶斯分类器（Naïve Bayesian Classifier）是一种基于Bayes理论的简单分类方法，它在很多领域都表现出优秀的性能[1][2]。朴素贝叶斯分类器的“朴素”指的是它的条件独立性假设，虽然在某些不满足独立性假设的情况下其仍然可能获得较好的结果[3]，但是大量研究表明此时可以通过各种方法来提高朴素贝叶斯分类器的性能。改进朴素贝叶斯分类器的方式主要有两种：一种是放弃条件独立性假设，在NBC的基础上增加属性间可能存在的依赖关系；另一种是重新构建样本属性集，以新的属性组（不包括类别属性）代替原来的属性组，期望在新的属性间存在较好的条件独立关系。
目前对于第一种改进方法研究得较多[2][4][5]。这些算法一般都是在分类精度和算法复杂度之间进行折衷考虑，限制在一定的范围内而不是在所有属性构成的完全网中搜索条件依赖关系。虽然如此，寻找条件依赖关系依然需要较复杂的算法。而通过重新构建样本属性集的方式则可以避免寻找条件依赖关系，保持朴素贝叶斯分类器的简单和直观。事实上，属性构造方法一直是机器学习领域中重要的方法之一，在决策树、规则学习、神经网络等方面得到了有效应用[6][7]。Pazzani提出了一种构建NBC的方法：BSEJ算法[8]，该算法是基于原有属性的笛卡儿积来构建新的属性。
本文基于信息几何理论和Fisher分，提出了一种新的属性构造方法，从而得到一种新的朴素Bayes分类器IG-NBC(Information Geometry – Naïve Bayes Classifier)。我们在理论上探讨了新属性间的条件独立关系，并对一些特殊情况进行了分析。最后给出了该算法与朴素贝叶斯分类器相比较的试验结果。
2. 信息几何和Fisher分
信息几何是采用（Riemann流形上的）微分几何方法来研究统计学的理论。自1975年Efron首先在统计学中采用微分几何方法以来，许多统计学家在这方面进行了大量的工作。特别是由于甘利俊一（S.Amari）[9]-[12]和ZHU Haiyu[13]-[15]等人的杰出工作，使得信息几何理论得到学术界的广泛关注，成为统计学中一个令人瞩目的新分支，并在许多领域得到了大量应用。
设m维样本空间上随机变量X的概率分布（参数）簇 S＝{p(X |θ)|θ∈Θ}，其中θ为该分布簇的参数向量，Θ为n维欧式空间Rn的一个开集。在p满足一些正则条件的情况下，S形成一个微分流形，称为统计流形，θ称为统计流形的自然坐标[9]。
对于一个带参数θ的概率分布p(X |θ)，其对数似然函数记为：
（1）
其中为n维欧式空间的向量。
记, , 则该概率分布的Fisher信息矩阵定义为：
（2）

在自然坐标θ下，Fisher信息矩阵成为此概率分布所对应的流形S的Riemann度量。事实上，从保持充分统计量变换下度量不变的意义上说，Fisher信息矩阵是统计流形上唯一合适的Riemann度量[16]。与欧式空间的距离不通，该度量具有相对坐标变化的不变性，从而在很大程度上体现了样本分布的内在特征。
设, 则Fisher信息矩阵I 可写为：
（3）
其中Ux又称为Fisher分。Fisher分作为一种特征抽取的手段，在机器学习领域得到了广泛的研究和应用[7][9][19][20]。可以看出，Fisher分Ux把m维样本空间中的每一个点映射为n维空间中的一个点：

（4）

Tsuda等人认为Fisher分可以完全地抽取出样本数据的类别分布信息，并可以分离出重要的属性和无关的属性[19]。
3. 基于Fisher分的朴素贝叶斯分类器
一个m维的有监督训练样本：(x1, x2, ..., xm , C)，其中xi表示第I个属性，C表示类别。记X＝(x1, x2, ..., xm)，X的分布模型为S＝{p(X |θ)|θ∈Θ}，Θ为n维欧式空间的一个开集，S成为一个统计流形。
我们记样本X对应的Fisher分Y＝(y1, y2, ..., yn)，其中yi＝，这样经过Fisher分映射的新的样本为（Y，C）。下面我们证明对于一类广泛存在的分布簇－指数分布簇，在一定的条件下其Fisher分的各分量是独立的。
定理1：对于指数簇分布p(X |θ)，在各充分统计量独立的情况下，Fisher分的各分量是相互独立的。
证明：
指数簇分布的一般形式可以写成：
其中为第i个充分统计量。
则其Fisher分为：

= ,,…,

易见：
在相互独立的情况下，Fisher分的各分量相互独立。
证毕。
在定理1中我们证明的是非条件独立关系，事实上，在考虑类别条件的情况下，上述证明过程同样成立。从该定理可以看出，在满足一定条件的情况下，Fisher分把原本（条件）相关的属性组映射为（条件）无关的属性组。
在实际应用中，常见的许多分布都属于指数簇分布簇，例如正态分布，离散分布等。一个统计试验的充分统计量经常对应于分布簇的参数，在许多情况下它们具有较好的独立性。
在Fisher分映射的基础上，我们可以采用通常的办法建立朴素Bayesian分类器。具体算法描述如下：
Step1：确定样本的先验分布形式。样本属性的先验分布可以根据专家的经验，也可以采用常用的统计方法或者是两者的结合来选择确定。
Step2：补足数据中的缺失值。从Fisher分的计算可以看出，一个值的缺失可能导致整个Fihser分都算不出来。可以采用常用的手段来补足缺失值，例如求期望，条件期望等。
Step3：应用Fisher分映射进行样本的变换。在确定样本的先验分布簇后，通过公式（4）计算出样本新的属性值。
Step4：特征选择。由于Fisher分映射可能产生较多的维数（属性数），需要采取特征选择算法去掉其中与分类无关的维，而保留重要的维。
Step5：对Fisher分进行离散化。由于一般的朴素贝叶斯分类器都只处理离散属性，而Fisher分为连续值，所以需要进行离散化。但这不是必需的，而是依赖于下一步采取的算法。可以采取多种常用的离散化方式。
Step6：建立朴素贝叶斯分类器。完成前面四步后，我们已经获得了新的属性集的离散形式，可以采用一般的方法建立朴素贝叶斯分类器。事实上本步骤还可以采用其它扩展的朴素贝叶斯分类器，例如TAN、BSEJ等。
我们认为，一个类别的样本对应于一组或几组特定的分布参数。由于Fisher分与样本分布的参数相关，因此新的样本属性能够较好地反映样本的类别。基于Fisher分构造朴素贝叶斯分类器不仅保留了样本数据中的信息，而且还可以通过选取分布簇的方式结合样本先验分布的信息。
从上面的讨论可以看出，IG-NBC算法本身只是一个框架。它没有确定如何去选择样本数据的先验分布簇。先验分布簇的确定是影响该算法性能的重要因素。先验分布形式的确定在统计学中已经有了大量研究，本文不对此作深入探讨。在具体应用中，用户可以在计算的复杂性和先验分布簇的准确性中做一个折衷。
4. 两种特殊先验分布的讨论
4.1无先验信息的离散分布
本节我们在理论上研究对于无先验信息的离散分布情况IM_NBC与NBC的性能比较。首先我们给出离散分布的指数簇表示[10]：
设样本为(X; C )，其中X＝(x1, x2, ..., xm)为样本的属性，C为类别标注。设X有n＋1个值v1, v2, ..., vn。令：
pi＝Prob{X=vi}, 即X=vi 的概率，
＝log, i=1,2,…,n
， i=1,2,…,n
在X＝vi时为1，其余情况为0。
则该离散分布可以写作：
p(X |θ)＝exp{} （5）
其中=log，此即离散分布的指数簇表示。
对该分布求Fisher分：

,,…,
,,…, （6）

也即是说，Fisher分只有对应于X=vi的一个分量为1，其余分量为0。该向量综合了原样本的所有信息。那么显然容易看出该分类器的性能高于原朴素Bayesian分类器的性能。事实上，采用这种方式得到的Fisher分可以看成Pazzani所提的BSEJ算法的扩展，也就是把所有属性的笛卡儿积作为新的属性。
4.2 各分量条件独立的情况
不失一般性，我们分析样本只有2个非类别标记属性的情况：样本(X; C )，X＝(x1, x2)，其中x1, x2相互条件独立。为方便起见下面的讨论中我们省去类别条件，这将不会影响讨论的过程和结果。
设x1的分布为P(x1|)，设x2的分布为P(x2|)，不妨设、均为实数。X的分布可表示为：
P( X|θ)＝P(x1|) P(x2|) （7）
则P( X|θ)的Fisher分为：

（8）

易见，在x1, x2相互（条件）独立的情况下，Fisher分的各分量仍然保持（条件）独立。也就是说，单从属性的独立要求方面来说，经过Fisher分变换后建立的朴素Bayes分类器的分类性能不会比原本的朴素Bayes分类器更差。
5. 试验结果
为了验证IG-NBC算法的性能，我们测试了UCI数据库中的10个数据集。如前所述，先验分布簇的确定是影响IG-NBC算法性能的重要因素。在试验中，对于离散属性我们简单地采用4.1中所述方法，采用计算互信息的方法进行属性分组，从而计算Fisher分；而对于连续属性，我们一律采用正态分布。对于有缺失值的情况，把缺失值作为一个特殊的值处理。
我们除测试了在Fisher分的基础上直接创建朴素贝叶斯分类器外，还测试了在Fisher分的基础上建立TAN分类模型。试验结果如下：

表1：试验结果（其中数据为分类精度）
Domain
NBC
IG-NBC
TAN
TA-IMNBC
Anneal
96.24
96.32
96.24
96.34
Glass
68.65
82.75
67.78
83.96
Iris
91.35
92.00
93.62
92.05
Letter
74.50
85.60
85.83
85.77
Mushroom
94.0
93.41
96.45
93.81
Pima
75.51
75.52
75.52
75.52
Post-op
69.88
70.00
70.01
70.00
Segment
91.16
93.55
95.56
94.05
Vote
90.21
87.78
91.95
88.45
Waveform
76.04
86.33
78.10
87.52

从上表可以看出IM-Bayes分类精度整体上比朴素贝叶斯分类器有了很大提高，与TAN模型比也有较大提高。还可以看出经过树扩展的TA-IMNBC算法与IG-NBC算法比较并没有很大的提高，这应该是由于经过Fisher分映射，新的样本属性间已经存在较好的条件独立性关系。试验中我们发现，对于缺失值较多的数据集，IG-NBC算法的精度有一定下降，这应该是由于对于缺失太多的数据集，其Fisher分的计算存在误差。
6. 总结
朴素贝叶斯分类器由于其简单而又具有较高的性能得到了广泛的研究，但是由于其不切实际的条件独立性假设限制了它的进一步应用。许多学者在研究如何提高朴素贝叶斯分类器的性能方面做了大量工作。目前主要有两种途径改进朴素贝叶斯分类器，其一是放松条件独立性的限制；其二是进行属性转换，在原有属性的基础上创建新的属性集。本文提出了一种基于信息几何和Fisher分的属性转换方法，在理论上探讨了新的属性集间存在较好的条件独立性关系，并通过试验验证了该方法在较大程度上提高了朴素贝叶斯分类器的性能。

参考文献：
[1] Langley, P., Iba, W., & Thompson, K.: An Analysis of Bayesian Classifiers. Proceedings of the Tenth National Conference on Artificial Intelligence, San Jose, CA, AAAI Press,pp. 223-228, 1992.
[2] Friedman, N., Geiger, D., Goldszmidt, M.: Bayesian Network Classifiers. Machine Learning, 29, pp.103-163 ,1997.
[3]Domingos, P., Pazzani, M.: Beyond Independence: Conditions for the Optimality of the Simple Bayesian Classifier. Proceedings of the Thirteenth International Conference on Machine Learning, Morgan Kaufmann Publishers, Inc. pp.105–112, 1996.
[4] Kononenko, I.: Semi- Naïve Bayesian Classifier. Y. Kodratoff (Ed.), Proceedings of Sixth European Working Session on Learning, Springer-Verlag, pp.206-219, 1991.
[5] Cheng, J., Greiner, R.: Comparing Bayesian Network Classifiers. Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI'99), pp.101-107, 1999.
[6] Matheus, C. J.: Adding Domain Knowledge to SBL through Feature Construction. Proceedings of the Eighth National Conference on Artificial Intelligence, Boston, MA: AAAI Press ,pp.803-808, 1990.
[7]Ragavan, H., Rendell, L.: Lookahead Feature Construction for Learning Hard Concepts. Proceedings of the Tenth International Conference on Machine Learning, Amherst, MA, pp.252-259, 1993.
[8] Pazzani, M.: Constructive Induction of Cartesian Product Attributes. Information, Statistics and Induction in Science, Melbourne, Australia. 1996.
[9] Amari, S.Differential-Geometrical Methods in Statistics, Lecture Notes in Statistics, Springer-Verlag, Berlin, Vol.28, 1985.
[10] Amari, S. Information Geometry of the EM and em Algorithms for Neural Networks. Neural Networks, 8(9) pp.1379-1408, 1995.
[11] Amari, S. Information Geometry on Hierarchical Decomposition of Stochastic Interactions. IEEE Transaction on Information Theory ,pp.1701-1711, 2001.
[12] Ikeda, S., Tanaka, T., Amari, S. T. G. Dietterich et al. (eds.), Information Geometrical Framework for Analyzing Belief Propagation Decoder. Advances in Neural Information Processing Systems, The MIT Press, Vol.14, 2002.
[13] Zhu, H., Rohwer, R.: Bayesian Geometric Theory of Statistical Inference. Submitted to Ann. Stat. 1995.
[14] Zhu, H.: On the Mathematical Foundation of Learning Algorithms. Submitted to Machine Learning 1996.
[15] Zhu, H.: Bayesian Geometric Theory of Learning Algorithms. Proceedings of the International Conference on Neural Networks (ICNN'97), volume 2, pp. 1041--1044, Houston, June 1997.
[16] Wei, B., Some invariance of statistic manifold, Application of probability statistics, Vol.3 pp.106-112 (in Chinese), 1987.
[17] Tsuda, K., Kawanabe, M., R¨atsch, G., Sonnenburg, S., Muller, K.-R.: A New Discriminative Kernel from Probabilistic Models. Neural Computation. 2002.
[18] Vinokourov, A., Girolami, M.: A Probabilistic Framework for the Hierarchic Organization and Classification of Document Collections. Journal of Intelligent Information Systems, 18(2/3), pp.153– 172, 2002
[19] Tsuda, K., Kawanabe, M., Muller, K.-R. Clustering with the Fisher Score. In S. Becker, S. Thrun, and K. Obermayer, (eds.), Advances in Neural Information Processing Systems 15. MIT Press. 2003.
[20] Muller Sonnenburg, S., R¨atsch, Jagota, A., M¨uller, K.-R.: New Methods for Splice Site Recognition. In ICANN’02, 2002.

Constructing Naïve Bayesian Classifier Based on Information Geometry
HUANG Youping1,2, SHI Zhongzhi1
（1 Key Laboratory of Intelligent Information Processing, Institute of Computing Technology,
Chinese Academy of Sciences, Beijing 100080, China;
2 Graduate School of the Chinese Academy of Sciences , Beijing 100080, China）
Abstract：The Naïve Bayesian Classifier (NBC) is a simple yet effective technique for machine learning. But the unpractical condition independence assumption of the Naïve Bayesian Classifier (NBC) greatly degrades the performance of classifying. This paper improved this method based on information geometry theory and Fisher score. We map the original attributes to new attribute set according to the Fisher score, and construct the NBC on the new attribute set. We further prove that these new attributes are condition independent of each other on certain conditions. This method shows excellent performance in experiments.
Key words：Naïve Bayesian Classifier; Information Geometry; Fisher Score; Condition Independence

(责任编辑：曾 丹)