不確定數(shù)據(jù)的約束頻繁閉項集挖掘算法

牛浩浩，李孝忠，連春月

(天津科技大學(xué)計算機科學(xué)與信息工程學(xué)院，天津 300457)

數(shù)據(jù)挖掘是從數(shù)據(jù)中獲取有價值的潛在信息，目的在于將海量的數(shù)據(jù)轉(zhuǎn)換成有用的知識，并用所得知識對未來的行為進(jìn)行指引．因此，通常也被稱為數(shù)據(jù)庫中的知識發(fā)現(xiàn)(knowledge discovery in databases，KDD)[1]．在數(shù)據(jù)挖掘領(lǐng)域，關(guān)聯(lián)規(guī)則挖掘是一種經(jīng)典的挖掘方法，旨在尋找數(shù)據(jù)庫中有意義的關(guān)聯(lián)，在挖掘過程中需要找到需要的頻繁項集[2]．

在實際情況中，很多數(shù)據(jù)的產(chǎn)生都帶有不確定性，導(dǎo)致原有的頻繁項集挖掘算法無法直接應(yīng)用于不確定數(shù)據(jù)中．目前，關(guān)于不確定數(shù)據(jù)庫的頻繁項集挖掘已有許多研究，如由確定數(shù)據(jù)挖掘算法 Apriori、FP-growth發(fā)展而來的 U-Apriori，UF-growth算法，以及基于此的一系列改進(jìn)算法．然而，隨著數(shù)據(jù)的大量增加，挖掘所得頻繁項集有過多冗余項集，有些甚至是毫無意義的．最大頻繁項集雖然在很大程度上減少了冗余項集，然而其并不包含項集支持度信息．而頻繁閉項集[3]很好地解決了這個問題，頻繁閉項集在不丟失所需信息的前提下，其數(shù)量遠(yuǎn)小于頻繁項集，并包含了所有頻繁項集的支持度信息[4]．

目前，對于不確定數(shù)據(jù)庫的頻繁閉項集挖掘，主要是在不確定數(shù)據(jù)頻繁項集挖掘的基礎(chǔ)上，對頻繁項集中的子集與其直接超集的支持度進(jìn)行比較，由此得到頻繁閉項集．對不確定數(shù)據(jù)的頻繁項集挖掘，其關(guān)鍵步驟之一在于如何確定不確定數(shù)據(jù)的支持度信息．除了上述 U-Apriori，UF-growth等算法將期望概率作為項集支持度處理之外，文獻(xiàn)[5]給出了概率分布的方法來近似項集的支持度計數(shù)，在已有成果中，將支持度近似為正態(tài)分布來進(jìn)行挖掘的結(jié)果準(zhǔn)確度較高[6]．本文在挖掘過程中也將采取此基于正態(tài)分布的方法．

然而，目前數(shù)據(jù)挖掘方法的環(huán)境過于理想，未考慮可能存在的一些針對性條件或者決策者決策需求的偏好．因此，本文將不確定數(shù)據(jù)的支持度近似為正態(tài)分布，在其頻繁閉項集挖掘過程中加入了簡潔性約束條件，分別研究了在簡潔反單調(diào)約束和簡潔非反單調(diào)約束下，對不確定數(shù)據(jù)庫進(jìn)行頻繁閉項集挖掘的方法．

1 相關(guān)定義

1.1 不確定數(shù)據(jù)上的概率頻繁閉項集

目前，在不確定數(shù)據(jù)庫中挖掘頻繁項集的方法分為兩大類[7]：基于期望支持度模型的方法和基于概率頻繁模型的方法．

基于期望支持度模型[8]的方法最早是由 Chui等提出的，這種方法使用期望支持度來對支持度進(jìn)行近似計數(shù)，在計算某項集支持度時，把數(shù)據(jù)庫中該項集在每個事務(wù)中對應(yīng)的概率相加，相加的結(jié)果表示該項集的支持度的估計值．因此，基于期望支持度的頻繁項集有如下定義：如果項集X是頻繁項集，那么X的期望支持度 esup(X)必須大于等于用戶給定的最小閥值．

基于概率頻繁模型[9]的方法由Bernecker在2009年提出，該方法認(rèn)為在不確定性數(shù)據(jù)庫中，項集的出現(xiàn)是不確定的，因此其支持度也是不確定的，可以使用適當(dāng)?shù)臉?biāo)準(zhǔn)參數(shù)分布近似不確定項集的概率支持度計數(shù)，即支持度的概率分布，如泊松分布[5]、正態(tài)分布[6]等．

已有不確定項集支持度的近似模型中，近似效果最好的是正態(tài)分布模型[6]，其相關(guān)定義[10]如下：

定義 1 頻繁概率：給定一個最小支持度閾值cminsup，項集X的頻繁概率是指X的支持度大于等于cminsup的概率[11]，記作 Pfreq(X)．

定義 2 頻繁概率項集：給定一個最小支持度cminsup∈［0，n］和置信度(概率頻繁閾值)τ∈［0，1］，如果項集 X的頻繁概率大于概率頻繁閾值，則X是一個概率頻繁項集，即

定義 3 概率支持度[12]：項集 X在置信度 τ下的概率支持度ProbSup(X，τ)定義為

其中：argmax()指使得括號內(nèi)取得最大值的i值，從定義中可知，概率支持度是指滿足項集X出現(xiàn)i次以上的概率大于等于 τ的最大的 i．也就是，在具體過程中，計算出P(support(X)≥cminsup)≥τ后，要繼續(xù)計算P(support(X)≥cminsup+1)≥τ，P(support(X)≥cminsup+2)≥τ，…，直至 P(support(X)≥cminsup＋n)＜τ，則cminsup＋n-1就是概率支持度．

定義 4 概率頻繁閉項集：項集 X是概率頻繁閉項集，當(dāng)且僅當(dāng) Pfreq(X)≥τ，且找不到任何項集 X的超集 Y，滿足 ProbSup(Y，τ)＝ProbSup(X，τ)[12]．

1.2 約束條件

現(xiàn)有的約束型頻繁項集挖掘，允許用戶使用一組SQL(structured query language)約束來規(guī)范其挖掘過程．根據(jù)此約束，可以挖掘滿足用戶需求的在事務(wù)中頻繁發(fā)生的項目，此類挖掘方法可以避免挖掘無意義的頻繁項集所引起的不必要計算[13]．

其中，大多數(shù)用戶定義的約束是簡潔的，如 C1：max(X．Price)≤$25，它表示用戶所感興趣的頻繁項集 X中，最貴的物品的價格不超過 25美元(即所需項集中每個項目的價格都不超過 25美元)；同樣的，C2：min(X．Price)≤$30表示所需項集中，價格最低的項不超過 30美元．除了購物籃項目，一套約束也可以針對其他領(lǐng)域的項目、事件或?qū)ο螅?，C3：X.Location＝Winnipeg表示用戶尋求的頻繁項集X的所有事件都發(fā)生在加拿大溫尼伯；C4：X.Symptom＝{drythroat，sneezing}表示 X中的每個人都患有喉嚨干燥、打噴嚏中至少一種癥狀．而非簡潔約束，如，C5：sum(X．Price)≤$100表示挖掘所得的 X中所有項集的價格之和不超過100美元，本文對非簡潔約束暫不作討論．

除了約束是否簡潔這一特性之外，還可以根據(jù)某些其他屬性(如反單調(diào)性：約束 C是反單調(diào)的，當(dāng)且僅當(dāng)滿足C的項集的所有子集也滿足C)對約束條件進(jìn)行劃分．如，根據(jù)反單調(diào)性，簡潔約束可以被劃分為兩類：簡潔反單調(diào)約束(succinct anti-monotone constraints，SAM)，簡潔非反單調(diào)約束(succinct non-antimonotone constraints，SUC)[13]．

上述所給簡潔性約束例子中，C1、C3為 SAM；C2、C4為SUC．

2 約束條件下的概率頻繁閉項集挖掘

2.1 概率頻繁閉項集及其概率支持度

在挖掘概率頻繁項集時，需要計算項集的概率支持度．假設(shè)項集 I在數(shù)據(jù)庫中出現(xiàn)的次數(shù)為 XI，由于事務(wù)數(shù)據(jù)庫足夠大(事務(wù)數(shù)為n)，將XI近似為連續(xù)的正態(tài)分布，則項集I的頻繁概率為

其中，F(xiàn)是概率密度函數(shù)的積分，即

而

在實際情況中，可以根據(jù)數(shù)據(jù)庫計算 μI和 σI2，進(jìn)而求出 I的頻繁概率 Pfreq(I)，若 Pfreq(I)＜τ，即項集 I出現(xiàn) cminsup次以上的概率小于 τ，則認(rèn)為項集 I是不頻繁的；否則項集I為頻繁項集．

根據(jù)定義 3，為了得到項集的概率支持度，在計算 P(support(X)≥cminsup)≥τ之后，需要繼續(xù)計算P(support(X) ≥cminsup＋1)≥ τ，…，直至P(support(X)≥cminsup＋i)＜τ，則 cminsup＋i-1 就是其概率支持度[10]．

2.2 約束條件下的概率頻繁閉項集

在約束條件下，可根據(jù)約束條件將數(shù)據(jù)庫中的項分為ItemM和ItemO兩部分[12]．其中，ItemM為強制性集合，該集合具有強制性，是因為它是約束條件下的必選項集合；ItemO表示非必選項的集合．

則對于任意約束SAM，ItemM表示滿足SAM約束的項集 X，ItemO表示不滿足該約束條件的項目集合，由于其反單調(diào)性，X不應(yīng)包含ItemO中的項，即X應(yīng)由ItemM中的項組合而成．相應(yīng)地，對于任意 SUC約束，滿足該約束的頻繁項集應(yīng)包含 ItemM中的至少一個中的項目，即目標(biāo)項集應(yīng)由 N1個 ItemM(N1≥1)和N2個ItemO(N2≥0)組成．

下面以實例解釋數(shù)據(jù)庫處理過程．表 1為不確定數(shù)據(jù)組成的交易數(shù)據(jù)庫，表2為補充的商品價格信息．其中，表 1是根據(jù)用戶購買習(xí)慣及瀏覽記錄得出的購買商品及其概率，“事務(wù)”欄中的“T1，T2，T3”等表示每條成交記錄，“項目”欄表示可能購買的商品及購買的概率，如 T1，{a，b，c，d，e}為其可能購買的商品，購買 a商品的概率為 0.7，購買 b商品的概率為0.8，…．表2表示各商品價格，如a商品價格為10，b商品價格為20等．

表1 交易數(shù)據(jù)庫Tab. 1 Transaction database

表2 商品價格表Tab. 2 Price of commodity

對于 SAM 約束 C1：max(X．Price)≤$25，根據(jù)約束的定義和要求，所挖掘的頻繁項集中每項的價格應(yīng)該小于等于 25美元，即所求頻繁項集為小于等于25美元的項的集合．根據(jù)附加信息可得：ItemM＝{a，b，f}和 ItemO＝{c，d，e}．則對于 SAM 約束，挖掘所得頻繁閉項集必須只包括ItemM中的項．

對于SUC約束C2：min(X．Price)≤$30，可以得到：ItemM＝{a，b}和 ItemO＝{c，d，e，f}．則所需約束頻繁閉項集必須包含至少一個 ItemM中的項，也可能還包含有一些額外的ItemM或ItemO中的項．

3 約束頻繁閉項集挖掘過程

數(shù)據(jù)被分為 ItemM和 ItemO之后，對于 SAM 約束，挖掘所得項集不包含 ItemO中的項，則可刪除原數(shù)據(jù)庫中ItemO包含的項；對于SUC約束，則可根據(jù)ItemM和 ItemO將原數(shù)據(jù)庫分成兩個子數(shù)據(jù)庫后進(jìn)行挖掘．

3.1 SAM約束下頻繁閉項集挖掘

對于 SAM 約束 C1：max(X．Price)≤$25，可以得到 ItemM＝{a，b，f}和 ItemO＝{c，d，e}．根據(jù)約束的定義和要求，對數(shù)據(jù)庫進(jìn)行修剪處理．處理之后的結(jié)果見表3．

表3 SAM約束下的必選數(shù)據(jù)庫Tab. 3 Mandatory database of SAM

對修剪后的數(shù)據(jù)庫進(jìn)行概率頻繁閉項集挖掘．首先進(jìn)行 1-項集挖掘，在進(jìn)行挖掘之前，先對數(shù)據(jù)庫進(jìn)行簡單的剪枝．由于任何一個非頻繁項集的超集是非頻繁的，所以對于 1-項集，暫時不考慮項集的概率，只計算其出現(xiàn)的次數(shù)，根據(jù)設(shè)定的 cminsup，若其出現(xiàn)次數(shù)小于 cminsup，則該項集一定不頻繁，該項集的超集也是非頻繁的，因此對項集進(jìn)行剪枝，以減少不必要的計算．

剪枝之后，對表 3中剩余的 1-項集分別進(jìn)行頻繁判斷：根據(jù)式(2)—式(5)可以計算數(shù)據(jù)庫中各項集的頻繁概率，若項集 I的頻繁概率大于設(shè)定的閾值，則為 1-頻繁項集，反之由于其單調(diào)性，去掉不頻繁的項．對于 1-頻繁項集，為了進(jìn)一步進(jìn)行概率頻繁閉項集判斷，可以根據(jù)式(1)求得項集的概率支持度．

然后采用相同的方法判斷 2-項集、3-項集等是否是頻繁項集，并計算其概率支持度．以例 1為例說明具體過程．

例1在上述數(shù)據(jù)表中，假設(shè)cminsup＝2，τ＝0.3，判斷2-項集I＝{a，b}和1-項集J＝{a}是否是頻繁項集．

對于 2-項集 I，μI＝1.12，σI2＝0.492,8，Prfreq(I)＝1-Φ((cminsup-0.5-μI)/σI)＝1-Φ(0.38/)＜1-Φ(0.38/)＝1-Φ(0.38/0.71)＜1-Φ(0.53)＝1-0.701,9＜τ，由于 Prfreq(I)＜τ，則 I為非頻繁項集，無需再進(jìn)行概率支持度的計算．

而對于 1-項集 J，μJ＝2.2，σJ2＝0.58，Pfreq(J)＝1-Φ((cminsup-0.5-μJ)/σJ)＝1-Φ(-0.7/)＝Φ(0.7/)＞Φ(0)＝0.5＞τ，則 J為 1-頻繁項集，再根據(jù)定義3計算可得到J的概率支持度為3．

根據(jù)以上計算可得，2-項集 I＝{a，b}為非頻繁項集，1-項集J＝{a}為頻繁項集，其概率支持度為3．

上述步驟中 n-項集的生成，可以采用基于寬度優(yōu)先的Apriori算法及其改進(jìn)算法[14]或者基于深度優(yōu)先的FP-Growth算法及其改進(jìn)算法[15]．

如在寬度優(yōu)先算法中，首先根據(jù)定義 2挖掘 1-頻繁項集，并得到其概率支持度；之后將 1-頻繁項集鏈接生成 2-項集，通過相同的計算方法確定 2-頻繁項集及其概率支持度，并根據(jù)定義4將1-頻繁項集X與 2-頻繁項集中其對應(yīng)的超集 Y進(jìn)行比較，若不滿足定義 4，則刪去前者保留后者，若滿足，則均保留；再根據(jù) 2-頻繁項集鏈接生成 3-項集…，重復(fù)上述步驟直至挖掘結(jié)束，可以得到所有滿足約束條件的概率頻繁閉項集及其概率支持度．

3.2 SUC約束下頻繁閉項集挖掘

對于 SUC 約束 C2：min(X．Price)≤$30，按照約束(X．Price)≤$30 和(X．Price)＞$30，將數(shù)據(jù)庫的項分為兩部分：ItemM＝{a，b，f}和 ItemO＝{c，d，e}，則所需要挖掘的頻繁閉項集應(yīng)該由N1個ItemM(N1≥1)和 N2個 ItemO(N2≥0)組成．因此將數(shù)據(jù)庫分為兩個數(shù)據(jù)庫：SUC下的必選數(shù)據(jù)庫(表 4)及可選數(shù)據(jù)庫(表 5)．

表4 SUC約束下的必選數(shù)據(jù)庫Tab. 4 Mandatory database of SUC

表5 SUC約束下的可選數(shù)據(jù)庫Tab. 5 Optional database of SUC

首先根據(jù)剪枝條件對兩個數(shù)據(jù)庫分別進(jìn)行剪枝，之后根據(jù)上述方法分別得到兩個數(shù)據(jù)庫的 1-頻繁項集及其概率支持度．值得注意的是，為避免數(shù)據(jù)損失，在挖掘過程中，并不對項集X及其超集Y進(jìn)行概率支持度比較，統(tǒng)一保留，由此可以得到兩個數(shù)據(jù)庫中所有的頻繁項集．其中，根據(jù)約束定義可知，表 4挖掘所得頻繁項集為符合約束條件的頻繁項集．

下一步，由表 4數(shù)據(jù)庫挖掘所得的頻繁項集M(M∈ItemM)向表 5數(shù)據(jù)庫挖掘所得的頻繁項集N(N∈ItemO)進(jìn)行擴展，過程如例2．

例 2 假設(shè) cminsup＝2，τ＝0.3，從例 1可知，對于表 4數(shù)據(jù)庫，ItemM中的項集 M＝{a}為頻繁項集，對于表5數(shù)據(jù)庫，計算N＝{c}是否為頻繁項集．

對于 1-項集 N，μN＝2.9，σN2＝0.73，Pfreq(N)＝1-Φ((cminsup-0.5-μN)/σN)＞τ．

則 N為表 5數(shù)據(jù)庫挖掘的 1-頻繁項集，根據(jù)定義3，通過計算可得到N的概率支持度為3．

因此，以表 4數(shù)據(jù)庫挖掘所得的 M＝{a}為基礎(chǔ)，與表 5數(shù)據(jù)庫所挖掘的頻繁項集 N＝{c}進(jìn)行結(jié)合，得到新的項集 O＝{a，c}，接下來使用概率頻繁模型判斷在原數(shù)據(jù)庫表 1中，項集 O是否頻繁且是否與項集 M 的概率支持度相同，若其不頻繁則不是目標(biāo)項集，若項集O頻繁則作為目標(biāo)項集保留．

按照例2所述方法，以表4數(shù)據(jù)庫挖掘所得的頻繁項集為基礎(chǔ)，與表5數(shù)據(jù)庫挖掘所得的頻繁項集進(jìn)行結(jié)合，并判斷是否頻繁，可得到此結(jié)合方法下符合約束的頻繁項集．則表 4數(shù)據(jù)庫挖掘的頻繁項集與結(jié)合所得的頻繁項集共同構(gòu)成滿足SUC約束的頻繁項集集合．

最后，對所得到的所有符合約束的頻繁項集根據(jù)定義4進(jìn)行驗證，若某一項集的直接超集與其概率支持度相同，則刪去該項集保留其直接超集，否則二者均保留．由此，可得到所有的目標(biāo)項集．

4 結(jié) 語

本文根據(jù)概率頻繁模型進(jìn)行數(shù)據(jù)挖掘，將項集的支持度近似為正態(tài)分布，避免了生成不確定數(shù)據(jù)庫的所有可能世界，在一定程度上減少了計算量．另外，引入了約束條件，在兩種約束限制下重新對數(shù)據(jù)庫進(jìn)行挖掘，使得挖掘結(jié)果更滿足不同的個人實際需求．然而，隨著不確定數(shù)據(jù)的增多，其復(fù)雜程度也隨之增加，加之現(xiàn)實生活中對數(shù)據(jù)庫挖掘的要求也多種多樣，需要有更高效更準(zhǔn)確的不確定數(shù)據(jù)挖掘方法來解決人們對數(shù)據(jù)庫的挖掘需求．接下來，可以針對SUC約束下較復(fù)雜的挖掘情況進(jìn)行研究，以期獲得更高的效率．并把約束思想應(yīng)用于其他挖掘算法中，以滿足人們對數(shù)據(jù)挖掘的不同需求．