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

陳鳳娟，馬 愷

（遼寧對(duì)外經(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ù)庫存儲(chǔ)的數(shù)據(jù)也就具有了不確定性.不確定性數(shù)據(jù)有的是由于數(shù)據(jù)采集設(shè)備的精度不夠造成的,如無線傳感器網(wǎng)絡(luò)和RFID等,有的則是對(duì)某些原始數(shù)據(jù)進(jìn)行綜合分析得到的,如對(duì)超市的購買記錄數(shù)據(jù)庫的顧客購買行為進(jìn)行統(tǒng)計(jì)或?qū)颊呔歪t(yī)記錄進(jìn)行分析獲得疾病信息等[1].這些不確定數(shù)據(jù)一般采用不確定數(shù)據(jù)庫進(jìn)行存儲(chǔ)和處理,采用數(shù)據(jù)挖掘方法來分析這些數(shù)據(jù)中隱含的有用的信息.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 Top-K概率頻繁項(xiàng)集挖掘

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

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

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

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

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

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

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

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

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

Output:Top-K概率頻繁項(xiàng)集

Begin

C0=? //概率頻繁項(xiàng)集的候選集合,初始為空

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

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

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

對(duì)所有概率頻繁1項(xiàng)集按頻繁概率降序排列

PK={前K個(gè)概率頻繁項(xiàng)集}

min_psup=第K個(gè)概率頻繁項(xiàng)集的頻繁概率

Do while Cn-1≠?

用PK生成Cn候選集

for i=1 to|Cn|

掃描數(shù)據(jù)庫,計(jì)算候選集中項(xiàng)集X的頻繁概率

If候選集中的項(xiàng)集X的頻繁概率＞=min_psup then

Pk=PK∪{X}

End If

End For

對(duì)所有對(duì)概率頻繁n項(xiàng)集按頻繁概率降序排列

PK={前K個(gè)概率頻繁項(xiàng)集}

min_psup=第K個(gè)概率頻繁項(xiàng)集的頻繁概率

End Do

End

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

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

為了測(cè)試Top-K概率頻繁項(xiàng)集挖掘算法的性能，在記錄級(jí)不確定數(shù)據(jù)庫上使用該算法進(jìn)行挖掘,并與UApriori算法進(jìn)行比較,分析算法的性能.采用人工合成的方法生成實(shí)驗(yàn)需要的記錄級(jí)不確定數(shù)據(jù)庫，合成方法分為兩個(gè)步驟.第一步，獲得確定數(shù)據(jù)庫，可以從FIMI’04數(shù)據(jù)集中獲得，如mushroom和connect等數(shù)據(jù)庫.第二步，為確定數(shù)據(jù)庫的每條記錄,增加一個(gè)概率,用于表示該記錄在數(shù)據(jù)庫中出現(xiàn)的可能性，為了保留數(shù)據(jù)庫中的頻繁項(xiàng)集，添加的概率服從正態(tài)分布.本文的實(shí)驗(yàn)采用的確定數(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)行時(shí)間，圖中比較了在選取不同的K值時(shí)所花費(fèi)的時(shí)間.很明顯,在K值越小時(shí),算法運(yùn)行時(shí)間越短.這是因?yàn)镵值越小,每次調(diào)整的最小頻繁概率就越大,被剪枝的項(xiàng)集就越多,需要計(jì)算頻繁概率的候選項(xiàng)集就越少,因此運(yùn)行時(shí)間短.

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

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

圖2 Top-K與UApriori的比較

5 結(jié)束語

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