李俊
【摘 要】為解決Apriori算法多次遍歷數(shù)據(jù)庫及產(chǎn)生大量中間冗余候選項集等問題,文章提出了一種基于對角線下方全為0的矩陣和向量矩陣相結(jié)合的改進(jìn)算法,該算法只對數(shù)據(jù)庫進(jìn)行一次遍歷,通過遍歷對角線下方全為0的矩陣可獲取頻繁1項集與頻繁2項集及候選3項集,再將候選3項集與布爾向量矩陣的各行循環(huán)做“與”運(yùn)算后相加,即可得項集支持度。通過實驗對比,改進(jìn)算法能較好地挖掘頻繁項集,提高了運(yùn)行效率和存儲空間利用率。
【關(guān)鍵詞】數(shù)據(jù)挖掘;Apriori算法;關(guān)聯(lián)規(guī)則;向量矩陣
【中圖分類號】TP311.13 【文獻(xiàn)標(biāo)識碼】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ù)工作量大,造成了空間和時間的浪費(fèi)。
本文基于上述的問題提出了一種基于矩陣和向量矩陣相結(jié)合的改進(jìn)算法。算法對只數(shù)據(jù)庫進(jìn)行一次遍歷,通過遍歷矩陣可獲取頻繁1項集與頻繁2項集及候選3項集,然后將候選3項集與布爾向量矩陣的各行循環(huán)做“與”運(yùn)算后相加即可得項集支持度。
2 Apriori改進(jìn)算法
2.1 算法的改進(jìn)思想
首先通過掃描數(shù)據(jù)庫將事物數(shù)據(jù)庫同時映射為對角線下方全為0的矩陣和只布爾向量矩陣。算法只對數(shù)據(jù)庫進(jìn)行一次遍歷,通過掃描矩陣可獲得頻繁1-項集、頻繁2-項集和候選3-項集。將候選3項集與布爾向量矩陣的各行循環(huán)做“與”運(yùn)算后相加即可得候選項集支持度。執(zhí)行步驟如下。
step1:先將事務(wù)數(shù)據(jù)庫同時轉(zhuǎn)換為對角線下方全為0的矩陣F和只含有0和1的布爾向量矩陣matrix。
step2:由于矩陣F的主對角線的數(shù)值表示單個項集在事務(wù)數(shù)據(jù)庫里出現(xiàn)的總次數(shù),讀取主對角線數(shù)值可得頻繁1項集。矩陣F的上三角數(shù)值代表項集在事物數(shù)據(jù)庫中總的計數(shù),通過與最小支持度比較可獲取頻繁2-項集。
step3:根據(jù)原始的Apriori算法對頻繁2-項集進(jìn)行自連接剪枝后能獲取候選3項集。
step4:將候選3項集合的各個項目轉(zhuǎn)為只含數(shù)值0和1的二進(jìn)制編碼向量,并將候選3項集的二進(jìn)制向量與布爾矩陣matrix的各行循環(huán)做“與”運(yùn)算后相加即可得項集支持度,從而生成了頻繁3-項集。
當(dāng)k>=4時,循環(huán)步驟5。
step5:將頻繁k-1項集自連接產(chǎn)生候選k項集,將候選k項集與布爾向量矩陣matrix的各行循環(huán)做“與”運(yùn)算后相加即可得項集支持度,當(dāng)不能產(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為“事物標(biāo)識”,列cv表示“項集標(biāo)識”
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的二進(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++ %計算支持度
if C_supkCi=0 else
Lk=候選集Ck的C_supk大于等于最小支持度的項目集合
if Lk==null %若頻繁項集為空,則運(yùn)算結(jié)束
return 1
2.3 Improved_Apriori算法的實現(xiàn)
下面結(jié)合案例來詳細(xì)說明算法的實現(xiàn)方法。設(shè)存在事物數(shù)據(jù)庫BD={T1,T2,T3,T4,T5,T6,T7,T8},DB中包含有8個事物,對應(yīng)的項目集I={A,B,C,D},如表1所示,設(shè)最小支持度min_sup為2。
(1)先對數(shù)據(jù)庫DB進(jìn)行掃描,生成對角線下方全為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進(jìn)行逐行掃描,獲取對角線位置的元素,生成頻繁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)為二進(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-項集為{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 改進(jìn)算法的實驗及性能分析
為對比分析改進(jìn)的Improved_Apriori算法與原始的Apriori算法的運(yùn)行效率,將這2種算法在不一樣數(shù)據(jù)記錄下的執(zhí)行時間進(jìn)行比較。
本測試的數(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進(jìn)行預(yù)處理。本實驗將采用不同的事物記錄數(shù)、不同的項目數(shù)及不同的支持度來對比計算2種算法的運(yùn)行時間。
(1)設(shè)最小支持度為6,該數(shù)據(jù)集的項目數(shù)為23。在事物數(shù)量不同的實驗條件下,這2種算法的執(zhí)行時間見表5。
由圖1可知,保持最小支持度不變,原始的apriori算法的執(zhí)行時間明顯大于改進(jìn)的Improved_Apriori算法運(yùn)行時間。
(2)該組測試取事物數(shù)據(jù)條數(shù)為8 000條,截取數(shù)據(jù)集的項目數(shù)為23。在支持度不同的條件下,這2種算法的執(zhí)行時間見表6。
經(jīng)圖2可知,隨著支持度的不斷增加,2種算法的執(zhí)行時間逐漸減少,然而原始的apriori算法的減少范圍更大。由圖2可得出:事物數(shù)據(jù)條數(shù)及項目數(shù)不變,支持度越小,改進(jìn)算法比原始算法的處理效率要高很多。
(3)該組測試選取的事物數(shù)為8 000條,支持度為3。實驗中,通過選取不同的項目個數(shù),計算執(zhí)行時間。2種算法的執(zhí)行時間見表7。
經(jīng)圖3可知,事物數(shù)據(jù)條數(shù)及支持度不變,當(dāng)項目數(shù)不斷增加時,2種算法的運(yùn)行時間也同時增加。由圖3可知,改進(jìn)的Improved_ Apriori比原始的apriori算法執(zhí)行效率更高。
改進(jìn)的Improved_ Apriori主要有以下幾個方面的優(yōu)點(diǎn)。
(1)由于將事物數(shù)據(jù)庫轉(zhuǎn)為單純的數(shù)字型類型,從而壓縮了存儲空間,減少I/0負(fù)擔(dān),大大提高空間利用效率。
(2)在獲取所有頻繁項集時,只需對事物數(shù)據(jù)庫進(jìn)行一次掃描,程序執(zhí)行效率得到提高,在時間利用效率上也有了明顯的提高。
(3)Improved_ Apriori算法通過對角線下方全為0的矩陣直接獲取了頻繁1-項集和頻繁2-項集及候選3-項集,避免大量無用中間候選2-項集的產(chǎn)生。
4 結(jié)語
本文針對Apriori算法存在的問題,提出了一種基于對角線下方全為0的矩陣和向量矩陣相結(jié)合的改進(jìn)算法,并將改進(jìn)的算法和原始算法進(jìn)行性能分析,算法通過將事情數(shù)據(jù)庫壓縮為矩陣,有效地減少了數(shù)據(jù)庫掃描次數(shù),同時減少了大量冗余候選2-項集的產(chǎn)生,從而從時間和空間上獲取了良好的性能。
參 考 文 獻(xiàn)
[1]王文正,王文平,許映秋,等.一種基于上三角頻繁項集矩陣的頻繁模式挖掘算法[J].微電子學(xué)與計算機(jī),2010,27(9):138-143.
[2]羅丹,李陶深.一種基于壓縮矩陣的Apriori算法改進(jìn)研究[J].計算機(jī)科學(xué),2013,40(12):75-80.
[3]曲睿,張?zhí)鞁?基于矩陣壓縮的Apriori改進(jìn)算法[J].計算機(jī)工程與設(shè)計,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ī)技術(shù)與發(fā)展,2016,26(6):62-64,68.
[6]陶立秋.改進(jìn)的Apriori算法在微信熱點(diǎn)分析中的應(yīng)用研究[D].武漢:華中師范大學(xué),2015.
[責(zé)任編輯:鐘聲賢]