牛浩浩，李孝忠，連春月

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

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

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

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

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

1 相關(guān)定義

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

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

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

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

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

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

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

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

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

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

1.2 約束條件

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

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

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

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

2 約束條件下的概率頻繁閉項(xiàng)集挖掘

2.1 概率頻繁閉項(xiàng)集及其概率支持度

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

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

而

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

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

2.2 約束條件下的概率頻繁閉項(xiàng)集

在約束條件下，可根據(jù)約束條件將數(shù)據(jù)庫(kù)中的項(xiàng)分為ItemM和ItemO兩部分[12]．其中，ItemM為強(qiáng)制性集合，該集合具有強(qiáng)制性，是因?yàn)樗羌s束條件下的必選項(xiàng)集合；ItemO表示非必選項(xiàng)的集合．

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

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

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

表2 商品價(jià)格表Tab. 2 Price of commodity

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

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

3 約束頻繁閉項(xiàng)集挖掘過(guò)程

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

3.1 SAM約束下頻繁閉項(xiàng)集挖掘

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

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

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

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

然后采用相同的方法判斷 2-項(xiàng)集、3-項(xiàng)集等是否是頻繁項(xiàng)集，并計(jì)算其概率支持度．以例 1為例說(shuō)明具體過(guò)程．

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

對(duì)于 2-項(xiàng)集 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為非頻繁項(xiàng)集，無(wú)需再進(jìn)行概率支持度的計(jì)算．

而對(duì)于 1-項(xiàng)集 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-頻繁項(xiàng)集，再根據(jù)定義3計(jì)算可得到J的概率支持度為3．

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

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

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

3.2 SUC約束下頻繁閉項(xiàng)集挖掘

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

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

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

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

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

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

對(duì)于 1-項(xiàng)集 N，μN(yùn)＝2.9，σN2＝0.73，Pfreq(N)＝1-Φ((cminsup-0.5-μN(yùn))/σN)＞τ．

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

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

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

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

4 結(jié) 語(yǔ)

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