System and method for classification using time sequences

• US 6,721,719 B1
• Filed: 07/26/1999
• Issued: 04/13/2004
• Est. Priority Date: 07/26/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C., Yu, Philip Shi-lung
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/361,381
• Time in Patent Office: 1,723 Days
• Field of Search: 706/20, 706/48, 345/440, 367/135, 382/220, 600/544, 700/52, 702/15, 702/19, 704/200, 704/240, 704/248, 704/254, 707/7, 714/26
• US Class Current: 706/20
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

System and method for generating classification using time sequences comprises inputting a set of time dependant feature variable graphs along with a set of time dependant category variable graphs; finding frequent shapes in the time dependant feature variable graphs; utilizing the frequent shapes to generate combinations of frequent shapes; generating rules relating one or more patterns of combinations of frequent shapes to a category variable; and, performing a categorization utilizing the rules generated.

Claims

1. Method of generating classification using time sequences comprising the steps of:

(a) receiving a set of time dependant feature variable graphs and a set of time dependant category variable graphs;

(b) finding frequent shapes in the time dependant feature variable graphs;

(c) utilizing frequent shapes in step b) to generate combinations of frequent shapes;

(d) generating rules relating one or more patterns of combinations of frequent shapes to a category variable; and

,

(e) performing a time-dependent categorization utilizing the rules generated in step d).

2. The method as claimed in claim 1, wherein said step e) of performing a categorization includes:

checking all rules for which there is a pattern matching the current test instance, a test instance comprising a set of feature variable graphs and a time stamp;

predicting a categorical variable at an input time stamp; and

, outputting said categorical variable.

3. The method as claimed in claim 2, wherein said step b) of finding frequent shapes in the time dependant feature variable graphs comprises iteratively determining (k+1)-shapes after finding k-shapes, with k being a length of a shape in contiguous time intervals.

4. The method as claimed in claim 1, wherein said step b) of finding frequent shapes in the time dependant feature variable graphs further includes:

discretizing behavior of each said graph into a plurality of time intervals; and

,

determining contiguous sequences of movement in time of the feature variable value in each said graph to generate a shape.

5. The method as claimed in claim 4, wherein said step b) of finding frequent shapes further includes:

determining a support for each said shape found, said support representing a percentage of all input feature variable graphs which contain said determined shape; and

,

setting as a frequent shape those shapes meeting a minimum support threshold.

6. The method as claimed in claim 1, wherein said step c) of generating combinations includes the step of combining the frequent shape patterns found in step b), each frequent shape pattern being of a same length and occurring during a same time-period.

7. The method as claimed in claim 1, wherein said step d) of generating possible rules includes:

constructing all combinations of frequent shapes as an antecedent condition;

relating each possible combination with a possible categorical value as a consequent; and

,

determining a rule that meets a minimum confidence value defined as a percentage of time that the rule is true given true antecedent conditions.

8. The method as claimed in claim 7, wherein said possible rules generated in step d) further includes:

denoting a phase lag of predetermined time t units for each possible rule, with a phase lag representing a duration of time from an end of a frequent shape time period that a categorical variable holds true; and

,

determining a rule that meets a minimum confidence and a phase lag of time t units.

9. The method as claimed in claim 8, wherein said step of determining possible rules is an iterative process with each iteration having a different phase lag of t units, whereby in each iteration, rules are found having a time lag of t units.

10. The method as claimed in claim 8, wherein said step (e) includes performing a categorization at a given time stamp and given feature variable graphs, said step e) including:

finding all rules having antecedent matches in said given feature variable graphs; and

,

ascertaining most commonly occurring categorical variable in consequents of said matched rules.

11. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for generating classification using time sequences, said method steps comprising:

(a) receiving a set of time dependant feature variable graphs and a set of time dependant category variable graphs;

(b) finding frequent shapes in the time dependant feature variable graphs;

(c) utilizing frequent shapes in step b) to generate combinations of frequent shapes;

(d) generating rules relating one or more patterns of combinations of frequent shapes to a category variable; and

,

(e) performing a time-dependent categorization utilizing the rules generated in step d).

12. The program storage device readable by a machine as claimed in claim 11, wherein said step e) of performing a categorization includes:

checking all rules for which there is a pattern matching the current test instance, a test instance comprising a set of feature variable graphs and a time stamp;

predicting a categorical variable at an input time stamp; and

,

outputting said categorical variable.

13. The program storage device readable by a machine as claimed in claim 12, wherein said step b) of finding frequent shapes in the time dependant feature variable graphs comprises iteratively determining (k+1)-shapes after finding k-shapes, with k being a length of a shape in contiguous time intervals.

14. The program storage device readable by a machine as claimed in claim 11, wherein said step b) of finding frequent shapes in the time dependant feature variable graphs further includes:

discretizing behavior of each said graph into a plurality of time intervals; and

,

determining contiguous sequences of movement in time of the feature variable value in each said graph to generate a shape.

15. The program storage device readable by a machine as claimed in claim 14, wherein said step b) of finding frequent shapes further includes:

determining a support for each said shape found, said support representing a percentage of all input feature variable graphs which contain said determined shape; and

,

setting as a frequent shape those shapes meeting a minimum support threshold.

16. The program storage device readable by a machine as claimed in claim 11, wherein said step c) of generating combinations includes the step of combining the frequent shape patterns found in step b), each frequent shape pattern being of a same length and occurring during a same time-period.

17. The program storage device readable by a machine as claimed in claim 11, wherein said step d) of generating possible rules includes:

constructing all combinations of frequent shapes as an antecedent condition;

relating each possible combination with a possible categorical value as a consequent; and

,

determining a rule that meets a minimum confidence value defined as a percentage of time that the rule is time given true antecedent conditions.

18. The program storage device readable by a machine as claimed in claim 17, wherein said possible rules generated in step d) further includes:

denoting a phase lag of predetermined time t units for each possible rule, with a phase lag representing a duration of time from an end of a frequent shape time period that a categorical variable holds true; and

,

determining a rule that meets a minimum confidence and a phase lag of time t units.

19. The program storage device readable by a machine as claimed in claim 18, wherein said step of determining possible rules is an iterative process with each iteration having a different phase lag of t units, whereby in each iteration, rules are found having a time lag of t units.

20. The program storage device readable by a machine as claimed in claim 18, wherein said step (e) includes performing a categorization at a given time stamp and given feature variable graphs, said step e) including:

finding all rules having antecedent matches in said given feature variable graphs; and

,

ascertaining most commonly occurring categorical variable in consequents of said matched rules for output thereof.

21. System for generating classifications using time sequences comprising the steps of:

means for storing data representing a set of time dependant feature variable graphs along with a set of time dependant category variable graphs;

means for generating a possible set of rules relating one or more variables of said set of time dependant feature variable graphs to a categorical variable of said time dependant category variable graphs;

means for receiving a test instance comprising a further set of time dependent variable graphs and a user-defined time stamp; and

,

means for predicting from said rules a categorical variable at said user-defined time stamp.

22. The system as claimed in claim 21, wherein said means for generating a possible set of rules comprises:

means for finding frequent shapes in said stored time dependant feature variable graphs;

means for utilizing frequent shapes to generate combinations of frequent shapes, said generating means generating rules relating one or more patterns of combinations of frequent shapes to a category variable.

23. The system as claimed in claim 22, wherein said means for finding frequent shapes in the time dependant feature variable graphs further includes:

means for discretizing behavior of each said graph into a plurality of time intervals; and

,

means for determining contiguous sequences of movement in time of the feature variable value in each said graph to generate a shape.

24. The system as claimed in claim 23, wherein said means for finding frequent shapes further includes means for applying a support threshold for each said shape found and establishing a frequent shape as those shapes meeting said minimum support threshold.

25. The system as claimed in claim 24, wherein said means for generating a possible set of rules further comprises:

means for constructing all combinations of frequent shapes as an antecedent condition and relating each possible combination with a possible categorical value as a consequent; and

,

means for applying a minimum confidence criteria to each generated rule and establishing a rule when a confidence criteria is met.

26. The system as claimed in claim 25, wherein said means for predicting from said rules a categorical variable at said user-defined time stamp fixer includes:

means for finding all rules having antecedent matches in said given time dependent feature variable graphs;

means for determining most commonly occuring categorical variable in consequents of said matched rules; and

,

means for outputting said most commonly occurring categorical variable.