JP6111543B2 - Method and apparatus for extracting similar sub time series - Google Patents

Description

  The present invention relates to the field of time series processing, and in particular, to a method and apparatus for extracting a sub time series similar to a reference series from a time series.

  Extracting a similar sub time series means extracting a sub series similar to a given reference. Similar sub-time series extraction is a basic technology applied to jobs such as time-series prediction, clustering, and abnormality detection. For example, for prediction of time series, it is necessary to extract similar sub-sequences so as to be used for training.

  In general, extracting similar subsequences involves two steps. The first step is to divide the time series, that is, divide the time series into a plurality of parts. The second step is to extract similar subsequences based on similarity calculation. The conventional similar sub-sequence extraction technique mainly has the following three problems. (1) Since the division is not flexible, the candidate set becomes small. (2) To consume storage space and processing time. (3) Do not consider physical significance.

  Therefore, a proposal of a technique that can solve the above problem is desired.

  The following presents a brief summary of the invention in order to provide a basic understanding of some aspects of the invention. It should be understood that this summary is not an exhaustive description of the invention. It is not intended to identify keys or key parts of the invention, nor is it intended to limit the scope of the invention. Its purpose is simply to provide a concept in a simplified form, which is a preface to a more detailed description of subsequent discussions.

  An object of the present invention is to provide a method and apparatus for extracting a sub time series similar to a reference series from a time series.

  According to one aspect of the present invention, a method is provided for extracting a sub time series similar to a reference series from a time series. The method includes a step of converting the time series and the reference series based on a change tendency of each of the time series and the reference series, a step of dividing the converted time series into a plurality of sub time series, and the plurality of sub times. Calculating an edit distance between each sub time series and the converted reference series for each sub time series of the series, and based on the calculated edit distance, the reference series from the plurality of sub time series Extracting a sub time series similar to.

  According to another aspect of the present invention, an apparatus for extracting a sub time series similar to a reference series from a time series is provided. The apparatus includes: a sequence conversion unit that converts a time series and a reference sequence based on a change tendency of each of the time series and the reference sequence; and a sub time series dividing unit that divides the converted time series into a plurality of sub time series. An edit distance calculating means for calculating an edit distance between each time series and the converted reference series for each time series of the plurality of time series, and the plurality of sub-sequences based on the calculated edit distance Similar time series extracting means for extracting a sub time series similar to the reference series from the time series.

  The embodiment of the present invention provides a computer program for realizing the above method.

  Also, embodiments of the present invention further provide a computer program product in the form of at least a computer readable medium. Computer program code for realizing the above method is stored in the computer program product.

  These and other advantages of the present invention will become more apparent from the best mode for carrying out the invention described below in connection with the drawings.

The above and other objects, features and advantages of the present invention will be more readily understood with reference to the following description of embodiments of the invention given in connection with the drawings. Each part in the drawings is only for illustrating the principle of the present invention. In the drawings, the same or similar technical features or parts are denoted by the same or similar reference numerals.
4 is a flowchart illustrating a method for extracting a sub time series similar to a reference series from a time series according to an embodiment of the present invention. It is a graph which shows the load time series for one week. It is a graph which shows two load sub time series and one reference series. FIG. 3 is a block diagram of an apparatus for extracting a sub-sequence similar to a reference sequence from a time series according to an embodiment of the present invention. FIG. 2 is a diagram illustrating an exemplary structure of a computing device for implementing the method and apparatus for extracting a sub time series similar to a reference series from the time series of the present invention.

  Embodiments of the present invention will be described below with reference to the drawings. Elements and features described in one drawing or embodiment of the invention may be combined with elements and features shown in one or more other drawings or embodiments. For clarity, illustration and description of parts and processes known to those skilled in the art that are not directly related to the present invention are omitted in the drawings and specification.

  Referring to FIG. 1, a method 100 for extracting a sub time series similar to a reference series from a time series according to an embodiment of the present invention will be described.

  As shown in FIG. 1, in step S102, the time series and the reference series can be converted based on the changing tendency of each of the time series and the reference series.

  Specifically, the time series can be converted based on a change with respect to the previous element or a plurality of previous elements of the current element in the time series. In addition, the reference sequence can be converted based on the change in the reference element from the previous element or a plurality of previous elements of the current element.

  Instead, the time series can be converted based on changes to the next element or elements after the current element in the time series. Further, the reference sequence can be converted on the basis of the change of the current element in the reference sequence with respect to the next element or a plurality of subsequent elements.

  Here, the same conversion rule is adopted for the conversion of the time series and the reference series. Note that the conversion between the time series and the reference sequence is not limited to the above method, and the time series and the reference sequence may be converted by any other method that can be conceived by those skilled in the art. If it can reflect.

  Next, in step S104, the converted time series can be divided into a plurality of sub time series.

  Preferably, the converted time series can be divided into a plurality of sub time series according to a predetermined division step length which may be different from the length of the reference series. Further, the converted time series can be divided into a plurality of sub time series according to a predetermined division length that may be different from the length of the reference series. By performing such flexible division on the time series, the time series can be divided more actively, and corresponding division results can be obtained as necessary, and necessary similar sub-sequences can be obtained. The For example, a similar sub-sequence similar to the reference sequence but having a length different from that of the reference sequence can be acquired.

  Next, in step S106, the edit distance between each sub time series and the converted reference series can be calculated for each sub time series among the plurality of divided sub time series.

  Preferably, in the above calculation, a weighted edit distance between each sub time series and the converted reference series is calculated. One or more of the following requirements can be satisfied. That is, regarding the insertion operation, it is allowed to give different weights for insertion of different elements, for the deletion operation, it is allowed to give different weights to deletion of different elements, and for the replacement operation, This includes allowing different weights to be assigned to different element pair replacements. Compared to the traditional method that does not use weights, the sub time series more similar to the reference series is shorter to the reference series by calculating the weighted edit distance between each sub time series and the changed reference series. Can have a distance.

  In step S108, a sub time series similar to the reference series is extracted from a plurality of sub time series based on the calculated editing distance.

  Specifically, one or a plurality of sub time series having an edit distance smaller than a predetermined threshold is extracted as a sub time series similar to the reference series from the plurality of sub time series.

  Preferably, a predetermined number of sub time series having a minimum editing distance is extracted as a sub time series similar to the reference series from a plurality of sub time series (that is, a predetermined number is extracted in ascending order of editing distance).

  Of course, extracting the sub time series similar to the reference series is not limited to the above method, and may be performed by any method conceivable by those skilled in the art.

  Hereinafter, a method for extracting a sub time series similar to the reference series from the load time series will be described with reference to FIGS. 2 is a graph showing a one-week load time series, and FIG. 3 is a graph showing two load sub-time series and one reference series. However, it should be understood that the time series associated with the load is only one example. Actually, the time series processed by the present invention may be any time series, and is not limited to the formats shown in FIGS.

First, the time series and the reference series are converted based on the change tendency of each of the time series and the reference series, that is, various changes are made by comparing changes between the current element and the previous element or a plurality of previous elements. Perform the conversion. For example, the time series is c ₁ , c ₂ , c ₃ ,..., C _n , and n is an integer greater than 1. The reference sequence is b ₁ , b ₂ ,..., B _m , where m is an integer greater than 1. Usually, m is smaller than n. Of course, it is not excluded even if it is larger than n.

ただし、必要に応じて予めeを設定しておく、またはパラメータ・トレーニングによってeを取得してもよい。 For example, the time series may be converted by the following expression (1), while the reference series may be converted by the following expression (2).

However, e may be set in advance as necessary, or e may be acquired by parameter training.

ただし、必要に応じて予めgを設定しておく、またはパラメータ・トレーニングによってgを取得してもよい。 Alternatively, the time series can be converted by the following expression (3), while the reference series can be converted by the following expression (4).

However, g may be set in advance as necessary, or g may be acquired by parameter training.

  Equations (1) and (2) or (3) and (4) are merely exemplary conversion methods, and in practice, any other conversion method that can be conceived by those skilled in the art is adopted as necessary. The method may be any method that can reflect the change tendency between the time series and the reference series.

  Next, the conversion of the load time series shown in FIG. 2 will be described using Equation (1) as an example. With the expression (1), the graph in FIG. 2 can be converted into the following form.

  20022222212000012222100001222222200000002221000000222222000000012222100000222222000000002222000000022222200000002220000000002222200000002220000000222222000000000220000.

  Then, a reference sequence (not shown) is converted by equation (2).

  Next, the above time series can be divided.

  Preferably, the converted time series is divided into a plurality of sub time series according to a flexible division method, that is, according to a predetermined step length and a predetermined length which may be different from the length of the reference sequence.

The length of the converted reference sequence is assumed to be 8. When dividing a time series according to a predetermined step length and a predetermined length that are the same as the length of the reference sequence, that is, when both the predetermined step length and the predetermined length used for the dividing process are 8 The time series is divided as follows, for example.
20022222,21200001,22221000,01222222 ……
Similarly, the length of the reference sequence after conversion is assumed to be 8. When dividing a time series according to a predetermined step length different from the length of the reference sequence and according to a predetermined length equal to the length of the reference sequence, for example, the predetermined step length used for the division process is 6 If the predetermined length is 8, the time series can be divided as follows. [That is, the length of each divided sub-sequence (overlapping each other) is 8, and the length of the step (interval) between the heads of each sub-sequence is 6. ]
20022222,22212000,00012222,22100001 ……
The length of the reference sequence after conversion is assumed to be 8. When dividing a time series according to a predetermined step length that is the same as the length of the reference sequence and according to a predetermined length that is different from the length of the reference sequence, for example, the predetermined step length used for the dividing process is 8. If the predetermined length is 6, the time series can be divided as follows. [That is, the length of each divided sub-sequence is 6, the length of the step (interval) between the heads of each sub-sequence is 8, and the end of each sub-sequence and the beginning of the next sub-sequence There is a gap of length 2 between them. ]
200222,212000,222210,012222 ……
The length of the reference sequence after conversion is assumed to be 8. When dividing a time series according to a predetermined step length different from the length of the reference sequence and according to a predetermined length different from the length of the reference sequence, for example, the predetermined step length used for the dividing process is 6 If the predetermined length is 6, the time series can be divided as follows.
200222,222120,000122,221000 ……
It should be understood that the lengths and step lengths here, such as 6 and 8, are exemplary and not limiting of the invention.

A weighted edit distance between each time series and the converted reference series among the plurality of sub time series is calculated. For example, transformed sub time series _{X {c 1, c 2,} ..., c i} a reference sequence _{Y {b 1, b 2,} ..., b j} edit distance between D (i, j) is the following It can be calculated by the following formula.

The edit distance between two sequences means the minimum cost required to convert one sequence to the other by several operations. Note that w _i is the cost of the insert operation, w _d is the cost of the delete operation, and _wr is the cost of the replacement operation. Actually, as described above, regarding insertion operations, different weights are allowed for insertion of different elements, and for deletion operations, different weights are permitted for deletion of different elements. Different weights can be given to different element pairs.

ただし、x_i及びy_iは距離を算出すべき二つの系列中の対応する要素である。 In the following, for the insertion operation, the same weight is given to the insertion of different elements, for the deletion operation, the same weight is given to the deletion of different elements, and for the replacement operation, different weights are given to the replacement of different element pairs. Is granted. (6)-(8) (Formula) may specify w _i , w _d, and w _r .

Where x _i and y _i are the corresponding elements in the two sequences whose distances are to be calculated.

  After calculating the edit distance using equations (5)-(8), a sub time series smaller than a predetermined threshold of the minimum weighted edit distance or a certain number of sub series with the smallest distance are extracted as similar sub time series. To do.

FIG. 3 is a graph showing two load sub time series and one reference series. As shown in FIG. 3, A and B each indicate a sub time series, and C indicates a reference series. The sub time series corresponding to the time series of FIG. 2 is not given, but the sub series A and the sub time series B are arbitrarily given in order to explain the equations (5) to (8). It should be understood that the time series of FIG. 2 may be divided to obtain the sub time series, and the edit distance between the obtained sub time series and the reference series C may be calculated.
From the equation (1), the sub time series A can be converted as follows. 00112222 1110 00122221000.
From the equation (1), the sub time series B can be converted as follows. 00112222 2220 00122221000.
From the equation (2), the sub time series C can be converted as follows. 00112222 0002 00122221000.

  When the traditional edit distance calculation method, that is, when no weight is introduced, the edit distance D (A, C) between the sub time series A and the reference time series C = 4, and the sub time series B and the reference time The edit distance D (B, C) between the series C is 4.

  The weighted edit distance calculated by the equations (5) to (8) is as follows, and the edit distance D ′ (A, C) between the sub time series A and the reference time series C is 2.5, and the sub time series The edit distance D ′ (B, C) = 4 between B and the reference time series C.

  From FIG. 3, it can be seen that most of time series A, time series B, and reference series C overlap, and only the middle part thereof is different. Since the middle part of the sub time series B is located above, the middle part of the sub time series A is located in the middle, and the middle part of the reference series C is located below, the sub time series A is closer to the reference C. The result calculated by the weighted edit distance calculation method is more suitable for the actual situation of FIG. 3, and the edit distance D ′ (A, C) = 2.5 between the sub time series A and the reference series C, sub time series B Since the edit distance D ′ (B, C) = 4 between the reference time series C and D ′ (A, C) <D ′ (B, C). On the other hand, in the traditional editing method in which no weighting is introduced, the editing distance D (A, C) between the sub time series A and the reference time series C = 4, the sub time series B and the reference time series C Since the edit distance D (B, C) = 4 in the interval, D (A, C) = D (B, C), but such a result cannot reflect the actual situation of FIG.

  Hereinafter, an apparatus 400 for extracting a sub time series similar to a reference series from a time series, which is an embodiment of the present invention, will be described with reference to FIG. Only the basic framework of the apparatus 400 that does not overlap with the parts corresponding to the above method will be described.

  As shown in FIG. 4, the apparatus 400 can include a series conversion unit 402, a sub time series division unit 404, an edit distance calculation unit 406, and a similar sub time series extraction unit 408.

  Note that the series conversion unit 402 may be configured to convert the time series and the reference series according to the changing tendency of each of the time series and the reference series.

  Series conversion unit 402 may include a time series conversion sub unit and a reference sequence conversion sub unit (none of which are shown). The time series conversion sub means converts the time series based on a change in the previous element or a plurality of previous elements of the current element in the time series. The reference sequence conversion means can convert the reference sequence based on a change of the current element in the reference sequence with respect to the previous element or a plurality of previous elements.

  Preferably, the time series conversion sub means can convert the time series based on a change of the current element in the time series with respect to the next element or a plurality of subsequent elements. The reference sequence conversion sub means can convert the reference sequence based on a change of the current element in the reference sequence with respect to the next element or a plurality of subsequent elements.

  The sub time series dividing unit 404 may be configured to divide the converted time series into a plurality of sub time series.

  The sub time series dividing means 404 is further transformed according to a predetermined division step length that may be different from the reference sequence length and / or a predetermined division length that may be different from the reference sequence length. The time series may be divided into a plurality of sub time series.

  The edit distance calculation means 406 may be configured to calculate an edit distance between each time series and the converted reference series for each time series of the plurality of sub time series.

  The edit distance calculation means 406 can calculate a weighted edit distance between each time series and the converted reference series. Note that one or more of the following requirements are satisfied. For insertion operations, allow different weights for insertion of different elements, for deletion operations, allow different weights for deletion of different elements, for replacement operations, for replacement of different element pairs Allow the application of different weights.

  The similar sub time series extracting unit 408 may be configured to extract a sub time series similar to the reference series from a plurality of time series based on the calculated editing distance.

  The similar sub time series extracting means 408 is configured to extract one or a plurality of sub time series having an edit distance smaller than a predetermined threshold from a plurality of sub time series, and sub time series similar to the reference series. Also good.

Alternatively, the similar sub time series extraction unit 408 may be further configured to extract a sub time series having a minimum number of minimum edit distances from a plurality of sub time series, and sub time series similar to the reference series. Good. [That is, a certain number is extracted from the one with the smaller edit distance. ]
According to the embodiment of the present invention, similar sub time series can be extracted more quickly, flexible time division can be realized, and similar time can be obtained depending on the physical significance of the series according to practical use. A series can be extracted.

  Although the basic principles of the present invention have been described in connection with the specific embodiments described above, for those skilled in the art, all or any step or component of the method and apparatus of the present invention may be performed on any computing device (processor or memory). It should be understood that the present invention may be implemented by hardware, firmware and software, or a combination thereof, in a network of computing devices). This can be achieved with the basic programming skills of those skilled in the art who have read the specification of the present invention.

  Accordingly, the objects of the present invention may be realized by executing a program or a set of programs on any computing device. The computing device may be a known general purpose device. Therefore, the object of the present invention may be further realized by providing a program product including a program code for realizing the method or apparatus. That is, it can be understood that such a program product can also constitute the present invention, and a product storing such a program can constitute the present invention. As will be apparent, the storage medium may be any known storage medium or any one developed in the future.

  Embodiments of the present invention, when implemented by software and / or firmware, configure the software from a storage medium or network to a computer having a dedicated hardware structure (eg, general purpose computer 500 shown in FIG. 5). Install the program. The computer can execute various functions when various programs are installed.

  In FIG. 5, a central processing unit (CPU) 501 performs various processes based on a program stored in a read-only memory (ROM) 502 or a program loaded from a storage unit 508 to a random access memory (RAM) 503. Execute. In the RAM 503, data necessary when the CPU 501 executes various processes and the like is stored as necessary. The CPU 501, ROM 502, and RAM 503 are connected to each other via a bus 504. An input / output interface 505 is also connected to the bus 504.

  The following components are connected to the input / output interface 505. An input unit 506 (including a keyboard and a mouse), an output unit 507 (including a display such as a cathode ray tube (CRT), a liquid crystal display (LCD), and a speaker), and a storage unit 508 (including a hard disk) A communication unit 509 (including a network interface card such as a LAN card, a modem, and the like). The communication unit 509 may be connected to the input / output interface 505 as necessary. A removable medium 511, for example, a magnetic disk, an optical disk, a magneto-optical disk, a semiconductor memory, or the like is attached to the drive 510 as necessary, whereby a computer program read from the medium is stored in the storage unit 508 as necessary. Installed.

  When the above-described series of processing is realized by software, a program constituting the software is installed from a network, for example, the Internet, or a storage medium, for example, a removable medium 511.

  Those skilled in the art will recognize that such storage media is not limited to the removable media 511 shown in FIG. 5 in which the program is stored and delivered remotely from the device to provide the program to the user. Should understand. Examples of the removable medium 511 include a magnetic disk (including a floppy (registered trademark) disk), an optical disk (including a compact disk read-only memory (CD-ROM) and a digital versatile disk (DVD)), and a magneto-optical disk. (Including Mini Disc (MD) (registered trademark)) and semiconductor memory. Alternatively, the storage medium may be a hard disk included in the ROM 502 and the storage unit 508, which stores a program and is delivered to a user together with a device including them.

  The present invention further provides a program product in which an instruction code readable by a device is stored. When the instruction code is read and executed by the device, the method according to the above-described embodiment of the present invention can be executed.

  Correspondingly, a storage medium for mounting a program product in which an instruction code readable by the above device is stored is also included in the disclosure of the present invention. Storage media include, but are not limited to, floppy disks, optical disks, magneto-optical disks, memory cards, memory sticks, and the like.

  Those skilled in the art should understand that the examples given here are illustrative and not limiting.

  In the specification, the descriptions of “first”, “second” and “Nth” are for distinguishing the described features and clearly illustrating the present invention. Therefore, these should not be regarded as any limiting meaning.

  As an example, each step of the method and each component module and / or means of the device may be implemented as software, firmware and hardware or a combination thereof and is part of a corresponding device. The specific means or method used when configuring each component module and means in the above-described apparatus in the form of software, firmware and hardware or a combination thereof is well known to those skilled in the art. Please do not explain.

  As an example, when implemented by software or firmware, a program constituting the software is installed from a storage medium or a network to a computer having a dedicated hardware structure (for example, the general-purpose computer 500 shown in FIG. 5). May be. The computer can execute various functions when various programs are installed.

  In the above description of the mode for carrying out the invention, the features described and / or illustrated in one embodiment may be used in one or more other embodiments in a homologous or similar manner. , In combination with features in other embodiments, or features in other embodiments may be replaced.

  The term “comprising / having” as used herein means the presence of a feature, element, step or component, but the presence or addition of one or more other features, elements, steps or components. Is not to be excluded.

  Further, the method of the present invention is not limited to being performed according to the time order described in the specification. They may be executed in parallel or independently of each other according to other time orders. Therefore, the execution order of the methods described herein does not limit the technical scope of the present invention.

  While the invention has been disclosed in terms of specific embodiments of the invention, those skilled in the art can design various modifications, improvements or equivalents within the spirit and scope of the claims. These modifications, improvements or equivalents are also considered to be covered within the protection scope of the present invention.

About embodiment containing said Example, the following additional remarks are also contained.
Note:
(Appendix 1)
A method of extracting a sub time series similar to a reference series from a time series, wherein a computer
Converting the time series and the reference series into a series representing a change tendency of the time series and the reference series, respectively;
Split the transformed time series into multiple sub time series,
Calculating an edit distance between each sub time series of the plurality of sub time series and the converted reference series;
A method of extracting a sub time series similar to the reference series from the plurality of sub time series based on the calculated editing distance.
(Appendix 2)
The series representing the change tendency of the time series is a series representing a change with respect to an element before one or a plurality of previous elements of the current element in the time series,
The series representing a change tendency of the reference series is a series representing a change with respect to an element one or more before the current element in the reference series.
The method according to appendix 1.
(Appendix 3)
The series representing a change tendency of the time series is a series representing a change with respect to an element after one or a plurality of elements after the current element in the time series,
The series representing a change tendency of the reference series is a series representing a change with respect to an element after one or a plurality of current elements in the reference series.
The method according to appendix 1.
(Appendix 4)
The edit distance is a weighted edit distance and is one or more of the following requirements:
For the insert operation, it is allowed to give different weights to the insertion of different elements,
For the delete operation, different weighting is allowed for the deletion of different elements, and / or
For replacement operations, satisfying that different weights are allowed for replacement of different element pairs.
The method according to appendix 1.
(Appendix 5)
Based on the calculated editing distance, a process of extracting a sub time series similar to the reference series from the plurality of sub time series,
The method according to claim 1, comprising extracting one or more sub time series having an edit distance smaller than a predetermined threshold from the plurality of sub time series as a sub time series similar to the reference series.
(Appendix 6)
Each sub time series divided by the process of dividing the converted time series into a plurality of sub time series has a predetermined length, and the interval between the heads of each divided sub time series is a predetermined step length. The method according to any one of appendices 1 to 5, wherein the predetermined length and the predetermined step length may be the same as or different from a length of the reference sequence.
(Appendix 7)
An apparatus for extracting a sub time series similar to a reference series from a time series,
Series conversion means configured to convert the time series and the reference series into a series representing a change tendency of the time series and the reference series, respectively;
Sub time series dividing means configured to divide the converted time series into a plurality of sub time series;
An edit distance calculating means configured to calculate an edit distance between each sub time series of the plurality of sub time series and the converted reference series;
A similar time series extracting unit configured to extract a sub time series similar to the reference series from the plurality of sub time series based on the calculated editing distance.
(Appendix 8)
The series representing the change tendency of the time series is a series representing a change with respect to an element before one or a plurality of previous elements of the current element in the time series,
The series representing a change tendency of the reference series is a series representing a change with respect to an element one or more before the current element in the reference series.
The apparatus according to appendix 7.
(Appendix 9)
The series representing a change tendency of the time series is a series representing a change with respect to an element after one or a plurality of elements after the current element in the time series,
The series representing a change tendency of the reference series is a series representing a change with respect to an element after one or a plurality of current elements in the reference series.
The apparatus according to appendix 8.
(Appendix 10)
The edit distance is a weighted edit distance and is one or more of the following requirements:
For the insert operation, it is allowed to give different weights to the insertion of different elements,
For the delete operation, different weighting is allowed for the deletion of different elements, and / or
The apparatus according to appendix 7, wherein the replacement operation satisfies that different weighting is permitted for replacement of different element pairs.
(Appendix 11)
The similar sub time series extraction means includes:
The supplementary note 7 is configured to extract one or a plurality of sub time series having an edit distance smaller than a predetermined threshold from the plurality of sub time series as a sub time series similar to the reference series. apparatus.
(Appendix 12)
The sub time series dividing unit performs the division so that each divided sub time series has a predetermined length, and an interval between the heads of each divided sub time series has a predetermined step length. The apparatus according to any one of appendices 7 to 11, wherein the device is configured as described above, and the predetermined length and the predetermined step length may be the same as or different from a length of the reference sequence.
(Appendix 13)
A program that causes a computer to execute the procedure of the method according to any one of appendices 1 to 6.
(Appendix 14)
A computer-readable storage medium storing a program for causing a computer to execute the procedure of the method according to any one of appendices 1 to 6.

Claims (10)

A method for extracting a sub-time-series similar to the reference sequence b _i from the time series c _i, computer,
The time series c _i and the reference series b _i , respectively,

(Except for the case of γ = 1) or according to an equation in which i−1 in the above equation is replaced by i + 1, and converted into a sequence representing a change tendency of the time series and the reference sequence,
Split the transformed time series into multiple sub time series,
Calculating an edit distance between each sub time series of the plurality of sub time series and the converted reference series;
A method of extracting a sub time series similar to the reference series from the plurality of sub time series based on the calculated editing distance. The series representing the change tendency of the time series is a series representing a change with respect to an element before one or a plurality of previous elements of the current element in the time series,
The series representing a change tendency of the reference series is a series representing a change with respect to an element one or more before the current element in the reference series.
The method of claim 1. The series representing a change tendency of the time series is a series representing a change with respect to an element after one or a plurality of elements after the current element in the time series,
The series representing a change tendency of the reference series is a series representing a change with respect to an element after one or a plurality of current elements in the reference series.
The method of claim 1. The edit distance is a weighted edit distance and is one or more of the following requirements:
For the insert operation, it is allowed to give different weights to the insertion of different elements,
For the delete operation, different weighting is allowed for the deletion of different elements, and / or
For replacement operations, satisfying that different weights are allowed for replacement of different element pairs.
The method of claim 1. Based on the calculated editing distance, a process of extracting a sub time series similar to the reference series from the plurality of sub time series,
The method according to claim 1, comprising extracting one or more sub time series having an edit distance smaller than a predetermined threshold from the plurality of sub time series as a sub time series similar to the reference series. . Each sub time series divided by the process of dividing the converted time series into a plurality of sub time series has a predetermined length, and the interval between the heads of each divided sub time series is a predetermined step length. The method according to any one of claims 1 to 5, wherein the predetermined length and the predetermined step length may be the same as or different from a length of the reference sequence. An apparatus for extracting a sub-time-series similar to the reference sequence b _i from the time series c _i,
The time series c _i and the reference series b _i , respectively,

(Except for the case where γ = 1) , or according to an expression in which i−1 in the above expression is replaced by i + 1, a series configured to convert the time series and the reference series into a series representing a change tendency Conversion means;
Sub time series dividing means configured to divide the converted time series into a plurality of sub time series;
An edit distance calculating means configured to calculate an edit distance between each sub time series of the plurality of sub time series and the converted reference series;
A similar time series extracting unit configured to extract a sub time series similar to the reference series from the plurality of sub time series based on the calculated editing distance. The series representing the change tendency of the time series is a series representing a change with respect to an element before one or a plurality of previous elements of the current element in the time series,
The series representing a change tendency of the reference series is a series representing a change with respect to an element one or more before the current element in the reference series.
The apparatus according to claim 7. The series representing a change tendency of the time series is a series representing a change with respect to an element after one or a plurality of elements after the current element in the time series,
The series representing a change tendency of the reference series is a series representing a change with respect to an element after one or a plurality of current elements in the reference series.
The apparatus according to claim 8. The program which makes a computer perform the procedure of the method as described in any one of Claims 1 thru | or 6.

Images