不確定數據的項集頻繁概率近似算法

陳鳳娟

(遼寧對外經貿學院 基礎課教研部,遼寧 大連 116052)

不確定數據的項集頻繁概率近似算法

陳鳳娟

(遼寧對外經貿學院 基礎課教研部,遼寧 大連 116052)

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

近似算法;不確定性;概率頻繁項集

關聯規則挖掘是數據挖掘重要的研究領域之一，它經常應用于購物籃數據庫分析，從而發現顧客購買行為的規律.頻繁模式挖掘是關聯分析的第一步也是最重要的一步，在挖掘過程中，通常認為被挖掘的事務數據庫是用一個二元矩陣M來表示的.其中，矩陣的每一行表示一個事務，而每一列表示事務中出現的一個項.矩陣中的一個元素Mij的值是1或0，分別表示項j在事務i中出現和不出現.在這種基本的事務數據模型中，一個項在一個事務中，要么出現，要么不出現，沒有其他可能.相對于不確定數據集，這種數據庫也稱為確定數據庫.在確定數據庫中挖掘頻繁模式的方法已經提出了很多，它們使用多種方法對事務數據庫進行模式挖掘.

但是，在很多應用中，一個項在一個事務中不是出現或不出現，而是用一個存在概率來表示該項在該事務中出現的可能性大小.這是因為實驗測量中搜集的數據容易受到噪聲的干擾.例如，在用衛星對物體進行觀察時，采集的衛星圖像數據中，一個對象在其中出現的可能性用一個概率值來表示，因為它的出現與否是依靠人工解釋或圖像處理工具來分析得到的.這類數據被稱為不確定數據.

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

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

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

1 不確定數據庫與可能世界

不確定數據庫是指在事務數據庫中，事務中每個項的出現與否由一個[0,1]之間的概率值來表示.當值為1時，表示該項出現在該事務中，當值為0時，表示該項不出現在該事務中，而值是區間的中間值時，表示該項在事務中出現的可能性大小.為了表示方式的簡單，值為0的項在數據庫中就不顯示了[1].

表1 確定數據庫

表2 不確定數據庫

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

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

2 頻繁概率的概念

在不確定事務數據庫中，一個項集的支持度是不確定的，它是由一個離散概率分布函數來定義的.所以，每一個項有一個頻繁概率，用來表示它是頻繁項集的可能性大小.在不確定事務數據庫中，一個項的支持度不應該僅用一個統計值來表示，而應該用離散概率分布來表示.

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

定義3 一個項集X的概率支持度是指項集X所有的可能支持度值對應的支持度概率組成的概率分布.

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

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

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

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

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

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

3 挖掘概率頻繁項集的近似算法

為了挖掘不確定數據庫中的概率頻繁項集，需要計算項集的頻繁概率，可以采用動態規劃的方法和分治的方法來計算頻繁概率.

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

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

雖然動態規劃和分治算法給出了計算頻繁概率的方法，但是在挖掘過程中，對于項集的頻繁概率的計算量還是很大的，當數據庫中記錄量很大時，算法的效率不是很高.

4 結語

概率頻繁項集挖掘問題是在不確定事務數據庫中發現某些項集可能是頻繁的，并計算它們是頻繁項集的可能性大小，找出大于用戶給定最小頻繁概率閾值的項集.用動態規劃和分治方法計算頻繁概率，從而找出概率頻繁項集的方法在數據量大時效果不是很好，而近似算法不去計算具體的頻繁概率，只關注頻繁概率的近似值，從而減少了運算量，提高了算法的效率.

[1] 王意潔,李小勇,祁亞斐，等.不確定數據查詢技術研究[J].計算機研究與發展,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] 汪金苗,張龍波,鄧齊志,等.不確定數據頻繁項集挖掘方法綜述[J].計算機工程與應用,2010,47(20):121-125.

[5] 周傲英,金澈清,王國仁,等.不確定性數據管理技術綜述[J].計算機學報,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] 王 爽,楊廣明,朱志良.基于不確定數據的頻繁項查詢算法[J].東北大學學報:自然科學版,2011,32(3):344-347.

責任編輯：趙秋宇

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—)，女，遼寧本溪人，副教授，碩士，研究方向：數據挖掘、無線傳感器網絡.

1671-9824(2016)02-0046-04

TP393

A