US6823323B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automatic classification method and apparatus
Assignee: Micro Focus LLC
•
Filing: 2001-04-26
•
Granted: 2004-11-23
•
Expires: 2021-04-26
Abstract
Abstract Methods and apparatus for classifying an instance (i.e., a data item or a record) automatically into one or more classes selected from a set of potential classes are described. This multi-class classification approach enables instances to be classified with high accuracy, even when the number of classes is very large. In accordance with one classification scheme, a subset of two or more classes to which the instance is determined to most likely belong is selected from the set of potential classes. A classifier that is generated from a set of training records corresponding to a class set inclusive of the selected subset of classes is applied to the instance a to identify at least one class to which the instance most likely belongs.
Inventors
- 👤 George H. Forman
- 👤 Henri J. Suermondt
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 10:02
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/35; G06F16/353; G06F18/00; G06F18/20; G06F18/25; G06F18/254; G06V; G06V30/00; G06V30/10; G06V30/24; G06V30/242
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
91 words
A machine-implemented method of classifying an instance into one or more classes selected from a set of potential classes, comprising: selecting from the set of potential classes a subset of two or more of the potential classes to which the instance is determined to most likely belong; and applying to the instance a scrutiny classifier generated from a set of training records, each including a respective class label matching a corresponding class in the selected subset of classes, to identify at least one class to which the instance most likely belongs.
Claim 2
Dependent Claim
91 words
A machine-implemented method of classifying an instance into one or more classes selected from a set of potential classes, comprising: selecting from the set of potential classes a subset of two or more of the potential classes to which the instance is determined to most likely belong; and applying to the instance a scrutiny classifier generated from a set of training records, each including a respective class label matching a corresponding class in the selected subset of classes, to identify at least one class to which the instance most likely belongs.
Claim 3
Dependent Claim
32 words
The method of claim 1 , wherein the subset of classes is selected based upon assignment to each of the potential classes a probability estimate of the instance belonging to the class.
Claim 4
Dependent Claim
25 words
The method of claim 2 , wherein the selected subset of classes consists of a preselected number of potential classes having highest assigned probability estimates.
Claim 5
Dependent Claim
34 words
The method of claim 2 , wherein the selected subset of classes consists of a number of potential classes having highest assigned probability estimates and a cumulative assigned probability estimate exceeding a preselected threshold.
Claim 6
Dependent Claim
38 words
The method of claim 2 , wherein the probability estimates are assigned to each potential class by applying to the instance a ballpark classifier generated from a set of training records corresponding to the set of potential classes.
Claim 7
Dependent Claim
18 words
The method of claim 5 , wherein the ballpark classifier is generated by a Naïve Bayes inducing algorithm.
Claim 8
Dependent Claim
23 words
The method of claim 1 , wherein the subset of classes is selected based at least in part upon a prescribed misclassification cost.
Claim 9
Dependent Claim
18 words
The method of claim 1 , wherein the scrutiny classifier is generated by a Naïve Bayes inducing algorithm.
Claim 10
Dependent Claim
18 words
The method of claim 1 , wherein the scrutiny classifier is generated by a decision tree inducing algorithm.
Claim 11
Dependent Claim
18 words
The method of claim 1 , further comprising generating the scrutiny classifier from the set of training records.
Claim 12
Dependent Claim
33 words
The method of claim 10 , wherein the scrutiny classifier is generated from the set of training records corresponding to the selected subset of classes after the subset of classes has been selected.
Claim 13
Dependent Claim
21 words
The method of claim 10 , wherein the scrutiny classifier is generated beforehand in anticipation of the instance to be classified.
Claim 14
Dependent Claim
23 words
The method of claim 12 , wherein the scrutiny classifier is generated based upon an occurrence probability estimate for the inclusive class set.
Claim 15
Dependent Claim
26 words
The method of claim 13 , further comprising selecting an inclusive class set encompassing the selected subset of classes from which to generate the scrutiny classifier.
Claim 16
Dependent Claim
48 words
The method of claim 1 , further comprising applying to the instance a classifier generated from a set of training records corresponding to two or more classes identified by the scrutiny classifier to identify at least one class to which the instance is determined to most likely belong.
Claim 17
Dependent Claim
109 words
A data processing machine for classifying an instance into one or more classes selected from a set of potential classes, comprising: a ballpark classifier configured to select from the set of potential classes a subset of two or more classes to which the instance is determined to most likely belong; and a scrutiny classifier generated from a set of training records, each including a respective class label matching a corresponding class in the subset of classes selected by the ballpark classifier for a given instance, the scrutiny classifier being configured to identify from the selected subset of classes at least one class to which the instance most likely belongs.
Claim 18
Dependent Claim
109 words
A data processing machine for classifying an instance into one or more classes selected from a set of potential classes, comprising: a ballpark classifier configured to select from the set of potential classes a subset of two or more classes to which the instance is determined to most likely belong; and a scrutiny classifier generated from a set of training records, each including a respective class label matching a corresponding class in the subset of classes selected by the ballpark classifier for a given instance, the scrutiny classifier being configured to identify from the selected subset of classes at least one class to which the instance most likely belongs.
Claim 19
Dependent Claim
25 words
The machine of claim 16 , wherein the ballpark classifier is generated from a set of training records corresponding to the set of potential classes.
Claim 20
Dependent Claim
43 words
The machine of claim 16 , further comprising an inducer configured to generate a scrutiny classifier from a subset of the training records corresponding to a class set inclusive of a subset of classes selected by the ballpark classifier for a given instance.
Claim 21
Dependent Claim
37 words
The machine of claim 18 , wherein the inducer is configured to generate the scrutiny classifier from the set of training records corresponding to the selected subset of classes after the subset of classes has been selected.
Claim 22
Dependent Claim
106 words
A computer program residing on a computer-readable medium for causing a processor executing the computer program to classifying an instance into one or more classes selected from a set of potential classes, the computer program comprising instructions to: select from the set of potential classes a subset of two or more classes to which the instance is determined to most likely belong; and apply to the instance a scrutiny classifier generated from a set of training records, each including a respective class label matching a corresponding class in the selected subset of classes, to identify at least one class to which the instance most likely belongs.
Claim 23
Dependent Claim
106 words
A computer program residing on a computer-readable medium for causing a processor executing the computer program to classifying an instance into one or more classes selected from a set of potential classes, the computer program comprising instructions to: select from the set of potential classes a subset of two or more classes to which the instance is determined to most likely belong; and apply to the instance a scrutiny classifier generated from a set of training records, each including a respective class label matching a corresponding class in the selected subset of classes, to identify at least one class to which the instance most likely belongs.
References Cited (Backward Citations)
US5371807A
Cited
US5671333A
Cited
US5991709A
Cited
US6061675A
Cited
US5719692A
Cited
US5835633A
Cited
US5787274A
Cited
US6301571B1
Cited
US6182058B1
Cited
US5930803A
Cited
US6137911A
Cited
US5930788A
Cited
US6161130A
Cited
US6192360B1
Cited
US6519580B1
Cited
US20020083067A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-11-23 | 2008-05-24 | 2008-11-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-11-23 | 2012-05-24 | 2012-11-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-11-23 | 2016-05-24 | 2016-11-23 | $7700.00 | Window Closed / Lapsed |