Rule induction on large noisy data sets

• US 5,719,692 A
• Filed: 07/07/1995
• Issued: 02/17/1998
• Est. Priority Date: 07/07/1995
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Cohen, William W.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/499,247
• Time in Patent Office: 956 Days
• Field of Search: 395/10, 395/21, 395/22, 395/23, 395/50, 395/54, 395/20, 395/77
• US Class Current: 706/47
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

Efficient techniques for inducing rules used in classifying data items on a noisy data set. The prior-art IREP technique, which produces a set of classification rules by inducing each rule and then pruning it and continuing thus until a stopping condition is reached, is improved with a new rule-value metric for stopping pruning and with a stopping condition which depends on the description length of the rule set. The rule set which results from the improved IREP technique is then optimized by pruning rules from the set to minimize the description length and further optimized by making a replacement rule and a modified rule for each rule and using the description length to determine whether to use the replacement rule, the modified rule, or the original rule in the rule set. Further improvement is achieved by inducing rules for data items not covered by the original set and then pruning these rules. Still further improvement is gained by repeating the steps of inducing rules for data items not covered, pruning the rules, optimizing the rules, and again pruning for a fixed number of times. The fully-developed technique has the O(nlog² n) running time characteristic of IREP, but produces rule sets which do a substantially better job of classification than those produced by IREP.

Claims

1. A method practiced in a computer system which includes a processor and a memory system of inducing sets of classification logic rules for classifying data items from an example dataset of the data items, the sets of classification logic rules and the example dataset being stored in the memory system and the method comprising the steps performed in the processor of:

inducing a first rule set from the example dataset according to a predetermined method, the first rule set being substantially smaller than a largest rule set producible by the predetermined method, and storing the first rule set in the memory system; and

optimizing the first rule set with regard to the largest rule set to produce a second rule set.

2. The method set forth in claim 1, further comprising the steps of:

after producing the second rule set, producing a third rule set by adding rules to the second rule set to cover data items from the example dataset not covered by the second rule set; and

optimizing the third rule set to produce a new second rule set.

3. The method set forth in claim 2, wherein the method is iterated n times and the second rule set is the new second rule set produced in the nth iteration.

4. The method set forth in any of claims 2 or 3, wherein the step of optimizing the first rule set or the third rule set includes the step of computing a description length for the first rule set or the third rule set and using the description length in the optimization.

5. The method set forth in claim 4, wherein the step of optimizing the first rule set or the third rule set includes the step of pruning the first rule set or the third rule set.

6. The method set forth in claim 5, and further comprising the step of pruning the first rule set or the third rule set as each rule is induced to maximize a function ##EQU4## where p is a number of positive examples for the rule in the example dataset and n is a number of negative examples for the rule.

7. The method set forth in claim 6, wherein the step of pruning the first rule set is done by deleting rules from the first rule set such that the description length of the first rule set is reduced.

8. The method set forth in claim 5, wherein the step of pruning the first rule set is done by deleting rules from the first rule set such that the description length of the first rule set is reduced.

9. The method set forth in any of claims 2 or 3, wherein the step of optimizing the first rule set or the step of optimizing the third rule set comprises the steps performed for each rule in the first or the third rule set of:

making a modification of the rule and pruning the modification to minimize an error of the first or the third rule set; and

determining from the description length of the first or the third rule set with the rule and with the modification whether to replace the rule with the modification.

10. The method set forth in claim 9, wherein the step of making a modification comprises the steps of:

making a first modification independently of the rule; and

making a second modification by adding conditions to the rule; and

the step of determining determines whether to replace the rule with the first modification or the second modification.

11. The method set forth in claim 9, wherein the step of optimizing further comprises pruning the first or the third rule set by deleting rules from the first or the third rule set such that the description length of the first or the third rule set is reduced.

12. The method set forth in any of claims 1, 2, or 3, wherein the step of inducing the first rule set is performed by inducing the rules, rule-by-rule, until a predetermined stopping condition occurs.

13. The method set forth in claim 12, wherein the step of inducing the first rule set includes the step of checking a description length of the first rule set to determine whether the stopping condition has occurred.

14. The method set forth in claim 13, wherein the step of checking the description length of the first rule set is performed repeatedly and includes the step of comparing a current value of the description length of the first rule set with a shortest description length thus far obtained to determine whether the stopping condition has occurred.

15. The method set forth in claim 14, wherein the step of comparing the description length determines that the stopping condition has occurred when the current value of the description length of the first rule set is more than a predetermined value larger than the shortest description length.

16. A method practiced in a computer system which includes a processor and a memory system of inducing a set of classification logic rules for classifying data items from an example dataset of the data items, the rules and the example dataset being stored in the memory system and the method comprising the steps performed in the processor for each rule of:

inducing the rule on the example dataset;

adding the rule to the set of classification logic rules;

computing a description length of the set of classification logic rules with the added rule; and

terminating the method if the description length satisfies a predetermined condition.

17. The method of claim 16, wherein the predetermined condition is the description length which is a predetermined amount larger than a smallest previously-computed description length.

18. The method of claim 16, further comprising the step performed for each rule of pruning the set of classification logic rules to maximize a function ##EQU5## where p is a number of positive examples for the rule in the example dataset and n is a number of negative examples for the rule.