Data mining model building using attribute importance

US 20030212691A1
Filed: 04/09/2003
Published: 11/13/2003
Est. Priority Date: 05/10/2002
Status: Active Grant

First Claim

Patent Images

1. A method of selecting predictive attributes for a data mining model comprising the steps of:

receiving a dataset having a plurality of predictor attributes;

for each predictor attribute, determining a predictive quality of the predictor attribute based on a predictor variance of the predictor attribute;

selecting at least one predictor attribute based on the determined predictive quality of the predictor attribute; and

building a data mining model including only the selected at least one predictor attribute.

View all claims

1 Assignment

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

A system, method, and computer program product that uses attribute importance (AI) to reduce the time and computation resources required to build data mining models, and which provides a corresponding reduction in the cost of data mining. Attribute importance (AI) involves a process of choosing a subset of the original predictive attributes by eliminating redundant, irrelevant or uninformative ones and identifying those predictor attributes that may be most helpful in making predictions. A new algorithm Predictor Variance is proposed and a method of selecting predictive attributes for a data mining model comprises the steps of receiving a dataset having a plurality of predictor attributes, for each predictor attribute, determining a predictive quality of the predictor attribute, selecting at least one predictor attribute based on the determined predictive quality of the predictor attribute, and building a data mining model including only the selected at least one predictor attribute.

160 Citations

46 Claims

1. A method of selecting predictive attributes for a data mining model comprising the steps of:
- receiving a dataset having a plurality of predictor attributes;
  
  for each predictor attribute, determining a predictive quality of the predictor attribute based on a predictor variance of the predictor attribute;
  
  selecting at least one predictor attribute based on the determined predictive quality of the predictor attribute; and
  
  building a data mining model including only the selected at least one predictor attribute.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
- - 2. The system of claim 1, wherein the step of determining a predictive quality of the predictor attribute comprises the steps of:
    - determining a predictive quality of the predictor attribute using an attribute importance algorithm.
  - 3. The system of claim 2, wherein the attribute importance algorithm comprises:
    - a predictor variance algorithm operable to select predictor attributes based on estimates of variances of predictor/target combinations and variance with respect to other predictors; and
      
      a selection criteria algorithm operable to select predictor attributes based on a combination of search and evaluation measures of the predictor attributes.
  - 4. The system of claim 2, wherein the attribute importance algorithm comprises the step of:
    - selecting predictor attributes based on selection criteria using a combination of search and evaluation measures of the predictor attributes.
  - 5. The system of claim 2, wherein the attribute importance algorithm comprises the steps of:
    - ranking the predictor attributes according to evaluation criteria; and
      
      selecting a minimum set of predictor attributes that satisfies the evaluation criteria.
  - 6. The method of claim 4, wherein the step of ranking the predictor attributes according to evaluation criteria comprises the steps of:
    - associating each predictor attribute with a rank based on the evaluation criteria; and
      
      forming a result set comprising the predictor attribute, a value of the predictor attribute, and the rank of the predictor attribute.
  - 7. The method of claim 5, wherein the step of selecting a minimum set of predictor attributes that satisfies the evaluation criteria comprises the step of:
    - selecting a minimum set of predictor attributes that satisfies the evaluation criteria using the result set.
  - 8. The method of claim 6, wherein the step of associating each predictor attribute with a rank based on the evaluation criteria comprises the step of:
    - ranking each predictor attribute according to at least one of accuracy, consistency, information, distance, dependence, relevance, and importance of the attribute compared to other attributes.
  - 9. The method of claim 6, wherein the step of associating each predictor attribute with a rank based on the evaluation criteria comprises the step of:
    - ranking each predictor attribute using Predictor Variance algorithm.
  - 10. The method of claim 2, wherein the attribute importance algorithm comprises the step of:
    - selecting predictor attributes based on estimates of variances of predictor/target combinations and variance with respect to other predictors.
  - 11. The method of claim 1, wherein the step of determining a predictive quality of the predictor attribute comprises the step of:
    - selecting predictor attributes using a predictor variance algorithm based on estimates of variances of predictor/target combinations and variance with respect to other predictors.
  - 12. The method of claim 11, wherein the step of determining a predictive quality of the predictor attribute further comprises the step of:
    - selecting predictor attributes based on selection criteria using a combination of search and evaluation measures of the predictor attributes.
  - 13. The method of claim 11, wherein the step of determining a predictive quality of the predictor attribute comprises the step of:
    - determining a predictor variance PV according to;
      
      $PV (P_{a}) = \sum_{i, k = 1}^{m, n} {((\frac{P_{i} T_{k}}{T_{k}} - \frac{1}{mn} \sum_{j, q = 1}^{n, n} \frac{P_{j} T_{q}}{T_{q}}))}^{2} / n \sum_{i = 1}^{m} {(P_{i} - \frac{1}{m} \sum_{j = 1}^{n} P_{j})}^{2},$ wherein P is the predictor and T is the target, P has values 1 . . . m, and T has values 1 . . . n.
  - 14. The method of claim 11, wherein the step of determining a predictive quality of the predictor attribute comprises the steps of:
    - determining a variance Q of all predictors ignoring a predictor P_aaccording to;
      
      $Q_{a} = \frac{1}{m - 1} (\sum_{i = 1 | i!= a}^{m - 1} {(P_{i} - \frac{1}{m - 1} \sum_{j = 1}^{m - 1} P_{j})}^{2}); and$ determining a predictor variance PV according to;
      
      $PV (P_{a}) = \sum_{i, k = 1}^{m, n} {(\frac{P_{i} T_{k}}{T_{k}} - \frac{1}{{mnQ}_{a}} \sum_{j, q = 1}^{m, n} \frac{P_{j} T_{q}}{T_{q}})}^{2} / n \sum_{i = 1}^{m} {(P_{i} - \frac{1}{m} \sum_{j = 1}^{m} P_{j})}^{2},$ wherein P is the predictor and T is the target, P has values 1 . . . m, and T has values 1 . . . n.

15. A system for selecting predictive attributes for a data mining model comprising:
- a processor operable to execute computer program instructions;
  
  a memory operable to store computer program instructions executable by the processor; and
  
  computer program instructions stored in the memory and executable to perform the steps of;
  
  receiving a dataset having a plurality of predictor attributes;
  
  for each predictor attribute, determining a predictive quality of the predictor attribute based on a predictor variance of the predictor attribute;
  
  selecting at least one predictor attribute based on the determined predictive quality of the predictor attribute; and
  
  building a data mining model including only the selected at least one predictor attribute.
- View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29)
- - 16. The system of claim 15, wherein the step of determining a predictive quality of the predictor attribute comprises the steps of:
    - determining a predictive quality of the predictor attribute using an attribute importance algorithm.
  - 17. The system of claim 16, wherein the attribute importance algorithm comprises:
    - a predictor variance algorithm operable to select predictor attributes based on estimates of variances of predictor/target combinations and variance with respect to other predictors; and
      
      a selection criteria algorithm operable to select predictor attributes based on a combination of search and evaluation measures of the predictor attributes.
  - 18. The system of claim 16, wherein the attribute importance algorithm comprises the step of:
    - selecting predictor attributes based on selection criteria using a combination of search and evaluation measures of the predictor attributes.
  - 19. The system of claim 16, wherein the attribute importance algorithm comprises the steps of:
    - ranking the predictor attributes according to evaluation criteria; and
      
      selecting a minimum set of predictor attributes that satisfies the evaluation criteria.
  - 20. The system of claim 19, wherein the step of ranking the predictor attributes according to evaluation criteria comprises the steps of:
    - associating each predictor attribute with a rank based on the evaluation criteria; and
      
      forming a result set comprising the predictor attribute, a value of the predictor attribute, and the rank of the predictor attribute.
  - 21. The system of claim 20, wherein the step of selecting a minimum set of predictor attributes that satisfies the evaluation criteria comprises the step of:
    - selecting a minimum set of predictor attributes that satisfies the evaluation criteria using the result set.
  - 22. The system of claim 21, wherein the step of associating each predictor attribute with a rank based on the evaluation criteria comprises the step of:
    - ranking each predictor attribute according to at least one of accuracy, consistency, information, distance, dependence, relevance, and importance of the attribute compared to other attributes.
  - 23. The system of claim 22, wherein the step of associating each predictor attribute with a rank based on the evaluation criteria comprises the step of:
    - ranking each predictor attribute using at least one of Information Gain, Distance Measure, and Dependence Measure.
  - 24. The system of claim 16, wherein the attribute importance algorithm comprises the step of:
    - selecting predictor attributes based on estimates of variances of predictor/target combinations and variance with respect to other predictors.
  - 25. The system of claim 16, wherein the attribute importance algorithm comprises the steps of:
    - for each predictor attribute column n, for each possible value i, and for each possible value k of a target column, computing a probability of a column n having value i given that the target column has a value k; and
      
      selecting predictor attributes based on the computed probability.
  - 26. The system of claim 15, wherein the step of determining a predictive quality of the predictor attribute comprises the step of:
    - selecting predictor attributes using a predictor variance algorithm based on estimates of variances of predictor/target combinations and variance with respect to other predictors.
  - 27. The system of claim 26, wherein the step of determining a predictive quality of the predictor attribute further comprises the step of:
    - selecting predictor attributes based on selection criteria using a combination of search and evaluation measures of the predictor attributes.
  - 28. The system of claim 26, wherein the step of determining a predictive quality of the predictor attribute comprises the step of:
    - determining a predictor variance PV according to;
      
      $PV (P_{a}) = \sum_{i, k = 1}^{m, n} {((\frac{P_{i} T_{k}}{T_{k}} - \frac{1}{mn} \sum_{j, q = 1}^{m, n} \frac{P_{j} T_{q}}{T_{q}}))}^{2} / n \sum_{i = 1}^{m} {(P_{i} - \frac{1}{m} \sum_{j = 1}^{m} P_{j})}^{2},$ wherein P is the predictor and T is the target, P has values 1 . . . m, and T has values 1 . . . n.
  - 29. The system of claim 26, wherein the step of determining a predictive quality of the predictor attribute comprises the steps of:
    - determining a variance Q of all predictors ignoring a predictor Pa according to;
      
      $Q_{a} = \frac{1}{m - 1} (\sum_{i = 1 | i!= a}^{m - 1} {(P_{i} - \frac{1}{m - 1} \sum_{j = 1}^{m - 1} P_{j})}^{2}); and$ determining a predictor variance PV according to;
      
      $PV (P_{a}) = \sum_{i, k = 1}^{m, n} {(\frac{P_{i} T_{k}}{T_{k}} - \frac{1}{{mnQ}_{a}} \sum_{j, q = 1}^{m, n} \frac{P_{j} T_{q}}{T_{q}})}^{2} / n \sum_{i = 1}^{m} {(P_{i} - \frac{1}{m} \sum_{j = 1}^{m} P_{j})}^{2},$ wherein P is the predictor and T is the target, P has values 1 . . . m, and T has values 1 . . . n.

30. A computer program product for selecting predictive attributes for a data mining model, comprising:
- a computer readable medium;
  
  computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of receiving a dataset having a plurality of predictor attributes;
  
  for each predictor attribute, determining a predictive quality of the predictor attribute based on a predictor variance of the predictor attribute;
  
  selecting at least one predictor attribute based on the determined predictive quality of the predictor attribute; and
  
  building a data mining model including only the selected at least one predictor attribute.
- View Dependent Claims (31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44)
- - 31. The computer program product of claim 30, wherein the step of determining a predictive quality of the predictor attribute comprises the steps of:
    - determining a predictive quality of the predictor attribute using an attribute importance algorithm.
  - 32. The computer program product of claim 31, wherein the attribute importance algorithm comprises:
    - a predictor variance algorithm operable to select predictor attributes based on estimates of variances of predictor/target combinations and variance with respect to other predictors; and
      
      a selection criteria algorithm operable to select predictor attributes based on a combination of search and evaluation measures of the predictor attributes.
  - 33. The computer program product of claim 31, wherein the attribute importance algorithm comprises the step of:
    - selecting predictor attributes based on selection criteria using a combination of search and evaluation measures of the predictor attributes.
  - 34. The computer program product of claim 31, wherein the attribute importance algorithm comprises the steps of:
    - ranking the predictor attributes according to evaluation criteria; and
      
      selecting a minimum set of predictor attributes that satisfies the evaluation criteria.
  - 35. The computer program product of claim 34, wherein the step of ranking the predictor attributes according to evaluation criteria comprises the steps of:
    - associating each predictor attribute with a rank based on the evaluation criteria; and
      
      forming a result set comprising the predictor attribute, a value of the predictor attribute, and the rank of the predictor attribute.
  - 36. The computer program product of claim 35, wherein the step of selecting a minimum set of predictor attributes that satisfies the evaluation criteria comprises the step of:
    - selecting a minimum set of predictor attributes that satisfies the evaluation criteria using the result set.
  - 37. The computer program product of claim 36, wherein the step of associating each predictor attribute with a rank based on the evaluation criteria comprises the step of:
    - ranking each predictor attribute according to at least one of accuracy, consistency, information, distance, dependence, relevance, and importance of the attribute compared to other attributes.
  - 38. The computer program product of claim 36, wherein the step of associating each predictor attribute with a rank based on the evaluation criteria comprises the step of:
    - ranking each predictor attribute using at least one of Information Gain, Distance Measure, and Dependence Measure.
  - 39. The computer program product of claim 31, wherein the attribute importance algorithm comprises the step of:
    - selecting predictor attributes based on estimates of variances of predictor/target combinations and variance with respect to other predictors.
  - 40. The computer program product of claim 31, wherein the attribute importance algorithm comprises the steps of:
    - for each predictor attribute column n, for each possible value i, and for each possible value k of a target column, computing a probability of a column n having value i given that the target column has a value k; and
      
      selecting predictor attributes based on the computed probability.
  - 41. The computer program product of claim 30, wherein the step of determining a predictive quality of the predictor attribute comprises the step of:
    - selecting predictor attributes using a predictor variance algorithm based on estimates of variances of predictor/target combinations and variance with respect to other predictors.
  - 42. The computer program product of claim 41, wherein the step of determining a predictive quality of the predictor attribute further comprises the step of:
    - selecting predictor attributes based on selection criteria using a combination of search and evaluation measures of the predictor attributes.
  - 43. The computer program product of claim 41, wherein the step of determining a predictive quality of the predictor attribute comprises the step of:
    - determining a predictor variance PV according to;
      
      $PV (P_{a}) = \sum_{i, k = 1}^{m, n} {((\frac{P_{i} T_{k}}{T_{k}} - \frac{1}{mn} \sum_{j, q = 1}^{m, n} \frac{P_{j} T_{q}}{T_{q}}))}^{2} / n \sum_{i = 1}^{m} {(P_{i} - \frac{1}{m} \sum_{j = 1}^{m} P_{j})}^{2},$ wherein P is the predictor and T is the target, P has values 1 . . . m, and T has values 1 . . . n.
  - 44. The computer program product of claim 41, wherein the step of determining a predictive quality of the predictor attribute comprises the steps of:
    - determining a variance Q of all predictors ignoring a predictor P_aaccording to;
      
      $Q_{a} = \frac{1}{m - 1} (\sum_{i = 1 | i!= a}^{m - 1} {(P_{i} - \frac{1}{m - 1} \sum_{j = 1}^{m - 1} P_{j})}^{2}); and$ determining a predictor variance PV according to;
      
      $PV (P_{a}) = \sum_{i, k = 1}^{m, n} {(\frac{P_{i} T_{k}}{T_{k}} - \frac{1}{{mnQ}_{a}} \sum_{j, q = 1}^{m, n} \frac{P_{j} T_{q}}{T_{q}})}^{2} / n \sum_{i = 1}^{m} {(P_{i} - \frac{1}{m} \sum_{j = 1}^{m} P_{j})}^{2},$ wherein P is the predictor and T is the target, P has values 1 . . . m, and T has values 1 . . . n.

45. A method of determining a predictive quality of a predictor attribute for a data mining model comprising the steps of:
- receiving a dataset having a plurality of predictor attributes, wherein the predictor attributes are conditionally independent;
  
  for each predictor attribute, determining a predictive quality of the predictor attribute by determining a predictor variance PV according to;
  
  $PV (P_{a}) = \sum_{i, k = 1}^{m, n} {((\frac{P_{i} T_{k}}{T_{k}} - \frac{1}{mn} \sum_{j, q = 1}^{m, n} \frac{P_{j} T_{q}}{T_{q}}))}^{2} / n \sum_{i = 1}^{m} {(P_{i} - \frac{1}{m} \sum_{j = 1}^{m} P_{j})}^{2},$ wherein P is the predictor and T is the target, P has values 1 . . . m, and T has values 1 . . . n.

46. A method of determining a predictive quality of a predictor attribute for a data mining model comprising the steps of:
- receiving a dataset having a plurality of predictor attributes, wherein the predictor attributes have at least some inter-correlations;
  
  for each predictor attribute, determining a predictive quality of the predictor attribute by determining a variance Q of all predictors ignoring a predictor P_aaccording to;
  
  $Q_{a} = \frac{1}{m - 1} (\sum_{i = 1 | i!= a}^{m - 1} {(P_{i} - \frac{1}{m - 1} \sum_{j = 1}^{m - 1} P_{j})}^{2}); and$ determining a predictor variance PV according to;
  
  $PV (P_{a}) = \sum_{i, k = 1}^{m, n} {(\frac{P_{i} T_{k}}{T_{k}} - \frac{1}{{mnQ}_{a}} \sum_{j, q = 1}^{m, n} \frac{P_{j} T_{q}}{T_{q}})}^{2} / n \sum_{i = 1}^{m} {(P_{i} - \frac{1}{m} \sum_{j = 1}^{m} P_{j})}^{2},$ wherein P is the predictor and T is the target, P has values 1 . . . m, and T has values 1 . . . n.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
Oracle International Corporation (Oracle Corporation)
Original Assignee
Oracle International Corporation (Oracle Corporation)
Inventors
Kuntala, Pavani, Drescher, Gary L.

Granted Patent

US 7,219,099 B2
Time in Patent Office

Days
Field of Search
US Class Current

707/100
CPC Class Codes

G06F 16/2465   Query processing support fo...

G06F 16/30   of unstructured textual dat...

G06N 20/00   Machine learning

G06N 7/01   Probabilistic graphical mod...

Y10S 707/99942   Manipulating data structure...

Y10S 707/99945   Object-oriented database st...

Data mining model building using attribute importance

First Claim

1 Assignment

0 Petitions

Accused Products

Abstract

160 Citations

46 Claims

Specification

Solutions

Use Cases

Quick Links

Data mining model building using attribute importance

First Claim

1 Assignment

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

160 Citations

46 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links