基于貝葉斯的不確定數據挖掘

黃永毅+鈕靖+王秋紅

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

關鍵詞 不確定性數據；數據挖掘；樸素貝葉斯；貝葉斯網絡

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

傳統數據挖掘分類算法是建立在確定性數據的基礎上的，其數據集合其屬性特征都是確定的，且樣本的屬性值是準確無誤的，而現實生活中由于各種原因屬性完全確定的樣本集是很難收集到的，其中必然會有屬性缺失或者偏移的情形，也就是說樣本里有噪聲，當這些噪聲多到足以影響所構造的分類器的分類精度，我們就不能忽略這些不確定數據的存在了。

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

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

1 貝葉斯網絡

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

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

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

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

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

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

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

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

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

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

2 實驗

圖4

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

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

表1 實驗數據集及結果

數據集 屬性個數 類別數 樣本個數 分類結果

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

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

3 結束語

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

項目基金

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

參考文獻

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

[2]李建中，于戈，周傲英.不確定性數據管理的要求與挑戰[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]周顏軍，王雙成，王輝.基于貝葉斯網絡的分類器研究[J].東北師范大學學報：自然科學版，2003，35（2）：21-27.

作者簡介

黃永毅（1975-），男，河南南陽人，南陽醫專圖書館，講師，碩士，研究方向：管理信息系統、數據挖掘。

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

王秋紅（1985-），女，河南南陽人，南陽醫專衛生管理系，碩士。endprint