Improved Approximation Algorithm for Maximal Information Coefficient

Improved Approximation Algorithm for Maximal Information Coefficient

Shuliang Wang (School of Software, Beijing Institute of Technology, Beijing, China), Yiping Zhao (Software Center, Bank of China, Beijing, China), Yue Shu (Tencent Technology (Beijing) Company Limited, Beijing, China) and Wenzhong Shi (Department of Land Surveying and Geo-Informatics, The Hong Kong Polytechnic University, Hung Hom, Hong Kong, China)
Copyright: © 2017 |Pages: 18
DOI: 10.4018/IJDWM.2017010104


A novel statistical maximal information coefficient (MIC) that can detect the nonlinear relationships in large data sets was proposed by Reshef et al. (2011), with emphasis being placed on the equitability, which is a very important concept in data exploration. In this paper, an improved algorithm for approximation of the MIC (IAMIC) is proposed for the development of the equitability. Based on quadratic optimization processes, the IAMIC can search for a more optimal partition on the y-axis rather than use that which was obtained simply through the equipartition of the y-axis, to enable it to come closer to the true value of the MIC. It has been proved that the IAMIC can search for a local optimal value while using a lower number of iterations. It has also been shown that the IAMIC provides higher accuracy and a more acceptable run-time, based on both a mathematical proof and the results of simulations.
Article Preview

1. Introduction

With the large amounts of data that are being generated in various fields, and particularly in the biological and geological information field (Shekar and Xiong, 2007; Ester et al., 2000; Meyer-Schoenberger and Cukier, 2013; Surhone et al., 2010; Wang and Yuan, 2014) information field, which is growing exponentially (Hastie et al., 2009; Howe and Rhee, 2008), there is a critical need to extract the meaning from the large datasets that are obtained (Frankel and Reid, 2008; United Nations Global Pulse, 2012; McKinsey Global Institute, 2011; Rajaraman and Ullman, 2011; Vatsavai et al., 2012). However, the real-world data is always dirty, which prevents researchers to reveal the real meaning behind the data (Hernandez and Stolfo, 1998; Kim et al., 2003; Dasu, 2003; Smets, 1996). Reshef et al. (2011) proposed a new measure to identify relationships between two variable pairs, called the maximal information coefficient (MIC), and it is an interesting approach that can be used to discover relationships between variables in large data sets because of two properties: generality and equitability. Generality of MIC means it can detect more interesting relationships, including functional or not, not limited to certain functional types as Pearson correlation coefficient or Spearman rank correlation coefficienct, etc. Furthermore, Equitability ensures MIC to explore the datasets impartially, with no inclinations to specific relation types.

MIC is a powerful tool for mining the correlation between random variables, which quantify the relationship to the range from 0 to 1. The closer to 1 means closer relationship, oppositely closer to 0 says more likely two independent variables. However, the algorithm used by Reshef et al. (2011) to compute the MIC can only obtain an approximation. In this case, the accuracy of the algorithm will directly affect similarity judgement. The experiment shows that with the improvement of the accuracy of MIC, the rank of pairs according to MIC value changes, and especially some pairs of variables rank much higher. In other words, the accuracy of MIC has a great influence on the measure of dependence for each pair. Because some pairs that are strongly related are more likely be overlooked results from low accuracy of MIC, so as MIC come closer to its true value, we can detect more valuable associations.

Moreover, the standard approximation algorithm to compute the MIC resulted in some deviations from the equitability property. Therefore, the need remains to fully explore its properties to enhance the MIC.

Here, we propose an improved approximation algorithm for MIC, called the IAMIC, which offers a better solution coupled with a reasonable run-time. A mathematical proof of the ability to search for extreme values that requires fewer iterations is also provided. A comparison between the proposed algorithm and the original MIC algorithm provided by Reshef et al. is also given.

Also, the MIC has lower statistical power than distance correlation methods (Szeleky et al., 2007; 2009) in many important relationships, as noted by Simon and Tibshirani (2012), and it is claimed that this power drawback could cause MIC to lose its advantage for general use. In this paper, we propose a probable hypothesis to argue the case of the low power problem of MIC based on the results of our experiments.

The rest of this paper is organized as follows. In section 2, the logic flow of the IAMIC is presented. In section 3, the mathematical proof of the improvement offered by the IAMIC is provided. In section 4, the IAMIC is compared with the algorithms used by Reshef et al. in terms of their effectiveness and accuracy. In Section 5, the work focuses on a discussion of the assumption of associations between the MIC with power and the IAMIC. Section 6 summarizes the work that has been done previously in this field.

Complete Article List

Search this Journal:
Open Access Articles
Volume 16: 4 Issues (2020): 2 Released, 2 Forthcoming
Volume 15: 4 Issues (2019)
Volume 14: 4 Issues (2018)
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing