檢測多元相關關系的最大信息熵方法

張亞紅李玉鑑 張 婷

(北京工業大學計算機學院 北京 100124)

檢測多元相關關系的最大信息熵方法

張亞紅*李玉鑑 張 婷

(北京工業大學計算機學院 北京 100124)

目前提出的用于檢測變量間相關關系的方法，如最大信息系數(Maximal Information Coefficient, MIC)，多應用于成對變量，卻很少用于三元變量或更高元變量間的相關性檢測。基于此，該文提出能夠檢測多元變量間相關關系的新方法 最大信息熵(Maximal Information Entropy, MIE)。對于k元變量，首先基于任意兩變量間的MIC值構造最大信息矩陣，然后根據最大信息矩陣計算最大信息熵來度量變量間的相關度。仿真實驗結果表明MIE能夠檢測三元變量間的1維流形依賴關系，真實數據集上的實驗驗證了MIE的實用性。

數據挖掘；多元相關；最大信息系數；最大信息熵

1 引言

相關性挖掘是數據挖掘的一個重要組成部分，其目標是發現數據集中變量間潛在的相關關系。當檢測數據集中成對變量間的相關關系時，通常需要對成千上萬對的變量進行檢測，對于人工來說這是不可行的，由此人們提出了大量的用于檢測變量間相關關系的方法。最常用于檢測變量間線性相關的方法為Pearson相關系數，可定義為兩個變量的協方差與二者標準差積的商，通常用r或ρ表示，其取值范圍在[-1, 1]之間，絕對值越大表明變量間正(負)線性相關性越強。Pearson相關系數僅對變量間的線性依賴關系敏感，不具有通用性，然而在實際數據分析中，變量間的相關可以是任意的線性或非線性函數關系，以及更為復雜的統計依賴關系。由于對于存在相關關系的變量，Pearson系數通常也為0，即Pearson相關系數為0并不意味著兩個變量在統計意義上獨立。文獻[1, 2]介紹了一種檢測兩個隨機變量或向量(兩向量可以不同維)間相關關系的方法 距離相關，任意兩個隨機變量的距離相關可由它們的距離協方差除以它們的標準距離方差的乘積得到，當且僅當兩個隨機變量在統計意義上獨立時，距離相關才為0，該方法能夠很好地檢測變量間的線性和非線性相關關系。然而，距離相關在所有的噪聲模型實驗中表現出高度的不公平性，即具有不同的函數依賴形式的數據都加上類似的噪音，其相關性評分就會差別很大。另一方面互信息提供了一種通用的衡量兩個變量間相關性的度量。文獻[3-5]分別應用B樣條方法、直方圖法以及密度估計方法來估算變量間的互信息試圖發現試驗數據中變量間的相關關系，但都不具有良好的通用性和公平性。文獻[6]介紹了一種以互信息為基礎的在大型數據集中發現潛在相關關系的統計方法 最大信息系數(Maximal Information Coefficient, MIC)，該方法能快速通過給不同類型相關進行評估，從而發現廣泛范圍的相關關系類型。與當前的變量相關性檢測方法相比，MIC同時具有通用性和公平性，即無論數據是怎樣分布的，不限于特定的相關函數類型，MIC都有效；計算的MIC值和噪音的程度有關，與相關的類型無關。MIC可能是世界上目前最好的相關性檢測方法，被稱為21世紀的相關性[7]。事實上，將MIC應用于世界衛生數據、棒球統計數據、酵母菌基因表達數據及一組人類腸道中細菌豐度的數據中確實發現了已知的和新奇的變量相關關系。此外，MIC還被廣泛地應用于基因組學[8]，蛋白質組學[9]，微生物學[10]，傳感器[11]以及臨床數據分析[12,13]等領域。

多元變量間相關性研究還比較少，主要有非線性相關信息熵[14](Nonlinear Correlation Information Entropy, NCIE)方法和距離相關t-檢驗[15](distance correlation t test)法。NCIE是一種無參數檢測多元變量相關關系的方法，計算簡單，且易于理解。通過將數據點均勻地分成幾部分來估計任意兩變量間的互信息，從而構造信息矩陣以計算多元變量間的非線性相關信息熵。NCIE雖然能夠用0到1之間的值來衡量變量間的相關性但卻不具有良好的通用性(如表1所示)，而且高維數據空間經常出現的稀疏數據分布會大大降低該方法的可靠性。距離相關t-檢驗法通過擴展距離相關的方法來檢驗高維空間隨機向量的獨立性，與NCIE相比，該方法能夠高效地檢測出隨機向量中的相關性，但同時計算復雜度也很高，且該方法僅適用于樣本維度遠大于樣本點個數的情況。

本文以MIC能夠很好地檢測成對變量間的線性和非線性依賴關系，但卻不能直接用于多元變量間的相關性分析為出發點，基于MIC，提出了能夠檢測多元變量間相關關系的最大信息熵(Maximal Information Entropy, MIE)方法。對于k元變量集合，首先根據任意兩個變量間的MIC值來構造最大信息矩陣R，然后由R的正特征根來計算這k個變量間的最大信息聯合熵，最后用1-來衡量變量間的相關度。MIE的取值范圍為[0, 1]，其中0和1分別表示最弱和最強的相關。

本文的組織結構如下：第2節介紹了最大信息系數(MIC)；第3節提出了最大信息熵(MIE)方法；第4節通過3維空間曲線上的仿真實驗說明MIE能夠有效地檢測三元變量間1維流形依賴關系，此外，本文還將MIE應用于全球健康數據的分析，進一步評價其分析真實數據的有效性和可行性；最后為總結和討論。

2 最大信息系數(MIC)

MIC為檢測兩元變量間相關關系的統計量，其依據的理念是：如果變量X和Y之間存在著一種相關關系，那么就應該能夠在變量的散點圖上畫一個網格，使得大多數的數據點集中在該網格的幾個單元格中。通過搜尋這種“最適合”的網格，MIC可發現變量間廣泛范圍的相關關系。

給定一有限兩元數據集合D，可按數據的x-和y-值把數據集D劃分到不同的x行或y列中，其中允許某些行或列為空，這樣一組劃分稱為x-by-y 網格G(grid)。D|G為集合D在G上的概率分布，其中任意一個格子內的概率密度函數值為這個格子內所包含的樣本點數量占全體樣本點的比例。對于固定的數據集合D，在不同的網格G劃分下有不同的分布D|G。這里本文給出MIC的定義：

定義1 給定一個有限兩元變量的數據集D，設G為一x-by-y劃分，I(D|G)為集合D在劃分G下的互信息，則

其中max取遍所有可能的x-by-y網格G。

定義2 給定一個有限兩元變量的數據集D，設n為數據集大小，x, y為大于1的正整數，則MIC可定義為

其中B為可搜尋網格的上界，控制了MIC能夠檢測的相關關系的復雜度，在文獻[6]中作者默認設置B=n0.6。

MIC以互信息來評價每個網格劃分的好壞，再對得到的互信息值進行歸一化處理，保證MIC的值在0到1之間。事實上，對于任意變量對(X, Y), MIC有如下3個性質：(1)如果Y為X的函數，且在任意的開區間不是常數，則隨著樣本數的增加，MIC必然趨于1; (2)如果X和Y是從形如c(t)=[x(t), y(t), z(t)]的可微空間曲線上抽取的，且dx/dt, dy/dt和dz/dt只在有限點為0，則隨著樣本點的增加，MIC必然趨于1; (3)如果X和Y在統計意義上獨立，則隨著樣本點的增加，MIC必然趨于0。

3 最大信息熵(MIE)

對于k元變量數據集{X1, X2,…,Xk}, k＞2，本文可根據MIC來計算任意兩個變量間的相關度，由此可構建這k個變量的最大信息矩陣R。

最大信息矩陣R的對角元素表示k個變量中每個變量的自相關，由于有MIC(X, X)=1，所以ri, j= 1,{i=j,1≤i, j≤k }；矩陣中的其他元素為不同變量間的最大信息系數，因為0≤MIC≤1，所以0≤故綜上所述可知最大信息矩陣R為對角元素全為1且其他元素值在0到1之間的實對稱矩陣。當k個變量中的任意兩個變量在統計意義上相互獨立，即R為單位矩陣，在這種情況下，k個變量間存在最弱的相關關系；當k個變量中的任意兩個變量都有≤k }, R為全1矩陣，在這種情況下，k個變量間存在著最強的相關關系。也就是說k元變量的最大信息矩陣R能夠反映這k個變量間的相關度。給定一有限數據集合D={X1, X2,…,Xk}以及對應的最大信息矩陣R，我們可定義集合D的信息聯合熵為

直觀上來說，MIE是MIC從2維平面到高維空間的一種推廣。給定一個有限k元變量的數據集D, MIE的計算過程可歸納為以下4步：

步驟1 計算k元變量間任意兩變量間的MIC值；

步驟2 根據計算得到的MIC值構造最大信息矩陣R，其中R中的元素為

接下來本文給出MIE的3個基本特征。(1)MIE值在0和1之間；(2)MIE是對稱的；(3)MIE具有保序變換不變性。這些特征的詳細描述如下：

特征1 對于任意的k (k＞2)元變量集合{X1,

證明 λiR為k元變量的最大信息矩陣R的正特征根，則有0＜λiR，且根據矩陣特征根理論有已知在x∈(0,1]的區間上-xlogx

k在x=1/e處取得最大值，故有

當k個變量中的任意兩個變量在統計意義上相互獨立，即最大信息矩陣R為單位矩陣，{i=1,2,…,k }，由式(5)可知MIE=0。當k個變量中任意兩個變量間都有MIC(Xi, Xj)=1,{1≤i, j≤k}，即最大信息矩陣R為全1矩陣，=0, {i=1,2,…,k -1}和=k，由式(5)可知MIE=1。

特征2 對于(1,2,…,k)的任意排列組合(i, j,…,m) 有MIE(X1, X2,…,Xk)=MIE(Xi, Xj,…,Xm)。

證明 任意k元變量集合{X1, X2,…,Xk}，變量位置的變換相當于最大信息矩陣的行或列的轉置，矩陣行或列的轉置并不會改變矩陣的特征根，最大信息矩陣的特征根不變，所以MIE不變。 證畢

特征3 給定一任意k元變量集D=(X1, X2,…, Xk)，如果D′為集合D中x1-,x2-,…,xk-值的保序變換集合，則有MIE(D′)=MIE (D)。

證明 給定集合D2={Xi, Xj},{1≤i, j≤k }和它的保序變換集合，有MIC(D2′)=MIC(D2)[6]，故對k元變量集合D={X1, X2,…,Xk}做保序變換時，集合D對應的最大信息矩陣不變，即最大信息矩陣的特征根不變，所以有MIE(D′)=MIE(D)。 證畢

此外，MIE具有與MIC類似的通用性，即MIE能夠檢測多元變量間的線性和非線性相關關系。如圖1所示。對于3維空間中的經典隨機分布：均勻分布，正態分布和指數分布，它們的MIE值都很小，非常接近于0(如表1所示)。而對于3維空間中不同的1維流形依賴關系包括線性(如圖1(d))和非線性(如圖1(e)～圖1(i))依賴關系，它們的MIE值都為1(如表1所示)。

4 實驗結果與分析

在這一節本文通過在3維空間上的仿真實驗來測試MIE的通用性；為了說明MIE在分析實際數據時檢測多元變量間相關關系的實用性，本文利用世界健康衛生數據(WHO)的一個子集進行了一組應用性實驗。

4.1 通用性實驗

根據表1中定義的9種函數類型，通過均勻抽樣的方式生成無噪聲三元數據集{Di, i=1,…,9}，其中數據集的大小為10000，分別計算它們的MIE值和NCIE值(其中在NCIE的計算過程中，通過將數據點均勻地分成100份來估算變量間的互信息)。由表1不難看出，對于三元變量間不同類型的線性和非線性1維流形依賴關系，它們的MIE值都為1，而NCIE值卻不全為1。對于NCIE來說，三元變量間無噪聲的線性依賴關系的相關度要強于非線性依賴關系的相關度，且表1(d)～表1(i)的依賴關系的相關度逐漸減弱，而事實并非如此。與NCIE相比，MIE具有通用性，而且統計意義上獨立的三元變量集合的MIE值比NCIE值更接近于0。

圖1 3維空間中經典隨機分布和1維流形依賴的例子

表1 圖1中相關關系的定義以及對應的MIE值

在無噪聲的情況下，以上實驗結果驗證了MIE能夠檢測三元變量間各種不同的1維流形依賴關系。對于圖1(d)～圖1(f)中列出的每一種流形依賴關系S，本文生成大小為10000的無噪聲數據序列。接著通過對每一種依賴類型漸增地添加y-和z-方向的噪聲的方式生成其余的49個數據序列計算確定系數R2(分別計算和在y-和z-方向上的平方Pearson相關系數和，其中R2為和的最小值)以及的MIE值。圖2列出了R2分別為0.95, 0.90, 0.85, 0.80時每一種依賴關系S對應的MIE值。由圖2不難看出，隨著噪聲的增加，三元變量間的相關度逐漸減弱，它們的MIE值逐漸減小。同時這一實驗結果也驗證了本文對MIE的定義：MIE值越大，變量間的相關性越強。

4.2 實用性實驗

世界健康衛生數據(WHO)包含世界衛生組織及其合作伙伴[16, 17]所提供的社會、經濟、健康和政治指標等數據。該數據集的二元依賴關系已經用MIC分析過[6]，這里本文主要應用MIE分析其中三元變量間的相關關系。在分析時，本文只選擇了其中的一個子集，由43個變量構成。這43個變量是文獻[6]的表S9提供的，共包含12341個三元組。圖3(a)是實驗得到的MIE值直方圖結果，其中MIE值大于0.5的三元組共有924個，占 7.5%。圖3(b)～圖3(h)給出了若干根據MIE值挑選的相關關系，圖中擬合曲線由回歸函數產生，較好地反映了數據的變化趨勢。值得注意的是，圖3(e)包含兩條趨勢線，少數點構成的趨勢主要由一組高度發達的科技產業的國家組成，另一條趨勢線則由其它大多數國家組成。此外，圖3(f)包含3條趨勢線，反映了“5歲以下兒童的死亡率(1/105)”，“人均健康投入”和“人均收入”這3個變量在不同條件下存在的3種依賴關系，從中不難看出，通過增加“人均收入”或者“人均健康投入”，都有助于降低“5歲以下兒童的死亡率(1/105) ”，因此可望指導決策者制定相應的全民健康政策。圖3(h)中沒有明顯的變量相關關系，所以MIE值較小，只有0.083。

5 結束語

本文提出了一種檢測多元變量間相關關系的最大信息熵(MIE)方法。同時給出了最大信息矩陣和MIE的定義，在該定義的基礎上總結出MIE 3個基本特性：有界性、 對稱性和保序變換不變性，且MIE值越大，變量間的相關性越強。3維空間上的仿真數據實驗證實了MIE的通用性，且MIE在世界衛生真實數據集上的應用進一步證實它的實用性，而且發現了數據集中三元變量間新穎的依賴關系，所以可以說MIE對于大型數據集的相關性分析有著重要的意義。然而MIE依然面臨不公平的問題，下一步將著重于研究MIE的公平性問題。

圖2 MIE值隨著噪聲的變化

圖3 MIE在WHO子集上的部分檢測結果

[1] Székely G J, Rizzo M L, and Bakirov N K. Measuring and testing independence by correlation of distances[J]. The Annals of Statistics, 2007, 35(6): 2769-2794.

[2] Székely G J, Rizzo M L, and Bakirov N K. Brownian distance covariance[J]. The Annals of Applied Statistics, 2009, 3(4): 1236-1265.

[3] Venelli A. Efficient Entropy Estimation for Mutual Information Analysis Using B-splines[M]. Heidelberg, Berlin, Germany, Springer Berlin Heidelberg, 2010: 17-30.

[4] Silva J and Narayanan S S. On data-driven histogram-based estimation for mutual information[C]. IEEE International Symposium on Information Theory Proceedings, Austin, Texas, USA, 2010: 1423-1427.

[5] 韓敏, 梁志平. 改進型平均移位柱狀圖估算概率密度并對互信息做相關分析[J]. 控制理論與應用, 2011, 28(6): 845-850. Han Min and Liang Zhi-ping. Correlation analysis of mutual information by probability density estimated from improved averaged-shifted-histogram[J]. Control Theory and Applications, 2011, 28(6): 845-850.

[6] 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.

[7] Speed T. A correlation for the 21st century[J]. Science, 2011, 334(6062): 1502-1503.

[8] Das J, Mohammed J, and Yu H. Genome-scale analysis of interaction dynamics reveals organization of biological networks[J]. Bioinformatics, 2012, 28(14): 1873-1878.

[9] Pang C N I, Goel A, Li S S, et al.. A multi-dimensional matrix for systems biology research and its application to interaction networks[J]. Journal of Proteome Research, 2012, 11(11): 5204-5220.

[10] Koren O, Goodrich J K, Cullender T C, et al.. Host remodeling of the gut microbiome and metabolic changes during pregnancy[J]. Cell, 2012, 150(3): 470-480.

[11] Sagl G, Blaschke T, Beinat E, et al.. Ubiquitous geo-sensing for context-aware analysis: exploring relationships between environmental and human dynamics[J]. Sensors, 2012, 12(7): 9800-9822.

[12] Wang X, Duren Z, Zhang C, et al.. Clinical data analysis reveals three subytpes of gastric cancer[C]. 2012 IEEE 6th International Conference on Systems Biology, Xi’an, China, 2012: 315-320.

[13] Lin C, Can H, Miller T, et al.. Maximal information coefficient for feature selection for clinical document classication[C]. International Conference on Machine Learning (ICML) 2012, Workshop on Machine Learning from Clinical Data, Edingburgh, UK, 2012: 245-249.

[14] Wang Qiang, Shen Yi, and Zhang Jian-qiu. A nonlinear correlation measure for multivariable data set[J]. Physica D, 2005, 200(3/4): 287-295.

[15] Székely G J and Rizzo M L. The distance correlation t-test of independence in high dimension[J]. Journal of Multivariate Analysis, 2013, 117(1): 193-213.

[16] World-Health-Organization. World health organization statistical information systems (whosis)[OL]. http:// www. who.int/whosis/en/ 2009 .

[17] Rosling H, Indicators in gapminder world[OL]. http://www. gapminder.org/data/ 2008.

張亞紅： 女，1987年生，博士生，研究方向為模式識別、數據挖掘、大數據分析等.

李玉鑑： 男，1968年生，教授，博士生導師，研究方向為模式識別、圖像處理、機器學習、數據挖掘等.

張 婷： 女，1986年生，博士生，研究方向為模式識別、深度學習、大數據分析等.

Detecting Multivariable Correlation with Maximal Information Entropy

Zhang Ya-hong Li Yu-jian Zhang Ting
(College of Computer Science Beijing University of Technology, Beijing 100124, China)

Many measures, e.g., Maximal Information Coefficient (MIC), are presented to identify interesting correlations for pairs of variables, but few for triplets or even for higher dimension variable set. Based on that, the Maximal Information Entropy (MIE) is proposed for measuring the general correlation of a multivariable data set. For k variables, firstly, the maximal information matrix is constructed according to the MIC scores of any pairs of variables; then, maximal information entropy, which measures the correlation degree of the concerned k variables, is calculated based on the maximal information matrix. The simulation experimental results show that MIE can detect one-dimensional manifold dependence of triplets. The applications to real datasets further verify the feasibility of MIE.

Data mining; Multivariable correlation; Maximal Information Coefficient (MIC); Maximal Information Entropy (MIE)

TP391

A

1009-5896(2015)01-0123-07

10.11999/JEIT140053

2014-01-09收到，2014-04-01改回

國家自然科學基金(61175004)，北京市自然科學基金(4112009)，北京市教委科技發展重點項目(KZ01210005007)，高等學校博士學科點專項科研基金(20121103110029)和北京工業大學第12屆研究生科技基金(ykj-2013-9492)資助課題

*通信作者：張亞紅 plahpu@163.com