Feature interaction is an important issue underlying most machine learning problems. Many approaches for classification do consider multiple features simultaneously in building predictive models, but they are not targeted at explicitly identifying feature interactions among all possible pairs of features, or subsets of features. In high-throughput biological data analysis, exploring phenotype-related interactions among genes (features) can provide significant insights to biological interactions and reveal potential biomarkers.

In this thesis, we define a theoretical framework for feature interaction in the context of labeled data and an empirical formulation for feature interaction. We propose an efficient method which applies common distance measures and linear discriminative analysis to explicitly search for feature interaction. The proposed method has been applied to identify significant interacting gene pairs from microarray data. Experiments on public microarray data sets have demonstrated the effectiveness of the proposed method and the statistical significance of the identified iterating gene pairs.