改進(jìn)關(guān)聯(lián)規(guī)則算法對乳腺癌擴(kuò)散的預(yù)測研究

艾云昊，楊超宇，李慧宗

（安徽理工大學(xué)，安徽淮南232001）

0 引言

乳腺癌是發(fā)生在乳腺上皮組織的惡性腫瘤，原位的乳腺癌并不致命，但是由于乳腺癌細(xì)胞喪失了正常細(xì)胞的特性，細(xì)胞之間連接松散、容易脫落，一旦癌細(xì)胞脫落，游離的癌細(xì)胞就會隨著血液或淋巴液擴(kuò)散至全身，形成轉(zhuǎn)移，危及患者的生命。根據(jù)2019年1月國家癌癥中心發(fā)布的全國癌癥統(tǒng)計(jì)數(shù)據(jù)，乳腺癌是女性中發(fā)病率和死亡率最高的癌癥［1］。因此，尋找出關(guān)聯(lián)度高的因素，并利用這些因素對乳腺癌的擴(kuò)散進(jìn)行預(yù)測具有十分重要的意義。

關(guān)聯(lián)規(guī)則的概念最早由Agrawal［2］于1993年提出，目的是用來解決顧客交易數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則問題。由于當(dāng)時(shí)用來進(jìn)行關(guān)聯(lián)規(guī)則挖掘的AIS算法在運(yùn)算過程中會產(chǎn)生過多的候選項(xiàng)集，在1994年Agrawal和Srikant根據(jù)AIS算法提出了Apriori算法［3］，這種布爾型關(guān)聯(lián)規(guī)則挖掘頻繁項(xiàng)集的算法能大大提高數(shù)據(jù)挖掘的效率。但是算法在實(shí)際應(yīng)用中存在一些缺點(diǎn)，其中之一就是此算法只能處理離散數(shù)值而無法處理連續(xù)數(shù)據(jù)。針對該問題，傳統(tǒng)的方法是通過直接劃分將連續(xù)數(shù)據(jù)轉(zhuǎn)換為若干離散區(qū)間。不過，這種離散化手段存在“尖銳邊界”問題。1995年，Cubero等［4］引入模糊集理論，提出“模糊關(guān)聯(lián)規(guī)則”，之后陸續(xù)有學(xué)者從隸屬度函數(shù)的確定［5］和模糊關(guān)聯(lián)規(guī)則模型的構(gòu)建［6］等方面對模糊關(guān)聯(lián)規(guī)則進(jìn)行了研究。

本文將從支持度的計(jì)算方法入手，提出根據(jù)模糊區(qū)域分別計(jì)算事務(wù)項(xiàng)支持度的計(jì)算方法，這項(xiàng)改進(jìn)使得Apriori算法能夠處理的數(shù)據(jù)不僅僅只限于離散型數(shù)據(jù)。改進(jìn)算法還引入了確定性因子（certainty factor，CF）［7-8］以完善傳統(tǒng)關(guān)聯(lián)規(guī)則采用的“支持度-置信度”評價(jià)體系。對比改進(jìn)算法和Apriori算法挖掘出的關(guān)聯(lián)規(guī)則的數(shù)量和規(guī)則質(zhì)量評價(jià)函數(shù)值［9］，可知改進(jìn)算法可以挖掘出更多的規(guī)則且挖掘出的規(guī)則質(zhì)量更高，并且改進(jìn)算法挖掘出的關(guān)聯(lián)規(guī)則對乳腺癌患者臨床治療有一定的參考意義。

1 Apriori算法

Apriori算法是經(jīng)典的布爾型關(guān)聯(lián)規(guī)則挖掘算法，被廣泛應(yīng)用于數(shù)據(jù)挖掘領(lǐng)域。Apriori算法采用逐層搜索的迭代方法，利用先驗(yàn)知識進(jìn)行候選項(xiàng)集剪枝，縮小搜索范圍，挖掘算法步驟如下：

1）設(shè)定最小支持度minSupp和最小置信度minConf的閾值；

2）對數(shù)據(jù)庫進(jìn)行掃描，記錄各項(xiàng)及其出現(xiàn)的次數(shù)得到候選1-項(xiàng)集，選取大于minSupp的項(xiàng)，組成頻繁1-項(xiàng)集；

3）將頻繁1-項(xiàng)集中任意兩個(gè)項(xiàng)集彼此連接得到候選2-項(xiàng)集，對候選2-項(xiàng)集進(jìn)行支持度的計(jì)算，然后保留滿足支持度值的項(xiàng)集，得到頻繁2-項(xiàng)集；

4）以此類推，將頻繁（k-1）-項(xiàng)集中任意兩個(gè)項(xiàng)集彼此連接得到候選k-項(xiàng)集，然后對候選k-項(xiàng)集進(jìn)行支持度的計(jì)算，保留大于minSupp的項(xiàng)，組成頻繁k-項(xiàng)集。重復(fù)該步驟，直到候選N-項(xiàng)集的所有項(xiàng)的支持度都小于minSupp為止，此時(shí)頻繁（N-1）-項(xiàng)集就被稱為最大頻繁項(xiàng)集；

5）獲取最大頻繁項(xiàng)集的非空子集，計(jì)算各個(gè)非空子集之間的置信度，選出大于minConf的規(guī)則，這些規(guī)則就是強(qiáng)關(guān)聯(lián)規(guī)則。

2 引入模糊集理論的改進(jìn)Apriori算法

2.1 連續(xù)型數(shù)據(jù)支持度的計(jì)算

本文考慮的情況是數(shù)據(jù)中只有一個(gè)屬性的數(shù)據(jù)是連續(xù)型數(shù)據(jù)的情況，運(yùn)行Apriori算法時(shí)只需改變對連續(xù)型數(shù)據(jù)的支持度計(jì)算方法即可。具體步驟如下，假設(shè)數(shù)據(jù)中只有一個(gè)屬性的數(shù)據(jù)是連續(xù)型數(shù)據(jù)，首先確定隸屬度函數(shù)，根據(jù)隸屬度函數(shù)對原始數(shù)據(jù)進(jìn)行模糊化，將模糊屬性分為N個(gè)模糊區(qū)域(X1,X2,…,XN)，然后將數(shù)據(jù)庫內(nèi)的每一個(gè)項(xiàng)Zi分為T=((Zi,Y1),(Zi,Y2),…,(Zi,YN))這N種情況。假設(shè)N為3，對候選項(xiàng)T進(jìn)行計(jì)數(shù)時(shí)，先對數(shù)據(jù)庫進(jìn)行掃描。假設(shè)一條事務(wù)內(nèi)同時(shí)含 有Zi和 連 續(xù) 數(shù) 據(jù)Y，先 將Zi分 為(Zi,Y1)、(Zi,Y2)、(Zi,Y3)這3種 情 況，它 們 的 支 持 度 為S1、S2、S3。計(jì) 算 連 續(xù) 數(shù) 據(jù)Y在(X1,X2,X3)這3個(gè) 模 糊 區(qū) 域 上 面 的 隸 屬 度f1、f2、f3，然 后S1、S2、S3分別加上f1、f2、f3。若某一條事務(wù)中只含有Zi不含有連續(xù)數(shù)據(jù)Y，則對S1、S2、S3分別加上1/N（這里假設(shè)N為3，所以是分別加上1/3），以此類推。最后將S1、S2、S3分別除以總事務(wù)數(shù)D就得到了(Zi,Y1)、(Zi,Y2)、(Zi,Y3)的支持度。

2.2 引入新指標(biāo)

本文引入兩個(gè)新的指標(biāo)：①確定性因子（certainty factor，CF）；②規(guī)則質(zhì)量評價(jià)函數(shù)φ(r)。確定性因子CF(A→B)定義［7］為式中A→B為一條關(guān)聯(lián)規(guī)則，A為前件，B為后件，Conf(A→B)為前件為A后件為B的關(guān)聯(lián)規(guī)則的置信度，Supp(B)為關(guān)聯(lián)規(guī)則后件B的支持度。由（1）式可知，確定性因子會產(chǎn)生一個(gè)［-1，1］區(qū)間的值。當(dāng)?shù)弥狝包含在某個(gè)事務(wù)中，確定性因子可以度量B在那個(gè)事務(wù)中的可信度是如何變化的。正值表示可信度增加，負(fù)值表示可信度下降，而0表示可信度沒有變化。“支持度-置信度”評價(jià)體系加入確定性因子，可以擁有更好的性能。

規(guī)則質(zhì)量評價(jià)函數(shù)φ(r)的定義［9］為式中的r為關(guān)聯(lián)規(guī)則，minSupp、minConf、minCF分別是最小支持度、最小置信度、最小確定性因子。由（2）式可以看出，φ(r)的值越大，表明規(guī)則的質(zhì)量越好。在此基礎(chǔ)上建立對規(guī)則質(zhì)量評價(jià)的指標(biāo)：

1）?5=maxr1,r2,...,r5φ(r)，質(zhì)量最高的5條規(guī)則的平均質(zhì)量；

2）?10=maxr1,r2,...,r10φ(r)，質(zhì)量最高的10條規(guī)則的平均質(zhì)量；

3）?n2=maxr1,r2,...,rn2φ(r)，質(zhì)量最高的n2條規(guī)則的平均質(zhì)量，n為挖掘出的規(guī)則總數(shù)。

2.3 改進(jìn)Apriori算法的挖掘步驟

根據(jù)2.1提出的新的支持度計(jì)算方法和2.2引入的確定性因子，結(jié)合傳統(tǒng)Apriori算法的挖掘步驟，最終改進(jìn)關(guān)聯(lián)規(guī)則算法的計(jì)算步驟如下：

1）設(shè)定minSupp、minConf和minCF的閾值與隸屬度函數(shù)；

2）對數(shù)據(jù)庫進(jìn)行掃描，得到不包含連續(xù)數(shù)據(jù)的候選1-項(xiàng)集，然后在候選1-項(xiàng)集內(nèi)的每個(gè)項(xiàng)后面加上表示連續(xù)數(shù)據(jù)的Y，使得候選1-項(xiàng)集變?yōu)門=((Zi,Y1),(Zi,Y2),…,(Zi,YN))，然后按照2.1提出的支持度計(jì)算方法計(jì)算T項(xiàng)集內(nèi)各個(gè)數(shù)據(jù)項(xiàng)的支持度，然后與minSupp比較，選取大于minSupp的項(xiàng)，組成頻繁1-項(xiàng)集；

3）將頻繁1-項(xiàng)集中的任意兩個(gè)項(xiàng)集彼此連接得到候選2-項(xiàng)集，對候選2-項(xiàng)集進(jìn)行支持度的計(jì)算，然后與minSupp進(jìn)行比較，選取大于minSupp的項(xiàng)組成頻繁2-項(xiàng)集；

4）以此類推，將頻繁（k-1）-項(xiàng)集中的任意兩個(gè)項(xiàng)集彼此連接，得到候選k-項(xiàng)集，然后對候選k-項(xiàng)集進(jìn)行支持度的計(jì)算，再將其與minSupp進(jìn)行比較，選取大于minSupp的項(xiàng)，組成頻繁k-項(xiàng)集。重復(fù)該步驟，直到候選N-項(xiàng)集的所有項(xiàng)的支持度都小于minSupp為止，此時(shí)頻繁（N-1）項(xiàng)集就被稱為最大頻繁項(xiàng)集；

5）獲取最大頻繁項(xiàng)集的非空子集，計(jì)算各個(gè)非空子集之間的置信度和確定性因子，選出同時(shí)大于minConf和minCF的規(guī)則，這些規(guī)則就是強(qiáng)關(guān)聯(lián)規(guī)則。

算法流程圖見圖1。

圖1改進(jìn)Apriori算法流程圖Fig.1 Improved Apriori algorithm flow chart

3 改進(jìn)Apriori算法在乳腺癌患者就診數(shù)據(jù)中的應(yīng)用

3.1 數(shù)據(jù)的來源與參數(shù)的選取

本文的原始數(shù)據(jù)來自于San Francisco-Oakl and SMSA、Connecticut、Metropolitan Detroit等18個(gè)參與SEER項(xiàng)目的注冊中心。原始數(shù)據(jù)包含有4 409 310位癌癥患者的就診記錄。本文使用的數(shù)據(jù)是從原始數(shù)據(jù)中抽取出的患有乳腺癌后癌癥發(fā)生擴(kuò)散的患者數(shù)據(jù)，擴(kuò)散方向?yàn)榻Y(jié)直腸癌、胃癌、女性生殖系統(tǒng)癌癥、淋巴癌、呼吸道系統(tǒng)癌癥、泌尿系統(tǒng)癌癥和其他。

目前的研究發(fā)現(xiàn)，乳腺癌中絕大多數(shù)為浸潤性導(dǎo)管癌，而雌激素受體（estrogen receptor，ER）、孕激素受體（progesterone receptor，PR）和人表皮生長因子受體-2（HER2）是乳腺癌組織中重要的生物學(xué)標(biāo)志物，因此ER、PR和它們相對應(yīng)的預(yù)后指標(biāo)（ERA、PRA）也成為乳腺癌重要的預(yù)測因子［10］。在乳腺癌發(fā)生、發(fā)展的過程中，細(xì)胞形態(tài)學(xué)變化的規(guī)律是“正常乳腺上皮細(xì)胞→乳腺一般增生→乳腺不典型性增生→乳腺癌”，其發(fā)生、發(fā)展、擴(kuò)散都與腫瘤的組織學(xué)分級等密切相關(guān)［11］。原始數(shù) 據(jù)包含的 參數(shù)中，表示ER和PR的是erstatus和prstatus，表示ER和PR對應(yīng) 的 乳腺癌預(yù)后指標(biāo)的參數(shù)是TUMOR_1V和TUMOR_2V，表示腫瘤組織學(xué)分級的參數(shù)是T_VAL?UE、N_VALUE和M_VALUE（這3個(gè)參數(shù)都是根據(jù)AJCC第八版文獻(xiàn)來劃分［12］）。由于年齡和雌孕激素受體有關(guān)聯(lián)［13］，且本文探究的是乳腺癌擴(kuò)散的預(yù)測，所以代表年齡的參數(shù)AGE_DX和代表乳腺癌擴(kuò)散方向的參數(shù)DIRECTION也需要在實(shí)驗(yàn)的時(shí)候被考慮。最終本文選取10個(gè)參數(shù) 進(jìn) 行 實(shí) 驗(yàn)，它 們 分 別 是erstatus、prstatus、her2、TUMOR_1V、TUMOR_2V、T_VALUE、N_VALUE、M_VALUE、AGE_DX、DIRECTION。

3.2 連續(xù)型數(shù)據(jù)的模糊化

由于3.1選取的10個(gè)指標(biāo)中的年齡是連續(xù)型數(shù)據(jù)，所以需要進(jìn)行模糊化，使其能夠被關(guān)聯(lián)規(guī)則算法處理。模糊化的第一步是劃分模糊區(qū)域。數(shù)據(jù)中的年齡的值域?yàn)椋?4，107］，所以此次討論的論域?yàn)椋?4，107］。利用模糊聚類方法對數(shù)據(jù)進(jìn)行模糊聚類劃分，將年齡數(shù)據(jù)分為青年、中年、老年3個(gè)模糊區(qū)域。第二步是確定隸屬度函數(shù)。實(shí)踐中，隸屬度函數(shù)存在很多不同類型，例如三角波形、梯形波形、高斯波形、鐘形波形、S型波形和S曲線波形［14］，本文參考Zadeh［15］對年齡屬性的劃分，選用梯形波形。結(jié)合本文使用的實(shí)際數(shù)據(jù)進(jìn)行調(diào)整，最終得到的隸屬度函數(shù)為

3.3 改進(jìn)算法對比分析

利用隸屬度函數(shù)將年齡數(shù)據(jù)模糊化之后，使用改進(jìn)算法進(jìn)行挖掘，并且將結(jié)果同使用傳統(tǒng)Apriori算法挖掘的結(jié)果進(jìn)行對比，其中使用Apriori挖掘時(shí)為了解決Apriori算法無法處理連續(xù)型數(shù)據(jù)的問題，通過對連續(xù)型數(shù)據(jù)直接劃分來達(dá)到離散化的目的，為了保證論文的嚴(yán)謹(jǐn)性，沿用連續(xù)數(shù)據(jù)模糊化時(shí)的劃分標(biāo)準(zhǔn)，將年齡直接劃分成{［14，44），［44，69），［69，107］}，這3段分別對應(yīng)青年、中年、老年。設(shè)定最小置信度為0.8，最小確定性因子為0.7，通過比較最小支持度不同時(shí)這兩種方法的規(guī)則數(shù)量和規(guī)則質(zhì)量，對這兩種方法進(jìn)行評判。圖2和圖3表明，改進(jìn)后的算法得到的規(guī)則數(shù)是持續(xù)大于改進(jìn)前的算法的，也就是說改進(jìn)后的算法可以得到更多的規(guī)則。

由圖3可以看出，若是只考慮包含有DIRECTION屬性的規(guī)則，在minSupp較低的時(shí)候改進(jìn)后的算法挖掘出的規(guī)則數(shù)量相對原算法有顯著的增加，但是隨著minSupp的增加，改進(jìn)算法的效果將會逐漸降低，這是因?yàn)楫?dāng)minSupp足夠大時(shí)，規(guī)則數(shù)量已經(jīng)大大減少，規(guī)則基本已經(jīng)具有高質(zhì)量，所以調(diào)整就變得困難和不必要。例如，在圖3中，minSupp為0.062 5時(shí)，改進(jìn)后的算法多得到了114條規(guī)則，但是，當(dāng)minSupp上升到0.087 5時(shí)，改進(jìn)算法只多得到了17條規(guī)則。

再使用規(guī)則質(zhì)量評價(jià)指標(biāo)φ5、φ10、φn2這3個(gè)度量來進(jìn)一步驗(yàn)證改進(jìn)算法。表1中收集的是在最小置信度為0.8，最小確定性因子為0.7，最小支持度不同的情況下，分別使用兩種算法挖掘出的包含有DIRECTION屬性的規(guī)則的φ5、φ10、φn2這3個(gè)度量的值。從表1中可以看出，在最小支持度小于0.1時(shí)，改進(jìn)后的算法得出的3個(gè)度量的值總是超過改進(jìn)前算法的。

圖2不含擴(kuò)散方向的規(guī)則數(shù)量Fig.2 Number of rules without diffusion direction

圖3包含有擴(kuò)散方向的規(guī)則數(shù)量Fig.3 Number of rules with diffusion direction

表1規(guī)則質(zhì)量Tab.1 Rule quality

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

從圖2和圖3可以看出，最小支持度小于0.075時(shí)，改進(jìn)算法挖掘出的規(guī)則數(shù)量過多，規(guī)則中含有大量冗余規(guī)則，而最小支持度大于0.075時(shí)，規(guī)則數(shù)量過少，很多有價(jià)值的規(guī)則被刪除，會影響最終結(jié)論，所以取最小支持度設(shè)為0.075時(shí)挖掘出的規(guī)則進(jìn)行研究最合適。部分挖掘出的規(guī)則如表2所示。根據(jù)挖掘出的關(guān)聯(lián)結(jié)果，得到以下結(jié)論。

1）由規(guī)則1可以看出,PR和PRA都為陰性的患者在樣本中的比例為7.72%，全部擴(kuò)散成結(jié)直腸癌。

2）由規(guī)則2可以看出,T_VALUE的值為T1且處于老年（69歲以上）的患者在樣本中的比例為9.28%，其中80.02%的患者擴(kuò)散成結(jié)直腸癌。

3）由規(guī)則3可以看出,ER、PRA和ERA的值都為陰性的患者在樣本中的比例為7.51%，其中84.29%的患者擴(kuò)散成女性生殖系統(tǒng)癌。

4）由規(guī)則4可以看出,ER、PR為陰性且處于老年的患者在樣本中的比例為7.76%，其中82.08%的患者擴(kuò)散成結(jié)直腸癌。

5）由規(guī)則5可以看出,ER、PR為陰性，ERA為陽性且T_VALUE的值為T1的患者在樣本中的比例為9.86%，其中95.76%的患者擴(kuò)散成呼吸道系統(tǒng)癌。

6）由規(guī)則4、5可以看出,若患者ER和PR都為陰性，乳腺癌有較大概率發(fā)生擴(kuò)散。醫(yī)院給患者制定治療方案時(shí)，可以根據(jù)這兩項(xiàng)指標(biāo)的檢測值對治療方案進(jìn)行調(diào)整。

7）由規(guī)則2、4可以看出，若患者處于老年，則乳腺癌有較大概率發(fā)生擴(kuò)散，醫(yī)院在對老年乳腺癌患者進(jìn)行治療時(shí)需注意。

表2關(guān)聯(lián)規(guī)則結(jié)果Tab.2 Results of association rules

4 結(jié)語

本文主要研究了改進(jìn)關(guān)聯(lián)規(guī)則算法在乳腺癌擴(kuò)散預(yù)測中的應(yīng)用，引入模糊集理論對Apriori算法進(jìn)行改進(jìn)，使用Apriori和改進(jìn)算法對乳腺癌患者就診記錄進(jìn)行實(shí)驗(yàn)處理，并比較了算法的性能。通過對乳腺癌患者就診數(shù)據(jù)進(jìn)行挖掘，得到乳腺癌擴(kuò)散和各個(gè)參數(shù)之間的內(nèi)在聯(lián)系，挖掘出有效的規(guī)則，為乳腺癌患者的臨床治療提供幫助。