王大勇，李 麗，張 蕾，孫時(shí)光

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

0 引言

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

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

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

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

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

1 FP-Tree算法

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

1.1 相關(guān)定義

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

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

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

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

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

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

AEFG

AFG

ABEFG

EFG

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

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

以此類推，{F，G}的支持?jǐn)?shù)為4，支持度為100%.{A}的支持?jǐn)?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)計(jì)CPB中每一個(gè)項(xiàng)目的個(gè)數(shù)，把個(gè)數(shù)小于最小支持?jǐn)?shù)minSuport的項(xiàng)目刪除掉，然后對(duì)于CPB中的每一條事務(wù)按項(xiàng)目個(gè)數(shù)降序排列.

由CPB構(gòu)建FP-Tree，F(xiàn)P-Tree中包含了表頭項(xiàng)headers，每一個(gè)header都指向了一個(gè)鏈表HeaderLinkList，鏈表中的每個(gè)元素都是FP-Tree上的一個(gè)節(jié)點(diǎn)，且節(jié)點(diǎn)名稱與header.name相同.得到從FP-Tree的根節(jié)點(diǎn)到TreeNode的全路徑path，把path作為一個(gè)事務(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ù)庫(kù)中的數(shù)據(jù)進(jìn)行相關(guān)處理，得到對(duì)應(yīng)的事務(wù)數(shù)據(jù)庫(kù)，再對(duì)事務(wù)數(shù)據(jù)庫(kù)中的數(shù)據(jù)運(yùn)用FP-Tree算法[8-11]，進(jìn)而得到一些有價(jià)值的關(guān)聯(lián)規(guī)則，為醫(yī)生診斷提供輔助依據(jù).

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

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

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

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

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

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

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

表1 慢性病事務(wù)

表2 病情編碼對(duì)照

2.2 實(shí)現(xiàn)過(guò)程

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

ABCD

BEDF

BCD

ABCEDF

ACF

BCF

ACD

ABCGD

ABGD

EG

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

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

DBCA

DBF

DBC

DBCAF

CAF

BCF

DCA

DBCA

DBA

上面的事務(wù)集合即為當(dāng)前的CPB，當(dāng)前的PostModel為空.開(kāi)始構(gòu)造FP-Tree，初始狀態(tài)下FP-Tree為空，建立FP-Tree時(shí)逐條讀入排序之后的數(shù)據(jù)集，按照排序后的順序插入到FP-Tree中，排序靠前的節(jié)點(diǎn)是祖先節(jié)點(diǎn)，靠后的是子孫節(jié)點(diǎn).如果有共同的祖先，則對(duì)應(yīng)的共同祖先節(jié)點(diǎn)計(jì)數(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àng)，表頭項(xiàng)中記錄的是頻繁項(xiàng)集及其出現(xiàn)的個(gè)數(shù).其次樹(shù)中相同名稱的節(jié)點(diǎn)要用鏈表鏈接起來(lái)，如圖4所示，鏈表的第一個(gè)元素就是表頭項(xiàng)里的元素.不論是表頭項(xiàng)節(jié)點(diǎn)還是FP-Tree中的所有節(jié)點(diǎn)，它們都有2個(gè)屬性：name(頻繁項(xiàng)集的名稱)和count(頻繁項(xiàng)集的個(gè)數(shù)).

圖4 用鏈表鏈接的FP-Tree

遍歷表頭項(xiàng)中的每一項(xiàng)，以“A：6”為例.

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

步驟1.從表頭項(xiàng)A開(kāi)始，找到FP-Tree中所有的A節(jié)點(diǎn)，然后找到從樹(shù)的根節(jié)點(diǎn)到A節(jié)點(diǎn)的路徑.得到如下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.對(duì)于每一條路徑上的節(jié)點(diǎn)，其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.因?yàn)槊恳豁?xiàng)末尾都是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)，當(dāng)發(fā)現(xiàn)CPB為空時(shí)遞歸結(jié)束.

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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