Tabu Search-Enhanced Graphical Models for Classification in High Dimensions

Xue Bai, Rema Padman, Joseph Ramsey, Peter Spirtes

INFORMS Journal on Computing · 2008 · Volume 20 · Issue 3

Abstract

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.

Keywords

Markov blanket, Bayesian networks, tabu search, machine learning, text analysis, health care decision support, online marketing

Enable JavaScript for citation tools and additional paper interactions.