趙志剛,萬(wàn) 軍,王 芳

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

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

趙志剛,萬(wàn) 軍,王 芳

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

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

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

1 引言

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

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

2 相關(guān)知識(shí)

2.1 基本概念

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

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

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

(4)

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟3

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

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

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

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

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

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

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

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

設(shè)有項(xiàng)目集I={A,B,C,D,E}，數(shù)據(jù)庫(kù)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用于存儲(chǔ)非頻繁項(xiàng)目屬性，F(xiàn)S用于存儲(chǔ)頻繁項(xiàng)目屬性，通過(guò)這組測(cè)試數(shù)據(jù)來(lái)演示本文算法的挖掘步驟。

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

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

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

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

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

計(jì)算事務(wù)向量集中每一行的和，將和小于2的行向量置0，連接頻繁1項(xiàng)集中的項(xiàng)目屬性，得到候選2項(xiàng)集C2={AB,AD,AE,BD,BE,DE}，再進(jìn)行剪枝，根據(jù)公式(2)～公式(4)計(jì)算其權(quán)值、出現(xiàn)頻率、加權(quán)支持度等步驟得到頻繁2項(xiàng)集為L(zhǎng)2={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項(xiàng)集為ABE，經(jīng)計(jì)算其加權(quán)支持度為0.048，小于最小加權(quán)支持度0.17，則NFS={A,B,C,D,E}，F(xiàn)S=?，此時(shí)事務(wù)向量集元素都為零，算法結(jié)束。合并所有的頻繁項(xiàng)集，得到L={A,B,D,E,AB,AE}。

5 實(shí)驗(yàn)結(jié)果分析

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

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

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

6 結(jié)束語(yǔ)

針對(duì)基于概率的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法存在的不足，本文提出一種基于向量的概率加權(quán)關(guān)聯(lián)規(guī)則挖掘算法。該算法采用加權(quán)的方法來(lái)突出項(xiàng)目的重要性，引入新的加權(quán)支持度和加權(quán)置信度的計(jì)算方法及新的剪枝策略，并滿足Apriori算法的向下封閉性；同時(shí)，采用矩陣向量存儲(chǔ)結(jié)構(gòu)，整個(gè)算法只需掃描一次數(shù)據(jù)庫(kù)，將挖掘頻繁項(xiàng)集的過(guò)程轉(zhuǎn)換為計(jì)算矩陣向量元素。與基于概率的加權(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]. 計(jì)算機(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]. 計(jì)算機(jī)工程, 2010, 36(7):55-57.

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

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

[7] 方剛,熊江. 二進(jìn)制的交叉挖掘關(guān)聯(lián)規(guī)則研究[J]. 計(jì)算機(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.

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

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

王芳(1987-),女,河南許昌人，碩士生，研究方向?yàn)閿?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

國(guó)家自然科學(xué)基金資助項(xiàng)目(60973074)

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

TP274

：A

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

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

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