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

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

0 引言

基于模式的數(shù)據(jù)流貝葉斯分類方法，利用事務(wù)中項(xiàng)之間的相互關(guān)系計(jì)算貝葉斯聯(lián)合概率，是一種有效的數(shù)據(jù)挖掘模型［1-2］。然而，現(xiàn)有的頻繁模式挖掘算法面向事務(wù)數(shù)據(jù)流，與實(shí)際應(yīng)用場景不完全吻合。大量的關(guān)系表型數(shù)據(jù)需要轉(zhuǎn)換為帶類值約束的事務(wù)數(shù)據(jù)流，才能用作有監(jiān)督學(xué)習(xí)的訓(xùn)練數(shù)據(jù)［3-4］。

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

挖掘頻繁閉合模式用于數(shù)據(jù)流分類，這種模式必須帶有類標(biāo)約束才有意義［7］。在挖掘頻繁閉合模式之前，大量的關(guān)系表型數(shù)據(jù)集要轉(zhuǎn)換成帶類值約束的事務(wù)數(shù)據(jù)集，這種預(yù)處理是批量進(jìn)行的。文獻(xiàn)［8］等開發(fā)的挖掘事務(wù)數(shù)據(jù)集閉合頻繁項(xiàng)集算法，不適用于關(guān)系表型數(shù)據(jù)集的批量挖掘，需要增加預(yù)處理環(huán)節(jié)。

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

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

1 相關(guān)工作

1.1 頻繁項(xiàng)集與頻繁閉合項(xiàng)集

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

定義2 頻繁項(xiàng)集。假設(shè)一個(gè)數(shù)據(jù)集最小支持度閾值為σ，如果項(xiàng)集在數(shù)據(jù)集中的支持度大于σ，則稱之為頻繁項(xiàng)集。

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

定義4 關(guān)系表型數(shù)據(jù)。對于關(guān)系表型數(shù)據(jù)的條件屬性值，本文采用“屬性名∶屬性值∶類別值”格式替換后，再掃描數(shù)據(jù)集得到各個(gè)項(xiàng)值id，構(gòu)成事務(wù)型數(shù)據(jù)。帶類標(biāo)屬性值與項(xiàng)存在一個(gè)映射關(guān)系。

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

1.2 數(shù)據(jù)流頻繁項(xiàng)集挖掘方法

現(xiàn)有的數(shù)據(jù)流頻繁項(xiàng)集挖掘算法，如Moment、FP-Stream、IncMine 等，都是面向事務(wù)型數(shù)據(jù)。根據(jù)分類標(biāo)準(zhǔn)不同，數(shù)據(jù)流頻繁項(xiàng)集挖掘有多種劃分方法。①挖掘頻繁閉合項(xiàng)集，還是所有頻繁項(xiàng)集。②是否引入滑動(dòng)窗口或時(shí)間衰減機(jī)制。③按每個(gè)事務(wù)、還是按批次更新頻繁項(xiàng)集。④挖掘結(jié)果是精確解還是近似解。

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

IncMine 在MOA 實(shí)現(xiàn)時(shí)，使用Charm［6］作為批處理挖掘器。Charm 的數(shù)據(jù)結(jié)構(gòu)本質(zhì)上是一種Apriori 層次結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)表示為（項(xiàng)集×事務(wù)集）鍵值對，子節(jié)點(diǎn)的事務(wù)集是父節(jié)點(diǎn)事務(wù)集的子集。

對于挖掘出來的FCI，IncMine 按長度把它們分別存儲(chǔ)在不同的列表中。同時(shí)，IncMine把這些FCI組織成IF（IInverted FCI Index）數(shù)據(jù)結(jié)構(gòu)?；贗FI，算法可以高效實(shí)現(xiàn)查詢、更新FCI等操作。

1.3 貝葉斯分類與顯露模式

貝葉斯分類器關(guān)鍵是計(jì)算各類值聯(lián)合概率，這是一種被廣泛研究的分類模型。經(jīng)典的樸素貝葉斯計(jì)算公式為：

然而現(xiàn)實(shí)中這種條件獨(dú)立性假設(shè)模型是很少成立的，于是出現(xiàn)了基于模式的貝葉斯分類算法，通過在數(shù)據(jù)集中抽取頻繁模式來近似計(jì)算聯(lián)合概率的乘積值：

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

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

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

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

2.2 關(guān)系表型數(shù)據(jù)流半懶惰學(xué)習(xí)

2.2.1 估計(jì)聯(lián)合概率

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

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

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

2.2.2 數(shù)據(jù)流貝葉斯分類

EPBIM 是基于顯露模式的貝葉斯數(shù)據(jù)流分類器，采用半懶惰式學(xué)習(xí)策略［10］進(jìn)行分類。在訓(xùn)練階段，其主要任務(wù)是挖掘當(dāng)前滑動(dòng)窗口的頻繁閉合項(xiàng)集C和C′，當(dāng)有新的批次數(shù)據(jù)生成時(shí)，更新滑動(dòng)窗口及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。對于一個(gè)待分類樣本S，EPBIM在每個(gè)類標(biāo)對應(yīng)的頻繁閉合項(xiàng)集中，利用邊界運(yùn)算方法選取S在該類標(biāo)的顯露模式集合，用來計(jì)算待分類樣本在每個(gè)類標(biāo)下的聯(lián)合概率。

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 數(shù)據(jù)集

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

3.1.1 原始數(shù)據(jù)集

實(shí)驗(yàn)中采用了三個(gè)實(shí)際數(shù)據(jù)集：iris-2D.arff，cpu.with.vendor.arff，credit-g.arff 和兩個(gè)合成數(shù)據(jù)流：AgrawallGenerator，RandomTreeGenerator。數(shù)據(jù)集具體參數(shù)見表1。

表1 數(shù)據(jù)集基本信息

3.1.2 挖掘模式形成的數(shù)據(jù)集

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

表2 原始數(shù)據(jù)集挖掘的最長模式

3.2 抽取顯露模式對實(shí)際數(shù)據(jù)集分類

3.2.1 顯露模式與原始數(shù)據(jù)集貝葉斯分類

將原始數(shù)據(jù)集與顯露模式分別應(yīng)用WEKA 貝葉斯分類，分類準(zhǔn)確度的結(jié)果如表3所示。

表3 原始數(shù)據(jù)集與顯露模式分類準(zhǔn)確度比較

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

3.2.2 多種分類器性能比較

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

表4 rotatingHyperplane 分類準(zhǔn)確度比較

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

4 結(jié)語

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