[[IEEE ACCESS review comments for MetricSifter paper 202301]]を受けて、 [[MetricSifter]]論文では、クラウドコンピューティングのインシデント対応の文脈で、時系列データと障害発生時の異常のネットワーク伝搬を論じていた。 しかし、[[時系列解析]]とネットワーク解析の分野において、MetricSifterがどのような位置づけにあるかは論じていない。 そこで、次の文献を基に、MetricSifterのアルゴリズムが時系列とネットワーク解析分野における位置づけを述べる。 ## ネットワーク解析・統計的因果推論 - [[2023__Physics Reports__Signal propagation in complex networks]] - [[2022__JAIR__Survey and Evaluation of Causal Discovery Methods for Time Series]] - [[2019__Review of Causal Discovery Methods Based on Graphical Models]] ## 時系列解析 - [[2022__VLDB__Anomaly Detection in Time Series - A Comprehensive Evaluation]] - [[2021__CSUR__A Review on Outlier-Anomaly Detection in Time Series Data]] - [[2020__Chaos__Wavelet entropy-based evaluation of intrinsic predictability of time series]] - [[2015__Information Systems__Time-series clustering – A decade review]] ## revisionの方針 - Automated Fault Localization -> Categorization - 時系列データの異常検知 最も大きなanomaly strengthをもつメトリクスを特定する問題に帰着。これはより単純なアプローチ。 - [[2022__VLDB__Anomaly Detection in Time Series - A Comprehensive Evaluation]]を引用し、どのファミリーの手法かを位置づける。 - [[2019__WWW__ε-Diagnosis - Unsupervised and Real-time Diagnosis of Small-window Long-tail Latency in Large-scale Microservice Platforms|ε-Diagnosis]] はdistanceの一種。 - 計算量がnに対して、O(n)となるため、計算効率が高いが、必ずしもanomaly strengthの強さが原因の強さを示すわけではないため、特定精度には限界がある。 - 時系列データ間の異常伝搬 anomaly propagation 異常伝搬をとらえ、sourceを特定する問題に帰着する より複雑な問題 - [[2023__Physics Reports__Signal propagation in complex networks|Peng Ji+, Physics Reports2023]] を引用し、複雑ネットワークおけるmodel-drivenとdata-driven typeのうち、data-driven typeの解析法が用いられている。 - メトリクスの観測時系列は、正常時に静的ネットワークとして構成されるが、障害発生時には、異常が伝搬するため、時間変化する[[Temporal networks]]とみなせる。 - 多くの故障箇所特定法がもつ仮定は、異常伝搬が非常に高速であることから、伝搬時間より、離散データのサンプリング間隔のほうが長いというものである。伝搬時間を考慮せずに、ノード間の依存関係をminingし、sourceはネットワークの中心的な役割を果たすノードと仮定する。ネットワークトポロジーをメトリクスの観測時系列データから再構成する。ネットワークトポロジーの同定には、統計的因果探索法が用いられる。任意の２ノード間の線形相関を用いた条件付き独立性をpairwiseで調べることにより、 - Problem Formulation - anomaly-strengthベースのアプローチとanomaly-propagationベースのアプローチにせよ、計算量は小さくなる。 - 障害発生時の一時的な異常伝搬ネットワークを再構成するために、 - Feature Reduction - 時系列データの正常削減 - 異常検知問題 - NSigma - Distribution - BIRCH - Distance - K-S test - Distribution - FluxInfer-AD - Distribution - NSigmaの亜種であり、異常部位を際立たせるための平滑化を事前に行う - 冗長削減 - 冗長なメトリクスを発見する問題は、時系列データのクラスタリングに帰着できる。 - クラスタリング - 時系列データのクラスタリング [[2015__Information Systems__Time-series clustering – A decade review]] - Whole time-series clustering - shape-based, feature-based, model-based - Distance Meatures - [[ユークリッド距離]] - [[ピアソン相関係数|ピアソン相関]] - [[DTW]] - [[Shape-based distance|SBD]] - Time Series Cluster prototype - Finding the cluster prototype or cluster representative - medoid - Time Series Clustering - partitioning - model-based - density-based - - HDBS-R, HDBS-SBD - 距離尺度: R, SBD - medoid - [[HDBSCAN]] - Framework - 異常検知と変化点検知の差異 - 異常検知はunusual datapoints、変化点検知は時系列中にシフトが発生した点を検知する - Anomaly detection is about identifying unusual data points, while change point detection is about identifying shifts in the data's statistical properties over time. - 故障による異常の影響は時系列中のシフトとして現れると仮定できるため、変化点検知問題に帰着できる。 - 正常期間に異常があっても、変化点検知は正常期間の事前の手動決定がないため、正常削減法の偽陽性を解決しやすい。 - Related Work - Fault Localization is various types of time series analysis - 時系列解析 - 時系列の異常検知 [[2022__VLDB__Anomaly Detection in Time Series - A Comprehensive Evaluation]] - Forecasting - [[2020__Chaos__Wavelet entropy-based evaluation of intrinsic predictability of time series|WEEM]]などの予測線と実測値との差分の大きさを異常の強さとする - Reconstruction - [[2019__KDD__Robust Anomaly Detection for Multivariate Time Series through Stochastic Recurrent Neural Network|OmniAnomaly]] - clustering - signal propagation -> source localization - 勾配ベースの因果探索法 - これらのより発展的な解析法を用いることにより、クラウドアプリケーションの故障箇所特定の精度が向上する可能性がある。