一種估計最大信息系數(shù)閾值最優(yōu)取值的方法

摘? 要：為了簡化最大信息系數(shù)計算的復(fù)雜度，達到計算準(zhǔn)確性與計算復(fù)雜度的最優(yōu)平衡，通過基因與疾病相關(guān)性實驗研究了最大信息系數(shù)閾值的合適取值區(qū)間及最優(yōu)取值。結(jié)果表明：利用變量間強相關(guān)數(shù)據(jù)和不相關(guān)數(shù)據(jù)出現(xiàn)的頻數(shù)，及其在不同閾值下的變化趨勢，可以估計出閾值的合適取值區(qū)間；通過統(tǒng)計閾值取值區(qū)間上界集合的最小值，可以估計閾值的最優(yōu)取值；對于不同變量，閾值的最優(yōu)取值也不相同，并且隨著采樣數(shù)的增大，閾值的最優(yōu)取值有減小的趨勢。

關(guān)鍵詞：最大信息系數(shù)；互信息；相關(guān)性；閾值；最小最大策略

中圖分類號：TP311.1；TP311? 文獻標(biāo)識碼：A? 文章編號：2096-4706（2023）24-0077-05

A Method for Estimating the Optimal Value of Threshold of Maximum Information Coefficient

TAN Zaowen

（Academy of National Space Planning， Hualan Design （Group） Co.， Ltd.， Nanning? 530011， China）

Abstract： In order to simplify the computational complexity of the maximum information coefficient and achieve the optimal balance between computational accuracy and computational complexity， the correlation experiment between genes and diseases is used to investigate the appropriate value interval and optimal value of the threshold of the maximum information coefficient. The results show that the appropriate value interval of the threshold can be estimated by using the frequency of strongly correlated data and uncorrelated data between variables and the variation trend under different thresholds. By calculating the minimum value of the upper bound set of threshold values， the optimal threshold value can be estimated; for different variables， the optimal value of the threshold is not the same， and with the increase of the number of samples， the optimal value of the threshold tends to decrease.

Keywords： maximum information coefficient; mutual information; correlation; threshold; Min-Max strategy

0? 引? 言

最大信息系數(shù)（Maximum Information Coefficient， MIC）由Reshef [1]等人在2011年提出，用于解決變量之間的相關(guān)性問題。與傳統(tǒng)方法相比，最大信息系數(shù)具有通用性和公平性的特點，包括：1）對復(fù)雜系統(tǒng)具有適應(yīng)性，能夠識別變量之間的線性以及非線性關(guān)系；2）泛化能力強，對不完整或有噪聲的數(shù)據(jù)有著抗干擾的能力；3）具有能夠分析先驗信息的潛力；4）可以對不同類型的數(shù)據(jù)進行分析，而無須對數(shù)據(jù)的統(tǒng)計分布（如正態(tài)性）進行假設(shè)[2]。最大信息系數(shù)方法的提出，很好地解決了皮爾森相關(guān)系數(shù)不能用于非線性相關(guān)變量之間相關(guān)性的問題。

然而作為一種計算機密集型方法，最大信息系數(shù)很難使用手動或者計算器的方式計算得出[3]，即使當(dāng)前計算機的計算能力已經(jīng)有了很大的提高，想要計算變量之間的最大信息系數(shù)的確切值仍然十分困難。隨著變量數(shù)據(jù)規(guī)模的提升，計算最大信息系數(shù)所需要迭代的次數(shù)將大幅提升，計算的時間復(fù)雜度也將迅速增長。

不少學(xué)者通過各種方式對最大信息系數(shù)進行算法優(yōu)化，并取得一定程度的效果。曹丹提出了最大信息系數(shù)優(yōu)化估計算法BackMIC[4]，該算法使得網(wǎng)格劃分更合理，最大信息系數(shù)的估計值更加準(zhǔn)確，具有更出色的統(tǒng)計效率和等價性。曹珊將最大信息系數(shù)與改進的和聲算法結(jié)合，提出了兩階段特征選擇方法MIC-MHS[5]，該算法能夠得到更小的子集，并且能夠更高的分類準(zhǔn)確率。王月將最大信息系數(shù)與K-means聚類算法相結(jié)合，提出了適用于海量數(shù)據(jù)集的MIC聚類算法[6]，提升了計算效率。孟燕霞提出了一種基于動態(tài)均分的最大信息系數(shù)算法DE-MIC[7]，具有更快的計算速度與更好的效率，同時保持了MIC算法原有的均勻性、普適性。郭園園基于最大相關(guān)最小冗余（mRMR）提出了新算法mRMR-ChiMIC[8]，其提取的特征相比于原算法擁有更高的分辨率，同時降低了計算復(fù)雜度。邵福波提出了針對大規(guī)模數(shù)據(jù)的最大信息系數(shù)快速算法[9]，使得計算時間更短。劉漢明利用全基因關(guān)聯(lián)性研究，提出了MICSNPs、mBoMIC等多種算法[10]，克服了最大信息系數(shù)的不足。朱道恒等提出了一種最大信息系數(shù)并行算法PCMIC[11]，旨在解決大規(guī)模數(shù)據(jù)下MIC計算時間復(fù)雜度高的問題。

為了使最大信息系數(shù)能夠在較短時間內(nèi)計算，一個可行方法為限制互信息（MI）計算次數(shù)的上限，即閾值，從而簡化最大信息系數(shù)計算的復(fù)雜度，以得出最大信息系數(shù)的近似值。本文將通過基因與疾病之間的相關(guān)性實驗，估計最大信息系數(shù)閾值的合適取值區(qū)間及最優(yōu)取值，以達到計算準(zhǔn)確性與計算復(fù)雜度的最優(yōu)平衡。

1? 關(guān)鍵技術(shù)

1.1? 皮爾森相關(guān)系數(shù)

皮爾森相關(guān)系數(shù)（Pearson correlation coefficient）可以用來計算兩個變量之間的相關(guān)性[12]。對于兩個變量的采樣X = {x1，x2，…，xn}，Y = { y1，y2，…，yn}，變量的皮爾森相關(guān)系數(shù)ρxy為：

為了表示方便，也可以使用皮爾森相關(guān)系數(shù)的平方? 來表示變量間的相關(guān)性。但皮爾森相關(guān)系數(shù)適合用來計算線性相關(guān)變量之間的相關(guān)性，并不能很好地表達出非線性相關(guān)變量之間的相關(guān)性。而最大相關(guān)系數(shù)可以解決這一問題，能夠同時計算線性相關(guān)和非線性相關(guān)變量之間的相關(guān)性。

1.2? 最大信息系數(shù)

最大信息系數(shù)是基于互信息[13]（Mutual Information）提出的一種算法。對于兩個變量的采樣X = {x1，x2，…，xn}，Y = { y1，y2，…，yn}之間的互信息I （X;Y）為：

式（2）為連續(xù)型變量的情況下互信息的計算方法，對于離散型變量，互信息Inavive{x; y}的計算公式為[2]：

把所有的（xi，yi）采樣放置到坐標(biāo)系平面中，將平面沿y方向和x方向分割成nx列和ny行。式（3）中， 表示第i列第j行網(wǎng)格中的散點數(shù)量占散點圖中所有散點數(shù)量的比例， 表示第i列中的散點數(shù)量占散點圖中所有散點數(shù)量的比例， 表示第j行中的散點數(shù)量占散點圖中所有散點數(shù)量的比例。

最大信息系數(shù)基于互信息的方法，將式（3）改進為式（4）[2]：

其中，nx和ny分別表示分割成的網(wǎng)格的列數(shù)與行數(shù)， 表示分成的網(wǎng)格為nx列和ny行時，最大的互信息值，即分成nx列nyny行的網(wǎng)格后，調(diào)整行、列之間的距離，找到一個最大的互信息值。

用mx， y表示分成的網(wǎng)格為nx列ny行時的最大信息系數(shù)，則最終的最大信息系數(shù)為[2]：

其中，N為散點數(shù)量，α為閾值，取值為（0，1]。α的取值越大，最大信息系數(shù)越準(zhǔn)確，但計算復(fù)雜度也會大幅上升，因此有必要將α限制在一個合適的區(qū)間里，以達到計算準(zhǔn)確性與計算復(fù)雜度的最優(yōu)平衡。

1.3? 最大信息系數(shù)網(wǎng)格分割過程

由上一章節(jié)可以看出，在求最大信息系數(shù)的過程中，需要對采樣所在的坐標(biāo)系平面沿y方向和x方向進行分割，從而計算互信息值。如圖1所示：

從圖1可以看出，坐標(biāo)系平面沿y方向和x方向被分割成2×2的網(wǎng)格，以下稱為m2，2，其中不同顏色的線代表不同的網(wǎng)格分割方法（圖1中只展示出其中3種劃分方法）。我們需要找到m2，2下使得互信息取得最大值的劃分方法，進而求出m2，2對應(yīng)的最大信息系數(shù)MIC2，2{x，y}。

然后將坐標(biāo)系平面沿y方向和x方向分割成2×3（或3×2）的網(wǎng)格，即m2，3（或m3，2），并求出其最大信息系數(shù)MIC2，3{x，y}（或MIC3，2{x，y}）。以此類推，直到nx ny = N α為止。最后，找到所有最大信息系數(shù)中的最大值，作為最終的最大信息系數(shù)，即式（5）所示。

2? 實驗分析

2.1? 實驗數(shù)據(jù)

本文利用基因與疾病之間的相關(guān)性實驗，來估計最大信息系數(shù)閾值α的最優(yōu)取值。

本實驗使用的數(shù)據(jù)存放在csv文件中。文件每一行表示一種基因，列上有多種疾病的探針采樣，有患病的和未患病的采樣作為對照?？梢詮牧袠?biāo)簽看出，N前綴表示未患病，T前綴表示患病。后綴數(shù)字表示同一種疾病的不同采樣。每個采樣（列）中，不同基因的表達程度可以從單元格中讀出。

需要對每個基因、每種疾病分別進行最大信息系數(shù)的計算。對于某種基因、疾病，將患病狀態(tài)作為y值，0表示未患病，1表示患病，將對應(yīng)的基因表達程度采樣值作為x。如表1所示（此處僅列出部分?jǐn)?shù)據(jù)）。

表1展示了UT疾病的部分基因表達數(shù)據(jù)，每行表示不同的基因，N前綴列表示未患UT疾病的采樣，即對照組，T前綴列表示患UT疾病的采樣。表中的數(shù)值表示某個基因在對應(yīng)采樣中的表達程度，數(shù)值越高，表達程度越明顯。

表1的第二行表示該列采樣是否患病，1為是，0為否。對該疾病的基因畫散點圖，一般會有以下幾種情況，如圖2所示。

從圖2中很難直觀地得出基因與疾病之間的相關(guān)性程度，但可以根據(jù)圖中散點的分布情況得出，在基因與疾病之間具有較強相關(guān)性的情況下，它們的關(guān)系是正相關(guān)還是負(fù)相關(guān)。具體方法如下：設(shè)P = { pr，i | i ∈ [1，nr]，r = 0，1}為某個基因相對于某個疾病的散點圖上所有的點，例如圖2所示，每個散點表示一個探針。其中r = 0，1分別表示未患病和患病的類別標(biāo)簽，nr表示該類別的探針數(shù)量。令 ，表示類別為未患病的所有探針的表達程度平均值，，表示類別為患病的所有探針的表達程度平均值。如果 ，則該基因與該疾病的相關(guān)性為正相關(guān)；反之，如果 ，則該基因與該疾病的相關(guān)性為負(fù)相關(guān)。值得注意的是，從本質(zhì)上來說，當(dāng) 時，基因與疾病之間的關(guān)系應(yīng)為無關(guān)，或相關(guān)性不大，但這里僅僅討論如何區(qū)分正負(fù)相關(guān)性，基因與疾病是否相關(guān)，或者相關(guān)的程度，應(yīng)通過計算最大信息系數(shù)得出。

部分基因的散點圖與圖2中的EAM185類似，患病狀態(tài)為0的點的平均值 ，在患病狀態(tài)為1的點的平均值? 的左側(cè)，即 ，可以認(rèn)為該基因與疾病之間的相關(guān)性為正相關(guān)。部分基因的散點圖與圖2中的EAM192類似，患病狀態(tài)為0的點的平均值 ，在患病狀態(tài)為1的點的平均值? 的右側(cè)，即 ，可以認(rèn)為該基因與疾病之間的相關(guān)性為負(fù)相關(guān)。部分基因的散點圖與圖2中的EAM103類似，患病狀態(tài)為0的點的平均值 ，與患病狀態(tài)為1的點的平均值? 近似，即 ，可以認(rèn)為該基因與疾病無關(guān)，或相關(guān)性不大。

2.2? 最大信息系數(shù)和閾值的關(guān)系

仍以UT疾病下，EAM103、EAM185、EAM192這三個基因舉例，觀察最大信息系數(shù)的結(jié)果和閾值 的關(guān)系。我們將 在 之間，每隔一小段距離取一個值，計算該值下這三個基因的最大信息系數(shù)，獲得基因與疾病間的最大信息系數(shù)隨閾值 變化的情況。如圖3所示。

從圖3中可以看出，EAM103基因最終的最大信息系數(shù)較低，為0.656，這印證了2.1章節(jié)所述的假設(shè)，EAM103基因和UT疾病的相關(guān)性不大；EAM185基因、EAM192基因最終的最大信息系數(shù)較高，分別為0.808、0.998，這也印證了2.1章節(jié)所述的假設(shè)，EAM185基因、EAM192基因和UT疾病有較強的相關(guān)性。從原始數(shù)據(jù)中還可以看出，EAM185基因與UT疾病之間的相關(guān)性為正相關(guān)，EAM192基因與UT疾病之間的相關(guān)性為負(fù)相關(guān)。

結(jié)合圖3中的三條折線，還可以推斷出，當(dāng)閾值α取值較小時，最大信息系數(shù)的取值也較小，并且?guī)缀醪蛔兓划?dāng)α大于某個值時，最大信息系數(shù)開始變化并增大；當(dāng)α繼續(xù)增大，再次超過某個值時，最大信息系數(shù)的增長達到極限，此時的最大信息系數(shù)為最終的、也是最準(zhǔn)確的最大信息系數(shù)。

可以看出，當(dāng)閾值α增大到某個程度時，繼續(xù)增大閾值，最大信息系數(shù)的變化程度將變得不明顯，但此時的計算復(fù)雜度仍然在明顯增大。因此，有必要為閾值α確定一個合適的取值。

2.3? 閾值的合適取值區(qū)間估計

本文使用以下方法估計閾值α的合理取值。

記nx為橫坐標(biāo)的網(wǎng)格數(shù)，ny為縱坐標(biāo)劃分的網(wǎng)格數(shù)，B表示最大的網(wǎng)格總數(shù)即nxny≤B，其為樣本數(shù)量的函數(shù)，記B = N α，N為樣本數(shù)量，α為閾值參數(shù)。對于閾值α，Reshef等人[1]只提供了參考的經(jīng)驗值0.60或0.55，但網(wǎng)格的疏密度會直接影響到最優(yōu)的最大信息系數(shù)值，因此對于不同的樣本，需要估計不同的閾值α，從而提高最大信息系數(shù)的最優(yōu)度。

假定當(dāng)最大信息系數(shù)值小于0.1時，X和Y是不相關(guān)，該條件下記為A1，當(dāng)MIC值大于0.9時，X和Y是強相關(guān)，此條件下記為A2。仍然使用UT疾病數(shù)據(jù)，統(tǒng)計出A1和A2在不同的閾值α ∈ [0.2，1.0]下對應(yīng)的基因出現(xiàn)頻數(shù)。如圖4所示。

從圖4中可以看出，在α = 0.6時，A1對應(yīng)的基因頻數(shù)開始有下降的趨勢，而A2對應(yīng)的基因頻數(shù)則開始出現(xiàn)上升的趨勢，在α = 0.73時，二者有一個交點，繼續(xù)增大α，A1狀態(tài)變化不明顯。因此可以認(rèn)為在該樣本下，閾值α設(shè)置在[0.6，0.73]之間是比較合適的。

2.4? 閾值的最優(yōu)取值估計

在估計出閾值α合適的取值區(qū)間后，本文還將繼續(xù)探討如何估計閾值α的最優(yōu)取值。

對某一疾病下，所有基因的最大信息系數(shù)在閾值α ∈ [0.2，1.0]的范圍內(nèi)進行迭代，獲得所有的基因與該疾病的最大信息系數(shù)閾值α的取值區(qū)間。由于最大信息系數(shù)隨α變化的曲線并不平滑，本文使用如下方法求出閾值α的取值區(qū)間：

對于每個基因，以最大信息系數(shù)開始變化的值作為閾值α的取值區(qū)間下界αmin，以最大信息系數(shù)停止變化的值作為閾值α的取值區(qū)間上界αmax，則區(qū)間[αmin，αmax]即為所求的閾值α的取值區(qū)間。仍以UT疾病為例，部分?jǐn)?shù)據(jù)表2所示。

由于不同基因之間的閾值α取值區(qū)間下界αmin過于近似，本文使用閾值α取值區(qū)間上界αmax的最小值，即最小最大策略，作為閾值α的最優(yōu)取值，結(jié)果為0.61。

對其他疾病也進行同樣的實驗，獲得更多的閾值α最優(yōu)取值，仍然使用最小最大策略，結(jié)果如表3所示。

從表3中可以看出，不同疾病下，閾值α的最優(yōu)取值也不相同。并且隨著采樣數(shù)的增大，閾值α的最優(yōu)取值有減小的趨勢。

3? 結(jié)? 論

最大信息系數(shù)之所以近年來才被發(fā)現(xiàn)，是因為它實際上是為大數(shù)據(jù)而生的一種典型的計算機密集型方法的應(yīng)用，旨在加強大數(shù)據(jù)下的統(tǒng)計相關(guān)性研究。

本文利用基因與疾病之間的相關(guān)性實驗，估計出最大信息系數(shù)閾值α的合適取值區(qū)間及最優(yōu)取值，并得到如下結(jié)論：1）最大信息系數(shù)具有很好的廣泛性和均勻性，能夠識別變量之間的非線性以及非線性關(guān)系；2）對最大信息系數(shù)閾值α進行合理的取值，能夠達到計算準(zhǔn)確性與計算復(fù)雜度的最優(yōu)平衡；3）利用變量間強相關(guān)數(shù)據(jù)和不相關(guān)數(shù)據(jù)出現(xiàn)的頻數(shù)，在不同閾值α下的變化趨勢，可以估計出閾值α的合適取值區(qū)間；4）通過統(tǒng)計閾值α的取值區(qū)間上界集合的最小值，可以估計閾值α的最優(yōu)取值；5）對于不同變量，閾值α的最優(yōu)取值也不相同。并且隨著采樣數(shù)的增大，α的最優(yōu)取值有減小的趨勢。

參考文獻：

[1] RESHEF D N，RESHEF Y A，F(xiàn)INUCANE H K，et al. Detecting novel associations in large data sets [J].science，2011，334（6062）：1518-1524.

[2] 武利園，潘宇霖，陳開宇，等.基于最大互信息系數(shù)的城市節(jié)水驅(qū)動因素分析 [J].人民黃河，2023，45（1）：87-92.

[3] 孟燕霞，郭禹辰，王莉.一種基于動態(tài)均分的最大信息系數(shù)改進算法 [J].山東大學(xué)學(xué)報：工學(xué)版，2019，49（5）：105-111.

[4] 曹丹.最大信息系數(shù)優(yōu)化算法及在生物信息學(xué)中的應(yīng)用 [D].長沙：湖南農(nóng)業(yè)大學(xué)，2020.

[5] 曹珊.最大信息系數(shù)與改進的和聲算法相融合的特征選擇方法 [D].長春：吉林大學(xué)，2020.

[6] 王月.最大信息系數(shù)的算法分析及改進 [D].西安：西安電子科技大學(xué)，2019.

[7] 孟燕霞.最大信息系數(shù)算法研究 [D].太原：太原理工大學(xué)，2019.

[8] 郭園園.基于互信息的信息基因選擇算法研究 [D].長沙：湘潭大學(xué)，2018.

[9] 邵福波.最大信息系數(shù)改進算法及其在鐵路事故分析中的應(yīng)用 [D].北京：北京交通大學(xué)，2016.

[10] 劉漢明.基于最大信息系數(shù)的復(fù)雜疾病全基因組關(guān)聯(lián)算法研究 [D].成都：電子科技大學(xué)，2015.

[11] 朱道恒，李志強.最大互信息系數(shù)的并行計算方法研究 [J].科學(xué)技術(shù)與工程，2021，21（34）：14625-14633.

[12] 尹歡一.基于皮爾森系數(shù)距離權(quán)重KNN算法的P2P流量分類方法研究 [D].株洲：湖南工業(yè)大學(xué)，2019.

[13] 閔捷.基于互信息極大化的多時相遙感影像分類算法研究 [D].西安：西安電子科技大學(xué)，2022.

作者簡介：譚藻文（1993—），男，漢族，廣西南寧人，系統(tǒng)分析師，碩士，研究方向：計算機技術(shù)、數(shù)據(jù)挖掘、人工智能、地理信息系統(tǒng)。