基于K-均值聚類的樸素貝葉斯網(wǎng)絡(luò)分類模型

劉亞輝，王 越，譚暑秋

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

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

1 相關(guān)概念

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

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

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

2 算法描述

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

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

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

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

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

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

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

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

(6)設(shè)通過PCA

第2步:求降維后各列屬性值的相對融合點。

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

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

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

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

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

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

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

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

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

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

第5步:對缺損的值分類分析后進行修補。

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

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

3 算法性能分析

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

4 實驗與分析

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

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

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

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

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

對刪除的屬性列“錳Mn”用數(shù)學(xué)家史特吉斯(Sturges)提出的公式:k=1+3.32logn來對該列數(shù)據(jù)進行分組，其中n為數(shù)據(jù)集中數(shù)據(jù)的個數(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是屬性列中的最大值，這里每一個分組被認為一個類，有18個分類，即:C1，C2，…，C18。

最后對缺失的x5，2進行修補，具體如下:

5 結(jié)束語

針對樸素貝葉斯網(wǎng)絡(luò)分類模型在處理高維大數(shù)據(jù)量時的效率偏低和準(zhǔn)確率有待提高的問題，在樸素貝葉斯網(wǎng)絡(luò)的基礎(chǔ)上結(jié)合主元分析法與K-均值聚類算法構(gòu)造出了一個改進的樸素貝葉斯網(wǎng)絡(luò)的分類模型。該模型摒棄了非類屬性變量相對于類屬性變量是相對獨立的前提條件，算法在一開始就用主元分析法在對數(shù)據(jù)集的信息量盡量保存的同時進行了降維操作，使得算法可以著重于進行分類問題。算法還提出了一個“相對融合點”的概念，并給出了相對融合點的獲取方法，有效地提高了算法的性能。最后將改進的算法應(yīng)用到質(zhì)量管理中進行了實驗，用算法產(chǎn)生的分類結(jié)果對數(shù)據(jù)集中產(chǎn)生的一些缺失數(shù)據(jù)進行修補，取得了較為理想的結(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］王洪春，彭宏.一種基于主成分分析的異常點挖掘方法［J］.計算機科學(xué):2007，10(34):192-194