Ad Hoc Attribute-Value Prediction

Abstract

The evolving ease and efficiency in accessing large amounts of data presents an opportunity to execute prediction tasks based on this data (Hunt, Marin, & Stone 1964). Research in learning-from-example has addressed this opportunity with algorithms that induce either decision structures (ID3) or classification rules (AQ15). Lazy learning research on the other hand, delay the model construction to strictly satisfy a prediction task (Aha, Kibler, & Albert 1991). To support a prediction query against a data set, current techniques require a large amount of preprocessing to either construct a complete domain model, or to determine attribute relevance. Our work in this area is to develop an algorithm that will automatically return a probabilistic classification rule for a prediction query with equal accuracy to current techniques but with no preprocessing requirements. The proposed algorithm, DBPredictor, combines the delayed model construction approach of lazy learning along with the information theoretic measure and top-down heuristic search of learning-from-example algorithms. The algorithm induces only the information required to satisfy the prediction query and avoids the attribute relevance tests required by the nearest-neighbour measures of lazy learning. Given a data set in some domain, an attributevalue prediction query requests the prediction of an attribute’s value for some partially described event drawn from this domain. Applicable classification rules for an attribute-value prediction query are shown to be based on the exponential number of combinations of the attribute-values specified in the query. DBPredictor performs an informed top-down search that incrementally specializes one attribute-value at a time to locate a maximally valued classification rule. In a sense the algorithm iteratively selects the next most relevant attribute-value for this query. If interrupted, the algorithm reports the best encountered classification rule to date. Given a query with n instantiated values the