關(guān)聯(lián)規(guī)則挖掘算法的研究

張 麗

（湖南文理學(xué)院 經(jīng)濟(jì)與管理學(xué)院，湖南 常德 415000）

關(guān)聯(lián)規(guī)則挖掘算法的研究目前是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要方向，其中，Apriori算法就是一個(gè)經(jīng)典的挖掘關(guān)聯(lián)規(guī)則算法.1993年，Agrawal等提出關(guān)聯(lián)規(guī)則挖掘的相關(guān)概念，隨后提出經(jīng)典Apriori算法，它是一個(gè)采用兩階段挖掘思想的算法，且多次掃描事務(wù)數(shù)據(jù)庫(kù)，直到尋找出給定數(shù)據(jù)集中數(shù)據(jù)項(xiàng)之間有趣的關(guān)聯(lián)規(guī)則.

1 關(guān)聯(lián)規(guī)則基本概念

1.1 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則是形如A圯B的蘊(yùn)含式，在關(guān)聯(lián)規(guī)則中，有兩個(gè)重要的概念：支持度和置信度.支持度是對(duì)關(guān)聯(lián)規(guī)則的重要性的衡量，置信度是對(duì)關(guān)聯(lián)規(guī)則的準(zhǔn)確度的衡量，一般情況下，用戶(hù)根據(jù)實(shí)際挖掘需要，預(yù)先給定最小支持度和最小置信度，通常情況下，如果規(guī)則的置信度和支持度大于用戶(hù)指定的最小置信度和支持度，那么這個(gè)規(guī)則就是一條有效規(guī)則.事實(shí)上，有效規(guī)則并不一定具有實(shí)用性，還要參照關(guān)聯(lián)規(guī)則的其他指標(biāo).

定義1 設(shè)I={I1,I2,…,IM}是數(shù)據(jù)項(xiàng)的集合,D是全體事務(wù)的集合,一個(gè)事務(wù)T有一個(gè)唯一的標(biāo)識(shí)TID.如果項(xiàng)集A哿T,則稱(chēng)事務(wù)T支持項(xiàng)集A,也稱(chēng)事務(wù)T包含項(xiàng)集A.

定義2 關(guān)聯(lián)規(guī)則是形如A圯B的蘊(yùn)含式，其中A奐I，B奐I，且 A∩B=Φ.

定義3 事務(wù)數(shù)據(jù)庫(kù)D中有N條交易事務(wù)，關(guān)聯(lián)規(guī)則A圯B的支持度定義為：

引理1 在數(shù)據(jù)庫(kù)中若有一事務(wù)T其長(zhǎng)度小于K+1，則由K項(xiàng)頻繁集生成K+1項(xiàng)頻繁集時(shí)，事務(wù)T是沒(méi)必要掃描的.

1.2 Apriori算法的基本思想

Apriori算法是發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的經(jīng)典算法.該算法分兩個(gè)步驟發(fā)現(xiàn)關(guān)聯(lián)規(guī)則：第一步通過(guò)迭代，找出事務(wù)數(shù)據(jù)庫(kù)中的所有頻繁項(xiàng)集，即支持度不低于最小支持度的項(xiàng)集；第二步利用頻繁項(xiàng)集構(gòu)造出滿(mǎn)足用戶(hù)最小可信度的規(guī)則.

2 Apriori算法的不足之處

Apriori算法最大的優(yōu)點(diǎn)是算法思路比較簡(jiǎn)單，它以遞歸統(tǒng)計(jì)為基礎(chǔ)，生成頻繁項(xiàng)集，易于實(shí)現(xiàn).Apriori算法雖然能夠從海量數(shù)據(jù)中挖掘出關(guān)聯(lián)規(guī)則，但是算法在執(zhí)行速度和效率上有一定的局限性，表現(xiàn)如下：

2.1 Apriori算法會(huì)產(chǎn)生大量的候選項(xiàng)集.該算法是由候選集函數(shù)Apriori-Gen利用Lk-1項(xiàng)產(chǎn)生候選項(xiàng)集Ck，所產(chǎn)生的Ck由CkLk-1項(xiàng)集組成.顯然k越大產(chǎn)生的候選項(xiàng)集的數(shù)目就越多.

2.2 I/O負(fù)載過(guò)大.Apriori算法需要多次掃描事務(wù)數(shù)據(jù)庫(kù)，需要很大的I/O負(fù)載.對(duì)每次k循環(huán)，候集Ck中的每個(gè)元素都必須掃描數(shù)據(jù)庫(kù)1次來(lái)決定其是否加入Ck.例如，一個(gè)頻繁大項(xiàng)目集包含12個(gè)項(xiàng)，那么就至少掃描事務(wù)數(shù)據(jù)庫(kù)12遍.

同理心對(duì)于做好辦公室工作尤其重要，在日常工作中，要有意識(shí)地安排一些活動(dòng)，形成一種氛圍去培養(yǎng)辦公室工作人員的同理心，這有利于我們做好辦公室的工作。但同時(shí)，也要正確認(rèn)識(shí)同理心，在合理利用同理心做好工作的同時(shí)，也要合理規(guī)避同理心帶來(lái)的負(fù)面影響，加強(qiáng)制度的約束力和執(zhí)行力。確保同理心能在合適的范圍得到充分的利用，服務(wù)于我們的辦公室工作。

3 對(duì)Apriori算法的改進(jìn)

算法改進(jìn)的思路

1.改變數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，用二進(jìn)制位存儲(chǔ)各項(xiàng)目的事務(wù)集，矩陣的列代表頻繁K-項(xiàng)集，矩陣的行代表事務(wù)，其中1表示該項(xiàng)目在某事務(wù)中出現(xiàn)，0表示該項(xiàng)目在某事務(wù)中沒(méi)有出現(xiàn).

2.生成頻繁1-項(xiàng)集.首先掃描源數(shù)據(jù)庫(kù)，生成矩陣.統(tǒng)計(jì)每列中包含1的數(shù)目,得到該項(xiàng)目的支持事務(wù)數(shù)，如果該項(xiàng)的支持事務(wù)數(shù)大于最小支持事務(wù)數(shù)，則該項(xiàng)是頻繁項(xiàng)集，否則是非頻繁項(xiàng)集.從矩陣中將該列刪除,并根據(jù)引理1，在矩陣中刪除第9行，得出頻繁1-項(xiàng)集.

3.由頻繁1-項(xiàng)集生成頻繁2-項(xiàng)集.對(duì)頻繁1-項(xiàng)集中的項(xiàng)兩兩連接得出候選2-項(xiàng)集,也就是對(duì)矩陣中第i列所代表的項(xiàng)集和第j列所代表的項(xiàng)集進(jìn)行邏輯與操作.然后計(jì)算支持候選2-項(xiàng)集各項(xiàng)集的事務(wù)集,在矩陣中刪除支持事務(wù)數(shù)小于最小支持事務(wù)數(shù)項(xiàng)集對(duì)應(yīng)的列,根據(jù)引理1，在矩陣中刪除第4、6、10行.得出頻繁2-項(xiàng)集.

4.類(lèi)推，得到頻繁K-項(xiàng)集，直到不能產(chǎn)生新的頻繁項(xiàng)集為止.

4 改進(jìn)算法舉例

假定最小支持?jǐn)?shù)為3

?

第一步 生成初始矩陣

?

第二步 將支持度小于3的列刪除.得到L1=(a,b,c,d)

?

第三步 將支持度小于3的列刪除，且根據(jù)引理1，刪除第9行,得到L2=(ac,bc,bd,cd)

?

第四步 將支持度小于3的列刪除，且根據(jù)引理1，刪除第4,6,10行,得到L3=(bcd)

?

5 結(jié)束語(yǔ)

進(jìn)算法通過(guò)改進(jìn)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，利用“0”和“1”存儲(chǔ)各項(xiàng)目的事務(wù)集，采用邏輯運(yùn)算求得某項(xiàng)集的支持事務(wù)數(shù)，再根據(jù)給定的最小支持?jǐn)?shù)生成頻繁項(xiàng)集.改進(jìn)后的算法與Apriori算法相比具有以下優(yōu)勢(shì)：（1）整個(gè)數(shù)據(jù)庫(kù)只要掃描一次.（2）由頻繁k-1項(xiàng)集直接生成頻繁k項(xiàng)集，不需要再掃描整個(gè)數(shù)據(jù)庫(kù).3)在求k頻繁項(xiàng)集時(shí)，刪除了長(zhǎng)度小于K的事務(wù).節(jié)約了存儲(chǔ)空間，算法的效率也大大提高.

〔1〕劉軍，謝康林.一種改進(jìn)的關(guān)聯(lián)規(guī)則提取算法[J].型微型計(jì)算機(jī)系統(tǒng)，2003(7).

〔2〕安穎．基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法研究[D]北京：北京工業(yè)大學(xué)，2009.

〔3〕楊志剛,何月順.基于壓縮事務(wù)矩陣相乘的Apriori改進(jìn)算法[J].中國(guó)新技術(shù)新產(chǎn)品,2010,30(6):57-58..

〔4〕黃建明,趙文靜,王星星.基于十字鏈表的 Apriori改進(jìn)算法[J].計(jì)算機(jī)工程,2009,35(2):37-38.

〔5〕李云峰,陳建文,程代杰.關(guān)聯(lián)規(guī)則挖掘的研究及對(duì)Apriori算法的改進(jìn)[J].計(jì)算機(jī)工程與科學(xué),2002,24(6):65-68.