基于信息幾何構(gòu)建樸素貝葉斯分類器.doc

基于信息幾何構(gòu)建樸素貝葉斯分類器基于信息幾何構(gòu)建樸素貝葉斯分類器黃友平黃友平，男，博士研究生，主要研究方向?yàn)锽ayesian網(wǎng)絡(luò)、信息幾何。E-mail: ., 史忠植史忠植，男，研究員，博士生導(dǎo)師，主要研究領(lǐng)域?yàn)橹悄芸茖W(xué)、數(shù)據(jù)挖掘、智能主體。E-mail: （1 中科院研究生院, 北京 100080）（1,2 中科院計(jì)算所智能信息處理重點(diǎn)實(shí)驗(yàn)室, 北京 100080）摘 要：樸素貝葉斯分類器是機(jī)器學(xué)習(xí)中一種簡(jiǎn)單而又有效的分類方法。但是由于它的屬性條件獨(dú)立性假設(shè)在實(shí)際應(yīng)用中經(jīng)常不成立，這影響了它的分類性能。本文基于信息幾何和Fisher分，提出了一種新的創(chuàng)建屬性集的方法。把原有屬性經(jīng)過(guò)Fisher分映射成新的屬性集，并在新屬性集上構(gòu)建貝葉斯分類器。我們?cè)诶碚撋咸接懥诵聦傩蚤g的條件依賴關(guān)系，證明了在一定條件下新屬性間是條件獨(dú)立的。試驗(yàn)結(jié)果表明，該方法較好地提高了樸素貝葉斯分類器的性能。關(guān)鍵詞：樸素貝葉斯分類器；信息幾何；Fisher分；條件獨(dú)立61. 引言樸素貝葉斯分類器（Nave Bayesian Classifier）是一種基于Bayes理論的簡(jiǎn)單分類方法，它在很多領(lǐng)域都表現(xiàn)出優(yōu)秀的性能12。樸素貝葉斯分類器的“樸素”指的是它的條件獨(dú)立性假設(shè)，雖然在某些不滿足獨(dú)立性假設(shè)的情況下其仍然可能獲得較好的結(jié)果3，但是大量研究表明此時(shí)可以通過(guò)各種方法來(lái)提高樸素貝葉斯分類器的性能。改進(jìn)樸素貝葉斯分類器的方式主要有兩種：一種是放棄條件獨(dú)立性假設(shè)，在NBC的基礎(chǔ)上增加屬性間可能存在的依賴關(guān)系；另一種是重新構(gòu)建樣本屬性集，以新的屬性組（不包括類別屬性）代替原來(lái)的屬性組，期望在新的屬性間存在較好的條件獨(dú)立關(guān)系。目前對(duì)于第一種改進(jìn)方法研究得較多245。這些算法一般都是在分類精度和算法復(fù)雜度之間進(jìn)行折衷考慮，限制在一定的范圍內(nèi)而不是在所有屬性構(gòu)成的完全網(wǎng)中搜索條件依賴關(guān)系。雖然如此，尋找條件依賴關(guān)系依然需要較復(fù)雜的算法。而通過(guò)重新構(gòu)建樣本屬性集的方式則可以避免尋找條件依賴關(guān)系，保持樸素貝葉斯分類器的簡(jiǎn)單和直觀。事實(shí)上，屬性構(gòu)造方法一直是機(jī)器學(xué)習(xí)領(lǐng)域中重要的方法之一，在決策樹(shù)、規(guī)則學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)等方面得到了有效應(yīng)用67。Pazzani提出了一種構(gòu)建NBC的方法：BSEJ算法8，該算法是基于原有屬性的笛卡兒積來(lái)構(gòu)建新的屬性。本文基于信息幾何理論和Fisher分，提出了一種新的屬性構(gòu)造方法，從而得到一種新的樸素Bayes分類器IG-NBC(Information Geometry Nave Bayes Classifier)。我們?cè)诶碚撋咸接懥诵聦傩蚤g的條件獨(dú)立關(guān)系，并對(duì)一些特殊情況進(jìn)行了分析。最后給出了該算法與樸素貝葉斯分類器相比較的試驗(yàn)結(jié)果。2. 信息幾何和Fisher分信息幾何是采用（Riemann流形上的）微分幾何方法來(lái)研究統(tǒng)計(jì)學(xué)的理論。自1975年Efron首先在統(tǒng)計(jì)學(xué)中采用微分幾何方法以來(lái)，許多統(tǒng)計(jì)學(xué)家在這方面進(jìn)行了大量的工作。特別是由于甘利俊一（S.Amari）9-12和ZHU Haiyu13-15等人的杰出工作，使得信息幾何理論得到學(xué)術(shù)界的廣泛關(guān)注，成為統(tǒng)計(jì)學(xué)中一個(gè)令人矚目的新分支，并在許多領(lǐng)域得到了大量應(yīng)用。設(shè)m維樣本空間上隨機(jī)變量X的概率分布（參數(shù)）簇 Sp(X |)|，其中為該分布簇的參數(shù)向量，為n維歐式空間Rn的一個(gè)開(kāi)集。在p滿足一些正則條件的情況下，S形成一個(gè)微分流形，稱為統(tǒng)計(jì)流形，稱為統(tǒng)計(jì)流形的自然坐標(biāo)9。對(duì)于一個(gè)帶參數(shù)的概率分布p(X |)，其對(duì)數(shù)似然函數(shù)記為： （1）其中為n維歐式空間的向量。記, , 則該概率分布的Fisher信息矩陣定義為： （2）在自然坐標(biāo)下，F(xiàn)isher信息矩陣成為此概率分布所對(duì)應(yīng)的流形S的Riemann度量。事實(shí)上，從保持充分統(tǒng)計(jì)量變換下度量不變的意義上說(shuō)，F(xiàn)isher信息矩陣是統(tǒng)計(jì)流形上唯一合適的Riemann度量16。與歐式空間的距離不通，該度量具有相對(duì)坐標(biāo)變化的不變性，從而在很大程度上體現(xiàn)了樣本分布的內(nèi)在特征。設(shè), 則Fisher信息矩陣I 可寫為： （3）其中Ux又稱為Fisher分。Fisher分作為一種特征抽取的手段，在機(jī)器學(xué)習(xí)領(lǐng)域得到了廣泛的研究和應(yīng)用791920?？梢钥闯觯現(xiàn)isher分Ux把m維樣本空間中的每一個(gè)點(diǎn)映射為n維空間中的一個(gè)點(diǎn)： （4） Tsuda等人認(rèn)為Fisher分可以完全地抽取出樣本數(shù)據(jù)的類別分布信息，并可以分離出重要的屬性和無(wú)關(guān)的屬性19。3. 基于Fisher分的樸素貝葉斯分類器一個(gè)m維的有監(jiān)督訓(xùn)練樣本：(x1, x2, ., xm , C)，其中xi表示第I個(gè)屬性，C表示類別。記X(x1, x2, ., xm)，X的分布模型為Sp(X |)|，為n維歐式空間的一個(gè)開(kāi)集，S成為一個(gè)統(tǒng)計(jì)流形。我們記樣本X對(duì)應(yīng)的Fisher分Y(y1, y2, ., yn)，其中yi，這樣經(jīng)過(guò)Fisher分映射的新的樣本為（Y，C）。下面我們證明對(duì)于一類廣泛存在的分布簇指數(shù)分布簇，在一定的條件下其Fisher分的各分量是獨(dú)立的。定理1：對(duì)于指數(shù)簇分布p(X |)，在各充分統(tǒng)計(jì)量獨(dú)立的情況下，F(xiàn)isher分的各分量是相互獨(dú)立的。證明：指數(shù)簇分布的一般形式可以寫成： 其中為第i個(gè)充分統(tǒng)計(jì)量。則其Fisher分為： = ,易見(jiàn)：在相互獨(dú)立的情況下，F(xiàn)isher分的各分量相互獨(dú)立。證畢。在定理1中我們證明的是非條件獨(dú)立關(guān)系，事實(shí)上，在考慮類別條件的情況下，上述證明過(guò)程同樣成立。從該定理可以看出，在滿足一定條件的情況下，F(xiàn)isher分把原本（條件）相關(guān)的屬性組映射為（條件）無(wú)關(guān)的屬性組。在實(shí)際應(yīng)用中，常見(jiàn)的許多分布都屬于指數(shù)簇分布簇，例如正態(tài)分布，離散分布等。一個(gè)統(tǒng)計(jì)試驗(yàn)的充分統(tǒng)計(jì)量經(jīng)常對(duì)應(yīng)于分布簇的參數(shù)，在許多情況下它們具有較好的獨(dú)立性。在Fisher分映射的基礎(chǔ)上，我們可以采用通常的辦法建立樸素Bayesian分類器。具體算法描述如下：Step1：確定樣本的先驗(yàn)分布形式。樣本屬性的先驗(yàn)分布可以根據(jù)專家的經(jīng)驗(yàn)，也可以采用常用的統(tǒng)計(jì)方法或者是兩者的結(jié)合來(lái)選擇確定。Step2：補(bǔ)足數(shù)據(jù)中的缺失值。從Fisher分的計(jì)算可以看出，一個(gè)值的缺失可能導(dǎo)致整個(gè)Fihser分都算不出來(lái)?？梢圆捎贸Ｓ玫氖侄蝸?lái)補(bǔ)足缺失值，例如求期望，條件期望等。Step3：應(yīng)用Fisher分映射進(jìn)行樣本的變換。在確定樣本的先驗(yàn)分布簇后，通過(guò)公式（4）計(jì)算出樣本新的屬性值。Step4：特征選擇。由于Fisher分映射可能產(chǎn)生較多的維數(shù)（屬性數(shù)），需要采取特征選擇算法去掉其中與分類無(wú)關(guān)的維，而保留重要的維。Step5：對(duì)Fisher分進(jìn)行離散化。由于一般的樸素貝葉斯分類器都只處理離散屬性，而Fisher分為連續(xù)值，所以需要進(jìn)行離散化。但這不是必需的，而是依賴于下一步采取的算法?？梢圆扇《喾N常用的離散化方式。Step6：建立樸素貝葉斯分類器。完成前面四步后，我們已經(jīng)獲得了新的屬性集的離散形式，可以采用一般的方法建立樸素貝葉斯分類器。事實(shí)上本步驟還可以采用其它擴(kuò)展的樸素貝葉斯分類器，例如TAN、BSEJ等。我們認(rèn)為，一個(gè)類別的樣本對(duì)應(yīng)于一組或幾組特定的分布參數(shù)。由于Fisher分與樣本分布的參數(shù)相關(guān)，因此新的樣本屬性能夠較好地反映樣本的類別?；贔isher分構(gòu)造樸素貝葉斯分類器不僅保留了樣本數(shù)據(jù)中的信息，而且還可以通過(guò)選取分布簇的方式結(jié)合樣本先驗(yàn)分布的信息。從上面的討論可以看出，IG-NBC算法本身只是一個(gè)框架。它沒(méi)有確定如何去選擇樣本數(shù)據(jù)的先驗(yàn)分布簇。先驗(yàn)分布簇的確定是影響該算法性能的重要因素。先驗(yàn)分布形式的確定在統(tǒng)計(jì)學(xué)中已經(jīng)有了大量研究，本文不對(duì)此作深入探討。在具體應(yīng)用中，用戶可以在計(jì)算的復(fù)雜性和先驗(yàn)分布簇的準(zhǔn)確性中做一個(gè)折衷。4. 兩種特殊先驗(yàn)分布的討論4.1無(wú)先驗(yàn)信息的離散分布本節(jié)我們?cè)诶碚撋涎芯繉?duì)于無(wú)先驗(yàn)信息的離散分布情況IM_NBC與NBC的性能比較。首先我們給出離散分布的指數(shù)簇表示10：設(shè)樣本為(X; C )，其中X(x1, x2, ., xm)為樣本的屬性，C為類別標(biāo)注。設(shè)X有n1個(gè)值v1, v2, ., vn。令：piProbX=vi, 即X=vi 的概率，log, i=1,2,n， i=1,2,n在Xvi時(shí)為1，其余情況為0。則該離散分布可以寫作：p(X |)exp （5）其中=log，此即離散分布的指數(shù)簇表示。對(duì)該分布求Fisher分： , , （6）也即是說(shuō)，F(xiàn)isher分只有對(duì)應(yīng)于X=vi的一個(gè)分量為1，其余分量為0。該向量綜合了原樣本的所有信息。那么顯然容易看出該分類器的性能高于原樸素Bayesian分類器的性能。事實(shí)上，采用這種方式得到的Fisher分可以看成Pazzani所提的BSEJ算法的擴(kuò)展，也就是把所有屬性的笛卡兒積作為新的屬性。4.2 各分量條件獨(dú)立的情況不失一般性，我們分析樣本只有2個(gè)非類別標(biāo)記屬性的情況：樣本(X; C )，X(x1, x2)，其中x1, x2相互條件獨(dú)立。為方便起見(jiàn)下面的討論中我們省去類別條件，這將不會(huì)影響討論的過(guò)程和結(jié)果。設(shè)x1的分布為P(x1|)，設(shè)x2的分布為P(x2|)，不妨設(shè)、均為實(shí)數(shù)。X的分布可表示為：P( X|)P(x1|) P(x2|) （7）則P( X|)的Fisher分為： （8）易見(jiàn)，在x1, x2相互（條件）獨(dú)立的情況下，F(xiàn)isher分的各分量仍然保持（條件）獨(dú)立。也就是說(shuō)，單從屬性的獨(dú)立要求方面來(lái)說(shuō)，經(jīng)過(guò)Fisher分變換后建立的樸素Bayes分類器的分類性能不會(huì)比原本的樸素Bayes分類器更差。5. 試驗(yàn)結(jié)果為了驗(yàn)證IG-NBC算法的性能，我們測(cè)試了UCI數(shù)據(jù)庫(kù)中的10個(gè)數(shù)據(jù)集。如前所述，先驗(yàn)分布簇的確定是影響IG-NBC算法性能的重要因素。在試驗(yàn)中，對(duì)于離散屬性我們簡(jiǎn)單地采用4.1中所述方法，采用計(jì)算互信息的方法進(jìn)行屬性分組，從而計(jì)算Fisher分；而對(duì)于連續(xù)屬性，我們一律采用正態(tài)分布。對(duì)于有缺失值的情況，把缺失值作為一個(gè)特殊的值處理。我們除測(cè)試了在Fisher分的基礎(chǔ)上直接創(chuàng)建樸素貝葉斯分類器外，還測(cè)試了在Fisher分的基礎(chǔ)上建立TAN分類模型。試驗(yàn)結(jié)果如下：表1：試驗(yàn)結(jié)果（其中數(shù)據(jù)為分類精度）DomainNBCIG-NBCTANTA-IMNBCAnneal96.2496.3296.2496.34Glass68.6582.7567.7883.96Iris91.3592.0093.6292.05Letter74.5085.6085.8385.77Mushroom94.093.4196.4593.81Pima75.5175.5275.5275.52Post-op69.8870.0070.0170.00Segment91.1693.5595.5694.05Vote90.2187.7891.9588.45Waveform76.0486.3378.1087.52從上表可以看出IM-Bayes分類精度整體上比樸素貝葉斯分類器有了很大提高，與TAN模型比也有較大提高。還可以看出經(jīng)過(guò)樹(shù)擴(kuò)展的TA-IMNBC算法與IG-NBC算法比較并沒(méi)有很大的提高，這應(yīng)該是由于經(jīng)過(guò)Fisher分映射，新的樣本屬性間已經(jīng)存在較好的條件獨(dú)立性關(guān)系。試驗(yàn)中我們發(fā)現(xiàn)，對(duì)于缺失值較多的數(shù)據(jù)集，IG-NBC算法的精度有一定下降，這應(yīng)該是由于對(duì)于缺失太多的數(shù)據(jù)集，其Fisher分的計(jì)算存在誤差。6. 總結(jié)樸素貝葉斯分類器由于其簡(jiǎn)單而又具有較高的性能得到了廣泛的研究，但是由于其不切實(shí)際的條件獨(dú)立性假設(shè)限制了它的進(jìn)一步應(yīng)用。許多學(xué)者在研究如何提高樸素貝葉斯分類器的性能方面做了大量工作。目前主要有兩種途徑改進(jìn)樸素貝葉斯分類器，其一是放松條件獨(dú)立性的限制；其二是進(jìn)行屬性轉(zhuǎn)換，在原有屬性的基礎(chǔ)上創(chuàng)建新的屬性集。本文提出了一種基于信息幾何和Fisher分的屬性轉(zhuǎn)換方法，在理論上探討了新的屬性集間存在較好的條件獨(dú)立性關(guān)系，并通過(guò)試驗(yàn)驗(yàn)證了該方法在較大程度上提高了樸素貝葉斯分類器的性能。參考文獻(xiàn)：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.3Domingos, 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.105112, 1996.4 Kononenko, I.: Semi- Nave 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 (UAI99), 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.7Ragavan, 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 (ICNN97), 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., Ratsch, 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, 200219 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., Ratsch, Jagota, A., Muller, K.-R.: New Methods for Splice Site Recognition. In ICANN02, 2002.Constructing Nave Bayesian Classifier Based on Information GeometryHUANG Youping1,2, SHI Zhongzhi1（1 Key Laboratory of Intel