孫明瑞, 臧天儀

(哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 哈爾濱 150001)

0 引 言

數(shù)據(jù)挖掘技術(shù)是從海量數(shù)據(jù)集中挖掘出用戶感興趣的物品或知識，這些知識是隱式的、未知的，挖掘出的知識表示為定律、規(guī)律、規(guī)則等形式。關(guān)聯(lián)分析(Association Analysis)是數(shù)據(jù)挖掘的基礎(chǔ)，用以挖掘大規(guī)模、海量數(shù)據(jù)中隱式的規(guī)則關(guān)系模式。大規(guī)模數(shù)據(jù)間存在關(guān)聯(lián)關(guān)系，變量的取值也存在某種規(guī)律性，但數(shù)據(jù)間的關(guān)系是復(fù)雜的、隱式存在的，關(guān)聯(lián)分析的目的就是挖掘數(shù)據(jù)間的隱藏關(guān)聯(lián)信息，對健康醫(yī)療領(lǐng)域具有新的價(jià)值。典型的規(guī)則如購物籃事務(wù)(Market Basket Transaction),“如果用戶購買了嬰兒尿布，那么該用戶購買啤酒的概率為33%”，產(chǎn)生的關(guān)系可以用關(guān)聯(lián)規(guī)則(Association Rule)或頻繁模式(Frequent Pattern)表示，用以反映用戶偏好的有用規(guī)則。

基于以上的分析和討論，本文提出了針對個(gè)人健康信息數(shù)據(jù)的頻繁特征項(xiàng)挖掘算法，擴(kuò)展了關(guān)聯(lián)規(guī)則頻繁模式的概念，引入連續(xù)性特征屬性值并給出離散化的解決方案，改進(jìn)了關(guān)聯(lián)規(guī)則的一般模式，提出了分類關(guān)聯(lián)規(guī)則挖掘算法，對健康醫(yī)療領(lǐng)域和其它領(lǐng)域中基于關(guān)聯(lián)規(guī)則的推薦具有重要的指導(dǎo)意義和研究價(jià)值。

1 相關(guān)工作

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的一個(gè)重要研究方向，描述了交易數(shù)據(jù)集中2組不同對象之間存在的某種關(guān)聯(lián)關(guān)系。在關(guān)聯(lián)規(guī)則挖掘過程中，需要對交易數(shù)據(jù)集進(jìn)行多次掃描并與候選頻繁項(xiàng)目集進(jìn)行匹配和計(jì)數(shù)。由于面對巨量交易數(shù)據(jù)集，這一匹配和計(jì)算過程需要花費(fèi)大量時(shí)間，因此效率是設(shè)計(jì)算法的關(guān)鍵。

1994年Agrawal等人[1]開創(chuàng)性地提出了Apriori算法，用來發(fā)現(xiàn)購物籃中有趣的關(guān)聯(lián)關(guān)系，基于“所有長頻繁項(xiàng)目集的子集都是頻繁”的思想，對候選頻繁項(xiàng)目集進(jìn)行剪枝，使候選頻繁項(xiàng)目集更小，從而顯著改進(jìn)頻繁項(xiàng)目集算法的性能。自此，學(xué)界進(jìn)行了廣泛的研究，來解決關(guān)聯(lián)分析中的實(shí)現(xiàn)和應(yīng)用等問題。FP-growth[2]算法實(shí)現(xiàn)了FP-tree的構(gòu)造及在FP-tree上進(jìn)行挖掘，在效率上較之Apriori算法有很大的提高。Park等人[3]在1995年提出一種高效地產(chǎn)生頻繁項(xiàng)目集的基于雜湊的DHP算法。Savasere等人[4]設(shè)計(jì)了基于劃分的算法。Toivonen[5]提出了一種基于采樣的算法，其核心是隨機(jī)從數(shù)據(jù)集中采集樣本S，然后搜索S中的頻繁項(xiàng)集?；輹詾I等人[6]提出了基于頻繁模式棧變換的高效關(guān)聯(lián)規(guī)則算法。以上這些算法都是從算法實(shí)現(xiàn)問題的角度來解決頻繁項(xiàng)集挖掘。

分類關(guān)聯(lián)規(guī)則(Class Association Rules)是對關(guān)聯(lián)規(guī)則的擴(kuò)展，用以區(qū)分或判別實(shí)例類標(biāo)簽的關(guān)聯(lián)規(guī)則。1998年，Liu等人[7]率先提出了分類關(guān)聯(lián)規(guī)則算法CBA。Wang等人[8]融合分類關(guān)聯(lián)規(guī)則和決策樹的優(yōu)勢，提出關(guān)聯(lián)決策樹ADT算法。Xu等人[9]首次提出利用原子型分類關(guān)聯(lián)規(guī)則構(gòu)建分類器的思想，創(chuàng)立了原子關(guān)聯(lián)規(guī)則分類(CAAR)新技術(shù)。

綜上所述，與傳統(tǒng)的關(guān)聯(lián)規(guī)則相比，分類關(guān)聯(lián)規(guī)則具有更高的準(zhǔn)確性及魯棒性。作為一種新的特征匹配方法，如何處理連續(xù)屬性特征，如何以較小的代價(jià)挖掘頻繁項(xiàng)集，如何從大量關(guān)聯(lián)規(guī)則中提取有效的分類關(guān)聯(lián)規(guī)則，是本文研究的重點(diǎn)內(nèi)容。

2 問題的定義

針對關(guān)聯(lián)規(guī)則模式的挖掘，本次研究的目標(biāo)是將數(shù)據(jù)的最后一列特征屬性類別標(biāo)識設(shè)置為關(guān)聯(lián)規(guī)則的后件，即挖掘分類關(guān)聯(lián)規(guī)則，而非全局關(guān)聯(lián)規(guī)則。設(shè)I={i1,i2, …,in}為具有n個(gè)特征屬性的數(shù)據(jù)集合(項(xiàng)集約束)，y表示類別標(biāo)識屬性，且y∩I=?。分類關(guān)聯(lián)規(guī)則的挖掘目標(biāo)是形如X→y的分類關(guān)聯(lián)關(guān)系，其中X∈I。

3 算法研發(fā)與設(shè)計(jì)

3.1 先驗(yàn)性原理

一般地，包含k個(gè)項(xiàng)的數(shù)據(jù)集會產(chǎn)生2k-1個(gè)頻繁項(xiàng)集，由于k的值可能非常大，導(dǎo)致項(xiàng)集搜索空間的時(shí)間復(fù)雜度是指數(shù)級規(guī)模的O(2n)。因此引入如下定理：

定理 先驗(yàn)(Apriori)原理如果一個(gè)項(xiàng)集是頻繁的，則其所有的子集也一定是頻繁的。

引理如果項(xiàng)集是非頻繁的，則其所有超集也都是非頻繁的。

性質(zhì) 單調(diào)性原理設(shè)I是項(xiàng)的集合，J=2I是I的冪集。度量f是單調(diào)的(向上封閉的)，當(dāng)

?X,Y∈J:(X?Y)→f(X)≤f(Y),

(1)

其中，X為Y的子集，則f(X)一定不會超過f(Y)。

另一方面，f是反單調(diào)的(向下封閉)，當(dāng)

?X,Y∈J:(X?Y)→f(Y)≤f(X).

(2)

根據(jù)性質(zhì)，如圖1所示，通?？梢圆捎米皂斚蛳?從1維到n維的項(xiàng)集搜索)或自底向上(從n維到1維的項(xiàng)集搜索)的搜索策略挖掘頻繁項(xiàng)集。

圖1 頻繁項(xiàng)集封閉性原則

3.2 頻繁項(xiàng)集挖掘算法

Apriori算法基于支持度剪枝技術(shù)，采用分層的完備搜索算法(深度優(yōu)先)，依據(jù)性質(zhì)向下封閉性，對關(guān)聯(lián)規(guī)則進(jìn)行挖掘，能有效防止項(xiàng)集的指數(shù)級增長。算法的功能是挖掘支持度大于等于minsup的項(xiàng)集。算法首先生成單個(gè)元素項(xiàng)集列表，通過掃描數(shù)據(jù)集計(jì)算滿足最小支持度的項(xiàng)集，刪除不滿足最小支持度的項(xiàng)集。對單個(gè)元素的項(xiàng)集進(jìn)行組合以生成2個(gè)元素的項(xiàng)集。然后，重新掃描數(shù)據(jù)集，刪除不滿足最小支持度的項(xiàng)集，重復(fù)該過程直到所有項(xiàng)集都被刪除。頻繁項(xiàng)集挖掘算法的設(shè)計(jì)描述見如下。

算法1 頻繁項(xiàng)集挖掘算法

輸入數(shù)據(jù)集I，最小支持度minsup，頻繁項(xiàng)集個(gè)數(shù)kmax

輸出頻繁項(xiàng)集Fk

k←random integer from 1 tokmax

Ifk=1 thenFk←{i|i∈I∧σ(i)≥N×minsup} //發(fā)現(xiàn)所有的頻繁1-項(xiàng)集

Else do

k←k+1

Ck←apriori-gen(Fk-1)//產(chǎn)生候選項(xiàng)集

For eacht∈Tdo

Ct←subset(Ck,t)

//識別屬于t的所有候選

For eachc∈Ctdo

σ(c)←σ(c)+1

//支持度計(jì)數(shù)增值

End for

End for

Fk←{c|c∈Ck∧σ(c)≥N×minsup} //提取頻繁k-項(xiàng)集

UntilFk=?

Return ∪Fk

3.3 候選項(xiàng)集的挖掘和剪枝

候選項(xiàng)集挖掘通過合并頻繁k-1項(xiàng)集，當(dāng)且僅當(dāng)前k-2項(xiàng)都相同。這里設(shè)X={x1,x2,…,xk-1}和Y={y1,y2,…,yk-1}是頻繁k-1項(xiàng)集，合并X和Y，當(dāng)其均滿足如下公式：

xi=yi(i=1, 2,…,k-2)且xi-1≠yi-1.

(3)

3.4 算法的時(shí)間復(fù)雜度

3.5 分類關(guān)聯(lián)規(guī)則挖掘算法

針對分類關(guān)聯(lián)規(guī)則挖掘，關(guān)聯(lián)規(guī)則的后件為類別標(biāo)識，即形如X→y的分類關(guān)聯(lián)規(guī)則。通過3.2節(jié)頻繁項(xiàng)集挖掘，研究得到了最大頻繁項(xiàng)集Fk，由其產(chǎn)生的子集可作為分類關(guān)聯(lián)規(guī)則的前件，而目標(biāo)類標(biāo)識作為關(guān)聯(lián)規(guī)則后件，是一種存在具體搜索目標(biāo)的挖掘優(yōu)化問題，同時(shí)需要滿足設(shè)定的最小支持度和最小置信度閾值要求。這里，給出了分類關(guān)聯(lián)規(guī)則挖掘算法的研發(fā)代碼詳見如下。

算法2 分類關(guān)聯(lián)規(guī)則挖掘算法

輸入頻繁k項(xiàng)集Fk

輸出分類關(guān)聯(lián)規(guī)則Car

For (i=2;Fi-1≠?;i++) Do

Ck←Car-candidate-gen(Fi-1);

Foreachfrequentitemsetf∈FkDo

Foreachcandidatec∈CkDo

Ifc.classsetiscontainedinfThen

c.classsupCount++;

Iff.class=c.classThen

c.rulesupCount++;

End for

End for

Cark←{f|f∈Fk,f.rulesupCount/f.classsupCount≥minconf};

End for

Return ∪Cark

4 實(shí)驗(yàn)評估

實(shí)驗(yàn)采用公開的臨床數(shù)據(jù)集：加州大學(xué)歐文分校慢性腎病(Chronic Kidney Disease，CKD)數(shù)據(jù)集和皮膚病(Dermatology)數(shù)據(jù)集?？紤]到數(shù)據(jù)集具有一定程度的缺失度，因此采用均值插值的方法對缺失值進(jìn)行插值，并對連續(xù)屬性項(xiàng)進(jìn)行離散化分類處理。挖掘個(gè)人健康數(shù)據(jù)之間隱式關(guān)系、頻繁項(xiàng)集、及分類關(guān)聯(lián)規(guī)則模式。

慢性腎病數(shù)據(jù)集中有400個(gè)觀測值，每個(gè)樣本有25個(gè)屬性項(xiàng)，其中14個(gè)是線性值類別屬性項(xiàng)，11個(gè)是連續(xù)數(shù)值屬性項(xiàng)，目標(biāo)類是二元指示器，表征患者是否患有慢性腎病(ckd表示患有慢性腎病，notckd表示不患有慢性腎病)。皮膚病數(shù)據(jù)集中有366個(gè)觀測值，每個(gè)樣本具有35個(gè)屬性項(xiàng)。其中，34個(gè)是線性類別屬性項(xiàng)，1個(gè)年齡屬性是連續(xù)屬性項(xiàng)，目標(biāo)類為6種可能的疾病類型。

4.1 數(shù)據(jù)預(yù)處理

實(shí)驗(yàn)中，當(dāng)對年齡區(qū)間進(jìn)行離散化時(shí)，遇到的問題是如何確定區(qū)間的寬度。如果區(qū)間過寬，會因?yàn)槿狈χ眯哦榷鴣G失部分關(guān)聯(lián)模式；如果區(qū)間過窄，會因?yàn)槿狈χС侄榷鴣G失部分關(guān)聯(lián)模式；如果區(qū)間寬度定為10歲，將會導(dǎo)致某些置信度低于閾值，或者某些支持度低于閾值。因此，研究采用分位數(shù)離散化(Quantile Discretizer)將連續(xù)型數(shù)據(jù)轉(zhuǎn)換成分類型數(shù)據(jù)。

對于連續(xù)屬性項(xiàng)類別數(shù)目，研究中是依據(jù)已有特征屬性項(xiàng)目的分類的最大值確定。因此采用6個(gè)類別來劃分各屬性值，詳見表1。例如，年齡屬性([2, 90])通過字典序排序后，取用戶數(shù)目的6個(gè)百分位數(shù)分成6個(gè)區(qū)間，即{(2, 34], (34, 46], (46, 54], (54, 60], (60, 67], (67, 90]}，確保轉(zhuǎn)換后的年齡特征的類別平衡性。

實(shí)驗(yàn)使用的皮膚病數(shù)據(jù)集見表2，年齡屬性項(xiàng)采用6個(gè)類別進(jìn)行離散化處理，即(0, 21], (21, 29], (29, 36], (36, 43], (43, 52], (52, 75]，確保轉(zhuǎn)換后的年齡特征的類別平衡性。

表1 實(shí)驗(yàn)所使用的慢性腎病數(shù)據(jù)集

表2 實(shí)驗(yàn)所使用的皮膚病數(shù)據(jù)集

4.2 CKD數(shù)據(jù)集頻繁項(xiàng)集及關(guān)聯(lián)規(guī)則挖掘

研究設(shè)定數(shù)據(jù)集中最后一列為目標(biāo)類(ckd=患病，notckd=未患病)，也就是分類關(guān)聯(lián)規(guī)則的后件，實(shí)驗(yàn)的最小支持度minsup=0.15，最小置信度minconf=0.6，挖掘出最大的頻繁k=13項(xiàng)集數(shù)量為3個(gè)，由此產(chǎn)生的關(guān)聯(lián)規(guī)則模式見表3(截取前6個(gè)強(qiáng)關(guān)聯(lián)規(guī)則模式)。

表3 CKD數(shù)據(jù)集關(guān)聯(lián)規(guī)則模式

Tab. 3 Association rule patterns for chronic kidney disease data sets

分類關(guān)聯(lián)規(guī)則模式支持度置信度高血壓=yes=>class=ckd0.367 51糖尿病=yes·==>·class=ckd0.342 51細(xì)菌域=notpresent·高血壓=yes·==>·class=ckd0.337 51膿細(xì)胞團(tuán)=notpresent·高血壓=yes·==>·class=ckd0.300 01高血壓=yes·冠心病=no·==>·class=ckd0.292 51膿細(xì)胞團(tuán)=notpresent·糖尿病=yes·==>·class=ckd0.282 51

由表3可知，當(dāng)用戶患有高血壓疾病時(shí)，患有慢性腎病的支持度為36.75%，置信度為1；當(dāng)用戶患有糖尿病時(shí)，患有慢性腎病的支持度為34.25%，置信度為1；當(dāng)這兩種疾病與其它個(gè)人健康數(shù)據(jù)狀況并發(fā)發(fā)生時(shí)，支持度略有下降。關(guān)聯(lián)規(guī)則模式中另外一條記錄(高血壓=yes 糖尿病=yes ==> class=ckdsup:0.265conf:1)，表示同時(shí)患有高血壓和糖尿病的患者罹患慢性腎病的樣例共有106例，置信度為1。此實(shí)驗(yàn)的研究結(jié)果與慢性腎病權(quán)威機(jī)構(gòu)NIDDK提出的影響因素完全吻合[10]。因此，如果一名患者滿足上述條件，那么該患者就有極大的可能性發(fā)展成為慢性腎病，對個(gè)人健康的影響風(fēng)險(xiǎn)巨大。針對此情況，患者要做好預(yù)防慢性腎病的準(zhǔn)備。通過對分類關(guān)聯(lián)規(guī)則模式和規(guī)律的分析，就可以挖掘有意義的信息來評價(jià)患者的身體狀況。通過研究結(jié)果，最終揭示慢性腎病致病因素與個(gè)人健康數(shù)據(jù)狀況的關(guān)聯(lián)關(guān)系，要控制并發(fā)癥的產(chǎn)生，防止疾病進(jìn)一步惡化的情況出現(xiàn)，使患者能夠及時(shí)接受治療，為用戶健康提供科學(xué)的服務(wù)推薦方法。

4.3 皮膚病數(shù)據(jù)集頻繁項(xiàng)集及關(guān)聯(lián)規(guī)則挖掘

研究中,設(shè)定數(shù)據(jù)集中最后一列為目標(biāo)類(銀屑病=1，皮脂性皮炎=2，扁平苔蘚=3，玫瑰糠疹=4，慢性皮炎=5，毛發(fā)紅糠疹=6)，即關(guān)聯(lián)規(guī)則的后件，本文中實(shí)驗(yàn)的最小支持度minsup=0.15，最小置信度minconf=0.6，挖掘出最大的頻繁k=14項(xiàng)集數(shù)量為1個(gè)，由此產(chǎn)生的關(guān)聯(lián)規(guī)則模式見表4。截取6個(gè)強(qiáng)關(guān)聯(lián)規(guī)則模式，其中2個(gè)分類關(guān)聯(lián)規(guī)則模式的目標(biāo)類為“皮脂性皮炎=2”和“扁平苔蘚=3”。

表4 皮膚病數(shù)據(jù)集關(guān)聯(lián)規(guī)則模式

由實(shí)驗(yàn)可知，銀屑病(class=1)的關(guān)聯(lián)規(guī)則模式數(shù)量遠(yuǎn)大于其它類型皮膚病關(guān)聯(lián)規(guī)則模式的數(shù)量。以表4中第一條數(shù)據(jù)為例，若某個(gè)皮膚病患者的臨床癥狀滿足“多邊形丘疹=0，乳頭狀真皮纖維化=0，胞吐=0，海綿水腫=0，濾泡性角插頭=0”，那么該患者的皮膚病類型為銀屑病的支持度為25.41%，置信度為1。因此，如果一名皮膚病患者滿足上述條件，那么就有極大的可能性是患有銀屑病類型的皮膚病，醫(yī)生會根據(jù)銀屑病的臨床癥狀與疾病特點(diǎn)，對患者對癥下藥。通過對皮膚病關(guān)聯(lián)規(guī)則模式和規(guī)律的分析，可以挖掘出有意義的數(shù)據(jù)信息來對患者所屬的皮膚病類別加以區(qū)分，針對疾病的特點(diǎn)進(jìn)行治療，為患者提供個(gè)性化的服務(wù)推薦方法。

4.4 算法性能評估

本節(jié)將討論算法的性能。首先研究在不同最小支持度和最小置信度下的算法運(yùn)行時(shí)間，如圖2所示。2個(gè)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果顯示，最小置信度的變化對運(yùn)行時(shí)間的性能影響不大，但是當(dāng)最小支持度變小時(shí)運(yùn)行時(shí)間會呈指數(shù)級增長。

對于構(gòu)建的關(guān)聯(lián)規(guī)則數(shù)量，如圖3所示，關(guān)聯(lián)規(guī)則的數(shù)量與運(yùn)行時(shí)間的情況類似，都是隨著最小支持度的降低，而呈現(xiàn)指數(shù)級的增長。

頻繁項(xiàng)集的數(shù)量，只與最小支持度有關(guān)，與最小置信度無關(guān)，如圖4所示。頻繁項(xiàng)集的數(shù)量也是隨著最小支持度的降低成指數(shù)級增長。這些實(shí)驗(yàn)結(jié)果表明，最小支持度，也就是項(xiàng)集的反單調(diào)性，對剔除非頻繁項(xiàng)集是非常有效的。

圖2 不同最小支持度和最小置信度的運(yùn)行時(shí)間

Fig. 2 Running time with different minimum support and minimum confidence

圖3 不同最小支持度和最小置信度的關(guān)聯(lián)規(guī)則數(shù)量

Fig. 3 Number of association rules with different minimum support and minimum confidence

圖4 不同最小支持度的頻繁項(xiàng)集數(shù)量

Fig. 4 Number of frequent itemsets with different minimum supports

綜上所述，如果最小支持度minsup較高，比如達(dá)到30%，此時(shí)就可以用較短的運(yùn)行時(shí)間獲得較少而有意義的關(guān)聯(lián)規(guī)則，當(dāng)然其中的很多規(guī)則可能是平凡的。如果為了挖掘更有意義的關(guān)聯(lián)規(guī)則模式，可以采用較小的最小支持度，但這會導(dǎo)致無法接受的系統(tǒng)運(yùn)行時(shí)間和指數(shù)級關(guān)聯(lián)規(guī)則和頻繁項(xiàng)集。因此采用合理的、可接受的最小支持度和最小置信度的值，是非常必要的。

5 結(jié)束語

本文提出從數(shù)據(jù)的隱式特征中識別出數(shù)據(jù)間的分類關(guān)聯(lián)規(guī)則模式，通過支持度和置信度的權(quán)衡保證分類關(guān)聯(lián)規(guī)則模式的有效性。基于關(guān)聯(lián)分析的算法，對數(shù)據(jù)內(nèi)在特征的分類關(guān)聯(lián)規(guī)則模式進(jìn)行挖掘，實(shí)現(xiàn)了個(gè)人健康數(shù)據(jù)的分解及分類，挖掘出數(shù)據(jù)的頻繁項(xiàng)集，發(fā)現(xiàn)致病因素的重要數(shù)據(jù)特征，對個(gè)人健康特征的疾病預(yù)防與推薦具有重要的指導(dǎo)和建設(shè)性意義。