US5727199A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Database mining using multi-predicate classifiers
Assignee: International Business Machines Corp
•
Filing: 1995-11-13
•
Granted: 1998-03-10
•
Expires: 2015-11-13
Abstract
Abstract A computer implemented system, two-step method and computer program product which improves the operations of multi-feature extraction and which efficiently develops classification rules from a large training database. Specifically, given a large training set of data tuples, the first phase, called the feature identification phase, identifies features, which have good power in separating data tuples, based on a subset of the training set. A feature that has a good power in correlating data tuples into groups is said to have a good discriminating power. Since the feature identification phase is performed on a subset of the training set, processing costs are minimized. Limiting this phase to the identification of features having good discriminating power ensures that the use of a subset of the training set does not adversely affect the validity of the conclusions drawn therefrom. In the second phase, called the feature combination phase, the identified features are evaluated in combination against the entire training set to determine the final classification rules. The prior identification of features having good discriminating power advantageously minimizes processing costs during this phase (which is run against the entire training set). The use of multiple features advantageously increases the discrimination power beyond that of the individual features.
Inventors
- 👤 Ming-Syan Chen
- 👤 Philip Shi-Ling Yu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 16:13
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2465; Y; Y02; Y02D; Y02D10/00; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99936
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
154 words
A computer-implemented method of mining classification rules from a computer database which includes a plurality of data tuples, each data tuple including a plurality of features, the database further including a training set including the data tuples, each data tuple in the training set including a group identifier, comprising the steps of: (a) evaluating each feature in a subset of the training set as a function of its correlation with the group identifier, and identifying said features, responsive to said step of evaluating, having an ID score exceeding a predetermined ID threshold; (b) combining identified features into feature pairs and evaluating each feature pair in the training set as a function of its correlation with said any one of the group identifiers, and identifying said feature pairs having a combination score which exceeds a predetermined feature combination threshold; and (c) classifying the database as a function the identified features and the identified feature pair.
Claim 2
Dependent Claim
154 words
A computer-implemented method of mining classification rules from a computer database which includes a plurality of data tuples, each data tuple including a plurality of features, the database further including a training set including the data tuples, each data tuple in the training set including a group identifier, comprising the steps of: (a) evaluating each feature in a subset of the training set as a function of its correlation with the group identifier, and identifying said features, responsive to said step of evaluating, having an ID score exceeding a predetermined ID threshold; (b) combining identified features into feature pairs and evaluating each feature pair in the training set as a function of its correlation with said any one of the group identifiers, and identifying said feature pairs having a combination score which exceeds a predetermined feature combination threshold; and (c) classifying the database as a function the identified features and the identified feature pair.
Claim 3
Dependent Claim
27 words
The method of claim 1, further comprising the step of storing the identified features and the identified feature pair in a memory, responsive to said step (b).
Claim 4
Dependent Claim
100 words
The method of claim 1, wherein said step of evaluating each feature as a function of its correlation with the group identifier comprises the steps of: sorting the data tuples according to the group identifier; performing the following steps for said each feature in the subset of the training set, wherein said each feature includes a plurality of values: for each value of a given feature, determining a winner group identifier which is associated with a greatest number of the data tuples including said each value; and determining a percentage of the data tuples associated with the winner group identifier.
Claim 5
Dependent Claim
64 words
The method of claim 1 wherein said step of evaluating each feature pair as a function of its correlation with said any one of the group identifiers comprises the steps of: determining a maximum match index for said each identified feature pair and eliminating from further processing all identified feature pairs having a maximum match index score less than a maximum match index threshold.
Claim 6
Dependent Claim
97 words
The method of claim 1 wherein said step of evaluating each feature pair as a function of its correlation with said any one of the group identifiers comprises the steps of: performing the following steps for said each feature pair in the training set, wherein said each feature pair includes a plurality of values: for each value of a given feature, determining a combination winner group identifier which is associated with a greatest number of the data tuples including said each value; and determining a percentage of the data tuples associated with the combination winner group identifier.
Claim 7
Dependent Claim
202 words
A computer program product comprising: a computer usable medium having computer readable program code means embodied therein for mining classification rules from a computer database which includes a plurality of data tuples, each data tuple including a plurality of features, the database further including a training set including the data tuples, each data tuple in the training set including a group identifier, said computer readable program code means comprising: feature identification program code means for causing the computer to evaluate each feature in a subset of the training set as a function of its correlation with the group identifier, and identify said features having an ID score exceeding a predetermined ID threshold; feature combination program code means for causing the computer to combine identified features into feature pairs and evaluate each feature pair in the training set as a function of its correlation with said any one of the group identifiers, and identify said feature pairs having a combination score which exceeds a predetermined feature combination threshold, responsive to said computer readable feature identification program code means; and computer readable program code means for causing the computer to classify the database as a function the identified features and the identified feature pair.
Claim 8
Dependent Claim
202 words
A computer program product comprising: a computer usable medium having computer readable program code means embodied therein for mining classification rules from a computer database which includes a plurality of data tuples, each data tuple including a plurality of features, the database further including a training set including the data tuples, each data tuple in the training set including a group identifier, said computer readable program code means comprising: feature identification program code means for causing the computer to evaluate each feature in a subset of the training set as a function of its correlation with the group identifier, and identify said features having an ID score exceeding a predetermined ID threshold; feature combination program code means for causing the computer to combine identified features into feature pairs and evaluate each feature pair in the training set as a function of its correlation with said any one of the group identifiers, and identify said feature pairs having a combination score which exceeds a predetermined feature combination threshold, responsive to said computer readable feature identification program code means; and computer readable program code means for causing the computer to classify the database as a function the identified features and the identified feature pair.
Claim 9
Dependent Claim
30 words
The computer program product of claim 6, comprising: a memory for storing the identified features and the identified feature pair, responsive to said computer readable feature combination program code means.
Claim 10
Dependent Claim
155 words
The computer program product of claim 6 wherein said feature identification program code means for causing the computer to evaluate each feature in a subset of the training set as a function of its correlation with the group identifier, comprises: computer readable program code means for causing the computer to effect sorting the data tuples according to the group identifier; computer readable program code means for causing the computer to iteratively execute the following for said each feature in the subset of the training set, wherein said each feature includes a plurality of values: computer readable program code means for causing the computer, for each value of a given feature, to determine a winner group identifier which is associated with a greatest number of the data tuples including said each value; and computer readable program code means for causing the computer to determine a percentage of the data tuples associated with the winner group identifier.
Claim 11
Dependent Claim
92 words
The computer program product of claim 6 wherein said feature combination program code means for causing the computer to combine identified features into feature pairs and evaluate each feature pair in the training set as a function of its correlation with said any one of the group identifiers, comprises: computer readable program code means for causing the computer to determine a maximum match index for said each identified feature pair and eliminate from further processing all identified feature pairs having a maximum match index score less than a maximum match index threshold.
Claim 12
Dependent Claim
145 words
The computer program product of claim 6 wherein said feature combination program code means for causing the computer to combine identified features into feature pairs and evaluate each feature pair in the training set as a function of its correlation with said any one of the group identifiers, comprises: computer readable program code means for causing the computer to iteratively execute the following for said each feature pair in the training set, wherein said each feature pair includes a plurality of values: computer readable program code means for causing the computer, for each value of a given feature, to determine a combination winner group identifier which is associated with a greatest number of the data tuples including said each value; and computer readable program code means for causing the computer to determine a percentage of the data tuples associated with the combination winner group identifier.
Claim 13
Dependent Claim
173 words
A program storage device readable by a computer tangibly embodying a program of instructions executable by said computer to perform method steps for mining classification rules from a computer database which includes a plurality of data tuples, each data tuple including a plurality of features, the database further including a training set including the data tuples, each data tuple in the training set including a group identifier, said method steps comprising: (a) evaluating each feature in a subset of the training set as a function of its correlation with the group identifier, and identifying said features, responsive to said step of evaluating, having an ID score exceeding a predetermined ID threshold; (b) combining identified features into feature pairs and evaluating each feature pair in the training set as a function of its correlation with said any one of the group identifiers, and identifying said feature pairs having a combination score which exceeds a predetermined feature combination threshold; and (c) classifying the database as a function the identified features and the identified feature pair.
Claim 14
Dependent Claim
173 words
A program storage device readable by a computer tangibly embodying a program of instructions executable by said computer to perform method steps for mining classification rules from a computer database which includes a plurality of data tuples, each data tuple including a plurality of features, the database further including a training set including the data tuples, each data tuple in the training set including a group identifier, said method steps comprising: (a) evaluating each feature in a subset of the training set as a function of its correlation with the group identifier, and identifying said features, responsive to said step of evaluating, having an ID score exceeding a predetermined ID threshold; (b) combining identified features into feature pairs and evaluating each feature pair in the training set as a function of its correlation with said any one of the group identifiers, and identifying said feature pairs having a combination score which exceeds a predetermined feature combination threshold; and (c) classifying the database as a function the identified features and the identified feature pair.
Claim 15
Dependent Claim
29 words
The program storage device of claim 11, further comprising the step of storing the identified features and the identified feature pair in a memory, responsive to said step (b).
Claim 16
Dependent Claim
103 words
The program storage device method of claim 11, wherein said step of evaluating each feature as a function of its correlation with the group identifier comprises the steps of: sorting the data tuples according to the group identifier; performing the following steps for said each feature in the subset of the training set, wherein said each feature includes a plurality of values: for each value of a given feature, determining a winner group identifier which is associated with a greatest number of the data tuples including said each value; and determining a percentage of the data tuples associated with the winner group identifier.
Claim 17
Dependent Claim
66 words
The program storage device of claim 11 wherein said step of evaluating each feature pair as a function of its correlation with said any one of the group identifiers comprises the steps of: determining a maximum match index for said each identified feature pair and eliminating from further processing all identified feature pairs having a maximum match index score less than a maximum match index threshold.
Claim 18
Dependent Claim
99 words
The program storage device of claim 11 wherein said step of evaluating each feature pair as a function of its correlation with said any one of the group identifiers comprises the steps of: performing the following steps for said each feature pair in the training set, wherein said each feature pair includes a plurality of values: for each value of a given feature, determining a combination winner group identifier which is associated with a greatest number of the data tuples including said each value; and determining a percentage of the data tuples associated with the combination winner group identifier.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-03-09 | 2001-09-08 | 2002-03-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-03-09 | 2005-09-08 | 2006-03-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-03-09 | 2009-09-08 | 2010-03-10 | $7700.00 | Window Closed / Lapsed |