不確定數(shù)據(jù)的項(xiàng)集頻繁概率近似算法

陳鳳娟

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

不確定數(shù)據(jù)的項(xiàng)集頻繁概率近似算法

陳鳳娟

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

研究在不確定事務(wù)數(shù)據(jù)庫中挖掘概率頻繁項(xiàng)集的問題，探討使用近似算法在不確定數(shù)據(jù)中的挖掘概率頻繁項(xiàng)集的方法.首先分析不確定數(shù)據(jù)庫與可能世界語言，然后介紹頻繁概率的概念，最后分析如何使用近似算法挖掘不確定數(shù)據(jù)庫中的概率頻繁項(xiàng)集. 從而降低運(yùn)行時(shí)間，提高算法效率.

近似算法;不確定性;概率頻繁項(xiàng)集

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘重要的研究領(lǐng)域之一，它經(jīng)常應(yīng)用于購物籃數(shù)據(jù)庫分析，從而發(fā)現(xiàn)顧客購買行為的規(guī)律.頻繁模式挖掘是關(guān)聯(lián)分析的第一步也是最重要的一步，在挖掘過程中，通常認(rèn)為被挖掘的事務(wù)數(shù)據(jù)庫是用一個(gè)二元矩陣M來表示的.其中，矩陣的每一行表示一個(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)的可能性大小.這是因?yàn)閷?shí)驗(yàn)測(cè)量中搜集的數(shù)據(jù)容易受到噪聲的干擾.例如，在用衛(wèi)星對(duì)物體進(jìn)行觀察時(shí)，采集的衛(wèi)星圖像數(shù)據(jù)中，一個(gè)對(duì)象在其中出現(xiàn)的可能性用一個(gè)概率值來表示，因?yàn)樗某霈F(xiàn)與否是依靠人工解釋或圖像處理工具來分析得到的.這類數(shù)據(jù)被稱為不確定數(shù)據(jù).

從這類數(shù)據(jù)庫中挖掘頻繁項(xiàng)集比從確定數(shù)據(jù)庫中挖掘更難，畢竟，計(jì)算一個(gè)項(xiàng)集的支持度必須考慮項(xiàng)集的存在概率.頻繁概率是一種衡量不確定數(shù)據(jù)庫中項(xiàng)集的支持度大小的概念，它全面考慮項(xiàng)集的支持度的概率分布，能表示該項(xiàng)集是頻繁項(xiàng)集的概率.

本文主要研究在不確定事務(wù)數(shù)據(jù)庫中挖掘概率頻繁項(xiàng)集的問題，并探討使用近似算法挖掘概率頻繁項(xiàng)集.首先分析不確定數(shù)據(jù)庫與可能世界語言，然后介紹頻繁概率的概念，最后分析如何使用近似算法挖掘不確定數(shù)據(jù)庫中的概率頻繁項(xiàng)集.

從事務(wù)數(shù)據(jù)庫中挖掘頻繁項(xiàng)集是關(guān)聯(lián)規(guī)則的最重要的步驟，大多數(shù)的頻繁項(xiàng)集挖掘算法假設(shè)輸入的數(shù)據(jù)不存在誤差.然后，真實(shí)數(shù)據(jù)常常被噪聲所影響，這種噪聲在不確定數(shù)據(jù)庫中用每個(gè)項(xiàng)的出現(xiàn)概率來表示.本文主要研究在不確定數(shù)據(jù)中用近似算法挖掘概率頻繁項(xiàng)集的問題.

1 不確定數(shù)據(jù)庫與可能世界

不確定數(shù)據(jù)庫是指在事務(wù)數(shù)據(jù)庫中，事務(wù)中每個(gè)項(xiàng)的出現(xiàn)與否由一個(gè)[0,1]之間的概率值來表示.當(dāng)值為1時(shí)，表示該項(xiàng)出現(xiàn)在該事務(wù)中，當(dāng)值為0時(shí)，表示該項(xiàng)不出現(xiàn)在該事務(wù)中，而值是區(qū)間的中間值時(shí)，表示該項(xiàng)在事務(wù)中出現(xiàn)的可能性大小.為了表示方式的簡(jiǎn)單，值為0的項(xiàng)在數(shù)據(jù)庫中就不顯示了[1].

表1 確定數(shù)據(jù)庫

表2 不確定數(shù)據(jù)庫

定義1 設(shè)T是一組不同事務(wù)的集合，I是一組項(xiàng)的集合.一個(gè)不確定數(shù)據(jù)庫D是一個(gè)從T×I到區(qū)間[0,1]的函數(shù).不確定數(shù)據(jù)庫D的一個(gè)可能世界W是T×I的一個(gè)子集.每個(gè)可能世界的概率PD(W)定義為

一個(gè)項(xiàng)集X在一個(gè)可能世界W中的支持度定義為W中包含X的事務(wù)的個(gè)數(shù)，因此，PD描述了不確定數(shù)據(jù)庫的所有可能世界上的概率分布.一個(gè)項(xiàng)集在不確定數(shù)據(jù)庫中的頻繁度計(jì)算就是基于這種概率分布得到的.在所有的可能世界中，我們不知道哪個(gè)可能世界是真正發(fā)生的，因此，PD表明了某個(gè)可能世界真正發(fā)生的概率[3].

2 頻繁概率的概念

在不確定事務(wù)數(shù)據(jù)庫中，一個(gè)項(xiàng)集的支持度是不確定的，它是由一個(gè)離散概率分布函數(shù)來定義的.所以，每一個(gè)項(xiàng)有一個(gè)頻繁概率，用來表示它是頻繁項(xiàng)集的可能性大小.在不確定事務(wù)數(shù)據(jù)庫中，一個(gè)項(xiàng)的支持度不應(yīng)該僅用一個(gè)統(tǒng)計(jì)值來表示，而應(yīng)該用離散概率分布來表示.

定義2 給定一個(gè)不確定事務(wù)數(shù)據(jù)庫T和它的所有可能世界的集合，項(xiàng)集X的支持度的概率Pi(X)是指在所有可能世界中X的支持度等于i的可能世界的概率之和，即

定義3 一個(gè)項(xiàng)集X的概率支持度是指項(xiàng)集X所有的可能支持度值對(duì)應(yīng)的支持度概率組成的概率分布.

這種概率分布也稱為支持度概率分布，其和為1.

由于可能世界的個(gè)數(shù)是指數(shù)增長(zhǎng)的，因此用定義1來計(jì)算支持度概率Pi(X)是不可行的，可以用下面的式子來計(jì)算[5].

項(xiàng)集X的頻繁概率P≥minsup(X)表示的是項(xiàng)集X是頻繁的可能性大小，依據(jù)這一策略，一個(gè)項(xiàng)集的頻繁度可以作為項(xiàng)集是否是候選項(xiàng)集的判斷條件.因此，給定一個(gè)最小的頻繁概率作為用戶定義的參數(shù)，可以找出概率頻繁項(xiàng)集.

頻繁概率可以通過計(jì)算所有滿足最小支持度的可能世界中的概率之和得到.

定義5 一個(gè)項(xiàng)集X是概率頻繁項(xiàng)集當(dāng)且僅當(dāng)該項(xiàng)集的頻繁概率P≥minsup(X)大于等于用戶給定的最小頻繁概率閾值.

因此，挖掘不確定數(shù)據(jù)庫中的概率頻繁項(xiàng)集的問題就是指在不確定數(shù)據(jù)庫中，根據(jù)用戶給定的最小支持度和最小頻繁概率閾值，找出所有頻繁概率大于最小頻繁概率閾值的項(xiàng)集.

3 挖掘概率頻繁項(xiàng)集的近似算法

為了挖掘不確定數(shù)據(jù)庫中的概率頻繁項(xiàng)集，需要計(jì)算項(xiàng)集的頻繁概率，可以采用動(dòng)態(tài)規(guī)劃的方法和分治的方法來計(jì)算頻繁概率.

而P≥i,j(X)=P≥i-1,j-1(X)·P(X?tj)+P≥i,j-1(X)·(1-P(X?tj)).

分治方法把不確定數(shù)據(jù)庫分成兩個(gè)子數(shù)據(jù)庫，在子數(shù)據(jù)庫上繼續(xù)調(diào)用該方法，再次劃分?jǐn)?shù)據(jù)庫，直到數(shù)據(jù)庫中只有一條記錄，然后計(jì)算頻繁概率，再把兩個(gè)數(shù)據(jù)庫中的頻繁概率進(jìn)行合并，通過不斷的合并，得到該項(xiàng)在整個(gè)數(shù)據(jù)庫中的頻繁概率.該方法可以在計(jì)算過程中使用快速傅里葉變換，提高該方法的效率[6].

雖然動(dòng)態(tài)規(guī)劃和分治算法給出了計(jì)算頻繁概率的方法，但是在挖掘過程中，對(duì)于項(xiàng)集的頻繁概率的計(jì)算量還是很大的，當(dāng)數(shù)據(jù)庫中記錄量很大時(shí)，算法的效率不是很高.

4 結(jié)語

概率頻繁項(xiàng)集挖掘問題是在不確定事務(wù)數(shù)據(jù)庫中發(fā)現(xiàn)某些項(xiàng)集可能是頻繁的，并計(jì)算它們是頻繁項(xiàng)集的可能性大小，找出大于用戶給定最小頻繁概率閾值的項(xiàng)集.用動(dòng)態(tài)規(guī)劃和分治方法計(jì)算頻繁概率，從而找出概率頻繁項(xiàng)集的方法在數(shù)據(jù)量大時(shí)效果不是很好，而近似算法不去計(jì)算具體的頻繁概率，只關(guān)注頻繁概率的近似值，從而減少了運(yùn)算量，提高了算法的效率.

[1] 王意潔,李小勇,祁亞斐，等.不確定數(shù)據(jù)查詢技術(shù)研究[J].計(jì)算機(jī)研究與發(fā)展,2012,49(7):1460-1466.

[2] Chui C, Kao B, Hung E. Mining frequent itemsets from uncertain data[C]. Berlin Heidelberg: Springer-verlag, 2007.

[3] Aggarwal C, Yu P. A survey of uncertain data algorithms and applications [J].IEEE Transactions on Knowledge and Data Engineering, 2009, 21(5): 609-623.

[4] 汪金苗,張龍波,鄧齊志,等.不確定數(shù)據(jù)頻繁項(xiàng)集挖掘方法綜述[J].計(jì)算機(jī)工程與應(yīng)用,2010,47(20):121-125.

[5] 周傲英,金澈清,王國(guó)仁,等.不確定性數(shù)據(jù)管理技術(shù)綜述[J].計(jì)算機(jī)學(xué)報(bào),2009,32(1):1-16.

[6] Wang L, Cheung D W, Cheng R, et al. Efficient mining of frequent itemsets on large uncertain databases[J].IEEE Transactions on Knowledge and Data Engineering, 2011,23(3):367-381.

[7] 王 爽,楊廣明,朱志良.基于不確定數(shù)據(jù)的頻繁項(xiàng)查詢算法[J].東北大學(xué)學(xué)報(bào):自然科學(xué)版,2011,32(3):344-347.

責(zé)任編輯：趙秋宇

Approximation Algorithm for Probability of Frequent Item-sets in Uncertain Database

CHEN Feng-juan

(InternationalBusinessandEconomics,LiaoningUniversity,Dalian116052,China)

In order to reduce the running time and improve efficiency of algorithm, studying items of mining approximation algorithm for probabilistic frequent item-sets in uncertain transaction databases, this paper acquired how to use approximation algorithm to mine probabilistic frequent item-sets in uncertain base. Starting with analyzing connections between uncertain databases and possible worlds, the paper introduces what frequent item-sets is. At last, a method of mining probabilistic frequent item-sets by approximation algorithm in uncertain databases is concluded.

approximation algorithm, uncertainty, probabilistic frequent item-sets

2015-10-17

陳鳳娟(1979—)，女，遼寧本溪人，副教授，碩士，研究方向：數(shù)據(jù)挖掘、無線傳感器網(wǎng)絡(luò).

1671-9824(2016)02-0046-04

TP393

A