张朝霞,吴 杰

(1太原师范学院 计算机系，山西 晋中 030619；2太原师范学院 研究生处，山西 晋中 030619)

0 引言

信息时代，全球的数据量呈现出爆炸式的增长，如何充分挖掘数据中隐藏的潜在价值，成了全球关注的问题[1].目前，在数据的相关性分析方面已形成了很多成果：统计相关分析主要集中在两变量和多变量间的线性相关分析[2-5]；基于互信息的相关分析主要针对两变量间的非线性相关分析[6]、基于矩阵的相关性分析可以描述线性、高维的相关性分析[1-4]；基于距离的相关分析可以探测非线性、高维的相关性[5-9].

通过研究现阶段的相关性分析进展情况，发现面对两个变量间的非线性复杂系统，2011年Science上的文献[6]中介绍的基于互信息的挖掘大数据集中两个变量间的相关性度量方法——MIC是最成熟和有效的.该方法基于归一化后的互信息定义了两个变量间的最大信息系数MIC，不仅能够发现两变量间广泛范围的相关关系，而且，同时满足通用性和公平性.这里的通用性是指，不管数据分布形式如何，MIC对于数据间的任意形式的依赖函数关系都能有效度量；公平性是指在不同函数依赖下，只要噪声水平相同，MIC的值基本保持相同.这在经典的相关性分析中是很难做到的.因此，MIC可能是目前最好的相关性检测方法，甚至有人称其为21世纪的相关性.但是，MIC只能够快速、有效地发觉两变量间线性和非线性的相关关系.

目前，多变量间的相关性分析研究相对较少，主要有非线性相关信息熵(Nonlinear Correlation Information Entropy，NCIE)方法[6].NCIE方法通过将多变量的值表示的数据点均匀地分成几部分来检测任意两变量间的互信息，然后利用互信息矩阵的特征值构造出多变量间的非线性相关信息熵.该方法计算简单，且易于理解，是一种高效地探测多变量间相关性的方法.但是该方法不具有良好的通用性，且在处理稀疏性强的高维数据时会降低其度量的可靠性.

本文在借鉴已有研究的基础上，主要做了两方面的工作：第一，将非线性相关信息熵方法中的互信息矩阵改进为最大信息系数矩阵，在保留了MIC方法的通用性和公平性优点的基础上，把两变量间的相关性度量准则MIC间接地推广到多变量间的任意函数形式的相关性分析中去.第二，在利用最大信息系数矩阵的特征值构造相关性度量方法时，将NCIE中只利用正特征值改为利用非零特征值，提高了测量的可靠性.最后，提出了一种高效的、能探测多变量间线性和非线性的相关关系的方法——Multivariable Maximal Mutual Information Coefficient(Mv_MMIC).

1 两变量间的最大信息系数(MIC)[6]

定义1(网格)[1]

对于变量X，Y，它们的所有取值的有序对〈xi，yj〉构成有限集合S={(x1，y1)，(x2，y2)，…，(xn，yn)}，将数据集S中的n个点绘制散点图，再对数据集S的n个点进行网格划分，形成i列j行的i×j网格，这样的划分称为i×j网格Gr[6].

i×j网格Gr中有些子格含有集合S中的点，有些子格可能是空的，随机变量X和Y之间的互信息根据网格Gr中各子网格内散点数的频率计算.

定义2(基于网格的互信息)[6]设随机向量为(X，Y)，其所有的有序对值〈x，y〉构成有限集合S，将S划分成网格Gr，根据网格Gr子格内各散点的频率得到随机变量X和Y之间的互信息为：

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

其中，n为散点的总个数，ni为散点图中落在网格Gr第i列中的散点数，nj为散点图中落在网格Gr第j行中的散点数，nij为散点图中落在网格Gr第i列第j行形成的子格中的散点数.

互信息作为相关性分析的度量准则，最大的优势在于能有效刻画两变量之间的非线性关系；但是，它的值没有上界，既不能被限定在闭区间[0，1]范围内，也不能直接比较互信息值的大小，因为不同变量的测量尺度(单位)不一样，难以通过互信息的值来比较不同两组变量相关性的绝对大小，因此，需要把互信息标准化，而最大信息系数本质上是最大互信息的标准化，可以通过比较最大信息系数的大小来实现比较不同两组变量相关性的绝对大小.

定义3(最大互信息)[6]设随机向量为(X，Y)，随机变量X和Y基于网格Gr的互信息为I(X，Y，S|Gr，i，j)，最大互信息定义为多种划分下互信息的最大值，即

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

其中，i表示网格的列，j表示网格的行.[1]

为了能够精确比较不同两组变量相关性的绝对大小，先把最大互信息标准化为：

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

定义4(最大信息系数MIC,表示为M*)[6]给定两个随机变量X和Y的数据集S，|S|=n，则随机变量X和Y的最大信息系数定义为：

其中，B(n)=n0.6，表示搜索网格数的上界.

最大信息系数M*具有如下性质：[5]

性质1M*是每个I*(X，Y，S，i，j)标准化后的最大值，0≤M*(X，Y)≤1.

性质2M*(X，Y)=M*(Y，X).

性质3M*具有极限性，即，当样本n→∞时，M*→1.

性质4当两个变量相互独立时，M*=0.

2 多变量间的非线性相关信息熵(NCIE)方法[6]

NCIE方法通过将多变量所表示的数据点均匀地分成几部分来检测任意两变量间的互信息，然后利用两变量间的互信息构建信息矩阵计算出多变量间的非线性相关信息熵.

下面先介绍相关概念，然后给出具体步骤.

定义5(两变量间的互信息NCC，表示为N*)[6]设随机变量为X和Y，两变量间的互信息定义为

其中，n为散点的个数，ni为散点图中落在网格第i列中的散点数，nj为散点图中落在网格第j行中的点数，nij为散点图中落在网格第i列和第j行中的散点数.

定义7(非线性相关信息熵)[6]n个变量X1，X2，…，Xn之间的非线性相关信息熵定义为

非线性相关信息熵NCIE虽然能够用区间[0，1]上的数字度量多变量间的相关性，但该方法不具有良好的通用性，而且当处理稀疏性强的高维数据时，它的可靠性会大幅降低[6].

3 多变量间的最大信息系数

本节首先给出最大信息系数矩阵和多变量间的最大信息系数的定义，然后借鉴MIC和NCIE两算法的优点，提出一种新的有效度量多变量间相关关系的度量准则.

定义8(最大信息系数矩阵) 设X1，X2，…,Xn是n个随机变量，n>2，则随机变量的最大信息系数矩阵定义为：

定义9(多变量间的最大信息系数Mv_MMIC,表示为Mv)n个变量X1，X2，…,Xn(n>2)之间的非线性相关信息熵定义为

0≤Mv≤1

其中

Mv_MMIC定义的合理性可以从线性空间的角度得到解释：在n维欧式空间中，对n阶对称方阵进行特征分解，可以产生该空间的一组标准正交基(即为n个特征向量)，把矩阵投影到这组基上，每个特征值λi(i=1，2，…,n)的模表示矩阵在相应基上投影的长度，当特征值λi(i=1，2，…，n)大于零时表示矩阵在相应基上的投影拉伸或缩短λi倍；当特征值λi(i=1，2，…，n)小于零时表示矩阵在相应基的负方向上的投影拉伸或缩短λi倍，当特征值λi(i=1，2，…，n)等于零时表示矩阵在相应基上的投影为0.所以，特征值往往对应着矩阵中隐含的重要信息，且重要性和特征值大小|λi|正相关.

Mv具有如下性质：

性质10≤Mv≤1.

证明 因为λi(i=1，2，…,l，l≤n)为最大信息系数矩阵R的非0特征根，令k=|λ1|+|λ2|+…+|λn|

因为当x∈(0，1]，可知

当k∈(2，+∞)时，可知

证毕.

性质2设X1，X2，…,Xn是n个随机变量(n>2)，Xi1，Xi2，…,Xin是X1，X2，…,Xn(n>2)的任意随机排列，则

证明 因为n个随机变量Xi1，Xi2，…，Xin(n>2)的最大信息系数矩阵R1是n个随机变量X1，X2，…，Xn(n>2)的最大信息系数矩阵R经若干次初等变换得到的，因此两个矩阵的特征值是相同的，所以

证毕.

性质3当n个变量中任意两个变量间相关时，Mv=1.

性质4当n个变量中任意两个变量相互独立时，Mv=0.

具体实现步骤如下.

步骤2：根据定义8构建最大信息系数矩阵R.

步骤3：计算最大信息系数矩阵R的特征值λi(i=1，2，…，n).

步骤4：根据定义9计算n个变量间的相关性Mv.

4 实验分析

本实验首先从六种不同的三元函数图像上均匀采集相应的模拟数据点集{(xi，yi，zi)(i=1，2，…,n)形成无噪声的数据点集，构造出相应的三个变量X，Y，Z，这里变量X的取值为xi(i=1，2，…,n)，变量Y的取值为yi(i=1，2，…,n)，变量Z的取值为zi(i=1，2，…,n)，然后利用多变量间的最大信息系数来计算三个变量X，Y，Z的相关性Mv，发现这六组数据的相关性Mv都近似为1(见表1)，而算法NCIE的值并不是全近似为1[6]，而且这六组数据的相关性随着实验数据量n的增大，Mv的值都在增大.由此可见，在没有噪声时，多个变量间的最大信息系数Mv_MMIC具有很强的通用性，保持了MIC的通用性优点，解决了NCIE不具有通用性的问题.

表1 三元变量的Mv

为了验证Mv_MMIC具有公平性，我们对这六组模拟数据都分别进行了0.5%，1%，2%，3%，4%，5%的高斯白噪声处理，见图1-6，每一组图的左边是数据的无噪声图形，右边是数据加上0.5%噪声的图形，加上不同噪声后，所测得的Mv_MMIC的值见图1.

从实验结果可以看出，不管变量间满足什么函数关系，加入相同的噪声，各组模拟数据中变量间的相关性MV_MMIC近似相等，表明MV_MMIC满足公平性；另外，随着数据量N的增大，各组模拟数据中变量间的相关性MV_MMIC都逐渐增大，且当N增大到10 000时，噪声对每个关系的影响都趋近于0，实验结果说明：当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 总结和展望

本文提出的多变量间的相关性度量方法MV_MMIC，把两变量间的相关性度量准则MIC间接地推广到多变量间的任意函数形式的相关性分析中去，且保留了两变量间的相关性度量方法MIC的通用性和公平性优点，并提高了测量的可靠性和抗噪声能力.另外，从MIC的计算过程可以看出，计算任意两变量间的最大信息系数MIC可以并行处理，若能利用云计算或GPU实现其中的MIC算法，该方法可适用于检测大数据多变量间的广泛的线性和非线性的相关性.