Detection of patterns in data records

• US 7,814,111 B2
• Filed: 01/03/2007
• Issued: 10/12/2010
• Est. Priority Date: 01/03/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft International Holdings BV (Microsoft Corporation)
• Original Assignee: Microsoft International Holdings BV (Microsoft Corporation)
• Inventors: Levin, Boris I.
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): GIRMA, ANTENEH B
• Application Number:
  US11/649,540
• Publication Number:
  US 20070156749A1
• Time in Patent Office: 1,378 Days
• Field of Search: None
• US Class Current: 707/756
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

A computer-implemented method for processing data includes receiving an input from a user including positive examples and negative examples of a specified data type. The positive examples include first character strings that belong to the specified data type, and the negative examples include second character strings that do not belong to the specified data type. The first and second character strings are processed to create a set of attributes that characterize the positive examples. A decision tree is built, based on the attributes, which when applied to the first and second strings, distinguishes the positive examples from the negative examples. The decision tree is applied to the data so as to identify occurrences of the specified data type.

Claims

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

receiving an input from a user comprising positive examples and negative examples of a specified data type, the positive examples comprising first character strings that belong to the specified data type, and the negative examples comprising second character strings that do not belong to the specified data type, wherein receiving the input comprises displaying a collection of the character strings, and accepting from the user an indication of which of the character strings to include in the specified data type and which of the character strings to exclude from the specified data type;

processing the first and second character strings to create a set of attributes that characterize the positive examples, wherein the processing comprises;

assigning a different character code from character codes to each character type of characters forming the first and second character strings; and

encoding the first and second character strings as sequences of the character codes without distinguishing between sequential characters of the same type, wherein one character code is assigned to letters and another character code is assigned to digits;

building a decision tree, based on the attributes, which when applied to the first and second strings, distinguishes the positive examples from the negative examples; and

applying the decision tree to the data so as to classify a character string of the character strings as belonging to the specified data type.

2. The method according to claim 1, wherein each of the character strings comprises one or more character sequences, each character sequence having a length and comprising characters of a single, given character type, and wherein processing the first and second character strings comprises encoding each character string to indicate character types and lengths of the character sequences in the character string.

3. The method according to claim 2, wherein the sequences of the character codes comprise ordered groups of two or more of the character codes that comprise different, respective character types.

4. The method according to claim 1, wherein processing the first and second character strings comprises choosing the attributes such that at least a predetermined fraction of the positive examples is characterized by the chosen attributes, and such that a larger fraction of the positive examples than of the negative examples is characterized by the chosen attributes.

5. The method according to claim 1, wherein building the decision tree comprises choosing splitting conditions for application at the nodes of the decision tree so that the decision tree is an optimal decision tree.

6. The method according to claim 5, wherein the decision tree comprises a root node, internal nodes, and leaf nodes, and wherein choosing the splitting conditions comprises finding a respective optimal splitting condition at the root node and at each of the internal nodes.

7. The method according to claim 6, wherein finding the respective optimal splitting condition comprises, at each node among the root and internal nodes, choosing one of the attributes and the optimal splitting condition for application to the one of the attributes so as to maximize an optimization criterion for separating the positive examples contained in the node from the negative examples contained in the node.

8. The method according to claim 6, wherein building the decision tree comprises determining one of the nodes to be a leaf node when the node contains only positive examples or only negative examples.

9. The method according to claim 6, wherein building the decision tree comprises determining one of the nodes to be a leaf node when there is splitting condition that will separate the positive examples contained in the leaf node from the negative examples contained in the leaf node with an effectiveness greater than a predetermined minimum optimization criterion.

10. The method according to claim 1, wherein applying the decision tree comprises receiving further input from the user indicating errors made by the decision tree in classifying the character string as belonging to the specified data type, and refining the decision tree using the further input.

11. The method according to claim 1, wherein applying the decision tree, comprises constructing a regular expression based on the decision tree, and applying the regular expression to the data.

12. The method according to claim 1, wherein applying the decision tree to the data comprises identifying occurrences of the specified data type and using the occurrences to identify duplications in records in a database, and resolving the duplications.

13. Apparatus for processing data comprising character strings, comprising:

a user interface, which is coupled to receive an input from a user comprising positive examples and negative examples of a specified data type, the positive examples comprising first character strings that belong to the specified data type, and the negative examples comprising second character strings that do not belong to the specified data type, wherein the user interface is arranged to display a collection of the character strings, and to accept from the user an indication of which of the character strings to include in the specified data type and which of the character strings to exclude from the specified data type; and

a pattern processor, which is arranged to;

process the first and second character strings to create a set of attributes that characterize the positive examples, wherein the processing comprises;

assigning a different character code from character codes to each character type of characters forming the first and second character strings, and

encoding the first and second character strings as sequences of the character codes without distinguishing between sequential characters of the same type, wherein one character code is assigned to letters and another character code is assigned to digits;

build a decision tree, based on the attributes, which when applied to the first and second strings, distinguishes the positive examples from the negative examples; and

apply the decision tree to the data so as to classify a character string of the character strings as belonging to the specified data type.

14. The apparatus according to claim 13, wherein each of the character strings comprises one or more character sequences, each character sequence having a length and comprising characters of a single, given character type, and wherein the processor is arranged to encode each character string to indicate the character types and lengths of the character sequences in the character string.

15. The apparatus according to claim 14, wherein the sequences of the character codes comprise ordered groups of two or more of the character sequences that comprise different, respective character types.

16. The apparatus according to claim 13, wherein the processor is arranged to choose the attributes such that at least a predetermined fraction of the positive examples is characterized by the chosen attributes, and such that a larger fraction of the positive examples than of the negative examples is characterized by the chosen attributes.

17. The apparatus according to claim 13, wherein the processor is arranged to choose splitting conditions for application at the nodes of the decision tree so that the decision tree is an optimal decision tree.

18. The apparatus according to claim 17, wherein the decision tree comprises a root node, internal nodes, and leaf nodes, and wherein the processor is arranged to find a respective optimal splitting condition at the root node and at each of the internal nodes.

19. The apparatus according to claim 18, wherein the processor is arranged to find the respective optimal splitting condition by choosing, at each node among the root and internal nodes, one of the attributes and the optimal splitting condition for application to the one of the attributes so as to maximize an optimization criterion for separating the positive examples contained in the node from the negative examples contained in the node.

20. The apparatus according to claim 18, wherein the processor is arranged to determine one of the nodes to be a leaf node when the node contains only positive examples or only negative examples.

21. The apparatus according to claim 18, wherein the processor is arranged to determine one of the nodes to be a leaf node when there is splitting condition that will separate the positive examples contained in the leaf node from the negative examples contained in the leaf node with an effectiveness greater than a predetermined minimum optimization criterion.

22. The apparatus according to claim 13, wherein the user interface is coupled to receive further input from the user indicating errors made by the decision tree in classifying the character string as belonging to the specified data type, and wherein the processor is arranged to refine the decision tree using the further input.

23. The apparatus according to claim 13, wherein the processor is arranged to construct a regular expression based on the decision tree, and to apply the regular expression to the data.

24. The apparatus according to claim 13, wherein the processor is arranged to identify occurrences of the specified data type and use the occurrences to identify duplications in records in a database, and to resolve the duplications.

25. A computer software product for processing data comprising character strings, the product comprising a computer-readable storage medium in which program instructions are stored, the program instructions, when executed by a computer, cause the computer to:

receive an input from a user comprising positive examples and negative examples of a specified data type, the positive examples comprising first character strings that belong to the specified data type, and the negative examples comprising second character strings that do not belong to the specified data type, wherein the instructions cause the computer to display a collection of the character strings, and to accept from the user an indication of which of the character strings to include in the specified data type and which of the character strings to exclude from the specified data type;

process the first and second character strings to create a set of attributes that characterize the positive examples, wherein the processing comprises;

assigning a different character code from character codes to each character type of characters forming the first and second character strings, and

encoding the first and second character strings as sequences of the character codes without distinguishing between sequential characters of the same type, wherein one character code is assigned to letters and another character code is assigned to digits;

build a decision tree, based on the attributes, which when applied to the first and second strings, distinguishes the positive examples from the negative examples; and

apply the decision tree to the data so as to classify a character string of the character strings as belonging to the specified data type.

26. The product according to claim 25, wherein each of the character strings comprises one or more character sequences, each character sequence having a length and comprising characters of a single, given character type, and wherein the instructions cause the computer to encode each character string to indicate character types and lengths of the character sequences in the character string.

27. The product according to claim 26, wherein the sequences of the character codes comprise ordered groups of two or more of the character sequences that comprise different, respective character types.

28. The product according to claim 25, wherein the instructions cause the computer to choose the attributes such that at least a predetermined fraction of the positive examples is characterized by the chosen attributes, and such that a larger fraction of the positive examples than of the negative examples is characterized by the chosen attributes.

29. The product according to claim 25, wherein the instructions cause the computer to choose splitting conditions for application at the nodes of the decision tree so that the decision tree is an optimal decision tree.

30. The product according to claim 29, wherein the decision tree comprises a root node, internal nodes, and leaf nodes, and wherein the instructions cause the computer to find a respective optimal splitting condition at the root node and at each of the internal nodes.

31. The product according to claim 30, wherein the instructions cause the computer to find the respective optimal splitting condition by choosing, at each node among the root and internal nodes, one of the attributes and the optimal splitting condition for application to the one of the attributes so as to maximize an optimization criterion for separating the positive examples contained in the node from the negative examples contained in the node.

32. The product according to claim 30, wherein the instructions cause the computer to determine one of the nodes to be a leaf node when the node contains only positive examples or only negative examples.

33. The product according to claim 30, wherein the instructions cause the computer to determine one of the nodes to be a leaf node when there is splitting condition that will separate the positive examples contained in the leaf node from the negative examples contained in the leaf node with an effectiveness greater than a predetermined minimum optimization criterion.

34. The product according to claim 25, wherein the instructions cause the computer to receive further input from the user indicating errors made by the decision tree in classifying the character string as belonging to the specified data type, and to refine the decision tree using the further input.

35. The product according to claim 25, wherein the instructions cause the computer to construct a regular expression based on the decision tree, and to apply the regular expression to the data.

36. The product according to claim 25, wherein the instructions cause the computer to apply the decision tree to the data so as to identify occurrences of the specified data type and use the occurrences to identify duplications in records in a database, and to resolve the duplications.