一種基于向量的概率加權(quán)關(guān)聯(lián)規(guī)則挖掘算法*

趙志剛,萬 軍,王 芳

(廣西大學(xué)計算機與電子信息學(xué)院，廣西 南寧 530004)

一種基于向量的概率加權(quán)關(guān)聯(lián)規(guī)則挖掘算法*

趙志剛,萬 軍,王 芳

(廣西大學(xué)計算機與電子信息學(xué)院，廣西 南寧 530004)

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘領(lǐng)域中最活躍的一個分支。目前提出的許多關(guān)聯(lián)規(guī)則挖掘算法需要多次掃描數(shù)據(jù)庫并產(chǎn)生大量候選項集，影響了挖掘效率。針對加權(quán)關(guān)聯(lián)規(guī)則挖掘算法中多次掃描數(shù)據(jù)庫影響算法性能的問題，對其進(jìn)行了優(yōu)化，采取了以空間換時間的思路，提出一種基于向量的概率加權(quán)關(guān)聯(lián)規(guī)則挖掘算法。以求概率的方式設(shè)置項目屬性的權(quán)值，通過矩陣向量存儲結(jié)構(gòu)保存事務(wù)記錄，只需掃描一次數(shù)據(jù)庫，并且采用不同的剪枝策略及加權(quán)支持度和置信度的計算方式。使用數(shù)據(jù)實例進(jìn)行模擬實驗，結(jié)果表明此算法明顯提高了挖掘效率。

數(shù)據(jù)挖掘；概率；向量；加權(quán)關(guān)聯(lián)規(guī)則；剪枝策略

1 引言

1993年，Agrawal R等[1]提出了經(jīng)典的Apriori算法，該算法是一種寬度優(yōu)先的算法，運用了其向下封閉的性質(zhì)，采用一種逐層搜索的迭代方法產(chǎn)生候選項集，然后通過掃描數(shù)據(jù)庫得到頻繁項集。但是，由于其多次掃描數(shù)據(jù)庫以及產(chǎn)生大量候選項集特別是候選二項集，消耗了大量的系統(tǒng)時間，占用了大量空間，降低了挖掘效率。之后很多學(xué)者對此提出一些改進(jìn)算法，然而這些算法都是將數(shù)據(jù)庫中的項目屬性“平等對待”，但在實際應(yīng)用中，用戶對項目屬性的重視程度是不同的。尹群等[2]提出一種基于概率的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法，該算法將項目屬性在事務(wù)數(shù)據(jù)庫中出現(xiàn)的概率的倒數(shù)設(shè)置成權(quán)值，提高了小概率項目的加權(quán)支持度，有效地挖掘出小概率事件中的關(guān)聯(lián)規(guī)則，但由于其頻繁掃描數(shù)據(jù)庫及低效的剪枝策略，影響了挖掘效率。候新麗等[3]提出基于矩陣的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法，該算法只需掃描一次數(shù)據(jù)庫，采用矩陣存儲結(jié)構(gòu)，將其列向量進(jìn)行邏輯“與”操作產(chǎn)生加權(quán)頻繁項集，但由于其依據(jù)個人主觀性賦予權(quán)值，權(quán)值小的關(guān)聯(lián)規(guī)則不容易被挖掘出來。李成軍等[4]提出一種改進(jìn)的加權(quán)關(guān)聯(lián)規(guī)則挖掘方法，該方法采用一種新的加權(quán)支持度和置信度計算方法，解決了一般加權(quán)關(guān)聯(lián)規(guī)則挖掘算法中不滿足“向下封閉性”的問題，在實際應(yīng)用中取得了較好的效果。文獻(xiàn)[5]提出了一種挖掘頻繁項集的New-MWFI算法，能較好地挖掘出頻繁項集。

本文提出了一種新的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法，該算法將項目屬性權(quán)值設(shè)置成其在事務(wù)數(shù)據(jù)庫中出現(xiàn)的概率，采用了不同的加權(quán)支持度和加權(quán)置信度計算方法，并采用一種新的剪枝策略，只掃描一次數(shù)據(jù)庫，明顯提高了挖掘效率。最后，通過一組數(shù)據(jù)實例，與Apriori 算法和基于概率的加權(quán)關(guān)聯(lián)規(guī)則算法相比較，比較結(jié)果表明本文算法能保持Apriori 算法向下封閉的特性，能快速有效地挖掘重要的關(guān)聯(lián)規(guī)則。

2 相關(guān)知識

2.1 基本概念

設(shè)I={i1，i2，…，im}是數(shù)據(jù)庫中項(item)的集合，包含K個項的集合稱為K項集(item set)。DB(database)={T1，T2，T3,…，Tn}為事務(wù)數(shù)據(jù)集T的集合，其中T?I，且每個事務(wù)都有一個唯一的標(biāo)識號，稱為TID(Transaction Identity)[6]。設(shè)X是項目屬性的集合，即X?I，如果項集X?T，則稱T包含項集X。

設(shè)項集X?I，項集X的加權(quán)支持度WS(Weighted Support)定義為事務(wù)數(shù)據(jù)庫DB中包含X的概率與它的事務(wù)權(quán)值的乘積。

最小加權(quán)支持度MWS(Minimum Weighted Support)表示在生成的候選項集中，其加權(quán)支持度必須滿足的最小加權(quán)支持度閾值。其中，加權(quán)支持度大于最小加權(quán)支持度的項集X稱為加權(quán)頻繁項目集，反之，稱為加權(quán)非頻繁項目集。

2.2 相關(guān)性質(zhì)、定理

定義1記W(ij)為項目屬性ij的權(quán)值，它是ij在事務(wù)記錄中出現(xiàn)的概率，體現(xiàn)了項目屬性的重要性，是一個范圍在[0,1]的數(shù)。即：

(1)

其中,P(ij)=|T:ij∈T,T?DB|/|DB|，它是包含項目屬性ij的事務(wù)記錄個數(shù)與總的事務(wù)個數(shù)的比值。

定義2記W(X)為項集X的事務(wù)權(quán)值，它是事務(wù)數(shù)據(jù)庫的項集X中各項目的權(quán)值匯總，即：

(2)

其中,|X|>1，ij∈X，X?T，T?DB；當(dāng)|X|=1時，W(X)=W(ij)。

定義3記Fre(X)為項集X在事務(wù)記錄中的出現(xiàn)頻率。即：

(3)

當(dāng)|X|=1時，F(xiàn)re(X) =W(ij)。

定義4WS為項集X的加權(quán)支持度，即：

(4)

定義5事務(wù)向量集：事務(wù)向量是由0和1組成的向量，若事務(wù)中的項屬于項集I，則相應(yīng)位置置1，否則置0[7]。例如項集I={ABCDE}，事務(wù)T={ACE}，則T對應(yīng)的事務(wù)向量為V=[1,0,1,0,1]，記事務(wù)向量為trans_vector，數(shù)據(jù)庫DB中所有事務(wù)對應(yīng)的事務(wù)向量的集合稱為事務(wù)向量集，記為trans_vectors。

定義6事務(wù)向量長度：事務(wù)記錄中項目屬性的個數(shù)或者事務(wù)向量元素為1的個數(shù)，記為t_length。

性質(zhì)1向下封閉性[1]：任何頻繁項集的子集為頻繁項集，非頻繁項集的超集也是非頻繁的。

定理1在基于向量的概率加權(quán)關(guān)聯(lián)規(guī)則挖掘算法中，假設(shè)正準(zhǔn)備挖掘頻繁K項集，在掃描事務(wù)向量集的過程中，若事務(wù)向量的長度小于K，則該事務(wù)中的項目屬性不參與挖掘頻繁項集[3]。

3 基于向量的概率加權(quán)關(guān)聯(lián)規(guī)則挖掘算法

基于概率的加權(quán)關(guān)聯(lián)規(guī)則算法保持了Apriori算法的特性，且具有較好的時間復(fù)雜度和空間復(fù)雜度。但是，在計算項目屬性權(quán)值以及每產(chǎn)生一次頻繁K項集時，都需要掃描一次數(shù)據(jù)庫；同時，該算法采用經(jīng)典Apriori算法的連接和剪枝策略，產(chǎn)生了大量候選項集，特別是候選二項集，影響了算法的效率。另外，在計算項目權(quán)值時，根據(jù)其計算方法，非重要項目的權(quán)值可能大于重要項目的權(quán)值，以至于遺漏一些出現(xiàn)頻率較高的關(guān)聯(lián)規(guī)則。

本文針對基于概率的加權(quán)關(guān)聯(lián)規(guī)則算法存在的不足作了改進(jìn)，提出了以下解決方案：

(1)在項目權(quán)值計算問題方面，根據(jù)定義1，將項目屬性在事務(wù)數(shù)據(jù)庫中的出現(xiàn)概率記為項目權(quán)值，體現(xiàn)了項目的重要性。

(2)在掃描數(shù)據(jù)庫方面，為了減少數(shù)據(jù)庫的掃描次數(shù)，采用了矩陣向量存儲結(jié)構(gòu)，根據(jù)事務(wù)中項目屬性是否出現(xiàn)在項目屬性集I中，將相應(yīng)位置分別置為1或0以生成事務(wù)向量，事務(wù)向量的長度和項目屬性集I中元素個數(shù)相等，只需掃描一次數(shù)據(jù)庫生成事務(wù)向量集，以后在產(chǎn)生候選項集和頻繁項集時只需操作事務(wù)向量集即可。

(3)在連接和剪枝方面，為了減少候選項集的產(chǎn)生，提高挖掘效率，在產(chǎn)生候選K項集之前，先排除事務(wù)向量長度(1的個數(shù))小于K的事務(wù)向量；如果小于K，將其置為零向量，否則通過向量元素之間的邏輯“與”操作，根據(jù)公式(2)及公式(3)計算加權(quán)支持度，以產(chǎn)生滿足最小加權(quán)支持度的頻繁項集。將頻繁項集中的項目屬性存入頻繁集合FS(Frequent Set)中，其它項目屬性存入非頻繁集合NFS(Not Frequent Set)，根據(jù)集合NFS，將事務(wù)向量中相應(yīng)的位置0，重復(fù)執(zhí)行直至所有事務(wù)向量都為零向量。

本文提出了基于向量的概率加權(quán)關(guān)聯(lián)規(guī)則挖掘算法，算法流程如下：

步驟1掃描數(shù)據(jù)庫DB，得到項目屬性權(quán)值向量與事務(wù)記錄向量集，其元素由0和1組成。

步驟2將權(quán)值為0的項目存入集合NFS，掃描事務(wù)向量集，根據(jù)公式(4)計算項目的加權(quán)支持度，將不小于最小加權(quán)支持度的項目加入頻繁1項集L1及頻繁項目集FS中，非頻繁項目加入非頻繁項目集NFS。令K=2。

步驟3

(1)根據(jù)NFS中的項目，將事務(wù)向量集中相應(yīng)的位置置0。

(2)計算事務(wù)向量的長度，將長度小于K(K≥2)的事務(wù)向量置為零向量。

(3)判斷所有事務(wù)向量是否為零向量，是則轉(zhuǎn)步驟5。

(4)掃描事務(wù)向量集計算加權(quán)支持度，產(chǎn)生頻繁K項集。

(5)將頻繁項集中的項目加入集合FS，非頻繁項目加入NFS。

步驟4K=K+1，轉(zhuǎn)步驟3。

步驟5合并所有頻繁項集，算法結(jié)束。

4 數(shù)據(jù)實例

設(shè)有項目集I={A,B,C,D,E}，數(shù)據(jù)庫DB中共有10條交易記錄，分別為T1={A,B,D,E}，T2={A,B,E}，T3={A,B}，T4={A,B,C,D,E}，T5={A,B,C}，T6={A,B,D}，T7={A,C,E}，T8={A,E},T9={C,D},T10={B,D,E}，NFS用于存儲非頻繁項目屬性，F(xiàn)S用于存儲頻繁項目屬性，通過這組測試數(shù)據(jù)來演示本文算法的挖掘步驟。

(1)掃描數(shù)據(jù)庫DB，根據(jù)公式(1)得到項目權(quán)值向量w_vector和事務(wù)向量集trans_vectors，其中項目權(quán)值向量中的分量值(向量元素值)是包含該項目的事務(wù)記錄數(shù)與總的事務(wù)記錄數(shù)之比；而事務(wù)向量中的分量值為1或0，表示其對應(yīng)的項目在或不在集合I中。結(jié)果如表1和表2所示。

(2)假設(shè)最小加權(quán)支持度MWS= 0.17，根據(jù)表1、表2，將權(quán)值為0的項目存入NFS集合中，此時NFS=?，為空集。計算事務(wù)向量中項目屬性的和(不計算NFS中的項目)得到A:8、B:7、C:4、D:5、E:6，根據(jù)公式(4)計算得到項目的加權(quán)支持度為A:0.64、B:0.49、C:0.16、D:0.25、E:0.36，從而得到頻繁1項集為L1={A,B,D,E}，再將非頻繁項目添加到NFS中，即NFS={C}，F(xiàn)S={A,B,D,E}。

Table 1 Vector of weight value of items表1 項目權(quán)值向量

Table 2 Transactions vectors表2 事務(wù)向量集

(3)根據(jù)NFS中的項目將事務(wù)向量集中對應(yīng)的位置0，即得到如表3所示的事務(wù)向量集。

計算事務(wù)向量集中每一行的和，將和小于2的行向量置0，連接頻繁1項集中的項目屬性，得到候選2項集C2={AB,AD,AE,BD,BE,DE}，再進(jìn)行剪枝，根據(jù)公式(2)～公式(4)計算其權(quán)值、出現(xiàn)頻率、加權(quán)支持度等步驟得到頻繁2項集為L2={AB,AE}，從而NFS={C,D}，F(xiàn)S={A,B,E}。

Table 3 Transactions vectors after being updated表3 更新后的事務(wù)向量集

(4)重復(fù)執(zhí)行步驟(3)，得到候選3項集為ABE，經(jīng)計算其加權(quán)支持度為0.048，小于最小加權(quán)支持度0.17，則NFS={A,B,C,D,E}，F(xiàn)S=?，此時事務(wù)向量集元素都為零，算法結(jié)束。合并所有的頻繁項集，得到L={A,B,D,E,AB,AE}。

5 實驗結(jié)果分析

實驗環(huán)境如下：操作系統(tǒng)Windows XP，開發(fā)工具eclipse，編程語言Java。本文算法與Apriori算法及基于概率的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法的比較結(jié)果如圖1所示。

Figure 1 Performance comparison of three algorithms圖1 三種算法的性能比較

通過圖1可以看出，隨著支持度(最小加權(quán)支持度)變大，三種算法挖掘出所有頻繁項集的時間逐漸減少，并且趨勢基本保持一致，說明三種算法都滿足了向下封閉的性質(zhì)；另外，在相同的支持度情況下，基于向量的加權(quán)算法較基于概率的加權(quán)算法執(zhí)行時間大大減少。這是因為前者在采用矩陣向量存儲結(jié)構(gòu)之后，只需掃描一次數(shù)據(jù)庫，在產(chǎn)生候選項集之前先判斷事務(wù)向量的長度，僅掃描符合條件的事務(wù)向量，減少了候選項集的產(chǎn)生，降低了算法的時間和空間復(fù)雜度，具有較高的挖掘效率。而后者采用的算法思路與Apriori算法類似，需多次掃描數(shù)據(jù)庫并且產(chǎn)生大量的候選項集。基于向量的加權(quán)算法與Apriori算法相比，前者對項目屬性加權(quán)處理后，一些用戶不關(guān)心的關(guān)聯(lián)規(guī)則不易被挖掘，從而減少了挖掘無用規(guī)則造成的時間和空間開銷。

6 結(jié)束語

針對基于概率的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法存在的不足，本文提出一種基于向量的概率加權(quán)關(guān)聯(lián)規(guī)則挖掘算法。該算法采用加權(quán)的方法來突出項目的重要性，引入新的加權(quán)支持度和加權(quán)置信度的計算方法及新的剪枝策略，并滿足Apriori算法的向下封閉性；同時，采用矩陣向量存儲結(jié)構(gòu)，整個算法只需掃描一次數(shù)據(jù)庫，將挖掘頻繁項集的過程轉(zhuǎn)換為計算矩陣向量元素。與基于概率的加權(quán)算法相比，本文算法執(zhí)行速度快，明顯提高了挖掘效率，具有較好的性能。

[1]AgrawalR,ImidinskiT,SwanmiA.Miningassociationrulesbetweensetsofitemsinlargedatabase[C]∥ProcoftheACMSIGMODConferenceonManagementofData, 1993:207-216．

[2]YinQun,WangLi-zhen,TianQi-ming.Algorithmofminingassociationruleswithweighteditemsbasedonprobability[J].ComputerApplications, 2005, 25(4):805-807.(inChinese)

[3]HouXin-li,MengXiao-wei,YuSong.Weightedassociationrulesminingalgorithmbasedonmatrix[J].ComputerDevelopment&Applications, 2010, 23(6):34-36.(inChinese)

[4]LiCheng-jun,YangTian-qi.Improvedweightedassociationrulesminingmethod[J].ComputerEngineering, 2010, 36(7):55-57.(inChinese)

[5]LiYan-wei,DaiYue-ming,WangJin-xin.Improvedalgorithmforminingweightedfrequentitemsets[J].ComputerEngineeringandApplications, 2011, 47(15):165-167.(inChinese)

[6]HuJi-ming,XianXue-feng.ResearchandimprovementonApriori’salgorithminminingwithassociationrules[J].ComputerTechnologyandDevelopment, 2006, 16(4):99-101.(inChinese)

[7]FangGang,XiongJiang.Algorithmofintercrossingminingassociationrulesbasedonbinary[J].ComputerEngineeringandApplications, 2009, 45(7):141-145.(inChinese)

附中文參考文獻(xiàn)：

[2] 尹群,王麗珍,田啟明. 一種基于概率的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法[J]. 計算機應(yīng)用,2005, 25(4):805-807.

[3] 侯新麗,孟曉偉,于松. 基于矩陣的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法[J]. 電腦開發(fā)與應(yīng)用,2010, 23(6):34-36.

[4] 李成軍,楊天奇. 一種改進(jìn)的加權(quán)關(guān)聯(lián)規(guī)則挖掘方法[J]. 計算機工程, 2010, 36(7):55-57.

[5] 李彥偉,戴月明,王金鑫. 一種挖掘加權(quán)頻繁項集的改進(jìn)算法[J]. 計算機工程與應(yīng)用,2011, 47(15):165-167.

[6] 胡吉明,鮮學(xué)豐. 挖掘關(guān)聯(lián)規(guī)則中Apriori算法的研究與改進(jìn)[J]. 計算機技術(shù)與發(fā)展,2006, 16(4):99-101.

[7] 方剛,熊江. 二進(jìn)制的交叉挖掘關(guān)聯(lián)規(guī)則研究[J]. 計算機工程與應(yīng)用, 2009, 45(7):141-145.

ZHAOZhi-gang,born in 1973,PhD,associate professor,his research interests include computational intelligence, and data mining.

萬軍(1987-),男,四川樂山人，碩士生，研究方向為數(shù)據(jù)挖掘。E-mail:wanjun614013@163.com

WANJun,born in 1987,MS candidate,his research interest includes data mining.

王芳(1987-),女,河南許昌人，碩士生，研究方向為數(shù)據(jù)挖掘。E-mail:woaiwojiawf@126.com

WANGFang,born in 1987,MS candidate,her research interest includes data mining.

Aprobability-weightedassociationrulesminingalgorithmbasedonvector

ZHAO Zhi-gang,WAN Jun,WANG Fang

(College of Computer and Electronics Information,Guangxi University,Nanning 530004,China)

Association rules mining is one of the most active branch of data mining. Many association rules mining algorithms need to scan the database many times and produce a large number of candidate items. Aiming at the problem of scanning database several times, a probability-weighted association rules mining algorithm based on vector is proposed. It sets the weight value of item by computing the probability and saves the transaction records via the matrix-vector structure by scanning the database only once. In addition, it employs different cutting strategies and computing ways of weighted support and confidence. Experimental results show that the new algorithm can improve the mining efficiency distinctly.

data mining;probability;vector;weighted association rules;cutting strategies

2012-06-28;

：2012-11-29

國家自然科學(xué)基金資助項目(60973074)

1007-130X(2014)02-0354-05

TP274

：A

10.3969/j.issn.1007-130X.2014.02.026

趙志剛(1973-),男,廣西桂林人，博士，副教授,研究方向為計算智能和數(shù)據(jù)挖掘。E-mail:zzgmail2002@163.com

通信地址：530004 廣西南寧市廣西大學(xué)計算機與電子信息學(xué)院Address:College of Computer and Electronics Information,Guangxi University,Nanning 530004,Guangxi,P.R.China