李俊

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

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

【中圖分類號(hào)】TP311.13 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】1674-0688（2018）09-0042-04

1 概述

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

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

2 Apriori改進(jìn)算法

2.1 算法的改進(jìn)思想

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

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

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

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

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

當(dāng)k>=4時(shí)，循環(huán)步驟5。

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

算法的偽代碼如下：

Improved_ Apriori算法的描述如下：

輸入：事物數(shù)據(jù)庫(kù)DB，最小支持度

輸出：頻繁項(xiàng)集

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

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

for each A==1&B==1

F[A][B]++

%生成布爾向量矩陣matrix，行rv為“事物標(biāo)識(shí)”，列cv表示“項(xiàng)集標(biāo)識(shí)”

rv=size（DB，1）；%獲取數(shù)據(jù)庫(kù)DB行數(shù)即事物數(shù)

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

matrix=zeros（rv，cv）；%

for i=1：M

for j=1：N

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

%通過掃描矩陣F對(duì)角線生成候選-1項(xiàng)集的支持度從而生成頻繁1項(xiàng)集

for i=1：rv

if F[i][i]>=min_sup %對(duì)比最小支持度即可獲得一項(xiàng)頻繁集L1

L1=F矩陣對(duì)角線大于最小支持度的項(xiàng)目集合

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

for i=1：rv

for j=1：cv

if F[i][j]>=min_sup

L2=F矩陣中除對(duì)角線大于最小支持度的項(xiàng)目集合

%L2自連接獲取候選3項(xiàng)集

C3=L2xL2

%產(chǎn)生K項(xiàng)頻繁集

for each C 屬于Ck

C_supk==0，BC=0 %初始化候選項(xiàng)的支持度C_supk，候選集C的二進(jìn)制碼為BC

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

for i in matrixi

if Ci==0 then continue

if BC&matrixi=BC %候選集的二進(jìn)制碼與矩陣的行向量進(jìn)行“與”運(yùn)算

C_supk++ %計(jì)算支持度

if C_supkCi=0 else

Lk=候選集Ck的C_supk大于等于最小支持度的項(xiàng)目集合

if Lk==null %若頻繁項(xiàng)集為空，則運(yùn)算結(jié)束

return 1

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

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

（1）先對(duì)數(shù)據(jù)庫(kù)DB進(jìn)行掃描，生成對(duì)角線下方全為0的矩陣F和布爾矩陣matrix。矩陣matrix的行代表事物，列代表項(xiàng)。生成的結(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-項(xiàng)集L1。對(duì)矩陣F進(jìn)行逐行掃描，獲取對(duì)角線位置的元素，生成頻繁1-集L1。掃描矩陣F中除對(duì)角線位置的數(shù)值，生成頻繁2-項(xiàng)集L2。查找結(jié)果見表2、表3。

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

（4）頻繁3-項(xiàng)集為{A，B，D}，{B，C，D}，由于此兩頻繁項(xiàng)集無(wú)法自連接，算法結(jié)束。綜合上述的計(jì)算結(jié)果可得出在事物數(shù)據(jù)庫(kù)DB中，包含頻繁項(xiàng)集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 改進(jìn)算法的實(shí)驗(yàn)及性能分析

為對(duì)比分析改進(jìn)的Improved_Apriori算法與原始的Apriori算法的運(yùn)行效率，將這2種算法在不一樣數(shù)據(jù)記錄下的執(zhí)行時(shí)間進(jìn)行比較。

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

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

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

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

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

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

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

改進(jìn)的Improved_ Apriori主要有以下幾個(gè)方面的優(yōu)點(diǎn)。

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

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

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

4 結(jié)語(yǔ)

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

參 考 文 獻(xiàn)

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

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

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

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

11，4.

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

[6]陶立秋.改進(jìn)的Apriori算法在微信熱點(diǎn)分析中的應(yīng)用研究[D].武漢：華中師范大學(xué)，2015.

[責(zé)任編輯：鐘聲賢]