概率數據集的垂直數據格式挖掘

陳鳳娟

(遼寧對外經貿學院，遼寧 大連 116052)

?

概率數據集的垂直數據格式挖掘

陳鳳娟

(遼寧對外經貿學院，遼寧 大連 116052)

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

[關鍵詞]概率數據集;概率頻繁項集;垂直數據格式

1引言

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

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

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

2不確定數據與期望支持度

不確定性可能是由測量的不精確引起的，也可能是人為添加到數據集中的。比如，在很多應用中，如環境監測和一些工廠環境中，傳感器常被用來收集數據，一些錯誤或不精確或偏差可以是由一段時間內測量屬性的快速變化而產生的無線傳輸錯誤或網絡中的錯誤。在隱私保護中，會故意添加一些不確定數據到數據集中，起到保護用戶隱私的作用。在實際應用中，有多種產生不確定數據的原因。

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

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

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

在這個等式中，sup(X,Wj)表示項集X在某個可能世界Wj中的支持度，prob(Wj)表示可能世界Wj成為真實世界的可能性大小。sup(X,Wj)可以通過在可能世界中統計項集X在記錄中出現的次數來得到。

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

其中，x和y是項集X中的項。當項集中的每個項相互之間獨立，就可以用下面的式子來計算expSup(X)。

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

3概率數據庫的垂直表示

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

為了表示概率數據庫中的不確定數據，可以為每一個不同的項使用一個向量，由該項的取值和該項的存在概率組成。然而，潛在的問題就是數量太多，因為存在概率可以在0和1之間取任意的實數，所有從理論上它可能是不可數的無限數。實際上，在數據庫中，這些<項的取值,存在概率>組成的一對值的數量是可數。

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

4基于垂直表示的頻繁項集挖掘

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

在包含不確定數據的概率數據庫中，用向量來垂直表示概率數據庫后，就可以在這個概率數據庫中應用擴展后的VIPER算法，來挖掘垂直數據模式下的頻繁項集了。這個擴展的VIPER算法可以稱為U-VIPER算法[8]。

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

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

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

5結束語

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

[參考文獻]

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

[責任編輯：江雪]

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

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

[中圖分類號]TP32

[文獻標識碼]A

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