FP-Tree算法規(guī)則挖掘的研究與應(yīng)用

王大勇，李 麗，張 蕾，孫時光

(1.遼寧大學(xué)創(chuàng)新創(chuàng)業(yè)學(xué)院，遼寧 沈陽 110036；2.東北師范大學(xué)物理學(xué)院，吉林 長春 130024)

0 引言

隨著大數(shù)據(jù)時代的到來，對數(shù)據(jù)和數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系進行深度挖掘和處理就顯得尤為重要，數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系是大數(shù)據(jù)中待挖掘的一類重要信息.關(guān)聯(lián)是指變量的數(shù)值中有2個或2個以上存在一定的規(guī)律，可以通過關(guān)聯(lián)分析挖掘出數(shù)據(jù)中的關(guān)聯(lián)關(guān)系.關(guān)聯(lián)分為簡單關(guān)聯(lián)、時序關(guān)聯(lián)和因果關(guān)聯(lián).關(guān)聯(lián)規(guī)則挖掘過程一般先從數(shù)據(jù)集合中找出所有的高頻項目組，再由高頻項目組產(chǎn)生關(guān)聯(lián)規(guī)則.

1993年，Agrawal等首先提出了挖掘關(guān)聯(lián)規(guī)則問題，并對顧客交易數(shù)據(jù)庫中項集之間的關(guān)聯(lián)規(guī)則挖掘問題進行研究，此后基于關(guān)聯(lián)規(guī)則的挖掘問題的研究逐步推廣，并吸引了大量的科研人員投入到該項研究中.關(guān)聯(lián)規(guī)則挖掘是大數(shù)據(jù)研究的一個重要課題.目前，關(guān)聯(lián)規(guī)則挖掘技術(shù)主要集中在金融行業(yè)以及電子商務(wù)中.

Apriori算法是一種挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法，廣泛應(yīng)用于多個領(lǐng)域中，包括商業(yè)金融、網(wǎng)絡(luò)安全、高校管理、移動通訊等.Apriori算法的實現(xiàn)包括3個階段：第1階段利用遞推方法找出所有的頻集，這些項集出現(xiàn)的頻繁性要大于等于預(yù)定義的最小支持度；第2階段由頻集產(chǎn)生強關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度；第3階段產(chǎn)生只包含集合項的所有規(guī)則.由該思想生成的規(guī)則均大于用戶給定的最小可信度.

Apriori算法雖然是經(jīng)典的規(guī)則挖掘算法，但在執(zhí)行過程中可能產(chǎn)生大量的候選集，并可能出現(xiàn)重復(fù)掃描數(shù)據(jù)庫的問題.針對Apriori算法的這些缺點，文獻[1-3]提出了FP-Tree算法.FP-Tree算法的思想是構(gòu)造一棵頻繁模式樹，把數(shù)據(jù)庫中的數(shù)據(jù)映射到樹上，這種頻繁模式樹簡稱為FP-Tree.通過兩次掃描事務(wù)數(shù)據(jù)庫把每個事務(wù)所包含的頻集壓縮到一棵FP-Tree中，此后只需通過FP-Tree進行查找，不需要再掃描事務(wù)數(shù)據(jù)庫，避免了重復(fù)掃描數(shù)據(jù)庫的問題.通過遞歸調(diào)用FP-Tree發(fā)現(xiàn)頻繁模式的算法，可直接產(chǎn)生頻繁模式，因此，該算法執(zhí)行過程中也避免了大量候選集的產(chǎn)生.數(shù)據(jù)表明，F(xiàn)P-Tree算法在效率上比Apriori算法有顯著的提高[4-7].

大學(xué)生所處的年齡階段正值生長穩(wěn)定期，各項生理功能處于成熟階段，具備較強的機體免疫力，相比其他年齡階段的人群患病率低.但由于近年來隨著科技水平的提高，外賣行業(yè)的興起等諸多因素，導(dǎo)致大學(xué)生使用手機電腦等電子產(chǎn)品的時間越來越長，不健康食品的攝入量過多，體育活動得不到重視等情況時有發(fā)生，使得一些慢性疾病在大學(xué)生群體中相比以往有所增多，例如肥胖、高血壓、免疫力低下等情況正在逐年遞增.國內(nèi)許多高校醫(yī)療系統(tǒng)內(nèi)存儲著大量的學(xué)生體檢數(shù)據(jù)，其中很多數(shù)據(jù)只是能進行簡單的存儲以及查詢等功能，而不能發(fā)掘出這些數(shù)據(jù)之間潛在的關(guān)聯(lián)關(guān)系并加以利用.因此本文采用FP-Tree算法對存儲的數(shù)據(jù)進行關(guān)聯(lián)規(guī)則挖掘，發(fā)現(xiàn)大學(xué)生群體中常見的各種慢性疾病，力求在早期敦促大學(xué)生養(yǎng)成良好的生活習慣、減少嚴重慢性疾病的發(fā)生.

1 FP-Tree算法

FP-Tree算法能夠高效地解決Apriori算法中存在的問題.因此對FP-Tree算法的相關(guān)定義和算法進行了描述.

1.1 相關(guān)定義

定義1 關(guān)聯(lián)規(guī)則：指有關(guān)聯(lián)的規(guī)則，對于兩個不相交的非空集合X和Y，如果有X→Y，就說X→Y是一條關(guān)聯(lián)規(guī)則.關(guān)聯(lián)規(guī)則的強度用支持度和置信度來描述.

定義2 支持度：關(guān)聯(lián)規(guī)則X→Y的支持度(support)用support(X→Y)=|X∩Y|/|N|表示，其中X和Y為事務(wù)數(shù)據(jù)庫中的集合，|X∩Y| 是X和Y同時出現(xiàn)的次數(shù)，|N|為事務(wù)數(shù)據(jù)庫中集合的個數(shù).

定義3 置信度(confidence)：關(guān)聯(lián)規(guī)則X→Y的置信度(confidence)用confidence(X→Y) =|X∩Y|/|X| 表示，其中X和Y為事務(wù)數(shù)據(jù)庫中的集合，|X∩Y| 是X和Y同時出現(xiàn)的次數(shù)，|X|是集合X出現(xiàn)的次數(shù).

支持度是對關(guān)聯(lián)規(guī)則重要性的衡量，支持度越大，表示這種關(guān)聯(lián)規(guī)則越重要.置信度是對關(guān)聯(lián)規(guī)則準確度的衡量.有些關(guān)聯(lián)規(guī)則的支持度雖高，但置信度低，說明該關(guān)聯(lián)規(guī)則準確度不夠，不能采用；有些關(guān)聯(lián)規(guī)則的置信度雖然很高，但是支持度低，說明該關(guān)聯(lián)規(guī)則出現(xiàn)的機會很小，實用價值不大.在進行實際關(guān)聯(lián)規(guī)則挖掘分析時，必須選擇恰當?shù)淖钚≈С侄乳撝岛妥钚≈眯哦乳撝?如果取值過低，則會發(fā)現(xiàn)大量無用的規(guī)則，不利于所需規(guī)則的發(fā)現(xiàn)和獲取.如果取值過高，則可能得不到規(guī)則，或者得到的規(guī)則過少，導(dǎo)致所需規(guī)則不滿足條件而沒有被篩選出來.一般需要根據(jù)實際情況設(shè)定合適的閾值.

支持度和置信度越高，說明規(guī)則越強，關(guān)聯(lián)規(guī)則挖掘就是挖掘出滿足一定強度的規(guī)則.下面舉例說明支持度與置信度的計算方法.

假設(shè)事務(wù)數(shù)據(jù)庫如下：

AEFG

AFG

ABEFG

EFG

其中每行代表一個事務(wù)，事務(wù)由若干個不相同項目構(gòu)成，任意幾個項目的組合稱為一個模式.該例中共有4個事務(wù).

模式{A，F(xiàn)，G}在4個事務(wù)中共出現(xiàn)3次，即支持數(shù)為3，經(jīng)計算得到支持度support為75%，支持數(shù)大于最小支持數(shù)minsupport的模式稱為頻繁模式(Frequent Partten).

以此類推，{F，G}的支持數(shù)為4，支持度為100%.{A}的支持數(shù)為3，支持度為75%.

Confidence({F，G}?{A})等于75%.Confidence({A}?{F，G})等于100%.

1.2 FP-Tree算法描述

輸入：事務(wù)集合 List> transactions，

輸出：頻繁模式集合及相應(yīng)的頻數(shù)Map，Integer>FrequentPattens，

初始化：PostModel=[]，CPB=transactions，

void FPGrowth(List> CPB，List PostModel){

if CPB為空，

return

}.

CPB的全稱是Conditional Pattern Base(條件模式基)，是算法在不同階段的事務(wù)集合.統(tǒng)計CPB中每一個項目的個數(shù)，把個數(shù)小于最小支持數(shù)minSuport的項目刪除掉，然后對于CPB中的每一條事務(wù)按項目個數(shù)降序排列.

由CPB構(gòu)建FP-Tree，F(xiàn)P-Tree中包含了表頭項headers，每一個header都指向了一個鏈表HeaderLinkList，鏈表中的每個元素都是FP-Tree上的一個節(jié)點，且節(jié)點名稱與header.name相同.得到從FP-Tree的根節(jié)點到TreeNode的全路徑path，把path作為一個事務(wù)添加到newCPB中，要重復(fù)添加TreeNode.count次.用java描述的具體代碼如下：

for header in headers：

newPostModel=header.name+PostModel，

newCPB=[]，

for TreeNode in HeaderLinkList：

FPGrowth(newCPB，newPostModel).

2 規(guī)則挖掘應(yīng)用

把大學(xué)生體檢數(shù)據(jù)庫中的數(shù)據(jù)進行相關(guān)處理，得到對應(yīng)的事務(wù)數(shù)據(jù)庫，再對事務(wù)數(shù)據(jù)庫中的數(shù)據(jù)運用FP-Tree算法[8-11]，進而得到一些有價值的關(guān)聯(lián)規(guī)則，為醫(yī)生診斷提供輔助依據(jù).

2.1 數(shù)據(jù)處理

體檢表中的數(shù)據(jù)很多都是有噪聲的，因此在使用之前應(yīng)該進行預(yù)處理操作：

(1) 把體檢表中與實驗無關(guān)的個人信息如姓名、民族、出生日期、專業(yè)等信息全部過濾掉.

(2) 對字段進行處理，例如身高和體重這2個數(shù)據(jù)不能完全體現(xiàn)出是否肥胖，所以需要對其進行處理，這2個字段需轉(zhuǎn)換為身體質(zhì)量參數(shù)BMI，m(體重)(kg)/h2(身高)(m)，這樣才能對規(guī)則的發(fā)現(xiàn)起到直接的幫助.

(3) 為了順利把關(guān)系數(shù)據(jù)庫轉(zhuǎn)換為事務(wù)數(shù)據(jù)庫，需要把原始數(shù)據(jù)表中的一些連續(xù)的數(shù)值型字段進行離散化處理.

(4) 以學(xué)生為單位，把學(xué)生所患慢性病用相應(yīng)的編碼代替，以達到每個字段只有一種信息的目的.

(5) 編寫程序讀取關(guān)系數(shù)據(jù)庫，得到適用于數(shù)據(jù)挖掘的事務(wù)數(shù)據(jù)庫[12-15]，如表1所示.在表1中ID代表某名學(xué)生，ITEM代表該名學(xué)生所患的慢性疾病，A，B，E等各代表某種慢性疾病.病情與編碼對照如表2所示.

表1 慢性病事務(wù)

表2 病情編碼對照

2.2 實現(xiàn)過程

在慢性病事務(wù)數(shù)據(jù)庫中任意選取10個事務(wù)應(yīng)用于FPGrowth函數(shù)，完整實現(xiàn)過程選取的10個事務(wù)：

ABCD

BEDF

BCD

ABCEDF

ACF

BCF

ACD

ABCGD

ABGD

EG

每行代表一個事務(wù)，事務(wù)由若干個不相同的項目構(gòu)成.假設(shè)最小支持數(shù)minSuport=3，統(tǒng)計每一個項目出現(xiàn)的次數(shù)，把次數(shù)低于minSupport的項目刪除掉，剩下的項目按出現(xiàn)的次數(shù)降序排列，得到F1{D：7B：7C：6A：6F：4}.

對于每一條事務(wù)，按照F1中的順序重新排序，并且把不在F1中的內(nèi)容刪除.這樣原來的事務(wù)集合成為：

DBCA

DBF

DBC

DBCAF

CAF

BCF

DCA

DBCA

DBA

上面的事務(wù)集合即為當前的CPB，當前的PostModel為空.開始構(gòu)造FP-Tree，初始狀態(tài)下FP-Tree為空，建立FP-Tree時逐條讀入排序之后的數(shù)據(jù)集，按照排序后的順序插入到FP-Tree中，排序靠前的節(jié)點是祖先節(jié)點，靠后的是子孫節(jié)點.如果有共同的祖先，則對應(yīng)的共同祖先節(jié)點計數(shù)加1.直到所有的數(shù)據(jù)都插入到FP-Tree后，F(xiàn)P-Tree建立完成.由CPB構(gòu)建FP-Tree的步驟為：

步驟1.插入第1條事務(wù)(D，B，C，A)，F(xiàn)P-Tree如圖1所示.

圖1 插入第1條事務(wù)的FP-Tree

步驟2.插入第2條事務(wù)(D，B，F(xiàn))，F(xiàn)P-Tree如圖2所示.

圖2 插入前兩條事務(wù)的FP-Tree

步驟3.以此類推，把9條事務(wù)全部插入之后，得到圖3所涉FP-Tree.

圖3 插入全部事務(wù)的FP-Tree

另外建立表頭項，表頭項中記錄的是頻繁項集及其出現(xiàn)的個數(shù).其次樹中相同名稱的節(jié)點要用鏈表鏈接起來，如圖4所示，鏈表的第一個元素就是表頭項里的元素.不論是表頭項節(jié)點還是FP-Tree中的所有節(jié)點，它們都有2個屬性：name(頻繁項集的名稱)和count(頻繁項集的個數(shù)).

圖4 用鏈表鏈接的FP-Tree

遍歷表頭項中的每一項，以“A：6”為例.

新的postModel為“表頭項+原有postModel”，由于原有postModel的list為空，所以新的PostModel為[A].新的PostModel就是一條頻繁模式，它對應(yīng)的支持數(shù)即為表頭項的count：6，所以此處可以輸出一條頻繁模式〈[A]，6〉.分為4個步驟.

步驟1.從表頭項A開始，找到FP-Tree中所有的A節(jié)點，然后找到從樹的根節(jié)點到A節(jié)點的路徑.得到如下4條路徑：

路徑1：D：7，B：6，A：1；

路徑2：D：7，B：6，C：4，A：3；

路徑3：D：7，C：1，A：1；

路徑4：C：1，A：1.

步驟2.對于每一條路徑上的節(jié)點，其count都設(shè)置為A的count，結(jié)果如下：

D：1，B1：6，A：1；

D：3，B：3，C：3，A：3；

D：1，C：1，A：1；

C：1，A：1.

步驟3.因為每一項末尾都是A，可以把A去掉，得到新的CPB：

D：1，B1：6；

D：3，B：3，C：3；

D：1，C：1；

C：1.

步驟4.繼續(xù)遞歸調(diào)用PFGrowth(新的CPB，新的PostMOdel)，當發(fā)現(xiàn)CPB為空時遞歸結(jié)束.

在FP-Tree是單枝的情況下，不需要再調(diào)用FPGrowth函數(shù)，直接輸出路徑上的各種組合+postModel即可.

3 實驗結(jié)果

把事務(wù)數(shù)據(jù)庫中的數(shù)據(jù)輸入之后，得到輸出結(jié)果如表3所示.

表3 測試樣本輸出結(jié)果

最小支持度閾值和最小置信度閾值一般由用戶或領(lǐng)域?qū)＜以O(shè)定，前者表示了規(guī)則的普遍程度，后者表示了規(guī)則的最低可靠度.支持度用于衡量關(guān)聯(lián)規(guī)則的重要性或適用范圍.置信度用于衡量關(guān)聯(lián)規(guī)則的準確度，它反映了關(guān)聯(lián)規(guī)則前提成立時其結(jié)果也成立的概率.

最小支持度與置信度閾值的設(shè)定對最終結(jié)果影響較大.如果最小支持度偏大，大量的潛在規(guī)則可能會被刪除；相反，最小支持度偏小，則會推導(dǎo)出大量的規(guī)則，不便于決策者做出正確的判斷.為使所挖掘到的關(guān)聯(lián)規(guī)則具有一定的實用性.支持度閾值不宜設(shè)置過高，否則會遺漏重要的規(guī)則.本文針對大學(xué)生這一健康群體，同時患有多種慢性病的可能性較小，經(jīng)過多次實驗，設(shè)定最小支持度閾值和最小置信度閾值分別為10%和 50%，所獲取的規(guī)則最符合醫(yī)學(xué)常識.把學(xué)生體檢表進行以上各種處理，對得到的事務(wù)數(shù)據(jù)庫中的數(shù)據(jù)通過FP-Tree算法進行挖掘.產(chǎn)生的規(guī)則數(shù)目較多，在獲取的規(guī)則中選取部分如表4所示.

表4 慢性病之間的關(guān)聯(lián)規(guī)則

4 結(jié)束語

本文對大學(xué)生體檢數(shù)據(jù)庫中的數(shù)據(jù)進行各種處理，得到便于進行數(shù)據(jù)挖掘的事務(wù)數(shù)據(jù)庫.再將該事務(wù)數(shù)據(jù)庫中的數(shù)據(jù)用FP-Tree算法進行處理，得到關(guān)聯(lián)規(guī)則，經(jīng)驗證本文得到的規(guī)則是正確的且符合醫(yī)學(xué)事實.在獲取相關(guān)數(shù)據(jù)之后，可以及時告知學(xué)生患慢性疾病的風險，降低患病的概率，從整體上提高大學(xué)生這一群體的身體素質(zhì).