Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
2000-03-22
2003-02-18
Black, Thomas (Department: 2121)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
C707S793000
Reexamination Certificate
active
06523020
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to decision rules for data mining and, more particularly, to a method that generates Disjunctive Normal Form (DNF) rules using lightweight rule induction. The induction method attempts to minimize classification error.
2. Background Description
Decision trees and decision rules are well-known and related types of classifiers. The terminal nodes of a tree can be grouped into Disjunctive Normal Form (DNF) rules, only one of which is satisfied for a new case. Decision rules are also DNF rules, but allow rules to overlap, which potentially allows for more compact and interesting rule sets.
Decision tree induction methods are more efficient than those for decision rule induction—some methods for decision rule induction actually start with an induced decision tree. Procedures for pruning and optimization are relatively complex (see S. Weiss and N. Indurkhya, “Optimized Rule Induction,” IEEE EXPERT, 8(6), pp. 61-69 (1993); and W. Cohen, “Fast Effective Rule Induction,”
The XII International Conference on Machine Learning
, pp. 115-123 (1995)). In terms of predictive performance, logic-based methods have difficulty with applications having complex solutions. With lesser support for many of the rules, the induced solutions are often bedeviled by high variance, where the training error is far from the test error.
Single decision trees are often dramatically outperformed by voting methods for multiple decision trees. Such methods produce exaggeratedly complex solutions, but they may be the best obtainable with any classifier. In W. Cohen and Y. Singer, “A Simple, Fast, and Effective Rule Learner,”
Proceedings of Annual Conference of American Association for Artificial Intelligence
, pp. 335-342 (1999), boosting techniques, as described in R. Schapire, “A Brief Introduction to Boosting,”
Proceedings of International Joint Conference on Artificial Intelligence
, pp. 1401-1405 (1999), are used by a system called SLIPPER to generate a weighted set of rules that are shown to generally outperform standard rule induction techniques. While these rules can maintain clarity of explanation, they do not match the predictive performance of the strongest learning methods, such as boosted trees. Of particular interest to the present invention is J. Friedman, T. Hastie and R. Tibshirani, “Additive Logistic Regression: A Statistical View of Boosting,” Technical Report, Stanford University Statistics Department (1998) where very small trees are boosted to high predictive performance by truncated tree induction (TTI). Small trees can be decomposed into a collection of interpretable rules. Some of the boosted collections of tiny trees, even tree stumps, have actually performed best on benchmark applications.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide a lightweight rule induction method that generates compact Disjunctive Normal Form (DNF) rules.
According to the invention, each class may have an equal number of unweighted rules. A new example is classified by applying all rules and assigning the example to the class with the most satisfied rules. The induction method attempts to minimize the training error with no pruning. An overall design is specified by setting limits on the size and number of rules. During training, cases are adaptively weighted using a simple cumulative error method. The induction method is nearly linear in time relative to an increase in the number of induced rules or the number of cases. Experimental results on large benchmark datasets demonstrate that predictive performance can rival the best reported results in the literature.
REFERENCES:
patent: 5592590 (1997-01-01), Jolly
patent: 5719692 (1998-02-01), Cohen
patent: 5960422 (1999-09-01), Prasad
patent: 6003029 (1999-12-01), Agrawal et al.
patent: 6061682 (2000-05-01), Agrawal et al.
patent: 6418432 (2002-07-01), Cohen et al.
Apte et al.; “Automated Learning of Decision Rules of Text Categorization”. ACM Transactions on Infornation Systems, Jul., 1994, pp. 233-240.*
Zhou et al.; “Probabilistic Induction of Decision Trees and Disjunctive Normal Forms”. Proceedures of the 1993 IEEE International Conference on Tools with Al, Nov. 1993, pp. 140-144.*
Sasisekharan et al.; “Using Machine Learning to Monitor Network Performance”. Proceedings of the 10thConference on Al for Applications, Mar. 1994, pp. 92-98.*
Apte et al.; “RAMP: Rules Abstraction for Modeling and Prediction”. IBM Research Division Technical Report RC-20271, Jan. 1996, pp. 1-14.*
Weiss et al.; “Rule -based Machine Learning Methods for Functional Prediction”. Journal of Al Research, vol. 3, Dec. 1995, pp. 383-403.*
Weiss et al.; “Rule-based Diagnostic Decision Aids for Common Eye Problems”. IEEE Engineering in Medicine and Biology Society 10thAnnual International Conference, vol. 3, Nov. 1988, pp. 1395-1396.*
Liu, H.; “Efficient Rule Induction from Noise Data”. Expert Systems with Applications: An International Journal, vol. 10, 1996.*
S. Weiss, et al., “Optimized Rule Induction”,IEEE Expert, 8(6), pp. 61-69 (Dec. 1993).
W. Cohen, “Fast Effective Rule Induction”,The XII International Conference on Machine Learning, pp. 115-123 (1995).
W. Cohen et al., “A Simple, Fast, and Effective Rule Learner”,Proceedings of Annual Conference of American Association for Artificial Intelligence, pp. 335-342 (1999).
R. Schapire, “A Brief Introduction to Boosting”,Proceedings of International Joint Conference on Artificial Intelligence, pp. 1401-1405 (1999).
J. Friedman et al., “Additive Logistic Regression: A Statistical View of Boosting”, Technical Report, Stanford University Statistics Department (Jul. 1998).
L. Breiman, “Bagging Predictors”,Machine Learning, 24, pp. 123-140 (Sep. 1994).
S. Weiss et al., “Maximizing Text-mining Performance”,IEEE Intelligent Systems, 14(4), pp. 63-69 (Jul. 1999).
E. Bauer et al., “An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting and Variants”,Machine Learning Journal, 36(1), pp. 105-139 (Sep. 1998).
T. Dietterich, “An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees: Bagging, Boosting and Randomization”,Machine Learning Journal, 0(0), (1999).
L. Breiman, “Bias, Variance and Arcing Classifiers”, Technical Report 460, University of California, Berkeley (1996).
R. Schapire et al., “Boosting the Margin: A New Explanation for the Efectiveness of Voting Methods”,The Annuals of Statistics, 26(5), pp. 1651-1686 (May 1998).
Black Thomas
Booker Kelvin
Kaufman Stephen C.
Whitham Curtis & Christofferson, P.C.
LandOfFree
Lightweight rule induction does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Lightweight rule induction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lightweight rule induction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3144647