基于數組的關聯規(guī)則挖掘算法的研究

李 敏，潘祥光，曲云波

(1.哈爾濱商業(yè)大學計算機與信息工程學院哈爾濱 150028;2.哈爾濱工業(yè)美術設計學校，哈爾濱 150059)

當今世界，數據成為企業(yè)寶貴的資源.數據挖掘(Datamining)就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應用數據中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程［1］.關聯規(guī)則是數據挖掘在商品銷售領域研究的熱點之一.例如在購物籃分析當中，它可以從大量的交易數據中辨別交易項目之間是否存在某種關聯關系，從而得知顧客的購買習慣，這些信息可以指導商品的貨架布置，生產安排等，為企業(yè)的銷售決策提供支持.

關聯規(guī)則挖掘過程可以分為兩步:一是尋找頻繁項集;二是利用頻繁項集產生有價值的規(guī)則.第二步比較容易實現，當前大部分研究是針對第一步.所以，如何采用合適高效的算法找出全部的頻繁項集是核心問題，是衡量關聯規(guī)則挖掘算法的標準.傳統(tǒng)的算法是經典的Apriori，之后還有其改進算法AprioriTid和AprioriHybrid.但這些算法存在以下兩個缺點:1)多次掃描事務數據庫，I/O時空開銷大;2)可能產生龐大的候選項集，內存執(zhí)行時間面臨嚴峻挑戰(zhàn)，整個數據庫裝入內存是不現實的［2］.因此相繼提出了如數據分割，散列技術，抽樣技術，動態(tài)項集技術等優(yōu)化算法.

為了快速挖掘出頻繁項集，本文在相關性質和Apriori算法的基礎上，對基于數組的關聯規(guī)則算法進行改進，在頻繁項集進行自連接生成候選項集之前對項目計數，從而減少參與連接的項的數目，即減小生成候選項集的數量和規(guī)模，克服了Apriori需多次掃描數據庫和產生大量候選集的弊端，提高了挖掘頻繁項集的效率.

1 基本概念

設 Item={I1，I2，...，In}是所有項目的集合，D是相應的事務數據庫，其中每個事務T是一個項目子集(T?I)，且具有一個惟一的標識符TID.設A是一個項目集合，稱為項集.事務T包含項集A，當且僅當A?T.如果項集A中含有的項目個數為k，則稱其為k項集.

定義1 關聯規(guī)則:形如A?B的蘊涵式，其中 A?I，B?I，并且 A∩B=φ.

定義2 支持度:假如規(guī)則A?B在事務集D中成立，則支持度support定義為D中事務包含A∪B的百分比.support(A?B)=P(A∪B)

定義3 置信度:假如規(guī)則AB在事務集D中成立，則置信度從從confidence定義為D中包含A的事務同時也包含B的百分比，是一個條件概率.如果用support_count(A∪B)表示包含項集A∪B的事務數，support_conut(A)表示包含項集A的事務數，則

定義4 頻繁項集:項的集合稱為項集(itemset)，頻繁項集(frequent itemset)是滿足最小支持度的項集，即包含項集的事務數大于或等于min_sup與D中事務總數的乘積.

2 Apriori算法及相關性質

2.1 Apriori算法基本思想

Apriori算法是采用逐層搜索的迭代方法，自底向上的尋求數據庫中的頻繁項集.該算法需要多次循環(huán)，每次循環(huán)都利用上次循環(huán)產生的頻繁(K－1)項集產生頻繁K項集的候選項集，然后再掃描數據庫來檢驗是否為要尋找的頻繁項集.即用頻繁(K－1)項集搜索產生頻繁K項集.假設Ck是Lk的候選項集，不管其的成員是否為頻繁的，全部的頻繁K項集都包含在候選Ck當中.Ck當中的元素是否全部都為頻繁項集，在驗證的過程中，需要多次掃描事務數據庫.大量的研究表明，頻繁2項集的挖掘是Apriori算法的效率主要缺陷，當項目的數量達到一定范圍，算法的復雜度將呈指數級增長，嚴重影響了其運行效率.如果存在1萬個頻繁1項集的情況下，Apriori算法需要產生多達1千萬個候選2項集.如果需要發(fā)現長度為100的頻繁模式，所需的候選多達1030.由此可以看出Apriori算法的兩個瓶頸:

1)需要多次掃描整個事務數據庫

2)識別頻繁項目集時需要進行模式匹配，效率很低.

2.2 相關性質及推論

性質:設X是數據集D中的頻繁K項集，則X的所有(K－1)項子集也一定是頻繁(K－1)項集.

Apriori算法用這個性質用于壓縮搜索空間，減少候選項集的數量.

推論1:Xk是數據集D的頻繁K項集，則頻繁(K－1)項集集合 LK－1中包括 Xk的(K－1)項子集的個數一定是K.

推論2:如果 Xk={X1，X2，X3，….，Xk}是數據集D的頻繁K項集，則其每個元素Xi在頻繁(K－1)項集集合LK－1的所有(K－1)集合中出現次數一定不小于(K－1).

由上可知某個元素要成為某個K維頻繁項集中的元素，則該元素在頻繁(K－1)項集集合中出現的次數一定不小于(K－1)次.所以頻繁(K－1)項集在進行自連接之前統(tǒng)計出所有項出現的次數，然后刪除頻繁(K－1)項集中出現次數小于(K－1)的項集，就能夠事先判斷出不可能成為頻繁集的連接減少相當數量的存儲空間和節(jié)省大量的時間［3］.

3 改進算法的思想和步驟

在已有算法的基礎上［4－6］，改進算法的基本步驟:

1)掃描數據庫，根據數據庫中出現的事務記錄進行編碼［6］，用二維數組結構保存數據，其中行表示事務信息，列表示項信息.以后的操作只針對主存對數組處理，與數據庫無關.大大減少了I/O時空開銷，節(jié)省了時間.

2)在由LK－1項集進行自連接，生成Ck項集的過程以前，首先是統(tǒng)計LK－1項集中所有項目出現的次數.根據推論2刪除LK－1中出現的次數小于(K－1)次的項目集，修改后的 LK－1改為 L'K－1.L'K－1自連接生成 Ck.

3)對Ck根據Apriori算法進行剪枝得到LK，計算LK中的K項集的個數，如果項集個數小于(K+1)，則不必再進行(K+1)項集的運算，算法結束.如果不小于(K+1)，則轉2).

算法主要偽代碼如下:

輸入:事務數據庫D;最小支持度min_sup.

輸出:D的頻繁項集L.

InitialArray(D，A［n］［m+1］)//根據事務數據庫構造二維數組

4 算法實例

給出實例數據庫如表1，設最小支持數為2.

1)首先掃描數據庫將數據存入二維數組.函數 InitialArray(D，A［n］［m+1］) 對每個事務進行分解成單個項目存放在二維數組，A［n］［m+1］中(n為事務數，m為事務項數，m+1列統(tǒng)計總數)，如果該項存在，數組中用“1”表示，反之用“0”表示，結果如表2.

表1 實例數據庫min_sup=2

存二維數組

表2 二維數組對應表

2)根據頻繁1－項集的獲得函數

find_frequent_1_itemset(A［n］［m+1］)，對應二維數組中每列之和，即事務數據庫中包含的每項的總數(如表3)，通過與min_sup比較，大于min_sup的各項就是要找的頻繁1項集.表2的頻繁1項集 是{I1，I2，I3，I4，I5}.

表3 數據庫包含各項總數

3) 函數 apriori_gen(Lk－1，min_sup)根據頻繁

k項集產生候選k項集.掃描相應的數組的列，統(tǒng)計每個候選項集的頻度，如果數組中相應的列值均為1，則相應的計數值加1.由于篇幅限制，省略C2的產生過程，獲得的頻繁2項集是{I1I2，I1I3，I1I5，I2I3，I2I4，I2I5}.

3)統(tǒng)計L2中各項出現的次數(如表4)，其中I4的次數是1，所以I2I4不符合要求，刪除此項，獲得L'2(如表5).

表4 各項次數統(tǒng)計

表5 符合要求的2項集

5)獲得候選3項集(如表6).例如候選3項集{I1I3I5}，掃描數組中的I1I3I53列，只有在T8時3列同時是1，于min_sup=2.候選3項集{I1I2I3}，掃描數組中的I1I2I33列，T8，T9滿足三列同時是1，計數為2，得出{I1I2I3}就是頻繁3項集.頻繁3項集(如表7).{I1I2I3}和{I1I2I5}的頻繁計數是2，小于K+1=4(此時K是3)，算法結束，得到最大頻繁3項集.

表6 候選3項集

表7 頻繁3項集

5 結語

采用基于數組結構的方法對Apriori算法進行改進.該算法將事務數據庫中項集信息存入二維數組中，用行表示事務信息，用列表式項信息.依行掃描相應的列來獲得項集的頻度，同時對頻繁項集在進行自連接之前統(tǒng)計出所有項出現的次數，通過比較刪除無用的項目集，提高了效率.但算法還有一定的局限性，數據庫的規(guī)模影響到算法效率的提高程度.由于受到內存的限制，事務數據庫中的數據可能不會一次性的全部存入數組，而用于關聯規(guī)則挖掘的數據庫通常是非常大的.

［1］邵峰晶，于忠清.數據挖掘—原理與算法［M］.北京:中國水利水電出版社，2003:36－43.

［2］張月琴.基于0－1矩陣的頻繁項集挖掘算法研究［J］.計算機工程與設計，2009，30(20):4663－4664.

［3］楊妮妮.基于集合和位運算的頻繁集挖掘優(yōu)化算法［J］.科學技術與工程，2009，23(9):7173－7174.

［4］孟祥萍，錢 進，劉大有.基于數組的關聯規(guī)則挖掘算法［J］.計算機工程，2003，29(15):98－99.

［5］劉 瑩，郭福亮.基于數組的關聯規(guī)則挖掘算法［J］.計算機與數字工程，2005，38(34):39－40.

［6］廖小平，王志堅，吳海玲.基于項編碼的關聯規(guī)則挖掘算法［J］.計算機與現代，2008(11):50－51.

［7］李 敏，劉 杰，Aprior算法的研究及在商業(yè)決策中的應用［J］.哈爾濱商業(yè)大學學報:自然科學版，2010，26(6):706－709.