We consider a classification problem wherein the class features are not given a priori. The classifier is responsible for selecting the features, to minimize the cost of observing features while also maximizing the classification performance. We propose a reward-directed Bayesian classifier (RDBC) to solve this problem. The RDBC features an internal state structure for preserving the feature dependence, and is formulated as a partially observable Markov decision process (POMDP). The results on a diabetes dataset show the RDBC with a moderate number of states significantly improves over the naive Bayes classifier, both in prediction accuracy and observation parsimony. It is also demonstrated that the RDBC performs better by using more states to increase its memory. © 2006 IEEE.