Nothing Special   »   [go: up one dir, main page]

WO2023084787A1 - 変化点検知装置、変化点検知方法及びプログラム - Google Patents

変化点検知装置、変化点検知方法及びプログラム Download PDF

Info

Publication number
WO2023084787A1
WO2023084787A1 PCT/JP2021/041966 JP2021041966W WO2023084787A1 WO 2023084787 A1 WO2023084787 A1 WO 2023084787A1 JP 2021041966 W JP2021041966 W JP 2021041966W WO 2023084787 A1 WO2023084787 A1 WO 2023084787A1
Authority
WO
WIPO (PCT)
Prior art keywords
time
data
cluster
devices
change point
Prior art date
Application number
PCT/JP2021/041966
Other languages
English (en)
French (fr)
Inventor
彰子 高橋
恵 竹下
Original Assignee
日本電信電話株式会社
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 日本電信電話株式会社 filed Critical 日本電信電話株式会社
Priority to US18/702,548 priority Critical patent/US20240411780A1/en
Priority to PCT/JP2021/041966 priority patent/WO2023084787A1/ja
Priority to JP2023559393A priority patent/JPWO2023084787A1/ja
Publication of WO2023084787A1 publication Critical patent/WO2023084787A1/ja

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/25—Integrating or interfacing systems involving database management systems
    • G06F16/258—Data format conversion from or to a database
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/28—Databases characterised by their database models, e.g. relational or object models
    • G06F16/283—Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/28—Databases characterised by their database models, e.g. relational or object models
    • G06F16/284—Relational databases
    • G06F16/285—Clustering or classification
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N20/00—Machine learning

Definitions

  • the present disclosure relates to a change point detection device, a change point detection method, and a program.
  • system state is the operating state of the system represented by quantitative variables such as "number of accesses” and "number of users”.
  • Non-Patent Literatures 1 to 4 are known as techniques for detecting change points in time-series data to which correct labels regarding the occurrence positions of change points are not assigned.
  • Non-Patent Document 1 proposes a method of calculating the degree of change by evaluating the distance between subspaces composed of partial time series using the subspace method.
  • a matrix is generated by bundling partial time series (time windows extracted from the time series) for each of the past period and the current period, and characteristic patterns are extracted by singular value decomposition. is a method of evaluating the distance of
  • Non-Patent Document 2 proposes a method of estimating the probability distribution of a new section based on data observed after the previous change point using a probability model. This is a method of detecting a change point by estimating the probability distribution of the run length from the last change point (elapsed time to the next change point) based on Bayesian theory.
  • Bayesian theory is a theory that indicates that "the possibility of something happening can be roughly estimated using the frequency of occurrence of that event in the past.”
  • Non-Patent Document 3 proposes a method of classifying time-series data using clustering and determining that a change has occurred when a new observed value does not match any existing cluster. This is a method of determining whether or not the Euclidean distance between a new observed value and the centroid of an existing cluster exceeds the radius of the cluster for all existing clusters, and detecting it as a change point if it exceeds all.
  • Non-Patent Document 4 Online change detection based on two-stage learning in Non-Patent Document 4 is a type of likelihood ratio test that determines whether there is a significant difference in the probability density of two consecutive sections based on the likelihood ratio.
  • the probability density function based on the same autoregressive model is calculated from the smoothed outlier score series calculated up to the previous point.
  • a logarithmic loss function under the probability density function is calculated for an outlier score calculated from newly observed data after learning, and a smoothed value is used as a change point score.
  • Non-Patent Document 5 is a method of classifying the state of time-series data using clustering and then tracing the clusters assigned to each time point along the time axis to extract cluster transitions between different clusters. Furthermore, this calculates the appearance frequency of each cluster transition pattern in the past fixed period, and detects as non-stationary fluctuation when the appearance frequency of the newly observed cluster transition pattern in the past period is below a preset threshold. The method.
  • Non-Patent Document 1 has the limitation that the time series to be detected must be a stationary process. In other words, it is necessary to satisfy the weak stationarity that the expected value and autocovariance of the target time series are constant regardless of time.
  • Non-Patent Document 2 has the restriction that the time series to be detected must be independently and identically distributed (iid: independently and identically distributed). In other words, it is necessary that the data at each point in the time series follow the same probability distribution independently of each other.
  • many of the time-series data observed in many systems, such as network systems show periodic fluctuations such as hourly fluctuations, day-of-week fluctuations, and monthly fluctuations. Therefore, it is not possible to apply change point detection technology that is subject to constraints such as the stationarity constraint and the iid constraint.
  • the change point detection technique by clustering proposed by Non-Patent Document 3 and the online change detection technique based on two-stage learning proposed by Non-Patent Document 4 are not subject to constraints such as stationarity constraints and iid constraints on the target time series. It is considered promising in terms of However, the change point detection technology based on clustering proposed by Non-Patent Document 3 classifies snapshot data extracted from time-series data at each point in time, and determines whether or not the classified state differs from the existing state. and does not consider the time axis. In other words, in time-series data in which state changes follow a certain pattern, such as time-series data showing periodic fluctuations observed in many systems, this time-change pattern changes at a certain moment. In this case, this change point cannot be detected.
  • Non-Patent Document 4 is based on an autoregressive model, so it can be said that it takes into consideration the time axis. Therefore, it is also promising for time-series data whose time-varying patterns change at certain moments.
  • an autoregression model for time-series data in which multiple types of periodic fluctuations with different periods, such as hourly fluctuations, day-of-the-week fluctuations, and monthly fluctuations, coexist.
  • Non-Patent Document 5 is based on clustering in which the target time series is not restricted, and is a technology that considers the time axis by a method of tracking cluster transitions in the direction of the time axis. is.
  • this technology is a technology that detects cluster transition patterns whose frequency of appearance calculated over a certain period of time in the past falls below a preset threshold as unsteady fluctuations, and that individual cluster transitions are in an abnormal state compared to past results. (low appearance frequency) or not, and does not detect a change point that can be said to be the beginning of a continuous abnormal state.
  • the present invention has been made in view of the above points.
  • the purpose is to detect the time point of occurrence as a change point when some change occurs.
  • the invention according to claim 1 provides time-series data representing a system state at each point in time of a system composed of one or more devices, wherein the number of devices constituting the system x the
  • a time window generating unit that generates transformed data by transforming data into data of the dimension of x time window length; and a detection unit that detects a change point when the value exceeds the change point detection device.
  • time-series data representing the system state at each point in time of a system (S) composed of one or more devices is used to change the point of occurrence when any change occurs in the system state.
  • a change point detection device 10 capable of detecting points will be described.
  • the "system state” is the operating state of the system represented by quantitative variables such as "number of accesses" and "number of users”.
  • FIG. 1 is a diagram showing an example of the functional configuration of the change point detection device according to this embodiment.
  • the change point detection device 10 includes an input unit 11, a time window generation unit 12, a period setting unit 13, a clustering unit 14, a cluster transition series generation unit 15, It has a cluster transition tensor calculation unit 16 , a change point score calculation unit 17 , a detection unit 18 and an output unit 19 .
  • the ⁇ devices'' in the ⁇ number of devices'' and ⁇ status of devices'' shown below indicate the devices constituting the system to be subjected to change point detection by the change point detection device 10.
  • the input unit 11 is time-series data representing the system state at each point in time of the system (S) composed of one or more devices, which constitutes the system (S) (representing the number of devices ⁇ device state Number of items) Enter time-series data consisting of dimensional data.
  • the time window generation unit 12 divides the time-series data input by the input unit 11 into fixed-length time windows, and converts the data at each time point from the (number of devices x number of items) dimensional data into (number of devices x number of items x time window length)-dimensional data to generate converted data and perform intermediate output.
  • the period setting unit 13 extracts the time series data of the preset past period and the current period from the (number of devices x number of items x time window length) time series data generated by the time window generation unit 12. , intermediate output.
  • the clustering unit 14 classifies the (number of devices ⁇ number of items ⁇ time window length) dimensional data at each time point constituting the time-series data of the past period and the current period extracted by the period setting unit 13 by a clustering method. , intermediate output.
  • the cluster transition series creation unit 15 traces the clusters assigned by the clustering unit 14 to the (number of devices ⁇ number of items ⁇ time window length)-dimensional data at each point in the past period and the current period in the direction of the time axis. and the current period, a series of cluster transitions between different clusters is created, and at the same time, each cluster constituting this cluster transition series is assigned a stay period in the cluster, and an intermediate output is performed.
  • the cluster transition tensor calculation unit 16 extracts cluster transitions of a preset fixed length from the cluster transition sequence created by the cluster transition sequence creation unit 15, and then calculates the appearance of each cluster transition pattern in the past period and the current period. Calculate the probability, set the above cluster transition length (length of cluster transition) as the rank (that is, dimension), have the unique value of all clusters that appeared in the past period and the current period in each dimension index, cluster transition pattern A cluster transition tensor whose value is the probability of occurrence of is calculated for each of the past period and the current period, and an intermediate output is performed.
  • the change point score calculation unit 17 calculates the degree of change from the past period to the current period based on the cluster transition tensors of the past period and the current period calculated by the cluster transition tensor calculation unit 16, and calculates the degree of change from the past period to the current period. Calculate the distance of the cluster transition tensor in the period and perform the intermediate output.
  • the detection unit 18 detects a change point when the change point score calculated by the change point score calculation unit 17 exceeds a preset threshold. That is, the detection unit 18 detects a change point when the change point score of the system state calculated based on the data (converted data) at each time exceeds a preset threshold value.
  • the output unit 19 outputs the change points detected by the detection unit 18 .
  • FIG. 2 is a flowchart showing an example of change point detection processing according to the present embodiment.
  • M is the number of devices that make up the system (S)
  • K is the number of data items representing the system state at each point in time
  • N is the number of observation points of the time-series data. Assume that series data is configured.
  • each element of the M ⁇ K dimensional data at each point in time is K observed values representing the states of the M devices at that point in time.
  • Step S11 First, the input unit 11 inputs time-series data composed of N pieces of M ⁇ K (the number of devices ⁇ the number of items) dimensional data. That is, if Xn is the M ⁇ K-dimensional data at time n , the input unit 11 inputs time-series data ⁇ X 1 , . . . , X N ⁇ .
  • Step S14 Next, the clustering unit 14 constructs time-series data of the past period of length (e1-s1+1) extracted in step S13 and the current period of length (e2-s2+1) (e1- s1+e2-s2+2) pieces of M ⁇ K ⁇ W (number of devices ⁇ number of items ⁇ time window length) dimensional data are classified by a clustering method to obtain a cluster series corresponding to the time series data. Specifically, when the cluster to which the M ⁇ K ⁇ W-dimensional data Y n at the point in time n belongs is C n , the clustering unit 14 uses the time-series data ⁇ Y s1 , . A cluster sequence ⁇ C s2 , . . .
  • C e2 ⁇ is obtained from the cluster sequence ⁇ C s1 , .
  • clustering is a process of classifying (e1-s1+e2-s2+2) pieces of M ⁇ K ⁇ W dimensional data into the same cluster based on the mutual distance.
  • a cluster series is obtained by arranging the clusters assigned to each M ⁇ K ⁇ W dimensional data in chronological order.
  • a hierarchical method e.g., shortest distance method, longest distance method, group average method, Ward method, etc.
  • a non-hierarchical method e.g., K-Means method, etc.
  • Step S15 Next, the cluster transition sequence creation unit 15 generates M ⁇ K ⁇ W (number of devices ⁇ number of items ⁇ time window length) dimensions at each point in the past period [s1, e1] and the current period [s2, e2].
  • the clusters assigned to the data in step S14 are tracked in the time axis direction, and for each of the past period and the current period, a series of cluster transitions between different clusters is created, and for each cluster that constitutes this cluster transition series Gives the length of stay in the cluster.
  • a cluster sequence ⁇ C s1 , . . . , C e1 ⁇ obtained from time-series data ⁇ Y s1 , .
  • Step S16 Next, the cluster transition tensor calculation unit 16 extracts cluster transitions of a preset fixed length L from the cluster transition sequence created in step S15, and extracts each cluster transition in the past period and the current period.
  • the occurrence probability of the pattern is calculated, the cluster transition length L is defined as the rank (dimension), the unique value of all clusters that have appeared in the past period and the current period are held in the index of each dimension, and the appearance probability of the cluster transition pattern is the value.
  • the cluster transition tensor calculation unit 16 collects the (I-(L-1)) cluster transitions for each pattern, calculates the appearance probability, and calculates an L-dimensional cluster transition tensor based on this.
  • the appearance probability of a cluster transition pattern is a value obtained by dividing the appearance frequency of the cluster transition pattern by the total appearance frequency of all cluster transition patterns.
  • a value weighted by the length of stay of the cluster transition pattern may be used as the frequency of appearance of the cluster transition pattern.
  • the cluster transition tensor can be represented by a 3 ⁇ 3 array, and if the appearance probability of the cluster transition pattern ⁇ is 0.1, the index of the first axis (the first element of the cluster transition pattern) is the value ⁇ , An appearance probability of 0.1 is stored in the array element whose index on the second axis (the second element of the cluster transition pattern) takes the value ⁇ .
  • Step S17 Next, the change point score calculation unit 17 calculates the cluster transition tensor in the past period as the degree of change from the past period to the current period based on the cluster transition tensor in the past period and the current period calculated in step S16. and the distance of the cluster transition tensor in the current period.
  • M in the following inter-tensor distance is the number of unique values of all clusters appearing in the past period and the current period.
  • Step S18 Next, the detection unit 18 detects a change point when the change point score calculated in step S17 exceeds a preset threshold. That is, the detection unit 18 detects a change point when the change point score of the system state calculated based on the data (converted data) at each time exceeds a preset threshold value.
  • Step S19 Finally, the output unit 19 outputs the change point detected in step S18.
  • FIG. 3 is a hardware configuration diagram of the change point detection device.
  • the change point detection device 10 has a processor 101, a memory 102, an auxiliary storage device 103, a connection device 104, a communication device 105, and a drive device .
  • Each piece of hardware constituting the change point detection device 10 is interconnected via a bus 107 .
  • the processor 101 plays the role of a control unit that controls the entire change point detection device 10, and has various computing devices such as a CPU (Central Processing Unit).
  • the processor 101 reads various programs onto the memory 102 and executes them.
  • the processor 101 may include a GPGPU (General-purpose computing on graphics processing units).
  • the memory 102 has main storage devices such as ROM (Read Only Memory) and RAM (Random Access Memory).
  • the processor 101 and the memory 102 form a so-called computer, and the processor 101 executes various programs read onto the memory 102, thereby realizing various functions of the computer.
  • the auxiliary storage device 103 stores various programs and various information used when the various programs are executed by the processor 101 .
  • connection device 104 is a connection device that connects an external device (eg, the display device 110, the operation device 111) and the change point detection device 10.
  • the communication device 105 is a communication device for transmitting and receiving various information to and from other devices.
  • the drive device 106 is a device for setting the recording medium 130 .
  • the recording medium 130 here includes media for optically, electrically, or magnetically recording information such as CD-ROMs (Compact Disc Read-Only Memory), flexible discs, magneto-optical discs, and the like.
  • the recording medium 130 may also include a semiconductor memory that electrically records information, such as a ROM (Read Only Memory) and a flash memory.
  • auxiliary storage device 103 Various programs to be installed in the auxiliary storage device 103 are installed by, for example, setting the distributed recording medium 130 in the drive device 106 and reading the various programs recorded in the recording medium 130 by the drive device 106. be done. Alternatively, various programs installed in the auxiliary storage device 103 may be installed by being downloaded from the network via the communication device 105 .
  • the change point detection device 10 uses the time-series data representing the system state at each point in time of the system (S) configured by one or more devices, When a change occurs, the point of occurrence can be detected as a change point.
  • the change point detection device 10 since the change point detection device 10 according to the present embodiment is based on the premise of classifying the system state at each point in time using a clustering method, data that does not satisfy the stationarity constraint or the iid constraint, such as showing periodic fluctuations, can also be used. It can target time-series data including Furthermore, the change point detection device 10 according to the present embodiment considers the state transition of the system (S) with the passage of time (that is, the transition of the cluster to which the system state belongs and the stay period at each point in time). The periodic variation of S) is modeled, and changes including changes in time-varying patterns, such as changes in periodic variation, can be detected.
  • S state transition of the system
  • the periodic variation of S is modeled, and changes including changes in time-varying patterns, such as changes in periodic variation, can be detected.
  • the present invention is not limited to the above-described embodiments, and may be configured or processed (operations) as described below.
  • the change point detection device 10 can be realized by a computer and a program, but it is also possible to record this program on a (non-temporary) recording medium or provide it through a network such as the Internet.
  • a change point detection device comprising a processor, The processor Time-series data representing the system state at each point in time of a system composed of one or more devices, composed of data of dimensions of the number of devices constituting the system x the number of items representing the state of the device an input step for inputting time series data; a time window generation step of generating converted data by converting the time-series data at each time point from data of dimensions of number of devices ⁇ number of items to data of dimensions of number of devices ⁇ number of items ⁇ time window length; a detection step of detecting a change point when the change point score of the system state calculated based on the conversion data at each time point exceeds a preset threshold value; A change point detector that performs
  • the change point detection device according to additional item 1,
  • the processor a clustering step of classifying the dimensional data of the number of devices x number of items x time window length at each time point constituting the time-series data for a preset past period and current period by a clustering method;
  • the clusters assigned to the dimensional data of the number of devices x number of items x time window length are tracked in the time axis direction, and for each of the past period and the current period, a series of cluster transitions between different clusters is created, and a cluster transition sequence creating step of assigning a stay period in the cluster to each cluster constituting a cluster transition sequence;
  • After extracting cluster transitions of a preset fixed length from the series of cluster transitions the probability of occurrence of each cluster transition pattern in the past period and the current period is calculated, and the length of the cluster transition is used as a dimension, and the past A cluster transition tensor that has a unique value of all clusters appearing in the period and the current period in each dimension index and calculates
  • Appendix 4 A non-transitory recording medium in which a program for causing a computer to execute the method according to claim 3 is recorded.

Landscapes

  • Engineering & Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Software Systems (AREA)
  • Artificial Intelligence (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Evolutionary Computation (AREA)
  • Medical Informatics (AREA)
  • Computing Systems (AREA)
  • Mathematical Physics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

本開示は、周期変動を示すなど定常性制約やiid制約を満たさないデータも含めた時系列データを対象に、周期変動の変化など時間変化パターンの変化も含め何らかの変化が発生した際に、その発生時点を変化点として検知することを目的とする。　そこで、本開示内容は、１つ又は複数の装置で構成されるシステムの各時点におけるシステム状態を表す時系列データであって、前記システムを構成する装置数×前記装置の状態を表す項目数の次元のデータで構成される時系列データを入力する入力部と、前記各時点における前記時系列データを装置数×項目数の次元のデータから、装置数×項目数×時間窓長の次元のデータに変換することで変換データを生成する時間窓生成部と、前記各時点における前記変換データに基づいて算出された前記システム状態の変化点スコアがあらかじめ設定された閾値を超えた場合に変化点として検知する検知部と、を有する変化点検知装置である。

Description

変化点検知装置、変化点検知方法及びプログラム
　本開示内容は、変化点検知装置、変化点検知方法及びプログラムに関する。
　１つ又は複数の装置で構成されるシステムの各時点におけるシステム状態を表す時系列データを用いて、当該システムのシステム状態の変化点を検知する技術が従来から知られている。ここで、「システム状態」とは、「アクセス数」や「ユーザ数」などの量的変数により表されるシステムの稼働状態のことである。
　変化点の発生位置に関する正解ラベルが付与されていない時系列データを対象に変化点を検知する技術としては、非特許文献１乃至４に記載されている技術が知られている。
　非特許文献１は、部分空間法を用いて部分時系列で構成される部分空間同士の距離を評価することで変化度を計算する方法を提案している。これは、過去期間と現在期間のそれぞれについて、部分時系列（時系列から切り出した時間窓）を束ねた行列を生成し、特異値分解により特徴的なパターンを抽出し、この特徴的なパターン間の距離を評価する方法である。
　非特許文献２は、確率モデルを用いて前の変化点以降に観測されたデータに基づき新たな区間の確率分布を推定する方法を提案している。これは、ベイズ理論に基づき、最後の変化点からの連長（次の変化点までの経過時間）の確率分布を推定することによって変化点を検知する方法である。なお、「ベイズ理論」は、「何かが起こる可能性は、その事柄の過去の発生頻度を使ってほぼ推測ができる」ということを示す理論である。
　非特許文献３は、クラスタリングを用いて時系列データを状態分類し、新たな観測値がいずれの既存クラスタにも適合しない場合に変化が発生したものと判断する方法を提案している。これは、新たな観測値と既存クラスタのセントロイドの間のユークリッド距離が当該クラスタの半径を上回るか否かをすべての既存クラスタについて判定し、すべて上回る場合に変化点として検知する方法である。
　非特許文献４にある二段階学習に基づくオンライン変化検知は、２つの連続する区間の確率密度に有意差があるか否かを尤度比に基づき判定する尤度比検定の一種であり、自己回帰モデルを二段階学習することにより外れ値を除去しつつ変化点スコアを計算する方法を提案している。これは、具体的に、まず１段階目の学習として、直前時点までに観測された時系列から自己回帰モデルに基づく確率密度関数を学習し、新たに観測されたデータについて前記確率密度関数の下での対数損失関数を外れスコアとして算出する方法である。さらに、これは、この外れスコア系列を平滑化した上で、次に２段階目の学習として、直前時点までに算出された平滑化済みの外れスコア系列から同じく自己回帰モデルに基づく確率密度関数を学習し、新たに観測されたデータから算出された外れスコアについて前記確率密度関数の下での対数損失関数を算出し、さらに平滑化したものを変化点スコアとする方法である。
　また、類似する技術として、１つ又は複数の装置で構成されるシステムの各時点におけるシステム状態を表す時系列データを用いて、当該システムの非定常変動を検知する技術が知られており、この技術が非特許文献５に記載されている。これは、具体的には、クラスタリングを用いて時系列データを状態分類した上で、各時点に割り当てられたクラスタを時間軸方向に追跡して異なるクラスタ間におけるクラスタ遷移を抽出する方法である。さらにこれは、過去一定期間におけるクラスタ遷移パターンごとの出現頻度を算出しておき、あらたに観測されたクラスタ遷移パターンの過去期間における出現頻度があらかじめ設定した閾値を下回る場合に非定常変動として検知する方法である。
T. Ide and K. Tsuda, "Change-Point Detection Using Krylov Subspace Learning," in Procs. of the SIAM International Conference on Data Mining, Apr. 2007. R. P. Adams and D. J. C. MacKay, "Bayesian Online Changepoint Detection," arXiv:0710.3742, Oct. 2007. D. H. Tran, "Automated Change Detection and Reactive Clustering in Multivariate Streaming Data," arXiv:1311.0505, Nov. 2013. 山西, "異常検知：外れ値検知と変化検知," REAJ誌2015 Vol.37, No. 3, 2015. 高橋, 池上, "多次元時系列データにおける非定常変動検知技術の提案," 信学技報, CQ2020-32, pp.57-62, July 2020.
　ところが、非特許文献１が提案する部分空間法による変化点検知技術は、検知対象とする時系列が定常過程でなければならないという制約がある。すなわち、対象時系列の期待値と自己共分散が時間によらず一定であるという弱定常性を満たす必要がある。
　また、非特許文献２が提案するベイズ理論に基づく変化点検知技術は、検知対象とする時系列が独立同分布（iid: independently and identically distributed）でなければならないという制約がある。すなわち、時系列を構成する各時点のデータが互いに独立に同一の確率分布に従っている必要がある。しかし、ネットワークシステムに代表される多くのシステムで観測される時系列データは、時間帯変動、曜日変動、月変動などの周期変動を示すものが多く、さらに周期の異なる複数種類の周期変動が混在しているものも多いため、前記の定常性制約やiid制約などの制約を受ける変化点検知技術を適用することができない。
　一方、非特許文献３が提案するクラスタリングによる変化点検知技術と非特許文献４が提案する二段階学習に基づくオンライン変化検知技術は、対象時系列が定常性制約やiid制約などの制約を受けない点で有望と考えられる。しかし、非特許文献３が提案するクラスタリングによる変化点検知技術は、時系列データから切り出した時点ごとのスナップショットのデータを状態分類し、分類された状態が既存の状態と異なるか否かの判定を行っており、時間軸を考慮していない。すなわち、多くのシステムで観測される周期変動を示す時系列データのように、状態の時間変化が一定のパターンに従うような時系列データにおいて、この時間変化パターンがある瞬間を境に変化するような場合にこの変化点を検知することができない。
　さらに、非特許文献４が提案する二段階学習に基づくオンライン変化検知技術は、自己回帰モデルに基づく方法であるため、時間軸を考慮していると言える。したがって、時間変化パターンがある瞬間を境に変化するような時系列データに対しても有望と考えられる。しかし、時間帯変動、曜日変動、月変動など周期の異なる複数種類の周期変動が混在しているような時系列データについては、自己回帰モデルによる対応は困難である。
　また、非特許文献５が提案する非定常変動検知技術は、対象時系列が制約を受けないクラスタリングをベースとしており、かつ時間軸方向にクラスタ遷移を追跡する方法により時間軸を考慮している技術である。しかし、当該技術は過去一定期間において算出された出現頻度があらかじめ設定された閾値を下回るクラスタ遷移パターンを非定常変動として検知する技術であり、個別のクラスタ遷移が過去実績と比べて異常状態である（出現頻度が低い）か否かを判定するに過ぎず、継続的な異常状態のはじまりとも言える変化点を検知するものではない。
　本発明は上記の点を鑑みてなされたものであり、周期変動を示すなど定常性制約やiid制約を満たさないデータも含めた時系列データを対象に、周期変動の変化など時間変化パターンの変化も含め何らかの変化が発生した際に、その発生時点を変化点として検知することを目的とする。
　上記目的を達成するため、請求項１に係る発明は、１つ又は複数の装置で構成されるシステムの各時点におけるシステム状態を表す時系列データであって、前記システムを構成する装置数×前記装置の状態を表す項目数の次元のデータで構成される時系列データを入力する入力部と、前記各時点における前記時系列データを装置数×項目数の次元のデータから、装置数×項目数×時間窓長の次元のデータに変換することで変換データを生成する時間窓生成部と、前記各時点における前記変換データに基づいて算出された前記システム状態の変化点スコアがあらかじめ設定された閾値を超えた場合に変化点として検知する検知部と、を有する変化点検知装置である。
　以上説明したように本発明によれば、周期変動を示すなど定常性制約やiid制約を満たさない時系列データに対しても、周期変動の変化など時間変化パターンの変化も含め何らかの変化が発生した際に、その発生時点を変化点として検知することができるという効果を奏する。
本実施形態に係る変化点検知装置の機能構成の一例を示す図である。 本実施形態に係る変化点検知処理の一例を示すフローチャートである。 本実施形態に係る変化点検知装置のハードウェア構成の一例を示す図である。
　以下、本発明の一実施形態について説明する。本実施形態では、１つ又は複数の装置で構成されるシステム（Ｓ）の各時点におけるシステム状態を表す時系列データを用いて、システム状態に何らかの変化が発生した際に、その発生時点を変化点として検知することが可能な変化点検知装置１０について説明する。ここで、「システム状態」とは、「アクセス数」や「ユーザ数」などの量的変数により表されるシステムの稼働状態のことである。
　〔機能構成〕
　まず、本実施形態に係る変化点検知装置１０の機能構成について、図１を参照しながら説明する。図１は、本実施形態に係る変化点検知装置の機能構成の一例を示す図である。
　図１に示すように、本実施形態に係る変化点検知装置１０は、入力部１１と、時間窓生成部１２と、期間設定部１３と、クラスタリング部１４と、クラスタ遷移系列作成部１５と、クラスタ遷移テンソル算出部１６と、変化点スコア算出部１７と、検知部１８と、出力部１９とを有する。なお、以下に示されている「装置数」及び「装置の状態」の「装置」は変化点検知装置１０によって変化点の検知対象となるシステムを構成する装置を示す。
　入力部１１は、１つ又は複数の装置で構成されるシステム（Ｓ）の各時点におけるシステム状態を表す時系列データであって、システム（Ｓ）を構成する（装置数×装置の状態を表す項目数）次元のデータで構成される時系列データを入力する。
　時間窓生成部１２は、入力部１１により入力された時系列データを固定長の時間窓で区切り、各時点のデータを（装置数×項目数）次元のデータから、（装置数×項目数×時間窓長）次元のデータに変換して変換データを生成し、中間出力を行う。
　期間設定部１３は、時間窓生成部１２により生成された（装置数×項目数×時間窓長）次元の時系列データから、あらかじめ設定された過去期間と現在期間の時系列データを抽出して、中間出力を行う。
　クラスタリング部１４は、期間設定部１３により抽出された過去期間と現在期間の時系列データを構成する各時点の（装置数×項目数×時間窓長）次元のデータをクラスタリング手法により状態分類して、中間出力を行う。
　クラスタ遷移系列作成部１５は、過去期間と現在期間の各時点における（装置数×項目数×時間窓長）次元のデータに対しクラスタリング部１４が割り当てたクラスタを時間軸方向に追跡し、過去期間と現在期間のそれぞれについて、異なるクラスタ間におけるクラスタ遷移の系列を作成すると同時に、このクラスタ遷移系列を構成する各クラスタに対し当該クラスタにおける滞在期間を付与して、中間出力を行う。
　クラスタ遷移テンソル算出部１６は、クラスタ遷移系列作成部１５により作成されたクラスタ遷移系列から、あらかじめ設定された固定長のクラスタ遷移を抽出した上で、過去期間と現在期間における各クラスタ遷移パターンの出現確率を算出し、上記クラスタ遷移長（クラスタ遷移の長さ）を階数（即ち、次元）とし、過去期間と現在期間に出現したすべてのクラスタのユニーク値を各次元のインデックスに持ち、クラスタ遷移パターンの出現確率を値に持つクラスタ遷移テンソルを過去期間と現在期間のそれぞれについて算出して、中間出力を行う。
　変化点スコア算出部１７は、クラスタ遷移テンソル算出部１６により算出された過去期間と現在期間それぞれのクラスタ遷移テンソルに基づき、過去期間から現在期間にかけての変化度として、過去期間におけるクラスタ遷移テンソルと現在期間におけるクラスタ遷移テンソルの距離を算出して、中間出力を行う。
　検知部１８は、変化点スコア算出部１７により算出された変化点スコアがあらかじめ設定された閾値を超えた場合に変化点として検知する。即ち、検知部１８は、各時点におけるデータ（変換データ）に基づいて算出されたシステム状態の変化点スコアがあらかじめ設定された閾値を超えた場合に変化点として検知する。
　出力部１９は、検知部１８により検知された変化点を出力する。
　〔変化点検知処理〕
　次に、本実施形態に係る変化点検知処理（手順）について、図２を参照しながら説明する。図２は、本実施形態に係る変化点検知処理の一例を示すフローチャートである。
　以降では、システム（Ｓ）を構成する装置数をＭ、各時点におけるシステム状態を表すデータの項目数をＫ、時系列データの観測時点数をＮとして、Ｎ個のＭ×Ｋ次元データで時系列データが構成されているものとする。
　なお、各時点におけるＭ×Ｋ次元データの各要素は、当該時点におけるＭ個の装置の状態を表すＫ個の観測値である。具体的には、或る時点におけるＭ×Ｋ次元データを［ｘ１，・・・，ｘＫ，ｘＫ＋１，・・・，ｘ２Ｋ，・・・，ｘ（Ｍ－１）Ｋ＋１，・・・，ｘＭＫ］とした場合、例えば、ｍ＝１，・・・，Ｍに対してｘ（ｍ－１）Ｋ＋１，・・・，ｘｍＫは当該時点におけるｍ番目の装置のＫ個の観測値である。
　ステップＳ１１：まず、入力部１１は、Ｎ個のＭ×Ｋ（装置数×項目数）次元データで構成される時系列データを入力する。すなわち、時点ｎにおけるＭ×Ｋ次元データをＸｎとすれば、入力部１１は、時系列データ｛Ｘ１，・・・，ＸＮ｝を入力する。
　ステップＳ１２：次に、時間窓生成部１２は、ステップＳ１１で入力された時系列データを固定長Ｗの時間窓で区切ることによって、各時点のデータをＭ×Ｋ（装置数×項目数）次元のデータからＭ×Ｋ×Ｗ（装置数×項目数×時間窓長）次元のデータに変換して変換データを生成し、中間出力を行う。具体的には、時点ｎ－（Ｗ－１），ｎ－（Ｗ－２），・・・，ｎそれぞれのＭ×Ｋ次元データＸｎ－（Ｗ－１），Ｘｎ－（Ｗ－２），・・・，Ｘｎで構成されるＭ×Ｋ×Ｗ次元ベクトルＹｎ＝（Ｘｎ－（Ｗ－１），Ｘｎ－（Ｗ－２），・・・，Ｘｎ）を時点ｎのＭ×Ｋ×Ｗ次元データとする。なお、元のＭ×Ｋ次元データＸｎが時点ｎ＝１，・・・，Ｎについて観測されている場合、変換後のＭ×Ｋ×Ｗ次元データＹｎは時点ｎ＝Ｗ，・・・，Ｎについて得られることになる。
　ステップＳ１３：次に、期間設定部１３は、ステップＳ１２で生成されたＭ×Ｋ×Ｗ（装置数×項目数×時間窓長）次元の時系列データから、あらかじめ設定された過去期間と現在期間の時系列データを抽出する。具体的には、過去期間を［ｓ１，ｅ１］、現在期間を［ｓ２，ｅ２］とした場合、時点ｎ＝Ｗ，・・・，ＮのＭ×Ｋ×Ｗ次元データＹｎから過去期間のデータ｛Ｙｓ１，・・・，Ｙｅ１｝と現在期間のデータ｛Ｙｓ２，・・・，Ｙｅ２｝を抽出する。
　ステップＳ１４：次に、クラスタリング部１４は、ステップＳ１３で抽出された長さ（ｅ１－ｓ１＋１）時点の過去期間と長さ（ｅ２－ｓ２＋１）時点の現在期間の時系列データを構成する（ｅ１－ｓ１＋ｅ２－ｓ２＋２）個のＭ×Ｋ×Ｗ（装置数×項目数×時間窓長）次元データをクラスタリング手法により状態分類することで、当該時系列データに対応するクラスタ系列を得る。具体的には、クラスタリング部１４は、時点ｎのＭ×Ｋ×Ｗ次元データＹｎが属するクラスタをＣｎとした場合、過去期間の時系列データ｛Ｙｓ１，・・・，Ｙｅ１｝からクラスタ系列｛Ｃｓ１，・・・，Ｃｅ１｝、現在期間の時系列データ｛Ｙｓ２，・・・，Ｙｅ２｝からクラスタ系列｛Ｃｓ２，・・・，Ｃｅ２｝が得られる。なお、クラスタリングは、（ｅ１－ｓ１＋ｅ２－ｓ２＋２）個のＭ×Ｋ×Ｗ次元データを互いの距離に基づいて近いデータ同士を同一クラスタに分類する処理である。各Ｍ×Ｋ×Ｗ次元データに割り当てられたクラスタを時系列順に並べることでクラスタ系列が得られる。クラスタリング手法としては、階層的手法（例えば、最短距離法、最長距離法、群平均法、ウォード法等）が用いられてもよいし、非階層的手法（例えば、Ｋ－Ｍｅａｎｓ法等）が用いられてもよい。
　ステップＳ１５：次に、クラスタ遷移系列作成部１５は、過去期間［ｓ１，ｅ１］と現在期間［ｓ２，ｅ２］の各時点におけるＭ×Ｋ×Ｗ（装置数×項目数×時間窓長）次元データに対しステップＳ１４で割り当てたクラスタを時間軸方向に追跡し、過去期間と現在期間のそれぞれについて、異なるクラスタ間におけるクラスタ遷移の系列を作成すると共に、このクラスタ遷移系列を構成する各クラスタに対し当該クラスタにおける滞在期間を付与する。具体的に過去期間［ｓ１，ｅ１］の時系列データ｛Ｙｓ１，・・・，Ｙｅ１｝から得られたクラスタ系列｛Ｃｓ１，・・・，Ｃｅ１｝を例にとり説明すると、区間［ｓ１，ｅ１］で異なるクラスタ間におけるクラスタ遷移が発生した時点をτｉ（ｉ＝１，２，・・・，Ｉ）（ただし、τ１＝ｓ１）、時点τｉにおける遷移後クラスタのクラスタをｃ（τｉ）とした場合、これを時系列順に並べることで長さＩのクラスタ遷移系列ｃ（τ１）→ｃ（τ２）→・・・→ｃ（τＩ）が得られる。また、このクラスタ遷移系列を構成する各クラスタｃ（τｉ）に対し、当該クラスタｃ（τｉ）における滞在期間ｄ（τｉ）＝τｉ＋１－τｉ（ただし、τＩ＋１＝ｅ１）を付与することにより、滞在期間つきクラスタ遷移系列ｃ（τ１）｜ｄ（τ１）→ｃ（τ２）｜ｄ（τ２）→・・・→ｃ（τＩ）｜ｄ（τＩ）が得られる。
　ステップＳ１６：次に、クラスタ遷移テンソル算出部１６は、ステップＳ１５で作成されたクラスタ遷移系列から、あらかじめ設定された固定長Ｌのクラスタ遷移を抽出した上で、過去期間と現在期間における各クラスタ遷移パターンの出現確率を算出し、上記クラスタ遷移長Ｌを階数（次元）とし、過去期間と現在期間に出現したすべてのクラスタのユニーク値を各次元のインデックスに持ち、クラスタ遷移パターンの出現確率を値に持つクラスタ遷移テンソルを過去期間と現在期間のそれぞれについて算出する。具体的に過去期間［ｓ１，ｅ１］の時系列データ｛Ｙｓ１，・・・，Ｙｅ１｝から得られた長さＩのクラスタ遷移系列ｃ（τ１）→ｃ（τ２）→・・・→ｃ（τＩ）を例にとり説明すると、このクラスタ遷移系列から長さＬ（ただし、Ｌ≦Ｉ）のクラスタ遷移は（Ｉ－（Ｌ－１））本抽出することができ、ｃ（τｉ－（Ｌ－１））→ｃ（τｉ－（Ｌ－２））→・・・→ｃ（τｉ）（ｉ＝Ｌ，・・・，Ｉ）で表される。クラスタ遷移テンソル算出部１６は、この（Ｉ－（Ｌ－１））本のクラスタ遷移をパターンごとにまとめて出現確率を算出し、これに基づきＬ次元のクラスタ遷移テンソルを算出する。ここで、クラスタ遷移パターンの出現確率とは、当該クラスタ遷移パターンの出現度数をすべてのクラスタ遷移パターンの出現度数合計で割った値である。
　なお、クラスタ遷移パターンの出現度数は、当該クラスタ遷移パターンの滞在期間で重みづけした値を用いても良い。以下、クラスタ遷移パターンの出現確率をテンソルに格納する方法について、簡単のため、Ｌ＝２、過去期間と現在期間を通じて出現したすべてのクラスタのユニーク値がα、β、γだった場合の例で説明する。このとき、クラスタ遷移テンソルは２次元で、各次元のインデックスは３つの値α、β、γをとる。クラスタ遷移テンソルは３×３の配列により表すことができ、クラスタ遷移パターンα→βの出現確率が０．１だった場合、第１軸のインデックス（クラスタ遷移パターンの第１要素）が値α、第２軸のインデックス（クラスタ遷移パターンの第２要素）が値βをとる配列要素に出現確率０．１を格納する。
　ステップＳ１７：次に、変化点スコア算出部１７は、ステップＳ１６で算出された過去期間と現在期間それぞれのクラスタ遷移テンソルに基づき、過去期間から現在期間にかけての変化度として、過去期間におけるクラスタ遷移テンソルと現在期間におけるクラスタ遷移テンソルの距離を算出する。過去期間のクラスタ遷移テンソルＤ１の要素をｄ１ ｉ１，・・・，ｉＬ、現在期間のクラスタ遷移テンソルＤ２の要素をｄ２ ｉ１，・・・，ｉＬとした場合、両者間の距離はたとえば以下の平均平方二乗誤差により表すことができる。
（Σｌ＝１ ＬΣｍ＝１ Ｍ（ｄ２ ｉ１，・・・，ｉＬ－ｄ１ ｉ１，・・・，ｉＬ）２／ＭＬ）１／２
　なお、下記テンソル間距離におけるＭは、過去期間と現在期間を通じて出現したすべてのクラスタのユニーク値の個数である。
　ステップＳ１８：次に、検知部１８は、ステップＳ１７で算出された変化点スコアがあらかじめ設定された閾値を超えた場合に変化点として検知する。即ち、検知部１８は、各時点におけるデータ（変換データ）に基づいて算出されたシステム状態の変化点スコアがあらかじめ設定された閾値を超えた場合に変化点として検知する。
　ステップＳ１９：最後に、出力部１９は、ステップＳ１８で検知された変化点を出力する。
　〔ハードウェア構成〕
　続いて、図３を用いて、変化点検知装置１０のハードウェア構成について説明する。図３は、変化点検知装置のハードウェア構成図である。
　図３に示されているように、変化点検知装置１０は、プロセッサ１０１、メモリ１０２、補助記憶装置１０３、接続装置１０４、通信装置１０５、ドライブ装置１０６を有する。なお、変化点検知装置１０を構成する各ハードウェアは、バス１０７を介して相互に接続される。
　プロセッサ１０１は、変化点検知装置１０全体の制御を行う制御部の役割を果たし、ＣＰＵ（Central Processing Unit）等の各種演算デバイスを有する。プロセッサ１０１は、各種プログラムをメモリ１０２上に読み出して実行する。なお、プロセッサ１０１には、ＧＰＧＰＵ(General-purpose computing on graphics processing units)が含まれていてもよい。
　メモリ１０２は、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）等の主記憶デバイスを有する。プロセッサ１０１とメモリ１０２とは、いわゆるコンピュータを形成し、プロセッサ１０１が、メモリ１０２上に読み出した各種プログラムを実行することで、当該コンピュータは各種機能を実現する。
　補助記憶装置１０３は、各種プログラムや、各種プログラムがプロセッサ１０１によって実行される際に用いられる各種情報を格納する。
　接続装置１０４は、外部装置（例えば、表示装置１１０、操作装置１１１）と変化点検知装置１０とを接続する接続デバイスである。
　通信装置１０５は、他の装置との間で各種情報を送受信するための通信デバイスである。
　ドライブ装置１０６は記録媒体１３０をセットするためのデバイスである。ここでいう記録媒体１３０には、ＣＤ－ＲＯＭ(Compact Disc Read-Only Memory)、フレキシブルディスク、光磁気ディスク等のように情報を光学的、電気的あるいは磁気的に記録する媒体が含まれる。また、記録媒体１３０には、ＲＯＭ(Read Only Memory)、フラッシュメモリ等のように情報を電気的に記録する半導体メモリ等が含まれていてもよい。
　なお、補助記憶装置１０３にインストールされる各種プログラムは、例えば、配布された記録媒体１３０がドライブ装置１０６にセットされ、当該記録媒体１３０に記録された各種プログラムがドライブ装置１０６により読み出されることでインストールされる。あるいは、補助記憶装置１０３にインストールされる各種プログラムは、通信装置１０５を介してネットワークからダウンロードされることで、インストールされてもよい。
　〔実施形態の主な効果〕
　以上のように、本実施形態に係る変化点検知装置１０は、１つ又は複数の装置で構成されるシステム（Ｓ）の各時点におけるシステム状態を表す時系列データを用いて、システム状態に何らかの変化が発生した際に、その発生時点を変化点として検知することができる。
　しかも、本実施形態に係る変化点検知装置１０は、各時点におけるシステム状態をクラスタリング手法により状態分類する方法を前提としていることで、周期変動を示すなど定常性制約やiid制約を満たさないデータも含めた時系列データを対象とすることができる。さらに、本実施形態に係る変化点検知装置１０は、時間経過に伴うシステム（Ｓ）の状態遷移（つまり、各時点でシステム状態が属するクラスタとその滞在期間の遷移）を考慮することでシステム（Ｓ）の周期変動をモデル化しており、周期変動の変化など時間変化パターンの変化も含めた変化を検知することができる。
　〔補足〕
　本発明は上述の実施形態に限定されるものではなく、以下に示すような構成又は処理（動作）であってもよい。
　変化点検知装置１０はコンピュータとプログラムによっても実現できるが、このプログラムを（非一時的）記録媒体に記録することも、インターネット等のネットワークを通して提供することも可能である。
　〔付記項〕
　本実施形態は、以下に示すように表現することが可能である。
　〔付記項１〕
　プロセッサを有する変化点検知装置であって、
　前記プロセッサは、
　１つ又は複数の装置で構成されるシステムの各時点におけるシステム状態を表す時系列データであって、前記システムを構成する装置数×前記装置の状態を表す項目数の次元のデータで構成される時系列データを入力する入力ステップと、
　前記各時点における前記時系列データを装置数×項目数の次元のデータから、装置数×項目数×時間窓長の次元のデータに変換することで変換データを生成する時間窓生成ステップと、
　前記各時点における前記変換データに基づいて算出された前記システム状態の変化点スコアがあらかじめ設定された閾値を超えた場合に変化点として検知する検知ステップと、
　を実行する変化点検知装置。
　〔付記項２〕
　付記項１に記載の変化点検知装置であって、
　前記プロセッサは、
　あらかじめ設定された過去期間と現在期間の前記時系列データを構成する各時点の装置数×項目数×時間窓長の次元データをクラスタリング手法により状態分類するクラスタリングステップと、
　前記装置数×項目数×時間窓長の次元データに対し割り当てられたクラスタを時間軸方向に追跡し、過去期間と現在期間のそれぞれについて、異なるクラスタ間におけるクラスタ遷移の系列を作成すると共に、当該クラスタ遷移の系列を構成する各クラスタに対し当該クラスタにおける滞在期間を付与するクラスタ遷移系列作成ステップと、
　前記クラスタ遷移の系列から、あらかじめ設定された固定長のクラスタ遷移を抽出した上で、過去期間と現在期間における各クラスタ遷移パターンの出現確率を算出し、前記クラスタ遷移の長さを次元とし、過去期間と現在期間に出現したすべてのクラスタのユニーク値を各次元のインデックスに持ち、前記各クラスタ遷移パターンの出現確率を値に持つクラスタ遷移テンソルを過去期間と現在期間のそれぞれについて算出するクラスタ遷移テンソル算出ステップと、
　過去期間と現在期間それぞれについて算出された前記クラスタ遷移テンソルに基づき、過去期間から現在期間にかけての変化度として、過去期間における前記クラスタ遷移テンソルと現在期間における前記クラスタ遷移テンソルの距離を算出する変化点スコア算出ステップと、
　を実行する変化点検知装置。
　〔付記項３〕
　１つ又は複数の装置で構成されるシステムの各時点におけるシステム状態を表す時系列データであって、前記システムを構成する装置数×前記装置の状態を表す項目数の次元のデータで構成される時系列データを入力する入力手順と、
　前記各時点における前記時系列データを装置数×項目数の次元のデータから、装置数×項目数×時間窓長の次元のデータに変換することで変換データを生成する時間窓生成手順と、
　前記各時点における前記変換データに基づいて算出された前記システム状態の変化点スコアがあらかじめ設定された閾値を超えた場合に変化点として検知する検知手順と、
　をコンピュータが実行する変化点検知方法。
　〔付記項４〕
　コンピュータに、付記項３に記載の方法を実行させるプログラムが記録された非一時的記録媒体。
１０　変化点検知装置
１１　入力部
１２　時間窓生成部
１３　期間設定部
１４　クラスタリング部
１５　クラスタ遷移系列作成部
１６　クラスタ遷移テンソル算出部
１７　変化点スコア算出部
１８　検知部
１９　出力部

Claims (4)

  1. 　１つ又は複数の装置で構成されるシステムの各時点におけるシステム状態を表す時系列データであって、前記システムを構成する装置数×前記装置の状態を表す項目数の次元のデータで構成される時系列データを入力する入力部と、
    　前記各時点における前記時系列データを装置数×項目数の次元のデータから、装置数×項目数×時間窓長の次元のデータに変換することで変換データを生成する時間窓生成部と、
    　前記各時点における前記変換データに基づいて算出された前記システム状態の変化点スコアがあらかじめ設定された閾値を超えた場合に変化点として検知する検知部と、
    　を有する変化点検知装置。
  2. 　請求項１に記載の変化点検知装置であって、
    　あらかじめ設定された過去期間と現在期間の前記時系列データを構成する各時点の装置数×項目数×時間窓長の次元データをクラスタリング手法により状態分類するクラスタリング部と、
    　前記装置数×項目数×時間窓長の次元データに対し割り当てられたクラスタを時間軸方向に追跡し、過去期間と現在期間のそれぞれについて、異なるクラスタ間におけるクラスタ遷移の系列を作成すると共に、当該クラスタ遷移の系列を構成する各クラスタに対し当該クラスタにおける滞在期間を付与するクラスタ遷移系列作成部と、
    　前記クラスタ遷移の系列から、あらかじめ設定された固定長のクラスタ遷移を抽出した上で、過去期間と現在期間における各クラスタ遷移パターンの出現確率を算出し、前記クラスタ遷移の長さを次元とし、過去期間と現在期間に出現したすべてのクラスタのユニーク値を各次元のインデックスに持ち、前記各クラスタ遷移パターンの出現確率を値に持つクラスタ遷移テンソルを過去期間と現在期間のそれぞれについて算出するクラスタ遷移テンソル算出部と、
    　過去期間と現在期間それぞれについて算出された前記クラスタ遷移テンソルに基づき、過去期間から現在期間にかけての変化度として、過去期間における前記クラスタ遷移テンソルと現在期間における前記クラスタ遷移テンソルの距離を算出する変化点スコア算出部と、
    　を有する変化点検知装置。
  3. 　１つ又は複数の装置で構成されるシステムの各時点におけるシステム状態を表す時系列データであって、前記システムを構成する装置数×前記装置の状態を表す項目数の次元のデータで構成される時系列データを入力する入力手順と、
    　前記各時点における前記時系列データを装置数×項目数の次元のデータから、装置数×項目数×時間窓長の次元のデータに変換することで変換データを生成する時間窓生成手順と、
    　前記各時点における前記変換データに基づいて算出された前記システム状態の変化点スコアがあらかじめ設定された閾値を超えた場合に変化点として検知する検知手順と、
    　をコンピュータが実行する変化点検知方法。
  4. 　コンピュータに、請求項３に記載の方法を実行させるプログラム。
PCT/JP2021/041966 2021-11-15 2021-11-15 変化点検知装置、変化点検知方法及びプログラム WO2023084787A1 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
US18/702,548 US20240411780A1 (en) 2021-11-15 2021-11-15 Change-point detection apparatus, change-point detection method and program
PCT/JP2021/041966 WO2023084787A1 (ja) 2021-11-15 2021-11-15 変化点検知装置、変化点検知方法及びプログラム
JP2023559393A JPWO2023084787A1 (ja) 2021-11-15 2021-11-15

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/JP2021/041966 WO2023084787A1 (ja) 2021-11-15 2021-11-15 変化点検知装置、変化点検知方法及びプログラム

Publications (1)

Publication Number Publication Date
WO2023084787A1 true WO2023084787A1 (ja) 2023-05-19

Family

ID=86335495

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2021/041966 WO2023084787A1 (ja) 2021-11-15 2021-11-15 変化点検知装置、変化点検知方法及びプログラム

Country Status (3)

Country Link
US (1) US20240411780A1 (ja)
JP (1) JPWO2023084787A1 (ja)
WO (1) WO2023084787A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN116340796A (zh) * 2023-05-22 2023-06-27 平安科技（深圳）有限公司 时序数据分析方法、装置、设备及存储介质

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2012204894A (ja) * 2011-03-24 2012-10-22 Toshiba Corp 情報推薦装置

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
KASUGA, AKIRA ET AL.: "Method for Detecting Explicit Structural Changes in Time Series Data", IEICE TECHNICAL REPORT, vol. 115, no. 337, 27 November 2015 (2015-11-27), pages 51 - 55, XP009545609, ISSN: 0913-5685 *
WANG TENG; LU GUOLIANG; YAN PENG; LU CHANGHOU: "Multidimensional Analysis of Time Series for Condition Monitoring of Rotating Machinery", 2017 INTERNATIONAL CONFERENCE ON SENSING, DIAGNOSTICS, PROGNOSTICS, AND CONTROL (SDPC), IEEE, 16 August 2017 (2017-08-16), pages 210 - 214, XP033269827, DOI: 10.1109/SDPC.2017.47 *

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN116340796A (zh) * 2023-05-22 2023-06-27 平安科技（深圳）有限公司 时序数据分析方法、装置、设备及存储介质
CN116340796B (zh) * 2023-05-22 2023-12-22 平安科技（深圳）有限公司 时序数据分析方法、装置、设备及存储介质

Also Published As

Publication number Publication date
JPWO2023084787A1 (ja) 2023-05-19
US20240411780A1 (en) 2024-12-12

Similar Documents

Publication Publication Date Title
Zhang et al. Unsupervised deep anomaly detection for multi-sensor time-series signals
Fulcher Feature-based time-series analysis
CN112154418B (zh) 异常检测
Behera et al. Multiscale deep bidirectional gated recurrent neural networks based prognostic method for complex non-linear degradation systems
Laxhammar et al. Online learning and sequential anomaly detection in trajectories
Wu et al. A weighted deep domain adaptation method for industrial fault prognostics according to prior distribution of complex working conditions
CN111914873A (zh) 一种两阶段云服务器无监督异常预测方法
Zhao et al. A novel multivariate time-series anomaly detection approach using an unsupervised deep neural network
CN117041017B (zh) 数据中心的智能运维管理方法及系统
Wu et al. Combining OC-SVMs with LSTM for detecting anomalies in telemetry data with irregular intervals
CN112101420A (zh) 一种相异模型下Stacking集成算法的异常用电用户识别方法
Xu et al. Generative adversarial networks with AdaBoost ensemble learning for anomaly detection in high-speed train automatic doors
Qin et al. CSCAD: Correlation structure-based collective anomaly detection in complex system
WO2023084787A1 (ja) 変化点検知装置、変化点検知方法及びプログラム
CN118133435A (zh) 基于svr与聚类的复杂航天器在轨异常检测方法
JP5826892B1 (ja) 変化点検出装置、変化点検出方法、及びコンピュータプログラム
CN117454165A (zh) 一种网络模型的训练方法、电机温度预测方法及相关设备
CN117807470A (zh) 用于无监督时间序列异常检测的多重校准单分类方法
Ho et al. Graph anomaly detection in time series: A survey
Wang et al. Forecast-based multi-aspect framework for multivariate time-series anomaly detection
CN116401537A (zh) 基于多任务的网络多元时间流量序列异常检测方法及装置
Zeng et al. Detecting anomalies in satellite telemetry data based on causal multivariate temporal convolutional network
Dhanalakshmi et al. Predicting the Price of Stock Using Deep Learning Algorithms
Senyukova et al. Ensemble decomposition learning for optimal utilization of implicitly encoded knowledge in biomedical applications
Du et al. Sailfish: a fast Bayesian change point detection framework with gaussian process for time series

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 21964140

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2023559393

Country of ref document: JP

Kind code of ref document: A

WWE Wipo information: entry into national phase

Ref document number: 18702548

Country of ref document: US

122 Ep: pct application non-entry in european phase

Ref document number: 21964140

Country of ref document: EP

Kind code of ref document: A1