基于貝葉斯的不確定數(shù)據(jù)挖掘

黃永毅+鈕靖+王秋紅

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

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

中圖分類號：TP311 文獻標識碼：A 文章編號：1671-7597（2014）02-0043-02

傳統(tǒng)數(shù)據(jù)挖掘分類算法是建立在確定性數(shù)據(jù)的基礎上的，其數(shù)據(jù)集合其屬性特征都是確定的，且樣本的屬性值是準確無誤的，而現(xiàn)實生活中由于各種原因?qū)傩酝耆_定的樣本集是很難收集到的，其中必然會有屬性缺失或者偏移的情形，也就是說樣本里有噪聲，當這些噪聲多到足以影響所構(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)上各領域的數(shù)據(jù)信息的規(guī)模以幾何指數(shù)遞增，然而，如何從數(shù)據(jù)中最大限度獲取有價值的資源成為重要難題，因此數(shù)據(jù)挖掘技術的研究成為熱點研究領域。在數(shù)據(jù)挖掘領域，比較成熟的分類算法有：樸素貝葉斯（Naive Bayes）、K近鄰KNN（K-Nearest Neighbors）、決策樹（Decision Tree）等，這些算法各有自己的特點。在對不確定性數(shù)據(jù)進行分類的研究中，Jinbo Bi等人提出了一種基于支撐向量機模型的不確定數(shù)據(jù)分類算法，用不確定數(shù)據(jù)來構(gòu)造分類邊界，得到一個最小化結(jié)構(gòu)風險的分類模型。Smith Tsang等人在構(gòu)建決策樹的過程中融入概率密度函數(shù)，從而使用擴展了的決策樹算法解決不確定數(shù)據(jù)分類問題等。因此在本文所研究的不確定性數(shù)據(jù)挖掘中，我們將著重研究使用貝葉斯算法解決不確定數(shù)據(jù)分類問題的性能。

1 貝葉斯網(wǎng)絡

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

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

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

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

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

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

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

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

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

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

2 實驗

圖4

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

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

表1 實驗數(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ù)據(jù)集，因其數(shù)據(jù)類型，類別數(shù)和樣本集大小的不同，貝葉斯算法的分類準確率存在差異，然而其總體的分類性能較好。

3 結(jié)束語

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

項目基金

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

參考文獻

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

[2]李建中，于戈，周傲英.不確定性數(shù)據(jù)管理的要求與挑戰(zhàn)[J].中國計算機學會通訊，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)絡的分類器研究[J].東北師范大學學報：自然科學版，2003，35（2）：21-27.

作者簡介

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

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

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