Sequence miner

• US 20040024773A1
• Filed: 04/29/2003
• Published: 02/05/2004
• Est. Priority Date: 04/29/2002
• Status: Abandoned Application

• Current Assignee: Kilian Stoffel, Paul Cotofrei
• Original Assignee: Kilian Stoffel, Paul Cotofrei
• Inventors: Cotofrei, Paul, Stoffel, Kilian
• Application Number:
  US10/425,507
• Publication Number:
  US 20040024773A1
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

A computer-based data mining method wherein an event database is extracted from sequential raw data in the form of a multi-dimensional time series and comprehensible temporal rules are extracted using the event database

Claims

1. A computer-based data mining method comprising:

a) obtaining sequential raw data;

b) extracting an event database from the sequential raw data; and

c) extracting comprehensible temporal rules using the event database.

2. The method of claim 1, wherein extracting an event database comprises extracting events from a multi-dimensional time series.

3. The method of claim 1, wherein extracting an event database comprises transforming sequential raw data into sequences of events wherein each event is a named sequence of points extracted from the raw data and characterized by a finite set of predefined features.

6. The method of claim 1, wherein extracting an event database includes discrete and continuous aspects from the sequential raw data.

7. The method of claim 6, wherein time series discretisation is used to describe the discrete aspect of the sequential raw data.

8. The method of claim 7, wherein the time series discretisation employs a window clustering method.

9. The method of claim 8, wherein the window clustering method includes a window of width w on a sequence s, wherein a set W(s) is formed from all windows w on the set s and wherein a distance for time series of length w is provided to cluster the set W(s), the distance being the distance between normalized sequences.

10. The method of claim 6, wherein global feature calculation is used to describe the continuous aspect of the sequential raw data.

11. The method of claim 1, wherein the sequential raw data is multi-dimensional and more than one time series at a time is considered during the extracting.

12. The method of claim 1, wherein the comprehensible temporal rules have one or more of the following characteristics:

a) containing explicitly at least a sequential and preferably a temporal dimension;

b) capturing the correlation between time series;

c) predicting possible future events including values, shapes or behaviors of sequences in the form of denoted events; and

d) presenting a structure readable and comprehensible by human experts.

13. The method of claim 1, wherein extracting comprehensible temporal rules comprises:

a) utilizing a decision tree procedure to induce a hierarchical classification structure;

b) extracting a first set of rules from the hierarchical classification structure; and

c) filtering and transforming the first set of rules to obtain comprehensible rules for use in feeding a knowledge representation system to answer questions.

14. The method of claim 1, wherein extracting comprehensible temporal rules comprises producing knowledge that can be represented in general Horn clauses.

15. The method of claim 1, wherein extracting comprehensible temporal rules comprises:

a) applying a first inference process, using the event database, to obtain a classification tree; and

b) applying a second inference process using the previously obtained classification tree and the previously extracted event database to obtain a set of temporal rules from which the comprehensible temporal rules are extracted.

16. The method of claim 15, wherein the process to obtain a classification tree comprises:

a) specifying criteria for predictive accuracy;

b) selecting splits;

c) determining when to stop splitting; and

d) selecting the right-sized tree.

17. The method of claim 15, wherein specifying criteria for predictive accuracy includes applying a C4.5 algorithm to minimize observed error rate using equal priors.

18. The method of claim 15, wherein selecting splits is performed on predictor variable used to predict membership of classes of dependent variables for cases or objects involved.

19. The method of claim 15, wherein determining when to stop splitting is selected from one of the following:

a) continuing the splitting process until all terminal nodes are pure or contain no more than a specified number of cases or objects; and

b) continuing the splitting process until all terminal nodes are pure or contain no more cases than a specified minimum fraction of the sizes of one or more classes.

20. The method of claim 15, wherein selecting the right-sized tree includes applying a C4.5 algorithm to a tree-pruning process which uses only the training set from which the tree was built.

21. The method of claim 15, wherein the second inference process uses a first-order logic language to extract temporal rules from initial sets and wherein quantitative and qualitative aspects of the rules are ranked by a J-measure metric.

4. The method of claim 4, wherein extraction of points is obtained by clustering.

5. The method of claim 4, wherein features describing events are extracted using statistical feature extraction processing.