JP7804319B2 - Time series classification device, time series classification program, and time series classification method - Google Patents

Description

Article 30, Paragraph 2 of the Patent Act applies. (1) Announced on July 11, 2021 at https://ieeexplorer.ieee.org/document/9494521. (2) Announced at the IEEE International Conference on Fuzzy Systems (FUZZ-IEEE) 2021 on July 12, 2021.

The present invention relates to a time series classification device, a time series classification program, and a time series classification method.

In the real world, various time series (or time series data) are generated. For example, ECG data (electrocardiogram data). A time series is a sequence of values (a series of values) obtained by observing the temporal change of a phenomenon continuously (or discontinuously at regular intervals). For example, it is a data sequence measured over time in statistics or signal processing, and is usually measured at regular time intervals (adapted from Wikipedia).

Classifying such time series is an important task. For example, as shown in the actual time series data TR_TSDB in Figures 2 and 3 (described below), 16 time series ts1 to ts16 each have 10 event values, timestamps 1 to 10. The 16 time series are then classified into two classes CL (CL=1 and CL=2), each with 8 events.

Given a classification model (classification device) with the above 16 time series as training data, the time series classifier classifies the test (target) time series into one of two classes based on the model's training data. In the case of the ECG data mentioned above, a classifier using ECG data of various cardiac diseases as training time series would classify the patient's ECG data time series into one of the cardiac diseases.

Conventional time series classification devices include the shortest Euclidean distance method, RNN, LSTM, and GRU (Recurrent neural network, Long Short Term Memory, Gated recurrent unit, each of which is a type of machine learning).

Fuzzy Classification of Time Series Data, Penugonda Ravikumar, V. Susheela Devi, published on October 8, 2013, 2013 IEEE-FUZZ Weighted Feature-based Classification of Time Series Data, Penugonda Ravikumar, V. Susheela Devi, published on January 15, 2015, 2014 IEEE-CIDM A Novel Parameter-Free Energy Efficient Fuzzy Nearest Neighbor Classifier for Time Series Data, Penugonda Ravikumar, R. Uday Kiran, et.al., published July 11, 2021, 2021 FUZZ-IEEE

The shortest Euclidean distance method finds the training data with the shortest Euclidean distance from the test time series and classifies the test time series into the detected training data class.

However, this method requires calculating the Euclidean distance between all event values in the test time series and all event values in all training data time series, which results in a huge amount of calculations if the number of training data time series and the number of event values in each time series are large. Furthermore, since the method detects training data with N event values that are most similar to the event values of the N timestamps (the aforementioned 10) in the test time series, classification accuracy is not high. This is because this shortest Euclidean distance method does not take into account the distribution of event values across multiple time series in the training data.

Furthermore, machine learning has black box problems, where it cannot explain why a particular classification was decided, and it requires a huge number of parameters, long calculation times, and is expensive.

Traditional time series classification methods do not take into account the fuzzy nature of event values within a time series. That is, multiple time series belonging to each class have different event values at each timestamp, and the different event values at each timestamp are values within a predetermined range or distribution. In traditional shortest Euclidean distance methods, training data time series have a single event value at each timestamp. This limits the accuracy of time series classifiers.

The purpose of the first aspect of this embodiment is to provide a time series classification device, a time series classification program, and a time series classification method that perform classification with high accuracy using a low-cost calculation method with a small amount of calculation.

A first aspect of this embodiment includes a memory and a processor that accesses the memory,
The processor:
(1) Dividing actual training time series data into classes, each of which has multiple time series labeled with a class;
(2) compressing the actual training time series data of each class, each having a plurality of time series for each of the divided classes, into representative training time series data for each class, each having a minimum value time series, a maximum value time series, and a representative value time series, each having a minimum value, a maximum value, and a representative value between the minimum and maximum values of the event values of each timestamp of the plurality of time series;
(3) calculating a plurality of fuzzy membership values (hereinafter referred to as FMS values) for each of the event values of the plurality of timestamps of the test time series to be classified, for each class, based on the representative training time series data of each class;
(4) classifying the class having the smallest average value of the FMS values of the plurality of timestamps as the class of the test time series;
In the process (3), the event value of the test time series is
If the maximum FMS value is less than or equal to the event value of the minimum value time series or greater than or equal to the event value of the maximum value time series,
When the event value of the representative value time series is equal to the minimum FMS value,
When the event value of the test time series is between the minimum value time series and the representative value time series, a second FMS value that decreases from a first FMS value between the maximum FMS value and the minimum FMS value to a minimum FMS value in response to an increase in the event value of the test time series,
a fourth FMS value that increases from the minimum FMS value to a third FMS value between the minimum FMS value and the maximum FMS value in response to an increase in the event value of the test time series when the event value is between the event value of the representative value time series and the event value of the maximum value time series;
The time series classifier calculates the FMS values of the event values of the test time series.

According to the first aspect, time series classification can be performed with low computational complexity, low cost, and high accuracy.

1 is a diagram illustrating a configuration of a time series classification device according to an embodiment of the present invention. FIG. 10 is a diagram showing actual training time series data TR_TSDB (CL=2) associated with class label CL=2 and test data time series data TST_TSDB. FIG. 10 is a diagram showing actual training time series data TR_TSDB (CL=1) associated with class label CL=1 and test data time series data TST_TSDB. FIG. 3 is a diagram showing a graph plotting the time series ts1 to ts8 of class CL2 in FIG. 2 and the test time series tts17. FIG. 4 is a diagram showing a graph in which the time series data ts9 to ts16 of the class CL1 in FIG. 3 and the test time series tts17 are plotted. FIG. 10 is a flowchart illustrating a method for classifying test time series of test data by the time series classification device according to the present embodiment. FIG. 10 is a flowchart illustrating a first example of a process S2 for generating representative training time-series data RP_TSDB. FIG. 10 is a flowchart showing processing S3. FIG. ₁₀ is a diagram showing an example of the time series of representative training time series data RP_TSDB2 and the test time series tts17 of class 2 ( _cl2 ). FIG. ₁₀ is a diagram showing an example of the time series of representative training time series data RP_TSDB1 and test time series tts17 of class 1 (cl ₁ ). FIG. 1 is a diagram illustrating a first example of an FMS function μ. FIG. 10 is a diagram showing an FMS function μ that calculates an FMS value when α and Δ given by the user are α=0.5 and Δ=0.1. This is a graph plotting the test time series ts17 and five time series ts_min_2, ts_β_2, ts_mean_2, ts_Γ_2, ts_max_2 of the representative training time series data for class CL=2. This is a graph plotting the test time series ts17 and five time series ts_min_2, ts_β_2, ts_mean_2, ts_Γ_2, ts_max_2 of the representative training time series data for class CL=1. FIG. 10 is a flowchart illustrating a second example of a method for generating representative training time-series data RP_TSDB. FIG. 16 is a diagram showing an FMS function μ in the second example of FIG. 15 .

Figure 1 shows the configuration of a time series classification device in this embodiment. The time series classification device 1 is a computer such as a server, client terminal, personal computer, tablet terminal, or smartphone. The time series classification device 1 has a processor 10, main memory 12, a network interface 14, storages 20-26, and a bus 28 connecting them. The storage stores a time series classification program 20, actual training time series data 22, representative training time series data 24 generated from the actual training time series data for each class, and test time series data 26 to be classified. The network interface 14 can be connected to multiple client terminal devices 30, 32 via a network NW.

The time series classification program 20 is deployed in the main memory 12 and executed by the processor 10. By executing the time series classification program 20, the processor 10 generates representative training time series data 24 from the actual training time series data 22 and classifies each test time series in the test time series data 26.

A univariate time series ts _id is a collection of event values occurring in a certain time interval in order. That is, the time series ts _id is expressed as follows:
ts _id ={v ₁ , v ₂ , ... v _c }
Here, v _p (1≦p≦c) represents the event value at timestamp p. The length of the time series |ts _id | represents the total number c of event values v _p .

The time series data TSDB is a collection of multiple time series, namely:
TSDB={ts ₁ , ts ₂ , ... ts _k }, k≧1
The size of the time series data |TSDB| is the total number k of time series ts _ids in the time series data TSDB. |TSDB|=k

Below, CL is a set of classification labels (class labels), and n is the number of classes.
CL={CL ₁ , CL ₂ , ... CL _n }, n≧1

In time series classification, each time series ts _id , which is an element of the time series data TSDB, is associated with a classification label (class label) clk or cl _k (1≦k≦n).

Figure 2 shows actual training time series data TR_TSDB(CL=2) associated with class label CL=2, and test data time series data TST_TSDB. Figure 3 shows actual training time series data TR_TSDB(CL=1) associated with class label CL=1, and test data time series data TST_TSDB. The training time series data TR_TSDB(CL=2) and TR_TSDB(CL=1) in Figures 2 and 3 are the actual training time series data TR_TSDB in Figure 1, and each contain eight time series, ts1-ts8 and ts9-ts16. Each time series, ts, is assigned a time series ID of 1 to 16. The test data time series data TST_TSDB in Figures 2 and 3 shows only one test time series, tts17.

The first time series TS1 in the training time series data TR_TSDB (CL=2) in FIG. 2 is as follows:
ts1: {10,9,8,8,7,6.9,6,6,4,3.8}:2
Here, ts1 is a time series, and {10,9,8,8,7,6.9,6,6,4,3.8} is a sequence of event values in ascending timestamp order. The size of this time series is |ts _id |=|{10,9,8,8,7,6.9,6,6,4,3.8}|=10. In other words, the first time series in Figure 2 contains 10 event values. The same applies to the other time series ts2 to ts16 and the test time series tts17. Furthermore, the size of the training time series data TR_TSDB(CL=2) and TR_TSDB(CL=1) is |TSDB|=16, and the set of class labels is CL={1,2}.

Figure 4 is a graph plotting the time series ts1 to ts8 and the test time series tts17 for class CL2 in Figure 2. Figure 5 is a graph plotting the time series data ts9 to ts16 and the test time series tts17 for class CL1 in Figure 3. In both Figures 4 and 5, the horizontal axis corresponds to timestamps 1 to 10, and the vertical axis corresponds to the event value of each timestamp. The test time series tts17 of the test data is shown with a dashed line, and the time series ts1 to ts16 of the training data is shown with a solid line. The time series ts1 to ts8 (solid line) of the training time series data for class label CL2 in Figure 4 and the time series ts9 to ts16 (solid line) of the training time series data for class label CL1 in Figure 5 appear in clearly different regions when plotted on a graph. As shown in Figures 4 and 5, it can be visually confirmed that the test time series tts17 (dashed line) of the test data is similar to the time series ts1 to ts8 (solid lines) of the training time series data for class label CL2.

However, in the real world, the number of training time series that make up a time series classification model is enormous, and the number of class labels is also large. Furthermore, it is expected that the range of event values in the time series of training time series data that belong to each class label will be approximated in a complex manner.

As mentioned above, conventional shortest Euclidean distance methods require calculating the Euclidean distance between every event value in the test time series of the test data and every event value in every time series of the training time series data. Therefore, if the number of time series in the training time series data and the number of event values in each time series are large, the amount of calculation required becomes enormous.

Furthermore, since the training time series with the N event values most similar to the event values of the N timestamps (the aforementioned 10) in the test time series of the test data is detected, the classification accuracy is not high. This is because the shortest Euclidean distance method does not take into account the distribution of event values in the training time series data. For example, in Figure 4, one time series in the training time series data has event values that are significantly different from the event values in the other time series. In this case, the sum or average Euclidean distance of all event values may be very large based on the event values in the test time series that deviate significantly from the distribution of the training time series data, which may result in incorrect classification.

Figure 6 is a flowchart showing a method for classifying test time series of test data using a time series classification device in this embodiment. The processor shown in Figure 1 executes the time series classification program 20 to perform the following processing.

That is, the processor 10 acquires actual training time series data TR_TSDB classified into multiple classes (S1). The actual training time series data TR_TSDB is, for example, the time series data TR_TSDB(CL=2) and TR_TSDB(CL=1) shown in Figures 2 and 3. The actual training time series data TR_TSDB is a collection of actually acquired time series, and is training time series data for a time series classification model.

Next, the processor 10 compresses (converts) the actual training time series data TR_TSDB for each class into representative training time series data RP_TSDB for each class (S2). The representative training time series data RP_TSDB is time series data that contains the minimum value min, first percentile β, representative value (mean, median, mode, midrange, etc.), second percentile Γ, and maximum value max of the event values at timestamps of the multiple time series included in the actual training time series data TR_TSDB for each class. The minimum value, first percentile, representative value, second percentile, and maximum value represent the distribution of event values at each timestamp of the multiple training time series. Details will be provided below.

Then, for the test time series in the test time series data TST_TSDB, the processor 10 calculates fuzzy membership values (hereinafter referred to as FMS values) for the event values of the test time series based on the representative training time series data for each of the multiple classes (S3). That is, for each event value of the test time series, the same number of FMS values as the number of classes are calculated. In process S3, the average value of the FMS values for each event value of the test time series is further calculated for each class as the FMS distance FMSD.

Specifically, the fuzzy membership values FMS_V are assigned to values below the minimum, minimum, first percentile, representative value, second percentile, maximum, and above the maximum of the representative training time series data. For example, the maximum FMS value, FMS_V=1.0, is assigned to values below the minimum and above the maximum; the minimum FMS value, FMS_V=0, is assigned to the representative value; the first FMS value between the maximum and minimum FMS values, FMS_V=α=0.5, is assigned to the minimum; and the second FMS value between the maximum and minimum FMS values, FMS_V=Δ=0.5, is assigned to the maximum.

The FMS value FMS_V is preferably a normalized value between 0 and 1.0, but it is sufficient if the representative value FMS_V is the minimum FMS value, the FMS_V below the minimum value and above the maximum value is the maximum FMS value, and the minimum and maximum values FMS_V are values between the minimum and maximum FMS values. Details are explained in Figures 9 and 10, etc. Then, the FMS value FMS_V for the event value of the test time series is calculated based on the representative training time series data and the assigned FMS value. Details are explained in Figure 8.

Then, processor 10 determines the class with the smallest average FMS value for the test time series as the class of the test time series (S4). The FMS value is a value that takes into account the distribution of event values at each timestamp. Therefore, the method for determining the class with the smallest average FMS value takes into account the fuzzy nature of the actual training time series data.

Figure 7 is a flowchart of a first example of the process S2 for generating representative training time series data RP_TSDB. The processor 10 of the time series classification device executes the time series classification program 20 and performs the following process S2 for generating representative training time series data RP_TSDB.

The processor 10 acquires the actual training time series data TR_TSDB (S21). Then, the processor performs the following steps S23-S25 on the actual training time series data TR_TSDB for each class (S22-S26).

The actual training time series data TR_TSDB for a certain class includes multiple time series ts. For the multiple time series ts for a certain class, the processor calculates the minimum value min, the first percentile β, and a representative value (such as the mean, median, mode, or midrange) of the event value v at each timestamp, such as the mean value mean, second percentile Γ, and maximum value max (S23-S25). The mean value mean may be any representative value. In this embodiment, the mean value mean is used as an example of a representative value. Processes S23-S25 are performed for the actual training time series data for all classes. As a result, the minimum value, first percentile, mean value, second percentile, and maximum value of the event values at each timestamp of the time series included in the actual training time series data TR_TSDB for all classes are calculated.

To be more specific, the actual training time series data of each class clk in the actual training time series data TR_TSDB is assumed to be TSDB _clk . The following δ is assumed to be a statistical parameter specified by the user.
δ＝{minimum, β-percentile, mean, Γ-percentile, maximum}
The processor executes step S24 to calculate the statistical parameter δ of each class.

The processor uses the statistical parameter δ of each class to compress (or convert) the actual training time series data TSDB _clk of each class _clk , which contains a huge number of time series ts, into a small set of representative training time series data RP_TSDB (^TSDB _clk (^ is the symbol above TSDB _clk )).
＾TSDB _clk = {ts ^min _clk , ts ^β _clk , ts ^mean _clk , ts ^Γ _clk , ts ^max _clk }
The above elements ts ^min _clk , ts ^β _clk , ts ^mean _clk , ts ^Γ _clk , and ts ^max _clk represent the minimum, β-percentile, mean, Γ-percentile, and max for each event or timestamp calculated from the time series data of class _clk , respectively.

The formula for compressing (or converting) the actual training time series data TSDB _clk of class _clk to the representative training time series data ^TSDB _clk is as follows:

Here, _{ts_id.v_i} represents the event value _{v_i} at timestamp i of _the time series _{ts_id} . The first percentile β-percentile and the second percentile Γ-percentile are percentiles provided by the user. The user sets the first and second percentiles based on the distribution of event values. Equation (1) means that the minimum time series ts_min_clk is the collection of the minimum event values at timestamp i of all time series _{ts_id} belonging to the actual training time series data _{TSDB_clk} of class _clk , for all timestamps i=1 to i=| _{ts_id} |. The same applies to the other equations (2) to (5).

Fig. 9 is a diagram showing an example of the time series of representative training time series data _{RP_TSDB2} for class 2 ( _cl2 ) and the test time series tts17. Fig. 10 is a diagram showing an example of the time series of representative training time series data _{RP_TSDB1} for class 1 ( _cl1 ) and the test time series tts17. These two representative training time series data are calculated from the actual training time series data TR_TSDB (CL=2) for class 2 and the actual training time series data TR_TSDB (CL=1) for class 1 in Figs. 2 and 3, respectively.

Note that the time series {ts_min_2, ts_β_2, ts_mean_2, ts_Γ_2, ts_max_2} in Fig. 9 corresponds to {ts ^min _clk , ts ^β _clk , ts ^mean _clk , ts ^Γ _clk , ts ^max _clk } of class clk=cl _2. The same applies to the time series {ts_min_1, ts_β_1, ts_mean_1, ts_Γ_1, ts_max_1} in Fig. 10.

For example, the event value of 9.5 at timestamp 1 in time series ts_min_2 in Figure 9 is the minimum value of the event value at timestamp 1 in the eight time series ts1 to ts8 in the actual training time series data TR_TSDB (CL=2) in Figure 2. The same is true for the other timestamps 2 to 10. Furthermore, the event values at timestamps 2 to 10 in time series ts_β_2, ts_mean_2, ts_Γ_2, and ts_max_2 in Figure 9 are also the β percentile, mean, Γ percentile, and maximum value, respectively, of the event values at timestamps 2 to 10 in the eight time series ts1 to ts8 in the actual training time series data TR_TSDB (CL=2) in Figure 2.

The 10 event values of the time series {ts_min_1, ts_β_1, ts_mean_1, ts_Γ_1, ts_max_1} in Figure 10 are similarly calculated from the event values of timestamps 1 to 10 of the eight time series ts9 to ts16 in the actual training time series data TR_TSDB (CL=1) in Figure 2.

FIG. 8 is a flowchart of step S3. In step S3, the processor calculates fuzzy membership values for the event values of the test time series based on the representative training time series data. That is, the processor 10 first acquires the test time series tts in the test time series data TST_TSDB (S31). Then, for the representative training time series data RP_TSDB for each class _clk (S32-S37), the processor calculates FMS values FMS_V for the event values of each timestamp 1-10 in the test time series based on the event values of each time series ts_min_clk to ts_max_clk in the representative training time series data (S33-S35).

Furthermore, the processor calculates the average value of the FMS values for the event values at each timestamp in the test time series (S36). This average value of the FMS values is the FMS distance (fuzzy membership distance) of the test time series to the representative training time series data of each class. The processor calculates the FMS distance between the test time series and the representative training time series data RP_TSDB of each class CL (S36, S37). Then, as shown in process S4 in Figure 6, the processor determines the class with the smallest average FMS value (FMS distance) as the class of the test time series tts (S4).

In step S34 of Figure 8, the processor calculates the FMS value of the event value at each timestamp in the test time series by interpolating the FMS values previously assigned to each time series ts_min_clk, ts_β_clk, ts_mean_clk, ts_Γ_clk, and ts_max_clk of the representative training time series data.

Specifically, let tts _id be the test time series for which class cl _k (1≦k≦n) needs to be estimated. The FMS function μ that determines the distance (FMS value) between the event value of the test time series tts _id and the distribution of multiple event values in the representative training time series data RP_TSDB is given by

Here, the five FMS values μ _a = 1, α, 0, Δ, 1 are the FMS values FMS_V for (1) the event value tts _id .v _a below the time series ts_min_clk of the representative training time series data RP_TSDB, (2) the event value tts _id .v _a between ts_min_clk and ts_β_clk, (3) the event value tts _id .v _a of ts_mean_clk, (4) the event value tts _id .v _a between ts_Γ_clk and ts_max_clk, and (5) the event value tts _id .v _a above ts_max_clk. Coefficient A is a coefficient of an interpolation operation that calculates an FMS value when the event value _{tts_id.v a} of the test time series _{tts_id} is between the event values ts_β_clk.v _a and ts_max_clk.v _a of the representative training time series data RP_TSDB. Similarly, coefficient B is a coefficient of an interpolation operation that calculates an FMS value when the event value _{tts_id.v a} of the test time series _{tts_id} is between the event values ts_mean_clk.v _a and ts_Γ_clk.v _a of the representative training time series data RP_TSDB.

11 is a diagram showing a first example of the FMS function μ. The horizontal axis represents the event value _{ts_id.v i} of timestamp i of the time series _{ts_id} , and the vertical axis represents the FMS value (μ). The thick solid line in FIG. 11 indicates the FMS value FMS_V corresponding to the event value _{tts_id.v i} of the test time series _{tts_id} , which is less than or equal to the event value of the time series ts_min_clk of the representative training time series data RP_TSDB, to greater than or equal to the event value of the time series ts_max_clk.

The FMS function μ in FIG. 11 calculates the following FMS value μ _a according to the following seven cases (a) to (g) where the event value of the test time series tts _id is:
(a) If tts _id .v _a ≦ts_min_clk.v _a : μ _a =1
(b) If ts_min_clk.v _a <tts _id .v _a ≦ts_β_clk.v _a : μ _a =α
(c) If ts_β_clk.v _a <tts _id .v _a <ts_mean_clk.v _a : μ _a =α×A
(d) If tts _id .v _a =ts_mean_clk.v _a : μ _a =0
(e) If ts_mean_clk.v _a <tts _id .v _a <ts_Γ_clk.v _a : μ _a =Δ×B
(f) If ts_Γ_clk.v _a ≦tts _id .v _a <ts_max_clk.v _a : μ _a =Δ
(g) If tts _id .v _a ≧ts_max_clk.v _a : μ _a =1
A = (ts_mean_clk.v _a -tts _id .v _a )/(ts_mean_clk.v _a -ts_β_clk.v _a )
B = (tts _id .v _{a -} ts_mean_clk.v _a ) / (ts_Γ_clk.v _{a -} ts_mean_clk.v _a )
where 0≦α≦1, 0≦Δ≦1, a is a timestamp, and β and Γ are chosen from percentiles between 0 and 100.

In particular, in (b), if ts_min_clk.v _a < tts _id .v _a ≦ ts_β_clk.v _a , we can say that μ _a = α × A (A = 1). Therefore, we can say that the coefficient A, which decreases from FMS value = α to FMS value = 0 in response to an increase in the event value of the test time series between (b) and (c), changes from A = 1 to A = (ts_mean_clk.v _a - tts _id .v _a ) / (ts_mean_clk.v _a - ts_β_clk.v _a ).

Similarly, in (f), if ts_Γ_clk.v _a ≦ tts _id .v _a < ts_max_clk.v _a , then μ _a = Δ × B (B = 1). Therefore, the coefficient B, which increases from FMS value = 0 to FMS value = Δ in response to an increase in the event value of the test time series in (f) and (e), changes from B = (tts _id .v _a - ts_mean_clk.v _a ) / (ts_Γ_clk.v _a - ts_mean_clk.v _a ) to B = 1.

The basic idea behind the above FMS function is as follows. First, as in (a) and (g), if the event value at a certain timestamp in the test time series is less than the minimum or greater than the maximum event value in the time series for a certain class, the FMS value μ is assigned a value of 1. Second, if this is not the case (if it is between the minimum and maximum values, as in (b) to (f)), the FMS value μ is assigned values α×A and Δ×B, which correspond to α and Δ between 0 and 1, respectively, depending on the proximity of the event value in the representative training time series to the mean value. If the event value in the test time series cannot be predicted and the event value in the test time series is significantly smaller than the minimum or significantly larger than the maximum value in the representative training time series data (as in (a) or (g)), this prevents the FMS value from becoming extremely large. In other words, classification into an inappropriate class due to noise in the event value in the test time series is suppressed.

Second, when the event value of the test time series is between the minimum value min and the first percentile β of the representative training time series data, and between the second percentile Γ and the maximum value max (cases (b) and (f)), these correspond to the extreme values (extreme values) of the distribution of event values at each timestamp of the actual training time series data. Therefore, as in (b) and (f), the FMS value μ for extreme values becomes a constant value α or Δ. As a result, when the event value of the test time series is between β and Γ, which is close to the mean value, which is the representative value of the distribution, but is not an extreme value, a smaller value is assigned to the FMS value μ. As a result, when the event value of the test time series is in a region close to the mean value of the distribution, the FMS distance becomes smaller, facilitating classification into an appropriate class.

12 is a diagram showing an FMS function μ for calculating the FMS value when the user-specified α and Δ are α=0.5 and Δ=0.1. An example of calculating the FMS value of the test time series tts17 based on the representative training time series data RP_TSDB2 of class CL= ₂ shown in FIG.
(1) The first event value of tts17 is 9.4. This value is smaller than ts_min_2=9.5, so μ ₁ =1.0
(2) The second event value of tts17 is 10.2. This value is equal to ts_Γ_2=10.2 (≒10.15) and μ ₂ =0.1
(3) The third event value of tts17 is 8.18. This value is between ts_β_2=8 and ts_mean_2=8.54, and μ ₃ =α×A=0.5×(8.54-8.18)/(8.54-8)=0.33
(4) The fourth event value of tts17 is 8.3. This value is between ts_mean_2=7.9 and ts_Γ_2=8.46, and μ ₄ = Δ×B=0.1×(8.3-7.9)/(8.46-7.9)=0.07
(5) Repeat the same process to calculate the FMS values of the remaining event values of tts17, and μ ₅ to μ ₁₀ become 0.28, 1, 0.08, 0.19, 0.3, and 0.38.

After calculating the FMS values _μ1 to _μ10 for each timestamp of the test time series tts17 based on the representative training time series data of class 2, the processor calculates the fuzzy membership distance FMSD (S4 in FIG. 6). Specifically, the FMS distance FMSD is the average value of the FMS values obtained by dividing the sum of the FMS values _μ1 to _μ10 by the number of timestamps. In the above example, the FMS distance between the test time series tts17 and the representative training time series data of class 2 is FMSD = 0.849.

Similarly, the processor calculates the FMS values μ ₁ to μ ₁₀ for each timestamp of the test time series tts17 based on the representative training time series data of class 1, and calculates the average value.

The processor then calculates the FMS distance FMSD of the test time series tts17 based on the representative training time series data of all remaining classes. The FMS distance between the test time series tts17 and the representative training time series data of class _clk is normalized to a value between 0 and 1. The closer the FMS distance is to 0, the closer the test time series is to that class, and the closer the FMS distance is to 1, the farther the test time series is from that class. Therefore, the processor determines the class corresponding to the smallest FMS distance FMSD as the class to which the test time series tts17 belongs (S4 in FIG. 6).

The FSM value α for the event value ts_min_clk.va of the minimum time series of representative training time series data and the FSM value Δ for the event value ts_max_clk.va of the maximum time series are selected by the user. For example, the FSM values α and Δ may be selected to obtain the highest accuracy by repeatedly performing the evaluation process of the time series classification method. Optimal values for the first percentile β and second percentile Γ may also be selected in a similar manner.

Figure 13 is a graph plotting the test time series tts17 and the five time series ts_min_2, ts_β_2, ts_mean_2, ts_Γ_2, and ts_max_2 of the representative training time series data for class CL=2. In contrast, Figure 14 is a graph plotting the test time series tts17 and the five time series ts_min_2, ts_β_2, ts_mean_2, ts_Γ_2, and ts_max_2 of the representative training time series data for class CL=1.

In Figure 13, the event values at each timestamp of the dashed test time series tts17 are within the distribution at each timestamp of the five time series ts_min_2, ts_β_2, ts_mean_2, ts_Γ_2, and ts_max_2 of the representative training time series data for class CL=2, and are close to the event values of the average time series ts_mean_2 at many timestamps. On the other hand, in Figure 14, many of the event values at each timestamp of the dashed test time series tts17 are outside the distribution of the five time series of the representative training time series data for class CL=1. In the example above, when plotted on a graph, it is relatively easy to determine that the test time series tts17 belongs to class 2 rather than class 1.

Figure 15 is a flowchart of a second example of a method for generating representative training time series data RP_TSDB. The flowchart in Figure 15 differs from the flowchart in the first example of Figure 7 in step S24_2. All other steps are the same. For multiple time series ts of a certain classification, the processor calculates the minimum value min of the event value v at each timestamp, and among representative values (mean, median, mode, midrange, etc.), for example, the mean value mean and the maximum value max (S23-S25). The mean value mean can be any representative value. In other words, in the second example of Figure 15, the first percentile β and second percentile Γ of the first example of Figure 7 are not calculated.

Figure 16 shows the FMS function μ in the second example of Figure 15. As in Figure 11, the horizontal axis represents the event value tsid.vi at timestamp i of the time series tsid, and the vertical axis represents the FMS value (= μ).

The FMS function μ in FIG. 16 calculates the following FMS value μ _a according to the following five cases of the event value tts _{id.v a} of the test time series tts _id :
(a) If tts _id .v _a ≦ts_min_clk.v _a : μ _a =1
(c) If ts_min_clk.v _a <tts _id .v _a <ts_mean_clk.v _a : μ _a =α×A
(d) If tts _id .v _a =ts_mean_clk.v _a : μ _a =0
(e) If ts_mean_clk.v _a <tts _id .v _a <ts_max_clk.v _a : μ _a =Δ×B
(g) If tts _id .v _a ≧ts_max_clk.v _a : μ _a =1
A = (ts_mean_clk.va _{-ttsid.v a} ) / (ts_mean_clk.va -ts_min_clk.v _a )
B=(ttsid.v _a -ts_mean_clk.v _a )/(ts_max_clk.va -ts_mean_clk.v _a )

(c) in Figure 16 corresponds to (b) and (c) in Figure 11, and (e) in Figure 16 corresponds to (e) and (f) in Figure 11. In the second example in Figure 16, coefficients A and B remain unchanged.

The FMS function shown in Figure 11 is a function for a normal distribution in which the distribution of event values for multiple time series ts in a certain class has extreme values on the minimum and maximum sides. A normal distribution is a distribution in which the bin with the highest frequency is located in the center.

The FSM function shown in Figure 12 is a function for a skewed distribution of event values for multiple time series ts in a certain class. A skewed distribution is a distribution in which bins with high frequencies are positioned off-center. The example in Figure 12 is an FSM function suitable for a skewed distribution in which bins with high frequencies are biased toward the maximum value.

Furthermore, the FMS function shown in Figure 16 is a function suitable for a normal distribution in which the distribution of event values for multiple time series ts in a certain class does not have extreme values on the minimum or maximum side. Because there are no extreme values on either end of the distribution, this FMS function does not perform calculations such as Figures 11 and 12, where the FMS value is α between the minimum value min and the first percentile β, or Δ between the second percentile Γ and the maximum value max. The FMS functions shown in Figures 11 and 12 are suitable for distributions with extreme values on both ends of the distribution.

The fuzzy nearest neighbor classification method (Fuzzy NNC) for time series in this embodiment determines the class of a test time series using representative training time series data RP_TSDB for each class, which is converted from the actual training time series data TR_TSDB for each class. Therefore, the computational complexity of the fuzzy nearest neighbor classification method is on the order of the number of classes n (O(n)). In contrast, the computational complexity of other time series classification methods is on the order of the number of training time series m (O(m)). Because the number of time series m in real-world time series data is far greater than the number of classes n, the fuzzy nearest neighbor classification method is preferable to other time series classification methods in terms of memory capacity, runtime time, and energy consumption.

The fuzzy nearest neighbor classification method in this embodiment has the following two stages. The first stage is an offline stage in which the processor compresses the actual training time series data TR_TSDB for each given class into representative training time series data RP_TSDB for that class. The second stage is an online stage in which the processor calculates the FMS distance between the test time series and the representative training time series data for each class. The processor then determines the class with the smallest FMS distance as the class of the test time series.

As described above, this embodiment enables test time series to be classified with high accuracy, using a small amount of memory, a short runtime, and low power consumption.

1: Time series classification device 20: Time series classification program 22, TR_TSDB: Actual training time series data 24, RP_TSDB: Representative training time series data 26, TST_TSDB: Test data time series data
tsid, ts _id : time series
TSDB: Time Series Data
min: minimum value β: 1st percentile
mean: average value (an example of a representative value)
Γ: 2nd percentile
max: maximum value
FMS_V: Fuzzy membership value
FMSD: Fuzzy Membership Distance
clk, cl _k : class, classification

Claims (6)

Memory and
a processor accessing the memory;
The processor:
(1) Dividing actual training time series data into classes, each of which has multiple time series labeled with a class;
(2) compressing the actual training time series data of each class, each having a plurality of time series for each of the divided classes, into representative training time series data for each class, each having a minimum value time series, a maximum value time series, and a representative value time series, each having a minimum value, a maximum value, and a representative value between the minimum and maximum values of the event values of each timestamp of the plurality of time series;
(3) calculating a plurality of fuzzy membership values (hereinafter referred to as FMS values) for each of the event values of the plurality of timestamps of the test time series to be classified, for each class, based on the representative training time series data of each class;
(4) classifying the class having the smallest average value of the FMS values of the plurality of timestamps as the class of the test time series;
In the process (3), the event value of the test time series is
If the maximum FMS value is less than or equal to the event value of the minimum value time series or greater than or equal to the event value of the maximum value time series,
When the event value of the representative value time series is equal to the minimum FMS value,
When the event value of the test time series is between the minimum value time series and the representative value time series, a second FMS value that decreases from a first FMS value between the maximum FMS value and the minimum FMS value to a minimum FMS value in response to an increase in the event value of the test time series,
a fourth FMS value that increases from the minimum FMS value to a third FMS value between the minimum FMS value and the maximum FMS value in response to an increase in the event value of the test time series when the event value is between the event value of the representative value time series and the event value of the maximum value time series;
A time series classifier that calculates FMS values for each of the event values of the test time series. a first coefficient for decreasing the second FMS value at a first percentile between the event value of the minimum value time series and the event value of the representative value time series;
The time series classification device according to claim 1 , wherein a second coefficient for increasing the fourth FMS value changes at a second percentile between the event value of the representative value time series and the event value of the maximum value time series. the factor by which the second FMS value between the minimum time series event value and the first percentile is reduced is 1;
3. The time series classifier of claim 2, wherein the factor by which the fourth FMS value between the second percentile and the maximum time series event value increases is one. A time series classification device according to any one of claims 1 to 3, wherein the representative value is one of the mean, median, mode, and midrange. (1) Dividing actual training time series data into classes, each of which has multiple time series labeled with a class;
(2) compressing the actual training time series data of each class, each having a plurality of time series for each of the divided classes, into representative training time series data for each class, each having a minimum value time series, a maximum value time series, and a representative value time series, each having a minimum value, a maximum value, and a representative value between the minimum and maximum values of the event values of each timestamp of the plurality of time series;
(3) calculating a plurality of fuzzy membership values (hereinafter referred to as FMS values) for each of the event values of the plurality of timestamps of the test time series to be classified, for each class, based on the representative training time series data of each class;
(4) classifying the class having the smallest average value of the FMS values of the plurality of timestamps as the class of the test time series;
In the process (3), the event value of the test time series is
If the maximum FMS value is less than or equal to the event value of the minimum value time series or greater than or equal to the event value of the maximum value time series,
When the event value of the representative value time series is equal to the minimum FMS value,
When the event value of the test time series is between the minimum value time series and the representative value time series, a second FMS value that decreases from a first FMS value between the maximum FMS value and the minimum FMS value to a minimum FMS value in response to an increase in the event value of the test time series,
a fourth FMS value that increases from the minimum FMS value to a third FMS value between the minimum FMS value and the maximum FMS value in response to an increase in the event value of the test time series when the event value is between the event value of the representative value time series and the event value of the maximum value time series;
Calculating FMS values for each of the event values of the test time series;
A time series classification program having program code for causing a computer to execute a process. (1) Dividing actual training time series data into classes, each of which has multiple time series labeled with a class;
(2) compressing the actual training time series data of each class, each having a plurality of time series for each of the divided classes, into representative training time series data for each class, each having a minimum value time series, a maximum value time series, and a representative value time series, each having a minimum value, a maximum value, and a representative value between the minimum and maximum values of the event values of each timestamp of the plurality of time series;
(3) calculating a plurality of fuzzy membership values (hereinafter referred to as FMS values) for each of the event values of the plurality of timestamps of the test time series to be classified, for each class, based on the representative training time series data of each class;
(4) classifying the class having the smallest average value of the FMS values of the plurality of timestamps as the class of the test time series;
In the process (3), the event value of the test time series is
If the maximum FMS value is less than or equal to the event value of the minimum value time series or greater than or equal to the event value of the maximum value time series,
When the event value of the representative value time series is equal to the minimum FMS value,
When the event value of the test time series is between the minimum value time series and the representative value time series, a second FMS value that decreases from a first FMS value between the maximum FMS value and the minimum FMS value to a minimum FMS value in response to an increase in the event value of the test time series,
a fourth FMS value that increases from the minimum FMS value to a third FMS value between the minimum FMS value and the maximum FMS value in response to an increase in the event value of the test time series when the event value is between the event value of the representative value time series and the event value of the maximum value time series;
Calculating FMS values for each of the event values of the test time series;
A time series classification method in which processing is performed by a processor.