安瑩 王志娜 陳先來(lái) 劉莉 李忠民 羅熹

摘? ?要：網(wǎng)絡(luò)分析法將潛在的共病關(guān)系預(yù)測(cè)轉(zhuǎn)化為復(fù)雜網(wǎng)絡(luò)上的鏈路預(yù)測(cè)問(wèn)題，而現(xiàn)有的基于相似性度量的鏈路預(yù)測(cè)方法大多僅單一地考慮某一方面的網(wǎng)絡(luò)特征，大大影響了預(yù)測(cè)的準(zhǔn)確性. 使用3個(gè)不同來(lái)源的真實(shí)醫(yī)療數(shù)據(jù)集分別構(gòu)建了相應(yīng)的帶權(quán)疾病網(wǎng)絡(luò)，并通過(guò)對(duì)不同網(wǎng)絡(luò)結(jié)構(gòu)差異性的比較，分析了現(xiàn)有的網(wǎng)絡(luò)相似性度量指標(biāo)的局限性. 在此基礎(chǔ)上，提出了一種新的基于有監(jiān)督分類的鏈路預(yù)測(cè)方法，綜合多種局部和全局相似性指標(biāo)作為輸入特征向量，更為精確地評(píng)估節(jié)點(diǎn)間的相似性，從而實(shí)現(xiàn)潛在共病關(guān)系的有效預(yù)測(cè). 實(shí)驗(yàn)結(jié)果表明，該方法能有效提高共病網(wǎng)絡(luò)中鏈路預(yù)測(cè)的準(zhǔn)確性，并且對(duì)于不同共病網(wǎng)絡(luò)和分類算法均具有較好的穩(wěn)定性和適用性.

關(guān)鍵詞：共病;網(wǎng)絡(luò)分析;監(jiān)督學(xué)習(xí);鏈路預(yù)測(cè)

中圖分類號(hào)：TP399? ? ? ?? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)志碼：A

Prediction of Latent Comorbidity Relationship in Weighted Disease Network

AN Ying1，2?，WANG Zhina1，CHEN Xianlai2，LIU Li2，LI Zhongmin2，LUO Xi3

（1. School of Information Science and Engineering，Central South University，Changsha 410083，China;

2. Institute of Information Security and Big Data，Central South University，Changsha 410083，China;

3. Department of Information Technology，Hunan Police Academy，Changsha 410138，China）

Abstract： Network analysis method transforms the prediction of potential comorbidity relationships into link prediction problems on complex network. However，most existing similarity measurement methods only consider a certain aspect of network characteristics，which greatly affects the accuracy of prediction. In this paper，three weighted disease networks are established using the real medical datasets from different sources. By comparing the structural differences of different networks，the limitations of existing network similarity indicators are analyzed. On this basis，a new link prediction method based on supervised classification is proposed，which integrates multiple local and global similarity indexes as input feature vectors in order to more accurately evaluate the similarity between nodes. Thus，the effective prediction of potential comorbidity relationships is achieved. The experimental results show that the proposed method can effectively improve the accuracy of link prediction in comorbidity network and has better stability and adaptability in different disease network and classification algorithms.

Key words： comorbidity;network analysis;supervised learning;link prediction

共病是一種或多種附加疾病與某種主要疾病在同一患者身上共同發(fā)生的現(xiàn)象. 由于目前針對(duì)共病的醫(yī)學(xué)研究尚不完善，許多疾病之間的相互關(guān)系仍然具有很大的不確定性，這使得如何有效地分析疾病之間的關(guān)聯(lián)，從而發(fā)現(xiàn)潛在的共病關(guān)系，預(yù)測(cè)共病的發(fā)展趨勢(shì)成為當(dāng)前備受關(guān)注的研究熱點(diǎn).

由于網(wǎng)絡(luò)分析理論能簡(jiǎn)潔直觀地展現(xiàn)實(shí)體對(duì)象之間的聯(lián)系，已經(jīng)在生物、醫(yī)學(xué)、信息等領(lǐng)域得到了廣泛應(yīng)用[1-3]. 人類疾病也可以構(gòu)建成一個(gè)復(fù)雜的網(wǎng)絡(luò)系統(tǒng)，不同疾病之間存在著不同的共病關(guān)系. 疾病網(wǎng)絡(luò)分析通過(guò)構(gòu)建疾病網(wǎng)絡(luò)模型，將共病關(guān)系的預(yù)測(cè)問(wèn)題轉(zhuǎn)化為網(wǎng)絡(luò)上的鏈路預(yù)測(cè)問(wèn)題，為潛在共病關(guān)系的發(fā)現(xiàn)以及共病發(fā)展趨勢(shì)的預(yù)測(cè)提供了一種全新的研究視角. 目前，研究人員針對(duì)鏈路預(yù)測(cè)問(wèn)題已經(jīng)開(kāi)展了大量的研究. 其中，最具代表性的是基于相似性的鏈路預(yù)測(cè)方法[4-6]. 由于這些方法中相似性的計(jì)算僅片面地考慮了網(wǎng)絡(luò)節(jié)點(diǎn)或結(jié)構(gòu)的部分特征，無(wú)法全面反映網(wǎng)絡(luò)的拓?fù)涮匦?，大大影響了鏈路預(yù)測(cè)結(jié)果的準(zhǔn)確性. 此外，由于不同網(wǎng)絡(luò)系統(tǒng)的結(jié)構(gòu)具有顯著的差異性，這進(jìn)一步導(dǎo)致現(xiàn)有的基于相似性的鏈路預(yù)測(cè)方法在不同網(wǎng)絡(luò)上的表現(xiàn)極不穩(wěn)定，算法的泛化能力不足.

針對(duì)上述問(wèn)題，本文提出一種帶權(quán)疾病網(wǎng)絡(luò)上的新型共病關(guān)系預(yù)測(cè)方法. 相比已有的研究成果，本文的主要貢獻(xiàn)包括：

1）本文基于MIMIC-III數(shù)據(jù)集、湘雅醫(yī)療數(shù)據(jù)集、德克薩斯州健康數(shù)據(jù)集分別構(gòu)建了帶權(quán)共病網(wǎng)絡(luò)，并分析和比較了3個(gè)共病網(wǎng)絡(luò)在網(wǎng)絡(luò)結(jié)構(gòu)上的差異.

2）本文將共病關(guān)系的發(fā)現(xiàn)轉(zhuǎn)化為共病網(wǎng)絡(luò)上的鏈路預(yù)測(cè)問(wèn)題. 針對(duì)現(xiàn)有鏈路預(yù)測(cè)方法考慮因素相對(duì)單一，預(yù)測(cè)準(zhǔn)確性差，對(duì)不同網(wǎng)絡(luò)的適應(yīng)性不足等缺陷，提出了一種新的基于有監(jiān)督分類的鏈路預(yù)測(cè)方法，綜合多種局部和全局相似性指標(biāo)作為輸入特征向量，實(shí)現(xiàn)潛在共病關(guān)系的有效預(yù)測(cè).

3）利用3個(gè)不同來(lái)源的真實(shí)醫(yī)療數(shù)據(jù)集對(duì)本文提出的方法進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明該鏈路預(yù)測(cè)方法有效地提高了預(yù)測(cè)的準(zhǔn)確性，同時(shí)在不同疾病網(wǎng)絡(luò)上均表現(xiàn)出了較穩(wěn)定的性能.

1? ?相關(guān)工作

網(wǎng)絡(luò)分析方法作為研究生物系統(tǒng)的有力工具，對(duì)生物信息學(xué)、醫(yī)學(xué)的研究越來(lái)越重要. 近年來(lái)，研究人員提出了許多不同的生物系統(tǒng)網(wǎng)絡(luò)，如蛋白質(zhì)交互作用（PPI）網(wǎng)絡(luò)、新陳代謝網(wǎng)絡(luò)、人類疾病網(wǎng)絡(luò)（HDN）等[7-9]. 此外，一些包含多種生物學(xué)實(shí)體的異構(gòu)網(wǎng)絡(luò)也相繼出現(xiàn). 例如，Sun[10]提出一種整合藥物、疾病和基因的多層網(wǎng)絡(luò)模型，旨在更直觀地理解藥物-疾病-基因的交互作用機(jī)制;Zhou等人[11]構(gòu)建了人類疾病-癥狀網(wǎng)絡(luò)，用于發(fā)現(xiàn)疾病癥狀相似性與共享基因數(shù)量間的強(qiáng)關(guān)聯(lián)性.

鏈路預(yù)測(cè)（Link prediction）可用于評(píng)估已知網(wǎng)絡(luò)中鏈路存在的可能性，目前已經(jīng)在許多科學(xué)領(lǐng)域開(kāi)展了大量的相關(guān)研究和應(yīng)用[12-15].共病的分析研究有助于發(fā)現(xiàn)共存疾病間的潛在聯(lián)系，實(shí)現(xiàn)潛在共存疾病的早期預(yù)警，對(duì)于提升患者生活質(zhì)量具有重要意義. 近年來(lái)，如何通過(guò)鏈路預(yù)測(cè)解決疾病風(fēng)險(xiǎn)預(yù)測(cè)及潛在共病關(guān)系發(fā)現(xiàn)的問(wèn)題成為了該研究領(lǐng)域關(guān)注的熱點(diǎn). Gül等人[16]使用疾病的共現(xiàn)關(guān)系構(gòu)建帶權(quán)網(wǎng)絡(luò)，利用現(xiàn)有的鏈路預(yù)測(cè)方法評(píng)估疾病間的潛在關(guān)系. Kaya等人[17]使用年齡特性構(gòu)建疾病進(jìn)化網(wǎng)絡(luò)，提出一種采用監(jiān)督策略的鏈接預(yù)測(cè)方法識(shí)別疾病間的潛在聯(lián)系. Shin等人[18]提出了一種基于疾病網(wǎng)絡(luò)計(jì)算疾病共現(xiàn)概率的方法.

在現(xiàn)有鏈路預(yù)測(cè)方法中，研究人員大多使用基于相似度的預(yù)測(cè)算法，為節(jié)點(diǎn)對(duì)分配一個(gè)相似度分值來(lái)衡量節(jié)點(diǎn)間的相似性[19-20].基于相似性的方法大致分為基于節(jié)點(diǎn)相似性和基于網(wǎng)絡(luò)結(jié)構(gòu)相似性兩類方法. 由于節(jié)點(diǎn)的相關(guān)信息獲取相對(duì)困難，使得基于節(jié)點(diǎn)相似性的方法具有較大的局限性. 而網(wǎng)絡(luò)的結(jié)構(gòu)特征通常更易獲得，因此，基于網(wǎng)絡(luò)結(jié)構(gòu)特征的鏈路預(yù)測(cè)方法得到了更為廣泛的應(yīng)用.

基于網(wǎng)絡(luò)結(jié)構(gòu)特征的鏈路預(yù)測(cè)方法又可被進(jìn)一步劃分為基于局部相似度指標(biāo)和基于全局相似度指標(biāo)的鏈路預(yù)測(cè)算法[21-22].基于網(wǎng)絡(luò)局部結(jié)構(gòu)相似度的算法具有復(fù)雜度低和性能好等優(yōu)點(diǎn)，目前研究人員針對(duì)網(wǎng)絡(luò)局部結(jié)構(gòu)相似度的評(píng)估已經(jīng)開(kāi)展了大量的工作，如，Common Neighbors（CN） index[23]、Preferential Attachment index[4]、Jaccard's Coefficient[6]等. 然而，基于局部相似度指標(biāo)的算法僅使用網(wǎng)絡(luò)的局部信息，不能準(zhǔn)確反映網(wǎng)絡(luò)的整體結(jié)構(gòu)特征，大大影響該類算法的預(yù)測(cè)準(zhǔn)確度. 基于全局相似度的鏈路預(yù)測(cè)方法通過(guò)考慮網(wǎng)絡(luò)路徑信息，將分析使用的網(wǎng)絡(luò)結(jié)構(gòu)信息從較小的局部范圍擴(kuò)展至較大的全局范圍，從而彌補(bǔ)上述方法的不足. 典型的基于全局相似度的鏈路預(yù)測(cè)算法包括Local Path index[24]、Katz index[25]等. 此外，研究人員也提出許多基于節(jié)點(diǎn)隨機(jī)游走的算法，如Average Commute Time Index[26]、Random Walk Index Based on Cosine Similarity[27]、SimRank Index[28]等. 在上述基于網(wǎng)絡(luò)結(jié)構(gòu)的鏈路預(yù)測(cè)算法中，研究人員通常選取單方面的網(wǎng)絡(luò)特征來(lái)評(píng)估節(jié)點(diǎn)間的相似度，并假設(shè)它們?cè)诓煌逆溌奉A(yù)測(cè)任務(wù)中都占有主導(dǎo)作用. 然而，大量研究表明不同網(wǎng)絡(luò)擁有各自獨(dú)特的結(jié)構(gòu)特征，同一個(gè)網(wǎng)絡(luò)的不同部分的結(jié)構(gòu)特征也有所差異[29]，這使得這些鏈路預(yù)測(cè)算法應(yīng)用到不同網(wǎng)絡(luò)上時(shí)性能差異較大，算法的適應(yīng)性不佳.

本文提出一種適應(yīng)不同帶權(quán)疾病網(wǎng)絡(luò)的潛在共病關(guān)系預(yù)測(cè)方法，通過(guò)綜合多種網(wǎng)絡(luò)結(jié)構(gòu)特征提高相似度計(jì)算的準(zhǔn)確性，從而實(shí)現(xiàn)更有效的共病關(guān)系預(yù)測(cè)，為臨床輔助決策提供有力的依據(jù).

2? ?帶權(quán)疾病網(wǎng)絡(luò)的構(gòu)建

本文將帶權(quán)疾病網(wǎng)絡(luò)表示為：G = （V，E，W），其中，V表示網(wǎng)絡(luò)節(jié)點(diǎn)的集合，E表示網(wǎng)絡(luò)中邊的集合，W為網(wǎng)絡(luò)邊上權(quán)重的集合. 在該網(wǎng)絡(luò)中，每一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)代表一種疾病，邊代表兩種疾病之間存在關(guān)聯(lián). 在疾病網(wǎng)絡(luò)構(gòu)建過(guò)程中，鑒于醫(yī)療數(shù)據(jù)集中患者診斷編碼通常缺失率較低，因此從數(shù)據(jù)的易獲取性和數(shù)據(jù)質(zhì)量的角度考慮，主要利用患者就診記錄中的診斷編碼，使每一種ICD編碼對(duì)應(yīng)疾病網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn). 同時(shí)，根據(jù)兩種疾病在同一患者的就診記錄中的共現(xiàn)關(guān)系來(lái)確定疾病之間的關(guān)聯(lián)，疾病對(duì)的共現(xiàn)頻次則作為其相應(yīng)邊上權(quán)重的衡量指標(biāo).

2.1? ?數(shù)據(jù)準(zhǔn)備及網(wǎng)絡(luò)構(gòu)建

本文使用3個(gè)真實(shí)的醫(yī)療數(shù)據(jù)集，MIMIC-III（Medical Information Mart for Intensive Care III）[30]臨床數(shù)據(jù)集（簡(jiǎn)稱MIMIC-III）、中南大學(xué)湘雅醫(yī)療數(shù)據(jù)集[31]（簡(jiǎn)稱湘雅）和德克薩斯州健康數(shù)據(jù)集（Texas Health Data[32]簡(jiǎn)稱Texas）來(lái)分別構(gòu)建對(duì)應(yīng)的疾病網(wǎng)絡(luò). 表1為這些數(shù)據(jù)集的統(tǒng)計(jì)信息.

為了確保構(gòu)建的疾病網(wǎng)絡(luò)的有效性和代表性，對(duì)原始醫(yī)療數(shù)據(jù)集進(jìn)行了一定的預(yù)處理，剔除了部分無(wú)效的患者記錄，具體包括：1） 清理重復(fù)的醫(yī)療記錄;2）刪除只包含一種疾病的患者就診記錄;3）由于疾病網(wǎng)絡(luò)的構(gòu)建工作不考慮稀有疾病，因此剔除了疾病對(duì)共現(xiàn)頻次小于100的數(shù)據(jù).

在完成數(shù)據(jù)清理步驟后，使用Cytoscape 3.5.0[33]來(lái)構(gòu)建和可視化帶權(quán)疾病網(wǎng)絡(luò)，結(jié)果分別見(jiàn)圖1、圖2和圖3. 圖中節(jié)點(diǎn)上的標(biāo)簽表示節(jié)點(diǎn)所代表疾病的ICD編碼，節(jié)點(diǎn)的大小與對(duì)應(yīng)的患者數(shù)成正比，節(jié)點(diǎn)間邊的寬度則與對(duì)應(yīng)的權(quán)重成正比.

2.2? ?共病網(wǎng)絡(luò)基礎(chǔ)特性對(duì)比

根據(jù)構(gòu)建的上述3個(gè)疾病網(wǎng)絡(luò)，首先從網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)、邊數(shù)、平均度數(shù)、聚類系數(shù)等方面對(duì)各網(wǎng)絡(luò)的基本結(jié)構(gòu)特性進(jìn)行了對(duì)比分析，詳見(jiàn)表2. 由表2可知，湘雅疾病網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量和邊數(shù)量最少，平均路徑長(zhǎng)度最大;MIMIC-III疾病網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量與湘雅疾病網(wǎng)絡(luò)的相當(dāng)，網(wǎng)絡(luò)密度最大而平均路徑長(zhǎng)度最短;而德克薩斯州疾病網(wǎng)絡(luò)，節(jié)點(diǎn)和邊的絕對(duì)數(shù)量均遠(yuǎn)超前兩者. 這說(shuō)明了不同疾病網(wǎng)絡(luò)在網(wǎng)絡(luò)結(jié)構(gòu)特征方面的明顯差異.

3? ?疾病網(wǎng)絡(luò)上的潛在共病關(guān)系預(yù)測(cè)

依據(jù)所構(gòu)建的疾病網(wǎng)絡(luò)，將潛在共病關(guān)系預(yù)測(cè)轉(zhuǎn)化為網(wǎng)絡(luò)上的鏈路預(yù)測(cè)問(wèn)題. 用Eexist = {Ei}表示網(wǎng)絡(luò)中已存在邊的集合，Emiss = {Ej}表示網(wǎng)絡(luò)中缺失邊的集合，E表示網(wǎng)絡(luò)中所有可能的邊集合. 顯然，它們滿足下面的關(guān)系，E = Eexist∪Emiss，且Eexist∩Emiss = ?. 本文的目標(biāo)是計(jì)算在給定加權(quán)疾病網(wǎng)絡(luò)中尚未連接節(jié)點(diǎn)間出現(xiàn)新連接關(guān)系的可能性. 即，根據(jù)節(jié)點(diǎn)間已知的連接建立映射關(guān)系 f：{Ej}→{0，1} ，從而確定是否存在 {Ej} 中的潛在鏈路關(guān)系. 為此，本文在結(jié)合多種基于局部和全局網(wǎng)絡(luò)結(jié)構(gòu)特征的網(wǎng)絡(luò)相似度指標(biāo)的基礎(chǔ)上，提出一種新的鏈路預(yù)測(cè)方法，實(shí)現(xiàn)潛在共病關(guān)系的準(zhǔn)確預(yù)測(cè).

3.1? ?相似度指標(biāo)

本文從現(xiàn)有的基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征的鏈路預(yù)測(cè)方法中選取了幾種常用的相似度指標(biāo)，將它們結(jié)合起來(lái)，從多個(gè)角度捕捉網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征，以提升鏈路預(yù)測(cè)的準(zhǔn)確性. 為保證表述的一致性，將下文中涉及的符號(hào)統(tǒng)一定義如下. w（vi，vj）表示網(wǎng)絡(luò)上節(jié)點(diǎn)vi和vj間連接的權(quán)重，Γ（vi）表示節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集合，a∈Γ（vi）表示a為節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn).

Γ（vi）∩Γ（vj）表示節(jié)點(diǎn)vi與vj的共同鄰居節(jié)點(diǎn)的集合，則z∈Γ（vi）∩Γ（vj）即為節(jié)點(diǎn)vi與vj的共同

鄰居.

本文所選取的相似度指標(biāo)主要包括：

Common Neighbors（CN）[23]. 該指標(biāo)假設(shè)若兩個(gè)節(jié)點(diǎn)共享的鄰居節(jié)點(diǎn)越多，那么它們之間出現(xiàn)連接的可能性越大. 計(jì)算公式如下：

CN（vi，vj） = [][z∈Γ（vi）∩Γ（vj）]w（vi，z） + w（vj，z）? ? （1）

Jaccard's Coefficient（JC）[6]. 該指標(biāo)認(rèn)為兩個(gè)節(jié)點(diǎn)的共同鄰居節(jié)點(diǎn)的權(quán)重之和占總鄰居節(jié)點(diǎn)數(shù)的權(quán)

重之和比例越大，節(jié)點(diǎn)間越易出現(xiàn)新的連接. 即：

JC（vi，vj）=[][z∈Γ（vi）∩Γ（vj）]

（2）

Adamic-Adar Coefficient（AA）[5]. 該指標(biāo)認(rèn)為節(jié)點(diǎn)間的共同鄰居節(jié)點(diǎn)越多，且這些共同鄰居節(jié)點(diǎn)的度數(shù)較小，則出現(xiàn)連接的可能性越大. 即：

AA（vi，vj）=[][z∈Γ（vi）∩Γ（vj）]? （3）

Preferential Attachment （PA）[4]. 該指標(biāo)假設(shè)兩個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)越多，且與鄰居節(jié)點(diǎn)的權(quán)重之和較大，則節(jié)點(diǎn)間越易出現(xiàn)新的連接. 即：

PA（vi，vj）=[a∈Γ（vi）][]w（a，vi）× [b∈Γ（vj）][] w（b，vj）? ?（4）

Resource Allocation Index（RA）[34]. 該指標(biāo)與AA指標(biāo)的區(qū)別在于對(duì)共同鄰居節(jié)點(diǎn)與其相鄰節(jié)點(diǎn)的權(quán)重之和的定義方式不同. 計(jì)算公式如下：

RA（vi，vj）=[][z∈Γ（vi）∩Γ（vj）]? ? （5）

除上述幾種局部相似度指標(biāo)外，本文還選取了帶重啟動(dòng)的隨機(jī)游走算法（Random walk with restart algorithm，RWR）[22]，來(lái)獲得更大范圍上的全局相似性. 其計(jì)算公式如下：

p（t+1）

= （1 - α）Sp（t）

+ αq? ? （6）

式中：p（t）

表示第t步游走后圖中的概率分布;列向量q為重啟動(dòng)向量，表示初始狀態(tài);S為轉(zhuǎn)移概率矩陣;α為直接回到出發(fā)頂點(diǎn)的概率.

3.2? ?基于多種相似度指標(biāo)的潛在共病關(guān)系預(yù)測(cè)

本文提出一種基于多種相似度指標(biāo)的潛在共病關(guān)系預(yù)測(cè)方法（Latent Comorbidity Prediction based on Multiple Similarity Indexes，LCPMSI），該方法將基于不同網(wǎng)絡(luò)結(jié)構(gòu)特征的相似度指標(biāo)進(jìn)行整合構(gòu)建特征矢量，將其輸入到基于有監(jiān)督學(xué)習(xí)的分類模型中，對(duì)疾病網(wǎng)絡(luò)中尚未連邊的節(jié)點(diǎn)對(duì)產(chǎn)生連接的可能性進(jìn)行估計(jì)，從而實(shí)現(xiàn)潛在共病關(guān)系的有效預(yù)測(cè). 在帶權(quán)疾病網(wǎng)絡(luò)中，潛在共病關(guān)系預(yù)測(cè)本質(zhì)上可以看成一個(gè)二分類問(wèn)題，即推斷疾病節(jié)點(diǎn)對(duì)間是否存在

邊連接. 對(duì)于給定網(wǎng)絡(luò)G中的任意節(jié)點(diǎn)對(duì)（vi，vj），

E（vi，vj）表示節(jié)點(diǎn)對(duì)間可能的鏈路，l（vi，vj）是一個(gè)邏輯狀態(tài)變量，用于指示網(wǎng)絡(luò)中該節(jié)點(diǎn)對(duì)間是否存在連接關(guān)系. 那么，如果網(wǎng)絡(luò)G中節(jié)點(diǎn)對(duì)（vi，vj）之間存在已知鏈路E（vi，vj），則E（vi，vj）將被標(biāo)記為正樣本并被置于集合Eexist中，同時(shí)l（vi，vj）將被設(shè)置為1. 否則，將E（vi，vj）設(shè)置為負(fù)樣本置于集合Emiss中，并將l（vi，vj）設(shè)置為0. 然后將所有樣本隨機(jī)分成兩部分，90%的樣本作為訓(xùn)練集，并保證其中包含網(wǎng)絡(luò)中90%的已存在鏈路，剩余的10%的樣本則作為測(cè)試集.

在訓(xùn)練集上，任意節(jié)點(diǎn)對(duì)（vi，vj），根據(jù)上述6種相似度指標(biāo)分別計(jì)算它們的相似度分值，并將計(jì)算得到的6種相似度分值結(jié)合起來(lái)構(gòu)建相應(yīng)的特征向量S（vi，vj），即：

S（vi，vj） = {S

M1（vi，vj），S

M2（vi，vj），…，S

Mn（vi，vj）}

（7）

式中：S

Mn（vi，vj）表示節(jié)點(diǎn)對(duì)基于指標(biāo)Mn計(jì)算得到的相似度分值，Mn∈{CN，AA，JC，PA，RA，RWR}.

然后，將各節(jié)點(diǎn)對(duì)的特征向量輸入分類器進(jìn)行訓(xùn)練，進(jìn)而實(shí)現(xiàn)目標(biāo)節(jié)點(diǎn)對(duì)間鏈路存在性的預(yù)測(cè).

4? ?實(shí)驗(yàn)結(jié)果及分析

4.1? ?實(shí)驗(yàn)設(shè)置及評(píng)價(jià)指標(biāo)

為了驗(yàn)證LCPMSI算法的有效性，將其分別與采用上述6種單一相似度指標(biāo)的方法以及2種簡(jiǎn)化的局部和全局相似度相結(jié)合的方法（CN+RWR和CN+PA+RWR）進(jìn)行了性能比較. 實(shí)驗(yàn)中通過(guò)Weka軟件包實(shí)現(xiàn)了Random Forest（RF），Random Tree（RT），Multi-Layer Perceptron（MLP），J48以及Naive Bayes 5種常見(jiàn)的分類器，各分類器的參數(shù)均采用Weka中的默認(rèn)設(shè)置.

本文使用的評(píng)價(jià)指標(biāo)包括：AUC（Area Under ROC Curve）、精準(zhǔn)率（Precision）以及召回率（Recall）. 此外，為了保證實(shí)驗(yàn)結(jié)果的可靠性，對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行隨機(jī)打亂處理，并采用十折交叉驗(yàn)證對(duì)樣本集進(jìn)行劃分. 每種預(yù)測(cè)算法均獨(dú)立地執(zhí)行10次，然后將其平均值作為最終的預(yù)測(cè)結(jié)果.

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

為了驗(yàn)證LCPMSI在共病預(yù)測(cè)中的有效性，利用已構(gòu)建的MIMIC-III、湘雅和Texas疾病網(wǎng)絡(luò)對(duì)各算法進(jìn)行性能評(píng)估，結(jié)果分別如圖4～圖6所示.

從實(shí)驗(yàn)結(jié)果可看出，采用單一相似度指標(biāo)的預(yù)測(cè)方法在不同疾病網(wǎng)絡(luò)上的性能存在明顯差異. 以使用RF分類器時(shí)的結(jié)果為例，按照AUC值對(duì)基于單一相似度指標(biāo)的6種方法的性能進(jìn)行排序，結(jié)果如下，MIMIC-III：PA>CN>AA>RA>RWR>JC;湘雅：CN>AA>JC>PA>RA>RWR;Texas：AA>CN>PA>RA>JC>RWR. 此外，當(dāng)采用不同的分類器時(shí)，各相似度指標(biāo)在不同疾病網(wǎng)絡(luò)上的鏈路預(yù)測(cè)效果也各不相同. 以CN為例，其在MIMIC-III疾病網(wǎng)絡(luò)中的表現(xiàn)最佳，AUC值達(dá)到了最高的0.963（采用Naive Bayes時(shí)），而在德州和湘雅疾病網(wǎng)絡(luò)上CN獲得的最優(yōu)結(jié)果分別為0.958（采用MLP時(shí)）和0.874（采用RF時(shí)）. 上述結(jié)果表明，基于單一相似度指標(biāo)的鏈路預(yù)測(cè)方法在不同的疾病網(wǎng)絡(luò)中的適應(yīng)性較差，性能不穩(wěn)定. 這正是由于上述6種單一的相似度指標(biāo)僅片面地考慮了網(wǎng)絡(luò)結(jié)構(gòu)特征，缺乏對(duì)網(wǎng)絡(luò)結(jié)構(gòu)相似性的全面評(píng)估，因此在應(yīng)用到不同結(jié)構(gòu)特征的疾病網(wǎng)絡(luò)上時(shí)，無(wú)法保證相似度計(jì)算的適用性，大大影響了預(yù)測(cè)算法的有效性和穩(wěn)定性.

通過(guò)將基于局部和全局相似性的多個(gè)指標(biāo)進(jìn)行結(jié)合，預(yù)測(cè)算法的性能在不同的疾病網(wǎng)絡(luò)上均獲得了明顯的提升. 如圖4所示，在MIMIC-III疾病網(wǎng)絡(luò)上，當(dāng)選取CN+RWR作為特征時(shí)，AUC值達(dá)到最高值0.975（采用Naive Bayes時(shí)），比單一采用CN時(shí)的AUC提高了0.012，相較于RWR的提升幅度更是達(dá)到了0.084. 隨著特征集合所包含的相似度指標(biāo)的增多，預(yù)測(cè)模型在AUC值、精準(zhǔn)率和召回率等方面的性能都逐漸有所提高. 當(dāng)結(jié)合6種單一的相似度指標(biāo)時(shí)，LCPMSI算法在不同的疾病網(wǎng)絡(luò)上均獲得了最佳的預(yù)測(cè)性能. 同時(shí)從不同分類器上的結(jié)果來(lái)看，LCPMSI在采用RF分類器時(shí)的性能表現(xiàn)最優(yōu). 如圖5中湘雅疾病網(wǎng)絡(luò)的結(jié)果所示，LCPMSI的AUC值、精準(zhǔn)率和召回率相比CN分別相應(yīng)地提高了0.072、0.105和0.131. 實(shí)驗(yàn)結(jié)果說(shuō)明，本文提出的方法相比現(xiàn)有的基于單一相似度指標(biāo)的鏈路預(yù)測(cè)算法能更好地適應(yīng)不同疾病網(wǎng)絡(luò)上的預(yù)測(cè)任務(wù)，并在預(yù)測(cè)的準(zhǔn)確性和性能的穩(wěn)定性上具有明顯的優(yōu)勢(shì). 這主要得益于LCPMSI對(duì)多方面網(wǎng)絡(luò)結(jié)構(gòu)特征的綜合考慮，實(shí)現(xiàn)了對(duì)相似度的更準(zhǔn)確把握. 同時(shí)，通過(guò)與有監(jiān)督分類模型的結(jié)合，大大提高了預(yù)測(cè)算法的有效性和泛化能力.

5? ?結(jié)? ?論

共病關(guān)系預(yù)測(cè)是醫(yī)學(xué)研究的熱點(diǎn)問(wèn)題. 通過(guò)構(gòu)建疾病網(wǎng)絡(luò)，可以將其轉(zhuǎn)化為網(wǎng)絡(luò)上的鏈路預(yù)測(cè)問(wèn)題進(jìn)行解決. 但現(xiàn)有的許多鏈路預(yù)測(cè)方法僅考慮了單一網(wǎng)絡(luò)結(jié)構(gòu)特征，在不同疾病網(wǎng)絡(luò)上的性能較不穩(wěn)定. 針對(duì)這一問(wèn)題，本文提出了一種基于監(jiān)督學(xué)習(xí)的潛在共病關(guān)系預(yù)測(cè)方法. 方法中使用基于監(jiān)督學(xué)習(xí)的分類方法挖掘不同疾病網(wǎng)絡(luò)的內(nèi)部結(jié)構(gòu)特征，學(xué)習(xí)每種網(wǎng)絡(luò)結(jié)構(gòu)特征的重要性，以提高算法的預(yù)測(cè)精度以及在不同疾病網(wǎng)絡(luò)上的泛化能力. 實(shí)驗(yàn)結(jié)果表明，該方法有效地提高了潛在共病關(guān)系的預(yù)測(cè)性能. 同時(shí)，通過(guò)在基于不同醫(yī)療數(shù)據(jù)集構(gòu)建的疾病網(wǎng)絡(luò)上的測(cè)試結(jié)果比較，進(jìn)一步證明了該方法的穩(wěn)定性和適用性.

在未來(lái)的工作中，我們將進(jìn)一步結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)特征和語(yǔ)義特征來(lái)提高共病關(guān)系的預(yù)測(cè)精度. 同時(shí)，還將考慮疾病發(fā)展的時(shí)序特性，改進(jìn)本文的算法以解決有向疾病網(wǎng)絡(luò)中的鏈路預(yù)測(cè)問(wèn)題.

參考文獻(xiàn)

[1]? ?ZONG N，KIM H，NGO V，et al. Deep mining heterogeneous networks of biomedical linked data to predict novel drug-target associations[J]. Bioinformatics，2017，33（15）：2337—2344.

[2]? ?CHEN H Y，LI J. A flexible and robust multi-source learning algorithm for drug repositioning[C]// Proceedings of the 8th ACM International Conference on Bioinformatics，Computational Biology，and Health Informatics. New York： ACM，2017：510—515.

[3]? ? 侯泳旭，段磊，李嶺，等. 基于疾病信息網(wǎng)絡(luò)的表型基因搜索[J]. 軟件學(xué)報(bào)，2018，29（3）：721—733.

HOU Y X，DUAN L，LI L，et al. Search of gene with similar phenotype based on disease information network[J]. Journal of Software，2018，29（3）：721—733.（In Chinese）

[4]? ? BARABASI A L，BONABEAU E. Scale free networks[J]. Scientific American，2003，288（5）：50—59.

[5]? ?ADAMIC L A，ADAR E. Friends and neighbors on the web[J]. Social Networks，2003，25（3）：211—230.

[6]? ? TAN P N，STEINBACH M，KUMAR V. Introduction to data mining[M]. New Jersey： Addison-Wesley，2005：38—50.

[7]? ? MART?N-JIM?NEZ C A，SALAZAR-BARRETO D，BARRETO G E，et al. Genome-scale reconstruction of the human astrocyte metabolic network[J]. Frontiers in Aging Neuroscience，2017，23（9）：1—17.

[8]? ?DEVREOTES P N，BHATTACHARYA S，EDWARDS M，et al. Excitable signal transduction networks in directed cell migration[J]. Annual Review of Cell and Developmental Biology，2017，33（1）：103—125.

[9]? ?JIANG Y，MA S，SHIA B C，et al. An epidemiological human disease network derived from disease co-occurrence in Taiwan[J]. Scientific Reports，2018，8（1）：1—12.

[10]? SUN P G. The human drug-disease-gene network[J]. Information Sciences，2015，306：70—80.

[11]? ZHOU X Z，MENCHE J，BARAB?SI A L，et al. Human symptoms-disease network[J]. Nature Communications，2014，5：4212.

[12]? 方陽(yáng)，趙翔，譚真，等. 一種改進(jìn)的基于翻譯的知識(shí)圖譜表示方法[J]. 計(jì)算機(jī)研究與發(fā)展，2018，55（1）：139—150.

FANG Y，ZHAO X，TAN Z，et al. A revised translation-based method for knowledge graph representation[J]. Journal of Computer Research and Development，2018，55（1）：139—150.（In Chinese）

[13]? 陳德華，殷蘇娜，樂(lè)嘉錦，等. 一種面向臨床領(lǐng)域時(shí)序知識(shí)圖譜的鏈接預(yù)測(cè)模型[J]. 計(jì)算機(jī)研究與發(fā)展，2017，54（12）：2687—2697.

CHEN D H，YIN S N，LE J J，et al. A link prediction model for clinical temporal knowledge graph[J]. Journal of Computer Research and Development， 2017， 54（12）： 2687—2697. （In Chinese）

[14]? YANG J，YANG T H，WU D Z，et al. The integration of weighted human gene association networks based on link prediction[J]. BMC Systems Biology，2017，11（1）：1—17.

[15]? SULAIMANY S，KHANSARI M，ZARRINEH P，et al. Predicting brain network changes in Alzheimer's disease with link prediction algorithms[J]. Molecular BioSystems，2017，13（4）：725—735.

[16]? G?L S，KAYA M，KAYA B. Predicting links in weighted disease networks[C]//International Conference on Computer and Information Sciences （ICCOINS）. Kuala Lumpur： IEEE，2016：77—81.

[17]? KAYA B，POYRAZ M. Finding relations between diseases by age-series based supervised link prediction[C]//International Conference on Advances in Social Networks Analysis and Mining （ASONAM）. New Jersey：IEEE，2015：1097—1103.

[18]? SHIN H J. Method for providing disease co-occurrence probability from disease network[P]. US：20160350502，2016—12-01.

[19]? 楊妮亞，彭濤，劉露. 基于聚類和決策樹(shù)的鏈路預(yù)測(cè)方法[J]. 計(jì)算機(jī)研究與發(fā)展，2017，54（8）：1795—1803.

YANG N Y，PENG T，LIU L. Link prediction method based on clustering and decision tree[J]. Journal of Computer Research and Development，2017，54（8）：1795—1803. （In Chinese）

[20]? LIBEN-NOWELL D，KLEINBERG J. The link-prediction problem for social networks[J]. Journal of the American Society for Information Science and Technology，2007，58（7）：1019—1031.

[21]? LEICHT E A，HOLME P，NEWMAN M E J. Vertex similarity in networks[J]. Physical Review E，2006，73（2）：026120.

[22]? TONG H，F(xiàn)ALOUTSOS C，PAN J Y. Fast random walk with restart and its applications[C]//IEEE International Conference on Data Mining （ICDM）. New Jersey：IEEE，2006：613—622.

[23]? NEWMAN M E J. Clustering and preferential attachment in growing networks[J]. Physical Review E，2001，64（2）：025102.

[24]? WANG Y，ZHOU T，SHI J，et al. Empirical analysis of dependence between stations in Chinese railway network[J]. Physica A： Statistical Mechanics and Its Applications，2009，388（14）：2949—2955.

[25]? KATZ L. A new status index derived from sociometric analysis[J]. Psychometrika，1953，18（1）：39—43.

[26]? KLEIN D J，[RANDICM][′]. Resistance distance[J]. Journal of Mathematical Chemistry，1993，12（1）：81—95.

[27] FOUSS F，PIROTTE A，RENDERS J M，et al. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J]. IEEE Transactions on Knowledge and Data Engineering，2007，19（3）：355—369.

[28]? JEH G，WIDOM J. Simrank： a measure of structural-context similarity[C]//The Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM，2002：538—543.

[29]? MA C，BAO Z，ZHANG H. Improving link prediction in complex networks by adaptively exploiting multiple structural features of networks[J]. Physics Letters A，2017，381（39）：3369—3376.

[30]? JOHNSON A E W，POLLARD T J，SHEN L，et al. MIMIC-III，a freely accessible critical care database[J]. Scientific Data，2016，3：160035.

[31]? LI B，LI J B，LAN X Y，et al. Experiences of building a medical data acquisition system based on two-level modeling[J]. International Journal of Medical Informatics，2018，112：114—122.

[32]? The Texas Department of State Health Services. TEXAS health and human services[EB/OL]. （2018-02-01）[2018-05-15].https：//www.dshs.texas.gov/THCIC/Hospitals/Download.shtm.

[33]? SHANNON P，MARKIEL A，OWEN O，et al. Cytoscape： a software environment for integrated models of biomolecular interaction networks[J]. Genome Research，2003，13：2498—2504.

[34]? ADAMIC L A，ADAR E. Friends and neighbors on the web[J]. Social Networks，2003，25（3）：211—230.