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

陳鳳娟

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

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

陳鳳娟

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

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

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

0 引 言

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

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

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

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

1 可能世界與期望支持度

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

對于任意給定的一個項x和每一個事務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包含的項集.假設記錄中的項的概率是通過獨立觀察得到的，那么可能世界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ù)集中給定的存在概率來建立的.對于每個事務t和事務t中的每個項i，生成一個獨立的隨機數(shù)r，并且r∈[0,1]，然后把r和項i的概率值p進行比較.如果p≥r，那么項i就在當前的抽樣事務中出現(xiàn)，否則，項i在當前的抽樣事務中就不出現(xiàn).對于不確定數(shù)據(jù)集中的每一條事務，重復上面的步驟n次，n是給定的一個常數(shù).這樣得到的數(shù)據(jù)集就是一個確定數(shù)據(jù)集，就可以使用現(xiàn)有的確定數(shù)據(jù)集的挖掘方法來挖掘.但是為了估計一個項集在不確定數(shù)據(jù)集中的支持度，由上面方法得到的抽樣數(shù)據(jù)集中，該項集的支持度計數(shù)需要除以n.

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

E[S]=expSup(X)

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

3 頻繁模式挖掘

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

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

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

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

4 結束語

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

[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.

[責任編輯：王軍]

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)學院副教授，碩士，主要從事數(shù)據(jù)挖掘、無線傳感器網(wǎng)絡的研究.

TP311.12

A

1672-3600(2015)12-0016-04