Method and system for detecting frequent association patterns

• US 6,618,725 B1
• Filed: 10/30/2000
• Issued: 09/09/2003
• Est. Priority Date: 10/29/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Fukuda, Takeshi, Matsuzawa, Hirofumi
• Primary Examiner(s): Mizrahi, Diane D.
• Assistant Examiner(s): Wu, Yicun
• Application Number:
  US09/699,661
• Time in Patent Office: 1,044 Days
• Field of Search: 707/1, 707/2, 707/3, 707/7, 707/100, 707/101, 400/63
• US Class Current: 1/1
• CPC Class Codes: G06F 16/345 Summarisation for human users
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A text-mining system and method automatically extracts useful information from a large set of tree-structured data by generating successive sets of candidate tree-structured association patterns for comparison with the tree-structured data. The number of times is counted that each of the candidate association patterns matches with a tree in the set of tree-structured data in order to determine which of the candidate association patterns frequently matches with a tree in the data set. Each successive set of candidate association patterns is generated from the frequent association patterns determined from the previous set of candidate association patterns.

Claims

1. A system for detecting frequent association patterns in a database of tree-structured data, comprising:

means for automatically generating an initial current set of candidate association patterns for counting;

means for counting association patterns in the database that match with the current set of candidate association patterns;

means for detecting frequent association patterns in the database from the result of said counting; and

means for automatically generating a new current set of candidate association patterns for next counting from said detected frequent association patterns.

2. A text-mining system for extracting useful concepts from a large volume of text data, comprising:

(a) means for parsing sentences in the text data;

(b) means for generating a set of structured trees of text data based on the results of said parsing;

(c) means for automatically generating an initial current set of candidate tree-structured association patterns for counting;

(d) means for counting tree-structured association patterns in the set of structured trees that match with one or more of the candidate tree-structured association patterns in the current counting set of candidate tree-structured association patterns;

(e) means for detecting frequent tree-structured association patterns in the set of structured trees from the result of said counting; and

(f) means for automatically generating a new current set of candidate tree-structured association patterns for next counting from said detected frequent tree-structured association patterns.

3. A text-mining system as in claim 2 for automatically generating a set of Frequently Asked Questions from a large volume of text data and further comprising:

(g) means for extracting original text data matching with said frequent tree-structured association patterns.

4. A text-mining system as in claim 2 for automatically classifying text data into a plurality of categories, and further comprising:

(g) means for detecting text data matching with said frequent tree-structured association patterns to classify the data into categories.

5. A method for detecting frequent association patterns in a database of tree-structured data, comprising the steps of:

automatically generating an initial current set of candidate association patterns for counting;

counting association patterns in the database that match with the current set of candidate association patterns;

detecting frequent association patterns in the database from the result of said counting; and

automatically generating a new set of current candidate association patterns for next counting from said detected frequent association patterns.

6. A record medium comprising a program for detecting frequent association patterns in a database of tree-structured data, said program having a computer implement:

a function for automatically generating an initial current set of candidate association patterns for counting;

a function for counting association patterns in the database that match with the current set of candidate association patterns;

a function for detecting frequent association patterns in the database from the result of said counting; and

a function for automatically generating a new set of candidate association patterns for next counting from said detected frequent association patterns.