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

陳鳳娟

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

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

陳鳳娟

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

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

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

0 引 言

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

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

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

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

1 可能世界與期望支持度

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

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

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

(1)

(2)

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

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

(3)

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

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

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

E[S]=expSup(X)

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

3 頻繁模式挖掘

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

U-Apriori是一個(gè)基于Apriori算法的不確定數(shù)據(jù)集頻繁模式挖掘算法，但是由于它在生成候選集和對(duì)候選集進(jìn)行測(cè)試時(shí)，需要不斷的掃描數(shù)據(jù)集，因此算法的可擴(kuò)展性不是很好.UCP-Apriori算法是基于增量剪枝技術(shù)的算法，它在掃描數(shù)據(jù)集時(shí)動(dòng)態(tài)地構(gòu)成一個(gè)支持度的上界并不斷的更新這個(gè)上界.只要項(xiàng)集的最大的可能值低于閾值，這個(gè)項(xiàng)集就被剪枝[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)行存儲(chǔ).在UF-tree結(jié)構(gòu)中，只有當(dāng)一個(gè)事務(wù)中的項(xiàng)和項(xiàng)的期望支持度都與樹中的結(jié)點(diǎn)相同，二者才合并為一個(gè)結(jié)點(diǎn)，這就導(dǎo)致UF-tree的樹結(jié)構(gòu)的壓縮性很差[8].提高樹的存儲(chǔ)壓縮性，可以用離散化期望支持度來避免很多不同的期望支持度.另外，還有一些擴(kuò)展已有的經(jīng)典頻繁模式挖掘算法，來實(shí)現(xiàn)對(duì)不確定數(shù)據(jù)集的頻繁模式挖掘的方法，如UH-mine算法.這些算法仍然存在它們?cè)诖_定數(shù)據(jù)庫中存在的問題，而且，在不確定數(shù)據(jù)集中，計(jì)算量要遠(yuǎn)遠(yuǎn)大于確定數(shù)據(jù)集.

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

4 結(jié)束語

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

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

TP311.12

A

1672-3600(2015)12-0016-04