Methods and apparatus for automated matching and classification of data

• US 7,657,506 B2
• Filed: 01/03/2007
• Issued: 02/02/2010
• Est. Priority Date: 01/03/2006
• Status: Active Grant

• Current Assignee: Microsoft Corporation
• Original Assignee: Microsoft International Holdings BV (Microsoft Corporation)
• Inventors: Levin, Boris I.
• Primary Examiner(s): Le; Uyen T.
• Application Number:
  US11/649,546
• Publication Number:
  US 20070282827A1
• Time in Patent Office: 1,126 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A computer-implemented method for processing data includes receiving an initial set of records including terms describing respective items in specified categories. Based on the initial set of records, respective term weights are calculated for at least some of the terms with respect to at least some of the categories. Each term weight indicates, for a given term and a given category, a likelihood that a record containing the given term belongs to the given category. Upon receiving a new record, not included in the initial set, respective assignment metrics are computed for two or more of the categories using the respective term weights of the particular terms in the new record with respect to the two or more of the categories. The new record is classified in one of the two or more of the categories responsively to the assignment metrics.

Claims

1. A computer-implemented method for processing data, comprising:

receiving an initial set of records comprising initial terms describing respective items in specified categories;

calculating, based on the initial set of records, respective term weights for at least some of the initial terms with respect to at least some of the categories, each term weight indicating, for a given initial term and a given category, a likelihood that a record containing the given initial term belongs to the given category, wherein calculating term weights comprises computing a general probability of occurrence of the given initial term over all of the categories, computing a specific probability of the occurrence of the given initial term in the records belonging to the given category, and determining the term weight responsively to a difference between the specific probability and the general probability for the given initial term with respect to the given category;

receiving a new record, not included in the initial set, the new record comprising particular terms, wherein the particular terms are a subset of the initial terms;

computing respective assignment metrics for two or more of the categories using the respective term weights of the particular terms in the new record with respect to the two or more of the categories; and

classifying the new record in one of the two or more of the categories responsively to the assignment metrics.

2. The method according to claim 1, wherein determining the term weight comprises setting the term weight for the given initial term with respect to the given category to zero unless the specific probability is higher than the general probability.

3. The method according to claim 2, wherein setting the term weight comprises determining, responsively to the general probability, a minimal number of occurrences of the given initial term within the given category, and setting the term weight to a non-zero value only if the given initial term occurs in at least the minimal number of the records in the given category.

4. The method according to claim 1, wherein computing the respective assignment metrics comprises building a contingency table containing the term weights indexed by the terms and by the categories, and selecting the categories and term weights to use in computing the respective assignment metrics from the contingency table.

5. The method according to claim 1, wherein computing the respective assignment metrics comprises calculating, for each of the two or more of the categories, a respective sum of the respective term weights of the particular terms in the new record, and wherein classifying the new record comprises assigning the new record to the one of the two or more of the categories having the greatest respective sum.

6. The method according to claim 5, wherein the records comprise multiple fields, and wherein calculating the respective sum comprises computing a weighted sum of the respective term weights over the multiple fields.

7. Apparatus for processing data, comprising:

a memory, which is arranged to hold an initial set of records comprising initial terms describing respective items in specified categories; and

a processor, which is arranged to;

calculate, based on the initial set of records, respective term weights for at least some of the initial terms with respect to at least some of the categories, each term weight indicating, for a given initial term and a given category, a likelihood that a record containing the given initial term belongs to the given category, wherein calculating term weights comprises computing a general probability of occurrence of the given initial term over all of the categories, computing a specific probability of the occurrence of the given initial term in the records belonging to the given category, and determining the term weight responsively to a difference between the specific probability and the general probability for the given initial term with respect to the given category;

receive a new record, not included in the initial set, the new record comprising particular terms, wherein the particular terms are a subset of the initial terms;

compute respective assignment metrics for two or more of the categories using the respective term weights of the particular terms in the new record with respect to the two or more of the categories; and

classify the new record in one of the two or more of the categories responsively to the assignment metrics.

8. The apparatus according to claim 7, wherein the processor is arranged to set the term weight for the given term with respect to the given category to zero unless the specific probability is higher than the general probability.

9. The apparatus according to claim 8, wherein the processor is arranged to determine, responsively to the general probability, a minimal number of occurrences of the given initial term within the given category, and to set the term weight to a non-zero value only if the given initial term occurs in at least the minimal number of the records in the given category.

10. The apparatus according to claim 7, wherein the processor is arranged to build a contingency table containing the term weights indexed by the terms and by the categories, and to select the categories and term weights to use in computing the respective assignment metrics from the contingency table.

11. The apparatus according to claim 7, wherein the processor is arranged to calculate, for each of the two or more of the categories, a respective sum of the respective term weights of the particular terms in the new record, and to assign the new record to the one of the two or more of the categories having the greatest respective sum.

12. A computer software product, comprising a computer-readable medium in which program instructions are stored, which instructions, when read by the computer, cause the computer to:

receive an initial set of records comprising initial terms describing respective items in specified categories, and to calculate, based on the initial set of records, respective term weights for at least some of the initial terms with respect to at least some of the categories, each term weight indicating, for a given initial term and a given category, a likelihood that a record containing the given initial term belongs to the given category, wherein calculating the term weight for the given initial term comprises computing a general probability of occurrence of the given initial term over all of the categories, computing, a specific probability of the occurrence of the given initial term in the records belonging to the given category, and determining the term weight responsively to a difference between the specific probability and the general probability for the given initial term with respect to the given category;

receive a new record, not included in the initial set, the new record comprising particular terms, wherein the particular terms are a subset of the initial terms;

compute respective assignment metrics for two or more of the categories using the respective term weights of the particular terms in the new record with respect to the two or more of the categories; and

classify the new record in one of the two or more of the categories responsively to the assignment metrics.

13. The product according to claim 12, wherein the instructions cause the computer to set the term weight for the given initial term with respect to the given category to zero unless the specific is higher than the general probability.

14. The product according to claim 13, wherein the instructions cause the computer to determine, responsively to the general probability, a minimal number of occurrences of the given initial term within the given category, and to set the term weight to a non-zero value only if the given initial term occurs in at least the minimal number of the records in the given category.

15. The product according to claim 12, wherein the instructions cause the computer to build a contingency table containing the term weights indexed by the terms and by the categories, and to select the categories and term weights to use in computing the respective assignment metrics from the contingency table.

16. The product according to claim 12, wherein the instructions cause the computer to calculate, for each of the two or more of the categories, a respective sum of the respective term weights of the particular terms in the new record, and to assign the new record to the one of the two or more of the categories having the greatest respective sum.

17. The product according to claim 16, wherein the records comprise multiple fields, and wherein the instructions cause the computer to compute a weighted sum of the respective term weights over the multiple fields.