System and method for meta-pattern discovery

• US 6,785,663 B2
• Filed: 12/28/2000
• Issued: 08/31/2004
• Est. Priority Date: 12/28/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wang, Wei, Yu, Philip Shi-Lung, Yang, Jiong
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/752,620
• Publication Number:
  US 20020087495A1
• Time in Patent Office: 1,342 Days
• Field of Search: 706/45, 382/229
• US Class Current: 706/45
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 2218/08 Feature extraction

Abstract

Periodic patterns in time series data can be hierarchical in nature, where a higher level pattern may comprise repetitions of lower level patterns. In the presence of noises, these repetitions of lower level patterns may not be perfect. A novel model, namely a meta-pattern, is provided in accordance with the present invention to capture these higher level patterns. The meta-pattern can not only provide a more compact representation of patterns but also capture the regularities of pattern evolutions, which may not be expressed by previous models due to the presence of noise. A method is provided to mine meta-patterns in an iterative manner by discovering meta-patterns and their supporting subsequences in the form of lists of segments of contiguous repetitions of a meta-pattern. The number of pattern repetitions in each said segment is at least a predefined threshold min_rep and the distance between any two adjacent segments is at most a predefined threshold max_dis.

Claims

1. A method of processing a sequence of symbols, the method comprising the steps of:

obtaining the sequence of symbols; and

identifying at least one meta-pattern in the sequence of symbols, the at least one meta-pattern being configured as a list of components, wherein each component of the at least one meta-pattern can be one of a symbol appearing in the sequence, a don'"'"'t care symbol, and another previously discovered pattern.

2. The method of claim 1, wherein the sequence of symbols comprises time series data.

3. The method of claim 1, wherein the sequence of symbols comprises event data.

4. A method of mining meta-patterns in a sequence of symbols, the method comprising the steps of:

obtaining the sequence of symbols; and

identifying at least one meta-pattern and corresponding subsequences of the at least one meta-pattern, wherein the subsequence is a list of segments of contiguous repetitions of the meta-pattern and wherein the number of repetitions in each segment is not less than a predefined threshold and a distance between any two adjacent segments is not greater than a predefined threshold.

5. The method of claim 4, wherein the identifying step further comprises an iterative process, wherein during the lth iteration, all meta-patterns of level l are mined.

6. The method of claim 5, wherein mining patterns of level l, 1 being greater than one, comprises the steps of:

generating candidate components from discovered level (l−

1) patterns; and

generating level l meta-patterns.

7. The method of claim 6, wherein the step of generating candidate components from level (l−

1) meta-patterns comprises an iterative process, wherein each level (l−

1) meta-pattern is examined sequentially.

8. The method of claim 7, wherein examining a given level (l−

1) meta-pattern comprises the steps of;

identifying a set of maximum valid segments of the level (l−

1) meta-pattern; and

generating candidate components involving the level (l−

1) meta-pattern.

9. The method of claim 8, wherein the step of identifying the set of maximum valid segments of a given meta-pattern further comprises the steps of:

identifying occurrences of the meta-pattern in the symbol sequence; and

generating the set of maximum valid segments of the meta-pattern.

10. The method of claim 9, wherein the step of identifying occurrences of a given meta-pattern in the symbol sequence uses a sliding window of width equal to a span of the meta-pattern.

11. The method of claim 8, wherein the step of generating candidate components involving a given meta-pattern further comprises the steps of:

discovering periodicy exhibited by the valid subsequences of the meta-pattern; and

generating candidate components involving the meta-pattern from the discovered periodicy preserved by valid subsequences of the meta-pattern.

12. The method of claim 11, wherein the step of discovering periodicy exhibited by the valid subsequences of a given meta-pattern further comprises the steps of:

collecting sets of possible starting positions and ending positions of valid subsequences of the meta-pattern; and

finding periodicy preserved by these starting positions and ending positions.

13. The method of claim 6, wherein the step of generating level/meta-patterns from the set of candidate components further comprises an iterative process, wherein during the kth iteration, the set of level l meta-patterns with at least one k non-don'"'"'t care component are mined.

14. The method claim 13, wherein the step of generating level l meta-patterns with at least one k non-don'"'"'t care component further comprises of the steps of:

constructing candidate level l meta-patterns with at least one k non-don'"'"'t care component; and

validating candidate meta-patterns against the symbol sequence.

15. The method of claim 14, wherein the step of constructing candidate level l meta-patterns with at least one k non-don'"'"'t care component utilizes a component-based property when k is equal to one.

16. The method of claim 15, wherein the component-based property is that a meta-pattern P may serve as a component of some higher level meta-pattern of span k only if the locations of valid subsequences of P exhibit some cyclic behavior with period k.

17. The method of claim 14, wherein the step of constructing candidate level l meta-patterns with at least one k non-don'"'"'t care component utilizes an a priori property when k is greater than one.

18. The method of claim 4, wherein the sequence of symbols comprises time series data.

19. The method of claim 4, wherein the sequence of symbols comprises event data.

20. Apparatus for processing a sequence of symbols, the apparatus comprising:

at least one processor operative to;

(i) obtain the sequence of symbols; and

(ii) identify at least one meta-pattern in the sequence of symbols, the at least one meta-pattern being configured as a list of components, wherein each component of the at least one meta-pattern can be one of a symbol appearing in the sequence, a don'"'"'t care symbol, and another previously discovered pattern.

21. The apparatus of claim 20, wherein the sequence of symbols comprises time series data.

22. The apparatus of claim 20, wherein the sequence of symbols comprises event data.

23. Apparatus for mining meta-patterns in a sequence of symbols, the apparatus comprising:

at least one processor operative to;

(i) obtain the sequence of symbols; and

(ii) identify at least one meta-pattern and corresponding subsequences of the at least one meta-pattern, wherein the subsequence is a list of segments of contiguous repetitions of the meta-pattern and wherein the number of repetitions in each segment is not less than a predefined threshold and a distance between any two adjacent segments is not greater than a predefined threshold.

24. The apparatus of claim 23, wherein the identifying operation further comprises an iterative process, wherein during the lth iteration, all meta-patterns of level l are mined.

25. The apparatus of claim 24, wherein mining patterns of level l, l being greater than one, comprises:

(i) generating candidate components from discovered level (l−

1) patterns; and

(ii) generating level l meta-patterns.

26. The apparatus of claim 25, wherein the operation of generating candidate components from level (l−

1) meta-patterns comprises an iterative process, wherein each level (l−

1) meta-pattern is examined sequentially.

27. The apparatus of claim 26, wherein examining a given level (l−

1) meta-pattern comprises;

(i) identifying a set of maximum valid segments of the level (l−

1) meta-pattern; and

(ii) generating candidate components involving the level (l−

1) meta-pattern.

28. The apparatus of claim 27, wherein the operation of identifying the set of maximum valid segments of a given meta-pattern further comprises:

(i) identifying occurrences of the meta-pattern in the symbol sequence; and

(ii) generating the set of maximum valid segments of the meta-pattern.

29. The apparatus of claim 28, wherein the operation of identifying occurrences of a given meta-pattern in the symbol sequence uses a sliding window of width equal to a span of the meta-pattern.

30. The apparatus of claim 27, wherein the operation of generating candidate components involving a given meta-pattern further comprises:

(i) discovering periodicy exhibited by the valid subsequences of the meta-pattern; and

(ii) generating candidate components involving the meta-pattern from the discovered periodicy preserved by valid subsequences of the meta-pattern.

31. The apparatus of claim 30, wherein the operation of discovering periodicy exhibited by the valid subsequences of a given meta-pattern further comprises:

(i) collecting sets of possible starting positions and ending positions of valid subsequences of the meta-pattern; and

(ii) finding periodicy preserved by these starting positions and ending positions.

32. The apparatus of claim 25, wherein the operation of generating level l meta-patterns from the set of candidate components further comprises an iterative process, wherein during the kth iteration, the set of level l meta-patterns with at least one k non-don'"'"'t care component are mined.

33. The apparatus of claim 32, wherein the operation of generating level/meta-patterns with at least one k non-don'"'"'t care component further comprises:

(i) constructing candidate level l meta-patterns with at least one k non-don'"'"'t care component; and

(ii) validating candidate meta-patterns against the symbol sequence.

34. The apparatus of claim 33, wherein the operation of constructing candidate level l meta-patterns with at least one k non-don'"'"'t care component utilizes a component-based property when k is equal to one.

35. The apparatus of claim 34, wherein the component-based property is that a meta-pattern P may serve as a component of some higher level meta-pattern of span k only if the locations of valid subsequences of P exhibit some cyclic behavior with period k.

36. The apparatus of claim 33, wherein the operation of constructing candidate level l meta-patterns with at least one knon-don'"'"'t care component utilizes an a priori property when k is greater than one.

37. The apparatus of claim 23, wherein the sequence of symbols comprises time series data.

38. The apparatus of claim 23, wherein the sequence of symbols comprises event data.

39. An article of manufacture for processing a sequence of symbols, the article comprising a machine readable medium containing one or more programs which when executed implement the steps of:

obtaining the sequence of symbols; and

identifying at least one meta-pattern in the sequence of symbols, the at least one meta-pattern being configured as a list of components, wherein each component of the at least one meta-pattern can be one of a symbol appearing in the sequence, a don'"'"'t care symbol, and another previously discovered pattern.

40. An article of manufacture for mining meta-patterns in a sequence of symbols, the article comprising a machine readable medium containing one or more programs which when executed implement the steps of:

obtaining the sequence of symbols; and

identifying at least one meta-pattern and corresponding subsequences of the at least one meta-pattern, wherein the subsequence is a list of segments of contiguous repetitions of the meta-pattern and wherein the number of repetitions in each segment is not less than a predefined threshold and a distance between any two adjacent segments is not greater than a predefined threshold.