不確定數據庫頻繁項集挖掘算法研究

陳鳳娟（遼寧對外經貿學院基礎課教研部　遼寧大連　116052）

?

不確定數據庫頻繁項集挖掘算法研究

陳鳳娟
（遼寧對外經貿學院基礎課教研部遼寧大連116052）

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

關鍵詞：不確定數據庫；期望支持度；頻繁概率；頻繁項集

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

一、不確定數據庫

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

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

表1屬性級不確定數據庫

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

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

表2記錄級不確定數據庫

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

設WD表示不確定數據庫D的所有可能世界的集合。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、結語

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

參考文獻：

[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]蔣濤,高云君,張彬等.不確定數據查詢處理[J].電子學報,2013,41(5):966～976.

[4]李建中,于戈,周傲英.不確定性數據管理的要求與挑戰(zhàn)[J].中國計算機學會通訊,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.

[責任編輯鄭麗娟]

中圖分類號：TP311

文獻標識碼：A

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

收稿日期：2016-01-10

作者簡介：陳鳳娟（1979－），女，遼寧本溪人，遼寧對外經貿學院基礎課教研部副教授，碩士，研究方向：數據挖掘、無線傳感器網絡。