基于加權(quán)螢火蟲算法的關(guān)聯(lián)規(guī)則特征挖掘

吳辰文, 劉文祎， 馬國娟， 閆光輝

(蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070)

當(dāng)今醫(yī)院存有大量的醫(yī)療數(shù)據(jù),在醫(yī)院診治患者過程中獲得了大量的診斷、病歷數(shù)據(jù)，通過對這些數(shù)據(jù)進(jìn)行挖掘分析，可以得出很多有用的信息，這些信息可以提升醫(yī)院的診斷水平以及服務(wù)質(zhì)量。醫(yī)院的醫(yī)療信息不是僅局限于短期的數(shù)據(jù)信息，而是長達(dá)數(shù)年或是十多年的數(shù)據(jù)積累，因此如此大并且時(shí)間跨度較長的數(shù)據(jù)中會(huì)有很多有用的信息以待發(fā)現(xiàn)。子宮癌的危害性較大，不論是發(fā)病率還是死亡率都十分高，因此通過藥物治療子宮癌變得十分重要。

針對關(guān)聯(lián)規(guī)則這一問題的解決方法有很多種，其中由Agrawal等人提出的改進(jìn)算法應(yīng)用最為廣泛，但算法挖掘效率低，而且頻繁的掃描事務(wù)數(shù)據(jù)庫極大地增加了系統(tǒng)的負(fù)擔(dān)，不僅浪費(fèi)時(shí)間并且浪費(fèi)空間[1]。文獻(xiàn)[2]提出采用遺傳算法來改進(jìn)Apriori算法，它引入興趣度，對生成規(guī)則進(jìn)行篩選，刪除其中的虛假規(guī)則，使得結(jié)論更具說服力，但其沒有對算法的運(yùn)行效率進(jìn)行提升。文獻(xiàn)[3]提出了通過矩陣來壓縮事務(wù)并相乘的改進(jìn)算法，該算法通過用二維矩陣來表示數(shù)據(jù)庫數(shù)據(jù)，再將數(shù)據(jù)二進(jìn)制矩陣與輔助矩陣相乘得到頻繁項(xiàng)目集。但這種方法需要很多矩陣相乘計(jì)算的內(nèi)容，致使時(shí)間效率不高。文獻(xiàn)[4]提出基于采樣思想的關(guān)聯(lián)規(guī)則挖掘算法，首先從數(shù)據(jù)庫中隨機(jī)抽取一部分?jǐn)?shù)據(jù)為樣本數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘進(jìn)而得到一些強(qiáng)關(guān)聯(lián)規(guī)則，再用其他所有數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘驗(yàn)證算法是否正確。該方法的優(yōu)勢在于可以快速挖掘出頻繁項(xiàng)集，但因?yàn)槭请S機(jī)抽取數(shù)據(jù)，所以最終得出的結(jié)果與實(shí)際情況相差很大，效果不好。因此本文提出將加權(quán)螢火蟲算法應(yīng)用到Apriori關(guān)聯(lián)規(guī)則挖掘算法中，通過螢火蟲算法的良好性能，提高醫(yī)療大數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘的效率。

1 關(guān)聯(lián)規(guī)則算法概述

1.1 關(guān)聯(lián)規(guī)則

兩個(gè)或多個(gè)變量之間的取值存在某種規(guī)律性，就稱為關(guān)聯(lián)?，F(xiàn)在已經(jīng)有多種關(guān)聯(lián)規(guī)則算法，其中較為經(jīng)典和使用率較高的是Apriori算法、FP-growth算法等。關(guān)聯(lián)規(guī)則算法的意義是：可以通過關(guān)聯(lián)規(guī)則得出的結(jié)論來調(diào)整不同事物之間的搭配或聯(lián)系，從而提升效率。

1.2 Apriori算法簡介

關(guān)聯(lián)規(guī)則挖掘可以發(fā)現(xiàn)數(shù)據(jù)中項(xiàng)目或?qū)傩灾g的有用聯(lián)系，而這些聯(lián)系是預(yù)先未知的，Apriori算法是Agrawal和Strikant在1994年提出的第一個(gè)關(guān)聯(lián)規(guī)則挖掘算法，能夠較好地挖掘出數(shù)據(jù)中的規(guī)則[5-7]。關(guān)聯(lián)規(guī)則挖掘規(guī)則的本質(zhì)是在所有頻繁項(xiàng)集中發(fā)現(xiàn)符合最小置信度的規(guī)則，所以一般來說，挖掘關(guān)聯(lián)規(guī)則主要分為兩部分：找出頻繁項(xiàng)集和找出所有強(qiáng)關(guān)聯(lián)規(guī)則[8]。

挖掘關(guān)聯(lián)規(guī)則的重點(diǎn)是生成所有頻繁項(xiàng)集，主要方法從1-項(xiàng)集開始挖掘出通過最小支持度判斷產(chǎn)生的1-項(xiàng)頻繁集，繼續(xù)對1-項(xiàng)頻繁集進(jìn)行組合產(chǎn)生2-項(xiàng)候選項(xiàng)集，再進(jìn)行最小支持度判斷生成2-項(xiàng)頻繁項(xiàng)集，按照這種方法類推，直到得出最大頻繁項(xiàng)集[9]。Apriori算法存在的性質(zhì)是：一個(gè)頻繁項(xiàng)集的任意子集也都是頻繁項(xiàng)集，除空集之外。

假如數(shù)據(jù)庫中包含有N項(xiàng)事務(wù)，其中A,B為數(shù)據(jù)庫中不相交的兩個(gè)項(xiàng)集，則支持度support(A)指的是項(xiàng)集A中出現(xiàn)的事務(wù)數(shù)占總事務(wù)數(shù)N的比值；當(dāng)支持度大于某一給定閾值時(shí)，既稱其為頻繁項(xiàng)集；包含規(guī)則X-Y的支持度support(A→B)其含義為當(dāng)A和B同時(shí)出現(xiàn)的事務(wù)數(shù)占事務(wù)總數(shù)N的比值；置信度confident(A→B)的含義為A→B的支持度support(A→B)與項(xiàng)集A的支持度support(A)的比值，當(dāng)此比值大于給定閾值時(shí)此規(guī)則為強(qiáng)關(guān)聯(lián)規(guī)則，強(qiáng)關(guān)聯(lián)規(guī)則的含義是項(xiàng)集A出現(xiàn)的情況下項(xiàng)集B也出現(xiàn)的概率很高，提升度指的是當(dāng)A出現(xiàn)時(shí)對B也出現(xiàn)的概率的提升，用來判斷實(shí)際價(jià)值，即當(dāng)使用規(guī)則兩者同時(shí)出現(xiàn)與只有一項(xiàng)事物出現(xiàn)頻率是否提升。

規(guī)則A→B的支持度與置信度提升度公式表示如下：

(1)

(2)

式中，σ(A)表示事務(wù)A出現(xiàn)的頻數(shù)；σ(A→B)表示規(guī)則A→B出現(xiàn)的頻數(shù)。

(3)

提升度大于1為規(guī)則有效；小于1則規(guī)則無效。

2 螢火蟲算法概述

2.1 螢火蟲算法仿生原理

螢火蟲算法是模擬自然界中螢火蟲發(fā)光行為的物理學(xué)意義，通過螢火蟲自身發(fā)光的特性按照發(fā)光相對強(qiáng)度來搜索一定范圍內(nèi)的其他螢火蟲，并且根據(jù)距離的遠(yuǎn)近向附近區(qū)域內(nèi)位置較好的螢火蟲靠攏，進(jìn)而實(shí)現(xiàn)位置的更新[10]。

算法中螢火蟲的移動(dòng)由兩個(gè)要素決定：自身亮度和吸引度。其中，螢火蟲自身的亮度由其所在位置的目標(biāo)值決定，位置越好的螢火蟲越亮。吸引度與亮度相關(guān)，越亮的螢火蟲吸引度越大，吸引度大的螢火蟲會(huì)吸引吸引度較小的螢火蟲向其移動(dòng)，大多數(shù)螢火蟲會(huì)聚集在搜索范圍內(nèi)最亮的螢火蟲附近。亮度以及吸引度都與螢火蟲間的距離成反比，兩只螢火蟲之間的相對亮度以及吸引度會(huì)隨著距離的增加而減弱[11]。

2.2 螢火蟲算法的數(shù)學(xué)定義

定義1：亮度。

I=I0×exp(-γrij)

(4)

式中,I0為初始熒光亮度,即在光源處的熒光亮度。

定義2：吸引力。

(5)

式中，β0為最大吸引力，即光源處的吸引力，通常情況下β0取值為1；m值大多數(shù)情況下取2；參數(shù)γ是空間中介質(zhì)對光的吸收率，常取γ∈[0.1，10]；rij為螢火蟲i到j(luò)的笛卡爾距離：

(6)

式中，d為變量的維數(shù)。吸引力函數(shù)可以為任何一種單調(diào)遞減函數(shù)[12]。

定義 3：位置更新公式。

假設(shè)螢火蟲i比螢火蟲j亮度大，則i向j移動(dòng)的位置更新公式為

xi=xi+β×(xj-xj)+α×(rand-1/2)

(7)

式中，xi,xj為螢火蟲i，j所處的位置；α為隨機(jī)步長因子，即螢火蟲每次移動(dòng)的步長，取值范圍為[0，1]；rand為[0，1]上服從均勻分布的隨機(jī)因子，α×(rand-1/2)的作用是增加螢火蟲移動(dòng)的擾動(dòng)項(xiàng)，防止算法陷入局部最優(yōu)解[13]。螢火蟲通過多次移動(dòng)后，所有個(gè)體都將移動(dòng)到搜索范圍內(nèi)亮度最大的螢火蟲位置上，最終實(shí)現(xiàn)尋優(yōu)。

2.3 算法的偽代碼

Start初始化。

設(shè)定參數(shù)γ，βο，α，G(最大迭代次數(shù))，n；初始化螢火蟲位置x(i)，(i=1，2，…，n)；初始化螢火蟲亮度I(i)，(i=1，2，…，n)。

迭代過如下：

Whileg≤G

Fori=1:n-1

Forj=i+1:n

IfI(j)

End If;

End Forj;

End Fori;

g=g+1;

End While

End Start

3 基于加權(quán)螢火蟲算法的關(guān)聯(lián)規(guī)則挖掘

3.1 YHC-Apriori算法設(shè)計(jì)

因?yàn)锳priori算法要反復(fù)求每個(gè)數(shù)據(jù)項(xiàng)的支持度，所以算法效率低，而螢火蟲算法可以根據(jù)數(shù)據(jù)項(xiàng)的支持度大小來快速求出數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián)度。

根據(jù)已有數(shù)據(jù)庫信息，掃描每一個(gè)事務(wù)，計(jì)算每一事物的支持度，再設(shè)定參數(shù)x為最小支持度，先將所有小于最小支持度的事務(wù)刪除，這樣不僅降低了由于數(shù)據(jù)過多導(dǎo)致的系統(tǒng)資源占用過多的弊端，而且篩選掉了支持度較小的數(shù)據(jù)，使得出的結(jié)論更有說服力。螢火蟲的亮度I設(shè)置為數(shù)據(jù)的支持度，螢火蟲根據(jù)數(shù)據(jù)支持度的大小判斷哪個(gè)數(shù)據(jù)集的吸引力β更大，并開始選擇向著吸引力更大的數(shù)據(jù)集移動(dòng)，螢火蟲的運(yùn)動(dòng)軌跡被記錄下來，當(dāng)至少有兩只螢火蟲近似位于同一位置時(shí)，說明二者之間存在較強(qiáng)關(guān)聯(lián)規(guī)則，將該信息記錄到關(guān)聯(lián)規(guī)則表中，以此類推直到所有螢火蟲遍歷完成停止移動(dòng)，則可得出所有關(guān)聯(lián)規(guī)則信息。

3.2 加權(quán)螢火蟲位置更新

一個(gè)優(yōu)化算法的效率在于對尋找一個(gè)新的最優(yōu)解的探索和開發(fā)。標(biāo)準(zhǔn)螢火蟲算法在移動(dòng)步驟中同時(shí)實(shí)現(xiàn)了對尋找一個(gè)最優(yōu)解的探索和開發(fā)[6]。自適應(yīng)權(quán)重被添加到螢火蟲算法的螢火蟲移動(dòng)步驟中以增強(qiáng)算法的效率。使用自適應(yīng)權(quán)重的螢火蟲運(yùn)動(dòng)由式(8)給出：

Xnew(t+1)=W(t)Xold+β0exp(-γcm)(xj-xi)+αεi

(8)

式中，Xnew(t+1)為i螢火蟲經(jīng)過t+1次運(yùn)動(dòng)后的位置;α為隨機(jī)化參數(shù)，值在0和1之間；εi是隨機(jī)數(shù)向量;W(t)是慣性權(quán)重，由式(9)給出。

(9)

式中，Wmax和Wmin是迭代t中的最大和最小權(quán)重；MaxG是最大迭代次數(shù)。

3.3 具體算法

首先掃描一次基準(zhǔn)數(shù)據(jù)庫中的所有事物,從而建立每只螢火蟲的支持度信息表。

輸入：數(shù)據(jù)項(xiàng)集合。

輸出：強(qiáng)關(guān)聯(lián)規(guī)則列表Rule。

① 初始設(shè)定所有帶有支持度的螢火蟲，即數(shù)據(jù)項(xiàng)，都沒有移動(dòng)過；

② 根據(jù)最小支持度，首先排除支持度小于最小支持度的數(shù)據(jù)；

③ 螢火蟲開始移動(dòng)，根據(jù)螢火蟲亮度的大小來判定螢火蟲之間的相對移動(dòng)；

④ 記錄螢火蟲移動(dòng)的路線，當(dāng)有至少兩只螢火蟲近似位于同一位置時(shí)，生成相應(yīng)的關(guān)聯(lián)規(guī)則并將生成的規(guī)則放入列表Rule中，以此類推得出總體的關(guān)聯(lián)規(guī)則列表；

⑤ 當(dāng)所有螢火蟲停止移動(dòng)則迭代結(jié)束；

⑥ 輸出最大頻繁項(xiàng)集T;

⑦ 輸出螢火蟲關(guān)聯(lián)規(guī)則算法挖掘的關(guān)聯(lián)規(guī)則。

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

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

實(shí)驗(yàn)數(shù)據(jù)來源于某地婦幼保健院的子宮癌完整數(shù)據(jù)，首先對數(shù)據(jù)進(jìn)行清洗，對數(shù)據(jù)結(jié)果沒有影響的屬性進(jìn)行刪減，例如：患者住院天數(shù)，患者編號，患者年齡等，另外對于數(shù)據(jù)中缺失部分進(jìn)行填充。

4.2 實(shí)驗(yàn)平臺(tái)及結(jié)果對比

本實(shí)驗(yàn)在Windows 7環(huán)境下實(shí)施,R語言版本為3.4.2，對比算法為Apriori，將數(shù)據(jù)集劃分為兩個(gè)不同大小等級，一個(gè)是1000數(shù)據(jù)，另一個(gè)是10000數(shù)據(jù)。實(shí)驗(yàn)結(jié)果如圖1、圖2所示。

圖1 事務(wù)集為10000時(shí)兩種方法時(shí)間效率比較

圖2 事務(wù)集為1000時(shí)兩種方法時(shí)間效率比較

取事務(wù)集個(gè)數(shù)為1000，10000，最小支持度取2%，最小置信度取45%，將改進(jìn)算法YHC-Apriori算法與Apriori算法進(jìn)行實(shí)驗(yàn)對比分析，從圖1、圖2可知，采用螢火蟲優(yōu)化算法的效率更高，當(dāng)運(yùn)行時(shí)間相同時(shí)，改進(jìn)算法得到的頻繁項(xiàng)集更多，當(dāng)生成頻繁項(xiàng)集數(shù)量相同時(shí)，改進(jìn)算法用的時(shí)間更短，證明用螢火蟲算法改進(jìn)的Apriori算法運(yùn)行效率更高，并且當(dāng)數(shù)據(jù)量越多時(shí)改進(jìn)算法的效率提升會(huì)更加顯著。醫(yī)生在通過改進(jìn)的關(guān)聯(lián)規(guī)則算法對大量的臨床數(shù)據(jù)進(jìn)行分析時(shí)更能得出有用的用藥信息。

4.3 螢火蟲Apriori算法穩(wěn)定性測試

本文選擇UCI上4種數(shù)據(jù)集來測試螢火蟲Apriori算法的準(zhǔn)確性以及穩(wěn)定性，數(shù)據(jù)集分別為乳腺癌數(shù)據(jù)(Breast Cancer)、甲狀腺癌數(shù)據(jù)( Thyroid Cancer)、葡萄酒質(zhì)量數(shù)據(jù)(Wine Quality)、肺癌數(shù)據(jù)(Lung Cancer)，4種數(shù)據(jù)集信息如表1所示。實(shí)驗(yàn)結(jié)果如表2所示。

表1 數(shù)據(jù)集信息

表2 算法時(shí)間效率對比表

由表2中信息可知,改進(jìn)的螢火蟲Apriori算法時(shí)間效率都要高于Apriori算法，證明螢火蟲Apriori算法適用于各種不同類型的數(shù)據(jù)集，其穩(wěn)定性更加出色。

4.4 子宮癌患者用藥分析

通過對患者用藥數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)一些子宮癌患者常用藥規(guī)律，其主要關(guān)聯(lián)藥品為奧美拉唑鈉、輔酶A針、頭孢呋辛鈉、復(fù)方聚乙二醇電解質(zhì)散、慶大霉素注射液、硝苯地平控釋片、鈉鉀鎂鈣葡萄糖、維生素B6，其中生成的關(guān)聯(lián)規(guī)則如表3所示。

表3 用藥關(guān)聯(lián)規(guī)則

通過分析表3可得出一些有用的用藥關(guān)聯(lián)規(guī)則，例如：有6.6%子宮瘤患者同時(shí)用到奧美拉唑鈉，硝苯地平控釋片兩種藥物，用奧美拉唑鈉藥物的患者有73.1%的概率用到硝苯地平控釋片；有5.1%的患者同時(shí)用輔酶A針和鈉鉀鎂鈣葡萄糖兩種藥物，用輔酶A針?biāo)幬锏幕颊哂?1.1%的概率用到鈉鉀鎂鈣葡萄糖。當(dāng)醫(yī)生開藥方時(shí)奧美拉唑鈉與硝苯地平緩釋片可一同寫進(jìn)藥方，輔酶A針與鈉鉀鎂鈣葡萄糖可一同寫進(jìn)藥方，以此類推關(guān)聯(lián)度大的藥品可以結(jié)合使用。

5 結(jié)束語

本文首先介紹了螢火蟲算法和關(guān)聯(lián)規(guī)則算法的特點(diǎn)和研究現(xiàn)狀。目前很多學(xué)者針對關(guān)聯(lián)規(guī)則提出了很多較好的算法，但也都存在著一些問題，本文提出一種基于加權(quán)螢火蟲算法的關(guān)聯(lián)規(guī)則挖掘算法，與之前經(jīng)典的算法比較，在算法運(yùn)行效率上有明顯的提升。同時(shí)本文將患者用藥情況進(jìn)行挖掘得出一些關(guān)聯(lián)性較高的規(guī)則，其可以為醫(yī)院醫(yī)師使用藥物進(jìn)行科學(xué)的統(tǒng)計(jì)分析，方便醫(yī)生對藥物進(jìn)行合理的使用。

由于關(guān)聯(lián)規(guī)則挖掘生成的規(guī)則數(shù)較多，在大量的規(guī)則中發(fā)現(xiàn)有用的信息還需要花費(fèi)一些額外的時(shí)間和精力，因此在同樣最小支持度參數(shù)情況下，能生成較少的但更有價(jià)值的規(guī)則就更能夠提升算法的效率，這是接下來要研究的方向。