Categorization based on record linkage theory

• US 20020156793A1
• Filed: 03/02/2001
• Published: 10/24/2002
• Est. Priority Date: 03/02/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jaro, Matthew A.
• Granted Patent: US 6,938,053 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

The method and apparatus for categorizing an item based on Record Linkage Theory is disclosed. A related method and apparatus for assigning a confidence level to the categorization process is disclosed. In one aspect, the item to be categorized is parsed into at least one token. At least one category that contains the token in the training set is identified. A weight is calculated for each token with respect to a first category. Weights are combined to determine the total weight of the first category. The weighting process is repeated for each relevant category. Where one of a plurality of threshold values is met or exceeded, the item may be automatically assigned to the category with the highest total weight. The combination of threshold values may be selected based on the confidence level associated with that combination of threshold values. Weights for each relevant category, possibly ordered, may be presented.

Claims

1. A method for categorizing an item based on a training set of categorized items, the method comprising the steps of:

(a) parsing an item into at least one token;

(b) identifying, from a plurality of categories, at least one category that contains at least one occurrence of at least one token from the item;

(c) calculating an agreement weight based on Record Linkage Theory for each of the at least one token from the item that occurs in a first category of the at least one category;

(d) combining the agreement weights to determine a total weight for the first category; and

(e) repeating steps (c) and (d) for each category that contains at least one occurrence of at least one token from the item.

2. The method of claim 1 wherein step (b) comprises looking up the at least one token on an index.

3. The method of claim 1 further comprising, prior to step (c), reading into memory a token vector that lists a frequency of occurrence of a token in each category that contains at least one occurrence of the token.

4. The method of claim 3 further comprising updating the token vector when the item is assigned to a category.

5. The method of claim 1 wherein the agreement weight based on Record Linkage Theory is a probability that the at least one token can correctly classify the first category divided by a probability that the at least one token can correctly classify the plurality of categories excluding the first category.

6. The method of claim 1 wherein step (c) comprises calculating an agreement weight based on Record Linkage Theory for each of the at least one token from the item and each token pair from the item that occurs in a first category of the at least one category.

7. The method of claim 1 further comprising, prior to step (d), calculating a disagreement weight based on Record Linkage Theory for each of the at least one token from the item that does not occur in the first category of the at least one category;

and wherein step (e) comprises combining the agreement weights and the disagreement weights to determine a total weight for the first category.

8. The method of claim 7 wherein the disagreement weight based on Record Linkage Theory is one minus a probability that the at least one token can correctly classify the first category divided by one minus a probability that the at least one token can correctly classify the plurality of categories excluding the first category.

9. The method of claim 8 further comprising, prior to step (c), reading into memory a token vector that lists a frequency of occurrence of a token in each category that contains at least one occurrence of the token;

wherein step (c) comprises calculating an agreement weight based on Record Linkage Theory for each of the at least one token from the item and each token pair from the item that occurs in a first category of the at least one category,

wherein the agreement weight based on Record Linkage Theory is a probability that the at least one token can correctly classify the first category divided by a probability that the at least one token can correctly classify the plurality of categories excluding the first category;

further comprising, prior to step (d), calculating a disagreement weight based on Record Linkage Theory for each of the at least one token from the item and each token pair from the item that does not occur in the first category of the at least one category;

wherein step (e) comprises combining the agreement weights and the disagreement weights to determine a total weight for the first category;

further comprising

ordering by total weight each category that contains at least one occurrence of at least one token from the item;

listing, in descending order by total weight, each category that contains at least one occurrence of at least one token and the log base 2 of its total weight; and

if a threshold value is met or exceeded, assigning the item to the category with the highest total weight;

or

if no threshold value is met or exceeded, presenting an item for further analysis.

10. The method of claim 7 further comprising, prior to step (d), calculating a disagreement weight based on Record Linkage Theory for each of the at least one token from the item and each token pair from the item that does not occur in the first category of the at least one category.

11. The method of claim 1 further comprising ordering by total weight each category that contains at least one occurrence of at least one token from the item.

12. The method of claim 11 further comprising listing, in descending order by total weight, each category that contains at least one occurrence of at least one token and the log base 2 of its total weight.

13. The method of claim 1 further comprising assigning the item to the category with the highest total weight if a threshold value is met or exceeded.

14. The method of claim 1 further comprising presenting an item for further analysis when no threshold value is met or exceeded.

16. The method of claim 15 wherein the agreement weight based on Record Linkage Theory is a probability that the at least one token can correctly classify the first category divided by a probability that the at least one token can correctly classify the plurality of categories excluding the first category.

17. The method of claim 15 wherein step (c) comprises calculating an agreement weight based on Record Linkage Theory for each of the at least one token from the item and each token pair from the item that occurs in a first category of the at least one category.

18. The method of claim 15 further comprising, prior to step (d), calculating a disagreement weight based on Record Linkage Theory for each of the at least one token from the item that does not occur in the first category of the at least one category;

and wherein step (e) comprises a step for combining the agreement weights and the disagreement weights to determine a total weight for the first category.

19. The method of claim 18 wherein the disagreement weight based on Record Linkage Theory is one minus a probability that the at least one token can correctly classify the first category divided by one minus a probability that the at least one token can correctly classify the plurality of categories excluding the first category.

20. The method of claim 19 wherein step (c) comprises calculating an agreement weight based on Record Linkage Theory for each of the at least one token from the item and each token pair from the item that occurs in a first category of the at least one category,

wherein the agreement weight based on Record Linkage Theory is a probability that the at least one token can correctly classify the first category divided by a probability that the at least one token can correctly classify the plurality of categories excluding the first category;

further comprising, prior to step (d), calculating a disagreement weight based on Record Linkage Theory for each of the at least one token from the item and each token pair from the item that does not occur in the first category of the at least one category;

wherein step (e) comprises a step for combining the agreement weights and the disagreement weights to determine a total weight for the first category;

further comprising

ordering by total weight each category that contains at least one occurrence of at least one token from the item;

listing, in descending order by total weight, each category that contains at least one occurrence of at least one token and the log base 2 of its total weight; and

if a threshold value is met or exceeded, assigning the item to the category with the highest total weight;

or

if no threshold value is met or exceeded, presenting an item for further analysis.

21. The method of claim 19 further comprising, prior to step (d), calculating a disagreement weight based on Record Linkage Theory for each of the at least one token from the item and each token pair from the item that does not occur in the first category of the at least one category.

22. The method of claim 15 further comprising listing, in descending order by total weight, each category that contains at least one occurrence of at least one token and the log base 2 of its total weight.

23. The method of claim 15 further comprising assigning the item to the category with the highest total weight if a threshold value is met or exceeded.

25. The method of claim 24 wherein one of the plurality of threshold values comprises a threshold value for a weight for the highest weight category.

26. The method of claim 24 wherein one of the plurality of threshold values comprises a threshold value for a difference between the highest weight category and the second highest weight category.

27. The method of claim 24 wherein one of the plurality of threshold values comprises a threshold value for a number of tokens and token pairs from the item found in an index.

28. The method of claim 25 wherein the plurality of threshold values further comprises a difference between the highest weight category and the second highest weight category and a threshold value for a number of tokens and token pairs from the item found in an index.

30. The apparatus of claim 29 further comprising a memory element, wherein the occurrence identifier reads into the memory element a token vector that lists a frequency of occurrence of a token in each category that contains at least one occurrence of the token.

31. The apparatus of claim 30 further comprising a vector reviser, the vector reviser updating the token vector after the item is assigned to a category.

32. The apparatus of claim 29 wherein the agreement weight is a probability that the at least one token can correctly classify the first category divided by a probability that the at least one token can correctly classify the plurality of categories excluding the first category.

33. The apparatus of claim 29 wherein the calculator calculates the agreement weight for each of the at least one token from the item and each token pair from the item that occurs in a first category of the at least one category.

34. The apparatus of claim 29 wherein the calculator also calculates a disagreement weight based on Record Linkage Theory for each of the at least one token from the item that does not occur in the first category of the at least one category;

and wherein the summer sums the agreement weights and the disagreement weights to determine a total weight for the first category.

35. The apparatus of claim 34 wherein the disagreement weight is one minus a probability that the at least one token can correctly classify the first category divided by one minus a probability that the at least one token can correctly classify the plurality of categories excluding the first category.

36. The apparatus of claim 34 wherein the calculator also calculates a disagreement weight for each of the at least one token from the item and each token pair from the item that does not occur in the first category of the at least one category.

37. The apparatus of claim 29 further comprising a first comparator in signal communication with the summer, the first comparator ordering by total weight each category that contains at least one occurrence of at least one token from the item.

38. The apparatus of claim 37 further an output device in signal communication with the first comparator, the output device listing, in descending order by total weight, each category that contains at least one occurrence of at least one token and the log base 2 of its total weight.

39. The apparatus of claim 29 further comprising a comparator in signal communication with the summer, the comparator assigning the item to the category with the highest total weight if a threshold value is met or exceeded.

40. The apparatus of claim 39 wherein the comparator presents the item for further analysis if no threshold value is not met or exceeded.

15. A method for categorizing an item based on a training set of categorized items, the method comprising the steps of:

(a) parsing an item into at least one token;

(b) a step for identifying, from a plurality of categories, at least one category that contains at least one occurrence of the at least one token;

(c) calculating an agreement weight based on Record Linkage Theory for each of the at least one token from the item that occurs in a first category of the at least one category;

(d) a step for combining the agreement weights to determine a total weight for the first category; and

(e) repeating steps (c) and (d) for each category that contains at least one occurrence of at least one token from the item.

24. A method for selecting threshold values for automatically categorizing an item with a training set of categorized items, the method comprising the steps of:

(a) calculating a weight for at least one category for each item in a training set;

(b) selecting a combination of a plurality of threshold values for a plurality of variables;

(c) deeming an item in the training set assigned to the highest weight category for purposes of determining whether the item is correctly categorized when one of the threshold values in the combination of threshold values is met or exceeded by the item;

(d) repeating steps (b) through (c) for each combination of threshold values;

(e) calculating a confidence level for the combination of threshold values, the confidence level being a number of correctly categorized items in the training set less a number of incorrectly categorized items in the training set; and

(f) choosing the combination of threshold values that results in the highest confidence level.

29. An apparatus for categorizing an item based on a training set of categorized items, the apparatus comprising:

an input device;

a parser in signal communication with the input device, said parser parsing an item from the input device into at least one token;

an occurrence identifier in signal communication with the parser, the occurrence identifier identifying, from a plurality of categories, at least one category that contains at least one occurrence of the at least one token;

a calculator in signal communication with the occurrence identifier, the calculator calculating an agreement weight based on Record Linkage Theory for each of the at least one token from the item that occurs in a first category of the at least one category;

a summer in signal communication with the calculator, the summer summing the agreement weights to determine a total weight for the first category; and

a looping mechanism in signal communication with the occurrence identifier and the summer, the looping mechanism initializing the calculator for each category that contains at least one occurrence of at least one token from the item.

41. An apparatus for categorizing an item based on a training set of categorized items, the apparatus comprising:

an input device;

a parser in signal communication with the input device, said parser parsing an item from the input device into at least one token;

a means for identifying at least one category that contains at least one occurrence of the at least one token, from a plurality of categories, the means for identifying at least one category in signal communication with the parser;

a means for calculating a weight based on Record Linkage Theory for each of the at least one token from the item that occurs in a first category of the at least one category, the means for calculating a weight in signal communication with the occurrence identifier;

a means for combining weights to determine a total weight for the first category, the means for combining weights in signal communication with the calculator; and

a looping mechanism in signal communication with the means for identifying at least one category and the means for calculating a weight, the looping mechanism initializing the means for calculating a weight for each category that contains at least one occurrence of at least one token from the item.

42. The apparatus of claim 41 wherein the means for calculating a weight calculates an agreement weight that is a probability that the at least one token can correctly classify the first category divided by a probability that the at least one token can correctly classify the plurality of categories excluding the first category.

43. The apparatus of claim 42 wherein the means for calculating a weight calculates the agreement weight for each of the at least one token from the item and each token pair from the item that occurs in a first category of the at least one category.

44. The apparatus of claim 42 wherein the means for calculating a weight also calculates a disagreement weight based on Record Linkage Theory for each of the at least one token from the item that does not occur in the first category of the at least one category;

and wherein the a means for combining weights combines the agreement weights and the disagreement weights to determine a total weight for the first category.

45. The apparatus of claim 44 wherein the disagreement weight is one minus a probability that the at least one token can correctly classify the first category divided by one minus a probability that the at least one token can correctly classify the plurality of categories excluding the first category.

46. The apparatus of claim 45 wherein the means for calculating a weight also calculates the agreement weight for each of the at least one token from the item and each token pair from the item that occurs in a first category of the at least one category;

and the disagreement weight for each of the at least one token from the item and each token pair from the item that does not occur in the first category of the at least one category.

47. The apparatus of claim 41 further comprising a means for ordering categories ordering by total weight each category that contains at least one occurrence of at least one token from the item, the means for ordering categories in signal communication with the means for combining weights.

48. The apparatus of claim 41 further comprising a means for assigning the item to the category with the highest total weight if a threshold value is met or exceeded, the means for assigning in signal communication with the means for combining.

50. The apparatus of claim 49 wherein one of the plurality of threshold values comprises a threshold value for a weight for the highest weight category.

51. The apparatus of claim 49 wherein one of the plurality of threshold values comprises a threshold value for a difference between the highest weight category and the second highest weight category.

52. The apparatus of claim 49 wherein one of the plurality of threshold values comprises a threshold value for a number of tokens and token pairs from the item found in an index.

53. The apparatus of claim 50 wherein the plurality of threshold values further comprises a difference between the highest weight category and the second highest weight category and a threshold value for a number of tokens and token pairs from the item found in an index.

49. An apparatus for selecting threshold values for automatically categorizing an item with a training set of categorized items, the apparatus comprising:

a memory element, the memory element containing a plurality of items in a training set;

a categorizer in signal communication with the memory element, the categorizer calculating a weight for at least one category for each of the plurality of items in the training set;

a selector in signal communication with the categorizer, the selector selecting a combination of a plurality of threshold values for a plurality of variables;

a first comparator in signal communication with the selector, the first comparator deeming an item in the training set assigned to the highest weight category for purposes of determining whether the item is correctly categorized when one or more of the threshold values in the combination of threshold values is met or exceeded by the item;

a looping mechanism in signal communication with the selector and the first comparator, the looping mechanism initializing the first comparator for each combination of threshold values; and

a calculator in signal communication with the looping mechanism, the calculator calculating a confidence level for the combination of threshold values, the confidence level being a number of correctly categorized items in the training set less a number of incorrectly categorized items in the training set;

a second comparator in signal communication with the calculator, the second comparator identifying the combination of threshold values that results in the highest confidence level.