一種估計最大信息系數閾值最優取值的方法

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

關鍵詞：最大信息系數；互信息；相關性；閾值；最小最大策略

中圖分類號：TP311.1；TP311? 文獻標識碼：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? 引? 言

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

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

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

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

1? 關鍵技術

1.1? 皮爾森相關系數

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

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

1.2? 最大信息系數

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

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

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

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

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

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

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

1.3? 最大信息系數網格分割過程

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

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

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

2? 實驗分析

2.1? 實驗數據

本文利用基因與疾病之間的相關性實驗，來估計最大信息系數閾值α的最優取值。

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

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

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

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

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

部分基因的散點圖與圖2中的EAM185類似，患病狀態為0的點的平均值 ，在患病狀態為1的點的平均值? 的左側，即 ，可以認為該基因與疾病之間的相關性為正相關。部分基因的散點圖與圖2中的EAM192類似，患病狀態為0的點的平均值 ，在患病狀態為1的點的平均值? 的右側，即 ，可以認為該基因與疾病之間的相關性為負相關。部分基因的散點圖與圖2中的EAM103類似，患病狀態為0的點的平均值 ，與患病狀態為1的點的平均值? 近似，即 ，可以認為該基因與疾病無關，或相關性不大。

2.2? 最大信息系數和閾值的關系

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

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

結合圖3中的三條折線，還可以推斷出，當閾值α取值較小時，最大信息系數的取值也較小，并且幾乎不變化；當α大于某個值時，最大信息系數開始變化并增大；當α繼續增大，再次超過某個值時，最大信息系數的增長達到極限，此時的最大信息系數為最終的、也是最準確的最大信息系數。

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

2.3? 閾值的合適取值區間估計

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

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

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

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

2.4? 閾值的最優取值估計

在估計出閾值α合適的取值區間后，本文還將繼續探討如何估計閾值α的最優取值。

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

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

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

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

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

3? 結? 論

最大信息系數之所以近年來才被發現，是因為它實際上是為大數據而生的一種典型的計算機密集型方法的應用，旨在加強大數據下的統計相關性研究。

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

參考文獻：

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

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

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

[4] 曹丹.最大信息系數優化算法及在生物信息學中的應用 [D].長沙：湖南農業大學，2020.

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

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

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

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

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

[10] 劉漢明.基于最大信息系數的復雜疾病全基因組關聯算法研究 [D].成都：電子科技大學，2015.

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

[12] 尹歡一.基于皮爾森系數距離權重KNN算法的P2P流量分類方法研究 [D].株洲：湖南工業大學，2019.

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

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