Towards efficient variables ordering for Bayesian networks classifier

摘要

Traditionally, the task of learning Bayesian Networks (BNs) from data has been treated as a NP-Hard search problem. To overcome such difficulty in terms of computational complexity, several approximations have been designed, such as imposing a previous ordering on the domain attributes that restrict the number of Bayesian structures to be learned or using other approaches trying to reduce the state space of this problem. In this paper, we propose a simple method based on feature ranking algorithms which has low computational complexity (O(n2), where n is the number of variables) and produces good results. We empirically demonstrate that feature ranking algorithms (namely, Chi-Squared and Information Gain) can be used to define efficient variables ordering in the BNC learning context. The proposed method can bring improvements, when using the K2 algorithm, to learn a Bayesian Network Classifier from data.