不確定數(shù)據(jù)集的模式挖掘

陳鳳娟

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

不確定數(shù)據(jù)集的模式挖掘

陳鳳娟

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

在傳統(tǒng)的事務(wù)數(shù)據(jù)庫中，頻繁模式的挖掘是一個已經(jīng)有很多較好解決辦法的問題，但是在不確定數(shù)據(jù)集上，僅僅提出了幾種頻繁模式的挖掘技術(shù)，而這些新技術(shù)對于不確定數(shù)據(jù)集中的項的不確定性的處理效果不是很好.本文主要探討在可能世界的概念下，用基于抽樣的方法來處理不確定數(shù)據(jù)，并在此基礎(chǔ)上，研究在保證較低的精度損失下優(yōu)化頻繁模式挖掘算法.

不確定數(shù)據(jù)集，模式挖掘，期望支持度

0 引 言

關(guān)聯(lián)規(guī)則分析是數(shù)據(jù)挖掘的最重要工作之一，它最早的應(yīng)用在購物籃分析中.一個事務(wù)數(shù)據(jù)集包含很多的事務(wù)，而每一個事務(wù)由多個項組成，每個項表示一個顧客在每次購物中購買的商品[1].事務(wù)數(shù)據(jù)庫被用來發(fā)現(xiàn)不同項集之間的關(guān)聯(lián)，以便發(fā)現(xiàn)顧客的購買規(guī)律，為銷售商的銷售決策提供建議.關(guān)聯(lián)規(guī)則分析的一個最關(guān)鍵、最重要的步驟就是挖掘頻繁模式.

在頻繁模式挖掘中，事務(wù)數(shù)據(jù)集通常用一個二元矩陣來表示，其中，矩陣的每一行表示一個事務(wù)，而每一列表示事務(wù)中出現(xiàn)的一個項.矩陣中的一個元素Mij的值是1或0，分別表示項j在事務(wù)i中出現(xiàn)和不出現(xiàn).在這種基本的事務(wù)數(shù)據(jù)模型中，一個項在一個事務(wù)中，要么出現(xiàn)，要么不出現(xiàn)，沒有其他可能.相對于不確定數(shù)據(jù)集，這種數(shù)據(jù)庫也稱為確定數(shù)據(jù)庫.在確定數(shù)據(jù)庫中挖掘頻繁模式的方法已經(jīng)提出了很多，它們使用多種方法對事務(wù)數(shù)據(jù)庫進(jìn)行模式挖掘.

但是，在很多應(yīng)用中，一個項在一個事務(wù)中不是出現(xiàn)或不出現(xiàn)，而是用一個存在概率來表示該項在該事務(wù)中出現(xiàn)的可能性大小.例如，實驗測量搜集的數(shù)據(jù)，或用傳感器采集的數(shù)據(jù)，它們都存在著不確定性.從這類具有不確定數(shù)據(jù)中挖掘頻繁模式是比從傳統(tǒng)的確定事務(wù)數(shù)據(jù)庫中挖掘頻繁模式要困難的工作.因為，對于每個項，我們無法確定它在數(shù)據(jù)集中是否出現(xiàn)，只知道其出現(xiàn)的可能性大小.如果把原來的二元矩陣變成一個概率矩陣，即原來用0或1表示項的出現(xiàn)情況，現(xiàn)在用其對應(yīng)的概率值來表示，把這種矩陣模型稱為不確定數(shù)據(jù)模型.

本文主要研究從不確定數(shù)據(jù)集中挖掘頻繁模式的方法，根據(jù)由項在事務(wù)中出現(xiàn)的可能性組成的矩陣，由統(tǒng)計學(xué)的一些概率分布規(guī)律，探討在抽樣的基礎(chǔ)上，挖掘出不確定事務(wù)數(shù)據(jù)集中的頻繁模式，并盡量控制由抽樣導(dǎo)致的數(shù)據(jù)精確度降低問題，保證算法的效率的同時，也不降低挖掘結(jié)果的精確度.

1 可能世界與期望支持度

在確定數(shù)據(jù)庫中，項在事務(wù)中出現(xiàn)的個數(shù)可以用支持度來表示，只要對數(shù)據(jù)庫進(jìn)行一次掃描，就能統(tǒng)計出項的支持度.而在不確定數(shù)據(jù)集中，無法明確的知道項是出現(xiàn)還是不出現(xiàn)，因此，原有的計數(shù)方式就無法使用了.在項的統(tǒng)計獨(dú)立假設(shè)的前提下，數(shù)據(jù)集中所有事務(wù)的項可以用新的計數(shù)方法來表示，即期望支持度，它是基于可能世界對于不確定數(shù)據(jù)庫的解釋得出的支持度.

對于任意給定的一個項x和每一個事務(wù)t，存在兩個可能世界的集合，一個集合中的所有可能世界，x在t中出現(xiàn)，另一個可能世界的集合中，x在t中不出現(xiàn).第一類可能世界的集合的概率由x在t中出現(xiàn)的存在概率P(x,t)來給出，而另一類可能世界的集合的概率由1-P(x,t)來給出.一個單個的可能世界的概率P(W)是通過將該世界中所有的項的存在概率與該世界中不存在的項的1-其存在概率相乘得到的[2].

通過不確定數(shù)據(jù)和可能世界的分析，可以用可能世界來表示項集X的支持度.給定一個可能世界Wi和一個項集X，定義P(Wi)是可能世界Wi的概率，而S(X,Wi)是項集X在可能世界Wi中的支持度，Ti,j表示可能世界Wi中的第j條記錄Tj包含的項集.假設(shè)記錄中的項的概率是通過獨(dú)立觀察得到的，那么可能世界Wi的概率和項集X的期望支持度可以通過下面的兩個公式得到.

(1)

(2)

其中，W是從不確定數(shù)據(jù)集D得到的所有可能世界的集合.

使用上面的公式來計算Se(X)需要窮舉所有的可能世界，并計算項集X在所有可能世界中的支持度.因為可能世界的個數(shù)是2m，其中，m是不確定數(shù)據(jù)庫D中所有記錄中出現(xiàn)的所有項的總和，所以用這個公式來計算Se(X)是不可行的.因此，可以用下面的公式來計算Se(X)[3].

(3)

2 不確定數(shù)據(jù)集的抽樣

為了分析不確定數(shù)據(jù)集，首先把不確定數(shù)據(jù)集與抽樣建立聯(lián)系，這種聯(lián)系是依據(jù)數(shù)據(jù)集中給定的存在概率來建立的.對于每個事務(wù)t和事務(wù)t中的每個項i，生成一個獨(dú)立的隨機(jī)數(shù)r，并且r∈[0,1]，然后把r和項i的概率值p進(jìn)行比較.如果p≥r，那么項i就在當(dāng)前的抽樣事務(wù)中出現(xiàn)，否則，項i在當(dāng)前的抽樣事務(wù)中就不出現(xiàn).對于不確定數(shù)據(jù)集中的每一條事務(wù)，重復(fù)上面的步驟n次，n是給定的一個常數(shù).這樣得到的數(shù)據(jù)集就是一個確定數(shù)據(jù)集，就可以使用現(xiàn)有的確定數(shù)據(jù)集的挖掘方法來挖掘.但是為了估計一個項集在不確定數(shù)據(jù)集中的支持度，由上面方法得到的抽樣數(shù)據(jù)集中，該項集的支持度計數(shù)需要除以n.

這種抽樣的方法物理上實例化了不確定數(shù)據(jù)集，并對其進(jìn)行存儲，但是在實例化的過程中，把該數(shù)據(jù)集放大了n倍，這樣就需要更多的存儲空間.但是，對于大多數(shù)有效的模式挖掘算法，不需要去實現(xiàn)這個抽樣數(shù)據(jù)集.畢竟，大多數(shù)有效的技術(shù)只從磁盤讀取數(shù)據(jù)集一次，之后，可以用高效的數(shù)據(jù)結(jié)構(gòu)把數(shù)據(jù)集放入內(nèi)存.所以，在數(shù)據(jù)集首次從磁盤讀入內(nèi)存時，可以立即在內(nèi)存中生成抽樣[4].

E[S]=expSup(X)

因此，和S是期望支持度的一個近似的無偏估計，并且其方差隨n值的增加而線性遞減.使用Hoeffding不等式，可以得到給定誤差率時，需要抽樣的數(shù)據(jù)集的個數(shù)，即n的個數(shù).當(dāng)數(shù)據(jù)集D包含10萬條概率事務(wù)時，對于一個項集X，為了獲得99%的X支持度的近似值，即只有1%的誤差，我們需要近似抽樣一個數(shù)據(jù)集D的實例.

3 頻繁模式挖掘

在傳統(tǒng)的確定數(shù)據(jù)庫中，有多種有效的技術(shù)可以挖掘頻繁模式，其中，F(xiàn)P-Tree采用了前綴樹的結(jié)構(gòu)存儲事務(wù)，并使用前綴樹結(jié)構(gòu)提出了PF-Growth[5]算法，而hyper-linkedarray結(jié)構(gòu)被用于構(gòu)造H-mine算法[6]，最簡單應(yīng)用也最廣的是Apriori算法，它采用寬度優(yōu)先的方法，思路簡單，不需要額外的存儲結(jié)構(gòu).但是這些方法都不能直接應(yīng)用于不確定數(shù)據(jù)集.因此，不確定數(shù)據(jù)集上的頻繁模式挖掘需要在原有的傳統(tǒng)的方法的基礎(chǔ)上進(jìn)行改進(jìn)，以實現(xiàn)對概率模型數(shù)據(jù)的挖掘.

U-Apriori是一個基于Apriori算法的不確定數(shù)據(jù)集頻繁模式挖掘算法，但是由于它在生成候選集和對候選集進(jìn)行測試時，需要不斷的掃描數(shù)據(jù)集，因此算法的可擴(kuò)展性不是很好.UCP-Apriori算法是基于增量剪枝技術(shù)的算法，它在掃描數(shù)據(jù)集時動態(tài)地構(gòu)成一個支持度的上界并不斷的更新這個上界.只要項集的最大的可能值低于閾值，這個項集就被剪枝[7].這種方法提高了Apriori類的不確定頻繁模式挖掘的效率.

UF-growth算法是擴(kuò)展FP-growth算法而來的不確定數(shù)據(jù)中的頻繁模式挖掘算法.它基于一種類似FP-tree的結(jié)構(gòu)UF-tree數(shù)據(jù)結(jié)構(gòu)，把不確定數(shù)據(jù)集用該結(jié)構(gòu)進(jìn)行存儲.在UF-tree結(jié)構(gòu)中，只有當(dāng)一個事務(wù)中的項和項的期望支持度都與樹中的結(jié)點(diǎn)相同，二者才合并為一個結(jié)點(diǎn)，這就導(dǎo)致UF-tree的樹結(jié)構(gòu)的壓縮性很差[8].提高樹的存儲壓縮性，可以用離散化期望支持度來避免很多不同的期望支持度.另外，還有一些擴(kuò)展已有的經(jīng)典頻繁模式挖掘算法，來實現(xiàn)對不確定數(shù)據(jù)集的頻繁模式挖掘的方法，如UH-mine算法.這些算法仍然存在它們在確定數(shù)據(jù)庫中存在的問題，而且，在不確定數(shù)據(jù)集中，計算量要遠(yuǎn)遠(yuǎn)大于確定數(shù)據(jù)集.

根據(jù)抽樣的方法，可以把Eclat算法修改為U-Eclat算法[9]，實現(xiàn)對不確定數(shù)據(jù)集的模式挖掘.U-Eclat算法基于Eclat算法，在第一次掃描數(shù)據(jù)集時，相關(guān)的項及其出現(xiàn)的事務(wù)表都被存儲在內(nèi)存，稱為tid-list結(jié)構(gòu).然后用深度優(yōu)先搜索策略生成候選集，并通過對它們子集的tid-list進(jìn)行交運(yùn)算，得到它們的支持度.U-Eclat算法的擴(kuò)展主要在于讀不確定數(shù)據(jù)集中的事務(wù)然后把它們按照抽樣的方法進(jìn)行實例化.具體地說，就是給定一個具體的n值，對每條事務(wù)t和事務(wù)中的每個項i，生成n個在0和1之間的獨(dú)立隨機(jī)變量，然后把這n個隨機(jī)變量與項i的概率值p相比較，如果該隨機(jī)變量大于概率p，則該事務(wù)出現(xiàn)在項i的tid-list中，如果該隨機(jī)變量不大于概率值p，則該事務(wù)不出現(xiàn)在項i的tid-list中.得到新的抽樣數(shù)據(jù)集后，就在上面運(yùn)行Eclat算法，挖掘出頻繁模式.

4 結(jié)束語

不確定數(shù)據(jù)集中的頻繁模式挖掘是很多數(shù)據(jù)挖掘工作的基礎(chǔ)，采用抽樣的方法實例化不確定數(shù)據(jù)集，能保證挖掘需要的精度，同時不需要對已有的傳統(tǒng)算法進(jìn)行大量的修改，減少了算法的計算工作量.

[1]AgrawalR,ImielinskiT,SwamiAN.Miningassociationrulesbetweensetsofitemsinlargedatabases[M].SIGMOD, 1993.

[2]BenjellounO,SarmaAD.ULDBs:Databaseswithuncertaintyandlineage[M].VLDB, 2006.

[3]ChuiC,KaoB,HungE.“Miningfrequentitemsetsfromuncertaindata[M].PAKDD, 2007.

[4]CaldersT,GarboniC,GoethalsB.Efficientpatternminingofuncertaindatawithsampling[M].PAKDD, 2010.

[5]HanJ,PeiJ,YinY.Miningfrequentpatternswithoutcandidategeneration[M].SIGMOD, 2000.

[6]AggarwalC,LiY,WangJ.Frequentpatternminingwithuncertaindata[M].KDD, 2009.

[7]ChuiC,KaoB.Adecrementalapproachforminingfrequentitemsetsfromuncertaindata[M].PAKDD, 2008.

[8]AggarwalC,YuP.Asurveyofuncertaindataalgorithmsandapplications[J].IEEETKDE, 2009,21(5).

[9]MohammedJ.Zaki,SrinivasanParthasarathy,etc.Newalgorithmforfastdiscoveryofassociationrules[M].KDD, 1997.

[責(zé)任編輯：王軍]

Pattern mining of uncertain datasets

CHEN Fengjuan

(Basic Teaching and Research Section,Liaoning University of International Business and Economics, Dalian 116052,China)

Mining frequent pattern from transactional datasets is a popular problem which has some good algorithmic solutions.In the case of uncertain datasets, however, several new techniques have been proposed.Unfortunately, these proposals often suffer when a lot of items occur with many different probabilities.In this paper, we focus on the method based on sampling by instantiating possible worlds of the uncertain data.Then we study the optimized frequent pattern mining algorithm which gains efficiency at a surprisingly low loss in accuracy.

uncertain dataset；pattern mining; expected support

2015-10-08

陳鳳娟(1979-)，女，遼寧本溪市人，遼寧對外經(jīng)貿(mào)學(xué)院副教授，碩士，主要從事數(shù)據(jù)挖掘、無線傳感器網(wǎng)絡(luò)的研究.

TP311.12

A

1672-3600(2015)12-0016-04