Data classification tool using dynamic allocation of attribute weights

• US 20100332434A1
• Filed: 06/30/2009
• Published: 12/30/2010
• Est. Priority Date: 06/30/2009
• Status: Active Grant

• Current Assignee: Global E Procure Incorporated
• Original Assignee: Global E Procure Incorporated
• Inventors: Pawar, Sachin Sharad, Joshi, Girish
• Granted Patent: US 8,234,230 B2
• Time in Patent Office: Days
• US Class Current: 706/45
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06Q 30/08 Auctions

Abstract

An analysis tool for causing a computer to use information gain of attributes and a classification algorithm to classify new records in a set of data by taking into account the predictive value of the attributes and the effect of the new record.

Claims

1. A computer readable medium comprising instructions to cause a processor to transform attribute values and attribute descriptors to dynamic weights for classifying a new record comprising:

a) determine a static weight for each of a plurality of attributes in a data set wherein said data set includes a plurality of records, each record comprises one of a plurality of descriptors for each of said plurality of attributes;

b) determine an interval of variation about each said static weight;

c) classify a new record comprising assigning a dynamic weight to each said descriptor included in said new record for each of said plurality of attributes and using said dynamic weights for each of said attributes to classify said new record.

2. The computer readable medium of claim 1 wherein said static weight for each of said plurality of attributes is determined by calculating overall entropy in the dataset, calculating conditional entropy for each descriptor of said attribute, finding a conditional entropy for said attribute by computing a weighted average of conditional entropy for each descriptor of said attribute, determining information gain of said attribute using the conditional entropy for the attribute and the overall entropy in the data set and normalizing the information gains determined for each of said plurality of attributes to sum to the number of attributes in said plurality of attributes.

3. The computer readable medium of claim 1 wherein said interval of variation for each of said plurality of attributes is determined by finding a conditional entropy for each of the plurality of descriptors for said attribute, inverting each conditional entropy to an attribute value importance score to from a group of attribute value importance scores, dividing the group of attribute value importance scores into quartiles, calculating a lower bound scaling factor for the interval of variation as

LBSF_i=(Q2−

Q1)/Q2

And an upper bound scaling factor for the interval of variation as

UBSF_i=(Q3−

Q2)/Q2

And a lower bound as

LB_i=W_i−

W_i*LBSF_i.

And an upper bound as

UB_i=W_i+W_i*UBSF_i.

4. The computer readable medium of claim 1 wherein said dynamic weight of an attribute in the new record is assigned by calculating conditional entropy of the descriptor of that attribute, inverting said conditional entropy to an attribute value importance score, and, transforming said attribute value importance score according to

5. The computer readable medium of claim 2 wherein said interval of variation for each of said plurality of attributes is determined by finding a conditional entropy for each of the plurality of descriptors for said attribute, in the data set, inverting each conditional entropy to an attribute value importance score to form a group of attribute value importance scores, dividing the group of attribute value importance scores into quartiles, calculating a lower bound scaling factor for the interval of variation as

LBSF_i=(Q2−

Q1)/Q2

And an upper bound scaling factor for the interval of variation as

UBSF_i=(Q3−

Q2)/Q2

And a lower bound as

LB_i=W_i−

W_i*LBSF_i.

And an upper bound as

UB_i=W_i+W_i*UBSF_i.

and said dynamic weight for each attribute in the new record is assigned by calculating conditional entropy in the data set for the descriptor of each said attribute in the new record and inverting each said conditional entropy to create an attribute value importance score for each attribute in the new record, transforming each said attribute value importance score according to

6. A computer readable medium comprising instructions to cause a processor to classify a new record relative to a set of data having a plurality of attributes wherein at least one of said plurality of attributes is described by at least one of a plurality of descriptors and classifying said record comprises causing the processor to determine a static weight for each of the plurality of attributes in said set of data, determine an interval of variation for each of said plurality of attributes caused by the distribution of the plurality of descriptors around said attribute in said set of data, determine a dynamic weight of each of said plurality of attributes in the record, and employ each said dynamic weight to classify said new record.

7. The computer readable medium of claim 6 wherein said static weight for each of the plurality of attributes comprises causing the processor to:

a) calculate overall entropy of said set of data;

b) calculate an information gain value for each one of said plurality of attributes using a conditional entropy value for each attribute and the overall entropy to create a set of information gain values; and

c) normalize said set of information gain values to sum up to the number of attributes in the plurality of attributes in said set of data.

8. The computer readable medium of claim 7 wherein said conditional entropy value for each attribute comprises causing the processor to:

a) calculate a conditional entropy value for each one of said plurality of descriptors for each one of said plurality of attributes to create a set of conditional entropy values for each of said plurality of attributes;

b) calculate a weighted average of each set of conditional entropy values.

9. The computer readable medium of claim 6 wherein said interval of variation for each of said plurality of attributes in said set of data comprises causing the processor to:

a) calculate a conditional entropy value for each descriptor of each of the plurality of attributes to create a set of conditional entropy values;

b) invert each of said set of conditional entropy values to create a set of attribute value importance scores;

c) divide said set of attribute value importance scores into four quartiles and determine an upper bound and a lower bound for each of said plurality of attributes in said set of data.

10. The computer readable medium of claim 6 wherein said dynamic weight for an attribute of said new record comprises causing the processor to:

a) calculate a conditional entropy value in the set of data for the descriptor of an attribute in said new record;

b) invert the conditional entropy value to create an attribute value importance score;

c) transform said attribute value importance score using linear transformation in the interval of variation for said attribute; and

d) repeat steps (a) through (c) for each attribute in said new record to create a group of transformed attribute value importance scores.

11. The computer readable medium of claim 6 wherein said dynamic weight for an attribute of said new record further comprises causing the processor to normalize the group of transformed attribute value importance scores to sum up to the number of said attributes in said plurality of attributes.

12. The computer readable medium of claim 6 wherein said instructions cause the processor to use the dynamic weight of each of said attributes in the new record to calculate posterior probability for a class.

13. The computer readable medium of claim 6 wherein said instructions cause the processor to:

a) calculate a conditional entropy value for each one of said plurality of descriptors for each one of said plurality of attributes to create a set of conditional entropy values for each of said plurality of attributes and calculate a weighted average of each set of conditional entropy values as the conditional entropy for the attribute;

b) calculate overall entropy of said set of data;

c) calculate an information gain value for each one of said plurality of attributes using said conditional entropy value for each attribute and the overall entropy to create a set of information gain values;

d) normalize said set of information gain values to sum up to the number of attributes in the plurality of attributes in said set of data to obtain said static weight for each of said plurality of attributes.

14. The computer readable medium of claim 6 wherein said instructions cause the processor to

a) calculate a conditional entropy value for each descriptor of each of the plurality of attributes in the data set to create a set of conditional entropy values;

b) invert each of said set of conditional entropy values to create a set of attribute value importance scores;

c) divide said set of attribute value importance scores into four quartiles and determine an upper bound and a lower bound for each of said plurality of attributes in said set of data to obtain an interval of variation for each of said plurality of attributes in said set of data;

d) determining said dynamic weight for an attribute of said new record comprise, for each descriptor of an attribute in the new records, calculate conditional entropy in the data model;

e) for each descriptor of an attribute in the new record, invert the conditional entropy value obtained in step (d) to create an attribute value importance score,

f) transform each attribute value importance score obtained in step (e) using linear transformation in the interval of variation to form a set of transformed importance values;

g) create a dynamic weight for each said attribute by normalizing the set of transformed importance values to sum up to the number of said attributes in said plurality of attributes;

h) employ each said dynamic weight to classify said new record.

15. The computer readable medium as claimed in claim 14 wherein said processor is instructed to calculate the posterior probability for a class.