基于權值向量矩陣約簡的Apriori算法

楊秋翔，孫 涵

(中北大學 軟件學院，山西 太原 030051)

0 引 言

數據挖掘是指通過數據分析，自動從大量數據中找出其中隱藏的特殊關系的過程[1]。關聯規則挖掘作為使用最廣泛的一種，可以發現大量數據間的關聯關系，為人們快速決策提供依據。Apriori算法作為一種經典的關聯規則挖掘算法，被廣泛應用于商業和網絡安全領域，但其存在數據庫掃描次數多、挖掘過程中頻繁項集丟失以及生成效率低等缺陷。

針對以上問題，國內外學者從改變數據結構和矩陣壓縮兩方面提出解決方案。Han J等參考Huffman樹結構，利用與根節點距離的思想，提出一種基于模式增長的FP-Growth算法[2]。將各項按項目支持數大小排序，支持度高則距離根節點近，充分利用了已有的頻繁項集。該算法雖然在一定程度上提高了頻繁項集的生成效率，但隨著項集數量的增加，并不能彌補需要多次掃描數據庫的缺陷。Park等提出基于Hash方法的DHP算法[3]，該算法利用數據結構哈希樹原理提高了運算效率。當某一葉子節點存放的項集超過預設值時，將該節點裂解為新的葉子節點[4]。該算法中生成的候選項集按照哈希函數分配，一次函數遍歷就可以完成項集的統計。但面對海量數據時計數工作量大，且依舊需要多次掃描數據庫，所以并不適用與海量數據的挖掘。基于壓縮矩陣的Apriori算法利用矩陣表示數據庫信息，解決了多次掃描數據庫的問題。通過對事務和項集的壓縮，降低了候選項集規模[5]。蘇姜妍等[6]提出基于壓縮矩陣先找出最大頻繁k項集，再逐步找出其余頻繁項集的算法。付沙等[7]提出基于壓縮矩陣的Apriori算法：NCM-Apriori-1。該算法通過聚類技術壓縮數據庫規模，不需要生成候選項集。但基于壓縮矩陣的Apriori算法在矩陣壓縮過程中存在數據丟失的問題，進而引起頻繁項集遺漏等現象，部分算法在執行過程中會生成大量與頻繁項集無關的元素[8]。

本文提出一種基于權值向量矩陣約簡的Apriori算法，在數據清洗階段對項集中各元素賦予權值，有效降低了源數據規模，運算過程中不斷約簡矩陣，提高了算法的運算效率。

1 關聯規則概念和算法原理

1.1 基本概念

關聯規則挖掘可表示為：設I={i1,i2,i3…im} 是待挖掘項的集合，T={t1,t2,t3…tn} 是挖掘事務的集合，其中ti(1≤i≤n)[9]。A、B稱為T中的關聯規則，其中A∈I、B∈I、A∩B=?，目的是為了找出其中的強關聯規則[10]。算法執行初期需要用戶定義支持度和置信度，其中支持度指某事務占全部事務的百分比，置信度則表示在包含A事務的同時，包含B事務的百分比。在項的集合中，假設全體事務為T，A?B的支持度記作：support(A?B)，表示為support(A?B)=P(A∪B)，A?B的置信度為confidence(A?B)，表示為confidence(A?B)=P(B/A)[11]。在一次關聯規則挖掘中，若T中有關聯規則A?B滿足支持度和置信度均大于等于其對應的最小閾值，則稱A?B是T中的強關聯規則。

本文研究重點在降低源數據規模的同時減少頻繁項集的丟失，提高關聯規則挖掘效率。

1.2 相關性質和定理

在生成的布爾矩陣中，行代表事務，列代表項目。矩陣中每行“1”的個數，代表該事務的項目數，項目的支持數可用每列中“1”的個數表示。

定理1[12]若矩陣中某項的支持數小于sup，則刪除該項對應的列。

定理2[13]若某行項目數為“0”，則刪除該項對應的行。

定理3[14]若某頻繁k項集集合中項集個數小于k+1，則該頻繁項集為最大頻繁項集。

2 Apriori算法的改進

2.1 算法改進思想

(1)基于項集重要性和用戶感興趣項集的方法，從數據庫所有項集中選取一個子集作為研究對象，將待研究項目集用事務標識號標記，并對各元素賦值。

(2)在頻繁k項集生成過程中，首先由事務項目數和項目支持數計算sup，比較各項項目支持數，刪除支持數小于sup的項在矩陣中對應的列。此時矩陣為頻繁k項集對應的矩陣，由定理3判斷該頻繁項集是否為最大頻繁項集，若不是則重新整理矩陣，統計新矩陣事務項目數，若存在某事務項目數為“0”，則從矩陣中刪除該事務行，按照上述方法繼續尋找頻繁k+1項集。否則終止查找過程。

2.2 算法流程

輸入：事務數據庫D，最小支持度min-support

輸出：關聯規則S

算法流程如下：

(1)選擇挖掘對象。從事務數據庫D中選取待研究項集，對項集中各元素賦予權值。得到挖掘對象D1。

(2)生成與數據庫D1對應的布爾矩陣。在矩陣后方添加一列，用于記錄事務項目數，在矩陣下方添加一行，記錄項目支持數。計算各項支持數sup。若某項支持數小于sup，根據定理1刪除該矩陣列。調整矩陣格式，重新計算事務項目數，根據定理2刪除統計值為“0”的事務在矩陣中對應的行。此時即為頻繁1項集對應的矩陣。

(3)將矩陣中各項將上述矩陣按各項支持數降序排列，得到矩陣D2。將D2中任意兩列組合，通過向量間“與”運算，求得各組合的支持數。按照(2)中方法約簡矩陣，生成頻繁2項集對應的矩陣。調整后記為矩陣D3。

(4)頻繁k項集的確定(k>2)，參照上述步驟(1)、(2)的矩陣簡化方法。若某頻繁項集滿足定理3，此即為最大頻繁項集，與之對應的矩陣記為Dk+1。

(5)頻繁k項集的集合用L表示。由L生成的所有非空集S中，若S中某個項集的最小支持度大于用戶定義的最小置信度，則存在強關聯規則“S→L-S”。

3 算法分析和實驗對比

3.1 算法分析

與基于壓縮矩陣的Apriori算法相比，本案優點如下：

(1)基于權值向量矩陣約簡的Apriori算法可以基于項集重要性和用戶興趣度從事務數據庫D中選擇待挖掘子集，并對項集中各元素賦予權值，可針對性的選取與所研究課題關系密切的子集，從數據源降低數據規模。

(2)算法的時間復雜度描述了一個算法的運行時間。基于權值向量矩陣約簡的Apriori算法中，頻繁項集的生成過程只與矩陣運算有關，將數據庫D1生成的布爾矩陣記為Rm×n，該算法的時間復雜度為O(mkn)。基于壓縮矩陣的Apriori算法平均時間復雜度為O(wk+1)，w代表項集個數，其值遠大于m，且隨著運算的進行，項集m呈指數級增長。所以本案時間復雜度遠小于基于壓縮矩陣的Apriori算法。

(3)基于權值向量矩陣約簡的Apriori算法在頻繁項集生成過程中，不斷刪除不符合條件的矩陣行與列。隨著k值的增長，頻繁k項集對應的矩陣Dk+1結構變的愈簡單。

3.2 實例分析

本案選取UCI數據集中的Thyroid+Disease集作為研究對象。首先對數據集做預處理，對項集中元素賦予權值，獲得符合數據挖掘要求的目標數據：DS={{ABDE},{ADE},{BDEF},{ABDE},{ACE},{BDE},{BCDE}}設最小支持度為0.3。

(1)將數據按照各項支持數降序排列，添加事務項目數和項目支持數后得到矩陣R

矩陣項集的最小支持數根據定義：sup=ceiling(min sup_count)=ceiling(min-support×n)=3。

(2)根據R求得頻繁1項集，按照步驟(1)處理后，重新整理得矩陣R1。

比較矩陣中各列支持數與sup大小，刪除支持數小于sup的矩陣列，得到矩陣R1。此即為頻繁1項集對應的矩陣

由此可求得頻繁1項集L1={{A}，{B}，{D}，{E}}。

(3)根據矩陣R1，求頻繁2項集。

按照步驟(3)，選取A和D進行“與”運算

sup_count(A∧D)=min sup-count=3， 所以{A,D}為頻繁2項集。重復上述步驟可得頻繁2項集為：L2={{AD},{AE},{BD},{BE},{DE}}。

(4)按照步驟(4)的流程，求頻繁3項集。

由定理1得矩陣R2如下所示

頻繁3項集的候選項集為：C3={{ABD},{ABE},{ADE},{BDE}} 求得各組合支持數分別為：count(ABE)=2，count(ACE)=3,count(ADE)=2，count(BDE)=5， 對比sup，可得頻繁3項集為：L3={{ABE},{BDE}}。

該頻繁項集中，項集個數小于4，符合定理3要求，所以此頻繁3項集為最大頻繁集。又存在L=L1∪L2∪L3， 由此證明該算法可行。

3.3 挖掘結果分析

利用3.2中數據集，設計如下對比實驗，在不同支持度下統計兩種算法生成的頻繁項集數量。

算法執行過程中一個重要因素是產生候選項集的數量，因為數據預處理可能會造成邊緣數據或重要數據的丟失，若兩算法產生的候選項集接近，則證明該算法可行。實驗結果如圖1所示，由圖可知，在相同支持度下基于權值向量矩陣約簡的Apriori算法產生的頻繁項集數量比基于壓縮矩陣的Apriori算法多，隨著用戶預設最小支持度的提高，兩種算法生成的頻繁項集數量趨于相等。

圖1 改進后的Apriori算法與基于壓縮矩陣的Apriori算法產生候選項集數量對比

3.4 算法執行效率分析

為比較基于壓縮矩陣的Apriori算法與基于權值向量矩陣約簡的Apriori算法的執行效率，從IBM Quest Market-Basket Synthetic Data Generator生成3組項數為50，平均事務長度為0.6，事務數為2000，支持度為45%的數據。設計4組實驗，分別控制實驗中項數、密集度、事務數和支持度，記錄并對比兩種算法的運行時間。對比結果如圖2～圖5所示。

由實驗結果可知，改進后的Apriori算法在各支持度下均無頻繁項集丟失的問題，且算法運行時間減少提高了運算效率。

圖2 項數不同時運行時間對比

圖3 密集度不同時運行時間對比

圖4 事務數不同時運行時間對比

圖5 支持度不同時運行時間對比

4 結束語

基于權值向量矩陣約簡的Apriori算法，通過項集重要性和用戶感興趣度選取挖掘對象，從數據源處降低了數據規模。矩陣約簡的思想簡化了矩陣結構，避免了候選項集重復生成。與基于壓縮矩陣的Apriori算法相比，沒有與頻繁項集無關元素的生成，提高運算效率的同時不會造成頻繁項集的丟失。但該算法在執行前期需要對源數據做篩選等工作，對海量數據可能有一定局限性，所以接下來的工作主要是該算法在海量數據挖掘中的應用研究。

[1]LIU Haiyan,WANG Chao,NIU Junyu.An improved feature selection algorithm based on conditional mutual information[J].Computer Engineering,2012,38(14):36-42(in Chinese).[劉海燕,王超,牛軍鈺.基于條件互信息的特征選擇改進算法[J].計算機工程,2012,38(14):36-42.]

[2]Han J,Pei J,Yin Y.Mining frequent patterns without candidate generations[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data,2012:1-12.

[3]YANG Yanxia,FENG Lin.Parallel DHP data analysis method based on Hadoop platform[J].Computer Application,2016,36(12):3280-3284(in Chinese).[楊燕霞,馮林.基于Hadoop平臺的并行DHP數據分析方法[J].計算機應用,2016,36(12):3280-3284.]

[4]Zhang R,Wang H.Research of commonly used association rules mining algorithm in data mining[C]//International Conference on Internet Computer & Information Service.IEEE Computer Society,2015:219-222.

[5]LI Zhiliang.Research and application of Apriori algorithm based on clustering and compression matrix[D].Suzhou:Soochow University,2013(in Chinese).[李志亮.基于聚類和壓縮矩陣的Apriori算法的研究與應用[D].蘇州:蘇州大學,2013.]

[6]Sun jiangyan.An improved K-means clustering algorithm for the community discovery[J].Journal of Software Enginee-ring,2015,9(2):242-253.

[7]FU Sha,LIAO Minghua,SONG Dan.An improved Apriori algorithm based on compressed matrix[J].Microelectronics and Computer,2012,20(4):93-96(in Chinese).[付沙,廖明華,宋丹.基于壓縮矩陣方式的Apriori改進算法[J].微電子學與計算機,2012,20(4):93-96.]

[8]SUN Fengxiao,NI Shihong,XIE Chuan.An improved Apriori algorithm based on matrix[J].Computer Simulation,2013,30(8):245-249(in Chinese).[孫逢嘯,倪世宏,謝川.一種基于矩陣的Apriori改進算法[J].計算機仿真,2013,30(8):245-249.]

[9]YAN Zhen,PI Dechang,WU Wenhao.Research on frequent itemsets mining algorithm for high-dimensional sparse data[J].Computer Science,2011,38(6):183-186(in Chinese).[閆珍,皮德常,吳文昊.高維稀疏數據頻繁項集挖掘算法的研究[J].計算機科學,2011,38(6):183-186.]

[10]Tabakhi S.An unsupervised feature selection algorithm based on ant colony optimization[J].Engineering Applications of Artificial intelligence,2014,32(2):112-123.

[11]LUO Dan,LI Taoshen.An improved Apriori algorithm based on compression matrix[J].Computer Science,2013,40(12):75-80(in Chinese).[羅丹,李陶深.一種基于壓縮矩陣的Apriori算法改進研究[J].計算機科學,2013,40(12):75-80.]

[12]REN Weijian,YU Bowen.Improvement of Apriori algorithm based on matrix reduction[J].Computer and Modernization,2015,31(9):5-9(in Chinese).[任偉健,于博文.基于矩陣約簡的Apriori算法改進[J].計算機與現代化,2015,31(9):5-9.]

[13]PAN Guo.A classification algorithm based on regularized mutual information to improve input feature[J].Computer Engineering and Applications,2014,50(15):25-29(in Chinese).[潘果.基于正則化互信息改進輸入特征的分類算法[J].計算機工程與應用,2014,50(15):25-29.]

[14]LI Rui,KANG Liangyu,GENG Hao.Improvement of data-based association rules algorithm[J].Science & Technology and Engineering,2012,8(2):148-153(in Chinese).[李瑞,康良玉,耿浩.基于數據的關聯規則算法的改進[J].科學技術與工程,2012,8(2):148-153.]