基于關(guān)聯(lián)規(guī)則的Apriori改進算法

李俊

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

【關(guān)鍵詞】數(shù)據(jù)挖掘；Apriori算法；關(guān)聯(lián)規(guī)則；向量矩陣

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

1 概述

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

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

2 Apriori改進算法

2.1 算法的改進思想

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

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

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

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

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

當k>=4時，循環(huán)步驟5。

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

算法的偽代碼如下：

Improved_ Apriori算法的描述如下：

輸入：事物數(shù)據(jù)庫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）；%獲取數(shù)據(jù)庫DB行數(shù)即事物數(shù)

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

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矩陣對角線大于最小支持度的項目集合

%產(chǎn)生頻繁2項集L2

for i=1：rv

for j=1：cv

if F[i][j]>=min_sup

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

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

C3=L2xL2

%產(chǎn)生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 %若頻繁項集為空，則運算結(jié)束

return 1

2.3 Improved_Apriori算法的實現(xiàn)

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

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

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中除對角線位置的數(shù)值，生成頻繁2-項集L2。查找結(jié)果見表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項集轉(zhuǎn)為二進制向量，即{A，B，C}→1110，{A，B，D}→1101，{A，C，D}→1011，{B，C，D}→0111，將轉(zhuǎn)換的二進制向量依次與矩陣matrix的每行進行“與”運算后進行求和。

（4）頻繁3-項集為{A，B，D}，{B，C，D}，由于此兩頻繁項集無法自連接，算法結(jié)束。綜合上述的計算結(jié)果可得出在事物數(shù)據(jù)庫DB中，包含頻繁項集L1={A，B，D}，L2={B，C，D}。根據(jù)Aporiori的性質(zhì)可知，由L1生成的非空子集也是頻繁的，L1的非空子集有{A}{B}{D}{A，B}{A，D}{B，D}。同樣可得L2的非空子集有則{B}{C}{D}{B，C}{B，D}{C，D}?？梢陨扇缦碌年P(guān)聯(lián)規(guī)則：

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種算法在不一樣數(shù)據(jù)記錄下的執(zhí)行時間進行比較。

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

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

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

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

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

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

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

改進的Improved_ Apriori主要有以下幾個方面的優(yōu)點。

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

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

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

4 結(jié)語

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

參 考 文 獻

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

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

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

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

11，4.

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

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

[責任編輯：鐘聲賢]