In some learning settings, the cost of acquiring features for classification

must be paid up front, before the classifier is evaluated. In this paper,

we introduce the forensic classification problem and present a new algorithm for

building decision trees that maximizes classification accuracy while minimizing

total feature costs. By expressing the ID3 decision tree algorithm in an information

theoretic context, we derive our algorithm from a well-formulated problem

objective. We evaluate our algorithm across several datasets and show that, for

a given level of accuracy, our algorithm builds cheaper trees than existing methods.

Finally, we apply our algorithm to a real-world system, CLARIFY. CLARIFY

classifies unknown or unexpected program errors by collecting statistics during

program runtime which are then used for decision tree classification after an error

has occurred. We demonstrate that if the classifier used by the CLARIFY system

is trained with our algorithm, the computational overhead (equivalently, total feature

costs) can decrease by many orders of magnitude with only a slight (< 1%)

reduction in classification accuracy.

In  ECML

Details