Tabu Search-Enhanced Graphical Models for Classification in High Dimensions

Data sets with many discrete variables and relatively few cases arise in health care, e-commerce, information security, text mining, and many other domains. Learning effective and efficient prediction models from such data sets is a challenging task. In this paper, we propose a tabu search-enhanced Markov blanket (TS/MB) algorithm to learn a graphical Markov blanket model for classification of high-dimensional data sets. The TS/MB algorithm makes use of Markov blanket neighborhoods: restricted neighborhoods in a general Bayesian network based on the Markov condition. Computational results from real-world data sets drawn from several domains indicate that the TS/MB algorithm, when used as a feature selection method, is able to find a parsimonious model with substantially fewer predictor variables than is present in the full data set. The algorithm also provides good prediction performance when used as a graphical classifier compared with several machine-learning methods.