元組級不確定數據庫的Top-K概率頻繁項集挖掘

陳鳳娟，馬 愷

（遼寧對外經貿學院，遼寧 大連 116052）

1 引言

在越來越多的實際應用中，如無線傳感器網絡和RFID等環境下,數據采集設備獲得的數據是不確定數據,因此,數據庫存儲的數據也就具有了不確定性.不確定性數據有的是由于數據采集設備的精度不夠造成的,如無線傳感器網絡和RFID等,有的則是對某些原始數據進行綜合分析得到的,如對超市的購買記錄數據庫的顧客購買行為進行統計或對患者就醫記錄進行分析獲得疾病信息等[1].這些不確定數據一般采用不確定數據庫進行存儲和處理,采用數據挖掘方法來分析這些數據中隱含的有用的信息.

關聯規則是數據挖掘的一個重要研究內容,也是分析事務數據庫中數據之間隱含的規則的重要工具,它對分析數據和預測未來趨勢都有很重要的意義[2].頻繁項集挖掘,也稱為頻繁模式挖掘是關聯規則挖掘的第一步,也是最關鍵的步驟，它能找出數據庫中出現次數大于用戶給定的最小閾值的所有模式，稱為頻繁項集或頻繁模式.在不確定數據庫中挖掘概率頻繁項集能發現不確定數據庫中出現次數大于某個閾值的所有模式,但是,由于數據不確定性的存在,使得挖掘工作比確定數據庫中的頻繁模式挖掘更為復雜.由于挖掘概率頻繁模式時,需要用戶提供最小頻繁概率的閾值,增加了挖掘難度,因為,閾值的設置沒有統一的標準.當閾值設置過高時,挖掘到的結果基本都是已知的,參考價值不大,但是,若將閾值設置過低,則會導致挖掘結果太多,且挖掘時間太長.

為了解決這些問題,本文主要研究無需設置閾值的Top-K概率頻繁項集挖掘問題.為了分析問題和節省運算時間,本文主要研究在記錄級不確定數據庫中，挖掘頻繁概率值最高的K個概率頻繁項集,即Top-K概率頻繁項集挖掘問題.文中分析不確定數據庫的性質并給出了Top-K概率頻繁項集挖掘算法,在不確定數據庫上對算法進行仿真實驗，驗證了算法的性能.

2 不確定數據庫與概率頻繁項集

不確定數據庫一般是指包括概率信息(不確定信息)的數據庫，根據不確定信息(概率值)在數據庫中出現的位置的不同，可以將不確定數據庫劃分為記錄級的不確定數據庫和屬性級的不確定數據庫[3].如果在不確定數據庫中,概率信息是出現在每條記錄的最后,表示該條記錄在數據庫中出現的概率,那么,這個數據庫就是記錄級不確定數據庫.如果在不確定數據庫中，每條記錄中每個屬性的屬性值是不確定的,即概率信息出現在記錄中每個屬性值的后面,那么,這個數據庫就是屬性級不確定數據庫[4].如表1和表2所示,記錄級不確定數據庫的結構比屬性級不確定數據庫簡單,算法在計算頻繁模式時,需要計算的信息較少.本文主要探討記錄級不確定數據庫中的頻繁模式挖掘問題,但下面的定義也適應于屬性級不確定數據庫.

表1 記錄級不確定數據庫

表2 屬性級不確定數據庫

下面,采用可能世界語義來分析不確定數據庫.可能世界用所有記錄的不確定信息(等于每條記錄在數據庫中出現的概率乘以不出現的概率)來表示記錄的所有的出現與否的可能性大小[5].可能世界可以描述不確定數據庫的所有的可能情況，它的個數是按照指數增長的,因此,直接在可能世界上做挖掘,會產生巨大的計算量,算法的擴展性差.可能世界出現的概率大小,用其概率值表示,每個可能世界出現的概率等于出現的每條記錄的概率與不出現的每條記錄的概率的乘積,這樣,所有可能世界的概率之和等于1.根據可能世界的分析,對不確定數據庫中的頻繁模式挖掘,進行如下定義[6].

定義1假設D是一個記錄級的不確定數據庫,D的一個可能世界W是D的所有可能世界的一個子集.其中,每個可能世界的概率稱為PD(W),則PD(W)的定義用公式可以表示為PD(W)=∏(t,v)∈WD(t,v)(∏(t,v)∈T×VW(1-D(t,v))).

假設構成不確定數據庫的所有項的集合為I,那么I的任意一個非空子集稱為項集,項集中包含的項的個數稱為項集的長度.在確定數據庫中,一個項集的支持度是判斷項集是否是頻繁的主要標志,而絕對支持度就是該項集在數據庫中出現的總次數,相對支持度是該項集在數據庫中的出現次數與數據庫總記錄數的比值.假設X是不確定數據庫中的一個項集,那么項集X在不確定數據庫中的支持度用X在可能世界中的支持度來計算[7].項集X在一個可能世界中的支持度就是該可能世界中包含該項集的所有記錄的個數.任意一個項集在不確定數據庫中的支持度可以定義為該項集在所有可能世界中的支持度之和,而該項集是否是頻繁項集,也可以用這個不確定數據庫中的支持度來定義.由此,可以給出不確定數據庫中的期望支持度概念.

定義2在不確定數據庫D中，I是所有項的全集,X是I的一個任意非空子集,項集X的期望支持度是該項集在不確定數據庫的所有的可能世界中出現的概率之和，記為ESup(X)，即ESup(X)=∑t∈TP(X?t)=∑t∈T∏x∈XP(x?t).

在期望支持度定義下,可以給定一個不確定數據庫的最小期望支持度,用于挖掘不確定數據庫中的頻繁項集.為了更精確的計算不確定數據庫中的支持度,還可以用項集在所有可能世界中的離散概率分布來定義不確定數據庫中的支持度.任意一個項集在不確定數據庫中的概率支持度表示其在可能世界中的離散概率分布.

定義3給定一個不確定數據庫D和該數據庫的所有可能世界的集合W，所有的項的集合為I,任意一個項集X的支持度為i的概率稱為支持度概率Pi(X)，它等于項集X的所有支持度為i的可能世界的概率之和，即 Pi(X)=∑S(X,wj)=twj，其中，wj表示一個可能世界，S(X,wj)表示可能世界中，項集X的支持度，P(wj)表示可能世界wj的概率.

定義4對于一個不確定數據庫D和D中的任意一個項集X，給定一個最小支持度minSup(minSup∈{0,…,|T|})，X在所有可能世界中的支持度至少是minSup的概率稱為頻繁概率，記為P≥minsup(X)，則有

這樣,任意一個項集X的頻繁概率P≥minsup(X)就是該項集出現的頻繁程度的可能性大小，因此，可以用該項集的頻繁度判斷該項集是否是可能的頻繁項集,即候選項集.當用戶給定一個具體的閾值,最小頻繁概率,作為算法的參數時，就可以用下面的定義挖掘出概率頻繁項集.

定義5給定一個不確定數據庫D，所有的項的集合為I,由用戶定義的兩個閾值,最小支持度值minsup和最小頻繁概率閾值minfp.若任意一個項集X頻繁概率P≥minsup(X)大于等于用戶給定的最小頻繁概率閾值minfp，則項集X是概率頻繁項集,即P≥minsup(X)≥minsp.

由此,可以定義不確定數據庫中的概率頻繁項集挖掘問題.

定義6給定一個不確定數據庫D，所有的項的集合為I,由用戶定義的兩個閾值,最小支持度值minsup和最小頻繁概率閾值minfp.在D中發現所有頻繁概率大于最小頻繁概率的項集的挖掘就是不確定數據庫中的頻繁項集挖掘問題.

3 Top-K概率頻繁項集挖掘

根據記錄級不確定數據庫中,出現的項集的頻繁概率和用戶給定的最小頻繁概率的閾值，可以得到記錄級不確定數據庫中的所有概率頻繁項集.但是,不確定數據庫的概率頻繁項集的數量非常大,尤其是在閾值設置較低時,概率頻繁項集的數量更大.這樣,無論是直接分析概率頻繁項集還是用概率頻繁項集實現關聯規則分析,都會帶來不便.為了減少輸出的概率頻繁模式,可以采用僅挖掘頻繁概率最大的K個概率頻繁項集,為分析者提供最有參考價值的關系.

Top-K概率頻繁項集的挖掘比概率頻繁項集的挖掘過程更為復雜，不確定數據庫的UApriori和UFP-Growth等算法是對確定數據庫上的經典頻繁模式挖掘算法Apriori和FP-Growth在不確定數據庫中的擴展,而不確定數據庫的Top-K概率頻繁模式挖掘,也可以從確定數據庫的頻繁項集的挖掘算法上進行擴展.Top-K概率頻繁項集挖掘不同與概率頻繁項集挖掘之處在于當最小頻繁概率給定時,概率頻繁項集是固定的,而Top-K概率頻繁項集是隨著每次得到的最新的概率頻繁項集的頻繁概率影響的.當挖掘到新的概率頻繁項集時,原有的概率頻繁項集不變,但是,所有的概率頻繁項集的排名卻會發生變化.因此,相對于概率頻繁項集的挖掘,Top-K概率頻繁項集的挖掘重點在動態調整概率頻繁項集的排名,并僅保留對后續挖掘有用的概率頻繁模式,從而減少挖掘時間,提高挖掘效率.

記錄級不確定數據庫的Top-K概率頻繁項集的挖掘算法基于UApriori算法的框架,基本思想是在每次掃描數據庫時,挖掘出當前候選集,根據最小頻繁概率(初始設置為0),得到概率頻繁項集,然后對本次挖掘到的概率頻繁項集進行排序,并根據當前的排序結果,比較第K個概率頻繁項集的頻繁概率與最小頻繁概率,用二者中大的作為最新的閾值,再進入下一次對數據集的掃描和概率頻繁模式的挖掘,直到不再產生候選集為止.

在記錄級不確定數據庫中,頻繁項集的向下封閉的特性仍然成立,用定理1來描述這種性質.

定理1對于給定的記錄級不確定數據庫D,所有項的集合是I.假設A是任意給一個項集,即A是I的非空子集.項集B是A的一個非空子集.如果項集B的頻繁概率小于用戶定義的最小閾值,則項集A的頻繁概率也一定小于最小閾值.

證明由頻繁概率的概率可得,任意一個項集的頻繁概率等于包含該項集的記錄的概率之和.因此,若包含兩個項集的記錄的集合是包含關系,即包含二者之一的項集的所有記錄是包含另一個項集的所有記錄的子集,則對應記錄集合大的項集的頻繁概率高,另一個頻繁概率低.對于兩個具有包含關系的項集,A和B,包含二者的記錄集合只有兩種可能,一個是完全相等,一是包含關系,且包含父項集A的記錄集合是包含子項集B的記錄集合的子集.這樣,就有項集A的頻繁概率小于等于項集B的頻繁概率.因此,當項集B的頻繁概率小于用戶給定的最小閾值是,項集A的頻繁概率也一定小于最小閾值.

定理1給出了不確定數據庫中,父項集和子項集的頻繁概率的關系.同時,定理1也是生成候選集時的剪枝依據.當(n-1)項集的頻繁概率小于最小頻繁概率時,其父項集n項集的頻繁概率一定小于最小閾值.也就是說,一個(n-1)項集是非概率頻繁項集,則包含它的n項集也一定是非概率頻繁項集.因此,在生成候選集的時候可以不用考慮.

在本文的Top-K算法中,當挖掘出1項概率頻繁項集后,對其按照頻繁概率的降序進行排序,若生成的概率頻繁項集的個數不少于K個,則第K個概率頻繁項集的頻繁概率必定不小于最小頻繁概率.這樣,調整最小頻繁概率的值,用第K個概率頻繁項集的頻繁概率作為新的最小頻繁概率的閾值,進行2項候選集的生成.不斷重復該過程,就可以快速的得到Top-K概率頻繁項集.算法的具體描述如下.

Input:一個記錄級不確定數據庫D，用戶指定的K值

Output:Top-K概率頻繁項集

Begin

C0=? //概率頻繁項集的候選集合,初始為空

PK=? //Top-K概率頻繁項集的集合,初始為空

min_psup=0 //最小頻繁概率的初始值

掃描不確定數據庫,統計1項集的頻繁概率

對所有概率頻繁1項集按頻繁概率降序排列

PK={前K個概率頻繁項集}

min_psup=第K個概率頻繁項集的頻繁概率

Do while Cn-1≠?

用PK生成Cn候選集

for i=1 to|Cn|

掃描數據庫,計算候選集中項集X的頻繁概率

If候選集中的項集X的頻繁概率＞=min_psup then

Pk=PK∪{X}

End If

End For

對所有對概率頻繁n項集按頻繁概率降序排列

PK={前K個概率頻繁項集}

min_psup=第K個概率頻繁項集的頻繁概率

End Do

End

Top-K概率頻繁項集挖掘算法能挖掘頻繁概率最大的K個概率頻繁項集,但是由于向下封閉特性的存在,會導致這K個項集有一些是另一些的子集.例如,如果項集ABC是K個概率頻繁項集之一,那么,它的所有子集A,B,C,AB,AC,BC一定都包含在Top-K概率頻繁項集內.

4 實驗與性能分析

為了測試Top-K概率頻繁項集挖掘算法的性能，在記錄級不確定數據庫上使用該算法進行挖掘,并與UApriori算法進行比較,分析算法的性能.采用人工合成的方法生成實驗需要的記錄級不確定數據庫，合成方法分為兩個步驟.第一步，獲得確定數據庫，可以從FIMI’04數據集中獲得，如mushroom和connect等數據庫.第二步，為確定數據庫的每條記錄,增加一個概率,用于表示該記錄在數據庫中出現的可能性，為了保留數據庫中的頻繁項集，添加的概率服從正態分布.本文的實驗采用的確定數據庫是Mushroom和connect，為每條記錄增加的概率值為服從正態分布的均值為0.8，標準差為0.1的概率值.算法采用JAVA實現，在JDK環境下編譯運行，運行環境的硬件配置為Intel core i7 CPU，16G內存,操作系統為Win7.

圖1描述了算法的運行時間，圖中比較了在選取不同的K值時所花費的時間.很明顯,在K值越小時,算法運行時間越短.這是因為K值越小,每次調整的最小頻繁概率就越大,被剪枝的項集就越多,需要計算頻繁概率的候選項集就越少,因此運行時間短.

圖2對比了算法與UApriori算法的運行時間.由于UApriori算法的最小頻繁概率是固定的,因此,它的時間與最小頻繁概率閾值的設置有很大關系,當閾值設置很高時,用向下封閉的特性可以剪枝掉很多非頻繁的項集,因此算法的運行時間短,當閾值設置很低時,算法的運行時間很長,而Top-K的運行時間是受K值影響.為了對比二者的性能,將UApriori算法中的最小頻繁概率和Top-K算法的K值共同抽象為模擬參數,用1～5來表示該參數值的增加

圖1 Top-K算法的運行時間

圖2 Top-K與UApriori的比較

5 結束語

在記錄級不確定數據庫中挖掘Top-K概率頻繁項集能大大減少輸出的概率頻繁項集的個數,為很多應用提供有參考價值的信息，同時,算法的運行時間也較短.但是,Top-k挖掘到的K個項集,會出現多個子集與其父集均在挖掘結果中的情況,減少了用戶發現更多有意義的項集的機會,在未來的工作中,將會研究Top-K概率頻繁閉項集的挖掘.