黃永毅+鈕靖+王秋紅

摘 要 隨著社會信息化的發(fā)展，數(shù)據(jù)庫技術(shù)、數(shù)據(jù)倉庫等的發(fā)展，社會發(fā)展各領(lǐng)域都面臨著海量數(shù)據(jù)處理的問題，其中不確定數(shù)據(jù)的處理成為熱點(diǎn)問題，文章通過分析不確定性數(shù)據(jù)分類問題的研究現(xiàn)狀，在對各種貝葉斯分類器的特點(diǎn)進(jìn)行總結(jié)的基礎(chǔ)上，基于Weka平臺研究使用貝葉斯分類算法在不同類型的不確定性數(shù)據(jù)上的分類性能。

關(guān)鍵詞 不確定性數(shù)據(jù)；數(shù)據(jù)挖掘；樸素貝葉斯；貝葉斯網(wǎng)絡(luò)

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1671-7597（2014）02-0043-02

傳統(tǒng)數(shù)據(jù)挖掘分類算法是建立在確定性數(shù)據(jù)的基礎(chǔ)上的，其數(shù)據(jù)集合其屬性特征都是確定的，且樣本的屬性值是準(zhǔn)確無誤的，而現(xiàn)實(shí)生活中由于各種原因?qū)傩酝耆_定的樣本集是很難收集到的，其中必然會有屬性缺失或者偏移的情形，也就是說樣本里有噪聲，當(dāng)這些噪聲多到足以影響所構(gòu)造的分類器的分類精度，我們就不能忽略這些不確定數(shù)據(jù)的存在了。

一般來講，數(shù)據(jù)的不確定性主要表現(xiàn)在以下兩個方面：1）樣本存在不確定性，即樣本具有特定的存在概率，而且一個樣本存在對其他樣本的存在有一定的影響；2）樣本屬性特征值的不確定性，即樣本的屬性特征值不是單一確定的數(shù)值，而是依一定分布特征的一段區(qū)間取值。該分布區(qū)間通常用概率密度函數(shù)PDF或其他分布函數(shù)如均值、方差等表示。在不確定性數(shù)據(jù)分類問題中，我們需要處理的數(shù)據(jù)樣本的屬性值不再是唯一確定的值，而是服從一定分布的一段范圍，通常每一個屬性值都是以符合一定分布的一段區(qū)間范圍用來表示。

隨互聯(lián)網(wǎng)上各領(lǐng)域的數(shù)據(jù)信息的規(guī)模以幾何指數(shù)遞增，然而，如何從數(shù)據(jù)中最大限度獲取有價(jià)值的資源成為重要難題，因此數(shù)據(jù)挖掘技術(shù)的研究成為熱點(diǎn)研究領(lǐng)域。在數(shù)據(jù)挖掘領(lǐng)域，比較成熟的分類算法有：樸素貝葉斯（Naive Bayes）、K近鄰KNN（K-Nearest Neighbors）、決策樹（Decision Tree）等，這些算法各有自己的特點(diǎn)。在對不確定性數(shù)據(jù)進(jìn)行分類的研究中，Jinbo Bi等人提出了一種基于支撐向量機(jī)模型的不確定數(shù)據(jù)分類算法，用不確定數(shù)據(jù)來構(gòu)造分類邊界，得到一個最小化結(jié)構(gòu)風(fēng)險(xiǎn)的分類模型。Smith Tsang等人在構(gòu)建決策樹的過程中融入概率密度函數(shù)，從而使用擴(kuò)展了的決策樹算法解決不確定數(shù)據(jù)分類問題等。因此在本文所研究的不確定性數(shù)據(jù)挖掘中，我們將著重研究使用貝葉斯算法解決不確定數(shù)據(jù)分類問題的性能。

1 貝葉斯網(wǎng)絡(luò)

貝葉斯分類方法具有很強(qiáng)的概率表達(dá)能力，能夠很好的進(jìn)行不確定知識表達(dá)形式和先驗(yàn)知識的檢驗(yàn)，是處理不確定性數(shù)據(jù)的重要方法。貝葉斯網(wǎng)絡(luò)以概率和統(tǒng)計(jì)理論為基礎(chǔ)，已經(jīng)被廣泛應(yīng)用于在處理不確定信息的智能化系統(tǒng)、醫(yī)療診斷、統(tǒng)計(jì)決策、專家系統(tǒng)等領(lǐng)域，表現(xiàn)出貝葉斯算法在不確定性推理方面的優(yōu)良性能特點(diǎn)：1）對于進(jìn)行貝葉斯分類實(shí)驗(yàn)的樣本，可以存在連續(xù)或者離散，或者兩者兼有的屬性值；2）由于在計(jì)算的過程中，貝葉斯分類模型首先得到的是某個樣本屬于各個類別的概率，而后將概率最大值所對應(yīng)的類作為其所屬的類別，因此其類別的判斷是基于計(jì)算后得到的概率最大值，這樣的結(jié)果是相對的而非絕對的；3）用于貝葉斯分類實(shí)驗(yàn)的樣本，分類的結(jié)果并不是依據(jù)其幾個單一屬性決定的，在分類的過程中，樣本的所有屬性都直接或者間接的對分類結(jié)果產(chǎn)生影響。

根據(jù)對特征值間不同關(guān)聯(lián)程度的假設(shè)，貝葉斯網(wǎng)絡(luò)分類器又有以下幾種典型的模型，樸素貝葉斯分類器Naive Bayes、樹增強(qiáng)樸素貝葉斯分類模型（在文中簡稱為TAN，Tree Augmented Naive Bayes）、貝葉斯網(wǎng)絡(luò)擴(kuò)展的Naive Bayes分類模型（在文中簡稱為BAN）等。

樸素貝葉斯分類器是一種基礎(chǔ)的貝葉斯網(wǎng)絡(luò)分類器，具有分類性能穩(wěn)定、準(zhǔn)確率高，計(jì)算過程的時間、空間復(fù)雜度小，易于實(shí)現(xiàn)等優(yōu)點(diǎn)，但這種分類器是建立的理論基礎(chǔ)是用于分類的樣本屬性是條件獨(dú)立的，但是該前提條件在實(shí)際的分類應(yīng)用中通常是不存在的。樣本數(shù)據(jù)的屬性之間很難做到完全相互獨(dú)立，因此在對貝葉斯算法的研究中，人們又提出了樹增強(qiáng)樸素貝葉斯分類器TAN、貝葉斯網(wǎng)絡(luò)擴(kuò)展的樸素貝葉斯分類器BAN等一系列改進(jìn)的貝葉斯網(wǎng)絡(luò)分類器。其中，TAN分類器在樸素貝葉斯分類器的基礎(chǔ)上進(jìn)行了拓展，在TAN模型中，樣本的各個屬性所對應(yīng)的結(jié)點(diǎn)構(gòu)成樹的結(jié)構(gòu)，類變量C是根結(jié)點(diǎn)，是每個屬性結(jié)點(diǎn)的父結(jié)點(diǎn)，每個屬性結(jié)點(diǎn)只能存在類變量和最多一個屬性結(jié)點(diǎn)作為其父結(jié)點(diǎn)。BAN分類器在TAN分類器的基礎(chǔ)上進(jìn)行了拓展，去掉了對屬性結(jié)點(diǎn)父結(jié)點(diǎn)數(shù)量的限制，并且規(guī)定屬性結(jié)點(diǎn)之間可以任意的形式組成貝葉斯網(wǎng)絡(luò)。幾種模型所對應(yīng)的貝葉斯網(wǎng)絡(luò)模型的區(qū)別如下圖所示。

圖1 Naive Bayes模型 圖2 TAN模型 圖3 BAN模型

對于一般的貝葉斯網(wǎng)絡(luò)分類，其原理可以表述如下：首先已知所有類別出現(xiàn)的先驗(yàn)概率，利用貝葉斯的類別判斷公式計(jì)算出在數(shù)據(jù)樣本出現(xiàn)的前提下，其分屬各個不同類別的后驗(yàn)概率，該數(shù)據(jù)樣本所屬的類即為計(jì)算結(jié)果中后驗(yàn)概率的值最大的類別。從結(jié)構(gòu)上看，貝葉斯網(wǎng)絡(luò)是一個有向無環(huán)圖，有向無環(huán)圖結(jié)點(diǎn)代表一個隨機(jī)樣本屬性，結(jié)點(diǎn)之間的弧代表兩個相連接的樣本屬性之間是是有依賴關(guān)系的而非條件獨(dú)立的，若兩個樣本屬性之間沒有弧相連接則說明它們是條件獨(dú)立的。對于有向無環(huán)圖中的每一個結(jié)點(diǎn)X，它與其他代表樣本屬性的其他結(jié)點(diǎn)之間的概率關(guān)系可以用一個條件概率表（文中簡稱為CPT，Conditional Probability Table）來表示。假設(shè)結(jié)點(diǎn)X存在父結(jié)點(diǎn)，CPT中的值為結(jié)點(diǎn)X相對于各個父結(jié)點(diǎn)存在的條件概率。若該結(jié)點(diǎn)沒有父結(jié)點(diǎn)，CPT中的值為所有類別出現(xiàn)的先驗(yàn)概率。貝葉斯網(wǎng)絡(luò)分類模型的運(yùn)行過程分為兩個階段：學(xué)習(xí)階段和推理階段，具體流程描述如下：1）學(xué)習(xí)基于已知的訓(xùn)練樣本集建立的貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)和各樣本屬性結(jié)點(diǎn)的CPT；2）利用貝葉斯公式計(jì)算出在數(shù)據(jù)樣本出現(xiàn)的前提下，其屬于各不同類別的后驗(yàn)概率，取最大值作為其判定類別。endprint

假設(shè)數(shù)據(jù)集合的特征集為，類別集合為 ，k為類別數(shù)，而表示具有m個屬性的樣本實(shí)例，則每個類別出現(xiàn)的概率為先驗(yàn)概率，在已知類別的情況下數(shù)據(jù)樣本出現(xiàn)的概率稱為類結(jié)點(diǎn)的條件概率，而在數(shù)據(jù)樣本出現(xiàn)的前提下，概率為某樣本屬于某個類別的后驗(yàn)概率，是出現(xiàn)的概率，根據(jù)貝葉斯公式：

是類別出現(xiàn)的先驗(yàn)概率，是一個常數(shù)，在實(shí)際的操作中僅對其進(jìn)行歸一化處理，它的值可以通過對訓(xùn)練樣本集中的數(shù)據(jù)進(jìn)行分析而得到，其計(jì)算公式如下：

而類條件概率和的計(jì)算較為困難，其中，它的作用是使某個樣本屬于所有類別的概率總和歸一化。將這些公式應(yīng)用到實(shí)際的分類問題中，設(shè)表示分類所得的類標(biāo)簽。貝葉斯分類器可以表示為：

也就是說，在已知樣本屬性條件的前提下，樣本X的類別為后驗(yàn)概率最大的類別時，分類器可以得到最為精確的預(yù)測結(jié)果。

由于樸素貝葉斯公式假設(shè)樣本屬性之間是條件獨(dú)立的，即，則條件概率的求解公式可以簡化為：

2 實(shí)驗(yàn)

圖4

本文中的實(shí)驗(yàn)使用Weka Waikato Environment for Knowledge Analysis（本文中簡稱為“Weka”）提供的貝葉斯分類工具完成了基于貝葉斯的不確定性數(shù)據(jù)分類。Weka是用Java開發(fā)的一種源代碼開放的數(shù)據(jù)挖掘系統(tǒng)。使用者可以通過對其中算法進(jìn)行改進(jìn)以達(dá)到特定研究的目的，本文使用的是Weka3.6.10版本。Weka的開發(fā)目的在于在數(shù)據(jù)挖掘領(lǐng)域，實(shí)現(xiàn)一個解決分類，回歸、聚類、關(guān)聯(lián)規(guī)則等多種問題的統(tǒng)一模型。它采用統(tǒng)一的數(shù)據(jù)保存格式和結(jié)果輸出格式，從而提高了數(shù)據(jù)挖掘研究過程的效率。我們采用Weka工具軟件來進(jìn)行實(shí)驗(yàn)，探索不用貝葉斯網(wǎng)絡(luò)模型對不確定數(shù)據(jù)集進(jìn)行分類的實(shí)際效果。實(shí)驗(yàn)中所需算法模型的調(diào)用方法如圖4所示。

實(shí)驗(yàn)采用的數(shù)據(jù)是從國際數(shù)據(jù)挖掘領(lǐng)域的標(biāo)準(zhǔn)數(shù)據(jù)集UCI中挑選的數(shù)據(jù)集。從UCI官網(wǎng)下載的原始數(shù)據(jù)集都是一些精確的數(shù)據(jù)，而不是不確定數(shù)據(jù)，為了進(jìn)行實(shí)驗(yàn)，必須先對這些數(shù)據(jù)進(jìn)行預(yù)處理，人為地為數(shù)據(jù)集添加噪音，使其成為不確定性數(shù)據(jù)集合。Weka所要求的數(shù)據(jù)文件的后綴為“.arff”，對此，我們對從UCI官網(wǎng)下載的數(shù)據(jù)集進(jìn)行轉(zhuǎn)換，使其符合weka所要求的數(shù)據(jù)格式，對于訓(xùn)練集和測試集的劃分，本文采用10-fold交叉驗(yàn)證的方式進(jìn)行測試。

表1 實(shí)驗(yàn)數(shù)據(jù)集及結(jié)果

數(shù)據(jù)集 屬性個數(shù) 類別數(shù) 樣本個數(shù) 分類結(jié)果

Chess 36 2 3196 87.58

Chest-Clinic 7 2 1000 81.64

Breast-Cancer 9 2 277 71.26

DNA 60 3 3186 90.11

Nursery 8 4 12960 91.35

通過實(shí)驗(yàn)表明，對于不同的數(shù)據(jù)集，因其數(shù)據(jù)類型，類別數(shù)和樣本集大小的不同，貝葉斯算法的分類準(zhǔn)確率存在差異，然而其總體的分類性能較好。

3 結(jié)束語

本文主要介紹了貝葉斯網(wǎng)絡(luò)的相關(guān)理論不確定數(shù)據(jù)挖掘領(lǐng)域的相關(guān)應(yīng)用，闡述了不同貝葉斯網(wǎng)絡(luò)分類算法的不同，并通過實(shí)驗(yàn)對其分類效果進(jìn)行了測試和分析，使用weka系統(tǒng)，將不確定性數(shù)據(jù)引入到標(biāo)準(zhǔn)數(shù)據(jù)集UCI中，通過測試貝葉斯分類器在屬性個數(shù)、類別數(shù)、樣本個數(shù)不同的數(shù)據(jù)集合上的分類性能，證明貝葉斯分類器在處理不確定性數(shù)據(jù)方面的優(yōu)良性能，后續(xù)實(shí)驗(yàn)中，我們還將考慮多分類器的融合，以期提高分類器的適用范圍和分類精度。

項(xiàng)目基金

本文系南陽市科技計(jì)劃編制項(xiàng)目“數(shù)字化圖書館不確定性數(shù)據(jù)管理研究”（2012RK019）。

參考文獻(xiàn)

[1]周傲英，金澈清，王國仁，李建中.不確定性數(shù)據(jù)管理技術(shù)綜述[J].計(jì)算機(jī)學(xué)報(bào)，2009，32（1）：1-16.

[2]李建中，于戈，周傲英.不確定性數(shù)據(jù)管理的要求與挑戰(zhàn)[J].中國計(jì)算機(jī)學(xué)會通訊，2009，5（4）：6-14.

[3]Nir Friedman.Bayesian network classifiers[J].Machine Learning ，1997，29：131-163.

[4]http：//www.cs.waikato.ac.nz/ml/weka/

[5]周顏軍，王雙成，王輝.基于貝葉斯網(wǎng)絡(luò)的分類器研究[J].東北師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2003，35（2）：21-27.

作者簡介

黃永毅（1975-），男，河南南陽人，南陽醫(yī)專圖書館，講師，碩士，研究方向：管理信息系統(tǒng)、數(shù)據(jù)挖掘。

鈕靖（1979-），男，河南南陽人，南陽醫(yī)專衛(wèi)生管理系，講師，研究方向：衛(wèi)生信息管理、多媒體技術(shù)。

王秋紅（1985-），女，河南南陽人，南陽醫(yī)專衛(wèi)生管理系，碩士。endprint