Prediction with local patterns using cross-entropy
Heikki Mannila, Dmitry Pavlov, Padhraic Smyth · 1999
Sets of local patterns in the forms of rules and co-occurrence counts are produced by many data mining methods such as association rule algorithms.While such patterns can yield useful insights it is not obvious how to synthesize local sparse information into a coherent global predictive model.We study the use of a cross-entropy approach to combining local patterns.Each local pattern is viewed as a constraint on an appropriate high-order joint distribution of interest.Typically, a set of patterns returned by a data mining algorithm under-constrains the high-order model.The cross-entropy criterion is used to select a specific distribution in this constrained family relative to a prior.We review the iterative-scaling algorithm which is an iterative technique for hiding a joint distribution given constraints.We then illustrate the application of this method to two specific problems.The first problem is combining information about frequent itemsets.We show that the cross-entropy approach can be used for query selectivity estimation for O/l data sets.The results show that we can accurately answer a large class of queries using just a small set of aggregate information.The second problem involves sequence modeling using historical rules, with an application to protejn sequences.We conclude that viewing local patterns as constraints on a high-order probability model is a useful and principled framework for prediction based on large sets of mined patterns.