Selecting feature subset for high dimensional data via the propositional FOIL rules

• Published in: Pattern recognition 2013-01, Vol.46 (1), p.199-214
• Main Authors: Wang, Guangtao, Song, Qinbao, Xu, Baowen, Zhou, Yuming
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Classifiers; Consistency; Detection, estimation, filtering, equalization, prediction; Exact sciences and technology; Feature interaction; Feature subset selection; Filter method; Foils; Information, signal and communications theory; Interactive; Propositional FOIL rule; Redundant; Rule based; Signal and communications theory; Signal representation. Spectral analysis; Signal, noise; Telecommunications and information theory
• ISSN: 0031-3203; 1873-5142
• DOI: 10.1016/j.patcog.2012.07.028

Feature interaction is an important issue in feature subset selection. However, most of the existing algorithms only focus on dealing with irrelevant and redundant features. In this paper, a propositional FOIL rule based algorithm FRFS, which not only retains relevant features and excludes irrelevant and redundant ones but also considers feature interaction, is proposed for selecting feature subset for high dimensional data. FRFS first merges the features appeared in the antecedents of all FOIL rules, achieving a candidate feature subset which excludes redundant features and reserves interactive ones. Then, it identifies and removes irrelevant features by evaluating features in the candidate feature subset with a new metric CoverRatio, and obtains the final feature subset. The efficiency and effectiveness of FRFS are extensively tested upon both synthetic and real world data sets, and it is compared with other six representative feature subset selection algorithms, including CFS, FCBF, Consistency, Relief-F, INTERACT, and the rule-based FSBAR, in terms of the number of selected features, runtime and the classification accuracies of the four well-known classifiers including Naive Bayes, C4.5, PART and IB1 before and after feature selection. The results on the five synthetic data sets show that FRFS can effectively identify irrelevant and redundant features while reserving interactive ones. The results on the 35 real world high dimensional data sets demonstrate that compared with other six feature selection algorithms, FRFS cannot only efficiently reduce the feature space, but also can significantly improve the performance of the four well-known classifiers. ► We originally propose a novel feature selection algorithm based on FOIL rule. ► We define irrelevant, redundant and interactive features by the FOIL rule. ► The algorithm can handle irrelevant, redundant and interactive features. ► The algorithm excels the other six algorithms in raising accuracies of classifiers. ► The proposed algorithm is quite efficient and works well on high-dimensional data.