Automatically Mining Patterns For Rule Based Data Standardization Systems

• US 20130238610A1
• Filed: 03/07/2012
• Published: 09/12/2013
• Est. Priority Date: 03/07/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chaturvedi, Snigdha, Faruquie, Tanveer A., Karanam, Hima P., Mendelssohn, Marvin, Mohania, Mukesh K., Subramaniam, L. Venkata
• Granted Patent: US 10,163,063 B2
• Time in Patent Office: Days
• US Class Current: 707/723
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Computer program products and systems are provided for mining for sub-patterns within a text data set. The embodiments facilitate finding a set of N frequently occurring sub-patterns within the data set, extracting the N sub-patterns from the data set, and clustering the extracted sub-patterns into K groups, where each extracted sub-pattern is placed within the same group with other extracted sub-patterns based upon a distance value D that determines a degree of similarity between the sub-pattern and every other sub-pattern within the same group.

Claims

1. A system for mining for sub-patterns within a text data set, the system comprising:

a data source to store a text data set; and

a processor configured with logic to;

find a set of N frequently occurring sub-patterns within the data set;

extract the N sub-patterns from the data set; and

cluster the extracted sub-patterns into K groups such that each extracted sub-pattern is placed within the same group with other extracted sub-patterns based upon a distance value D that determines a degree of similarity between the sub-pattern and every other sub-pattern within the same group.

2. The system of claim 1, wherein the processor is configured to determine the distance value D between any two sub-patterns s₁ and s₂ of the N sub-patterns based upon the following equation:

3. The system of claim 1, wherein the processor is further configured with logic to:

assign a number ranking to each of the K groups based upon a frequency of occurrence of a sub-pattern within the data set for each group.

4. The system of claim 3, wherein the processor is configured to designate a first group including a sub-pattern having a highest frequency in relation to all other sub-patterns in the first group and a second group including a sub-pattern having a highest frequency in relation to all other sub-patterns in the second group, the highest frequency associated with the first group being greater than the highest frequency associated with the second group, and the first group being ranked with a lower number than a ranking number of the second group.

5. The system of claim 1, wherein the processor is further configured with logic to select a representative sub-pattern from each of the K groups.

6. A computer program product for mining for sub-patterns within a text data set, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code configured to;

find a set of N frequently occurring sub-patterns within the data set;

extract the N sub-patterns from the data set; and

cluster the extracted sub-patterns into K groups such that each extracted sub-pattern is placed within the same group with other extracted sub-patterns based upon a distance value D that determines a degree of similarity between the sub-pattern and every other sub-pattern within the same group.

7. The computer program product of claim 6, wherein the N frequently occurring sub-patterns are the N most frequently occurring sub-patterns within the data set.

8. The computer program product of claim 6, wherein each sub-pattern has a selected length of consecutive characters or symbols within the text data set that is no greater than a selected number.

10. The computer program product of claim 6, wherein the computer readable program code is further configured to:

assign a number ranking to each of the K groups based upon a frequency of occurrence of a sub-pattern within the data set for each group.

11. The computer program product of claim 10, wherein a first group includes a sub-pattern having a highest frequency in relation to all other sub-patterns in the first group and a second group includes a sub-pattern having a highest frequency in relation to all other sub-patterns in the second group, the highest frequency associated with the first group is greater than the highest frequency associated with the second group, and the first group is ranked with a lower number than a ranking number of the second group.

12. The computer program product of claim 6, wherein the computer readable program code is further configured to:

select a representative sub-pattern from each of the K groups.

13. The computer program product of claim 12, wherein the sub-pattern in each group of the K groups having a highest determined frequency of occurrence in relation to determined frequencies of occurrence for all other sub-patterns within each group is selected as the representative sub-pattern for each group.

9. A computer program product for mining for sub-patterns within a text data set, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code configured to;

find a set of N frequently occurring sub-patterns within the data set;

extract the N sub-patterns from the data set; and

cluster the extracted sub-patterns into K groups such that each extracted sub-pattern is placed within the same group with other extracted sub-patterns based upon a distance value D that determines a degree of similarity between the sub-pattern and every other sub-pattern within the same group;

wherein the computer readable program code is configured to calculate the distance value D between any two sub-patterns s₁ and s₂ of the N sub-patterns based upon the following equation;