概率數(shù)據(jù)集的垂直數(shù)據(jù)格式挖掘

陳鳳娟

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

?

概率數(shù)據(jù)集的垂直數(shù)據(jù)格式挖掘

陳鳳娟

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

[摘要]由于頻繁項(xiàng)集挖掘在各種實(shí)際應(yīng)用中起到了重要的作用，它已經(jīng)成為了很多研究的主題，大部分研究的是在精確數(shù)據(jù)的事務(wù)數(shù)據(jù)集上進(jìn)行挖掘。然而，有很多情況，數(shù)據(jù)是不確定的。在過去的幾年里，提出了一些基于Apriori和基于樹包含不確定數(shù)據(jù)的概率數(shù)據(jù)集上頻繁項(xiàng)集的挖掘算法。這些算法從記錄收集的角度把數(shù)據(jù)集看成水平的，本文則把包含不確定數(shù)據(jù)的概率數(shù)據(jù)集看成垂直的向量，并研究在此基礎(chǔ)上的挖掘算法。

[關(guān)鍵詞]概率數(shù)據(jù)集;概率頻繁項(xiàng)集;垂直數(shù)據(jù)格式

1引言

頻繁項(xiàng)集挖掘的目標(biāo)是找出數(shù)據(jù)集中隱含的、未知的和潛在有用的信息，而這些信息以項(xiàng)集的形式出現(xiàn)，這些項(xiàng)集是數(shù)據(jù)集中的某些項(xiàng)的集合[1]。自從頻繁項(xiàng)集挖掘被提出以來，它已經(jīng)成為了很多研究的主題。它也在其他模式挖掘中起到了至關(guān)重要的作用，如共同位置模式挖掘、出現(xiàn)模式挖掘、流行模式挖掘及社交網(wǎng)絡(luò)中的重要朋友圈挖掘等等。

在最開始對(duì)于頻繁項(xiàng)集挖掘的研究中，大部分算法都是基于Apriori的生成-測(cè)試模型的算法。這類算法通過生成候選頻繁項(xiàng)集，然后再測(cè)試這些候選項(xiàng)集是否為頻繁項(xiàng)集，刪除不頻繁的項(xiàng)集。為了提高Apriori算法的效率，提出了基于樹的FP-growth算法，這種算法在挖掘過程中，遞歸的創(chuàng)建FP樹，從這些樹中可以挖掘出頻繁項(xiàng)集。無論是基于Apriori的算法，還是FP-growth算法，都是把數(shù)據(jù)集中的記錄按照水平方式來處理，每一個(gè)記錄包含了一組項(xiàng)的集合。相反的，數(shù)據(jù)集可以被看成垂直的，即一組向量或一組記錄標(biāo)號(hào)的集合。這個(gè)向量或記錄標(biāo)號(hào)的集合表示哪些記錄包含當(dāng)前的項(xiàng)。VIPER和Eclat算法是垂直挖掘數(shù)據(jù)集的兩個(gè)算法。

無論是水平的還是垂直的挖掘算法都是在精確數(shù)據(jù)集上進(jìn)行的，這種數(shù)據(jù)集中，用戶很清楚地知道一個(gè)項(xiàng)在數(shù)據(jù)集中的某條記錄中是出現(xiàn)還是不出現(xiàn)。然而，現(xiàn)實(shí)的應(yīng)用中，有很多不能確定項(xiàng)是否出現(xiàn)的情況，僅僅是懷疑而不能保證該項(xiàng)一定出現(xiàn)。這種不確定性可以用一個(gè)與項(xiàng)相關(guān)聯(lián)的存在概率來表示。為了能從這些概率數(shù)據(jù)集中挖掘頻繁項(xiàng)集，已經(jīng)有很多水平算法的擴(kuò)展，如U-Apriori，UF-growth等[2]。本文主要研究在垂直數(shù)據(jù)格式上挖掘概率數(shù)據(jù)集，找到其中的頻繁項(xiàng)集，主要通過對(duì)確定數(shù)據(jù)中的VIPER進(jìn)行擴(kuò)展，使其能在包含不確定數(shù)據(jù)的概率數(shù)據(jù)集中工作。

2不確定數(shù)據(jù)與期望支持度

不確定性可能是由測(cè)量的不精確引起的，也可能是人為添加到數(shù)據(jù)集中的。比如，在很多應(yīng)用中，如環(huán)境監(jiān)測(cè)和一些工廠環(huán)境中，傳感器常被用來收集數(shù)據(jù)，一些錯(cuò)誤或不精確或偏差可以是由一段時(shí)間內(nèi)測(cè)量屬性的快速變化而產(chǎn)生的無線傳輸錯(cuò)誤或網(wǎng)絡(luò)中的錯(cuò)誤。在隱私保護(hù)中，會(huì)故意添加一些不確定數(shù)據(jù)到數(shù)據(jù)集中，起到保護(hù)用戶隱私的作用。在實(shí)際應(yīng)用中，有多種產(chǎn)生不確定數(shù)據(jù)的原因。

由于不確定性的存在，用戶無法確定一個(gè)項(xiàng)x在一個(gè)記錄ti中是否存在。對(duì)于這種是否存在的不確定性，可以用存在概率P(x,ti)來表示，它表示x在包含不確定數(shù)據(jù)的概率數(shù)據(jù)庫的記錄ti中存在的可能性大小[3]。存在概率P(x,ti)的范圍是從一個(gè)接近于0的正數(shù)，表明x在記錄ti中出現(xiàn)的概率非常小，到1，表明x在記錄ti中一定出現(xiàn)。按照這種表示方式，在確定數(shù)據(jù)庫中的每個(gè)項(xiàng)都可以被看成存在概率是1的不確定數(shù)據(jù)。

如果使用可能世界語義來解釋不確定數(shù)據(jù)，對(duì)于給定一個(gè)項(xiàng)x和一個(gè)記錄ti，就有兩個(gè)可能世界。一個(gè)可能世界W1表示x在記錄ti中出現(xiàn)，另一個(gè)可能世界W2表示x在記錄ti中不出現(xiàn)。雖然無法確定這兩個(gè)可能世界哪個(gè)是真正出現(xiàn)的，但是可以得到這兩個(gè)可能世界出現(xiàn)的可能性大小，即W1出現(xiàn)的概率是P(x,ti)，W2出現(xiàn)的概率是1-P(x, ti)。通常，給定m個(gè)不同的項(xiàng)和n條記錄，就有2mn個(gè)可能世界。

在包含不確定數(shù)據(jù)的概率數(shù)據(jù)集中，假設(shè)其記錄總數(shù)為n，如果一個(gè)項(xiàng)集X的期望支持度expSup大于用戶給定的最小支持度minSup，那么這個(gè)項(xiàng)集X就是頻繁的。項(xiàng)集X的期望支持度expSup可以用下面的式子得到[4]。

在這個(gè)等式中，sup(X,Wj)表示項(xiàng)集X在某個(gè)可能世界Wj中的支持度，prob(Wj)表示可能世界Wj成為真實(shí)世界的可能性大小。sup(X,Wj)可以通過在可能世界中統(tǒng)計(jì)項(xiàng)集X在記錄中出現(xiàn)的次數(shù)來得到。

prob(Wj)可以用下式計(jì)算得到[5]

其中，x和y是項(xiàng)集X中的項(xiàng)。當(dāng)項(xiàng)集中的每個(gè)項(xiàng)相互之間獨(dú)立，就可以用下面的式子來計(jì)算expSup(X)。

這樣就可以使用expSup(X)來計(jì)算所有項(xiàng)集的期望支持度了。

3概率數(shù)據(jù)庫的垂直表示

在確定數(shù)據(jù)集中，頻繁項(xiàng)集挖掘算法VIPER使用了向量來表示每個(gè)項(xiàng)x在記錄中是否出現(xiàn)，并從這些向量中采用自定向上的候選生成模式來挖掘頻繁項(xiàng)集。在挖掘包含不確定數(shù)據(jù)的概率數(shù)據(jù)庫時(shí)，保存每個(gè)項(xiàng)x在每個(gè)記錄ti中的存在概率。那么，如何用垂直方式來表示包含存在概率值的概率數(shù)據(jù)庫[6]。

為了表示概率數(shù)據(jù)庫中的不確定數(shù)據(jù)，可以為每一個(gè)不同的項(xiàng)使用一個(gè)向量，由該項(xiàng)的取值和該項(xiàng)的存在概率組成。然而，潛在的問題就是數(shù)量太多，因?yàn)榇嬖诟怕士梢栽?和1之間取任意的實(shí)數(shù)，所有從理論上它可能是不可數(shù)的無限數(shù)。實(shí)際上，在數(shù)據(jù)庫中，這些<項(xiàng)的取值,存在概率>組成的一對(duì)值的數(shù)量是可數(shù)。

為了找到頻繁概率，需要找到期望支持度大于最小支持度的項(xiàng)集，也就是說，我們需要找到比每個(gè)<項(xiàng)的取值,存在概率>的出現(xiàn)次數(shù)要多的所有頻繁項(xiàng)集。因此，不需要保留所有的不同的<項(xiàng)的取值,存在概率>的向量，而是只需要對(duì)項(xiàng)集X中的每個(gè)x保留其向量。

4基于垂直表示的頻繁項(xiàng)集挖掘

在確定數(shù)據(jù)庫中，VIPER算法通過統(tǒng)計(jì)向量中每個(gè)項(xiàng)的元素1的個(gè)數(shù)，然后與給定的最小支持度比較，如果大于等于最小支持度minsup，則該項(xiàng)就是頻繁的。找到頻繁1項(xiàng)集后，VIPER算法應(yīng)用一個(gè)組織候選生成步驟，對(duì)兩個(gè)向量做交叉形成候選2項(xiàng)集。重復(fù)上述比較過程，直到生成全部的頻繁項(xiàng)集[7]。

在包含不確定數(shù)據(jù)的概率數(shù)據(jù)庫中，用向量來垂直表示概率數(shù)據(jù)庫后，就可以在這個(gè)概率數(shù)據(jù)庫中應(yīng)用擴(kuò)展后的VIPER算法，來挖掘垂直數(shù)據(jù)模式下的頻繁項(xiàng)集了。這個(gè)擴(kuò)展的VIPER算法可以稱為U-VIPER算法[8]。

在U-VIPER算法中，首先要解決的問題是，如何計(jì)算只包含一個(gè)項(xiàng)的項(xiàng)集的概率支持度。對(duì)于確定數(shù)據(jù)庫，可以通過計(jì)算向量中元素1的總個(gè)數(shù)得到項(xiàng)的支持度，類似的，在U-VIPER算法中，可以通過求向量中所有非零的存在概率之和來計(jì)算概率數(shù)據(jù)庫中的期望支持度。

當(dāng)U-VIPER算法計(jì)算出1項(xiàng)集的期望支持度后，用該期望支持度與用戶給定的最小支持度進(jìn)行比較，如果expSup(x)≥minsup，那么，該項(xiàng)就是頻繁的，否則該項(xiàng)就是不頻繁的。這樣，可以找出所有的頻繁1項(xiàng)集。然后，下面的問題是如何生成由更多項(xiàng)組成的候選項(xiàng)集，如2項(xiàng)集、3項(xiàng)集和k項(xiàng)集等等。

為了挖掘概率數(shù)據(jù)庫中的頻繁項(xiàng)集，U-VIPER算法計(jì)算保存在向量中的單個(gè)項(xiàng)的期望支持度，如果項(xiàng)集的期望支持度大于給定閾值，則該項(xiàng)是頻繁的，否則，是不頻繁的。找到頻繁1項(xiàng)集后，應(yīng)用向量點(diǎn)積運(yùn)算，找出候選頻繁2項(xiàng)集，再計(jì)算候選項(xiàng)集的期望支持度，并與最小支持度閾值比較，不斷重復(fù)上述過程，直到得到概率數(shù)據(jù)庫中所有的頻繁項(xiàng)集。

5結(jié)束語

在包含不確定數(shù)據(jù)的概率數(shù)據(jù)庫中挖掘頻繁項(xiàng)集已經(jīng)引起了越來越多的關(guān)注，現(xiàn)有的很多算法都是在水平表示數(shù)據(jù)庫的基礎(chǔ)上，給出挖掘算法。在確定數(shù)據(jù)庫中，可以把數(shù)據(jù)庫采用垂直數(shù)據(jù)格式來表示，同樣，在概率數(shù)據(jù)庫中，也可以在垂直表示的數(shù)據(jù)庫上進(jìn)行頻繁項(xiàng)集的挖掘。

[參考文獻(xiàn)]

[1]R. Agrawal, R. Srikant, “Fast algorithms for mining association rules,” in VLDB, 1994.

[2]C. Aggarwal and P. Yu. “A survey of uncertain data algorithms and applications, ” IEEE TKDE, 2009 , 21(5):609～623.

[3]O. Benjelloun, A.D. Sarma. “ULDBs:Databases with uncertainty and lineage,” in VLDB, 2006.

[4]C. Chui, B. Kao, E. Hung, “Mining frequent itemsets from uncertain data,” in PAKDD, 2007.

[5]T. Bernecker, H.P. Kriegel, M. Renz, F. Verhein, A. Zuefle,“Probabilistic frequent itemset mining in uncertain databases,” in KDD,2009.

[6]P. Shenoy et al.“Turbo-charging vertical mining of large databases, ” in SIGMOD 2000.

[7]C.K.S. Leung.“Mining uncertain data. Wiley Interdisc,” Data Mining and Knowledge Discovery,July/Aug. 2011,1(4):316-329.

[8]C.K.S. Leung. “ Mining probabilistic datasets vertically,” in IDEAS’ 2012.

[責(zé)任編輯：江雪]

Mining Vertical Data Format over Probabilistic Dataset

CHEN Feng-juan

(Liaoning University of International Business and Economics, Dalian 116052，China)

Abstract:As frequent itemset mining plays an important role in various real-life applications, it has been the subject of numerous studies. Most of the studies mine transactional datasets of precise data. However, there are situations in which data are uncertain. Over the few years, Apriori-based, tree-based mining algorithms have been proposed to mine frequent itemsets from these probabilistic datasets of uncertain data. These algorithms view the datasets horizontally as collections of transactions. In this paper, probabilistic datasets of uncertain data are viewed vertically as collections of vectors. Then an algorithm to mine probabilistic datasets vertically is be studied.

Key words:Probabilistic Dataset; Probabilistic Frequent Itemset；Vertical Data Format

[收稿日期]2016-01-21

[作者簡(jiǎn)介]陳鳳娟(1979-)，女，遼寧省本溪市人，副教授，主要從事數(shù)據(jù)挖掘、無線傳感器網(wǎng)絡(luò)研究。

[中圖分類號(hào)]TP32

[文獻(xiàn)標(biāo)識(shí)碼]A

[文章編號(hào)]1671-5330(2016)02-0041-04