Patent US5719692A successfully refreshed from Google Patents.
US5719692A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Rule induction on large noisy data sets
Assignee: Nokia of America Corp
•
Filing: 1995-07-07
•
Granted: 1998-02-17
•
Expires: 2015-07-07
Abstract
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 2 n) running time characteristic of IREP, but produces rule sets which do a substantially better job of classification than those produced by IREP.
Inventors
- 👤 William W. Cohen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:02
CPC Classifications
G; G06; G06N; G06N5/00; G06N5/02; G06N5/022; G06N5/025
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
121 words
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.
Claim 2
Independent Claim
121 words
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.
Claim 3
Dependent Claim
59 words
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.
Claim 4
Dependent Claim
30 words
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.
Claim 5
Independent Claim
51 words
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.
Claim 6
Dependent Claim
35 words
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.
Claim 7
Dependent Claim
59 words
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.
Claim 8
Dependent Claim
38 words
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.
Claim 9
Dependent Claim
38 words
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.
Claim 10
Independent Claim
96 words
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.
Claim 11
Dependent Claim
56 words
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.
Claim 12
Dependent Claim
48 words
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.
Claim 13
Independent Claim
34 words
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.
Claim 14
Dependent Claim
37 words
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.
Claim 15
Dependent Claim
57 words
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.
Claim 16
Dependent Claim
47 words
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.
Claim 17
Independent Claim
105 words
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.
Claim 18
Independent Claim
105 words
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.
Claim 19
Dependent Claim
25 words
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.
Claim 20
Dependent Claim
52 words
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.
References Cited (Backward Citations)
US5588091A
Cited
US5222197A
Cited
US5265192A
Cited
US5504840A
Cited
US5481650A
Cited
US5373486A
Cited
US5444796A
Cited
US5590218A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-02-16 | 2001-08-18 | 2002-02-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-02-16 | 2005-08-18 | 2006-02-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-02-16 | 2009-08-18 | 2010-02-17 | $7700.00 | Window Closed / Lapsed |