基于改進(jìn)FP-Growth算法的基因-疾病關(guān)系自動(dòng)提取的應(yīng)用研究

王明令, 王 蘋, 紀(jì)懷猛

(陽(yáng)光學(xué)院人工智能學(xué)院，福建福州 350015)

計(jì)算機(jī)技術(shù)為數(shù)據(jù)存儲(chǔ)與搜索提供了便利，使以往很難被利用的海量數(shù)據(jù)能經(jīng)由數(shù)據(jù)分析、數(shù)據(jù)挖掘的方式，發(fā)現(xiàn)其中潛藏的有意義的規(guī)則和信息.這樣的大數(shù)據(jù)分析應(yīng)用被廣泛運(yùn)用在許多領(lǐng)域.其中文本數(shù)據(jù)挖掘的方式能在社區(qū)意見、產(chǎn)品評(píng)論、輿情預(yù)警、客戶分群、熱點(diǎn)預(yù)測(cè)、醫(yī)療科研等方面提供信息挖掘與規(guī)則發(fā)現(xiàn).諸如在傳媒情緒研究領(lǐng)域，學(xué)者王鵬為解決個(gè)體生涯輔導(dǎo)的準(zhǔn)確性，結(jié)合生活設(shè)計(jì)范式提出一種將文本挖掘和項(xiàng)目反應(yīng)理論相結(jié)合的新的生涯適應(yīng)力測(cè)評(píng)方法[1]；學(xué)者王超等研究中文詞語(yǔ)銜接的概率語(yǔ)言模型，在短文本數(shù)據(jù)挖掘中針對(duì)文本語(yǔ)義進(jìn)行量化分析[2]；學(xué)者鐘智錦等詳細(xì)總結(jié)了文本挖掘技術(shù)在新聞傳播學(xué)科中的使用場(chǎng)景和特征等[3].在金融運(yùn)行領(lǐng)域，學(xué)者孟志青等利用文本挖掘技術(shù)構(gòu)建金融領(lǐng)域的情感詞典，通過(guò)貝葉斯方法將其合成網(wǎng)絡(luò)情緒指數(shù)，應(yīng)用ARMA-GARCH族模型分別刻畫網(wǎng)絡(luò)情緒與個(gè)股收益序列[4]；學(xué)者吳寅愷等研究使用文本挖掘和網(wǎng)絡(luò)爬蟲技術(shù)從報(bào)刊文章中提取金融風(fēng)險(xiǎn)的信息[5].在電商推廣領(lǐng)域，學(xué)者崔永生通過(guò)對(duì)在線評(píng)論的文本挖掘，了解消費(fèi)者真正的購(gòu)物需求[6].

生物信息學(xué)是近年來(lái)的研究熱點(diǎn)之一，它綜合了計(jì)算機(jī)科學(xué)、信息技術(shù)與生物學(xué)研究的數(shù)據(jù)與技術(shù)手段，對(duì)生物學(xué)的研究數(shù)據(jù)——如基因序列、蛋白質(zhì)序列等——進(jìn)行分析與加工，得出有價(jià)值的信息與規(guī)則.學(xué)者唐金鳳等利用文本挖掘技術(shù)分析抗生素后效應(yīng)(PAE), 為抗生素的合理應(yīng)用提供參考[7]；學(xué)者甄曙光等利用文本數(shù)據(jù)挖掘技術(shù)研究中醫(yī)臨床診療數(shù)字化、文本向量呈像，試圖得出中醫(yī)辨證論治及理法方藥的規(guī)律性[8]；學(xué)者劉燕等對(duì)癌癥基因組數(shù)據(jù)進(jìn)行挖掘，對(duì)特異癌癥基因加以注釋并實(shí)現(xiàn)可視化展示[9]；學(xué)者宋嘉麒等以遺傳模型對(duì)基因-疾病關(guān)聯(lián)進(jìn)行研究，在實(shí)例中比較了不同參數(shù)先驗(yàn)信息對(duì)合并效應(yīng)量的影響[10]；在學(xué)者宋嘉麒等人后續(xù)的研究中，繼續(xù)以貝葉斯模型對(duì)基因-疾病關(guān)聯(lián)進(jìn)行研究[11]；學(xué)者李雪探討基于云平臺(tái)提高基因病診斷率的診斷模式[12].

其中對(duì)基因序列的研究是生物信息學(xué)的一項(xiàng)重點(diǎn).經(jīng)由成熟的醫(yī)療技術(shù)能夠測(cè)定與獲取生物的基因序列數(shù)據(jù)，并使用計(jì)算機(jī)技術(shù)將基因序列以多個(gè)線性序列編碼的方法來(lái)表示染色體上攜帶的數(shù)據(jù).這些對(duì)醫(yī)療研究與生命學(xué)研究等都是極有價(jià)值的信息數(shù)據(jù).

1 基因-疾病關(guān)聯(lián)

現(xiàn)代的醫(yī)學(xué)研究發(fā)現(xiàn)，人類基因與疾病之間存在一定的因果關(guān)聯(lián).某一種或多種基因的存在預(yù)兆著一種或多種疾病發(fā)作的可能性，基因與疾病之間呈現(xiàn)多對(duì)多的復(fù)雜關(guān)聯(lián)性.如果醫(yī)療工作者能深入了解基因與疾病之間的關(guān)聯(lián)性，能從病體表征上預(yù)先察知發(fā)病的可能性，就能對(duì)某些疾病做到良好的治療作用，甚至做好預(yù)防工作.

傳統(tǒng)的生物學(xué)實(shí)驗(yàn)統(tǒng)計(jì)分析存在效率不高的缺陷.而且基因和疾病的種類都非常復(fù)雜，僅僅依靠實(shí)驗(yàn)室測(cè)試的方式進(jìn)行關(guān)聯(lián)關(guān)系建立或排除工作量較大.如果有一個(gè)預(yù)測(cè)目標(biāo)，來(lái)進(jìn)行基因與疾病之間關(guān)聯(lián)性的實(shí)驗(yàn)，就能更好地提高醫(yī)療科研的工作效率和準(zhǔn)確性.人工智能的數(shù)據(jù)分析是一個(gè)很好的辦法，利用數(shù)據(jù)挖掘的關(guān)聯(lián)規(guī)則分析挖掘，能發(fā)現(xiàn)基因和疾病數(shù)據(jù)的特性和關(guān)聯(lián)性強(qiáng)弱.

已知的生物科學(xué)與醫(yī)療科研工作都累積了大量的基因序列數(shù)據(jù)和疾病信息.其中，生物科學(xué)研究者為現(xiàn)有的基因序列做了較好的結(jié)構(gòu)化數(shù)據(jù)表示，并大量公開地在網(wǎng)絡(luò)上發(fā)布，使針對(duì)基因序列的統(tǒng)計(jì)研究與特征描述能更方便地進(jìn)行.而針對(duì)疾病信息的結(jié)構(gòu)化數(shù)據(jù)較少，一方面因?yàn)榧膊〉谋碚餍问竭^(guò)于復(fù)雜，使對(duì)疾病的結(jié)構(gòu)化數(shù)據(jù)描述方式?jīng)]能很好地統(tǒng)一；另一方面是因?yàn)殚L(zhǎng)期以來(lái)人工、手工記錄的大量醫(yī)療數(shù)據(jù)沒能被很好地利用的緣故.

可見要充分利用現(xiàn)有醫(yī)療數(shù)據(jù)進(jìn)行基因與疾病關(guān)聯(lián)的研究，首先要做好醫(yī)療數(shù)據(jù)的結(jié)構(gòu)化.本文所采取的醫(yī)療數(shù)據(jù)來(lái)自武漢某醫(yī)院神經(jīng)內(nèi)科的病歷，經(jīng)由前期數(shù)據(jù)錄入、數(shù)據(jù)清洗、關(guān)鍵詞生成、主題提取等工作，形成了可供進(jìn)一步挖掘基因-疾病關(guān)聯(lián)的醫(yī)療數(shù)據(jù).本文應(yīng)用的基因數(shù)據(jù)使用網(wǎng)絡(luò)公開的NCBI數(shù)據(jù)庫(kù)的子庫(kù)PubMed數(shù)據(jù)庫(kù).

2 文本挖掘與關(guān)聯(lián)規(guī)則FP-Growth算法

在文本挖掘的模式中，TF-IDF是經(jīng)典的計(jì)算模式.其中TF代表某個(gè)關(guān)鍵詞的詞頻，也就是該關(guān)鍵詞在相關(guān)系列文檔中出現(xiàn)的次數(shù)；IDF代表提及某關(guān)鍵詞存在的文檔數(shù)量在總的文檔數(shù)量中所占的比例的倒數(shù).

即:

TF=關(guān)鍵詞k在文檔中出現(xiàn)的次數(shù)

TF與IDF參數(shù)能很好地說(shuō)明關(guān)鍵詞與文檔之間的關(guān)聯(lián)緊密度.假設(shè)當(dāng)前的TF關(guān)鍵詞為基因，IDF為疾病主題數(shù)據(jù)集.當(dāng)TF詞頻較大時(shí)，說(shuō)明多種疾病病歷文本描述與TF關(guān)鍵詞基因相關(guān)，也就是該基因?qū)?yīng)了多種關(guān)于疾病的描述.當(dāng)IDF較大時(shí)，說(shuō)明提及該關(guān)鍵詞的文檔數(shù)較少.但是IDF較大也可能是在疾病文獻(xiàn)中對(duì)該基因的描述較少.但是當(dāng)IDF較大時(shí)，該基因關(guān)鍵詞與對(duì)應(yīng)文檔的關(guān)聯(lián)性更強(qiáng).當(dāng)TF和IDF聯(lián)合使用時(shí)，能表現(xiàn)出關(guān)鍵詞與文檔之間關(guān)聯(lián)的強(qiáng)弱.

將關(guān)鍵詞k表示為kx，文檔f表示為fy，關(guān)鍵詞k在文檔f中出現(xiàn)的次數(shù)表示為nx, y，文檔集合中文檔數(shù)表示為M.則:

(2.1)

(2.2)

(TF-IDF)x, y=TFx, y*IDFx

(2.3)

當(dāng)比較基因k與病歷文檔f之間的關(guān)聯(lián)時(shí)，運(yùn)用TF-IDF模式能有效發(fā)現(xiàn)基因與疾病之間的關(guān)聯(lián).在運(yùn)用TF-IDF模式時(shí)，關(guān)鍵詞出現(xiàn)的詞頻是一個(gè)重要的參數(shù)，也就是說(shuō)挖掘關(guān)鍵詞對(duì)應(yīng)的頻繁項(xiàng)是重要的研究?jī)?nèi)容.數(shù)據(jù)挖掘的關(guān)聯(lián)規(guī)則算法正是通過(guò)挖掘頻繁項(xiàng)來(lái)確認(rèn)兩個(gè)項(xiàng)之間的關(guān)聯(lián)度強(qiáng)弱.

FP-Growth算法是由經(jīng)典Apriori算法改進(jìn)而來(lái)的.Apriori算法在挖掘頻繁項(xiàng)時(shí)會(huì)生成大量候選集，效率較低.FP-Growth算法只需要在挖掘過(guò)程中掃描數(shù)據(jù)集兩次，通過(guò)遞歸演算FP-tree子項(xiàng)頻次的方式，剔除頻次較低(關(guān)聯(lián)度低)的子項(xiàng)，最終形成單一的路徑，效率較高.一個(gè)FP-Growth算法的流程如圖1所示.

FP-Growth算法構(gòu)造FP-tree來(lái)存儲(chǔ)項(xiàng)的頻次，每個(gè)項(xiàng)以路徑的方式存儲(chǔ)在FP-tree中.FP-tree在構(gòu)建的過(guò)程中刪除小于最小支持度(最小項(xiàng)出現(xiàn)頻次)的項(xiàng)，留下出現(xiàn)頻次較高的項(xiàng).與其它樹形結(jié)構(gòu)不同，F(xiàn)P-Growth的項(xiàng)可以在一個(gè)FP-tree中出現(xiàn)多次.一個(gè)FP-tree中的項(xiàng)只有在項(xiàng)-頻次完全不同的時(shí)候，才會(huì)分枝.FP-tree節(jié)點(diǎn)表示為一個(gè)項(xiàng)及其在序列中出現(xiàn)的頻次，路徑表示該序列出現(xiàn)的次數(shù).越靠近根節(jié)點(diǎn)的項(xiàng)，其頻次越高.一個(gè)FP-tree通過(guò)鏈接來(lái)連接相似的項(xiàng)，類似于一個(gè)鏈表.一個(gè)FP-tree示例圖如圖2所示.

圖1FP-Growth算法的流程圖

圖2 一個(gè)FP-tree示例圖

3 FP-Growth算法局限與改進(jìn)

FP-Growth算法不需要在構(gòu)建過(guò)程中存儲(chǔ)頻繁項(xiàng)集，所以對(duì)算法空間的利用率較高.但是FP-Growth算法屬于深度優(yōu)先算法，在構(gòu)建的過(guò)程中遞歸地調(diào)用樹結(jié)構(gòu)，形成每一條路徑分枝，這就導(dǎo)致了當(dāng)數(shù)據(jù)集比較大的時(shí)候，為了能生成路徑，F(xiàn)P-Growth算法會(huì)反復(fù)遍歷FP-tree，構(gòu)造數(shù)據(jù)的FP-tree結(jié)構(gòu)會(huì)變得很龐大，對(duì)系統(tǒng)資源的消耗較大，甚至可能導(dǎo)致內(nèi)存溢出.

為了能夠降低FP-tree在構(gòu)建過(guò)程中的內(nèi)存消耗，提高其路徑計(jì)算的并行性是一個(gè)可行的方法.

許多學(xué)者已經(jīng)對(duì)FP-Growth算法的并行優(yōu)化提出了自己的建議，學(xué)者孫鴻艷等基于Map/Reduce并行計(jì)算模型，對(duì)頻繁模式樹的存儲(chǔ)結(jié)構(gòu)進(jìn)行改進(jìn)，并利用HDFS實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)[13]；學(xué)者陸可等基于Spark框架, 通過(guò)對(duì)支持度計(jì)數(shù)和分組過(guò)程的優(yōu)化改進(jìn)了FP-Growth算法[14]；學(xué)者朱顥東等提出的基于Hadoop框架的分布式FP-Growth算法，以實(shí)現(xiàn)海量數(shù)據(jù)的頻繁模式FP挖掘方式[15]；學(xué)者李贊等提出基于FP-growth的前后部項(xiàng)約束關(guān)聯(lián)規(guī)則挖掘算法，關(guān)鍵在于對(duì)用戶感興趣的規(guī)則前后部項(xiàng)進(jìn)行標(biāo)記，構(gòu)成約束條件，能對(duì)事務(wù)集進(jìn)行篩選，壓縮事務(wù)空間[16]；學(xué)者何晴等用哈希頭表代替頭表，通過(guò)合并頻繁模式樹中支持?jǐn)?shù)相同的結(jié)點(diǎn)，壓縮了樹的規(guī)模[17].

本文以粒子群優(yōu)化，提出一種改進(jìn)的FP-Growth算法.改進(jìn)的基本思路分為兩步:

第一步，先將要進(jìn)行分析的數(shù)據(jù)集分成若干塊.這里采用平均分配的切分法，避免隨機(jī)大小的數(shù)據(jù)塊引發(fā)效率不平衡問(wèn)題.切分后的數(shù)據(jù)集小于原數(shù)據(jù)集，因此在分別進(jìn)行遞歸運(yùn)算構(gòu)造FP-tree時(shí)能較好地被載入內(nèi)存.同時(shí)，分塊數(shù)據(jù)集能夠進(jìn)行并行構(gòu)造操作，以提升算法的效率；

第二步，當(dāng)數(shù)據(jù)集被分塊操作之后，顯然進(jìn)入路徑計(jì)算的并行構(gòu)建階段.針對(duì)并行優(yōu)化的算法有很多，這里采用粒子群優(yōu)化算法.

粒子群優(yōu)化算法(PSO，Particle Swarm Optimization)是一種并行算法，源于對(duì)大規(guī)模外出的鳥群覓食方式的模仿.粒子群優(yōu)化算法假設(shè)每一只外出在搜索空間覓食的鳥兒就是一個(gè)粒子，它對(duì)應(yīng)每個(gè)問(wèn)題的優(yōu)化解.鳥兒粒子在隨機(jī)搜索問(wèn)題最優(yōu)解的時(shí)候，搜索已經(jīng)確認(rèn)離食物(最優(yōu)解)最接近的附近區(qū)間.每個(gè)鳥兒粒子的屬性表示為由優(yōu)化函數(shù)所決定的一個(gè)適應(yīng)值，并且?guī)в幸粋€(gè)決定粒子下一步搜索方向和距離的速度.當(dāng)鳥兒粒子初始化時(shí)，是一群隨機(jī)的鳥兒粒子群，在每一次迭代過(guò)程中，個(gè)體鳥兒粒子隨時(shí)向整個(gè)鳥群共享自己的信息，以幫助其它鳥兒粒子調(diào)整更新自己的狀態(tài).用于更新個(gè)體鳥兒粒子的參數(shù)有兩個(gè)，其中一個(gè)參數(shù)是個(gè)體鳥兒粒子本身所找到的最優(yōu)解，即個(gè)體極值；另一個(gè)參數(shù)是個(gè)體鳥兒粒子共享信息后，整個(gè)鳥群當(dāng)前找到的最優(yōu)解，即全局極值.隨著迭代運(yùn)動(dòng)的繼續(xù)，粒子群體在解空間中由隨機(jī)、無(wú)序的初始化狀態(tài)，慢慢進(jìn)化，最終得到最優(yōu)解.

設(shè)同時(shí)有n個(gè)鳥兒粒子在D維搜索空間中搜索飛行，在某一時(shí)刻n，鳥兒粒子i有位置xi、飛行速度vi、個(gè)體最優(yōu)解極值pi、當(dāng)前全局最優(yōu)解極值pg等幾個(gè)參數(shù)，即鳥兒粒子i在搜索過(guò)程中對(duì)應(yīng)的位置Xi、速度Vi、個(gè)體最優(yōu)解極值Pi、當(dāng)前全部鳥兒粒子搜索到的全局最優(yōu)解極值Pg為:

Xi=(xi1,xi2, …,xiD)i=1, 2, …,N

(3.1)

Vi=(vi1,vi2, …,viD)i=1, 2, …,N

(3.2)

Pi=(pi1,pi2, …,piD)i=1, 2, …,N

(3.3)

Pg=(pg1,pg2, …,pgD)i=1, 2, …,N

(3.4)

(3.5)

其中ω為慣性因子，c1和c2為學(xué)習(xí)因子，δ和η為[0, 1]之間的隨機(jī)數(shù).

4 改進(jìn)Fp-Growth算法的基因-疾病關(guān)系提取

基因數(shù)據(jù)集與病歷文本數(shù)據(jù)集都是比較特殊的文本，呈現(xiàn)高度的離散性，適合使用FP-Growth算法進(jìn)行關(guān)聯(lián)規(guī)則挖掘.而粒子群算法也在適合離散的解空間中并發(fā)操作，優(yōu)化最優(yōu)解的查找.以粒子群算法優(yōu)化FP-Growth算法在基因-疾病關(guān)系自動(dòng)提取運(yùn)算時(shí)，因?yàn)榛驍?shù)據(jù)集相對(duì)規(guī)范，結(jié)構(gòu)化程度高，所以這里只對(duì)病歷文本數(shù)據(jù)集進(jìn)行數(shù)據(jù)集分塊.利用粒子群算法改進(jìn)的FP-Growth算法的基因-疾病關(guān)系提取過(guò)程圖如圖3所示.

提取過(guò)程包括以下幾步:

第一步，讀取基因數(shù)據(jù)集和疾病文本數(shù)據(jù)集；

第二步，將病歷數(shù)據(jù)集平均分為n塊，減少載入內(nèi)存的負(fù)擔(dān)，做并發(fā)處理之用；

圖3 改進(jìn)的FP-Growth算法的基因-疾病關(guān)系提取過(guò)程圖

第四步，并發(fā)處理的模塊i中，遞歸添加構(gòu)建FP-tree i；

第五步，并發(fā)處理的模塊i中，以粒子群算法優(yōu)化規(guī)則學(xué)習(xí)，迭代地搜索全局最優(yōu)解，加快搜索效率，生成優(yōu)化的樹結(jié)構(gòu)路徑與節(jié)點(diǎn)鏈接；

第六步，并發(fā)處理的模塊i中，生成FP-tree，列舉所有組合i；

第七步，合并FP-tree；

第八步，導(dǎo)出、篩選基因-疾病關(guān)聯(lián)關(guān)系頻繁項(xiàng)，生成規(guī)則集，提取其中有意義、有價(jià)值的信息并解讀.

在合并FP-tree的過(guò)程中，由于并發(fā)操作得到的結(jié)果必然存在頻次相同的節(jié)點(diǎn)，因此對(duì)FP-tree的合并原則主要有:

(1)如果節(jié)點(diǎn)i的子節(jié)點(diǎn)>1，則節(jié)點(diǎn)i不能再進(jìn)行向上的合并操作；

(2)只有相同頻次的節(jié)點(diǎn)(項(xiàng))才能被合并；

(3)合并后的節(jié)點(diǎn)，以合并的所有節(jié)點(diǎn)組合為名.

5 仿真實(shí)驗(yàn)

本文在實(shí)驗(yàn)時(shí)采用NCBI數(shù)據(jù)庫(kù)的子庫(kù)PubMed數(shù)據(jù)庫(kù)，讀取其中的基因序列數(shù)據(jù)，疾病文本數(shù)據(jù)使用武漢某醫(yī)院神經(jīng)內(nèi)科的病歷文本轉(zhuǎn)換而得的主題數(shù)據(jù)集.通過(guò)改進(jìn)的FP-Growth算法對(duì)其進(jìn)行基因-疾病關(guān)系的文本挖掘所得出的規(guī)則集，經(jīng)由專業(yè)醫(yī)生確認(rèn)有較好的相關(guān)性，使用粒子群算法優(yōu)化后，F(xiàn)P-Growth的運(yùn)行效率更是明顯提高.

6 結(jié)論

FP-Growth算法對(duì)疾病相關(guān)文本的挖掘有較好的適應(yīng)性，但FP-Growth算法在數(shù)據(jù)集較大時(shí)，對(duì)內(nèi)存載入有較大的負(fù)擔(dān).本文提出劃分?jǐn)?shù)據(jù)集，以并行的方式生成FP-tree的方法，并由粒子群算法改進(jìn)FP-tree的構(gòu)建，加快了FP-tree的生成.實(shí)驗(yàn)的不足一則在于病歷文本的樣本數(shù)仍然不足，對(duì)驗(yàn)證大數(shù)據(jù)集上的FP-Growth算法的效率仍嫌不足；另一方面則是中文病歷文本的數(shù)據(jù)挖掘準(zhǔn)確性還應(yīng)該繼續(xù)提升，在中文劃分詞組、疾病別名與基因關(guān)聯(lián)關(guān)系、疾病別名與疾病權(quán)威名對(duì)應(yīng)關(guān)系等方面，需要進(jìn)一步的數(shù)據(jù)質(zhì)量提升.這是需要進(jìn)一步改進(jìn)的問(wèn)題.