不確定數據的約束頻繁閉項集挖掘算法

牛浩浩，李孝忠，連春月

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

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

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

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

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

1 相關定義

1.1 不確定數據上的概率頻繁閉項集

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

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

基于概率頻繁模型[9]的方法由Bernecker在2009年提出，該方法認為在不確定性數據庫中，項集的出現是不確定的，因此其支持度也是不確定的，可以使用適當的標準參數分布近似不確定項集的概率支持度計數，即支持度的概率分布，如泊松分布[5]、正態分布[6]等．

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

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

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

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

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

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

1.2 約束條件

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

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

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

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

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

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

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

其中，F是概率密度函數的積分，即

而

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

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

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

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

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

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

表1 交易數據庫Tab. 1 Transaction database

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

對于 SAM 約束 C1：max(X．Price)≤$25，根據約束的定義和要求，所挖掘的頻繁項集中每項的價格應該小于等于 25美元，即所求頻繁項集為小于等于25美元的項的集合．根據附加信息可得：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 約束頻繁閉項集挖掘過程

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

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

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

表3 SAM約束下的必選數據庫Tab. 3 Mandatory database of SAM

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

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

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

例1在上述數據表中，假設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為非頻繁項集，無需再進行概率支持度的計算．

而對于 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-頻繁項集，再根據定義3計算可得到J的概率支持度為3．

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

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

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

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

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

表4 SUC約束下的必選數據庫Tab. 4 Mandatory database of SUC

表5 SUC約束下的可選數據庫Tab. 5 Optional database of SUC

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

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

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

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

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

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

按照例2所述方法，以表4數據庫挖掘所得的頻繁項集為基礎，與表5數據庫挖掘所得的頻繁項集進行結合，并判斷是否頻繁，可得到此結合方法下符合約束的頻繁項集．則表 4數據庫挖掘的頻繁項集與結合所得的頻繁項集共同構成滿足SUC約束的頻繁項集集合．

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

4 結 語

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