張朝霞,吳 杰

(1太原師范學(xué)院 計(jì)算機(jī)系，山西 晉中 030619；2太原師范學(xué)院 研究生處，山西 晉中 030619)

0 引言

信息時代，全球的數(shù)據(jù)量呈現(xiàn)出爆炸式的增長，如何充分挖掘數(shù)據(jù)中隱藏的潛在價值，成了全球關(guān)注的問題[1].目前，在數(shù)據(jù)的相關(guān)性分析方面已形成了很多成果：統(tǒng)計(jì)相關(guān)分析主要集中在兩變量和多變量間的線性相關(guān)分析[2-5]；基于互信息的相關(guān)分析主要針對兩變量間的非線性相關(guān)分析[6]、基于矩陣的相關(guān)性分析可以描述線性、高維的相關(guān)性分析[1-4]；基于距離的相關(guān)分析可以探測非線性、高維的相關(guān)性[5-9].

通過研究現(xiàn)階段的相關(guān)性分析進(jìn)展情況，發(fā)現(xiàn)面對兩個變量間的非線性復(fù)雜系統(tǒng)，2011年Science上的文獻(xiàn)[6]中介紹的基于互信息的挖掘大數(shù)據(jù)集中兩個變量間的相關(guān)性度量方法——MIC是最成熟和有效的.該方法基于歸一化后的互信息定義了兩個變量間的最大信息系數(shù)MIC，不僅能夠發(fā)現(xiàn)兩變量間廣泛范圍的相關(guān)關(guān)系，而且，同時滿足通用性和公平性.這里的通用性是指，不管數(shù)據(jù)分布形式如何，MIC對于數(shù)據(jù)間的任意形式的依賴函數(shù)關(guān)系都能有效度量；公平性是指在不同函數(shù)依賴下，只要噪聲水平相同，MIC的值基本保持相同.這在經(jīng)典的相關(guān)性分析中是很難做到的.因此，MIC可能是目前最好的相關(guān)性檢測方法，甚至有人稱其為21世紀(jì)的相關(guān)性.但是，MIC只能夠快速、有效地發(fā)覺兩變量間線性和非線性的相關(guān)關(guān)系.

目前，多變量間的相關(guān)性分析研究相對較少，主要有非線性相關(guān)信息熵(Nonlinear Correlation Information Entropy，NCIE)方法[6].NCIE方法通過將多變量的值表示的數(shù)據(jù)點(diǎn)均勻地分成幾部分來檢測任意兩變量間的互信息，然后利用互信息矩陣的特征值構(gòu)造出多變量間的非線性相關(guān)信息熵.該方法計(jì)算簡單，且易于理解，是一種高效地探測多變量間相關(guān)性的方法.但是該方法不具有良好的通用性，且在處理稀疏性強(qiáng)的高維數(shù)據(jù)時會降低其度量的可靠性.

本文在借鑒已有研究的基礎(chǔ)上，主要做了兩方面的工作：第一，將非線性相關(guān)信息熵方法中的互信息矩陣改進(jìn)為最大信息系數(shù)矩陣，在保留了MIC方法的通用性和公平性優(yōu)點(diǎn)的基礎(chǔ)上，把兩變量間的相關(guān)性度量準(zhǔn)則MIC間接地推廣到多變量間的任意函數(shù)形式的相關(guān)性分析中去.第二，在利用最大信息系數(shù)矩陣的特征值構(gòu)造相關(guān)性度量方法時，將NCIE中只利用正特征值改為利用非零特征值，提高了測量的可靠性.最后，提出了一種高效的、能探測多變量間線性和非線性的相關(guān)關(guān)系的方法——Multivariable Maximal Mutual Information Coefficient(Mv_MMIC).

1 兩變量間的最大信息系數(shù)(MIC)[6]

定義1(網(wǎng)格)[1]

對于變量X，Y，它們的所有取值的有序?qū)Α磝i，yj〉構(gòu)成有限集合S={(x1，y1)，(x2，y2)，…，(xn，yn)}，將數(shù)據(jù)集S中的n個點(diǎn)繪制散點(diǎn)圖，再對數(shù)據(jù)集S的n個點(diǎn)進(jìn)行網(wǎng)格劃分，形成i列j行的i×j網(wǎng)格，這樣的劃分稱為i×j網(wǎng)格Gr[6].

i×j網(wǎng)格Gr中有些子格含有集合S中的點(diǎn)，有些子格可能是空的，隨機(jī)變量X和Y之間的互信息根據(jù)網(wǎng)格Gr中各子網(wǎng)格內(nèi)散點(diǎn)數(shù)的頻率計(jì)算.

定義2(基于網(wǎng)格的互信息)[6]設(shè)隨機(jī)向量為(X，Y)，其所有的有序?qū)χ怠磝，y〉構(gòu)成有限集合S，將S劃分成網(wǎng)格Gr，根據(jù)網(wǎng)格Gr子格內(nèi)各散點(diǎn)的頻率得到隨機(jī)變量X和Y之間的互信息為：

I(X，Y，S|Gr，i，j)=H(X|Gr)+H(Y|Gr)-H(X，Y|Gr)

其中，n為散點(diǎn)的總個數(shù)，ni為散點(diǎn)圖中落在網(wǎng)格Gr第i列中的散點(diǎn)數(shù)，nj為散點(diǎn)圖中落在網(wǎng)格Gr第j行中的散點(diǎn)數(shù)，nij為散點(diǎn)圖中落在網(wǎng)格Gr第i列第j行形成的子格中的散點(diǎn)數(shù).

互信息作為相關(guān)性分析的度量準(zhǔn)則，最大的優(yōu)勢在于能有效刻畫兩變量之間的非線性關(guān)系；但是，它的值沒有上界，既不能被限定在閉區(qū)間[0，1]范圍內(nèi)，也不能直接比較互信息值的大小，因?yàn)椴煌兞康臏y量尺度(單位)不一樣，難以通過互信息的值來比較不同兩組變量相關(guān)性的絕對大小，因此，需要把互信息標(biāo)準(zhǔn)化，而最大信息系數(shù)本質(zhì)上是最大互信息的標(biāo)準(zhǔn)化，可以通過比較最大信息系數(shù)的大小來實(shí)現(xiàn)比較不同兩組變量相關(guān)性的絕對大小.

定義3(最大互信息)[6]設(shè)隨機(jī)向量為(X，Y)，隨機(jī)變量X和Y基于網(wǎng)格Gr的互信息為I(X，Y，S|Gr，i，j)，最大互信息定義為多種劃分下互信息的最大值，即

I*(X，Y，S，i，j)=arg maxI(X，Y，S|Gr，i，j)

其中，i表示網(wǎng)格的列，j表示網(wǎng)格的行.[1]

為了能夠精確比較不同兩組變量相關(guān)性的絕對大小，先把最大互信息標(biāo)準(zhǔn)化為：

M(X，Y|S)i.j=I*(X，Y，S，i，j)/log min(i，j).

定義4(最大信息系數(shù)MIC,表示為M*)[6]給定兩個隨機(jī)變量X和Y的數(shù)據(jù)集S，|S|=n，則隨機(jī)變量X和Y的最大信息系數(shù)定義為：

其中，B(n)=n0.6，表示搜索網(wǎng)格數(shù)的上界.

最大信息系數(shù)M*具有如下性質(zhì)：[5]

性質(zhì)1M*是每個I*(X，Y，S，i，j)標(biāo)準(zhǔn)化后的最大值，0≤M*(X，Y)≤1.

性質(zhì)2M*(X，Y)=M*(Y，X).

性質(zhì)3M*具有極限性，即，當(dāng)樣本n→∞時，M*→1.

性質(zhì)4當(dāng)兩個變量相互獨(dú)立時，M*=0.

2 多變量間的非線性相關(guān)信息熵(NCIE)方法[6]

NCIE方法通過將多變量所表示的數(shù)據(jù)點(diǎn)均勻地分成幾部分來檢測任意兩變量間的互信息，然后利用兩變量間的互信息構(gòu)建信息矩陣計(jì)算出多變量間的非線性相關(guān)信息熵.

下面先介紹相關(guān)概念，然后給出具體步驟.

定義5(兩變量間的互信息NCC，表示為N*)[6]設(shè)隨機(jī)變量為X和Y，兩變量間的互信息定義為

其中，n為散點(diǎn)的個數(shù)，ni為散點(diǎn)圖中落在網(wǎng)格第i列中的散點(diǎn)數(shù)，nj為散點(diǎn)圖中落在網(wǎng)格第j行中的點(diǎn)數(shù)，nij為散點(diǎn)圖中落在網(wǎng)格第i列和第j行中的散點(diǎn)數(shù).

定義7(非線性相關(guān)信息熵)[6]n個變量X1，X2，…，Xn之間的非線性相關(guān)信息熵定義為

非線性相關(guān)信息熵NCIE雖然能夠用區(qū)間[0，1]上的數(shù)字度量多變量間的相關(guān)性，但該方法不具有良好的通用性，而且當(dāng)處理稀疏性強(qiáng)的高維數(shù)據(jù)時，它的可靠性會大幅降低[6].

3 多變量間的最大信息系數(shù)

本節(jié)首先給出最大信息系數(shù)矩陣和多變量間的最大信息系數(shù)的定義，然后借鑒MIC和NCIE兩算法的優(yōu)點(diǎn)，提出一種新的有效度量多變量間相關(guān)關(guān)系的度量準(zhǔn)則.

定義8(最大信息系數(shù)矩陣) 設(shè)X1，X2，…,Xn是n個隨機(jī)變量，n>2，則隨機(jī)變量的最大信息系數(shù)矩陣定義為：

定義9(多變量間的最大信息系數(shù)Mv_MMIC,表示為Mv)n個變量X1，X2，…,Xn(n>2)之間的非線性相關(guān)信息熵定義為

0≤Mv≤1

其中

Mv_MMIC定義的合理性可以從線性空間的角度得到解釋：在n維歐式空間中，對n階對稱方陣進(jìn)行特征分解，可以產(chǎn)生該空間的一組標(biāo)準(zhǔn)正交基(即為n個特征向量)，把矩陣投影到這組基上，每個特征值λi(i=1，2，…,n)的模表示矩陣在相應(yīng)基上投影的長度，當(dāng)特征值λi(i=1，2，…，n)大于零時表示矩陣在相應(yīng)基上的投影拉伸或縮短λi倍；當(dāng)特征值λi(i=1，2，…，n)小于零時表示矩陣在相應(yīng)基的負(fù)方向上的投影拉伸或縮短λi倍，當(dāng)特征值λi(i=1，2，…，n)等于零時表示矩陣在相應(yīng)基上的投影為0.所以，特征值往往對應(yīng)著矩陣中隱含的重要信息，且重要性和特征值大小|λi|正相關(guān).

Mv具有如下性質(zhì)：

性質(zhì)10≤Mv≤1.

證明 因?yàn)棣薸(i=1，2，…,l，l≤n)為最大信息系數(shù)矩陣R的非0特征根，令k=|λ1|+|λ2|+…+|λn|

因?yàn)楫?dāng)x∈(0，1]，可知

當(dāng)k∈(2，+∞)時，可知

證畢.

性質(zhì)2設(shè)X1，X2，…,Xn是n個隨機(jī)變量(n>2)，Xi1，Xi2，…,Xin是X1，X2，…,Xn(n>2)的任意隨機(jī)排列，則

證明 因?yàn)閚個隨機(jī)變量Xi1，Xi2，…，Xin(n>2)的最大信息系數(shù)矩陣R1是n個隨機(jī)變量X1，X2，…，Xn(n>2)的最大信息系數(shù)矩陣R經(jīng)若干次初等變換得到的，因此兩個矩陣的特征值是相同的，所以

證畢.

性質(zhì)3當(dāng)n個變量中任意兩個變量間相關(guān)時，Mv=1.

性質(zhì)4當(dāng)n個變量中任意兩個變量相互獨(dú)立時，Mv=0.

具體實(shí)現(xiàn)步驟如下.

步驟2：根據(jù)定義8構(gòu)建最大信息系數(shù)矩陣R.

步驟3：計(jì)算最大信息系數(shù)矩陣R的特征值λi(i=1，2，…，n).

步驟4：根據(jù)定義9計(jì)算n個變量間的相關(guān)性Mv.

4 實(shí)驗(yàn)分析

本實(shí)驗(yàn)首先從六種不同的三元函數(shù)圖像上均勻采集相應(yīng)的模擬數(shù)據(jù)點(diǎn)集{(xi，yi，zi)(i=1，2，…,n)形成無噪聲的數(shù)據(jù)點(diǎn)集，構(gòu)造出相應(yīng)的三個變量X，Y，Z，這里變量X的取值為xi(i=1，2，…,n)，變量Y的取值為yi(i=1，2，…,n)，變量Z的取值為zi(i=1，2，…,n)，然后利用多變量間的最大信息系數(shù)來計(jì)算三個變量X，Y，Z的相關(guān)性Mv，發(fā)現(xiàn)這六組數(shù)據(jù)的相關(guān)性Mv都近似為1(見表1)，而算法NCIE的值并不是全近似為1[6]，而且這六組數(shù)據(jù)的相關(guān)性隨著實(shí)驗(yàn)數(shù)據(jù)量n的增大，Mv的值都在增大.由此可見，在沒有噪聲時，多個變量間的最大信息系數(shù)Mv_MMIC具有很強(qiáng)的通用性，保持了MIC的通用性優(yōu)點(diǎn)，解決了NCIE不具有通用性的問題.

表1 三元變量的Mv

為了驗(yàn)證Mv_MMIC具有公平性，我們對這六組模擬數(shù)據(jù)都分別進(jìn)行了0.5%，1%，2%，3%，4%，5%的高斯白噪聲處理，見圖1-6，每一組圖的左邊是數(shù)據(jù)的無噪聲圖形，右邊是數(shù)據(jù)加上0.5%噪聲的圖形，加上不同噪聲后，所測得的Mv_MMIC的值見圖1.

從實(shí)驗(yàn)結(jié)果可以看出，不管變量間滿足什么函數(shù)關(guān)系，加入相同的噪聲，各組模擬數(shù)據(jù)中變量間的相關(guān)性MV_MMIC近似相等，表明MV_MMIC滿足公平性；另外，隨著數(shù)據(jù)量N的增大，各組模擬數(shù)據(jù)中變量間的相關(guān)性MV_MMIC都逐漸增大，且當(dāng)N增大到10 000時，噪聲對每個關(guān)系的影響都趨近于0，實(shí)驗(yàn)結(jié)果說明：當(dāng)n很大時，該算法具有一定的抗噪聲能力.

圖1 0.5%噪聲水平的三變量的Mv_MMIC

圖3 2%噪聲水平的三變量的Mv_MMIC

圖5 4%噪聲水平的三變量的Mv_MMIC

圖2 1%噪聲水平的三變量的Mv_MMIC

圖4 3%噪聲水平的三變量的Mv_MMIC

圖6 5%噪聲水平的三變量的Mv_MMIC

5 總結(jié)和展望

本文提出的多變量間的相關(guān)性度量方法MV_MMIC，把兩變量間的相關(guān)性度量準(zhǔn)則MIC間接地推廣到多變量間的任意函數(shù)形式的相關(guān)性分析中去，且保留了兩變量間的相關(guān)性度量方法MIC的通用性和公平性優(yōu)點(diǎn)，并提高了測量的可靠性和抗噪聲能力.另外，從MIC的計(jì)算過程可以看出，計(jì)算任意兩變量間的最大信息系數(shù)MIC可以并行處理，若能利用云計(jì)算或GPU實(shí)現(xiàn)其中的MIC算法，該方法可適用于檢測大數(shù)據(jù)多變量間的廣泛的線性和非線性的相關(guān)性.