最大互信息系数的并行计算方法研究

针对最大互信息系数（Maximal Information Coefficient，MIC）近似算法在大规模数据场景下的计算时间复杂度高，计算时间增长快的问题，提出一种最大互信息系数并行计算（The Parallel Computing Maximal Information Coefficient，PCMIC）方法。分别在Spark和Spark-消息传递接口（Message Passing Interface，MPI）计算框架中，在不同的数据规模和不同的噪声水平下，利用PCMIC算法对十四种典型的相关关系做并行计算。另外在不同节点数的情况下，选择两种具有代表性的相关关系来测试PCMIC算法在两种计算框架中的性能。实验结果表明：（1）PCMIC算法在两种框架下的运算效果与原始MIC近似算法相比，同样具有普适性和均匀性，而且具有良好的可扩展性。（2）随着数据规模和节点数的增加，PCMIC算法在两种框架中运算的时间增长明显比MIC近似算法慢，而且在Spark-MPI框架下的并行加速比和效率略优于Spark。（3）Spark能够支持MPI任务的调度，为研究不同并行计算框架之间的融合奠定了一定的理论和应用基础。

Parallel calculation method for Maximum Information Coefficient

In order to address the high complexity of computational time and the fast growth of maximum information coefficient (MIC) approximation algorithm in the context of big data, a parallel computing maximum information coefficient algorithm is proposed in this study. A total of fourteen typical correlations were computed in parallel using the Parallel Computing Maximal Information Coefficient (PCMIC) algorithm at different data sizes and noise levels under Spark and Spark-Message Passing Interface (MPI) computing frameworks, respectively. In addition, two representative correlations were chosen to test the performance produced by the PCMIC algorithm under the two computing frameworks with different numbers of nodes. The analysis of the experimental results leads to the following conclusions. Firstly, the PCMIC algorithm is as pervasive and uniform in both frameworks as the original MIC approximation algorithm, with scalability demonstrated. Secondly, with the increase in data size and the number of nodes, the pace of time growth is significantly slower for the PCMIC algorithm in both frameworks than for the MIC approximation algorithm. Besides, Spark is slightly outperformed by the Spark-MPI framework in parallel speedup ratio and efficiency. Lastly, Spark is capable to support the scheduling of MPI tasks, thus laying a theoretical foundation for studying the convergence between different parallel computing frameworks and its application.