Learning Trees an ules with Set-val ed Features
William W. Cohen · 1996
In most learning systems examples are represented as fixed-length “feature vectors”, the components of which are either real numbers or nominal val-ues. W e propose an extension of the feature-vector representation that allows the value of a feature to be a set of strings; for instance, to represent a small white and black dog with the nominal features size and species and the set-valued feature color, one might use a feature vec-tor with size=small, species=canis-f amiliaris and color= { white, black}. Since we make no assumptions about the number of possible set elements, this exten-sion of the traditional feature-vector representation is closely connected to Blum’s “infinite attribute ” rep resentation. We argue that many decision tree and rule learning algorithms can be easily extended to set-valued features. We also show by example that many real-world learning problems can be efficiently and nat-urally represented with set-valued features; in particu-lar, text categorization problems and problems that arise in propositionalizing first-order representations lend themselves to set-valued features.