基于選擇性模式的貝葉斯分類算法

鞠卓亞 王志海

1(北京交通大學計算機與信息技術學院 北京 100044)2(32178部隊 北京 100012)(juzhuoya@bjtu.edu.cn)

在機器學習理論和數據挖掘技術中，分類是一種非常重要的學習方法.已有的分類器構造算法中，基于貝葉斯網絡的分類算法具有堅實的理論基礎、較強的抗噪性能、良好的分類性能和健壯性.其中，樸素貝葉斯分類器(Na?ve Bayes classifier, NB)假設在給定類標的條件下，所有屬性取值之間都是相互獨立的[1].這一假設被稱為“條件獨立假設”，可以大幅降低構造分類器的復雜度，然而現實中屬性之間往往具有一定的依賴關系.因此，許多分類方法在“條件獨立假設”的基礎上，對屬性之間的依賴關系進行了進一步研究，如樹型增廣的樸素貝葉斯分類器(tree augmented Na?ve Bayes classifier, TAN)[2]、超親樹增廣樸素貝葉斯算法(super parent TAN, SP-TAN)[3]、聚合單層依賴分類器(aggregating one-dependence estimators, AODE)[4]、屬性選擇平均單層依賴分類器(attribute selection for averaged one-dependence estimators, ASAODE)[5]、內存約束的選擇性平均多層依賴分類器(memory con-strained selective averagedn-dependence estimators)[6]等，但是，屬性與屬性值所構成的模式在分類問題中的關鍵作用仍未在這些算法中得到足夠的重視.

通常一個實例是由n個“屬性-值”序偶來刻畫的，這種序偶稱之為“項”，則不含缺損值的實例可視為具有n個項的項集，因此數據集可以看作是項集的集合.利用項集這種模式來完成分類任務已有大量研究，并且取得了較好的分類效果.

Meretakis等人在文獻[7]中提出了LB(large Bayes)算法，選擇和組合使用多個長項集(large itemsets)來構建分類器，當選擇的項集長度均為1時，該分類器退化為樸素貝葉斯分類器.該分類算法有效提升了樸素貝葉斯分類器的分類精度.

Dong等人在文獻[8]中提出了顯現模式的概念，它是指支持度在不同數據集上發生顯著變化的項集，可用于構建高精度的分類器.文獻[9]提出的基于顯現模式的貝葉斯分類算法(Bayesian classi-fication based on emerging patterns， BCEP)，理論基礎是Meretakis等人提出的“長模式減弱屬性獨立性”的原理，它將顯現模式分解為相互聯系的子模式以近似估計條件概率，削弱了樸素貝葉斯分類算法屬性條件獨立的假設限制.這種方法比聚合顯現模式的分類方法精度更高，但仍未充分利用顯現模式的區分能力，僅是將顯現模式作為一般項集進行處理.

文獻[10]給出了基于跳躍顯現模式(jumping emerging patterns， JEP)的分類器.跳躍顯現模式是指從非目標類到目標類增長率為無窮大的顯現模式，它能夠捕獲不同類別數據之間的關鍵差異，聚合跳躍顯現模式可以構建具有更強分類性能的分類器.如果數據集的每個類別都有多個跳躍顯現模式，則該分類器的性能會非常好.然而，在現實世界的分類問題中，一些數據類別可能只含有很少甚至不含支持度達到某一合理閾值(如1%)的跳躍顯現模式，這種情況難以利用跳躍顯現模式進行分類.

文獻[11]考慮平衡跳躍顯現模式的高分類能力和其在數據集上的覆蓋程度，使用跳躍顯現模式集合描述待分類對象，其中，使得最小覆蓋集的取值最小的跳躍顯現模式集合對應的類別，即為待分類實例的類別.但其求解近似最小化覆蓋集的方法，可能會對分類精度產生不利影響.

文獻[12]提出了基于顯露模式的數據流貝葉斯分類模型EPDS(Bayesian classifier algorithm based on emerging pattern for data stream).該模型使用混合森林結構維護內存中事務的項集，并采用一種快速的模式抽取機制提高算法速度，能夠在數據流分類中取得較高精度，但主要適用于二值分類問題.

文獻[13]提出了一種有效的基于模式的貝葉斯數據流分類器(pattern-based Bayesian classifier for data stream, PBDS).該分類器采用數據驅動的懶惰學習策略來發現每個測試實例的局部頻繁模式，將貪婪搜索和最小描述長度與貝葉斯網絡結合以評估提取的模式.盡管該分類器使用了一種壓縮樹存儲結構，但其時間開銷仍然可觀.

關聯分類也是利用項集模式分類的一種重要方法.關聯挖掘技術能夠在大型數據庫中搜索頻繁出現的模式，而頻繁模式與對應的相關規則表征了屬性與類別之間的聯系，近年來出現了許多基于關聯規則的分類方法[14].Li等人提出了基于多個分類關聯規則的分類算法(classification based on multiple class-association rules, CMAR)[15].該算法基于改進的FP(frequent pattern)-growth進行關聯規則挖掘，通過基于權重的多個強關聯規則來判定新實例的類別.但該算法內存消耗過大，不適合高維、大型的數據庫.張明衛等人給出了一種大數據環境中分布式關聯分類器構建算法，改進了關聯分類算法處理不平衡數據的性能缺陷，但該方法需設定的閾值“空間支持度”對算法的影響較大，而通過人工嘗試的方式又會增加時間開銷[16].

在不同數據子集上訓練得到特定的模式，充分考量它們的區分能力，有助于進一步將其應用在分類器的構建過程中.選擇性模式能夠刻畫數據特征，然而當某種類別數據數量很少甚至不含選擇性模式時，將難以利用選擇性模式進行分類.實際問題中，屬性之間的依賴關系往往是復雜不清的，通過選擇性模式進行分類可以削弱樸素貝葉斯分類算法屬性條件獨立的假設限制，而通過研究選擇性模式之外屬性之間的依賴關系，既能降低只依賴選擇性模式進行分類的風險，又有助于提升分類器的分類效果.因此，在挖掘出選擇性模式之后，應進一步探索模式所包含的屬性與其他屬性之間的依賴關系，同時兼顧處理高維數據時的復雜程度，以構建更精準高效的分類器.選擇性模式是指利用特定的模式(如顯現模式、跳躍顯現模式等)，將屬性劃分為屬于該模式和不屬于該模式2類，分別考慮這2類屬性對分類結果的影響.本文在深入研究屬性間依賴關系對分類結果影響的基礎上，提出了基于選擇性模式的貝葉斯分類算法.鑒于模式的數量眾多且存在屬性冗余的情況，本文通過挖掘發揮主要作用的特定模式作為分類依據；而對這些模式之外的屬性，通過建立貝葉斯網絡來分析其依賴關系，從而構建更為恰當的分類模型.

本文首先介紹利用選擇性模式分類的過程，給出挖掘特定模式的方法，分析削弱樸素貝葉斯算法屬性條件獨立假設限制的方法.之后介紹基于選擇性模式的貝葉斯分類算法，并通過實驗驗證了所提算法的有效性.

1 定義與背景

分類任務就是根據給定的訓練數據集建立分類器，用于預測實例的類標.基于選擇性模式進行分類，就是通過挖掘分析，尋找從非目標類到目標類具有高增長率的特定模式，并分析這些模式所包含的屬性與其他屬性之間的依賴關系，據此構建分類器.

1.1 相關概念

假定一個實例X=((A1,a1),(A2,a2),…,(An,an))，其中，A1,A2,…,An為屬性，a1,a2,…,an為屬性值.屬性可以是離散的或是連續的.對于離散型屬性，假設所有可能的值都映射到一個連續正整數集.對于連續型屬性，假設它的值域范圍被離散化為區間，這些區間也能夠映射為連續正整數.稱每個“屬性-正整數值”序偶為一個“項”.

令C={c1,c2,…,cm}為類標的有限集合，每個實例X，都有一個類標cX∈C.分類器是一個函數，自某個實例X映射到C，它將類標分配給類別未知的實例.記S為數據集D中所有項的集合.項的集合I稱為“項集”，被定義為S的子集.

定義1.支持度.數據集D中項集I的支持度定義為

其中，countD(I)表示數據集D中包含項集I的實例的數目，|D|是數據集D中實例的總數.

定義2.增長率.給定數據集D，將其劃分為數據子集D1和D2，即D1∩D2=?，D1∪D2=D.項集I從數據子集D1到數據子集D2的增長率Growth(I,D1,D2)定義為

(1)

假定數據子集D1和D2分別表示類別為C1和C2類的數據集，則增長率刻畫了項集I從類C1到類C2支持度變化的顯著程度.

通過挖掘在某一數據類別中頻繁出現、在另一數據類別中很少出現的項集來確定用于分類的特定模式.這些模式是在不同數據類別上支持度有明顯變化的項集，它們呈現了區分不同數據集類別的知識.模式的支持度決定其作用范圍，增長率決定其分類預測能力.類標Ci的模式I被看作是Ci的區別特征，它在Ci的支持度估計了給定類標Ci時出現該模式的概率.

1.2 模式的挖掘

模式由數據集中頻繁出現或強相關的一組特征、子序列、子結構等所組成.模式是數據的一種壓縮表示，它能夠代表數據集的本質和重要特性，是許多重要數據挖掘任務的基礎.比如，頻繁模式可用于關聯規則的發現和關聯式分類，非頻繁模式或非正常模式可用于孤立點檢測，辨別性模式可直接用于分類[17-18]等.模式發現的主要目的是發現數據的主要特征，并使用它們表示和區分不同類別數據.

Dong等人[8]利用集合閉區間的知識用于挖掘顯現模式，提出了用于挖掘顯現模式的邊界算法BORDER_DIFF，本文利用該邊界算法挖掘用于分類的特定模式.

實際上，每個數據集對應的用于分類的模式數目眾多，在分類問題中也并不需要使用所有的模式，只需要那些起決定性作用的少數模式就可以達到很好的分類效果.文獻[9]給出了一種篩選模式的方法，只采用滿足3個特征條件的模式用于分類：

1) 具有很高的增長率，以保證很高的區分能力；

2) 對目標集(范圍在1%內)有足夠大的支持度，確保在訓練數據集上有足夠的覆蓋率，確保抗噪聲能力強；

3) 包含在代表模式集合邊界的左邊界中.任何邊界項集的真子集都不在挑選范圍.

如果可以使用較少的屬性來區分2個數據類別，則增加更多的屬性并不能為分類做出貢獻，在更壞的情況下還有可能引入噪聲.具體來說，假設模式ei在類別Ci上覆蓋了實例集合COVei，模式fi在類別Ci上覆蓋了實例集合COVfi.如果COVfi是COVei的子集，即ei的增長率和支持度比fi的要大，那么COVfi就無法提供更多有用的信息.由于存在這種情況，滿足上述3個特征條件的模式可能存在冗余.去除冗余的模式和噪音，有助于加速分類、提升分類精度.因此，在訓練階段，每個類別的完整模式被挖掘完之后，執行這種基于數據類別覆蓋概念的剪枝.

1.3 屬性依賴關系分析

已知每個實例均是由一個n維特征(屬性)向量X=(a1,a2,…,an)來描述的，這里ai表示第i個屬性Ai的取值.假設訓練實例共有m個不同的類標值，即

Values(C)={c1,c2,…,cm}.

給定一個未知類標值的數據實例X，則分類任務就是如何在已知實例X的情況下，計算后驗概率最大(maximum a posteriori， MAP)的類標值作為其預測類別，即分類器將未知類標的實例X歸屬到類標ck的類，當且僅當P(ck|X)≥P(ci|X)，其中?i，1≤i≤m且i≠k.

根據Bayes定理可知：

從計算上講，對于所有的類標值的后驗概率P(ck|X)來說，由于分母P(X)均是相同的，所以，要使式(2)取得最大值，只需要保證分子P(X|ck)×P(ck)取得最大值即可.

根據給定的訓練集，難以直接估算P(X|ck).為了實現有效估算，不同的分類算法給出了不同的計算方法：

1) 簡單樸素貝葉斯分類器[1].假設給定類標取值的條件下，各個屬性取值之間相互獨立，此時式(3)就可以表達為

其中，P(ai|ck)根據訓練數據進行估算.

2) 樹型增廣的樸素貝葉斯分類器[2].通過計算互信息，建立了表達屬性之間依賴關系的樹結構，由此計算給定實例分到某一類別的概率.

3) 懶惰貝葉斯規則(lazy Bayes rules, LBR)[19].一種懶惰式學習方式，挑出屬性集合Ai，其余屬性被認為是相互條件獨立的，每個屬性依賴于分類屬性和集合Ai中的屬性.

4) 聚合單層依賴分類器[4].建立了表達屬性依賴關系的樹結構，這個樹結構只有一層，如圖1所示.

Fig. 1 Dependencies among attributes in one layer Bayesian network圖1 單層貝葉斯網絡屬性間依賴關系

除了依賴于類屬性ck之外，每個屬性ai依次作為其他屬性的父節點，除此之外屬性之間不再有任何依賴關系.由此建立與屬性個數相同數量的分類器，以這些分類器預測的平均值作為某個實例分類的最終預測值，此時式(3)就可以表達為:

(4)

其中，G={i|1≤i≤n∧F(ai)≥m},F(ai)是屬性值包含ai的訓練實例數目，用參數m限制，以達到進行條件概率估計所需的支持度[4].這種方法利用了屬性間所有的依賴關系，通過計算所有模型的平均值來解決無法呈現多個相互依賴關系的問題.

2 基于選擇性模式的貝葉斯分類算法

本節提出了基于選擇性模式的分類算法，選擇具有高區分能力的特定模式用于分類，同時，基于貝葉斯網絡深入分析特定模式所包含的屬性與其他屬性間的依賴關系.訓練階段，利用訓練數據集挖掘用于分類的特定模式；測試階段，根據測試實例所包含的模式，將測試實例的屬性分為2部分，即屬于該特定模式，或不屬于該特定模式，之后構建屬性之間的依賴關系，形成具體的分類器.

假設數據集D具有n個屬性，每個訓練實例表示為X=(a1,a2,…,an)，其中ai(1≤i≤n)是實例X在第i個屬性的取值.訓練實例的類別屬于類別C={c1,c2,…,cm}中的一個.下面用c來表示實例的類別.根據貝葉斯公式，X的類別為c的概率P(c|X)可表示為

基于選擇性模式的分類算法，將模式所包含的屬性作為整體考慮.給定類別c，假定模式所包含的屬性與其他屬性相互條件獨立，即：

P(c|a1,a2,…,an)∝P(c)P(a1,a2,…,ai|c)×
P(ai+1,…,an|c)=P(c|a1,a2,…,ai)×
P(a1,a2,…,ai)P(ai+1,…,an|c),

(5)

其中，{a1,a2,…,ai}代表該模式所包含的屬性.

由式(5)可知，對于所有類值的后驗概率P(ck|a1,a2,…,an)來說，P(a1,a2,…,ai)均相同，因而只需要關注屬性值集合{a1,a2,…,ai}對后驗概率的影響以及屬性間的依賴關系對分類結果的影響.

2.1 模式分類能力的刻畫

模式分類能力的強弱在于是否具有明顯的區分性，并能夠以一組特征、子序列或子結構等形式表示出不同類別數據間的不同特點.選擇性模式是指利用特定的模式(如顯現模式、跳躍顯現模式等)，將屬性劃分為屬于該模式和不屬于該模式2類，分別考慮這2類屬性對分類結果的影響.

假定項集e所包含的屬性集合為{a1,a2,…,ai}，是從類別為c′的數據集到類別為c的數據集增長率為Growth(e,c′,c)的特定模式，當待分類實例包含e時，此實例屬于類c的概率為P(c|a1,a2,…,ai)，簡記為P(c|e)，則：

根據定義1有：

根據式(1)，則有:

由式(6)可知，包含模式e的實例被分到類c的概率，不僅與e從類c′到類c的增長率有關，也取決于類值為目標類c和非目標類c′的實例數目之比，即當目標類和非目標類包含的實例數目相差懸殊時，會對分類結果產生較大影響.具體來說，當目標類包含的實例數目遠大于非目標類實例數目時，分類結果主要取決于先驗概率P(c)；當目標類包含的實例數目遠小于非目標類實例數目時，分類結果則取決于e從類c′到類c的增長率Growth(e,c′,c)和P(c).

下面分別介紹基于選擇性模式的分類算法如何利用模式的分類能力以及如何處理屬性之間的依賴關系.

2.2 基于選擇性模式的樸素貝葉斯分類算法

樸素貝葉斯分類算法假定給定類標時所有屬性之間相互條件獨立，本文提出的基于選擇性模式的樸素貝葉斯分類算法(Na?ve Bayes classification based on selective patterns， NBSP)，則是將特定模式中的屬性作為整體處理，并假定該模式所包含的屬性與其他屬性之間相互條件獨立，且該模式之外的屬性之間相互條件獨立.

設項集e所包含的屬性集合為{a1,a2,…,ai}，是增長率為Growth(e,c′,c)的特定模式，將e涉及的屬性作為整體考慮.E為所有模式的集合.根據式(5)和樸素貝葉斯定理，由此形成的貝葉斯網絡滿足：

(7)

將模式的分類能力應用到貝葉斯網絡中，即將式(6)代入式(7)，得到：

聚合所有模式對應的分類情況，得到基于選擇性模式的樸素貝葉斯分類算法采用的概率預測公式：

(8)

式(8)集成了所有模式的分類能力.在對測試實例進行分類時，實例的預測類別為使式(8)取值最大的類.

下面給出基于選擇性模式的樸素貝葉斯分類算法.

算法1.NBSP(instance,m,E).

輸入：待分類實例instance、類別數量m、模式集合E;

輸出：instance的預測類別分布probs.

① FORi=0 tom

②probs[i]←0;

③ FORj=0 toE[i].size()

④ Itemsete=(Itemset)E[i].elementAt(j);

⑤ IFinstance包含e

⑥ 計算P(i|attributes ine);

⑦ 計算PNB(attributes not ine|i);

⑧ 計算P(a1,a2,…,ai),其中a1,a2,…,ai∈e;

⑨p←P(i|instance);

⑩ END IF

算法1中，行④從模式集合E中，取出類別i上的第j個模式e；行⑤判斷待分類實例是否包含模式e；行⑥使用式(6)計算e所包含的屬性在類別i上的后驗概率；行⑦利用樸素貝葉斯分類器計算e之外其他屬性在類別i上的條件概率；行⑧計算e本身發生的概率；行⑨利用以上3部分概率計算包含e的實例instance類別為i的概率p.行聚合所有分類器的分類能力.行至當基于選擇性模式的樸素貝葉斯分類器未能進行有效分類時，使用樸素貝葉斯分類器計算實例的概率分布.

2.3 基于選擇性模式的單層依賴分類算法

基于選擇性模式的樸素貝葉斯分類算法(NBSP)假定選擇性模式的屬性與其他屬性之間的依賴關系是相互獨立的，為了進一步減弱這種獨立性假設對分類結果的影響，基于選擇性模式的聚合單層依賴分類算法(aggregate one dependence classification based on selective patterns, AODSP)，將特定模式中的屬性作為整體來處理，但假定該模式之外的屬性并非完全條件獨立，而是存在一定的依賴關系.

由于屬性間的依賴關系并不明確，基于選擇性模式的聚合單層依賴分類算法考慮了所有的依賴關系.假定特定模式之外的屬性間的依賴關系滿足單層貝葉斯樹結構(如圖1所示)，即每個屬性依次作為其他屬性的父節點，剩余屬性作為子節點依賴于該屬性，除此之外，屬性之間不再有任何依賴關系.將由此產生的多個分類器計算出的分類概率取平均值，作為最終的實例分類概率.這種方式使用了屬性間所有的依賴關系，在依賴關系復雜不清時，既可以避免花費過多時間分析屬性之間的依賴關系，又兼顧了屬性間依賴關系的所有可能.

設項集e所包含的屬性集合為{a1,a2,…,ai}，是從類c′到類c的增長率為Growth(e,c′,c)的特定模式，將e涉及的屬性作為整體考慮.E為所有模式的集合.由式(4)可知，模式e之外的屬性之間的條件概率滿足：

其中，H={j|i+1≤j≤n∧F(aj)≥m},F(aj)是屬性值包含aj的訓練實例數目，用參數m限制，以達到進行條件概率估計所需的支持度[4]，則：

P(c|a1,a2,…,an)∝P(c|a1,a2,…,ai)×
P(a1,a2,…,ai)P(ai+1,…,an|c)∝
P(c|a1,a2,…,ai)P(a1,a2,…,ai)×

將模式的分類能力應用到貝葉斯網絡中，即將式(6)代入式(9)，并聚合所有模式的分類情況，得到基于選擇性模式的聚合單層依賴分類算法采用的概率預測公式：

(10)

式(10)集成了所有模式的分類能力，并且進一步綜合考慮了模式之外屬性間的依賴關系.在對測試實例進行分類時，實例的預測類別為使式(10)取值最大的類.

下面給出基于選擇性模式的聚合單層依賴分類算法.

算法2.AODSP(instance,m,E).

輸入：待分類實例instance，類別數量m，模式集合E;

輸出：instance的預測類別分布probs.

① FORi=0 tom

②probs[i]←0；

③ FORj=0 toE[i].size()

④ Itemsete=(Itemset)E[i].elementAt(j);

⑤ IFinstance包含e

⑥ 計算P(i|attributes ine);

⑦ 計算PAODE(attributes not ine|i);

⑧ 計算P(a1,a2,…,ai),其中a1,a2,…,ai∈e;

⑨p←P(i|instance);

⑩ END IF

算法2中，行④從模式集合E中，取出類別i上的第j個模式e；行⑤判斷待分類實例是否包含模式e；行⑥使用式(6)計算e所包含的屬性在類別i上的后驗概率；行⑦利用聚合單層依賴分類器計算e之外其他屬性在類別i上的條件概率；行⑧計算e本身發生的概率；行⑨利用以上3部分概率計算包含e的實例instance，類別為i的概率p.行聚合所有分類器的分類能力.行至當基于選擇性模式的單層貝葉斯分類器未能進行有效分類時，使用聚合單層依賴分類器計算實例的概率分布.

3 實 驗

為驗證本文提出的基于選擇性模式的樸素貝葉斯分類算法和基于選擇性模式的聚合單層依賴分類算法的準確性，采用UCI機器學習庫[20]和Weka[21]提供的共計10個數據集作為實驗數據集，并將實驗結果與C4.5算法[22]、k近鄰算法[23]、支持向量機算法(SVM)[24]、基于多個分類關聯規則的分類算法(CMAR)、樸素貝葉斯算法(NB)、聚合單層依賴分類器(AODE)、基于顯現模式的貝葉斯分類算法(BCEP)等分類模型的錯誤率進行比較.

3.1 實驗環境

本實驗在Weka-3-6-10[21]軟件(Waikato environ-ment for knowledge analysis)中設計實現，運行環境的CPU為3.40 GHz，內存為8 GB，操作系統是Windows 7.表1給出了實驗所采用的10個數據集的信息摘要.本文所提出的分類算法基于選擇性模式，需要選擇在目標類與非目標類上支持度變化較大的模式用于分類，因此主要選擇類值為2個或者3個的數據集進行考察.同時，為了驗證算法在不同數據維度下的準確率，選擇了屬性數目各異的數據集，屬性數范圍為4～216個.

Table 1 Summary of Datasets表1 實驗數據集信息摘要

3.2 錯誤率分析

本文考慮的是基于模式的分類問題，即可處理的實例屬性為離散型，因此首先對數據集進行屬性離散化的預處理.對于數值型屬性，使用文獻[25]提供的多區間離散方法進行處理.實驗采用10重交叉驗證統計分類結果的錯誤率，以評價各分類算法.

實驗在Weka系統中進行了5次10重交叉驗證，為了使劃分的數據子集更加具有隨機性，實驗中設定隨機種子參數依次為1,2,3,5,7，實驗結果為這5次分類結果的平均值.

本文提出的基于選擇性模式的樸素貝葉斯分類算法(NBSP)基于樸素貝葉斯分類器(NB)構建，基于選擇性模式的聚合單層依賴分類算法(AODSP)采用了聚合單層貝葉斯分類算法(AODE)的思路來處理顯現模式之外其他屬性之間的依賴關系，而基于顯現模式的貝葉斯分類算法(BCEP)是將顯現模式與貝葉斯網絡結合的一種方法，因此選取NB,AODE和BCEP為參照對象.

此外，決策樹分類算法C4.5、k近鄰分類器(kNN)、支持向量機分類算法(SVM)、基于多個分類關聯規則的分類算法(CMAR)都是具有較高分類精度的經典分類器，實驗選取了這些基于不同原理的分類器作為參照對象.

表2為C4.5,kNN,SVM,CMAR,NB,AODE,BCEP,NBSP和AODSP在10個數據集上分類的錯誤率，錯誤率最低的用粗體表示.

由表2可知，在本文所選的10個數據集上，基于選擇性模式的聚合單層依賴分類算法(AODSP)的平均錯誤率最低.根據實驗可以得到5個結論：

1) 與聚合單層依賴分類器(AODE)相比，基于選擇性模式的聚合單層依賴分類算法(AODSP)在6個數據集上取得更低的錯誤率，在1個數據集上取得相同的錯誤率，在全部10個數據集上具有更低的平均錯誤率，降低了4.29%.與基于選擇性模式的樸素貝葉斯分類算法(NBSP)相比，基于選擇性模式的聚合單層依賴分類算法(AODSP)在8個數據集上取得更低的錯誤率，在1個數據集上取得相同的錯誤率，在全部10個數據集上具有更低的平均錯誤率.

2) 與樸素貝葉斯分類器(NB)相比，基于選擇性模式的樸素貝葉斯分類算法(NBSP)在6個數據集上取得更低的錯誤率，在2個數據集上取得相同的錯誤率，在全部10個數據集上具有更低的平均錯誤率，降低了1.65%.結合1)的分析可知，利用選擇性模式用于分類有助于提升分類器精度.

3) 在bupa數據集上，基于選擇性模式的樸素貝葉斯分類算法(NBSP)、基于選擇性模式的聚合單層依賴分類算法(AODSP)的錯誤率與樸素貝葉斯分類器(NB)、聚合單層依賴分類器(AODE)的錯誤率均相同.通過對實驗情況分析得知，由于無論如何設置支持度參數，基于選擇性模式的樸素貝葉斯分類算法(NBSP)、基于選擇性模式的聚合單層依賴分類算法(AODSP)均未能挖掘出有效的用于分類的特定模式，這種情況下它們已分別退化為樸素貝葉斯分類器(NB)和聚合單層依賴分類器(AODE).

4) 在labor數據集上，基于選擇性模式的聚合單層依賴分類算法(AODSP)取得了最低的錯誤率.labor數據集類別為2類，包含缺損值.基于選擇性模式的聚合單層依賴分類算法(AODSP)，需要選擇在目標類與非目標類上支持度變化較大的模式用于分類，因此在二值分類問題上的分類效果更好；在數據集稀疏的情況下，屬性之間的依賴關系難以尋找，但由于基于選擇性模式的聚合單層依賴分類算法(AODSP)使用了屬性間所有的依賴關系，在依賴關系復雜不清時，既可以避免花費過多時間處理分析屬性之間的依賴關系，又兼顧了屬性間依賴關系的所有可能，因而能夠在labor數據集上取得較好的分類效果.

5) 在數據集稀疏、不易挖掘選擇性模式的情況下，如labor和supermarket數據集，通過研究非選擇性模式之間屬性的依賴關系，有助于獲得較高準確率.當可以挖掘足夠的選擇性模式時，通過分析非選擇性模式屬性之間的依賴關系，分類器準確率的提升并不明顯.

Table 2 Comparison of Error Rates of these 9 Algorithms表2 9種算法錯誤率比較 %

本文采用Dem?ar[26]提出的方法，對樸素貝葉斯(NB)、聚合單層依賴分類器(AODE)、基于顯現模式的貝葉斯分類算法(BCEP)、基于選擇性模式的樸素貝葉斯分類算法(NBSP)和基于選擇性模式的聚合單層依賴分類算法(AODSP)等5種基于貝葉斯網絡的分類器在10個數據集上的分類性能進行顯著性檢驗，其中顯著性水平為0.05，如圖2所示.可以看出，基于選擇性模式的聚合單層依賴分類算法(AODSP)的準確率排名第一，與聚合單層依賴分類器(AODE)相比有較大提升.同樣，與樸素貝葉斯分類算法(NB)相比，基于選擇性模式的樸素貝葉斯分類算法(NBSP)的分類準確率排名更好.

Fig. 2 Critical difference diagram for different classifiers on the 10 datasets圖2 5種分類器在10個數據集上的Critical Difference圖(α=0.05)

實驗發現，不同的支持度對分類結果有較大影響，只有符合一定增長率和支持度的模式才能被采納用于分類.對于不同的數據集、不同的分類算法，均采用相同的支持度等參數，可能無法充分展現其分類效果，也并不是評價某種分類方法的最佳方式.因此，需要進一步探索在具體環境中模式的選取標準，以充分利用其分類能力.

3.3 參數分析

模式在不同類別上的支持度，決定了其分類能力的強弱.在構建分類器的過程中，支持度的選擇會對挖掘出的模式數量產生巨大影響，從而進一步影響分類結果.

表3和表4分別給出了基于選擇性模式的聚合單層依賴分類算法(AODSP)在iris數據集和supermarket數據集上，設置6組不同支持度參數時對應的分類錯誤率.其中，Support1和Support2分別表示項集在非目標類和目標類上滿足的支持度,S的取值表示5次實驗使用的隨機種子，Mean表示5次實驗的平均值.

Table 3 Error Rates of AODSP on iris with Respect to Different Supports表3 AODSP算法在iris上不同支持度的分類錯誤率 %

Table 4 Error Rates of AODSP on supermarket with Respect to Different Supports表4 AODSP算法在supermarket上不同支持度的分類錯誤率 %

可以看出，不同的支持度對分類結果有較大影響.當支持度設置過高時，無法挖掘出可用于分類的特定模式，基于選擇性模式的聚合單層依賴分類算法(AODSP)退化為聚合單層依賴分類器(AODE)；當支持度設置太低時，挖掘出的模式過多，出現了過擬合問題，最終損害了分類結果.此外，基于選擇性模式的聚合單層依賴分類算法(AODSP)在iris數據集和supermarket數據集上取得最佳分類效果時，對應的支持度并不相同.說明針對不同數據集，具備良好區分能力的模式滿足的支持度不盡相同，而這與數據集本身的屬性特點密切相關.因此，針對不同數據集的特點，需要選取不同的支持度參數以挖掘用于分類的特定模式.

4 結束語

本文提出了2種基于選擇性模式區分能力的貝葉斯分類算法.第1種分類算法將特定模式與樸素貝葉斯分類方法結合，以減弱樸素貝葉斯網絡中的屬性條件獨立假設限制；第2種分類算法則將特定模式與聚合單層依賴分類器結合，利用其處理屬性依賴關系的方法，在減弱屬性條件獨立假設限制的同時，進一步平衡了模式內外屬性之間的依賴關系.

實驗結果表明：充分挖掘模式的分類能力，研究削弱樸素貝葉斯算法屬性條件獨立假設限制的方法，分析選擇性模式內外屬性之間的依賴關系，構造基于選擇性模式區分能力的貝葉斯分類算法，可以實現良好的分類效果，并能夠在某些數據集上取得最低錯誤率，驗證了本文所提算法的正確性和合理性.

本文基于“屬性-值”序偶構成的特定模式，將屬性劃分為包含在特定模式內和不在特定模式內2類，并基于貝葉斯網絡深入分析2類屬性的依賴關系，削弱了樸素貝葉斯算法屬性條件獨立假設限制，提出了基于選擇性模式的貝葉斯分類算法.通過實驗分析可知:與基準算法NB和AODE相比，所提算法NBSP和AODSP的分類錯誤率明顯降低，說明了充分利用模式的分類能力，恰當處理模式內外屬性之間的依賴關系，能夠有效提升分類精度.下一步工作將針對不同數據集的特點，研究如何選取恰當的支持度參數以挖掘用于分類的特定模式.