TIME-SERIES PATTERN FINDING APPARATUS, METHOD AND PROGRAM

• US 20080222109A1
• Filed: 01/29/2008
• Published: 09/11/2008
• Est. Priority Date: 03/09/2007
• Status: Abandoned Application

• Current Assignee: AMIN Turocy&Calvin LLP, Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Sakurai, Shigeaki
• Application Number:
  US12/021,747
• Publication Number:
  US 20080222109A1
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: A61B 5/022 by applying pressure to close blood vessels, e.g. against the skin; Ophthalmodynamometers
• CPC Class Codes: A61B 5/14532 for measuring glucose, e.g. by tissue impedance measurement
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: G06F 2218/00 Aspects of pattern recognition specially adapted for signal processing

Abstract

A time-series pattern finding apparatus, includes decomposing unit decomposing a condition, which indicates a condition of time-series relationship between first elements each defined as including first events each including an attribute and an attribute value of the attribute, into a partial condition, determining unit determining whether the partial condition holds for each potential events, each potential characteristic event sets, and each potential time-series patterns, calculating unit calculating frequency of occurrence in the time-series data items only for fourth events in the potential events, first sets in the potential characteristic event sets, and first patterns in the potential time-series patterns, which satisfy the partial condition, and extracting unit extracting a potential event, a potential event set and a potential time-series pattern from the fourth events, the first sets and the first patterns, respectively, based on the frequency of occurrence not less than a threshold value, as a time-series pattern.

Claims

1. A time-series pattern finding apparatus, comprising:

a decomposing unit configured to decompose a time-series constraint condition, which indicates a condition of time-series relationship between first elements each defined as including one or more first events each including an attribute and an attribute value of the attribute, into a partial time-series constraint condition which is generated by combining the first events, the attribute being a property indicating a characteristic of data;

a determining unit configured to determine whether the partial time-series constraint condition holds for each of potential events, for each of potential characteristic event sets, and for each of potential time-series patterns, the potential events being extracted from one of time-series data items indicating the time-series relationship, the potential characteristic event sets being generated from characteristic event sets and formed of plural second events, number of the second events being more than number of third events included in the characteristic event sets, the potential time-series patterns being generated from time-series patterns and formed of plural second elements, the number of second elements being more than the number of third elements included in the potential time-series patterns;

a calculating unit configured to calculate frequency of occurrence in the time-series data items only for fourth events in the potential events, first sets in the potential characteristic event sets, and first patterns in the potential time-series patterns, the fourth events, the first sets, and the first patterns satisfying the partial time-series constraint condition; and

an extracting unit configured to extract a potential event, a potential event set and a potential time-series pattern from the fourth events, the first sets and the first patterns, respectively, the potential event, the potential event set and the potential time-series pattern having an evaluation value based on the frequency of occurrence not less than a threshold value, as a time-series pattern.

2. A time-series pattern finding apparatus, comprising:

a constraint condition storage unit configured to store, as a time-series constraint condition, a time-series relationship between first elements, each of which is defined as including one or more first events each including an attribute and an attribute value of the attribute, the attribute being a property indicating a characteristic of data;

a decomposing unit configured to decompose the time-series constraint condition into a plurality of partial constraint conditions in a time-series manner;

a data storage unit configured to store a plurality of time-series data items, each of which indicates the time-series relationship;

a first extracting unit configured to extract a second event from one of the time-series data items;

a first calculating unit configured to calculate a first rate of inclusion of the second event in each of the time-series data items when an attribute value included in the second event is included in the partial constraint conditions;

a second extracting unit configured to extract the second event as a characteristic event when the first rate is not less than a threshold value;

a characteristic event storage unit configured to store all characteristic events extracted for all the time-series data items stored in the data storage unit;

a first selecting unit configured to select two characteristic event sets including a first event number from the characteristic events;

a first generating unit configured to generate a potential characteristic event set including all characteristic events included in the two characteristic event sets, when the two characteristic event sets partly match and do not completely match;

a second calculating unit configured to calculate a second rate of inclusion of the potential characteristic event set in each of the time-series data items;

a third extracting unit configured to extract, as a first time-series pattern, the potential characteristic event set when the second rate is not less than a threshold value;

a pattern storage unit configured to store the first time-series pattern to obtain first time-series patterns;

a determining unit configured to determine whether second time-series patterns each having a second event number obtained by adding 1 to the first event number and having a first element number are included in the pattern storage unit when a third time-series pattern having a third event number larger than the first event number by 1 and having the first element number is not included in the pattern storage unit;

a second selecting unit configured to select, from the first time-series patterns, two time-series patterns each having the second event number and having the first element number when the determining unit determines that the second time-series patterns are included;

a second generating unit configured to generate a potential time-series pattern obtained by adding a last element of one time-series patterns to the other time-series pattern of the two time-series patterns when the two time-series patterns partly match and do not completely match; and

a third calculating unit configured to calculate a third rate of inclusion of the potential time-series pattern in each of the time-series data items when the potential time-series pattern corresponds to the partial constraint conditions,

wherein the potential time-series pattern is extracted as the first time-series pattern and stored in the pattern storage unit, when the third rate is not less than a threshold value, and

processing performed by the determining unit, the second selecting unit, the second generating unit, and the third calculating unit is performed for a fourth time-series pattern of a second element number obtained by 1 to the first element number, and third time-series patterns for all element numbers are stored in the pattern storage unit.

3. The apparatus according to claim 2, wherein

the first generating unit generates, as the potential characteristic event set, a set obtained by adding an event located at an end of one set to the other set, when the other event partial sets of two sets match except for events located at an end of the sets and attributes of the events located at an end of the sets do not match.

4. The apparatus according to claim 2, wherein

the second generating unit generates, as the potential time-series pattern, a time-series pattern obtained by adding the last element of one time-series pattern to the other time-series pattern of the two time-series patterns when the partial time-series patterns of the two time-series patterns match except for the last element and attribute sets of the events included in the last element do not match.

5. The apparatus according to claim 2, wherein

the first calculating unit calculates the first rate by the following:

(number of time-series data items including the second event)/(number of time-series data items stored in the data storage unit).

6. The apparatus according to claim 2, wherein

the second calculating unit calculates the second rate by the following:

(number of time-series data items including the potential characteristic event set)/(number of time-series data items stored in the data storage unit).

7. The apparatus according to claim 2, wherein

the third calculating unit calculates the third rate by the following:

(number of time-series data items including the potential time-series pattern)/(number of time-series data items stored in the data storage unit).

8. The apparatus according to claim 2, wherein

the first generating unit starts generation of a potential characteristic event set from case where the first event number is 1.

9. The apparatus according to claim 2, wherein

the first element number is 1.

10. A time-series pattern finding method, comprising:

decomposing a time-series constraint condition, which indicates a condition of time-series relationship between first elements each defined as including one or more first events each including an attribute and an attribute value of the attribute, into a partial time-series constraint condition which is generated by combining the first events, the attribute being a property indicating a characteristic of data;

determining whether the partial time-series constraint condition holds for each of potential events, for each of potential characteristic event sets, and for each of potential time-series patterns, the potential events being extracted from one of time-series data items indicating the time-series relationship, the potential characteristic event sets being generated from characteristic event sets and formed of plural second events, number of the second events being more than number of third events included in the characteristic event sets, the potential time-series patterns being generated from time-series patterns and formed of plural second elements, the number of second elements being more than the number of third elements included in the potential time-series patterns;

calculating frequency of occurrence in the time-series data items only for fourth events in the potential events, first sets in the potential characteristic event sets, and first patterns in the potential time-series patterns, the fourth events, the first sets, and the first patterns satisfying the partial time-series constraint condition; and

extracting a potential event, a potential event set and a potential time-series pattern from the fourth events, the first sets and the first patterns, respectively, the potential event, the potential event set and the potential time-series pattern having an evaluation value based on the frequency of occurrence not less than a threshold value, as a time-series pattern.

11. A time-series pattern finding method, comprising:

storing in a constraint condition storage unit, as a time-series constraint condition, a time-series relationship between first elements, each of which is defined as including one or more first events each including an attribute and an attribute value of the attribute, the attribute being a property indicating a characteristic of data;

decomposing the time-series constraint condition into a plurality of partial constraint conditions in a time-series manner;

storing in a data storage unit a plurality of time-series data items, each of which indicates the time-series relationship;

extracting a second event from one of the time-series data items;

calculating a first rate of inclusion of the second event in each of the time-series data items when an attribute value included in the second event is included in the partial constraint conditions;

extracting the second event as a characteristic event when the first rate is not less than a threshold value;

storing in a characteristic event storage unit all characteristic events extracted for all the time-series data items stored in the data storage unit;

selecting two characteristic event sets including a first event number from the characteristic events;

generating a potential characteristic event set including all characteristic events included in the two characteristic event sets, when the two characteristic event sets partly match and do not completely match;

calculating a second rate of inclusion of the potential characteristic event set in each of the time-series data items;

extracting, as a first time-series pattern, the potential characteristic event set when the second rate is not less than a threshold value;

storing in a pattern storage unit the first time-series pattern to obtain first time-series patterns;

determining whether second time-series patterns each having a second event number obtained by adding 1 to the first event number and having a first element number are included in the pattern storage unit when a third time-series pattern having a third event number larger than the first event number by 1 and having the first element number is not included in the pattern storage unit;

selecting, from the first time-series patterns, two time-series patterns each having the second event number and having the first element number when the determining unit determines that the second time-series patterns are included;

generating a potential time-series pattern obtained by adding a last element of one time-series patterns to the other time-series pattern of the two time-series patterns when the two time-series patterns partly match and do not completely match;

calculating a third rate of inclusion of the potential time-series pattern in each of the time-series data items when the potential time-series pattern corresponds to the partial constraint conditions; and

storing in the pattern storage unit third time-series patterns for all element numbers.