基于信息論的優(yōu)化降噪方法研究

劉飛(寶雞文理學(xué)院 物理與信息技術(shù)系，陜西 寶雞 721016)

基于信息論的優(yōu)化降噪方法研究

劉飛
(寶雞文理學(xué)院 物理與信息技術(shù)系，陜西 寶雞 721016)

復(fù)雜網(wǎng)絡(luò)的重構(gòu)可以挖掘出網(wǎng)絡(luò)節(jié)點(diǎn)之間潛在的調(diào)控關(guān)系，幫助我們更深刻地理解網(wǎng)絡(luò)節(jié)點(diǎn)間復(fù)雜的作用機(jī)制，因此產(chǎn)生了很多網(wǎng)絡(luò)構(gòu)建的模擬理論和計(jì)算方法。由于數(shù)據(jù)的高維低樣本特性以及數(shù)據(jù)固有的噪聲，這些方法在構(gòu)建網(wǎng)絡(luò)時(shí)會(huì)有很高的假陽性率。為了克服這個(gè)缺點(diǎn)一種新的方法被提出，方法結(jié)合了互信息理論和常微分方程來優(yōu)化降噪。網(wǎng)絡(luò)中相關(guān)性較小的邊可以通過信息論的方法來檢測濾除，而一些冗余的邊信息可以通過微分方程優(yōu)化降噪來篩除，從而進(jìn)一步提高網(wǎng)絡(luò)構(gòu)建的精度。算法通過DREAM(Dialogue for Reverse Engineering Assessments and Methods)實(shí)驗(yàn)數(shù)據(jù)集來仿真驗(yàn)證，結(jié)果顯示算法在復(fù)雜網(wǎng)絡(luò)構(gòu)建過程中有較高的準(zhǔn)確率及較低的假陽性。

復(fù)雜網(wǎng)絡(luò)；網(wǎng)絡(luò)構(gòu)建；信息論；逐步優(yōu)化；降噪

0 引 言

復(fù)雜網(wǎng)絡(luò)的構(gòu)建已經(jīng)成為人們研究的熱點(diǎn)領(lǐng)域，通過構(gòu)建的網(wǎng)絡(luò)可以系統(tǒng)地研究網(wǎng)絡(luò)中節(jié)點(diǎn)之間的調(diào)配關(guān)系，為深入挖掘節(jié)點(diǎn)之間的復(fù)雜關(guān)系及作用機(jī)制提供理論模型。在網(wǎng)絡(luò)的建模方面，國內(nèi)外已經(jīng)研究了大量的數(shù)學(xué)建模方法，如布爾代數(shù)模型理論方法[1-2]、偏微分方程模型[3]、貝葉斯網(wǎng)絡(luò)模型[4-5]以及統(tǒng)計(jì)回歸模型[6]等方法。在復(fù)雜網(wǎng)絡(luò)構(gòu)建的方法中，信息論的方法[7-8]可以識(shí)別網(wǎng)絡(luò)節(jié)點(diǎn)變量之間的非線性相關(guān)性而被廣泛采用。實(shí)驗(yàn)數(shù)據(jù)由于其成本問題而具有高維低樣本特性，這成為了網(wǎng)絡(luò)構(gòu)建的難點(diǎn)所在，但信息論的方法對(duì)樣本的個(gè)數(shù)要求很低，所以信息論的方法在構(gòu)建網(wǎng)絡(luò)模型有較高的性能。

盡管信息論方法在構(gòu)建網(wǎng)絡(luò)模型中有很多優(yōu)點(diǎn)，但由于其計(jì)算出來用于構(gòu)建網(wǎng)絡(luò)的互信息矩陣具有對(duì)稱性，所以無法判斷網(wǎng)絡(luò)中邊的方向問題，而且計(jì)算出來的網(wǎng)絡(luò)規(guī)模相對(duì)較大，有很多冗余的邊，使得構(gòu)建的網(wǎng)絡(luò)假陽性率較高。為了克服這個(gè)缺點(diǎn)，本文提出了一種基于信息論的微分方程優(yōu)化降噪方法，來降低網(wǎng)絡(luò)的假陽性，提高網(wǎng)絡(luò)構(gòu)建的精度，算法的流程圖如圖1所示。該方法首先對(duì)實(shí)驗(yàn)產(chǎn)生的數(shù)據(jù)用信息論的方法來計(jì)算節(jié)點(diǎn)之間的相關(guān)性，從而構(gòu)建出網(wǎng)絡(luò)，對(duì)于網(wǎng)絡(luò)中冗余的邊用基于微分方程的優(yōu)化方法來去除降噪，從而去除假陽性和假陰性的邊。通過DREAM[9]競賽的標(biāo)準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)來對(duì)方法進(jìn)行測試，實(shí)驗(yàn)結(jié)果表明我們構(gòu)建出的網(wǎng)絡(luò)具有較高的性能和精度。

圖1 算法流程圖

1 理論方法

1.1 信息論

基于信息論的互信息已經(jīng)廣泛應(yīng)用于網(wǎng)絡(luò)的重構(gòu)，而且取得了較好的效果。它是衡量兩個(gè)變量X和Y之間的相關(guān)性，現(xiàn)給定一個(gè)變量X，它的信息熵H(X)描述如下：

(1)

其中p(x)表示變量X為x時(shí)的概率值，變量X和Y的聯(lián)合熵H(X,Y)可以被定義為：

(2)

其中p(x,y)表示變量X和Y分別為x和y時(shí)的聯(lián)合概率值，變量X和Y的互信息值I(X,Y)定義如下：

(3)

由公式(2)和(3) 互信息值I(X,Y)被重寫為：

I(X,Y)=H(X)+H(Y)-H(X,Y)

(4)

這里H(X,Y)表示變量X和Y的聯(lián)合熵，互信息值的大小表示變量相互作用關(guān)系的強(qiáng)弱，當(dāng)互信息值非常小或者接近于零時(shí)表示兩個(gè)變量相互獨(dú)立。條件互信息CMI的公式定義如下：

(5)

其中H(X,Y)表示變量X，Y和Z的聯(lián)合熵，這里的熵用高斯核概率密度函數(shù)來估計(jì)[10]，它的計(jì)算機(jī)公式如下：

P(Xi)=

(6)

(7)

由公式(7)，互信息公式(4)被重寫為：

(8)

同理，條件互信息公式(5)被重寫為：

(9)

1.2 優(yōu)化方法

網(wǎng)絡(luò)節(jié)點(diǎn)間的調(diào)配關(guān)系可以用如下的線性模型來描述，其中y，X表示網(wǎng)絡(luò)節(jié)點(diǎn)，β表示節(jié)點(diǎn)間相關(guān)系數(shù):

yi=βiX,i=1,2,…,n

(10)

β可以用最小化預(yù)測值和觀察值的差來估計(jì)，即如下公式，λ是調(diào)節(jié)網(wǎng)絡(luò)規(guī)模大小的非負(fù)參數(shù):

(11)

公式(10)可以寫成如下線性規(guī)劃模型:

(12)

對(duì)于公式(11)，可以用線性規(guī)劃模型的標(biāo)準(zhǔn)解法來求解[11]。

2 分析討論

2.1 網(wǎng)絡(luò)性能評(píng)價(jià)標(biāo)準(zhǔn)

網(wǎng)絡(luò)預(yù)測的結(jié)果用真陽性(True Positive, TP)，假陽性(False Positiv,簡稱FP)，真陰性(True Negative,簡稱TN)，假陰性(Flase Negative,簡稱FN)等指標(biāo)來衡量，本文用真陽性率(True Positive Rate,簡稱TPR)，假陽性率(Flase Positive Rate,簡稱FPR)，查準(zhǔn)率(Positive Predictive Value,簡稱PPV)和精確度(Accuracy,簡稱ACC)來對(duì)構(gòu)建的網(wǎng)絡(luò)進(jìn)行檢測，公式定義如下：

TTPR=TTP/(TTP+FN)

FFPR=FP/(FP+TN)

PPPV=TTP/(TTP+FP)

AACC=(TTP+TN)/(TTP+FP+TN+FN)

除了上述指標(biāo)外還有受試者工作特性曲線 (Receiver Operation Characteristic Curve, ROC曲線)和其曲線下的面積 (Area under ROC, AUROC)來衡量構(gòu)建算法的優(yōu)劣性。

2.2 網(wǎng)絡(luò)構(gòu)建仿真分析

圖2 標(biāo)準(zhǔn)網(wǎng)絡(luò)

圖3 構(gòu)建網(wǎng)絡(luò)

圖4 構(gòu)建網(wǎng)絡(luò)ROC曲線圖

標(biāo)準(zhǔn)的實(shí)驗(yàn)數(shù)據(jù)集可以檢測網(wǎng)絡(luò)構(gòu)建算法的精確性，研究的網(wǎng)絡(luò)構(gòu)建算法對(duì)這些實(shí)驗(yàn)數(shù)據(jù)進(jìn)行網(wǎng)絡(luò)構(gòu)建，然后和實(shí)驗(yàn)數(shù)據(jù)集潛在的真實(shí)網(wǎng)絡(luò)進(jìn)行比對(duì)，從而驗(yàn)證算法的優(yōu)略性。在本文中采用的DREAM競賽數(shù)據(jù)來對(duì)算法進(jìn)行檢測評(píng)估。這里選取了DREAM3的一個(gè)子網(wǎng)絡(luò)對(duì)應(yīng)的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)仿真，真實(shí)網(wǎng)絡(luò)含有10頂點(diǎn)，10條作用邊，如圖2所示為網(wǎng)絡(luò)的真實(shí)關(guān)系圖。

圖3是按照算法，在互信息理論構(gòu)建出來的網(wǎng)絡(luò)基礎(chǔ)上，再采用基于微分方程優(yōu)化降噪后得出的最終網(wǎng)絡(luò)。從圖中可以看出方法構(gòu)建的網(wǎng)絡(luò)可以預(yù)測出大部分真實(shí)網(wǎng)絡(luò)，算法準(zhǔn)確無誤地預(yù)測出8條邊，僅遺漏掉了6—4、4—9兩條邊，有3條冗余的邊。表1給出了算法優(yōu)化前后構(gòu)建網(wǎng)絡(luò)的各種指標(biāo)性能評(píng)價(jià)，從表中可以看出算法優(yōu)化降噪前，網(wǎng)絡(luò)有較高的真陽率90%，同樣假陽率也較高為18.8%，能反映網(wǎng)絡(luò)整體性能的精確度指標(biāo)為82.2%；而經(jīng)過算法優(yōu)化降噪后網(wǎng)絡(luò)的假陽率降低至3.7%，網(wǎng)絡(luò)的精確度高達(dá)94.4%，可見逐步優(yōu)化降噪的方法可以提高網(wǎng)絡(luò)構(gòu)建的準(zhǔn)確率和精度。為了進(jìn)一步說明算法的性能，給出了網(wǎng)絡(luò)構(gòu)建的ROC曲線如圖4所示，反映網(wǎng)絡(luò)構(gòu)建綜合性能指標(biāo)AUROC的值達(dá)到0.908。綜上所述，各種性能指標(biāo)反映了基于信息論的優(yōu)化降噪方法在網(wǎng)絡(luò)構(gòu)建中有很好的性能。

表1 構(gòu)建網(wǎng)絡(luò)ROC曲線圖

文中提出的基于信息論的微分方程優(yōu)化降噪方法對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行復(fù)雜網(wǎng)絡(luò)構(gòu)建，通過實(shí)驗(yàn)驗(yàn)證了其良好的性能，主要?dú)w因于以下特征。首先，信息論的方法在構(gòu)建網(wǎng)絡(luò)中濾除了一些噪聲，使得后面的優(yōu)化更為精確，這也是算法保持高效性能的關(guān)鍵步驟。其次，算法用信息論方法集合了網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)間的線性和非線性關(guān)系，最后的微分方程優(yōu)化模型檢測了數(shù)據(jù)的線性成分，使得數(shù)據(jù)間的線性和非線性關(guān)系充分互補(bǔ)，提高算法性能。但方法也存在一些不足，一些數(shù)據(jù)間特殊的非線性三角函數(shù)關(guān)系，算法無法識(shí)別檢測，這也是以后考慮的方向。

3 結(jié)束語

文中提出了一種基于信息論的優(yōu)化降噪方法，該方法能夠去除噪聲和冗余來提高復(fù)雜網(wǎng)絡(luò)構(gòu)建的準(zhǔn)確性。網(wǎng)絡(luò)中相關(guān)性較小的邊可以通過信息論的方法來檢測濾除，而一些冗余的邊信息可以通過微分方程優(yōu)化降噪來篩除，從而進(jìn)一步提高網(wǎng)絡(luò)構(gòu)建的精度。通過實(shí)驗(yàn)數(shù)據(jù)的模擬仿真，算法表現(xiàn)出良好的性能，網(wǎng)絡(luò)的構(gòu)建準(zhǔn)確率和精度都非常高。實(shí)驗(yàn)各種性能參數(shù)指標(biāo)都證明了算法設(shè)計(jì)的合理性和方法的有效性。

[ 1 ] GIACOMANTONIO C E, GOODHILL G J. A Boolean model of the gene regulatory network underlying Mammalian cortical area development[J]. PLoS computational biology, 2010, 6(9): e1000936.

[ 2 ] HERRMANN F, GRO B A, ZHOU D, et al. A boolean model of the cardiac gene regulatory network determining first and second heart field identity[J]. PloS one, 2012, 7(10): e46798.

[ 3 ] NOMAN N,PALAFOX L, IBA H. Inferring genetic networks with a recurrent neural network model using differential evolution[M]. Springer Handbook of Bio-/Neuroinformatics. Springer Berlin Heidelberg, 2014.

[ 4 ] WATANABE Y,SENO S, TAKENAKA Y, et al. An estimation method for inference of gene regulatory net-work using Bayesian network with uniting of partial problems[J]. BMC genomics, 2012, 13(Suppl1): S12.

[ 5 ] YOUNG W C, RAFTERY A E, YEUNG K Y. Fast bayesian inference for gene regulatory networks using scanBMA[J]. BMC Systems Biology, 2014, 8(1): 47.

[ 6 ] TIBSHIRANI R. Regression shrinkage and selection via the lasso[J]. Journal of the Royal Statistical Society:Series B (Statistical Methodology), 1996: 267-288.

[ 7 ] FAITH J J,HAYETE B, THADEN J T, et al. Large-scale mapping and validation of Escherichia coli transcriptional regulation from a compendium of expression profiles[J]. PLoS biology, 2007, 5(1): e8.

[ 8 ] ZHANG X, ZHAO X M, HE K, et al. Inferring gene regulatory networks from gene expression data by path consistency algorithm based on conditional mutual information[J]. Bioinformatics, 2012, 28(1): 98-104.

[ 9 ] MARBACH D, PRILL R J, SCHAFFTER T, et al. Revealing strengths and weaknesses of methods for gene network inference[J]. Proceedings of the National Academy of Sciences, 2010, 107(14): 6286-6291.

[10] BASSO K,MARGOLIN A A, STOLOVITZKY G, et al. Reverse engineering of regulatory networks in human B cells[J]. Nature genetics, 2005, 37(4): 382-390.

[11] WANG R, JIN G, ZHANG X, et al.Modeling post-transcriptional regulation activity of small non-coding RNAs in Escherichia coli[J]. BMC Bioinformatics, 2009, 10:S6.

A Research on Optimal Noise Reduction Methods Based on Information Theory

LIU Fei
(Department of Physics and Information Technology,Baoji University of Arts and Sciences,Baoji Shaanxi 721016, China)

Reconstruction of complex networks can disclose the potential control relationship among network nodes and help us better understand the complex regulatory mechanisms among them. Thus, lots of theoretical and computational approaches have been introduced for network construction. Due to the high-dimensional low-sample characteristics of data and the noise inherited in it, however, these approaches have a high false positive rate during network construction. To overcome this disadvantage, this paper presents a new method, which combines mutual information theory and ordinary differential equation to optimize noise reduction. Edges with low correlation in the network can be detected and removed in the methods based on the information theory, while redundant edge information can be screened out through noise reduction optimization realized by differential equation, so that the accuracy of network construction may be further improved. The algorithm is verified through simulation of DREAM (Dialogue for Reverse Engineering Assessments and Methods). The results indicate that our algorithm has a quite high accuracy and low false positive rate in the course of construction of complex networks.

complex network; network construction; information theory; progressive optimization; noise reduction

寶雞市科技計(jì)劃項(xiàng)目資助(2013R5-5,15Rkx-1-5-18)

10.3969/j.issn.1000-3886.2015.05.009

TP391

A

1000-3886(2015)05-0025-02

劉飛，男(1981-)，陜西榆林人,碩士，講師，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)和數(shù)據(jù)挖掘。

定稿日期: 2014-10-13