包小兵 ，翟素蘭 ，程蘭蘭

（1.池州學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，安徽 池州 247000；2.安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230039）

基于雨林框架的樸素貝葉斯分類算法

包小兵1，2，翟素蘭2，程蘭蘭2

（1.池州學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，安徽 池州 247000；2.安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230039）

提出了一種可伸縮的樸素貝葉斯分類算法。算法針對(duì)大數(shù)據(jù)集的訓(xùn)練數(shù)據(jù)，通過(guò)構(gòu)建雨林框架，能在有限主存里存儲(chǔ)訓(xùn)練數(shù)據(jù)，訓(xùn)練生成概率矩陣，進(jìn)而對(duì)測(cè)試樣本進(jìn)行分類。算法僅對(duì)整庫(kù)一次掃描。實(shí)驗(yàn)表明，該算法能夠獲得與整庫(kù)讀入主存相同的分類準(zhǔn)確率，并且有較高的處理效率。

雨林;可伸縮算法;樸素貝葉斯分類

1 引言

分類問(wèn)題是一種重要的數(shù)據(jù)挖掘問(wèn)題，分類算法在各個(gè)領(lǐng)域已得到廣泛的應(yīng)用，為了增加分類算法的準(zhǔn)確性，除了改進(jìn)算法本身，更重要的是能夠使用大數(shù)據(jù)集進(jìn)行訓(xùn)練，而這樣會(huì)受到兩個(gè)方面的因素制約：一是增加處理時(shí)間，二是沒有足夠的主存來(lái)存儲(chǔ)大數(shù)據(jù)集，主輔存數(shù)據(jù)的轉(zhuǎn)出轉(zhuǎn)入將耗用更多的處理時(shí)間。迫切需要解決該問(wèn)題。

算法的可伸縮性是指當(dāng)算法運(yùn)行需要大數(shù)據(jù)集時(shí)算法的有效性問(wèn)題，即是說(shuō)一個(gè)分類算法的可伸縮性好意味著它可以處理大訓(xùn)練集且有較高的分類精確度。而有些分類算法的可伸縮性差則成了阻礙它們廣泛應(yīng)用的原因之一。在處理算法的可伸縮性問(wèn)題上通常用下面的方法：(1)在大訓(xùn)練集中進(jìn)行數(shù)據(jù)采樣；(2)將數(shù)據(jù)分成若干小塊，分別構(gòu)建分類器，然后綜合成一個(gè)最終的分類器。但這些方法最大的問(wèn)題是降低了分類算法的準(zhǔn)確性，所以它們并不是好的處理方法。本文提出了基于Rainforest[2]框架的樸素貝葉斯分類算法[1]，在能夠訓(xùn)練大數(shù)據(jù)集的同時(shí)也具有較高的分類精確度。

2 預(yù)備知識(shí)

2.1 基本理論

貝葉斯分類法是統(tǒng)計(jì)學(xué)的方法，可以預(yù)測(cè)類成員關(guān)系的可能性。實(shí)踐表明表現(xiàn)出高準(zhǔn)確率和高速度。貝葉斯分類基于貝葉斯定理，下面介紹貝葉斯定理。

定理1[1]（貝葉斯定理）設(shè)樣本空間S被分成一個(gè)含有n個(gè)互斥事件的集合，每個(gè)事件成為S的一個(gè)劃分：

S={A1,A2， …,An},AiAj=0,i≠j，X 是 S中任意一個(gè)事件，則有下面的結(jié)論：

樸素貝葉斯分類法[2](Nalve Bayesian Classifier，NBC)是基于條件獨(dú)立性假設(shè)，即假設(shè)一個(gè)屬性對(duì)給定類的影響?yīng)毩⒂谄渌鼘傩?。這一假定稱為類條件獨(dú)立性。

設(shè)D是包含類標(biāo)號(hào)的訓(xùn)練元組集合，每個(gè)元組用n維向量X={x1,x2,…,xn}表示，屬性集合可記為DA={A1,A2，…,An}。假設(shè)有 J個(gè)類 C1,C2,…，CJ，給定的元組X，分類法將預(yù)測(cè)X屬于具有最高后驗(yàn)概率（條件X下）的類。根據(jù)貝葉斯定理有：

其中，P(X)為常數(shù)，先驗(yàn)概率P(Ci)可以根據(jù)訓(xùn)練元組計(jì)算得到。為最大化后驗(yàn)概率P（Ci|X），需要最大化條件概率 P（Xi|Ci）。 而事實(shí)上計(jì)算 P（X|Ci）往往是復(fù)雜并且開銷較大的，因此做了類條件獨(dú)立的樸素假設(shè)，于是有：

其中xk表示元組 X屬性 Ak的值，P （Xk|Ci）的值由訓(xùn)練元組計(jì)算。

2.2 樸素貝葉斯分類算法

為了計(jì)算條件概率P（Xk|Ci）以計(jì)算后驗(yàn)概率，在本文提出的算法中給出如下的定義。

定義1設(shè)A為元組的一個(gè)屬性，xk為屬性A的取值，其中k=1,2,…，nA,類標(biāo)號(hào)取值為Ci,i∈{1,2,…，J}，稱由所有條件概率P（Xk|Ci）生成的矩陣為概率矩陣，定義如下：

那么對(duì)于DA中的所有屬性，得到如下的概率矩陣簇，記為：

在對(duì)預(yù)測(cè)元組X進(jìn)行分類時(shí)，只需要將元組值和上面定義的概率矩陣簇進(jìn)行對(duì)照，找出相應(yīng)的條件概率值，根據(jù)公式（3）算出各個(gè)類的后驗(yàn)概率，比較后得出預(yù)測(cè)分類，分類完成。

2.3 雨林框架

從樸素貝葉斯分類算法中可以看出，為了計(jì)算條件概率P（X|Ci），僅需要對(duì)各個(gè)屬性取值和類取值分別統(tǒng)計(jì)，面對(duì)大數(shù)據(jù)集，使用如下的Rainforest框架處理。

設(shè)D為訓(xùn)練數(shù)據(jù)集的元組集合，屬性列表集為X，對(duì)于屬性x∈X，將D往屬性列x和類標(biāo)號(hào)列C作投影，得到新數(shù)據(jù)集 Dx={t(x,i)|x∈X,i∈C}，其中，設(shè)類標(biāo)號(hào)取值為dom(C)={1,2,…,J}。對(duì)屬性x的不同值在每個(gè)類別i上作計(jì)數(shù)，令aX,x,i為滿足屬性值t.X=x且類標(biāo)號(hào)t.C=i的元組t的個(gè)數(shù)，形式地定義如下：

定義 2[3]令 S=dom(x)×NJ，其中 NJ={(a1,a2,…，aJ)|ai=aX,x,i,i∈dom(C)}，如下定義 AVC-set(Attribute-Value Classlabel set):

定義3[3]稱由每個(gè)屬性x∈X對(duì)應(yīng)的AVC-sets構(gòu)成的集合為AVC-group，形式表示為：AVCgroup={AVC(x)|x∈X}。

用以上定義構(gòu)建的結(jié)構(gòu)被稱為是雨林框架（Rainforest Framework），如果訓(xùn)練集存儲(chǔ)在數(shù)據(jù)庫(kù)，AVC-set可以通過(guò)簡(jiǎn)單的SQL查詢得到：select D.x,D.C,count(*)from D where fn group by D.x,D.C。因此，對(duì)于雨林框架，一方面算法實(shí)現(xiàn)簡(jiǎn)單，另一方面是對(duì)于大訓(xùn)練數(shù)據(jù)集，生成的AVC-group的存儲(chǔ)開銷僅與屬性個(gè)數(shù)、各屬性取值個(gè)數(shù)及類標(biāo)號(hào)取值有關(guān)，容易被有限的主存接受。

3 可伸縮的樸素貝葉斯分類算法

3.1 算法步驟

本文提出的可伸縮的樸素貝葉斯分類算法是將雨林算法應(yīng)用到樸素貝葉斯分類算法上，算法流程如下圖1。

圖1 算法流程

具體的算法過(guò)程描述如下：

（1）預(yù)掃描訓(xùn)練樣本的前n條記錄，以獲取屬性個(gè)數(shù)、屬性名、類標(biāo)號(hào)名、各個(gè)屬性的取值和類標(biāo)號(hào)取值；

（2）建立雨林結(jié)構(gòu) AVC-set；

（3）掃描整個(gè)訓(xùn)練樣本，計(jì)算上面定義的aX,x,i，寫入雨林結(jié)構(gòu)AVC-set的valueClass，進(jìn)而生成AVC-group，樣本掃描完畢，整個(gè)雨林結(jié)構(gòu)建立完成；

（4）建立定義1的概率矩陣結(jié)構(gòu)，將從AVC-group讀取的數(shù)據(jù)計(jì)算出結(jié)果寫入概率矩陣。概率矩陣建立完成，則訓(xùn)練過(guò)程完成；

（5）讀取測(cè)試樣本，從概率矩陣中獲取各屬性相對(duì)各類的條件概率，計(jì)算各個(gè)類的后驗(yàn)概率，比較得出所屬類，分類完成。算法結(jié)束。

3.2 算法改進(jìn)及一些說(shuō)明

3.2.1 算法的時(shí)間和空間復(fù)雜度 該算法的時(shí)間復(fù)雜度主要在于對(duì)訓(xùn)練樣本的訓(xùn)練過(guò)程中AVC-group的建立，訓(xùn)練樣本元組數(shù)目為n，時(shí)間復(fù)雜度為O(n)。算法中除了掃描訓(xùn)練集所需的內(nèi)存開銷外，常駐內(nèi)存的是AVC-group和概率矩陣，而屬性名個(gè)數(shù)與屬性取值均為常數(shù)，故空間復(fù)雜度為O(1)。

3.2.2 算法說(shuō)明與改進(jìn) 該算法的主要優(yōu)點(diǎn)是讓貝葉斯分類算法具有可伸縮性，對(duì)于無(wú)法一次性讀入主存的大數(shù)據(jù)集，采取分批讀入，一次讀入的行數(shù)可視具體硬件配置設(shè)定。

在一些專業(yè)領(lǐng)域訓(xùn)練數(shù)據(jù)不是一次給出的，該算法還可以做一點(diǎn)簡(jiǎn)單改進(jìn)，將第一次訓(xùn)練生成的AVC-group寫入輔存，第二次讀取新的訓(xùn)練集時(shí)把生成的AVC-group與前次生成的AVC-group合并，而不需要重新讀取前次的訓(xùn)練集，也不需要花費(fèi)額外的存儲(chǔ)空間，僅需要多出讀取前次生成的AVC-group的算法做了具體的實(shí)驗(yàn)，其中硬件平臺(tái)：Pentium E2160 1.8GHz處理器，1G內(nèi)存；軟件平臺(tái)：Windows XP sp3， 開發(fā)環(huán)境：Visual Studio 2005，C#實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果分析如下：

對(duì)UCI數(shù)據(jù)庫(kù)里的Nursery樣本數(shù)據(jù)129600條記錄用本算法分批讀入內(nèi)存處理，所得的結(jié)果能與樣本全部讀入內(nèi)存得到相同的分類準(zhǔn)確率，并且耗用時(shí)間相當(dāng)。這表明，該算法是有效的，可以用于大數(shù)據(jù)集的訓(xùn)練分類。

5 結(jié)束語(yǔ)

針對(duì)為提高分類準(zhǔn)確率而增大訓(xùn)練樣本帶來(lái)的算法可伸縮問(wèn)題，本文提出一種基于雨林框架的樸素貝葉斯分類算法，實(shí)驗(yàn)表明在解決伸縮性問(wèn)題的同時(shí)，保證了算法的高效和高準(zhǔn)確率。但是本算法是基于“樸素”前提的，對(duì)于實(shí)際數(shù)據(jù)集并不滿足屬性獨(dú)立，針對(duì)這種情況，本算法還需進(jìn)一步改進(jìn)；另一方面還需考慮當(dāng)訓(xùn)練數(shù)據(jù)存在數(shù)據(jù)缺失的情況的處理方法。下步將進(jìn)行這方面的研究。

[1]李賢平.概率論基礎(chǔ)[M].北京:高等教育出版社,1997.

[2]Jiawei Han,Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)[M].范明,孟小峰，譯.北京:機(jī)械工業(yè)出版社,2007:201-206.

[3]GehrkeJ,Ramakrishnan R,Gantiy V.RainForest-A Framework for Fast Decision Tree Construction of Large Datasets[C]//Data Mining and Knowledge Discovery.NetheHands:Kluwer Academic Pcblisher,2000:135-149.

Bao Xiaobing,Zhai Sulan,Cheng Lanlan
（Institute of Mathematical Sciences,Anhui university,Heifei Anhui 230039）

A scalable Nave bayesian classifier algorithm is proposed which is aimed at training data of large dataset.Through constructing rainforest framework,training data can be stored in the limited memory and generates probability matrix,Then the testing samples are classified.Algorithm only scans whole dataset for one time.Experiments shows that Algorithm can obtain the same classification accuracy as reading-in of the whole database and have a higher processing efficiency.

Rainforest;Scalable Algorithm;Na ve Bayesian Classifier

TP 391

A

1674-1103(2012)03-0001-03

2011-11-23

安徽省高校優(yōu)秀青年人才基金項(xiàng)目（0510118）。

包小兵（1981-），男，安徽廬江人，安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘；翟素蘭（1977-），女，安徽渦陽(yáng)人，安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院副教授，博士，碩士生導(dǎo)師，研究方向?yàn)槟Ｊ阶R(shí)別與數(shù)據(jù)挖掘。

[責(zé)任編輯：曹懷火]