李玉鑑,張亞紅

(北京工業(yè)大學(xué)計算機學(xué)院,北京 100124)

?

三元變量間一維流形依賴關(guān)系的檢測

李玉鑑,張亞紅

(北京工業(yè)大學(xué)計算機學(xué)院,北京 100124)

摘要：最大信息系數(shù)(Maximum Information Coefficient,MIC)能夠很好的檢測成對變量間的線性和非線性依賴關(guān)系，但卻不能直接用于檢測三元變量間的相關(guān)關(guān)系.基于MIC的思想和全相關(guān)的概念，本文提出了一種直接檢測三元變量間一維流形依賴關(guān)系的方法—最大全相關(guān)系數(shù)(Maximal Total Correlation Coefficient,MTCC).MTCC用落在[0,1]區(qū)間上的值來表明三元變量間一維流形依賴關(guān)系的強弱，其中0和1分別表示最弱和最強的依賴關(guān)系.使用MIC的計算策略，本文還提出了一種有效的動態(tài)規(guī)劃方法來近似計算MTCC的值.仿真實驗說明MTCC與非線性相關(guān)信息熵(Nonlinear Correlation Information Entropy,NCIE)相比具有更好的通用性和公平性，真實數(shù)據(jù)的分析驗證了MTCC的實用性.最后，強調(diào)了其專用性.

關(guān)鍵詞:數(shù)據(jù)挖掘；三元相關(guān)；一維流形依賴；最大信息系數(shù)；最大全相關(guān)系數(shù)；非線性相關(guān)信息熵

1引言

近年來，由于在基因組學(xué)、物理學(xué)、政治科學(xué)、經(jīng)濟學(xué)等眾多領(lǐng)域出現(xiàn)了越來越多的大規(guī)模數(shù)據(jù)集，因此如何檢測大數(shù)據(jù)中潛在的依賴關(guān)系受到了人們?nèi)找鎻V泛的關(guān)注[1,2].檢測依賴關(guān)系的主要目的是發(fā)現(xiàn)大數(shù)據(jù)集中成對變量間的重要相關(guān)關(guān)系，其中相關(guān)關(guān)系可以是任意的線性或非線性函數(shù)關(guān)系、以及更為復(fù)雜的統(tǒng)計依賴關(guān)系.如果數(shù)據(jù)集中包含幾百、甚至幾千個以上的變量，那么用人工方法一一檢測這些變量之間的依賴關(guān)系是不現(xiàn)實的.

迄今為止，研究者們已經(jīng)提出了許多用于檢測數(shù)據(jù)變量依賴關(guān)系的方法，如互信息估計[3～5]、最大相關(guān)[6,7]、基于主曲線的方法[8～11]、距離相關(guān)[12,13]、Pearson相關(guān)系數(shù)和Spearman秩相關(guān)等等.以互信息為基礎(chǔ)， Reshef等人[1]于2011年在國際上最頂級的期刊Science上發(fā)表論文，引入了最大信息系數(shù)(Maximal Information Coefficient,MIC)的概念，用于檢測大數(shù)據(jù)集中的相關(guān)關(guān)系.MIC可能是世界上目前最好的相關(guān)性檢測方法，被稱為一種21世紀的相關(guān)性[14].與其它方法相比，最大信息系數(shù)MIC通常具有更好的通用性和公平性，也就是說，利用MIC不僅能夠檢測更為廣泛的關(guān)系類型，而且在同等噪聲條件下，不同關(guān)系類型的MIC值彼此更為接近.雖然MIC的公平性受到質(zhì)疑[15]，但經(jīng)過學(xué)術(shù)爭論后又得到了進一步的確認[16].正是由于這些優(yōu)點，MIC獲得了大量成功的應(yīng)用.比如，將MIC應(yīng)用于世界衛(wèi)生數(shù)據(jù)、棒球統(tǒng)計數(shù)據(jù)、酵母菌基因表達數(shù)據(jù)和人類腸道的細菌豐度數(shù)據(jù)，確實幫助發(fā)現(xiàn)了許多已知和新穎的相關(guān)關(guān)系[1].此外， MIC還被應(yīng)用于基因組學(xué)[17]，蛋白質(zhì)組學(xué)[18]，微生物學(xué)[19]，以及傳感器[20]等領(lǐng)域.

然而，以上介紹的相關(guān)性分析方法，包括MIC，都不能直接檢測三元(多元)變量間的相關(guān)關(guān)系.事實上，目前涉及三元(多元)變量間相關(guān)性的研究還比較少，本文在分析相關(guān)工作時只找到了一種方法，即非線性相關(guān)信息熵(Nonlinear Correlation Information Entropy,簡稱NCIE)[21].NCIE是一種檢測多元變量依賴關(guān)系的非參數(shù)方法，可以通過用兩兩變量估計的互信息矩陣來計算，能夠用0～1之間的取值表示三元變量數(shù)據(jù)集的依賴關(guān)系強弱.NCIE的主要缺點是只有在三個變量完全相同的情況下才能取值1，對許多常見的空間曲線取值明顯小于1，因此不具有良好的通用性.而且，NCIE也不具有良好的公平性，因為對不同類型的依賴關(guān)系相同的NCIE值對應(yīng)的噪聲水平一般差別較大.

本文將利用MIC的通用性和公平性優(yōu)點，將其擴展為一種新的統(tǒng)計分析工具，即最大全相關(guān)系數(shù)(Maximal Total Correlation Coefficient,MTCC)，用于直接檢測三元變量間一維流形依賴關(guān)系.由于MTCC和MIC具有共同的信息理論基礎(chǔ)，所以MTCC能夠在一定程度上繼承MIC的通用性和公平性.本文將通過三維空間曲線上的仿真實驗說明MTCC能夠有效的檢測三元變量間一維流形依賴關(guān)系，同時在與NCIE比較的基礎(chǔ)上驗證其通用性和公平性.此外，我們還將MTCC應(yīng)用于分析全球健康和棒球聯(lián)盟數(shù)據(jù)，進一步評價其分析真實數(shù)據(jù)的有效性和可行性.最后，本文通過三維空間曲面上的仿真實驗指出了MTCC的固有缺點，這雖然說明MTCC還不足以有效地檢測三元變量間二維流形依賴關(guān)系，但同時也說明它具有良好的專用性，即可以被看作一種檢測三元變量間一維流形依賴關(guān)系的專用方法，能夠給出比較可靠的檢測結(jié)果.

2最大全相關(guān)系數(shù)(MTCC)

本節(jié)在簡介MIC的基礎(chǔ)上，給出MTCC的嚴格定義和計算方法.

2.1MIC簡介

MIC的基礎(chǔ)是二元隨機變量X和Y之間的互信息.如果用H(·)表示為信息熵，那么X和Y的互信息定義為：I(X,Y)=H(X)+H(Y)-H(X,Y).

MIC的基本思想是：如果變量X和Y之間存在某種相關(guān)關(guān)系，那么在它們的散點圖上就應(yīng)該能夠構(gòu)造一個特殊的網(wǎng)格，使得數(shù)據(jù)點在該網(wǎng)格上的互信息明顯大于0.MIC就是通過具有最大歸一化互信息的網(wǎng)格來定義的，并由此評估變量依賴關(guān)系的強弱.

給定有限二元數(shù)據(jù)集D，任意劃分x行和y列，就可以得到一個x-by-y的2維網(wǎng)格G(x,y)，其中允許某些行或列包含的數(shù)據(jù)點為空，而且網(wǎng)格線的間距可以不相等.D|G為集合D在G上的概率分布，其中數(shù)據(jù)點落在每個格子的概率是該格子內(nèi)所包含的樣本點數(shù)量占全體樣本點的比例.如果用I(D|G)表示網(wǎng)格G在D上產(chǎn)生的互信息，用I(D,x,y)表示所有大小為x-by-y的網(wǎng)格G(x,y)在D上產(chǎn)生的最大互信息，那么I(D,x,y)=maxG{I(D|G(x,y))}.據(jù)此，可以把數(shù)據(jù)集D的最大信息系數(shù)定義為：

(1)

其中B=nα(0<α<1)，計算時取經(jīng)驗值B=n0.6用于控制網(wǎng)格的大小上限.

MIC的計算流程如圖1所示.需要指出的是，對每個給定的x和y，搜索產(chǎn)生理論上最大互信息的網(wǎng)格G是非常耗時的計算過程，因此在應(yīng)用時需要采用一種基于動態(tài)規(guī)劃的方法近似處理，詳見文獻[1].

2.2MTCC的定義

前面已經(jīng)指出，MIC以兩元隨機變量間的互信息為基礎(chǔ)，而最大全相關(guān)系數(shù)MTCC則以三元隨機變量間的全相關(guān)為基礎(chǔ).在信息理論中，全相關(guān)可以看作是互信息的一種推廣，能夠定量地表達n個隨機變量間依賴關(guān)系的強弱.全相關(guān)在n=2時退化為互信息.任意三個隨機變量(X,Y,Z)的全相關(guān)可定義如下：

TC(X;Y;Z)=H(X)+H(Y)+H(Z)-H(X,Y,Z)

(2)

從直觀上說，MTCC是MIC從兩維平面到三維空間的一種推廣，即從兩元變量間的一維流形依賴推廣到三元變量間的一維流形依賴.與MIC的主要區(qū)別在于，MTCC是用3維網(wǎng)格代替2維網(wǎng)格來定義的，通過搜索具有最大歸一化全相關(guān)的網(wǎng)格來評估三元變量依賴關(guān)系的強弱.

根據(jù)概率論，0≤TC(D,x,y,z)≤log min{xy,xz,yz}，因此0≤T(D)x,y,z≤1，從而0≤MTCC(D)≤1.這意味著最大全相關(guān)系數(shù)MTCC的取值恒在0和1之間.MTCC=0表示三個變量完全獨立，此時依賴關(guān)系最弱.MTCC=1表示三個變量完全相互依賴，此時依賴關(guān)系最強.

2.3MTCC的計算方法

根據(jù)MTCC的定義，參照MIC的計算流程，對給定三元變量數(shù)據(jù)集D，計算其最大全相關(guān)系數(shù)MTCC的過程可歸納為以下5個步驟：

步驟1對于任意三個均大于1的正整數(shù)x,y,z，如果xyz

步驟2統(tǒng)計每個格子所包含D的樣本點數(shù)，在G上誘導(dǎo)出概率分布p(x,y,z)、p(x)、p(y)和p(z).其中，p(x,y,z)表示在第(x,y,z)個格子中包含的樣本點數(shù)占全體樣本點的比例，p(x)、p(y)和p(z)分別表示x-軸、y-軸和z-軸上的邊際分布；

步驟4計算特征張量元素T(D)x,y,z，構(gòu)造特征張量T(D)；

圖3給出了一些特征張量的可視化結(jié)果.不難看出，對不同類型的一維流形依賴關(guān)系而言，相應(yīng)的特征張量通常是不同的.

3實驗結(jié)果與分析

本節(jié)通過實驗討論MTCC的通用性、公平性、實用性和專用性.

3.1通用性和公平性實驗

由圖2不難看出，在無噪聲的情況下，對于三元變量間的許多線性和非線性一維流形依賴關(guān)系，它們的MTCC值都為1，而非線性相關(guān)信息熵NCIE的值卻幾乎不為1.對于NCIE來說，三元變量間的無噪線性依賴關(guān)系的強度要明顯大于無噪非線性依賴關(guān)系的強度，而事實上它們的強度應(yīng)該大體相同才是合理的.因此，與NCIE相比，MTCC具有更好的通用性.

圖5是采用類似圖4的方法構(gòu)造帶噪聲的數(shù)據(jù)集，但只列舉了MTCC=0.80,0.65,0.50,0.35的情況.從中不難看出，隨著噪聲水平的增加，雖然MTCC將逐步減小，但只要噪聲水平大致相同，不同類型依賴關(guān)系的MTCC值也是彼此接近的.

3.2實用性實驗

為了說明MTCC在分析實際數(shù)據(jù)時檢測三元變量間一維流形依賴關(guān)系的實用性，本文利用世界健康衛(wèi)生數(shù)據(jù)(WHO)和美國職業(yè)棒球聯(lián)盟數(shù)據(jù)(MLB)進行了兩組應(yīng)用實驗.WHO包含世界衛(wèi)生組織及其合作伙伴[22,23]所提供的社會，經(jīng)濟，健康和政治指標(biāo)等數(shù)據(jù)，MLB包含2008年美國職業(yè)棒球大聯(lián)盟賽季[24,25]的性能統(tǒng)計數(shù)據(jù).這兩個數(shù)據(jù)集的二元依賴關(guān)系已經(jīng)用MIC分析過[1]，這里我們主要應(yīng)用MTCC在類似的統(tǒng)計顯著性條件下分析其中三元變量間的一維流形依賴關(guān)系.

在WHO上做分析時，我們只選擇了其中的一個子集，由43個變量構(gòu)成.這43個變量是文獻[1]的表S9提供的，共包含12341個三元組.圖6(a)是實驗得到的MTCC直方圖結(jié)果，其中MTCC值大于0.7的三元組共有758個，占6.14%.圖6(b)～(h)給出了若干根據(jù)MTCC值挑選的依賴關(guān)系，圖中擬合曲線由手工選擇回歸函數(shù)產(chǎn)生，較好地反映了數(shù)據(jù)的變化趨勢.值得注意的是，圖6(d)包含兩條趨勢線，一條是少數(shù)點趨勢線，主要由一組科技產(chǎn)業(yè)高度發(fā)達的國家組成，其人均電腦較多、電力消耗和人均能源消耗較大，另一條是多數(shù)點趨勢線，由其它國家組成，其電力消耗和人均能源消耗隨著人均電腦數(shù)大致均勻地增加.此外，圖6(e)包含3條趨勢線，反映了“5歲以下兒童死亡率”，“人均健康投入”和“人均收入”這3個變量在不同條件下存在的三種依賴關(guān)系，從中不難看出，通過增加“人均收入”或者“人均健康投入”，都有助于降低“5歲以下兒童的死亡率”，因此可望指導(dǎo)決策者制定相應(yīng)的全民健康政策.圖6(i)中沒有明顯的變量依賴關(guān)系，所以MTCC值較小，只有0.167.

在MLB上做分析時，我們也只選擇了其中的一個子集，由50個變量構(gòu)成.這50個變量是文獻[1]的表S12提供的，共包含196000個三元組.圖7(a)是實驗得到的MTCC直方圖，其中MTCC值大于等于0.7的三元組共有3929個，占20%.圖7(b)～(h)給出了若干根據(jù)MTCC值挑選的依賴關(guān)系，其中反映數(shù)據(jù)變化趨勢的擬合曲線也是由手工產(chǎn)生的.值得注意的是，圖7(f)包含兩條趨勢線，反映了“games played as a pinch hitter (G-PH)”，“plate appearances as a pinch hitter (PA-PH)”和“true runs tells of a player′s total offensive contribution in runs (EqR)”這三個變量之間在不同條件下可能存在的兩種依賴關(guān)系，其具體含義留給棒球愛好者來闡明.

3.3MTCC的專用性實驗

通過上述分析，MTCC在用來檢測三元變量間的一維流形依賴關(guān)系時無疑是非常成功的.但它并不是萬能的，也有其固有缺陷.比如，MTCC在檢測三元變量間的二維流形依賴關(guān)系時，還不能被看作一種理想的方法.事實上，針對圖8所示的無噪空間曲面，MTCC的值雖然不算太小，但一般也小于0.6.當(dāng)然，這同時也進一步說明，MTCC可以看作是一種檢測三元變量間一維流形依賴關(guān)系的專用方法，具有較高的可靠性.

4結(jié)論

本文通過推廣最大信息系數(shù)MIC，提出了最大全相關(guān)系數(shù)MTCC的概念.MTCC可以用來直接檢測三元變量間一維流形依賴關(guān)系，并較好地繼承了MIC的通用性和公平性.通過將MTCC應(yīng)用于分析世界健康衛(wèi)生數(shù)據(jù)和美國職業(yè)棒球聯(lián)盟數(shù)據(jù)，本文還進一步驗證了其實用性，有助于確認或揭示數(shù)據(jù)中三元一維流形依賴關(guān)系.雖然MTCC不能有效的檢測三元二維流形依賴關(guān)系，但這又說明了它的專用性，因此在檢測三元一維流形依賴關(guān)系方面給出的結(jié)果具有良好的可靠性.

由于MIC在檢測二元變量間的依賴關(guān)系方面已經(jīng)被公認為是一種重要的工具和方法[15]，所以MTCC作為MIC的推廣，MTCC可以看作是MIC的一大進步.與MIC相比，MTCC有時可以揭示更多的信息內(nèi)容，因此像MIC一樣，MTCC也將在分析各個不同科學(xué)領(lǐng)域的復(fù)雜數(shù)據(jù)時獲得越來越多的應(yīng)用.

參考文獻

[1]Reshef D N,Reshef Y A,Finucane H K,et al.Detecting novel associations in large data set[J].Science,2011,334 (6062):1518-1524.

[2]Staff S.Challenges and opportunities[J].Science,2011,331(6018):692-693.

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

[4]Khan S,Bandyopadhyay S,Ganguly A R,et al.Relative performance of mutual information estimation methods for quantifying the dependence among short and noisy data[J].Physical Review E,2007,76(2):62-85.

[5]Kraskov A,St?gbauer H,Grassberger P.Estimating mutual information[J].Physical Review E,2004,69(6):279-307.

[6]Yu Y.On the maximal correlation coefficient[J].Statistics & Probability Letters,2008,78(9):1072-1075.

[7]Zhang L H,Liao L Z,Sun L M.Towards the global solution of the maximal correlation problem[J].Journal of Global Optimization,2011,49(1):91-107.

[8]蘇菡，黃鳳崗.一種基于主曲線的步態(tài)識別方法[J].電子學(xué)報,2007,35(9):1685-1690.

Su H,Huang F G.An automatic human gait recognition based on principle curves[J].Acta Electronica Sinica,2007,35(9):1685-1690.(in Chinese)

[9]Hongyun Z,Duoqian M,Dongxing Z.Analysis and extraction of structural features of off-line handwritten digits based on principal curves[J].Journal of Computer Research and Development,2005,42(8):1344-1349.

[10]Verbeek J J,Vlassis N,Kr?se B.A k-segments algorithm for finding principal curves[J].Pattern Recognition Letters,2002,23(8):1009-1017.

[11]Delicado P,Smrekar M.Measuring non-learning dependence for two random variables distributed along a curve[J].Statistics and Computing,2009,19(3):255-269.

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

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

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

[15]Kinney J B,Atwal G S.Equitability,mutual information,and the maximal information coefficient[J].Proceedings of the National Academy of Sciences,2014,111(9):3354-3359.

[16]Reshef D N,Reshef Y A,Mitzenmacher M,et al.Cleaning up the record on the maximal information coefficient and equitability[J].Proceedings of the National Academy of Sciences,2014,111(33):E3362-E3363.

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

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

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

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

[21]Wang Q,Shen Y,Zhang J Q.A nonlinear correlation measure for multivariable data set[J].Physica D,2005,200(3-4):287-295.

[22]World-Health-Organization.World Health Organization Statistical Information Systems (whosis)[DB/OL],http://www.who.int/whosis/en/,2009.

[23]Rosling H.Indicators in Gapminder World[DB/OL].http://www.gapminder.org/data/,2009.

[24]Baseball Prospectus Statistics Reports[DB/OL].http://www.baseballpropectus.com/sortable/,2009.

[25]Lahman S.The Baseball Archive[DB/OL].http://baseball1.com/statistics/,2009.

李玉鑑男，1968年生于廣西省，1999在中國科學(xué)院半導(dǎo)體研究所獲得博士學(xué)位，現(xiàn)為北京工業(yè)大學(xué)計算機學(xué)院教授.主要研究方向為模式識別與機器學(xué)習(xí)，圖像處理，深度學(xué)習(xí)等.

E-mail:liyujian@bjut.edu.cn

張亞紅女，1987年生于河南省,2011年獲得河南理工大學(xué)計算機系學(xué)士學(xué)位，現(xiàn)為北京工業(yè)大學(xué)計算機學(xué)院博士.主要研究方向為模式識別與機器學(xué)習(xí).

E-mail:plahpu@163.com

A Detecting Measure for Trivariate One-Dimensional Manifold Dependences

LI Yu-jian,ZHANG Ya-hong

(CollegeofComputerScienceandTechnology,BeijingUniversityofTechnology,Beijing100124,China)

Abstract:Maximal information coefficient (MIC) is a good measure for detecting linear and nonlinear correlation between pairs of variables,but not directly applicable for triplets.Based on the idea of MIC and concept of total correlation,we propose the maximal total correlation coefficient (MTCC),which measures a one-dimensional manifold dependence among three variables with a score in [0,1],where 0 stands for the weakest and 1 for the strongest.Using the strategy of computing MIC,we also present an efficient dynamic programming method to approximate the true value of MTCC in practice.Simulation results show that MTCC has better generality and better equitability than nonlinear correlation information entropy (NCIE).By analyzing real datasets,we further verify the feasibility of MTCC.Finally,we emphasize its specificity.

Key words:data mining;trivariate correlation;one-dimensional manifold dependence;maximal information coefficient;maximal total correlation coefficient;nonlinear correlation information entropy

作者簡介

DOI:電子學(xué)報URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.022

中圖分類號:TP391

文獻標(biāo)識碼：A

文章編號：0372-2112 (2016)03-0639-07

基金項目:國家自然科學(xué)基金(No.61175004);北京市自然科學(xué)基金(No.4112009);高等學(xué)校博士學(xué)科點專項科研基金(No.20121103110029)

收稿日期:2014-07-07；修回日期：2015-03-09；責(zé)任編輯：梅志強