陳鳳娟（遼寧對外經(jīng)貿(mào)學(xué)院基礎(chǔ)課教研部　遼寧大連　116052）

?

不確定數(shù)據(jù)庫頻繁項集挖掘算法研究

陳鳳娟
（遼寧對外經(jīng)貿(mào)學(xué)院基礎(chǔ)課教研部遼寧大連116052）

摘要：在不確定數(shù)據(jù)庫中，一個項集的支持度不再是一個出現(xiàn)次數(shù)的累計，而是一個隨機變量。因此，不像確定數(shù)據(jù)庫中頻繁項集有一個特定的定義，在不確定數(shù)據(jù)環(huán)境下，頻繁項集有兩種不同的定義。根據(jù)這兩種定義，現(xiàn)有的頻繁項集挖掘工作被分成了兩類。文章主要比較這兩種不同的定義以及在這些定義基礎(chǔ)上提出的挖掘算法。

關(guān)鍵詞：不確定數(shù)據(jù)庫；期望支持度；頻繁概率；頻繁項集

在設(shè)計挖掘不確定數(shù)據(jù)庫中的頻繁項集的算法之前，如何定義頻繁項集是最重要的問題。在確定數(shù)據(jù)庫中，只要一個項集的支持度或頻度不小于一個用戶給定的最小支持度minsup，那么這個項集就是頻繁的。因此，一個項集是否是頻繁的是很明確的一件事。但是在不確定數(shù)據(jù)庫中，情況就不同了。在不確定數(shù)據(jù)庫中，一個項集是頻繁的有兩種不同的語義解釋，一個是基于期望支持度的頻繁項集，一個是概率頻繁項集。這兩種解釋都把項集的支持度看成一個離散的隨機變量，但是，二者在使用隨機變量來定義頻繁項集的方法是不同的。

一、不確定數(shù)據(jù)庫

不確定數(shù)據(jù)庫就是在數(shù)據(jù)庫中包括不確定信息的數(shù)據(jù)庫，根據(jù)不確定信息存在的位置不同，可以分為屬性級不確定數(shù)據(jù)庫和記錄級不確定數(shù)據(jù)庫。

在屬性級不確定模型中，每一個屬性值都由一些不確定的信息給出。假設(shè)一個數(shù)據(jù)庫D包含n條記錄，每一條記錄都是由一些項組成的集合，而項的全集記為V。出現(xiàn)在記錄tj中的V中的任意一個項v，都有一個存在概率Pr與之對應(yīng)，這個概率表示的是項v屬于記錄tj的可能性大小，如表1所示。

表1屬性級不確定數(shù)據(jù)庫

記錄級不確定模型中，每個記錄與一個概率值相關(guān)聯(lián)，即一組項的集合有一個概率。假設(shè)有數(shù)據(jù)庫D，其中每個記錄都是一組項的集合，并且每個記錄都有一個存在概率，表示該記錄在數(shù)據(jù)庫D中出現(xiàn)的可能性大小，如表2所示。與屬性級不確定數(shù)據(jù)庫相比，記錄級不確定數(shù)據(jù)庫更簡單[1]。

無論是屬性級不確定數(shù)據(jù)庫還是記錄級不確定數(shù)據(jù)庫，都可以用可能世界語義來分析?？赡苁澜绺鶕?jù)每個項或每個記錄在數(shù)據(jù)庫中出現(xiàn)的概率，可以計算得到其不出現(xiàn)的概率，用所有項或記錄的出現(xiàn)概率和不出現(xiàn)的概率的乘積可以表示所有的可能性?？赡苁澜绫硎玖瞬淮_定事務(wù)數(shù)據(jù)庫的所有可能出現(xiàn)的情況，屬性級不確定數(shù)據(jù)庫，總共有2|T|*|V|個可能世界，其中|T|是記錄的總數(shù)，|V|是項的總數(shù)，而對于記錄級不確定數(shù)據(jù)庫，則有2|T|個可能世界，其中|T|是記錄的總數(shù)。在這種假設(shè)下，不同項的出現(xiàn)和不出現(xiàn)在統(tǒng)計上是獨立的。每個可能世界的概率可以用項集中每個單獨的項的概率相乘得到，而所有可能世界的概率和為1。因此，可以把記錄級不確定數(shù)據(jù)庫看做屬性級不確定數(shù)據(jù)庫的特例。下面以屬性級不確定數(shù)據(jù)庫為例來分析問題。

表2記錄級不確定數(shù)據(jù)庫

設(shè)T是一組不同記錄的集合，I是一組項的集合。一個不確定數(shù)據(jù)庫D是一個從T×I到區(qū)間[0,1]的函數(shù)。不確定數(shù)據(jù)庫D的一個可能世界W是T×I的一個子集。每個可能世界的概率PD(W)定義為。

設(shè)WD表示不確定數(shù)據(jù)庫D的所有可能世界的集合。

一個項集X在一個可能世界W中的支持度定義為W中包含X的記錄的個數(shù)，PD描述了不確定數(shù)據(jù)庫的所有可能世界上的概率分布。在所有的可能世界中，我們不知道哪個可能世界是真正發(fā)生的，因此，PD表明了某個可能世界真正發(fā)生的概率。

二、期望支持度及其挖掘算法

設(shè)I={i1,i2,…,in}是一個不同項的集合，X是I的一個非空子集。用X=x1x2…xm表示項集X={x1,x2,…,xm}。如果X有m個項，則稱X是一個m-項集。給定一個不確定數(shù)據(jù)庫UDB，每個記錄都可以表示為一個元組，其中tid是記錄的標(biāo)識，Y={y1(p1),y2(p2),…,ym(pm)}。Y包括m個元素，每個元素有一個項yi和一個概率pi，表示項yi在第tid個元組中出現(xiàn)的可能性大小。在UDB中包含項集X的記錄的個數(shù)是一個隨機變量，表示為sup(X)[2]。

期望支持度。給定一個包含N條記錄的不確定事務(wù)數(shù)據(jù)庫UDB，對于任意一個項集X，X的期望支持度是：

基于期望支持度的頻繁項集。給定一個包含N條記錄的不確定事務(wù)數(shù)據(jù)庫UDB，一個最小期望支持度閾值，min_esup，一個項集X是一個基于期望概率的頻繁項集當(dāng)且僅當(dāng)X的期望支持度大于等于N倍的最小期望支持度閾值，即esup(X)≥N×min_esup。

最具有代表性的基于期望支持度的頻繁項集挖掘算法主要有三個，它們是UApriori，UFP-growth和UH-Mine。其中，UApriori算法基于生成測試框架，使用寬度優(yōu)先的搜索策略。其他兩個算法基于分治框架，使用深度優(yōu)先的搜索策略。盡管在確定數(shù)據(jù)庫中，Apriori算法比其他兩個算法慢，但是它在不確定數(shù)據(jù)中的擴(kuò)展算法UApriori算法在這三個算法中效率很好，并且在稠密數(shù)據(jù)庫中效果最好。

UApriori算法是Chui等人在2007年提出的一個Apriori擴(kuò)展算法，它把經(jīng)典的Apriori算法推廣到了不確定數(shù)據(jù)環(huán)境，使用生成-測試框架發(fā)現(xiàn)所有的基于期望支持度的頻繁項集。UApriori算法首先找到所有基于期望支持度的單個頻繁項，然后重復(fù)加入基于期望支持度的頻繁i-項集，生成i+1項候選集，再測試i+1項候選集，得到基于期望支持度的頻繁i+1項集。最后，當(dāng)沒有頻繁項集生成時結(jié)束算法。

在不確定數(shù)據(jù)庫中，向下封閉性質(zhì)仍然成立。這樣，當(dāng)測試一個項集是否是基于期望支持度的頻繁項集時，傳統(tǒng)的Apriori剪枝策略仍然適應(yīng)。也就是說，如果一個項集不是基于期望支持度的頻繁項集，那么這個項集的所有超集也一定不是基于期望支持度的頻繁項集。另外，還有一些對數(shù)衰減的剪枝方法來進(jìn)一步提高算法的效率，這些方法主要目標(biāo)是盡快找到一個項集的期望支持度的上界。一旦這個上界小于最小期望支持度閾值，那么就可以用傳統(tǒng)的Apriori剪枝技術(shù)，刪除這個項集及其所有的超集。但是，這個對數(shù)衰減剪枝方法依靠數(shù)據(jù)集的數(shù)據(jù)結(jié)構(gòu)，這樣，在UApriori中最重要的剪枝方法仍然是傳統(tǒng)的Apriori剪枝[3]。

UFP-growth算法是從一個確定數(shù)據(jù)庫中最有名的模式挖掘算法，F(xiàn)P-growth算法，擴(kuò)展得到的。類似于傳統(tǒng)的FP-growth算法，UFP-growth算法也是先建立一個索引樹，稱為UFP-tree，來存儲不確定數(shù)據(jù)庫中的所有信息。然后，基于UFP-tree結(jié)構(gòu)，UFP-growth算法遞歸地建立條件子樹，并發(fā)現(xiàn)基于期望支持度的頻繁項集。

在建立UFP-tree的過程中，首先找出所有基于期望支持度的單個頻繁項，然后依據(jù)這些單個項的期望支持度大小對它們進(jìn)行排序。由這些排好序的單個項，把每個記錄重新排序，然后把這些記錄插入到UFP-tree中。在UFP-tree中，每個結(jié)點包括三個值。第一個值是項的標(biāo)簽，第二個值是這個項出現(xiàn)的概率，第三個值是該項從根結(jié)點到該結(jié)點共享的個數(shù)，即出現(xiàn)的次數(shù)。與傳統(tǒng)的FP-tree不同，UFP-tree的壓縮效果顯著的降低。在UFP-tree中，必須是項的標(biāo)簽和其概率值都相同時，才能共享一個結(jié)點，否則，標(biāo)簽相同的項也必須作為兩個不同的結(jié)點[4]。

UH-Mine算法也是基于分治框架的深度優(yōu)先搜索算法，它是H-Mine算法在不確定數(shù)據(jù)庫中的擴(kuò)展，而H-Mine算法特別適合稀疏數(shù)據(jù)庫。H-Mine算法首先掃描不確定數(shù)據(jù)庫，找到所有基于期望支持度的單個頻繁項，然后建立一個頭表，用來保存所有的單個頻繁項。對于其中的每個項，頭表存儲三個元素，項的標(biāo)簽，項的期望支持度和一個指針域。建立好頭表后，H-Mine算法把所有的記錄插入到一個新的數(shù)據(jù)結(jié)構(gòu)，UH-Struct結(jié)構(gòu)中。在UH-Struct結(jié)構(gòu)中，每個項是仍然包括三部分，項的標(biāo)簽，項的期望支持度和一個指針域。算法遞歸的建立不同前綴的頭表，生成所有的基于期望支持度的頻繁項集。

三、頻繁概率及其挖掘算法

對于不確定數(shù)據(jù)庫，頻繁概率是一個不同于期望支持度的定義。

頻繁概率。給定一個包含N條記錄的不確定事務(wù)數(shù)據(jù)庫UDB，一個最小期望支持度閾值，min_esup，對于任意一個項集X，X的頻繁概率，Pr(X)等于

概率頻繁項集。給定一個包含N條記錄的不確定事務(wù)數(shù)據(jù)庫UDB，一個最小期望支持度閾值，min_esup，一個概率頻繁閾值pft，如果一個項集X的頻繁概率大于概率頻繁閾值pft，則項集X是一個概率頻繁項集，即

兩個代表性的概率頻繁項集的挖掘算法是基于動態(tài)規(guī)劃的Apriori算法DP和基于分治的Apriori算法DC。精確的概率頻繁項集挖掘算法首先計算或估計每個項集的頻繁概率，然后僅僅返回頻繁概率大于給定概率閾值的項集及其具體的頻繁概率。因為頻繁概率的計算比期望支持度要復(fù)雜得多，因此，對一個項集是否是概率頻繁項集進(jìn)行一下快速的估計能提高算法的效率。所以，一個基于概率尾不等式的剪枝策略，Chernoff邊界剪枝策略，成為了提高概率頻繁項集挖掘算法效率的一個重要工具[5]。

在概率頻繁項集的定義下，計算項集的頻繁概率是影響算法效率的關(guān)鍵問題。在DP算法中，采用了動態(tài)規(guī)劃方法，通過把頻繁概率的公式轉(zhuǎn)換成，并且有P≥0，j(X)=1,0≤j≤|T|，P≥I，j(X)=0,∨i＞j，來實現(xiàn)動態(tài)規(guī)劃。

在DC算法中，采用分治方法，把不確定數(shù)據(jù)庫劃分成兩個子數(shù)據(jù)庫，然后在兩個子數(shù)據(jù)庫中，算法遞歸地調(diào)用自己把每個子數(shù)據(jù)庫再劃分成兩個子數(shù)據(jù)庫，直到子數(shù)據(jù)庫中只有一條記錄為止。然后算法統(tǒng)計項集在這個記錄中支持度的概率分布，最后，通過合并步驟，在算法結(jié)束時，獲得該項集支持度的整個的概率分布。如果DC算法僅有上述的分治步驟，那么它計算頻繁概率的時間復(fù)雜度同DP一樣，也是O (N2)，其中，N是不確定數(shù)據(jù)庫中記錄的個數(shù)。但是，在合并步驟中，DC算法可以使用快速傅里葉變換方法來加速算法，最后得到的時間復(fù)雜度是O(NlogN)。在大多數(shù)情況下，DC算法要優(yōu)于DP算法。

四、結(jié)語

由于現(xiàn)有的不確定數(shù)據(jù)庫中的頻繁項集挖掘有兩種定義方法，因此，現(xiàn)存的研究也被分為了兩類，基于這兩種定義發(fā)展了很多挖掘方法。在今后的研究中，可以探討這兩種定義之間的聯(lián)系。

參考文獻(xiàn)：

[1]L. Wang, D.W. Cheung,R. Cheng, etc. Efficient mining of frequent itemsets on large uncertain databases [J]. IEEE Transactions on Knowledge and Data Engineering, 2011,23(3): 367～381.

[2]C. Aggarwal, P. Yu. A survey of uncertain data algorithms and applications [J]. IEEE Transactions on Knowledge and Data Engineering, 2009,21(5): 609～623.

[3]蔣濤,高云君,張彬等.不確定數(shù)據(jù)查詢處理[J].電子學(xué)報,2013,41(5):966～976.

[4]李建中,于戈,周傲英.不確定性數(shù)據(jù)管理的要求與挑戰(zhàn)[J].中國計算機學(xué)會通訊,2009,5(4):6～14.

[5]C. Chui, B. Kao, E. Hung. Mining frequent itemsets from uncertain data [C]//The Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD). Berlin Heidelberg: Springer-verlag,2007:47～58.

[責(zé)任編輯鄭麗娟]

中圖分類號：TP311

文獻(xiàn)標(biāo)識碼：A

文章編號：2095- 0438（2016）05- 0149- 03

收稿日期：2016-01-10

作者簡介：陳鳳娟（1979－），女，遼寧本溪人，遼寧對外經(jīng)貿(mào)學(xué)院基礎(chǔ)課教研部副教授，碩士，研究方向：數(shù)據(jù)挖掘、無線傳感器網(wǎng)絡(luò)。