一種基于向量的概率加權關聯規則挖掘算法*

趙志剛,萬 軍,王 芳

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

一種基于向量的概率加權關聯規則挖掘算法*

趙志剛,萬 軍,王 芳

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

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

數據挖掘；概率；向量；加權關聯規則；剪枝策略

1 引言

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

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

2 相關知識

2.1 基本概念

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

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

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

2.2 相關性質、定理

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

(1)

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

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

(2)

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

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

(3)

當|X|=1時，Fre(X) =W(ij)。

定義4WS為項集X的加權支持度，即：

(4)

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

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

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

定理1在基于向量的概率加權關聯規則挖掘算法中，假設正準備挖掘頻繁K項集，在掃描事務向量集的過程中，若事務向量的長度小于K，則該事務中的項目屬性不參與挖掘頻繁項集[3]。

3 基于向量的概率加權關聯規則挖掘算法

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

本文針對基于概率的加權關聯規則算法存在的不足作了改進，提出了以下解決方案：

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

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

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

本文提出了基于向量的概率加權關聯規則挖掘算法，算法流程如下：

步驟1掃描數據庫DB，得到項目屬性權值向量與事務記錄向量集，其元素由0和1組成。

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

步驟3

(1)根據NFS中的項目，將事務向量集中相應的位置置0。

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

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

(4)掃描事務向量集計算加權支持度，產生頻繁K項集。

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

步驟4K=K+1，轉步驟3。

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

4 數據實例

設有項目集I={A,B,C,D,E}，數據庫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用于存儲非頻繁項目屬性，FS用于存儲頻繁項目屬性，通過這組測試數據來演示本文算法的挖掘步驟。

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

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

Table 1 Vector of weight value of items表1 項目權值向量

Table 2 Transactions vectors表2 事務向量集

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

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

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

(4)重復執行步驟(3)，得到候選3項集為ABE，經計算其加權支持度為0.048，小于最小加權支持度0.17，則NFS={A,B,C,D,E}，FS=?，此時事務向量集元素都為零，算法結束。合并所有的頻繁項集，得到L={A,B,D,E,AB,AE}。

5 實驗結果分析

實驗環境如下：操作系統Windows XP，開發工具eclipse，編程語言Java。本文算法與Apriori算法及基于概率的加權關聯規則挖掘算法的比較結果如圖1所示。

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

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

6 結束語

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

[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)

附中文參考文獻：

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

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

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

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

[6] 胡吉明,鮮學豐. 挖掘關聯規則中Apriori算法的研究與改進[J]. 計算機技術與發展,2006, 16(4):99-101.

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

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

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

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

王芳(1987-),女,河南許昌人，碩士生，研究方向為數據挖掘。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

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

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

TP274

：A

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

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

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