基于關聯規則的Apriori改進算法

李俊

【摘 要】為解決Apriori算法多次遍歷數據庫及產生大量中間冗余候選項集等問題，文章提出了一種基于對角線下方全為0的矩陣和向量矩陣相結合的改進算法，該算法只對數據庫進行一次遍歷，通過遍歷對角線下方全為0的矩陣可獲取頻繁1項集與頻繁2項集及候選3項集，再將候選3項集與布爾向量矩陣的各行循環做“與”運算后相加，即可得項集支持度。通過實驗對比，改進算法能較好地挖掘頻繁項集，提高了運行效率和存儲空間利用率。

【關鍵詞】數據挖掘；Apriori算法；關聯規則；向量矩陣

【中圖分類號】TP311.13 【文獻標識碼】A 【文章編號】1674-0688（2018）09-0042-04

1 概述

Apriori算法是經典的關聯規則挖掘算法之一，它分為兩個過程：查找頻繁項集及生成關聯規則，核心是頻繁項集的自連接和候選集的剪枝。然而該算法存在幾個挑戰：？譹？訛事物數據庫的多次掃描；？譺？訛產生龐大的中間候選項集；？譻？訛候選項集的支持度計算需不斷掃描數據庫，支持度計數工作量大，造成了空間和時間的浪費。

本文基于上述的問題提出了一種基于矩陣和向量矩陣相結合的改進算法。算法對只數據庫進行一次遍歷，通過遍歷矩陣可獲取頻繁1項集與頻繁2項集及候選3項集，然后將候選3項集與布爾向量矩陣的各行循環做“與”運算后相加即可得項集支持度。

2 Apriori改進算法

2.1 算法的改進思想

首先通過掃描數據庫將事物數據庫同時映射為對角線下方全為0的矩陣和只布爾向量矩陣。算法只對數據庫進行一次遍歷，通過掃描矩陣可獲得頻繁1-項集、頻繁2-項集和候選3-項集。將候選3項集與布爾向量矩陣的各行循環做“與”運算后相加即可得候選項集支持度。執行步驟如下。

step1：先將事務數據庫同時轉換為對角線下方全為0的矩陣F和只含有0和1的布爾向量矩陣matrix。

step2：由于矩陣F的主對角線的數值表示單個項集在事務數據庫里出現的總次數，讀取主對角線數值可得頻繁1項集。矩陣F的上三角數值代表項集在事物數據庫中總的計數，通過與最小支持度比較可獲取頻繁2-項集。

step3：根據原始的Apriori算法對頻繁2-項集進行自連接剪枝后能獲取候選3項集。

step4：將候選3項集合的各個項目轉為只含數值0和1的二進制編碼向量，并將候選3項集的二進制向量與布爾矩陣matrix的各行循環做“與”運算后相加即可得項集支持度，從而生成了頻繁3-項集。

當k>=4時，循環步驟5。

step5：將頻繁k-1項集自連接產生候選k項集，將候選k項集與布爾向量矩陣matrix的各行循環做“與”運算后相加即可得項集支持度，當不能產生頻繁k項集即可退出循環，算法結束，否則繼續。

算法的偽代碼如下：

Improved_ Apriori算法的描述如下：

輸入：事物數據庫DB，最小支持度

輸出：頻繁項集

%取一條記錄row，生成對角線下方全為0的矩陣F

for A，B in row %若記錄中任意兩項A，B若都為1則將對角線上方位置F[A][B]加1

for each A==1&B==1

F[A][B]++

%生成布爾向量矩陣matrix，行rv為“事物標識”，列cv表示“項集標識”

rv=size（DB，1）；%獲取數據庫DB行數即事物數

cv= size（DB，1）；%獲取數據庫DB列數即事物中包含的項目總數

matrix=zeros（rv，cv）；%

for i=1：M

for j=1：N

matrix（i，DB（i，j））=1；

%通過掃描矩陣F對角線生成候選-1項集的支持度從而生成頻繁1項集

for i=1：rv

if F[i][i]>=min_sup %對比最小支持度即可獲得一項頻繁集L1

L1=F矩陣對角線大于最小支持度的項目集合

%產生頻繁2項集L2

for i=1：rv

for j=1：cv

if F[i][j]>=min_sup

L2=F矩陣中除對角線大于最小支持度的項目集合

%L2自連接獲取候選3項集

C3=L2xL2

%產生K項頻繁集

for each C 屬于Ck

C_supk==0，BC=0 %初始化候選項的支持度C_supk，候選集C的二進制碼為BC

從左往右掃描C的列若等于0則BC加0，否則加1

for i in matrixi

if Ci==0 then continue

if BC&matrixi=BC %候選集的二進制碼與矩陣的行向量進行“與”運算

C_supk++ %計算支持度

if C_supkCi=0 else

Lk=候選集Ck的C_supk大于等于最小支持度的項目集合

if Lk==null %若頻繁項集為空，則運算結束

return 1

2.3 Improved_Apriori算法的實現

下面結合案例來詳細說明算法的實現方法。設存在事物數據庫BD={T1，T2，T3，T4，T5，T6，T7，T8}，DB中包含有8個事物，對應的項目集I={A，B，C，D}，如表1所示，設最小支持度min_sup為2。

（1）先對數據庫DB進行掃描，生成對角線下方全為0的矩陣F和布爾矩陣matrix。矩陣matrix的行代表事物，列代表項。生成的結果如下所示。

F=5 6 2 7 6 2 5 4 2 6

matrix=1 1 0 11 1 1 11 0 0 10 1 1 01 0 1 01 1 0 10 1 1 10 1 0 1

（2）生成頻繁1-項集L1。對矩陣F進行逐行掃描，獲取對角線位置的元素，生成頻繁1-集L1。掃描矩陣F中除對角線位置的數值，生成頻繁2-項集L2。查找結果見表2、表3。

（3）由表3可知，頻繁2-項集L2為{A，B}，{A，C}，{A，D}，{B，C}，{B，D}，{C，D}，由頻繁2-項集生成候選3-項集{A，B，C}{A，B，D}{A，C，D}{B，C，D}。為求頻繁3項集- L3，先將候選3項集轉為二進制向量，即{A，B，C}→1110，{A，B，D}→1101，{A，C，D}→1011，{B，C，D}→0111，將轉換的二進制向量依次與矩陣matrix的每行進行“與”運算后進行求和。

（4）頻繁3-項集為{A，B，D}，{B，C，D}，由于此兩頻繁項集無法自連接，算法結束。綜合上述的計算結果可得出在事物數據庫DB中，包含頻繁項集L1={A，B，D}，L2={B，C，D}。根據Aporiori的性質可知，由L1生成的非空子集也是頻繁的，L1的非空子集有{A}{B}{D}{A，B}{A，D}{B，D}。同樣可得L2的非空子集有則{B}{C}{D}{B，C}{B，D}{C，D}。可以生成如下的關聯規則：

B -> D 置信度：83.333 3%

D -> B 置信度：83.333 3%

A -> D 置信度：80%

D -> A 置信度：66.666 7%

A -> B 置信度：60%

C -> B 置信度：75%

A -> B，D 置信度：60%

A，B -> D 置信度：100%

A，D -> B 置信度：75%

B，D -> A 置信度：60%

B，C -> D 置信度：66.666 7%

C，D -> B 置信度：100%

3 改進算法的實驗及性能分析

為對比分析改進的Improved_Apriori算法與原始的Apriori算法的運行效率，將這2種算法在不一樣數據記錄下的執行時間進行比較。

本測試的數據來源于mushroom.dat數據集（http：//fimi.ua.ac.be/）。測試環境：操作系統為win7 64位，內存容量為8 G，測試工具為Matlab 2016a。實驗時利用oracle的plsqldev工具先將mushroom.dat進行預處理。本實驗將采用不同的事物記錄數、不同的項目數及不同的支持度來對比計算2種算法的運行時間。

（1）設最小支持度為6，該數據集的項目數為23。在事物數量不同的實驗條件下，這2種算法的執行時間見表5。

由圖1可知，保持最小支持度不變，原始的apriori算法的執行時間明顯大于改進的Improved_Apriori算法運行時間。

（2）該組測試取事物數據條數為8 000條，截取數據集的項目數為23。在支持度不同的條件下，這2種算法的執行時間見表6。

經圖2可知，隨著支持度的不斷增加，2種算法的執行時間逐漸減少，然而原始的apriori算法的減少范圍更大。由圖2可得出：事物數據條數及項目數不變，支持度越小，改進算法比原始算法的處理效率要高很多。

（3）該組測試選取的事物數為8 000條，支持度為3。實驗中，通過選取不同的項目個數，計算執行時間。2種算法的執行時間見表7。

經圖3可知，事物數據條數及支持度不變，當項目數不斷增加時，2種算法的運行時間也同時增加。由圖3可知，改進的Improved_ Apriori比原始的apriori算法執行效率更高。

改進的Improved_ Apriori主要有以下幾個方面的優點。

（1）由于將事物數據庫轉為單純的數字型類型，從而壓縮了存儲空間，減少I/0負擔，大大提高空間利用效率。

（2）在獲取所有頻繁項集時，只需對事物數據庫進行一次掃描，程序執行效率得到提高，在時間利用效率上也有了明顯的提高。

（3）Improved_ Apriori算法通過對角線下方全為0的矩陣直接獲取了頻繁1-項集和頻繁2-項集及候選3-項集，避免大量無用中間候選2-項集的產生。

4 結語

本文針對Apriori算法存在的問題，提出了一種基于對角線下方全為0的矩陣和向量矩陣相結合的改進算法，并將改進的算法和原始算法進行性能分析，算法通過將事情數據庫壓縮為矩陣，有效地減少了數據庫掃描次數，同時減少了大量冗余候選2-項集的產生，從而從時間和空間上獲取了良好的性能。

參 考 文 獻

[1]王文正，王文平，許映秋，等.一種基于上三角頻繁項集矩陣的頻繁模式挖掘算法[J].微電子學與計算機，2010，27（9）：138-143.

[2]羅丹，李陶深.一種基于壓縮矩陣的Apriori算法改進研究[J].計算機科學，2013，40（12）：75-80.

[3]曲睿，張天嬌.基于矩陣壓縮的Apriori改進算法[J].計算機工程與設計，2017，38（8）：2127-2131.

[4]葉濤，于利霞，張亞平.基于上三角矩陣構造多叉樹的多維關聯規則挖掘算法[J].軟件工程，2017，20（6）：8-

11，4.

[5]宋文慧，高建瓴.基于矩陣的Apriori算法改進[J].計算機技術與發展，2016，26（6）：62-64，68.

[6]陶立秋.改進的Apriori算法在微信熱點分析中的應用研究[D].武漢：華中師范大學，2015.

[責任編輯：鐘聲賢]