Article Preview
Top1. 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.