Tractable Average-Case Analysis of Naive Bayesian Classifiers

Abstract

In this paper we present an average-case analysis of the naive Bayesian classifier, a simple induction algorithm that performs well in many domains. Our analysis assumes a monotone `M of N' target concept and training data that consists of independent Boolean attributes. The analysis supposes a known target concept and distribution of instances, but includes parameters for the number of training cases, the number of irrelevant, relevant, and necessary attributes, the probability of each attribute, and the amount of class noise. Our approach differs from most previous average-case analyses by introducing approximations to achieve computational tractability. This lets us explore the behavioral implications for larger training and attribute sets than the earlier exact analyses, and experimental studies show that the analysis makes very accurate predictions despite its use of approximations. In closing, we suggest promising directions for future research on the averag...