Multifactor dimensionality reduction

Consider the following simple example using the exclusive OR (XOR) function. XOR is a logical operator that is commonly used in data mining and machine learning as an example of a function that is not linearly separable. The table below represents a simple dataset where the relationship between the attributes (X1 and X2) and the class variable (Y) is defined by the XOR function such that Y = X1 XOR X2.

Table 1

A machine learning algorithm would need to discover or approximate the XOR function in order to accurately predict Y using information about X1 and X2. An alternative strategy would be to first change the representation of the data using constructive induction to facilitate predictive modeling. The MDR algorithm would change the representation of the data (X1 and X2) in the following manner. MDR starts by selecting two attributes. In this simple example, X1 and X2 are selected. Each combination of values for X1 and X2 are examined and the number of times Y=1 and/or Y=0 is counted. In this simple example, Y=1 occurs zero times and Y=0 occurs once for the combination of X1=0 and X2=0. With MDR, the ratio of these counts is computed and compared to a fixed threshold. Here, the ratio of counts is 0/1 which is less than our fixed threshold of 1. Since 0/1 < 1 we encode a new attribute (Z) as a 0. When the ratio is greater than one we encode Z as a 1. This process is repeated for all unique combinations of values for X1 and X2. Table 2 illustrates our new transformation of the data.

Table 2

The machine learning algorithm now has much less work to do to find a good predictive function. In fact, in this very simple example, the function Y = Z has a classification accuracy of 1. A nice feature of constructive induction methods such as MDR is the ability to use any data mining or machine learning method to analyze the new representation of the data. Decision trees, neural networks, or a naive Bayes classifier could be used in combination with measures of model quality such as balanced accuracy[11][12] and mutual information.[13]

As illustrated above, the basic constructive induction algorithm in MDR is very simple. However, its implementation for mining patterns from real data can be computationally complex. As with any machine learning algorithm there is always concern about overfitting. That is, machine learning algorithms are good at finding patterns in completely random data. It is often difficult to determine whether a reported pattern is an important signal or just chance. One approach is to estimate the generalizability of a model to independent datasets using methods such as cross-validation.[14][15][16][17] Models that describe random data typically don't generalize. Another approach is to generate many random permutations of the data to see what the data mining algorithm finds when given the chance to overfit. Permutation testing makes it possible to generate an empirical p-value for the result.[18][19][20][21] Replication in independent data may also provide evidence for an MDR model but can be sensitive to difference in the data sets.[22][23] These approaches have all been shown to be useful for choosing and evaluating MDR models. An important step in a machine learning exercise is interpretation. Several approaches have been used with MDR including entropy analysis[9][24] and pathway analysis.[25][26] Tips and approaches for using MDR to model gene-gene interactions have been reviewed.[7][27]

Numerous extensions to MDR have been introduced. These include family-based methods,[28][29][30] fuzzy methods,[31] covariate adjustment,[32] odds ratios,[33] risk scores,[34] survival methods,[35][36] robust methods,[37] methods for quantitative traits,[38][39] and many others.

MDR has mostly been applied to detecting gene-gene interactions or epistasis in genetic studies of common human diseases such as atrial fibrillation,[40][41] autism,[42] bladder cancer,[43][44][45] breast cancer,[46] cardiovascular disease,[14] hypertension,[47][48][49] obesity,[50][51] pancreatic cancer,[52] prostate cancer[53][54][55] and tuberculosis.[56] It has also been applied to other biomedical problems such as the genetic analysis of pharmacology outcomes.[57][58][59] A central challenge is the scaling of MDR to big data such as that from genome-wide association studies (GWAS).[60] Several approaches have been used. One approach is to filter the features prior to MDR analysis.[61] This can be done using biological knowledge through tools such as BioFilter.[62] It can also be done using computational tools such as ReliefF.[63] Another approach is to use stochastic search algorithms such as genetic programming to explore the search space of feature combinations.[64] Yet another approach is a brute-force search using high-performance computing.[65][66][67]

• www.epistasis.org provides an open-source and freely-available MDR software package.
• An R package for MDR.[68]
• An sklearn-compatible Python implementation.
• An R package for Model-Based MDR.[69]
• MDR in Weka.
• Generalized MDR.

• Data mining
• Dimensionality reduction
• Epistasis
• Feature Engineering
• Machine learning
• Multilinear subspace learning

• Michalski, R. S., "Pattern Recognition as Knowledge-Guided Computer Induction," Department of Computer Science Reports, No. 927, University of Illinois, Urbana, June 1978.