一種基于有向圖的多維多值屬性關聯(lián)規(guī)則挖掘算法

汪峰坤，張婷婷

安徽機電職業(yè)技術學院，安徽蕪湖，241000

?

一種基于有向圖的多維多值屬性關聯(lián)規(guī)則挖掘算法

汪峰坤，張婷婷

安徽機電職業(yè)技術學院，安徽蕪湖，241000

針對多維多值數(shù)據(jù)特點，提出了基于FP-Growth的改進算法FP-G。FP-G算法存儲結構使用有向圖，增加了頭結點，方便對圖剪枝和遍歷。針對圖結構使用了新的剪枝策略，對于小于最小支持度的邊直接刪除，無須修改結點指針。關聯(lián)規(guī)則生成時通過頭結點進行深度遍歷生成最大頻繁模式集。實驗結果表明，F(xiàn)P-G算法相比FP-Growth算法，在百萬數(shù)量級的高維數(shù)據(jù)集上，執(zhí)行時間平均節(jié)約30%左右。

數(shù)據(jù)挖掘；關聯(lián)規(guī)則；頻繁項集；多值屬性

1 問題的提出

關聯(lián)規(guī)則數(shù)據(jù)挖掘是從海量數(shù)據(jù)中發(fā)現(xiàn)數(shù)據(jù)集之間潛在聯(lián)系的一項技術。根據(jù)數(shù)據(jù)集維數(shù)是否大于1，數(shù)據(jù)挖掘分為單維和多維兩種；又根據(jù)數(shù)據(jù)集屬性取值情況，分為布爾和多值兩種情況。

Srikant R.和Agrawal R.于1996年提出了基于Apriori算法的多值屬性關聯(lián)規(guī)則[1]，即通過量化規(guī)則將數(shù)據(jù)集的屬性轉換為單維二元屬性，然后使用經典的Apriori算法進行挖掘，但容易造成事務屬性急劇增加，挖掘效率較低。后來，國內學者穆云婷等提出了基于FP-Growth的多維關聯(lián)規(guī)則挖掘[2]即把樹中每個節(jié)點作為一個屬性值，樹中每個分支作為數(shù)據(jù)集中的一條記錄，在第一次掃描數(shù)據(jù)庫時統(tǒng)計1階頻繁集，按個數(shù)的逆序生成頭節(jié)點列表。第二次掃描數(shù)據(jù)庫時生成頻繁樹，樹中每個節(jié)點出現(xiàn)下一屬性指針等，但當維數(shù)和屬性值較多時生成的樹的深度很大，生成關聯(lián)規(guī)則較慢。

在多值屬性挖掘應用中，在某些情況下一條記錄中某屬性的取值是唯一的。例如，某位教職工在某次常規(guī)體檢中，他的空腹血糖只能是正常、受損、糖尿病三種情況中的任意一種，不可能同時是兩種及兩種以上的組合。針對這些情況的應用，本文提出了FP-G算法。FP-G算法是FP-Growth關聯(lián)規(guī)則的一種改進算法，它通過修改FP-Tree為有向圖、增加新的數(shù)據(jù)存儲結構和優(yōu)化的剪枝策略，提高了算法執(zhí)行的效率，實驗結果驗證了它的有效性。

2 關聯(lián)規(guī)則的基本概念和理論

關聯(lián)規(guī)則挖掘中基本概念和相關定義[1-8]：

定義1 設I={I1，I2，…，Im}是文字屬性，稱為項(item)。給定一個事務數(shù)據(jù)庫D，其中每個事務T是項的集合，滿足T?I。每個事務都有一個標識符，稱為TID。X是I的子集，如果X?I，則稱T包含X；如果X的元素個數(shù)為k，則可以稱X為k-項集(k-ItemSet)。

定義2 如果項集X?I，Y?I，并且X∩Y=?，形如X?Y的蘊涵式稱為關聯(lián)規(guī)則，其中，X稱為規(guī)則的前項集，Y是規(guī)則的后項集。

定義3 給定最小支持度閾值minSup，如果項集X的支持度大于等于minSup，則稱X為頻繁項集。頻繁k項集的集合記為項集Lk。

對于數(shù)據(jù)挖掘中的關聯(lián)規(guī)則主要有兩個步驟：(1)給定事務數(shù)據(jù)庫D和項目集I={I1，I2，…，Im}，發(fā)現(xiàn)D中所有大于指定minSup的頻繁模式完全集P；(2)從頻繁項集中的每個頻繁模式中抽取關聯(lián)規(guī)則I?l-s，其置信度大于等于minConf。其中，第(1)步是核心，決定挖掘關聯(lián)規(guī)則的總體性能。

關聯(lián)規(guī)則挖掘算法中的主要性質：

性質1 頻繁項集的所有非空子集都是頻繁的。

性質2 非頻繁項集的所有超集都是非頻繁項集。

在多維多值屬性挖掘應用中，有些應用針對某個屬性在一條記錄中其取值是唯一的，有如下性質：

性質3 每條事務所包含的屬性數(shù)目相同，即每個事務的長度相同。

性質4 某一屬性的不同的屬性值不會出現(xiàn)在同一個頻繁屬性集中。

3 改進算法

3.1 算法的基本數(shù)據(jù)結構

設事務數(shù)據(jù)有N維，每一維的屬性都是多值屬性，各維屬性個數(shù)為：x1,x2,…，xn。設第m維的屬性取值標記為Vm(1),Vm(2),…，Vm(xm)。

構建基于維的單鏈表，每個單鏈表對于某一維的所有屬性取值。

單鍵表中每個節(jié)點包括3個數(shù)據(jù)域和2個指針域。

屬性值：指此節(jié)點所在維屬性取值的一個。

出現(xiàn)次數(shù)：指此節(jié)點在數(shù)據(jù)庫中出現(xiàn)的次數(shù)。

next指針：指向下一維的某個節(jié)點，表示此節(jié)點值和下一節(jié)點值在某條事務中同時出現(xiàn)。

next指針個數(shù)：表示此節(jié)點值和下一節(jié)點值在事務數(shù)據(jù)庫中一共出現(xiàn)了多少次。

right指針：指向同一維的下一個屬性值節(jié)點。

3.2 FP-G算法流程

3.2.1 構建有向圖G

(1)第一遍掃描事務數(shù)據(jù)庫D，統(tǒng)計每一維的每個屬性值出現(xiàn)的個數(shù)，生成一階頻繁子集。

(2)根據(jù)一階頻繁子集和頻繁項所在的維，按順序生成相應的單鏈表，每一維生成一條單鏈表。每條單鏈表中每個節(jié)點是此維的頻繁屬性值。

(3)生成G的Head節(jié)點，Head節(jié)點通過指針指向第一維的所有節(jié)點。

(4)第二遍掃描事務數(shù)據(jù)庫D，對于每條記錄按維加入到FP-G中。首先去除不在一階頻繁子集中的維，然后根據(jù)記錄中各維值的順序關系在FP-Tree中增加邊。如果是第一次增加，將節(jié)點的next指針指向下一維值對應的節(jié)點。如果不是第一次增加，將next個數(shù)加1，并且將兩個節(jié)點出現(xiàn)次數(shù)加1。

3.2.2 生成關聯(lián)規(guī)則

(1)深度遍歷有向圖G，將邊值小于minSup的邊刪除。如果剩余路徑上的結點還有父指針指向，則不作處理；如果沒有父指針指向，則掛在Head節(jié)點下。當遍歷結束時，樹中結點之間的邊數(shù)目都是大于minSup的。

(2)再深度遍歷有向圖G，得到的每條路徑就是滿足minSup的最大頻繁模式項。

(3)最后根據(jù)組合算法，可求出所有頻繁項。

本算法類似于FP-Growth算法，都是在內存中生成事務數(shù)據(jù)庫的結構。根據(jù)多維多屬性數(shù)據(jù)特點，使用的是有向圖作為內存數(shù)據(jù)存儲結構。在根據(jù)有向圖生成關聯(lián)規(guī)則之前，對有向圖G使用了新的剪枝策略。生成關聯(lián)規(guī)則時，先生成最大頻繁模式集，最后根據(jù)最大頻繁模式集生成所有的頻繁集。

4 FP-G算法實驗與分析

4.1 算法流程實驗

某事務數(shù)據(jù)庫中有6個事務，D={T1,T2,T3，T4,T5,T6}，每條事務固定有4個屬性，每個屬性有若干取值。如表1所示。

表1 多值屬性數(shù)據(jù)示例

假設最小支持度30%，即最小支持計數(shù)為：minSup=30%×|D|=30%×6≈2。

圖1 生成的FP-G圖

(1)第一遍掃描事務數(shù)據(jù)庫D，統(tǒng)計每一維的屬性值出現(xiàn)的個數(shù)。統(tǒng)計結果：{{"1"∶3,"2"∶2,"3"∶1},{"4"∶3,"5"∶1,"6"∶2},{"7"∶3,"8"∶3},{"9"∶3,"10"∶2}}。根據(jù)minSupNum=2，則得到一階頻繁子集：{{"1"∶3,"2"∶2},{"4"∶3,"6"∶2},{"7"∶3,"8"∶3},{"9"∶4,"10"∶2}}，并同時生成一階頻繁子集相應維的單鏈表和Head節(jié)點。

(2)第二次掃描事務數(shù)據(jù)庫，將記錄按維加入到FP-G中。規(guī)則是，每條記錄按維在圖G上生成邊。如果維值不在圖中，則跳過此維。如果兩維之間的邊不存在，則增加邊并計數(shù)為1。如果兩維之間的邊存在，則邊上的計數(shù)加1。

本例中，生成的FP-G如圖1。

(3)對FP-G進行遍歷剪枝。深度遍歷圖G，去除邊計數(shù)小于minSupNum的邊(與Head相連的除外)。結果如圖2所示。

圖2 剪枝后的FP-G圖

(4)深度優(yōu)先遍歷FP-G，得到滿足minSup的最大頻繁模式集：{{"1"∶2,"4"∶2,"7"∶3，"9"∶null},{"2"∶2,"7"∶3,"9"∶null},{"6"∶2,"8"∶2,"10"∶null}}。數(shù)據(jù)含義：“1”等是指某維的屬性值節(jié)點，屬性值后面的數(shù)字指此節(jié)點與下一節(jié)點的連接邊的個數(shù)。根據(jù)組合算法，可以得到所有的頻繁項。

4.2 算法性能比較

關聯(lián)規(guī)則挖掘中，核心內容是生成支持minSup的頻繁模式完全集，決定了算法的總體性能。本文以生成頻繁模式完全集的時間開銷，來對FP-G算法和FP-Growth算法進行性能比較。

測試數(shù)據(jù)為某醫(yī)院健康體檢數(shù)據(jù)，共有9個屬性，即9維，每個屬性有3～5個屬性值。取最小支持度為10%，數(shù)據(jù)量從16萬條升到200萬條。

圖3 低維數(shù)據(jù)運行時間和數(shù)據(jù)量關系

由圖3中可見，當數(shù)據(jù)量較少時，F(xiàn)P-G算法性能與FP-Growth算法性能相近。在數(shù)據(jù)量較大時，F(xiàn)P-G算法要優(yōu)于基本的FP-Growth算法。

圖4為數(shù)據(jù)集有16維，每維有3～5個屬性值時的性能比較。

從圖4中可見，F(xiàn)P-Growth對維數(shù)敏感，當數(shù)據(jù)集的維數(shù)較高時，算法開銷比較大。FP-G算法在高維數(shù)據(jù)集上算法性能也較好。

圖4 高維數(shù)據(jù)運行時間和數(shù)據(jù)量關系

圖5表示FP-G算法在不同的最小支持度下的性能，測試數(shù)據(jù)集共16維，每維3～5個屬性值，數(shù)據(jù)集有100萬條記錄。

圖5 FP-G運行時間和最小支持度關系

從圖5中可見，當最小支持度過小時，需要更長的運行時間，因為要判斷和生成圖中更多的邊。當最小支持度較大時，運行時間較短，最后穩(wěn)定在某個時間值，這個時間值應該是掃描兩次數(shù)據(jù)集所用的時間。選擇合適的最小支持度，F(xiàn)P-G算法在較大數(shù)據(jù)集上性能表示良好。

5 結束語

本文根據(jù)多維多值關聯(lián)規(guī)則的特點，提出了基于有向圖的關聯(lián)規(guī)則挖掘算法。該算法總體思路類似于FP-Growth算法，通過第一遍掃描數(shù)據(jù)庫計算一階的頻繁集，通過第二遍掃描數(shù)據(jù)庫在內存中生成基于有向圖的頻繁數(shù)據(jù)結構。相對于FP-Growth算法，該算法無須對一階頻繁集排序，也無須生成每個葉子結點的指向下一個相同結點的指針。結合本文提出的剪枝策略，可以方便地生成最大關聯(lián)規(guī)則模式集。通過仿真，本算法性能相對于經典的FP-Growth算法有了一定的提升。

[1]AgrawalR,ImielinskiT,SwamiA.MiningAssociationRulesBetweenSetsofItemsinLargeDatabases[J].ACMSIGMODRecord,1993,22(2):207-216

[2]穆云婷,謝文閣.基于FP-Growth算法的多維關聯(lián)規(guī)則挖掘方法[J].遼寧工業(yè)大學學報：自然科學版,2010,4(2):81-83

[3]楊云,羅艷霞.FP-Growth算法的改進[J].計算機工程與設計,2010,31(7):1506-1510

[4]姜麗莉,孟凡榮,周勇,等.多值屬性關聯(lián)規(guī)則挖掘的Q-Apriori算法[J].計算機工程,2011,37(9):81-83

[5]鄭亞軍,胡學鋼.基于PFP的關聯(lián)規(guī)則增量更新算法[J].合肥工業(yè)大學學報,2015,38(4):500-505

[6]石杰.一種快速頻繁模式挖掘算法[J].煙臺大學學報：自然與工程版,2015,28(2):113-119

[7]Sathish K.Efficient tree based distributed data mining algorithms for mining frequent patterns[J].International Journal of Computer Application,2010,11(10):233-242

[8]Rahul M.Comparative analysis of apriori algorithm and frequent pattern algorithm for frequent pattern mining in web log data[J].International Journal of Computer Science and Information Technologies,2012,3(4):4662-4665

(責任編輯：汪材印)

2015-06-29

安徽省高校省級自然科學研究重點項目“基于移動客戶端的教職工健康體檢數(shù)據(jù)智能分析管理系統(tǒng)的研發(fā)”(KJ2014A038)。

汪峰坤(1978-)，安徽霍邱人，碩士，講師，主要研究方向：數(shù)據(jù)挖掘、大數(shù)據(jù)處理。

TP301.6

：A

：1673-2006(2015)12-0099-04

10.3969/j.issn.1673-2006.2015.12.027