劉亞輝，王 越，譚暑秋

(重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

樸素貝葉斯網(wǎng)分類器(Na?ve Bayesian classifier，NB)［1］是目前被公認(rèn)的一種簡(jiǎn)單而有效的概率分類的方法，它同時(shí)也是貝葉斯網(wǎng)分類器的一種。從某種意義上來(lái)說(shuō)其預(yù)測(cè)性能可與神經(jīng)網(wǎng)絡(luò)、決策樹(shù)等算法相媲美，因此在某些領(lǐng)域中表現(xiàn)出了它性能的優(yōu)異性［2］。許多工作研究者從不同的方向思考，并從NB方法中的“獨(dú)立性假設(shè)”出發(fā)，為了提高分類器的性能從而構(gòu)造出了不同的改進(jìn)模型［3-5］。由于樸素貝葉斯網(wǎng)絡(luò)的分類模型以各個(gè)非類屬性變量相對(duì)于類屬性變量相對(duì)獨(dú)立為前提的，也就是各個(gè)非類屬性變量獨(dú)立地作用于類屬性變量。此前提條件在一定程度上限制了樸素貝葉斯網(wǎng)絡(luò)分類模型的適用范圍，雖然降低了貝葉斯網(wǎng)絡(luò)的構(gòu)建復(fù)雜性，但是當(dāng)處理的數(shù)據(jù)維數(shù)較多，且數(shù)據(jù)量較大時(shí)，樸素貝葉斯網(wǎng)絡(luò)分類的效率則是偏低的，其準(zhǔn)確率有待提高。在樸素貝葉斯網(wǎng)絡(luò)的基礎(chǔ)上結(jié)合主元分析法與K-均值聚類算法構(gòu)造出了一個(gè)改進(jìn)的樸素貝葉斯網(wǎng)絡(luò)的分類模型。由于主元分析法是解決多維數(shù)據(jù)行之有效的方法，而K-均值聚類算法能夠使簇內(nèi)具有較高的相似度，而簇間的相似度較低，這將有便于從多維屬性中有效地進(jìn)行降維處理。

1 相關(guān)概念

概念1(相對(duì)融合點(diǎn)) 在一個(gè)數(shù)據(jù)集D=(x1，x2，…，xn)中，設(shè)存在一個(gè)值x'能夠代表數(shù)據(jù)中的特點(diǎn)并與數(shù)據(jù)集具有很好的擬合性，則x'稱為相對(duì)融合點(diǎn)。

概念2(K-均值聚類)K-means算法以K為參數(shù)，把N個(gè)對(duì)象分為K個(gè)簇，以使簇內(nèi)的相似度較高，而簇間的相似度較低。根據(jù)一個(gè)簇中的平均值(視為簇重心)來(lái)進(jìn)行相似度的計(jì)算。K-means算法的處理過(guò)程如下:(1)隨機(jī)選擇K個(gè)對(duì)象，每一個(gè)對(duì)象初始代表一個(gè)簇的中心或平均值。計(jì)算剩余的每個(gè)對(duì)象與各個(gè)簇中心的距離，再將剩余的對(duì)象賦給最近的簇。(2)不斷重復(fù)地計(jì)算每個(gè)簇的平均值，直至準(zhǔn)則函數(shù)收斂到期望值［6］。

概念3(主元分析) 主元分析(PCA)是在有一定相關(guān)性的m個(gè)樣本值與n個(gè)參數(shù)所構(gòu)成的數(shù)據(jù)陣列的基礎(chǔ)上，通過(guò)建立較小數(shù)目的綜合變量，使其更集中的反映原有數(shù)據(jù)陣列中包含的信息的方法［7］。

2 算法描述

設(shè)存在一張數(shù)據(jù)表，有m個(gè)對(duì)象記為X1，X2，…，Xm，有n個(gè)屬性記為a1，a2，…，an。其中每個(gè)對(duì)象Xi=(xi1，xi2，…，xin)，i=1，…，m，且xij(j=1，…，n)代表對(duì)象Xi的aj屬性。同樣aj=(x1j，x2j，…，xmj)，j=1，…，n。因此這張表可以用下面的矩陣來(lái)表示:

在一個(gè)歷史數(shù)據(jù)集中總是會(huì)出現(xiàn)一些數(shù)據(jù)保存不完善的情況，而且丟失數(shù)據(jù)不只一個(gè)。為了使問(wèn)題更容易地呈現(xiàn)，只討論一個(gè)數(shù)據(jù)丟失數(shù)據(jù)的情況。當(dāng)然此過(guò)程也可以被用到多個(gè)數(shù)據(jù)的丟失。改進(jìn)的樸素貝葉斯算法的步驟如下:

假設(shè)Xj是缺損比較嚴(yán)重的數(shù)據(jù)列，屬性Xj的值需要修補(bǔ)完整。在此假設(shè)數(shù)據(jù)的屬性列比較多，算法的基本步驟如下:

第1步:利用PCA算法降維。

(1)刪除矩陣B的第j列，得到如下矩陣D:

(2)對(duì)樣本數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理。

(3)計(jì)算相關(guān)矩陣。對(duì)給定的m個(gè)樣本，計(jì)算指標(biāo)變量的相關(guān)系數(shù)矩陣:

(4)求特征值和特征向量。求解特征方程:|R-λf|=0。通過(guò)此方程，可得到k個(gè)特征值(i=1～n)與對(duì)應(yīng)于每一個(gè)特征值的特征向量Qi=(ai1，ai2，…，aip)，其中i=1～k。

(6)設(shè)通過(guò)PCA

第2步:求降維后各列屬性值的相對(duì)融合點(diǎn)。

設(shè)列屬性yi={x1j，x2j，…，xmj}且j=1，…，n-l-1，則D1={y1，y2，…，yn}。設(shè)列屬性yi中任何兩個(gè)值之間的距離為d(xhi，xki)。

(1)求數(shù)值點(diǎn)的密度。確定一個(gè)正數(shù)d0，以每個(gè)數(shù)據(jù)為中心d0為半徑作n維空間的超球，令d(xhi，xki)為xhi到xki的距離，其中d(xhi，xki)=(h，k=1，2，…，m;j≠k)，若滿足d(xhi，xki)≤d0則認(rèn)為xki落在以xhi為圓心的超球內(nèi)，落在超球內(nèi)的點(diǎn)的總數(shù)為xhi的密度phi。不難發(fā)現(xiàn)，phi越大，則以它為相對(duì)融合點(diǎn)的資格就越大。

第3步:用K-均值算法對(duì)數(shù)據(jù)進(jìn)行聚類。

(1)初始時(shí)設(shè)前k個(gè)數(shù)作為簇的均值，并建立k個(gè)集合。依次分別把D1中的前k個(gè)數(shù)據(jù)依次放入到S1，S2，…，Sk(k≤n，k≠j)中，即S1={y'1}，S2={y'2}，…，Sk={y'k};

(2)依次從D1中取數(shù)據(jù)對(duì)象y'k+1，…，y'n，利用歐幾里德公式計(jì)算每個(gè)數(shù)據(jù)對(duì)象與每個(gè)簇均值的距離dqh=|y'q-y'h|(1≤q≤k，k+1≤h≤n)，dmin=min{dqh};

(4)若這k個(gè)集合里面的元素不再發(fā)生變化時(shí)，聚類結(jié)束。

第4步:形成貝葉斯網(wǎng)絡(luò)模型。

對(duì)聚類產(chǎn)生的各個(gè)元組中用鑒別信息來(lái)計(jì)算各個(gè)屬性之間的相互關(guān)系。最后再增加類到各個(gè)元組之間的有向邊。

圖1 聚類后局部貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)示意圖

為了便于理解，設(shè)類屬性為C，各個(gè)非類屬性為X={X1，X2…Xn}。設(shè)各個(gè)元組產(chǎn)生的聚類結(jié)果S1={X1，X3，X4，X9}，S2={X5，X13，X23}，…，Sk={X33，X38，X39，X41}。則經(jīng)過(guò)第一步處理之后如圖 1 所示。則最后形成的貝葉斯網(wǎng)絡(luò)如2所示。

第5步:對(duì)缺損的值分類分析后進(jìn)行修補(bǔ)。

圖2 形成的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)示意圖

圖3 改進(jìn)的樸素貝葉斯網(wǎng)絡(luò)算法流程示意圖

3 算法性能分析

分類算法模型是以在樸素貝葉斯網(wǎng)絡(luò)的基礎(chǔ)上提出來(lái)的，與之不同之處在于算法摒棄了非類屬性變量相對(duì)于類屬性變量是相對(duì)獨(dú)立的前提條件。在改進(jìn)的算法中，由于處理的數(shù)據(jù)非常的龐大，故在算法開(kāi)始就借用了主成分分析法在對(duì)數(shù)據(jù)信息量保存的同時(shí)來(lái)進(jìn)行降維操作，這樣對(duì)算法著重于分類模型的研究有很大的幫助。在改進(jìn)的算法中，給出了相對(duì)融合點(diǎn)這個(gè)概念，并給出了獲取相對(duì)融合點(diǎn)的算法。最后算法利用K-均值來(lái)研究各列屬性之間存在的隱含的依賴關(guān)系，有利于將列屬性值進(jìn)行融合，這樣就簡(jiǎn)化了下一步的K-均值聚類算法在數(shù)據(jù)中的處于算法對(duì)缺損值的分類。算法相當(dāng)于是擴(kuò)大了樸素貝葉斯網(wǎng)絡(luò)應(yīng)用的領(lǐng)域。當(dāng)對(duì)數(shù)據(jù)量很大，且各維屬性之間又存在著隱含關(guān)系時(shí)，樸素貝葉斯網(wǎng)絡(luò)很難達(dá)到理想的效果，而改進(jìn)的算法將是處理這些問(wèn)題行之有效的辦法。

4 實(shí)驗(yàn)與分析

實(shí)驗(yàn)采用“某工廠3月份高爐數(shù)據(jù)”樣本數(shù)據(jù)表作為數(shù)據(jù)集，共有200條數(shù)據(jù)記錄，11個(gè)屬性:硅Si，錳Mn，磷 P，硫 S，鈦Ti，鉻Cr，鎳 Ni，鐵Fe，鋅Zn，銅Cu，鎂Mg;其中有幾個(gè)缺失的數(shù)據(jù)，缺失數(shù)據(jù)會(huì)對(duì)分析結(jié)果造成一定的影響，減小結(jié)果的準(zhǔn)確度，必須使用合適的方法對(duì)數(shù)據(jù)進(jìn)行修補(bǔ)。該數(shù)據(jù)表的部分?jǐn)?shù)據(jù)情況如下表1所示。

表1 某工廠3月份高爐數(shù)據(jù)數(shù)據(jù)表

下面以缺失的第5條數(shù)據(jù)的“錳Mn”屬性值為例，通過(guò)實(shí)際的實(shí)驗(yàn)來(lái)說(shuō)明如何修補(bǔ)該缺失的值。第一步首先刪除該缺失值所在的屬性列“錳Mn”，對(duì)數(shù)據(jù)表進(jìn)行標(biāo)準(zhǔn)化處理，那么該數(shù)據(jù)表變?yōu)橐粋€(gè)200行10列的數(shù)據(jù)表，用矩陣表示如下:

然后對(duì)該數(shù)據(jù)表進(jìn)行標(biāo)準(zhǔn)化處理，再通過(guò)PCA算法作用后，數(shù)據(jù)表由10維降到了8維，去掉了“鈦Ti”，“銅Cu”。降維后的數(shù)據(jù)表用矩陣D1表示如下:

求降維后各列屬性值的相對(duì)融合點(diǎn)，并利用相對(duì)融合點(diǎn)結(jié)合K-均值算法對(duì)數(shù)據(jù)進(jìn)行聚類，聚類結(jié)果得到如下屬性分組:S1={鐵 Fe}，S2={硅 Si，鋅 Zn，鎂 Mg}，S3={磷 P，硫 S}，S4={鉻 Cr，鎳 Ni}。

對(duì)刪除的屬性列“錳Mn”用數(shù)學(xué)家史特吉斯(Sturges)提出的公式:k=1+3.32logn來(lái)對(duì)該列數(shù)據(jù)進(jìn)行分組，其中n為數(shù)據(jù)集中數(shù)據(jù)的個(gè)數(shù);則屬性值xi如果在［min+l*((max-min)/k)，min+(l+1)*((max-min)/k)］區(qū)間內(nèi)，則變換后的值為l。其中l(wèi)=0，1，…，k，min是屬性列中的最小值，而max是屬性列中的最大值，這里每一個(gè)分組被認(rèn)為一個(gè)類，有18個(gè)分類，即:C1，C2，…，C18。

最后對(duì)缺失的x5，2進(jìn)行修補(bǔ)，具體如下:

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

針對(duì)樸素貝葉斯網(wǎng)絡(luò)分類模型在處理高維大數(shù)據(jù)量時(shí)的效率偏低和準(zhǔn)確率有待提高的問(wèn)題，在樸素貝葉斯網(wǎng)絡(luò)的基礎(chǔ)上結(jié)合主元分析法與K-均值聚類算法構(gòu)造出了一個(gè)改進(jìn)的樸素貝葉斯網(wǎng)絡(luò)的分類模型。該模型摒棄了非類屬性變量相對(duì)于類屬性變量是相對(duì)獨(dú)立的前提條件，算法在一開(kāi)始就用主元分析法在對(duì)數(shù)據(jù)集的信息量盡量保存的同時(shí)進(jìn)行了降維操作，使得算法可以著重于進(jìn)行分類問(wèn)題。算法還提出了一個(gè)“相對(duì)融合點(diǎn)”的概念，并給出了相對(duì)融合點(diǎn)的獲取方法，有效地提高了算法的性能。最后將改進(jìn)的算法應(yīng)用到質(zhì)量管理中進(jìn)行了實(shí)驗(yàn)，用算法產(chǎn)生的分類結(jié)果對(duì)數(shù)據(jù)集中產(chǎn)生的一些缺失數(shù)據(jù)進(jìn)行修補(bǔ)，取得了較為理想的結(jié)果。

［1］PELIKAN M，GOLDBERG D，SASTRY K.Bayesian optimization algorithm，decision graphs，and Ocam’s razor［R］.Proceedings of the Genetic and Evolutionary Computation Conference(GECCO-2001)，PP.519-526.Also IlliGAL Report No.2000020(2001)

［2］FRIEDMAN N，GEIGER D，GOLDSZMIDT M.Bayesian Network Classifiers［J］.Machine Learning，1997，29:103-163

［3］PELIKAN M，SASTRY K，GOLDBERG D.Scalability of the Bayesian optimization algorithm［J］.International Journal of Approximate Reasoning，2002，31(3):221-258

［4］KAI M，ZHENG Z.A Study of AdaBoost with Na?ve Bayesian Classifier:Weakness and Improvement［J］.Computational Intelligence，2003(19):186-200

［5］DING Z，PENG Y，PAN R.BayesOWL:Uncertainty Modeling in Semantic Web Ontologies［J］.In Soft Computing in Ontologies and Semantic Web，Springer-Verlag，December 2005

［6］HAN J，KAMBER M.Data Mining:Concepts and Techniques［M］.Academic Press，2001

［7］王洪春，彭宏.一種基于主成分分析的異常點(diǎn)挖掘方法［J］.計(jì)算機(jī)科學(xué):2007，10(34):192-194