Time-series feature extraction apparatus, time-series feature extraction method and recording medium

A time-series feature extraction apparatus has a coefficient outputter to output a coefficient to be used in calculation for classifying time series data into a plurality of segments, a segment position outputter to perform calculation for classifying the time series data into the plurality of segments based on the coefficient to output information on boundary positions of the plurality of segments, a cluster classifier to classify the plurality of segments into a certain number of plurality of clusters equal to or smaller than a certain number of the plurality of segments, a representative element outputter to output a representative element which represents a local feature of each of the plurality of clusters and is set for each of the plurality of segments, a feature degree calculator to calculate a feature degree of the representative element, and a representative element updater to update the representative element based on the feature degree.

CROSS REFERENCE TO RELATED APPLICATIONS

This application is based upon and claims the benefit of priority from the prior Japanese Patent Application No. 2018-206777, filed on Nov. 1, 2018, the entire contents of which are incorporated herein by reference.

FIELD

Embodiments of the present disclosure relate to a time-series feature extraction apparatus, a time-series feature extraction method and a recording medium.

BACKGROUND

Since various data can be obtained with advancement of IoT, an environment in which the conditions of various infrastructure equipment, production apparatuses, etc. can be captured in real time has been gradually developed. Since obtainable data include various kinds of data, the process of extracting a feature value of each data is often required as preprocessing.

However, it is difficult to extract the feature value in the case where there is no knowledge of each data and the characteristics of each data are not known. There are two methods, as follows, for dealing with such a case.

If data to be obtained is time series data, the first method is to divide the time series data into segments. According to this method, a global feature of the data can be extracted using correlation analysis, regression, etc. The second method is to extract a local feature of the time series data by picking up distinctive partial data of the time series data.

In the case of time series data, it largely depends on time and situation which of the global feature and local feature is better to extract, and hence, it is required to determine an appropriate method of preprocessing for each time series data. Moreover, when data carries a noise, both of the global and local features may not be correctly extracted.

There is a method, which has been proposed, to divide time series data into clusters with some sort of technique and to extract partial data that is a local feature, for each cluster. However, when the clusters include similar data, extracted partial data are also similar to one another, resulting in that the local feature cannot be correctly extracted.

DETAILED DESCRIPTION

According to one embodiment, a time-series feature extraction apparatus has:

a coefficient outputter to output a coefficient to be used in classifying time series data into a plurality of segments;

a segment position outputter to classify the time series data into the plurality of segments based on the coefficient to output information on boundary positions of the plurality of segments;

a cluster classifier to classify the plurality of segments into a certain number of plurality of clusters equal to or smaller than a certain number of the plurality of segments;

a representative element outputter to output a representative element which represents a local feature of each of the plurality of clusters and is set for each of the plurality of segments;

a feature degree calculator to calculate a feature degree of the representative element; and

a representative element updater to update the representative element based on the feature degree.

Hereinafter, embodiments of the present disclosure will now be explained with reference to the accompanying drawings. In the following embodiments, a unique configuration and operation of a time-series feature extraction apparatus will be mainly explained. However, the time-series feature extraction apparatus may have other configurations and operations omitted in the following explanation.

First Embodiment

FIG.1is a schematic block diagram showing the configuration of a time-series feature extraction apparatus1according to a first embodiment. The time-series feature extraction apparatus1ofFIG.1has a feature capable of correctly extracting a global feature and a local feature of time series data. To the time-series feature extraction apparatus1ofFIG.1, one or plural kinds of time series data are input. Accordingly, the time-series feature extraction apparatus1ofFIG.1is capable of accepting the input of multivariate time-series data composed of plural kinds of time series data.

The time-series feature extraction apparatus1ofFIG.1is provided with a coefficient outputter2, a segment position outputter3, a cluster classifier4, a representative element outputter5, a feature degree calculator6, and a representative element updater7.

The coefficient outputter2outputs a coefficient to be used in calculation for classifying time series data into a plurality of segments. For example, when classifying the time series data into a plurality of segments using a regression model, the coefficient outputter2outputs a regression coefficient of the regression model.

The time series data to be input to the coefficient outputter2are output from a target data outputter8such as infrastructure equipment, a variety of production apparatuses, plants, etc. The target data outputter8may output plural kinds of time series data. The time series data output from the target data outputter8may be aligned in the order of time stamps by a data aligner9. The time series data aligned by the data aligner9may be stored once in a time series database (time series DB, hereinafter)10, and then the time series data output from the time series DB10may be input to the coefficient outputter2at a desired timing.

FIG.2is a figure showing one example of time series data output from the target data outputter8.FIG.2shows an example in which time series data are output from a sensor A and a sensor B. Each time series data has sensor data and recorded date and time, as a pair. The sensor data may be univariate data or multivariate data. The data output from the target data outputter8may be data for which preprocessing has been applied. The preprocessing may, for example, be a process of normalizing each time series data into 0 s and 1 s, a whitening process implemented with correlation between time series data in the case of multivariate data, a process of specifying the maximum or minimum value each sensor data can take, a frequency conversion process for each time series data, etc. In the time series DB10, sensor data per product, time series data at a predetermined time interval, etc. may be stored.FIG.3is a figure showing one example of time series data obtained after the time series data ofFIG.2are aligned by the data aligner9.

At the former stage side of the coefficient outputter2, a variable initializer11may be provided, as shown inFIG.1. The variable initializer11initializes various kinds of variables to be used in classifying time series data into a plurality of segments. When classifying the time series data into a plurality of segments using a regression model, the variable initializer11initializes various kinds of variables to be used in the regression model. The variable initializer11may perform initialization on segment positions, cluster allocation, etc. The initialization on cluster allocation may, for example, be performed based on k-means, mixed regularization distribution, etc. The initialization on segment positions may be performed to set the segments at a regular interval.

The coefficient output from the coefficient outputter2ofFIG.1is input to the segment position outputter3. The segment position outputter3classifies the time series data into a plurality of segments based on the coefficient output from the coefficient outputter2, to output information on boundary positions between the plurality of segments. For example, with the regression model using the regression coefficient output from the coefficient outputter2, the segment position outputter3performs fitting to the time series data. The regression model is provided for each of a plurality of clusters. Then, the segment position outputter3outputs boundary positions between the plurality of segments based on a regression model with which the most appropriate fitting result can be obtained.

The cluster classifier4classifies the plurality of segments into a plural number of clusters equal to or smaller than the number of the plurality of segments. By the cluster classifier4, each segment is assigned to any of the clusters. The details of segments and clusters will be described later.

The representative element outputter5outputs a representative element that expresses a local feature of each of the plurality of clusters and is set for each of the plurality of segments. The representative element is an indicator that expresses a local feature of each segment. The representative element outputter5may output a predetermined number of representative elements for each of the plurality of clusters.

The feature degree calculator6calculates a feature degree of representative elements. The feature degree is expressed, for example, with the difference between the representative elements. The feature degree calculator6may calculate the feature degree based on a similarity degree with time series data in a segment in which a representative element is present and a dissimilarity degree from time series data in a segment in which no representative element is present.

The representative element updater7updates the representative elements based on the feature degree calculated by the feature degree calculator6. The representative element updater7updates each representative element so that the difference between the representative elements of the segments becomes as large as possible. A larger difference between the representative elements indicates that the local feature is more noticeable.

The time-series feature extraction apparatus1ofFIG.1may be provided with a visualizer13. The visualizer13visualizes time series data input to the coefficient outputter2and a plurality of representative elements corresponding to a plurality of clusters, respectively, output from the representative element outputter5. The visualizer13may visualize time series data before being input to the coefficient outputter2and after subjected to noise component removal, and a plurality of representative elements corresponding to a plurality of clusters, respectively, output from the representative element outputter5. Visualization may, for example, be performed in such a manner that the input time series data, segment positions, and cluster allocation can be visually perceived on a screen of a display apparatus not shown. Examples of visualization will be described later.

The time-series feature extraction apparatus1ofFIG.1may be provided with a representative-element degree outputter14. The representative-element degree outputter14outputs a representative element degree obtained by converting a representative element into a numerical value. Examples of the representative element degree will also be described later.

The time-series feature extraction apparatus1ofFIG.1may be provided with a representative-element exclusion specifier15. The representative-element exclusion specifier15specifies partial data to be excluded by the representative element outputter5from a representative element, in a plurality of clusters. In this case, the representative element outputter5generates a representative element from time-series data except for the partial data specified by the representative-element exclusion specifier15, for each of the plurality of clusters.

The time-series feature extraction apparatus1ofFIG.1may be provided with a representative element specifier16. The representative element specifier16specifies partial data to be included by the representative element outputter5in a representative element, in a plurality of clusters. In this case, the representative element outputter5generates a representative element including the partial data specified by the representative element specifier16, for each of the plurality of clusters. For the representative element specifier16and the representative-element exclusion specifier15, a user may specify any part of a waveform that represents time series data, with a mouse or the like on a GUI window for visualization.

The time-series feature extraction apparatus1ofFIG.1may be provided with a representative element selector17. The representative element selector17selects remaining representative elements after excluding unnecessary representative elements from among the representative elements output from the representative element outputter5. In this case, the feature degree calculator6calculates the feature degree of the representative elements selected by the representative element selector17.

FIG.4is a figure showing one example of visualization by the visualizer13. InFIG.4, the abscissa is time and the ordinate is a sensor value of sensor data.FIG.4shows an example in which time series data is classified into eleven segments and then each segment is assigned to any of three clusters. InFIG.4, the three clusters are distinguished from one another with different hatching. In the example ofFIG.4, each segment is provided with one representative element in accordance with each cluster. Each representative element is indicated with a thick line. As shown inFIG.4, the number of clusters is equal to or smaller than the number of segments. The representative element is determined for each cluster. Representative elements in a plurality of segments belonging to the identical clusters have the identical waveform. The representative element is partial data having a distinctive waveform in time series data of each segment.

FIG.5is a flowchart showing a process performed by the time-series feature extraction apparatus1according to the first embodiment. The time-series feature extraction apparatus1ofFIG.1repeatedly performs the process of the flowchart ofFIG.5. First of all, various parameters are set in the components of the time-series feature extraction apparatus1ofFIG.1, from the parameter inputter12(step S1).

Subsequently, the variable initializer11initializes each variable of a regression model for classifying time series data into a plurality of segments (step S2). Moreover, the variable initializer11initializes the number of repetition k of the flowchart ofFIG.5to zero (step S3).

Subsequently, the coefficient outputter2calculates and outputs a regression coefficient for classifying time series data obtained from the time series DB10to a plurality of segments (step S4). In step S4, a regression coefficient of a regression model expressed, for example, by a linear regression equation shown in an equation (1), is output.
∥x(k)−x(Vk)θ∥2(1)

The equation (1) is a linear regression equation for regressing the value of the k-th time series data using time series data other than the k-th time series data.

Subsequently, using the regression model based on the regression coefficient, the segment position outputter3classifies the time series data into a plurality of segments and outputs boundary position information of each segment (step S5). The segment position outputter3outputs a segment boundary position that is most conformable in the case where regression is performed with the regression model based on the regression coefficient output from the coefficient outputter2.

The following equation (2) expresses a fitting error using linear regression in dividing the k-th time series x(k) of data having time stamps, the number of the time stamps being T, by a position u into two.
∥x(k)(1:u)−x(Vk)1:u)θA∥2+∥x(k)(u+1:T)−x(Vk)(u+1:T)θB∥2(2)

In the above-described step S5, a boundary position of each segment is calculated and output, so that, for example, the value of the equation (2) becomes minimum.

Subsequently, the cluster classifier4classifies the plurality of segments into a plural number of clusters equal to or smaller than the number of the plurality of segments (step S6). In more specifically, the cluster classifier4uses the data of each segment obtained by the segment position outputter3to perform cluster allocation of the segments, in accordance with a determination criterion of which regression coefficient gives a minimum error when regression is performed with the regression coefficient. The regression coefficient is provided for each cluster.

Subsequently, the representative element outputter5calculates and outputs a representative element that expresses a local feature of each of the plurality of clusters and is set for each segment (step S7). As for the representative element, for example, Shapelets may be used.

Subsequently, the feature degree calculator6calculates a difference (feature degree) between representative elements and updates the representative elements so that the difference becomes as large as possible (step S8). The feature degree calculator6calculates a difference between representative elements, for example, using an objective function indicated by the following equation (3).
Mindis(x1,y1)+Mindis(x2,y2)+|C−minds(x1,y2)|+|C−minds(x2,y1)|  (3)

In the equation (3), x1 and x2 are data of segments, respectively, y1 and y2 are representative elements of the segments, respectively, C is a large enough value, and mindis(A, B) is an error most conformable when two time series data A and B are shifted. In the equation (3), mindis(x1, y1) is a numeric value of the degree of conformity between time series data of a segment x1 and the representative element y1 that is part of the time series data of the segment x1, the smaller the better. In the same manner, mindis(x2, y2) is a numeric value of the degree of conformity between time series data of a segment x2 and the representative element y2 that is part of the time series data of the segment x2, the smaller the better. On the other hand, mindis(x1, y2) is a numeric value of the degree of conformity between the time series data of the segment x1 and the representative element y2 of the segment x2, the larger the better. Therefore, it is desirable for |C−mindis(x1, y2)| to be smaller as much as possible. Moreover, mindis(x2, y1) is a numeric value of the degree of conformity between the time series data of the segment x2 and the representative element y1 of the segment x1, the larger the better. Therefore, it is desirable for |C−mindis(x2, y1)| to be smaller as much as possible.

As described above, in step S8, the representative elements are updated so that addition of the terms in the equation (3) becomes as smaller as possible.

Subsequently, the variable k is incremented by 1 (step S9). It is then determined whether the number of repetition k is smaller than a threshold value K (step S10). If the number of repetition k is smaller than the threshold value K, step S4and the following steps are repeated. The process ofFIG.5ends when the number of repetition k becomes equal to the threshold value K.

In addition to perform the process of the flowchart ofFIG.5, the time-series feature extraction apparatus1may perform visualization to express each time series data in the form of a waveform as shown inFIG.4so that the segment boundary positions, cluster allocations, and representative elements can be visually perceived. Or, a representative element degree, which is obtained by converting a representative element into a numerical value based on, for example, the following equation (4), may be visualized.

The denominator in the equation (4) is a numeric value of the degree of conformity between time series data of a segment xi and a representative element yi in the segment xi. The numerator in the equation (4) is a numeric value of the degree of conformity between time series data of a segment xj and the representative element yi in the segment xi. Since, in the equation (4), it is desirable for the denominator to be smaller whereas it is desirable for the numerator to be larger, it is desirable for the representative element degree to be larger.

FIG.6is a figure showing one example of visualization of the representative element degree. Since the representative element is set for each cluster, inFIG.6, the representative element degree is converted into a numerical value for each cluster. The example ofFIG.6shows that the representative element is in better conformity in the cluster B than in the cluster A.

The coefficient outputter2in the time-series feature extraction apparatus1ofFIG.1outputs, for example, a regression coefficient, however, may output a coefficient other than regression coefficient, such as, a correlation coefficient that is each component of a correlation matrix. As the correlation matrix, for example, a variance-covariance matrix S shown in an equation (5) may be used.
log|Σ|+tr|Σ−1S|(5)

In the equation (5), Σ is a variable in the case where time series data is assumed to follow the multivariate normal distribution, and S is a variance-covariance matrix among variables of time series data X. When performing correlation analysis using a correlation matrix, in step S4ofFIG.5, the coefficient outputter2calculates and outputs a correlation coefficient for classifying time series data into a plurality of segments. In step S4ofFIG.5, the segment position outputter3uses a correlation matrix based on the correlation coefficient to classify the time series data into the plurality of segments, to output boundary position information of the segments.

As described above, in the first embodiment, in order to capture a global feature of time series data, the time series data is classified into a plurality of segments, cluster allocation of the segments is performed, the boundary position of each segment is adjusted using a regression model or the like, and cluster allocation is updated. Moreover, in order to capture a local feature of the time series data, representative elements provided for respective clusters are set for respective segments, and then the representative elements are updated so that the difference between the representative elements becomes as large as possible. According to the above, both of the global and local features of the time series data can be captured. In the present embodiment, since the global and local features of each time series data can be captured for multivariate time series data composed of a plurality of time series data, great many kinds of time series data can be efficiently processed.

Second Embodiment

A second embodiment is to remove a noise of time series, as preprocessing.

FIG.7is a block diagram schematically showing the configuration of a time-series feature extraction apparatus1according to the second embodiment. The time-series feature extraction apparatus1ofFIG.7is provided with a noise remover18, added to the configuration of the time-series feature extraction apparatus1ofFIG.1. The noise remover18is provided between the time series DB10and the variable initializer11. The noise remover18performs noise removal from time series data read out from the time series DB10. Although, the noise removing method does not matter, for example, principal component analysis (PCA) may be performed to extract a useful data component only. Or, a regularization term may be added to a regression equation or the like. A larger penalty is given by the regularization term as being more separated from a predetermined reference value. Or, noise-removed time series data may be obtained by regression from another time series data. The optimization method in this case may be ADMM (Alternating Direction Method of Multipliers) and the like. For example, by regression with the following equation (6), noise-removed time series data may be estimated.
{circumflex over (x)}(k)=x(Vk)θ  (6)

FIG.8is a figure showing waveforms of time series data obtained before and after the noise remover18performs noise removal from the time series data. InFIG.8, a waveform w1and a waveform w2indicate time series data obtained before and after noise removal, respectively. As shown, by performing noise removal, the shape of waveform can be smoothed.

As described above, in the second embodiment, the noise remover18is provided to classify time series data into a plurality of segments to perform cluster allocation, after a noise included in the time series data is removed. Therefore, segmentation and cluster allocation are not affected by the noise.

Third Embodiment

When plural kinds of time series data are input, with a time lag, to the time-series feature extraction apparatus1, it is not desirable to utilize segment boundary positions of one kind of time series data for segmentation of another kind of time series data, with no position adjustments. For example, when a sensor B starts detection five minutes after the detection staring time of a sensor A, it is desirable to adjust the time lag of five minutes for sensor data of the sensors A and B. Accordingly, a third embodiment is to perform segmentation and cluster allocation in view of the time lag between various kinds of time series data.

FIG.9is a block diagram schematically showing the configuration of a time-series feature extraction apparatus1according to the third embodiment. The time-series feature extraction apparatus1ofFIG.9is provided with a segment position adjuster19, added to the configuration of the time-series feature extraction apparatus1ofFIG.1. In accordance with the time lag between plural kinds of time series data to be input, the segment position adjuster19adjusts the boundary positions of a plurality of segments output from the segment position outputter3. The cluster classifier4classifies a plurality of segments, for which the boundary positions have been adjusted by the segment position adjuster19, into a plurality of clusters, for each of the plurality of time series data.

FIGS.10A and10Bare figures schematically showing the operation of the segment position adjuster19. When the sensor data of the sensors A and B are input, with a time lag, to the time-series feature extraction apparatus1, the sensor data are classified into segments of completely different waveforms when segmentation is performed with the time lag as it is, as shown inFIG.10A. Accordingly, as shown inFIG.10B, the segment position adjuster19shifts in time the segment boundary positions of the sensor data of the sensor B from the segment boundary positions of the sensor data of the sensor A, so that both sensor data can be classified into segments of similar waveforms.

FIG.11is a flowchart showing a process performed by the time-series feature extraction apparatus1ofFIG.9. Steps S21to S26are identical to steps S1to S6ofFIG.5, respectively. In step S27, variables i and j for adjusting a time lag between different time series data are initialized to1(step S27).

Subsequently, the segment position adjuster19compares the i-th time series data and the j-th time series data to adjust the segment boundary positions of the i-th and j-th time series data so that both time series data are most conformable with each other (step S28). Then, the variable j is incremented by 1 (step S29). It is then determined whether the variable j is smaller than the total number of variables j (step S30). If the variable j has not exceeded the total number, step S28is repeated. If it is determined in step30that the variable j is not smaller than the total number, the variable i is incremented by 1 (step S31). It is then determined whether the variable i is smaller than the total number of variables i (step S32). If the variable j has not exceeded the total number, step S28and the following steps are repeated. If it is determined in step32that the variable i has exceeded the total number, the processes identical to steps S7and S8are performed (step S33, S34). Next, the number of repetition k is incremented by 1 (step S35), it is determined whether the number of repetition k has reached a threshold value K (step S36). Step S24and the following steps are repeated until the number of repetition k has reached the threshold value K. If it is determined in step32that the variable i has reached the total number of variables i, the processes is completed.

As described above, in the third embodiment, since the segment position adjuster19is provided, even if plural kinds of time series data are input with time lags to the time-series feature extraction apparatus1, representative element calculation and updating can be performed after the time lag of each time series data is adjusted. Accordingly, change in segmentation and cluster allocation due to the time lag of time series data input to the time-series feature extraction apparatus1can be prevented.

At least part of the time-series feature extraction apparatus1explained in the above-described embodiments may be configured with hardware or software. When it is configured with software, a program that performs at least part of the time-series feature extraction apparatus1may be stored in a storage medium such as a flexible disk and CD-ROM, and then installed in a computer to run thereon. The storage medium may not be limited to a detachable one such as a magnetic disk and an optical disk but may be a standalone type such as a hard disk and a memory.

Moreover, a program that achieves the function of at least part of the time-series feature extraction apparatus1may be distributed via a communication network a (including wireless communication) such as the Internet. The program may also be distributed via an online network such as the Internet or a wireless network, or stored in a storage medium and distributed under the condition that the program is encrypted, modulated or compressed.