一種面向數據流貝葉斯分類的顯露模式挖掘方法

李志杰，劉基旺，廖旭紅，江華

（湖南理工學院信息科學與工程學院，岳陽 414006）

0 引言

基于模式的數據流貝葉斯分類方法，利用事務中項之間的相互關系計算貝葉斯聯合概率，是一種有效的數據挖掘模型［1-2］。然而，現有的頻繁模式挖掘算法面向事務數據流，與實際應用場景不完全吻合。大量的關系表型數據需要轉換為帶類值約束的事務數據流，才能用作有監督學習的訓練數據［3-4］。

數據流本質上是非平穩的，除了有用信息外，大部分是一些無用的冗余信息，往往還包含噪聲。然而，如果從原始數據流中挖掘頻繁模式，則可以清除冗余信息和噪聲的影響，比單個項值包含更多的信息［5］。不過，直接挖掘高密度數據流頻繁模式，常常會產生大量超過需求數量的頻繁模式。因此，實際應用中改為挖掘頻繁閉合模式，它是頻繁模式的無損壓縮［6］。

挖掘頻繁閉合模式用于數據流分類，這種模式必須帶有類標約束才有意義［7］。在挖掘頻繁閉合模式之前，大量的關系表型數據集要轉換成帶類值約束的事務數據集，這種預處理是批量進行的。文獻［8］等開發的挖掘事務數據集閉合頻繁項集算法，不適用于關系表型數據集的批量挖掘，需要增加預處理環節。

影響貝葉斯模型分類性能的的另一重要因素在于，大多數基于模式的貝葉斯分類器沒有綜合考慮模式在各個類數據集中的支持度，僅僅只計算了模式在目標類數據集中的支持度［9］。這樣的模式挖掘方式難以進一步提升貝葉斯分類模型的性能［10］。

本文基于IncMine［5］算法，提出一種面向數據流貝葉斯分類的顯露模式挖掘方法EPBIM，用于數據流貝葉斯分類。MOA 平臺上的實驗結果驗證了本文提出方法的有效性。

1 相關工作

1.1 頻繁項集與頻繁閉合項集

定義1 事務型數據。設A={a1，a2，…，an}表示屬性集，項為屬性的整型取值。一個事務是項的集合，其中，項集的長度不大于屬性集長度。每個事務只包含每個屬性的最多一個項。事務型數據由多個事務Tid組成。

定義2 頻繁項集。假設一個數據集最小支持度閾值為σ，如果項集在數據集中的支持度大于σ，則稱之為頻繁項集。

定義3 頻繁閉合項集。假設X是頻繁項集，Y是X的任一超項集。如果對于所有的Y，其支持度均低于X的支持度，則稱X為頻繁閉合項集。

定義4 關系表型數據。對于關系表型數據的條件屬性值，本文采用“屬性名∶屬性值∶類別值”格式替換后，再掃描數據集得到各個項值id，構成事務型數據。帶類標屬性值與項存在一個映射關系。

定義5 約束頻繁閉合項集。帶有類別值的頻繁閉合項集，稱為約束頻繁閉合項集。

1.2 數據流頻繁項集挖掘方法

現有的數據流頻繁項集挖掘算法，如Moment、FP-Stream、IncMine 等，都是面向事務型數據。根據分類標準不同，數據流頻繁項集挖掘有多種劃分方法。①挖掘頻繁閉合項集，還是所有頻繁項集。②是否引入滑動窗口或時間衰減機制。③按每個事務、還是按批次更新頻繁項集。④挖掘結果是精確解還是近似解。

以IncMine［5］為例，是一種引入滑動窗口機制、按批次增量更新的、挖掘頻繁閉合項集近似算法，有可控且少量的漏報，但比精確解算法Moment、FP-Stream快得多。

IncMine 在MOA 實現時，使用Charm［6］作為批處理挖掘器。Charm 的數據結構本質上是一種Apriori 層次結構，每個節點表示為（項集×事務集）鍵值對，子節點的事務集是父節點事務集的子集。

對于挖掘出來的FCI，IncMine 按長度把它們分別存儲在不同的列表中。同時，IncMine把這些FCI組織成IF（IInverted FCI Index）數據結構。基于IFI，算法可以高效實現查詢、更新FCI等操作。

1.3 貝葉斯分類與顯露模式

貝葉斯分類器關鍵是計算各類值聯合概率，這是一種被廣泛研究的分類模型。經典的樸素貝葉斯計算公式為：

然而現實中這種條件獨立性假設模型是很少成立的，于是出現了基于模式的貝葉斯分類算法，通過在數據集中抽取頻繁模式來近似計算聯合概率的乘積值：

顯露模式是從一個目標類數據集到另一個對立類數據集的支持度有明顯差異的模式，基于顯露模式的貝葉斯分類方法，能夠捕獲不同類型數據之間的明顯趨勢，分類精度高，易于理解。

2 基于IncMine的顯露模式挖掘方法

2.1 基于批次的FCI增量更新算法

Charm 挖掘出最新批次的FCI，需要增量更新滑動窗口中的FCI。IncMine 增量更新算法如算法1所示。

2.2 關系表型數據流半懶惰學習

2.2.1 估計聯合概率

假設事務的類屬性C有屬性值c和cˊ，T={a1，a2，a3，a4，a5，a6}為待分類事務。為了估計聯合概率P（T，c）i的值，需要在窗口的頻繁項隊列鏈表A和Aˊ中抽取顯露模式。

如圖1 所示，假定事務T抽取的類c的顯露模式為{{a1,a2},{a3,a4}}，屬性A5和A6是未被覆蓋的屬性，則聯合概率的估計值為：

圖1 基于顯露模式未被覆蓋的弱條件獨立模型

2.2.2 數據流貝葉斯分類

EPBIM 是基于顯露模式的貝葉斯數據流分類器，采用半懶惰式學習策略［10］進行分類。在訓練階段，其主要任務是挖掘當前滑動窗口的頻繁閉合項集C和C′，當有新的批次數據生成時，更新滑動窗口及相應的數據結構。對于一個待分類樣本S，EPBIM在每個類標對應的頻繁閉合項集中，利用邊界運算方法選取S在該類標的顯露模式集合，用來計算待分類樣本在每個類標下的聯合概率。

3 實驗結果與分析

本文的實驗平臺是MOA（massive online analysis）［1］，主要使用真實數據集，以及MOA數據生成器生成的合成數據集對算法的性能進行評價。實驗采用分類精度性能指標，對本文分類器與MOA平臺上的多種類型分類器進行對比。實驗在2.60 GHz、Intel（R）Core（TM）i7-6700HQ CPU、內存16 GB、操作系統Windows 10的計算機上進行。

3.1 數據集

為了評價EPBIM 算法的性能，本文使用的數據集分別是原始數據集及其挖掘模式形成的數據集。

3.1.1 原始數據集

實驗中采用了三個實際數據集：iris-2D.arff，cpu.with.vendor.arff，credit-g.arff 和兩個合成數據流：AgrawallGenerator，RandomTreeGenerator。數據集具體參數見表1。

表1 數據集基本信息

3.1.2 挖掘模式形成的數據集

表1 所示的五個原始數據集，劃分為訓練集和測試集，占比分別為0.7 和0.3。通過Charm 挖掘出訓練集的頻繁閉合模式，并選擇輸出最長的顯露模式，如表2所示。

表2 原始數據集挖掘的最長模式

3.2 抽取顯露模式對實際數據集分類

3.2.1 顯露模式與原始數據集貝葉斯分類

將原始數據集與顯露模式分別應用WEKA 貝葉斯分類，分類準確度的結果如表3所示。

表3 原始數據集與顯露模式分類準確度比較

從表3 可看到，應用顯露模式的貝葉斯分類相對于只用原始數據集，分類準確度都得到提升。只有iris-2D的分類準確度維持不變。

3.2.2 多種分類器性能比較

對于MOA 平臺上的rotatingHyperplane 數據流，表4 比較EPBIM 算法與樸素貝葉斯分類器（nb）、多數分類器（mc）、裝袋分類器（oz）、杠桿袋裝分類器（lb）、霍夫丁樹分類器（ht）等在線分類器的準確度結果。

表4 rotatingHyperplane 分類準確度比較

顯然，rotatingHyperplane 數據流經過模式挖掘之后再對其進行基于顯露模式的數據流分類，其分類準確率最高。樸素貝葉斯分類器準確率其次，多數分類器最低。所以，顯露模式挖掘工作是有意義的，貝葉斯與顯露模式結合的EPBIM 分類器在以上幾種分類器中準確度最高。

4 結語

樸素貝葉斯是一個理想模型，假設所有輸入數據具有獨立性。樸素貝葉斯作為一個增量算法，十分適合數據流的場景。不過，現實數據集往往包含大量噪聲或無用信息，在分類前加一個模式挖掘的環節很有必要。挖掘頻繁模式預處理可以去除冗余信息和噪聲，頻繁模式比單個屬性更有區分力，基于模式的貝葉斯分類具有更高的準確度。