Feature selection and classification using ensembles of genetic programs and within-class and between-class permutations

Many feature selection methods are based on the assumption that important features are highly correlated with their corresponding classes, but mainly uncorrelated with each other. Often, this assumption can help eliminate redundancies and produce good predictors using only a small subset of features. However, when the predictability depends on interactions between features, such methods will fail to produce satisfactory results. In this paper a method that can find important features, both independently and dependently discriminative, is introduced. This method works by performing two different types of permutation tests that classify each of the features as either irrelevant, independently predictive or dependently predictive. It was evaluated using a classifier based on an ensemble of genetic programs. The attributes chosen by the permutation tests were shown to yield classifiers at least as good as the ones obtained when all attributes were used during training — and often better. The proposed method also fared well when compared to other attribute selection methods such as RELIEFF and CFS. Furthermore, the ability to determine whether an attribute was independently or dependently predictive was confirmed using artificial datasets with known dependencies.