JP2013077194A - Information system device utilizing knowledge - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a general-purpose device configured to operate without using the knowledge of a user for performing new knowledge discovery with respect to time-sequential data to be analyzed by installing a function for outputting partial shapes for predicting the classification of the time-sequential data or its combination.SOLUTION: An information system device includes four functions, that are, a feature pattern discovery function, a classification rule extraction function, a classification prediction function, and a feature pattern improvement function. The shapes of time-sequential data as the features of each classification are discovered by the feature pattern discovery function, and a classification rule using the feature pattern is extracted by the classification rule extraction function. The shape of the feature pattern is improved by the feature pattern improvement function, and the classification rule whose quantity is high is extracted by using the improved pattern. The classification rule extracted in this way is utilized by inputting unclassified data, and the classification of the time-sequential data is predicted.

Description

The present invention relates to an information system apparatus for automatically discovering, accumulating and utilizing knowledge for predicting classification of time series data.

Data mining enables heuristic knowledge acquisition from a large amount of data in the database. The time-series data handled in the present invention is a sequence of numerical data recorded along with the passage of time, and aims to discover new knowledge by applying a data mining technique. In the real world, this type of data appears frequently in various fields, and by analyzing these data, it is expected to be able to predict fluctuations such as a sudden increase in precipitation, the occurrence of a large earthquake, and a fall in stock prices. It has become a theme.

Non-Patent Document 1 proposes an efficient frequent pattern finding method from time-series data, and this method uses the frequent pattern as a characteristic pattern. However, a method of simply extracting a frequent pattern is known to many analysts, or a common form is often extracted from any data, and an interesting pattern cannot often be found. The present invention aims to extract patterns for representing differences between data.

In non-patent document 2, analysis is performed by the user specifying a partial shape of time-series data to be extracted. By using the user's knowledge, it is possible to extract a pattern according to the interest of the analyst, but it takes a lot of trial and error to obtain a shape that the analyst does not imagine. Furthermore, it can be said that such a method that depends on background knowledge is difficult to use for a user without knowledge.

In Non-Patent Document 3, the attributes used for decision tree learning are extracted by clustering 18 kinds of indices attached to various stock price data with respect to the stock price data. Although it is thought that effective patterns for future prediction can be extracted from decision trees and training data created by this method, this method depends on the characteristics of stock prices and cannot be said to be a general-purpose analysis method. Unlike stock price data, it cannot be applied to time-series data that does not have many indicators such as temperature and humidity.

Agrawal, R. and Srikant, R .: Mining sequential patterns, in Data Engineering, 1995.Proceedings of the Eleventh International Conference on, pp. 3-14, IEEE (2002) Haigh, K., Foslien, W., and Guralnik, V .: Visula Query Language: Finding patterns in and relationships among time series data, in Proceedings of the seventh Workshop on Mining Scientific and Engineering Datasets, Citeseer (2004) Abe, H., Hirabayashi, S., Ohsaki, M., and Yamaguchi, T .: Evaluating a Trading Rule Mining Method based on Temporal Pattern Extraction, in The Third International Workshop on Mining Complex Data (MCD2007) In Conjunction with ECML / PKDD 2007, pp. 49-58 (2007)

The present invention has been made in view of the above-described problems of the prior art, and has a function of outputting partial shapes and combinations thereof for predicting classification of time series data, thereby using user knowledge. It is an object to provide a general-purpose device that operates without any problem and can discover new knowledge for time-series data to be analyzed.

The device first finds a feature pattern from the time series data. Obviously, shapes that appear frequently in time series data are important in analyzing the data, while shapes that appear widely across multiple categories are useless to identify them. The present invention applies TF * IDF to time-series data for the purpose of classifying time-series data in order to find a pattern that characterizes the classification.

TF * IDF is used in the field of text mining, and its value is evaluated as a statistical measure of word importance. One document is a set of words, and the database is a set of documents. The importance of a word increases as it appears frequently in one document, and decreases as the number of documents in which the word appears in the database increases. Usually, the word appearance frequency TF is the appearance probability of the word wi in the document tj. Words that appear in a particular document are more important than words that appear in all documents. This is called reverse document frequency, where N is the number of documents and n is the number of documents including at least one word wi, TF * IDF is defined by the following Equation 1.

The present invention extends this concept of TF * IDF and applies it to time series data. One time series data is regarded as one document, and a part of the time series data is called partial time series data and is considered as one word. At this time, if a fixed-length portion obtained simply from time-series data is simply extracted, the total number thereof becomes very large. Therefore, it is necessary to find a representative partial time-series data shape. For this purpose, the proposed device performs clustering on the extracted partial time series data. Although clustering of time series data is controversial, what if we can find some representative partial time series data or a shape that represents it from many extracted partial time series data? Such a method may be used and is not mentioned because it is not the essence of the present invention.

For clustering, k-means which is one of general methods is used. M clustering optimizes clustering criteria for the purpose of dividing a given data set into disjoint M subsets (clusters). The standard of clustering is the distance between each data x and the center (centroid) ci of the cluster which is a subset Xi including xi. When k centroids are c1,..., ck and D (p, q) is a function for calculating the distance between the data p and q, the clustering reference Err is defined by the following Equation 2.

The most widely used method for the distance function D (p, q) is Euclidean distance or its extension. FIG. 1 shows a correspondence example of two time-series data points for calculating the Euclidean distance. As shown in FIG. 1A, the Euclidean distance can be applied only to a pair of time-series data having the same length, and may cause a result contrary to human intuition. This is probably because humans can flexibly recognize the form of time-series data, but this method fixes the correspondence in the time direction.

Dynamic Time Warping (hereinafter DTW) flexibly associates two time-series data points and calculates distances that match human intuition. In order to calculate the optimum degree of similarity between time series data, the horizontal distance and the vertical axis are scaled to minimize the cumulative distance and appropriately correspond. FIG. 1B shows an example of this correspondence.

The DTW distance g (A, B) between the two time series data A and B having the lengths i and j is defined by the following Equation 3. A (i-1) and B (j-1) are sequences obtained by removing the last values of A (i) and B (j). In Equation 3, q and r are costs associated with the expansion / contraction of the sequence, and s is a cost due to mismatch of values. Similar pairs have small values, and two sequences that match exactly will be zero.

The classification rule is extracted using the feature pattern acquired by the feature finding function. Decision tree learning is used to extract classification rules. Decision tree learning is a type of supervised learning, in which a decision model with a tree structure with attributes as branches is created by inputting training data. An example of training data is shown in FIG. P1 to P3 are feature patterns discovered by the feature discovery function. S1 to S4 are subsequences in the database. The distance between all the sub-sequences and each feature pattern is calculated using the DTW and set as an attribute value. Each instance of training data is associated with a class label. One table with these distance and class label pairs is the training data. As a result of performing decision tree learning using this training data, knowledge as shown in FIG. 2D can be acquired.

When unclassified time-series data is input to the device after the decision tree learning, the classification is predicted according to the classification rule. The prediction is performed according to the following procedure.
1. The distance from all feature patterns used in the classification rule is calculated using DTW.
2. Let the root node of the classification rule be the survey node.
3. The survey node and the unclassified data are compared, and the next node is moved according to the condition indicated by the survey node.
4). When the movement destination is a branch, the current node is set as the investigation node, and the process is repeatedly executed from 3.
5. If it is a leaf, its class value is output.

The device has the capability to provide higher quality classification rules by improving the discovered feature patterns. There are several methods for improving the feature pattern, such as search methods such as hill-climbing and reinforcement learning such as Q-learning. However, simple search and reinforcement learning quickly fall into local solutions. It is necessary to avoid this. For this reason, in this study, improvements are made using genetic algorithms (GA). GA is a heuristic search algorithm based on the evolutionary idea of natural selection and heredity. The genetic algorithm is an effective method for obtaining an approximate solution from various and complex evaluation functions, and is applied to an optimization problem and a search problem. There is a technique to encode branches and leaves of decision trees as chromosomes and apply genetic operations such as intersection and mutation, but the present invention also has an important purpose of finding the shape of characteristic time-series data for prediction. is there. Therefore, we developed a technique to improve the quality of decision trees by improving the feature pattern. Finally, the apparatus outputs not only the learned decision tree but also the improved feature pattern used for it as a set.

The operation outline of the function for improving the feature pattern is as follows.
1. The pattern obtained by the feature extraction function is set as the initial feature pattern.
2. A decision tree is created using feature patterns.
3. Evaluate the created decision tree.
4). If the stop condition is satisfied, the created decision tree and the feature pattern used for it are output.
5. If the stop condition is not met, use GA to improve the feature pattern.
6). The process is repeated from 2 based on the improved feature pattern.

In the explanation of the method for improving the feature pattern using GA, first, the correspondence between the feature pattern and the chromosome in GA will be explained, and the evaluation, crossover, and mutation of the chromosome will be explained.

One chromosome corresponds to one feature pattern, and the manipulation of the chromosome is equivalent to the manipulation of the feature pattern. A sequence of values obtained by normalizing the numerical value of the feature pattern to the rate of change is defined as a chromosome. That is, an individual is a sequence C = (x1,... Xn) of length n composed of real values. FIG. 3 shows an example of a chromosome corresponding to one feature pattern. Since the gene to be handled is not a discrete variable but a real value, it is not a method of handling a simple bit string of 0 and 1, but gene improvement is performed by a real value GA.

For the evaluation value of the chromosome, the amount of information acquired when the training data is classified by the DTW distance using the feature pattern corresponding to the chromosome is used. The acquired information amount Gain (X) can be calculated by the following equations 4 and 5. Here, T is a set before division, and is divided into n subsets Ti (i is greater than 1 and less than or equal to n) by a certain division. info (S) is an amount called information entropy and is defined by the following Equation 6. S indicates a set, freq (Cj, S) is the number of elements of S belonging to class Cj, and k is the number of classes.

In selection, roulette selection is performed. In this method, the higher the fitness of the chromosome, the greater the probability of being selected, but there is a possibility that the next generation will remain even in the low fitness chromosome, and it is easy to be caught by the local solution by leaving only the high fitness chromosome. prevent. The roulette selection is performed according to the following procedure.
1. Roulette scaling is performed based on the evaluation value of each chromosome.
2. Leave the chromosome selected by roulette selection.
3. Repeat step 2 and select the chromosomes that will remain in the next generation until a predetermined number is reached.

The real value GA has a problem in that simple crossover has a problem that the children X 'and Y' due to crossover of two parents X and Y do not always approach the optimal solution E as shown in Fig. 4. Use the average crossover method. The average crossover method is a method of generating points that are the inner and outer parts of two search points in the search region.If the real-valued vectors corresponding to two chromosome pairs are X and Y, their center (X + Y) / 2 and two external dividing points (3X-Y) / 2 and (-X + 3Y) / 2 are generated, and two chromosomes having high fitness are selected. The intersection is selected by two-point intersection. Crossover is performed by the average crossover method for the inside of the two selected points. FIG. 5 shows an outline of the crossover method combining the average crossover method and the two-point crossover method.

In the mutation, the perturbation width M is defined, and the gene xi randomly selected from the chromosome is increased or decreased by the maximum M value. When the number of chromosome genes is n, the changing genes are xi, the upper limit of xi is a, and the lower limit is b, mutation is performed as follows.
1. Select i that is greater than or equal to 0 and less than or equal to n.
2. Positive and negative directions are selected with a probability of 0.5 each.
3. In the positive direction, the upper limit is a, and a value is randomly selected from xi to xi + M.
4). In the negative direction, the value from xi-M to xi is selected at random with the lower limit as b.

As described above, the feature pattern of the classified time series data and the classification rule using the same, or the automatically improved feature pattern and the classification rule using the same are extracted, and the extracted classification rule is used. A function for predicting classification of unclassified time series data is provided.

Difference between Euclidean distance and DTW distance. Training data example and extracted decision tree. Example of correspondence between feature pattern and chromosome. A simple crossover problem. Two-point crossover and average crossover. The entire device. Ideal method for creating experimental data. Effect of pattern improvement by genetic algorithm.

For the purpose of extracting the shape of time series data for each classification and the rules using it, the device was actually created and realized. (1) Is decision tree generation based on feature patterns effective? (2) Can effective feature patterns be extracted? (3) How effective is the improved function? Investigate three points. Two types of experimental data are used for this purpose. The effect (1) is investigated by artificially creating ideal data assumed by the proposed apparatus. Next, effects (2) and (3) are investigated using actual medical data.

FIG. 6 shows an outline of the entire apparatus. One piece of time-series data based on the stock price of one company, one patient, etc. is stored in association with the class value. First, for each time series data, a set of all partial time series data is collected by a fixed-length sliding window. Clustering is performed using all the collected partial time series data. Next, some representative sequences are filtered by TF * IDF, and the remaining sequences become feature patterns. Each partial time series data is expressed using a distance from the feature pattern. This is training data when extracting features using decision tree learning.

When extracting feature patterns, the size of the slide window for partial time series data extraction is 20 and the slide amount is 5. At this time, data less than the size of the sliding window at the end of the data is discarded. In DTW, the horizontal cost (cost of time axis deviation) is 50.0, and the cost of vertical cost (measurement value deviation) is the absolute value of the difference in values. C4.5 was used for decision tree learning. In order to investigate the effect of pattern improvement, 100 generations are calculated using a genetic algorithm, and the prediction accuracy in each generation is obtained. The classification accuracy of the decision tree is measured by 10-fold cross validation.

First, an ideal experimental data creation method will be described. First, five types of combinations of priority, future state, and feature pattern are prepared in advance. Time-series data is created by randomly arranging five types of feature patterns and random patterns for which future states are not set. FIG. 7 shows an outline of a method for creating ideal experimental data. Prepare 20 types of created time-series data and conduct experiments. The stagnation width magnification was 5%.

From the created time-series data, the time value of partial time-series data is simply used as an attribute, the feature pattern used for test data creation, and the randomly generated feature pattern are used. Perform decision tree learning by type and compare.

Table 1 shows the experimental results of accuracy, variance, and decision tree size. Simple is a decision tree whose attribute is simply the value of each time of partial time-series data. Known patterns is a decision tree with the feature pattern used for test data creation as an attribute. GA + Known patterns is a decision tree that has been improved by a genetic algorithm after using the feature pattern used for test data creation as an attribute. Random patterns are decision trees that have randomly generated feature patterns as attributes. GA + Random patterns are decision trees that are improved by a genetic algorithm after using randomly generated feature patterns as attributes. In the method using the characteristic pattern, the number of genes is changed to 5, 10, and 20 for measurement. All numbers in the table are average values of 20 types of data. We also show the variance of prediction accuracy to investigate the stability of the acquired decision tree.

From Table 1, it can be seen that there is not much difference in prediction accuracy when comparing Simple and Random patterns, and there is some improvement in accuracy as the level of detail of the cluster increases. However, it can be seen that using the pattern is more stable than the conventional method in terms of dispersion. In addition, with regard to Known patterns, prediction accuracy exceeding the conventional method was obtained in all settings. This experiment also shows that the prediction accuracy increases as the level of detail of the cluster increases.

Before and after the GA, the prediction accuracy has improved by several points, which is not a big effect, but it can be seen that it has the effect of improving the prediction accuracy. The detailed results of GA using the following actual medical data will be considered in detail. However, with artificially generated data, high prediction accuracy could be obtained by extracting feature patterns, so the improvement in accuracy by GA was sluggish. Conceivable.

To further investigate the effectiveness of the proposed device, experiments were performed using actual medical data. The data used is the test data for chronic hepatitis provided by the Chiba University Hospital. This data is a record of tests for 771 people over the 20 years from 1982 to 2001. From this data, the type of chronic hepatitis is predicted using only time series data (PLT) of platelets. There are two types of chronic hepatitis, type B and type C, but there are data on patients who received interferon administration for treatment of hepatitis C, so the predicted class is "hepatitis B" There were three types: “no hepatitis C interferon administration” and “with hepatitis C interferon administration”.

For comparison, each time of partial time series data obtained by sliding window using C4.5, support vector machine (hereinafter SVM), neural network (NN) as conventional method is used as attribute value. The classification is predicted. These conventional methods are labeled as direct approach (DA). In the proposed method, the number of clusters in feature extraction is tested with 5, 20, 30, 40, and 50 types. Table 2 shows the results of prediction accuracy.

When only feature pattern extraction was used, the classification accuracy was higher than all existing methods by setting the number of clusters to 40 or more. However, looking at the classification accuracy after pattern improvement by GA, it can be seen that higher classification accuracy than all existing methods can be obtained in all cluster number settings. From these facts, the pattern improvement function by GA is considered to work effectively for problems with low initial classification accuracy.

FIG. 8 shows changes in classification accuracy by generation by GA. As shown in the graph, it can be seen that the setting of the number of all five types of clusters has high prediction accuracy. Also, since the initial accuracy is worse as the number of clusters is lower, the improvement effect by GA seems to be higher. From these facts, it can be said that the improvement by GA is more effective when the accuracy becomes lower without securing a sufficient number of feature patterns, and finally has the effect of stably outputting high prediction accuracy.

Since the time-series data targeted by the present invention is basic data that frequently appears in various fields such as economy, medical care, and science, it is a technique that can be applied in a wide range of fields.

(A) Euclidean distance point correspondence example.
(B) Dynamic Time Warping point correspondence example.
(C) Example of training data based on feature patterns.
(D) An example of an output decision tree.
(E) Feature pattern normalized to rate of change.
(F) Chromosome corresponding to the characteristic pattern.
(G) Two selected parental chromosomes.
(H) A child chromosome created as a result of crossover.
(I) A feature pattern that combines priority and future state.
(J) Ideal experimental data created based on characteristic patterns.

Claims (4)

An apparatus for extracting, as a feature pattern, a change in a partial section of time-series data that characterizes the classification of each time-series data from a time-series database that can distinguish time-series data classified by a certain concept. The apparatus according to claim 1, which has a function of extracting a classification rule for classifying unclassified time-series data into an appropriate concept group based on the feature pattern extracted in claim 1. 3. The apparatus according to claim 2, wherein the time series data that is actually unclassified is classified into an appropriate concept group in accordance with the classification rule extracted in claim 2. The apparatus according to claim 2, which has a function of improving the classification accuracy of the classification rule extracted in claim 2 by automatically improving the feature pattern extracted in claim 1.