Method for mining causality rules with applications to electronic commerce

• US 5,832,482 A
• Filed: 02/20/1997
• Issued: 11/03/1998
• Est. Priority Date: 02/20/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yu, Phillip Shi-lung, Liang, Bob Chao-Chu, Chen, Ming-Syan
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/804,128
• Time in Patent Office: 621 Days
• Field of Search: 707/1-10, 707/100-206, 707/500, 707/512, 707/515, 707/533, 705/10, 379/207, 600/523, 395/683, 364/468, 706/55
• US Class Current: 1/1
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

For mining causality rules in an event database, the rules are obtained by iteratively generating candidate rules and counting their occurrences in the event database. Newly identified causality rules are used to generate the next set of candidate rules to be evaluated, by increasing the size of the set of consequential events triggered by triggering events and/or the number of triggering events. The preferred embodiment uses an iterative approach to deriving the causality rules in order of the consequential set sizes and triggering set sizes. The detection of an occurrence of a causality rule in an event sequence is handled as a sub-sequence matching problem using a novel hierarchical matching method to improve efficiency.

Claims

1. A method for a computer to derive category information from a database of event data, wherein an event selected from said event data may belong to one or more of a plurality of categories, comprising the steps of:

preprocessing said event data into an event category database by ordering said event data into at least one event category sequence; and

determining at least one causality rule from said preprocessed event data, wherein said determining of causality rules comprises the steps of;

(a) selecting at least one trigger event category from said preprocessed event database;

(b) determining a first consequential set comprising at least one event category from said preprocessed event database which may be caused by said at least one trigger event category;

(c) pairing said at least one trigger event category and said first consequential set into a first causality rule candidate;

(d) counting the number of occurrences of said first causality rule candidate in said preprocessed event database;

(e) generating a successive causality rule candidate comprising said at least one trigger event category and a successive consequential set by adding at least one additional event category which may be caused by said trigger event category;

(f) obtaining a count of the number of occurrences of said successive causality rule candidate;

(g) comparing said count of the number of occurrences of said successive causality rule candidate to a pre-set threshold; and

(h) repeating steps (e) through (g) if said count exceeds said pre-set threshold.

2. The method of claim 1 additionally comprising the step of

(a) comparing said number of occurrences of said first causality rule candidate to a first rule threshold;

and

(b) deriving a second consequential set if said number of occurrences of said first causality rule candidate does not exceed said first rule threshold.

3. The method of claim 1 further comprising the step of applying at least one pre-defined constraint to said at least one event category and said at least one additional event category from said preprocessed event database which may be caused by said trigger event category.

4. The method of claim 1 wherein said event database includes at least one composite event and wherein said determining of said first consequential set is preceded by the steps of:

(a) breaking each of said at least one composite events into its basic event categories; and

(b) re-ordering said event category sequence including said basic event categories from said at least one composite event to provide a re-ordered event category sequence.

5. The method of claim 4 wherein said obtaining a count of the number of occurrences of said successive causality rule candidate comprises comparing said successive causality rule candidate to said re-ordered event category sequence.

6. The method of claim 5 further comprising the final step of comparing said determined at least one causality rule to said preprocessed event database.

7. The method of claim 6 wherein said comparing comprises applying a bipartite graph matching algorithm.

8. The method of claim 1 additionally comprising the steps of:

(a) generating a succeeding causality rule candidate comprising said successive causality rule candidate and at least one additional trigger event category;

(b) obtaining a count of the number of occurrences of said succeeding causality rule candidate;

(c) comparing said count of the number of occurrences of said succeeding causality rule candidate to said pre-set threshold; and

(d) repeating steps (a) through (c) if said count exceeds said pre-set threshold.

9. A method for a computer to derive category information from a database of event data, wherein an event selected from said event data may belong to one or more of a plurality of categories, comprising the steps of:

(a) preprocessing said event data into an event category database by sorting said event data according to event criteria and mapping said sorted event data into said event categories; and

(b) determining at least one causality rule from said preprocessed event data.

10. The method of claim 9 additionally comprising the step of forming a plurality of event category sequences, whereby at least one event category sequence is formed for each event category.

11. The method of claim 9 wherein said event criteria comprises user information.