一種利用相關(guān)性度量的不確定數(shù)據(jù)頻繁模式挖掘

任永功，高 鵬，張志鵬

(遼寧師范大學 計算機信息與技術(shù)學院，遼寧 大連 116029)

1 引 言

隨著數(shù)據(jù)收集和存儲技術(shù)的進步，產(chǎn)生了海量數(shù)據(jù).其中，現(xiàn)實生活中產(chǎn)生的不確定數(shù)據(jù)受到了廣泛重視，繼而對不確定數(shù)據(jù)頻繁模式挖掘的需求日益增長，然而從中提取有用的信息已經(jīng)成為巨大的挑戰(zhàn).

頻繁項集[1]挖掘作為數(shù)據(jù)挖掘方面的基礎(chǔ)步驟，在不同領(lǐng)域都出現(xiàn)了許多有效的方法.比如項集挖掘[2,3](例如Apriori，F(xiàn)P-growth)，數(shù)據(jù)流挖掘[4]，序列模式挖掘，頻繁圖挖掘，高效用模式挖掘[5]，相關(guān)模式挖掘[6](例如興趣度方法)，行為挖掘和時序數(shù)據(jù)挖掘.其中多數(shù)方法僅是基于支持度來剪枝組合搜索空間，另外加上確定數(shù)據(jù)庫與不確定數(shù)據(jù)庫在計算上和語義上的差異致使它們并不適用于不確定數(shù)據(jù)庫.

近些年已經(jīng)提出了不少算法[7-14](例如FOCUS，U-Apriori，UF-growth，UFP-growth，CUF-growth，PUF-growth， TVDBSCAN，WUIPM等)來進行不確定數(shù)據(jù)庫中的模式挖掘,其中也涉及到不確定數(shù)據(jù)庫中一些有效的聚類算法[15,16].其中CUF-growth算法通過引入限值而獲得一個緊湊樹結(jié)構(gòu)，其性能優(yōu)于UFP-growth算法，但會產(chǎn)生許多誤報信息.于是，PUF-growth算法在樹的前綴分支引入限值進而減少誤報來成功減少運行時間.所有這些都集中在不確定數(shù)據(jù)庫頻繁模式挖掘.然而，頻繁模式往往在數(shù)量上巨大并且在很多時候包含過多冗余信息，但項之間的相關(guān)分析可以在已挖掘的模式中消除冗余和不重要的項集.

此前，WIP[17]和Hyperclique Miner[18]挖掘相關(guān)模式和加權(quán)相關(guān)模式表現(xiàn)突出，但是確定數(shù)據(jù)庫和不確定數(shù)據(jù)庫之間的基本區(qū)別使這些方法在不確定的數(shù)據(jù)庫中已經(jīng)過時.因此，探究新的方法來從不確定的數(shù)據(jù)庫中挖掘相關(guān)模式，將更具有價值.

本文將充分考慮項集各項之間的相關(guān)性來發(fā)現(xiàn)不確定數(shù)據(jù)中有價值的模式，其中考慮到了每一項的重要性并賦予其相應(yīng)的權(quán)重值代表其項的重要性.

2 相關(guān)工作

確定數(shù)據(jù)庫和不確定數(shù)據(jù)庫存在語義上的差異，所以在不確定的數(shù)據(jù)庫中通常用一個項集的期望支持度來代替實際的確定數(shù)據(jù)庫的支持度.目前已經(jīng)有了許多從不確定數(shù)據(jù)庫中挖掘頻繁項集的算法.其中，CUF-growth*[9]介紹的緊湊樹和快

速挖掘算法，其性能優(yōu)于其它算法.然后，提出的PUF-growth算法[12]，其采用依賴于前綴分支的樹型結(jié)構(gòu)來挖掘頻繁模式.所有這些方法只適用于挖掘頻繁模式，并且未解決數(shù)據(jù)挖掘的一個有價值的問題，即頻繁項集內(nèi)各項目之間的相關(guān)性.在一般情況下，頻繁項集可以是大數(shù)量的，它們之間的相關(guān)性分析可以刪除大量的不相關(guān)項集，選擇最有效的項集進行知識挖掘.在本節(jié)中，按時間順序?qū)ΜF(xiàn)有的方法進行一個簡短的討論.

首先，U-Apriori[8]算法擴展了Apriori[2]算法，來從一個不確定的數(shù)據(jù)庫中挖掘頻繁模式.相對于Apriori算法它有類似的缺點，例如，過度的候選集生成.在U-Apriori之后，提出了基于FP-growth[3]的方法，即UF-growth[9]算法.UF-growth算法使用一棵被稱為UF-tree[8]的樹結(jié)構(gòu)來存儲一個不確定數(shù)據(jù)庫，并從樹中挖掘頻繁模式.在構(gòu)建UF-tree[9]的過程中，首先找出期望支持度計數(shù)大于或等于最小支持計數(shù)的頻繁1-項集.然后，在不確定的數(shù)據(jù)庫中每個事務(wù)更新只保持頻繁1-項集.UF-tree[9]的構(gòu)造過程就像建造FP-tree[3]除了有著不同存在概率的相同項被放在了不同的節(jié)點.而在事務(wù)中只有相同的存在概率的相同項才合并在一起.為了進一步減小UF-tree的大小以獲取挖掘效率，UFP-growth[10]把相似的節(jié)點(即節(jié)點具有相同的項X和相近的存在概率值)分成一簇.此簇包含其成員之間最大存在概率值的項X以及其成員的數(shù)量.因此，如果沒有集群可以形成，UFP-tree[10]可能和UF-tree同樣大.另外，它可以減小樹的規(guī)模，但它可能會產(chǎn)生一個模糊的結(jié)果(誤報頻繁項集).

之后,CK Leung提出CUF-growth[11]和CUF-growth*[12],顯著減小了樹的規(guī)模，達到了比其它不確定數(shù)據(jù)庫中頻繁項集挖掘算法更好的性能.雖然CUF-growth*[11]優(yōu)于所有現(xiàn)有的方法，但它還是避免不了會產(chǎn)生過多的誤報信息.因此，CUF-growth*[11]的性能很大程度上取決于其產(chǎn)生的誤報數(shù).

目前，為了降低UF-tree[9]和UFP-tree[10]的大小，CK Leung又提出了基于前綴上界的不確定頻繁模式樹結(jié)構(gòu)(PUF-tree[12])，并可從其中獲取不確定性數(shù)據(jù)的重要信息，進而可以從中挖掘頻繁模式.

3 相關(guān)描述和問題定義

定義1. (前綴).事務(wù)ti為{a1:p1,a2:p2,…,aj-1:pj-1,…,an:pn},則定義事務(wù)ti中的數(shù)據(jù)項aj的前綴為p(ti,aj)={ak:pk|ak:pk∈ti,且1≤k

(1)

定理1.事務(wù)ti任意k-項集(k>2)I={a1:p1,…,ak:pk} 的存在概率總是小于等于其事務(wù)前綴上界TpCap(ti,ak),即P(I,ti)≤TpCap(ti,ak).

定義3.(事務(wù)前綴代理).ti中項aj的事務(wù)前綴代理值記作TpProxy(ti,aj)其值為p(ti,aj)中的第三大概率值.在事務(wù)ti={a1:p1,a2:p2,…,aj:pj,…,an:pn}中h=|p(ti,aj)|表示其前綴長度，第三大值M-3=thirdmaxw∈[1,h](pw)則

(2)

定義4.(前綴代理).在數(shù)據(jù)庫T中具有相同p(ti,aj)的事務(wù)ti的集合記為TP，在TP中取所有事務(wù)第三大值M3中的最大值記為項aj的前綴代理值pProxyk(aj).則

pProxy(aj)=maxti∈TP(TpProxy(ti,aj) ).

(3)

定義5.(期望支持度前綴上界).項集X的期望支持度前綴上界記為ExpSuppCap(X)，定義如下

(4)

定理2.項集X的實際期望支持度總是小于等于X的期望支持度前綴上界，即ExpSup(X)≤ExpSuppCap(X).

假設(shè)這些不確定數(shù)據(jù)庫包含事務(wù)ti，ti表示n項集合{a1:p1,a2:p2,…,an:pn}，其中每一項aj對應(yīng)著一個概率值Pj(0

(5)

式中|T|表示不確定數(shù)據(jù)庫中事務(wù)的數(shù)量,P(x,ti)是項x在事務(wù)ti中存在的概率.如果某一項集的期望支持度大于等于預(yù)定閾值，則它可以被認定為頻繁的.

然而，在不確定數(shù)據(jù)庫中，僅僅依靠期望支持度并不能準確地估計頻繁模式，其丟失了項集支持度的不確定性產(chǎn)生誤報.繼而針對不確定數(shù)據(jù)庫又提出了概率頻繁模型[19]，假設(shè)最小支持度minsup和頻繁概率閾值τ，如果

P(sup(X)≥|T|×misup)≥τ

(6)

式中sup(X)表示不確定數(shù)據(jù)庫T中包含X的事務(wù)數(shù)量，滿足上式則X被認定為頻繁項集.

4 本文算法

在本文中，提出了一種新的針對不確定數(shù)據(jù)挖掘的樹結(jié)構(gòu)-UFPM樹和對應(yīng)的快速挖掘算法-UFPM-CM算法，其中考慮到了每一項的重要性并給予相應(yīng)的權(quán)重值代表其項的重要性.引入不確定數(shù)據(jù)庫的度量不確定置信度(uConf)和加權(quán)不確定置信度(wUConf)進行項集之間的相關(guān)性分析，以刪除大量的不相關(guān)項集，得到最有效的項集進行知識挖掘.

在不確定數(shù)據(jù)庫(UD)中，|UD|表示事務(wù)數(shù)量.假定事物之間相互獨立，每個事務(wù)ti包含多個數(shù)據(jù)項k，p(k∈ti)∈[0,1]表示數(shù)據(jù)項k在事務(wù)ti中的存在概率.一個不確定數(shù)據(jù)庫樣例如表1所示.

UFPM樹的構(gòu)建分兩步來完成.第一步通過掃描數(shù)據(jù)庫得到頻繁項的集合，第二步使用這些頻繁項集構(gòu)造UFPM樹.一般來說，一次讀取一個事務(wù)并將其頻繁項插入作為樹的一個分支.在插入的過程中，前綴上界TpCap(定義2)和前綴代理值pProxy(定義4)也逐步被計算出來并存儲在相應(yīng)的結(jié)點中.

表1 帶權(quán)值的數(shù)據(jù)庫樣例Table 1 Example database with weight

例如在表1中，數(shù)據(jù)庫有6個事務(wù){(diào)a1,a2,…,a6}，設(shè)定最小支持度閾值為38%，則最小支持度計數(shù)為0.38×6=2.28.在事務(wù)t1中項a的不確定值為0.6，于是項a的期望支持度ExpectedSupport({a}=p(a,t1)+p(a,t2)+p(a,t3)+p(a,t4)+p(a,t5)+p(a,t6)=0.6+0.5+0.4+0.9+0.7=3.1.則掃描數(shù)據(jù)庫，計算出所有項的期望支持(a：3.1,b:3,c:3.3,d:2.9,e:3,,f:3.7).然而通常不確定數(shù)據(jù)庫包含了項集支持度的不確定性，其對項集是否頻繁十分重要.根據(jù)文獻[19]，設(shè)置合適的頻繁概率閾值τ為0.9，計算各項的支持度概率.其中發(fā)現(xiàn)項目b和項目e期望支持度相同，但從表2所示的支持度概率分布可以看出，根據(jù)公式P(sup(X)≥|T|×minsup)≥τ則e的頻繁概率為0.702(=0.534+0.12+0.048),b的頻繁概率為0.91(=0.82+0.08+0)，這樣項e的存在和不存在相較于項b更加明確，然后刪除不頻繁的項，按期望支持度遞減排序到列表Item-list中.這樣，結(jié)果Item-list={f:3.7,c:3.3,a:3.1,e:3,d:2.9}.

第二步再次掃描數(shù)據(jù)庫，事務(wù)插入到樹中作為其分支，其中每個項所需要的信息將一個個計算出來.例如，第一個事務(wù)t1={a:0.6,c:0.4,d:0.9,e:1,f:0.7}被讀取，其中所有不頻繁項被移除.然后按Ttem_list中的次序排序得到{f:0.7,c:0.4,a:0.6,e:1,d:0.9}.現(xiàn)在這些項就被插入到樹中，并且根據(jù)定義2、定義4，相應(yīng)的前綴上界TpCap和前綴代理值pProxy也被計算出來.具體細節(jié)如下.在第一個事務(wù)中，f:0.7首先插入空樹，其前綴p(t1,f)={φ}，所以，TpCap(t1,f)=∞，pProxy(f)=0.接下來，c:0.4作為f(∞,0)的孩子插入，其p(t1,c)={f:0.7}，則TpCap(t1,c)=∞，pProxy(c)=0.然后a:3.1作為c(∞,0)的孩子插入，其p(t1,a)={f:0.7,c:0.4}，則TpCap(t1,a)=0.7*0.4*0.6=0.168，pProxy(c)=0.如此，{e:1,d:0.9}同上一樣插入樹中.圖1描述了t1插入樹中的過程.

所有的事務(wù)都以上述方式插入樹中，當遇到共享的前綴時，對于前綴上界值與結(jié)點已存在的值相加，而前綴代理值pProxy則更新為其最大值.例如，當事務(wù)t2插入到樹中后，樹更新為{f:∞:0,c:∞:0,a:0.168+0.1:0,e:0.42+0.02:0.8,d:0.63+0.06:0.6}.同樣，樣例中所有事務(wù)插入到樹中后，得到的樹如圖2所示.

對UFPM樹的挖掘過程分為3個步驟：

1)構(gòu)建項集投影樹；

2)利用剪枝策略過濾投影樹；

3)挖掘所需要的項集.

首先，初始頻繁項集取自上面的結(jié)果集Item-list.UFPM-CM算法對result中的每個項遞歸地執(zhí)行這3個步驟，直到產(chǎn)生所有的頻繁項集.詳細描述見算法2.

圖2 最終構(gòu)建的樹Fig.2 Final tree construction

受全置信度的啟發(fā)引入不確定數(shù)據(jù)庫的度量不確定置信度(uConf)和加權(quán)不確定置信度(wUConf)，即項集I滿足置信度uConf(I)和wUConf(I)，那么中的所有規(guī)則至少有一條規(guī)則也滿足置信度閾值，也就是意味著uConf和wUConf隱含著項集中各項之間的相關(guān)性，而不是其中兩個項之間的相關(guān)性，所以一項集只要滿足相應(yīng)的閾值就可以挖掘出強相關(guān)的模式.

根據(jù)文獻[20]所提出的全置信度，提出不確定期望支持度置信度前綴上界和加權(quán)不確定期望支持度置信度前綴上界可分別定義如下.

定義6.在不確定性數(shù)據(jù)庫中模式的不確定性置信度前綴上界uConfpCap可表示為：

(7)

性質(zhì)1.(uConfpCap的反單調(diào)性)：如果模式Z的uConfpCap不小于最小閾值，那么Z的所有子集的uConfpCap值也不小于最小閾值.

定義7.在不確定性數(shù)據(jù)庫中模式的不確定性置信度前綴上界wUConfpCap(Z) 可表示為：

(8)

性質(zhì)2.(wUConfpCap的反單調(diào)性)：如果模式Z的wUConfpCap不小于最小閾值，那么Z的所有子集的wUConfpCap值也不小于最小閾值.

如果項集Z的uConfpCap(Z)和wUConfpCap(Z)值小于最小閾值,則就無須更深地挖掘它的超集，進而可以有效地剪枝無用的項集.利用UFPM樹來簡單有效地計算任意項集I的uConfpCap(Z)和wUConfpCap(Z)值，并可以把它們單獨地加入到UFPM-CM算法中.因此，除了頻繁模式之外，UFPM樹可以提取到相關(guān)模式，而不需要任何大量的計算.

算法1.構(gòu)建UFPM樹

輸入：不確定數(shù)據(jù)庫UD，最小期望支持度閾值δ，頻繁概率閾值τ

輸出：UFPM樹

begin

1. foreach itemI∈UD do

2. Calculate expected supportI;

3. CalculatePi(I);

4. If ExpectedSupport(I)<δthen

5. RemoveI;

6. If P(sup(I)≥N×δ)<τthen

7. RemoveI;

8.Item-list:=Arrangeitemsinapre-definedorder;

9.CreatetherootnodeR;

10. Foreach transactionTi∈UD do

11. Delete all infrequent items fromTi;

12. IfTi≠NULLthen

13. SortTiaccording to the order in Item-list;

14. Insert transactionTi;

end

算法2.挖掘強相關(guān)模式

輸入：UFPM樹，最小期望支持度閾值δ

輸出：加權(quán)強相關(guān)項集

begin

1. foreach itemα∈Item-list do

2.Pα= ProjectTree(UFPM-tree, α);

3. Mine(Pα,α,Item-listα,{α});

4. end

5. ProjectTree(UFPM-tree,α)

6. foreach nodeNα∈UFPM-tree do

7.pathα:=ProjectNα;

8. foreach nodePNα∈pathαdo

9. Calculate PNα·TpCapand PNα·pProxy∈projected treePα;

10. returnPα;

11. Mine(Pα,α,Item-listα,candidate) ;

12. Set candidate as candidate frequent itemset;

13. foreach β∈Item-listαdo

14. ifExpSuppCap(β)<δoruConfpCap(β)

then

15. PruneTree(β,Pα);

16. Item-listα=Item-listα-β;

17. ifPα≠NULLthen

18. foreach itemβ∈Item-listαdo;

19. nextCandidate=candidate∪β;

20.Pβ=ProjectTree(Pα,β);

21. Mine(Pβ,β,Item-listβ,nextcandidate);

22. PruneTree(β,Pα) ;

23. foreach nodeNβ∈Pαdo

24. ifNβ·parent≠NULL then

25. foreach st∈Nβdo

26.Nβ·parent:=Nβ·parent∪st;

27. Merge duplicate children;

28. DeleteNβ;

end

上述過程中，每一項α，投影樹Pα通過ProjectTree()構(gòu)建，從投影樹Pα中挖掘頻繁項集通過Mine()實現(xiàn).

5 實驗與分析

為驗證本文所提出方法的性能在，本實驗針對誤報數(shù)、產(chǎn)生模式數(shù)和運行時間與PUF-growth算法[12]進行對比實驗.數(shù)據(jù)集選用http://fimi.Ha.ac.be/data/上的mushroom，kosarak兩個真實數(shù)據(jù)集.其中mushroom是一個稠密數(shù)據(jù)集，有8124個事務(wù)，120個不同項；kosarak是一個稀疏數(shù)據(jù)集，有990002個事務(wù)，41270個不同項.在實驗中對事務(wù)中的每一個數(shù)據(jù)項按照正態(tài)分布的規(guī)律隨機生成一個概率值，并使該值的范圍是[0，1] .對于數(shù)據(jù)集中不同的項的權(quán)重賦值同樣采取上述方法.

實驗算法采用C++語言實現(xiàn)，電腦配置為Intel(R) Xeon(R) CPU E5-1607 V3 @3.10GHz 3.00GHz的處理器，8GB內(nèi)存，Microsoft Windows7操作系統(tǒng).實驗結(jié)果取自于多次運行的平均值，實驗中的UFPM樹均按照其期望支持度降序構(gòu)造，頻繁概率閾值τ均取值0.9.

本文所提UFPM-CM算法可以挖掘出強相關(guān)模式，但同類算法中僅僅只是挖掘不確定頻繁模式，所以當和PUF-growth算法[12]作對比時，置信度閾值均設(shè)為0.同時，實驗也取值驗證其算法相關(guān)性挖掘效果.

120010008006004002000誤報數(shù)202122232425最小支持度(%)PUFUFPMCMUFPMCMuConf06wUconf06--[ = . ,= . ]圖3 mushroom數(shù)據(jù)集中誤報數(shù)比較Fig.3 Number of false positives comparison for mushroom圖4 kosarak數(shù)據(jù)集中誤報數(shù)比較Fig.4 Number of false positives comparison for kosarak圖5 mushroom數(shù)據(jù)集中運行時間比較Fig.5 Running time comparison for mushroom

實驗1.誤報數(shù)的比較

由于算法中使用估計值代替實際期望支持度，勢必會產(chǎn)生一定誤報.實驗針對兩個真實數(shù)據(jù)集進行實驗，由于使用了pProxy值來計算邊界值，導致了一個更緊湊的限制，所以效果如圖3、圖4所示，證實了UFPM-CM算法產(chǎn)生了更少的誤報，且產(chǎn)生的誤報數(shù)隨著最小支持度的增加而減少.

實驗2.運行時間的比較.

從圖5、圖6可以看出，UFPM-CM算法挖掘頻繁項集的時間遠小于PUF算法，由于其產(chǎn)生了更少的誤報數(shù)來節(jié)省了運行時間.當給UFPM-CM算法加上兩個置信度uConf和wUConf時它會預(yù)先剪枝不相關(guān)模式，因為這兩個度量具有反單調(diào)性，并且值整合在了已經(jīng)構(gòu)造好的UFPM樹和相應(yīng)算法中，從而沒有額外的計算量.

實驗3.產(chǎn)生模式數(shù)的比較.

圖6 kosarak數(shù)據(jù)集中運行時間比較Fig.6 Running time comparison for kosarak圖7 mushroom數(shù)據(jù)集中模式數(shù)比較Fig.7 Number of patterns comparison for mushroom圖8 kosarak數(shù)據(jù)集中模式數(shù)比較Fig.8 Number of patterns comparison for kosarak

UFPM-CM算法與PUF算法在兩個真實數(shù)據(jù)集上運行產(chǎn)生模式數(shù)量如圖7、圖8所示，圖中可以看出，所產(chǎn)生的模式數(shù)明顯減少.其中，利用UFPM樹中pProxy度量值有效剪枝了非頻繁項集.當使用uConf和wUConf這兩個置信度時，將產(chǎn)生強相關(guān)的模式.

以上實驗證實，UFPM-CM算法利用UFPM樹高效地存儲了不確定數(shù)據(jù)庫，快速挖掘出較少、相關(guān)性強的頻繁模式且其效率優(yōu)于同類算法.

6 結(jié) 論

通過對不確定頻繁項挖掘的研究，本文提出了新的不確定模式樹UFPM-tree和對應(yīng)的UFPM-CM算法.深入研究項集之間的相關(guān)性和權(quán)重度量來發(fā)現(xiàn)有價值的相關(guān)模式，其中引入了uConf和wUConf兩個置信度來挖掘強相關(guān)模式.通過實驗證明，本文所提出的算法在誤報數(shù)的減少、運行時間和產(chǎn)生的模式數(shù)量上優(yōu)于其他同類算法.未來，UFPM-CM算法將探索挖掘其他類型的數(shù)據(jù)挖掘，例如網(wǎng)絡(luò)數(shù)據(jù)流等.