FP-Tree算法規則挖掘的研究與應用

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

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

0 引言

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

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

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

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

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

1 FP-Tree算法

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

1.1 相關定義

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

定義2 支持度：關聯規則X→Y的支持度(support)用support(X→Y)=|X∩Y|/|N|表示，其中X和Y為事務數據庫中的集合，|X∩Y| 是X和Y同時出現的次數，|N|為事務數據庫中集合的個數.

定義3 置信度(confidence)：關聯規則X→Y的置信度(confidence)用confidence(X→Y) =|X∩Y|/|X| 表示，其中X和Y為事務數據庫中的集合，|X∩Y| 是X和Y同時出現的次數，|X|是集合X出現的次數.

支持度是對關聯規則重要性的衡量，支持度越大，表示這種關聯規則越重要.置信度是對關聯規則準確度的衡量.有些關聯規則的支持度雖高，但置信度低，說明該關聯規則準確度不夠，不能采用；有些關聯規則的置信度雖然很高，但是支持度低，說明該關聯規則出現的機會很小，實用價值不大.在進行實際關聯規則挖掘分析時，必須選擇恰當的最小支持度閾值和最小置信度閾值.如果取值過低，則會發現大量無用的規則，不利于所需規則的發現和獲取.如果取值過高，則可能得不到規則，或者得到的規則過少，導致所需規則不滿足條件而沒有被篩選出來.一般需要根據實際情況設定合適的閾值.

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

假設事務數據庫如下：

AEFG

AFG

ABEFG

EFG

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

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

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

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

1.2 FP-Tree算法描述

輸入：事務集合 List> transactions，

輸出：頻繁模式集合及相應的頻數Map，Integer>FrequentPattens，

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

void FPGrowth(List> CPB，List PostModel){

if CPB為空，

return

}.

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

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

for header in headers：

newPostModel=header.name+PostModel，

newCPB=[]，

for TreeNode in HeaderLinkList：

FPGrowth(newCPB，newPostModel).

2 規則挖掘應用

把大學生體檢數據庫中的數據進行相關處理，得到對應的事務數據庫，再對事務數據庫中的數據運用FP-Tree算法[8-11]，進而得到一些有價值的關聯規則，為醫生診斷提供輔助依據.

2.1 數據處理

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

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

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

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

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

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

表1 慢性病事務

表2 病情編碼對照

2.2 實現過程

在慢性病事務數據庫中任意選取10個事務應用于FPGrowth函數，完整實現過程選取的10個事務：

ABCD

BEDF

BCD

ABCEDF

ACF

BCF

ACD

ABCGD

ABGD

EG

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

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

DBCA

DBF

DBC

DBCAF

CAF

BCF

DCA

DBCA

DBA

上面的事務集合即為當前的CPB，當前的PostModel為空.開始構造FP-Tree，初始狀態下FP-Tree為空，建立FP-Tree時逐條讀入排序之后的數據集，按照排序后的順序插入到FP-Tree中，排序靠前的節點是祖先節點，靠后的是子孫節點.如果有共同的祖先，則對應的共同祖先節點計數加1.直到所有的數據都插入到FP-Tree后，FP-Tree建立完成.由CPB構建FP-Tree的步驟為：

步驟1.插入第1條事務(D，B，C，A)，FP-Tree如圖1所示.

圖1 插入第1條事務的FP-Tree

步驟2.插入第2條事務(D，B，F)，FP-Tree如圖2所示.

圖2 插入前兩條事務的FP-Tree

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

圖3 插入全部事務的FP-Tree

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

圖4 用鏈表鏈接的FP-Tree

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

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

步驟1.從表頭項A開始，找到FP-Tree中所有的A節點，然后找到從樹的根節點到A節點的路徑.得到如下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.對于每一條路徑上的節點，其count都設置為A的count，結果如下：

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.繼續遞歸調用PFGrowth(新的CPB，新的PostMOdel)，當發現CPB為空時遞歸結束.

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

3 實驗結果

把事務數據庫中的數據輸入之后，得到輸出結果如表3所示.

表3 測試樣本輸出結果

最小支持度閾值和最小置信度閾值一般由用戶或領域專家設定，前者表示了規則的普遍程度，后者表示了規則的最低可靠度.支持度用于衡量關聯規則的重要性或適用范圍.置信度用于衡量關聯規則的準確度，它反映了關聯規則前提成立時其結果也成立的概率.

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

表4 慢性病之間的關聯規則

4 結束語

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