陳 靜

（鹽都廣播電視大學(xué)，江蘇 鹽城 224006）

基于Apriori的改進(jìn)算法

陳 靜

（鹽都廣播電視大學(xué)，江蘇 鹽城 224006）

關(guān)聯(lián)規(guī)則的提取是數(shù)據(jù)挖掘中的重要研究內(nèi)容，對(duì)關(guān)聯(lián)規(guī)則提取中的Apriori算法進(jìn)行了分析與研究，針對(duì)該算法的運(yùn)算效率不高，對(duì)該算法進(jìn)行了改進(jìn)，提出了Apriori改進(jìn)算法。Apriori改進(jìn)算法采用二進(jìn)制數(shù)據(jù)垂直表示方法，只用掃描事務(wù)數(shù)據(jù)庫一次得到一階大項(xiàng)集的二進(jìn)制數(shù)據(jù)垂直表示。K階候選項(xiàng)集的操作只要基于這個(gè)一階大項(xiàng)集，而不需重復(fù)掃描數(shù)據(jù)庫，從而提高了挖掘算法的效率。

數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；Apriori算法；Apriori改進(jìn)算法

數(shù)據(jù)挖掘(Date Mining),通常也稱為數(shù)據(jù)庫中的知識(shí)發(fā)現(xiàn)(KDD)，精確地說，在KDD中進(jìn)行知識(shí)學(xué)習(xí)的階段稱為數(shù)據(jù)挖掘。數(shù)據(jù)挖掘是KDD中的一個(gè)非常重要的處理步驟，但人們通常不加區(qū)別地使用這兩個(gè)術(shù)語。數(shù)據(jù)挖掘是一個(gè)多學(xué)科交叉研究領(lǐng)域，它融合了數(shù)據(jù)庫、人工智能、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)學(xué)、知識(shí)工程、面向?qū)ο蠓椒?、信息檢索、高性能計(jì)算以及數(shù)據(jù)可視化等最新技術(shù)的研究成果[1]。

1 關(guān)聯(lián)規(guī)則分析

關(guān)聯(lián)規(guī)則展示屬性-值頻繁地在給定數(shù)據(jù)集中一起出現(xiàn)的條件。關(guān)聯(lián)規(guī)則可描述為：設(shè)集合I={i1,i2,…,ik}是k個(gè)不同項(xiàng)目組成的集合。給定一個(gè)事務(wù)數(shù)據(jù)庫D,其中的每個(gè)事務(wù)T是I中一組項(xiàng)目的集合，即TíI，T有唯一的標(biāo)識(shí)TID.若項(xiàng)集X ì

I,且X ì T，則事務(wù)集T包含項(xiàng)集X。一條關(guān)聯(lián)規(guī)則就是形如X=＞Y的蘊(yùn)涵式，其中X ì I,Yì I，并且X∩Y= ?。關(guān)聯(lián)規(guī)則X=＞Y成立的條件是：(1)它具有支持度Supp，即事務(wù)數(shù)據(jù)庫D中至少有Supp%的事務(wù)包含X∪Y；它具有置信度Conf，即事務(wù)數(shù)據(jù)庫D中包含X的事務(wù)至少有Conf%同時(shí)也包含Y[5]。

關(guān)聯(lián)規(guī)則挖掘問題就是發(fā)現(xiàn)具有用戶指定的最小支持度minsup和最小置信度minconf的關(guān)聯(lián)規(guī)則。該問題可以分解為兩個(gè)子問題：（1）求出D中滿足最小支持度minsup的所有項(xiàng)目集；（2）檢測(cè)滿足最小支持度的項(xiàng)目集是否滿足最小置信度minconf，并生成對(duì)應(yīng)的關(guān)聯(lián)規(guī)則。

2 Apriori算法

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘研究中的一個(gè)重要內(nèi)容。影響最大的挖掘關(guān)聯(lián)規(guī)則的算法是RakeshAgrawal[2]等人提出的Apriori算法,Apriori算法首先產(chǎn)生頻繁項(xiàng)集(由連接和剪枝兩步完成)，再產(chǎn)生關(guān)聯(lián)規(guī)則。

Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。Apriori使用一種稱作逐層搜索的迭代方法，i-項(xiàng)集用于搜索(i+1)項(xiàng)集。首先，找出頻繁一項(xiàng)集集合。該集合記為L1，L1用于尋找頻繁2項(xiàng)集的集合L2，L2用于尋找L3，如此下去，直到不能找到頻繁k-項(xiàng)集Lk，找出每個(gè)Li需要一次數(shù)據(jù)庫掃描。如何由Li-1找出Li，分為連接和剪枝兩個(gè)過程組成。根據(jù)Apriori算法的核心思想，分析得到程序的模塊圖[3](如圖1所示)。

圖1 頻繁項(xiàng)集挖掘算法模塊圖

3 Apriori改進(jìn)算法

3.1 算法優(yōu)化技術(shù)

由Apriori算法可以看出，每一Ci均要對(duì)數(shù)據(jù)庫掃描一次，而這時(shí)有些事務(wù)已經(jīng)對(duì)頻繁項(xiàng)集的生成不產(chǎn)生作用，減少對(duì)數(shù)據(jù)庫D的掃描次數(shù)對(duì)于算法來說是很有必要的[5]。基于Apriori算法的不足，本文提出了一種高效的關(guān)聯(lián)規(guī)則挖掘算法--Apriori-B算法。Apriori-B算法采用二進(jìn)制垂直表示方法，用“1”,“0”來表示信息有無兩種情況。當(dāng)該位為“1”表示事務(wù)記錄Ti中含有該項(xiàng)目集X,該位為“0”表示事務(wù)記錄Ti中不含有該項(xiàng)目集X.

定義1項(xiàng)目集二進(jìn)制數(shù)垂直表示，給定I=(i1,i2,…,im),事務(wù)數(shù)據(jù)庫D={T1,T2,…,Tn},項(xiàng)目集X的二進(jìn)制數(shù)垂直表示為b1b2…bn-1bn,并稱b=b1b2…bn-1bn為項(xiàng)目集X所對(duì)應(yīng)的二進(jìn)制數(shù)，記為Bx其中bi∈{0,1},如果XíTi,則Bi=1，否則bi=0；i=1,2,…,n.舉例(如表1所示)[4].

表 1 交易數(shù)據(jù)表

項(xiàng)集X={A} 所對(duì)應(yīng)的二進(jìn)制數(shù)垂直表示 100

定義2 位與操作&，數(shù)值位按位進(jìn)行“與”操作

例 0010 0100 1001 0010

& 0000 0000 1010 0111

0000 0000 1000 0010

3.2 Apriori改進(jìn)算法示例說明

設(shè)min-sup=2/9=22%，最小支持度計(jì)數(shù)為2；示例如表1所示：

（1）掃描事務(wù)數(shù)據(jù)庫D，將D中的項(xiàng)轉(zhuǎn)化為表2所示，并對(duì)標(biāo)識(shí)集中元素的個(gè)數(shù)計(jì)數(shù)。

（2）由給定的支持度計(jì)數(shù)為2，得到候選1-項(xiàng)集。將不是頻繁1-項(xiàng)集的項(xiàng)從第一步得到的垂直表示中刪去，生成頻繁1-項(xiàng)集的標(biāo)識(shí)集垂直表示即表3所示。

表 2 候選 1-項(xiàng)集的垂直表示

{D} 010 1

表3 頻繁 1-項(xiàng)集的垂直表示

（3）由表3產(chǎn)生的垂直表示對(duì)任意兩行進(jìn)行二進(jìn)制的按位與運(yùn)算。然后對(duì)每個(gè)結(jié)果中“1”的個(gè)數(shù)計(jì)數(shù)并將計(jì)數(shù)作為它的支持度計(jì)數(shù)，如果支持度≥min_sup，則相應(yīng)的項(xiàng)集的結(jié)合就是頻繁 2-項(xiàng)集，由頻繁 2-項(xiàng)集得到一個(gè)新的數(shù)據(jù)垂直表示如表4所示。

表 4 頻繁 2-項(xiàng)集的垂直表示

（4）發(fā)現(xiàn)頻繁項(xiàng)集的過程結(jié)束，得到所有的頻繁項(xiàng)集：

L1={ B,C };

L2={{B,C}};

4 結(jié)束語

本算法是一種基于二進(jìn)制數(shù)垂直表示、生成候選項(xiàng)集樹和相應(yīng)的支持度計(jì)算算法-Apriori改進(jìn)算法。本算法只需要對(duì)事務(wù)數(shù)據(jù)庫進(jìn)行一次掃描，能大量減少I/O次數(shù)，通過構(gòu)造候選項(xiàng)集樹生成候選項(xiàng)集的算法和計(jì)算項(xiàng)集支持度的算法比Apriori算法中通過連接和剪枝生成候選項(xiàng)集并多次掃描事務(wù)數(shù)據(jù)庫計(jì)算項(xiàng)集支持度的算法簡單，且內(nèi)存開銷適中。

[1] 曾孝文.關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘方法的研究[J].計(jì)算機(jī)與現(xiàn)代化,2006,9:90-93.

[2] JiaweiHan,JianPei,YiwenYin.Mining frequent pattern swithout candidate generation[J].SIGMOD,2000.1-12.

[3] 程玉勝,鄧小光,江效堯.Apriori算法中頻繁項(xiàng)集挖掘?qū)崿F(xiàn)研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2006,16(3):58-60.

[4] 周翠紅,賀建軍.挖掘關(guān)聯(lián)規(guī)則中對(duì) Apriori算法的一個(gè)改進(jìn)[J].湖南城市學(xué)院學(xué)報(bào),2006,15(4):68-69.

[5] 陳安,陳寧,等.數(shù)據(jù)挖掘技術(shù)與應(yīng)用[M].北京:科學(xué)出版社,2006.

Based on the improved algorithm Apriori

Association Rules is the extraction of data mining in the important research, The extraction of association rules Apriori algorithm analysis and research, The algorithm for computing efficiency is not high, By improving the algorithms, the improved Apriori proposed algorithm. The improved Apriori algorithm using binary data that the vertical approach, Scanning Service database used only once by a large band of binary data sets that vertical. K-order designate the options set for this operation as long as the first order of the large -,Scanning the database without having to repeat, Thereby improving the efficiency of the mining algorithms.

data-mining; association rules; Apriori algorithm; the improved Apriori algorithm

TP39

A

1008-1151(2012)06-0046-02

2012-04-15

陳靜（1984－），女，鹽都廣播電視大學(xué)教師，碩士，研究方向?yàn)閿?shù)據(jù)挖掘。