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

陳鳳娟，馬 愷

（遼寧對外經(jīng)貿(mào)學(xué)院，遼寧 大連 116052）

1 引言

在越來越多的實(shí)際應(yīng)用中，如無線傳感器網(wǎng)絡(luò)和RFID等環(huán)境下,數(shù)據(jù)采集設(shè)備獲得的數(shù)據(jù)是不確定數(shù)據(jù),因此,數(shù)據(jù)庫存儲的數(shù)據(jù)也就具有了不確定性.不確定性數(shù)據(jù)有的是由于數(shù)據(jù)采集設(shè)備的精度不夠造成的,如無線傳感器網(wǎng)絡(luò)和RFID等,有的則是對某些原始數(shù)據(jù)進(jìn)行綜合分析得到的,如對超市的購買記錄數(shù)據(jù)庫的顧客購買行為進(jìn)行統(tǒng)計或?qū)颊呔歪t(yī)記錄進(jìn)行分析獲得疾病信息等[1].這些不確定數(shù)據(jù)一般采用不確定數(shù)據(jù)庫進(jìn)行存儲和處理,采用數(shù)據(jù)挖掘方法來分析這些數(shù)據(jù)中隱含的有用的信息.

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

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

2 不確定數(shù)據(jù)庫與概率頻繁項集

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Output:Top-K概率頻繁項集

Begin

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

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

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

掃描不確定數(shù)據(jù)庫,統(tǒng)計1項集的頻繁概率

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

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

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

Do while Cn-1≠?

用PK生成Cn候選集

for i=1 to|Cn|

掃描數(shù)據(jù)庫,計算候選集中項集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個概率頻繁項集,但是由于向下封閉特性的存在,會導(dǎo)致這K個項集有一些是另一些的子集.例如,如果項集ABC是K個概率頻繁項集之一,那么,它的所有子集A,B,C,AB,AC,BC一定都包含在Top-K概率頻繁項集內(nèi).

4 實(shí)驗與性能分析

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

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

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

圖1 Top-K算法的運(yùn)行時間

圖2 Top-K與UApriori的比較

5 結(jié)束語

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