# 重要アラートマイニング Navigation: [[アラート相関]] | [[根本原因分析]] ## 定義 重要アラートマイニング(critical alert mining, CAM)は、アラート間の因果関係(依存規則)から構築した有向非巡回グラフ(アラートグラフ)上で、「修正すればカスケード的に最も多くの他アラートを解消できる `k` 個のアラート」を選ぶ組合せ最適化問題である。既存のアラート因果関係の**発見**(Granger 因果性などによる依存規則マイニング)を前提としたうえで、その一歩先にある「どのアラートを優先して直すべきか」という下流の意思決定問題として定式化される([[@2014__KDD__Towards Scalable Critical Alert Mining]])。CAM は最大被覆問題への帰着により NP 完全であることが示されている。目的関数 `Gain(S) = Σ_u w_u · P_f(S, u)`(`P_f` はアラート修復確率)は単調劣モジュラ関数であり、貪欲近似で近似比 `1 - 1/e` を達成できる([[@2014__KDD__Towards Scalable Critical Alert Mining]])。 ## 未解決の問い - アラートグラフの動的維持(オンラインでの重要アラート再計算)は、静的なグラフに対する近似アルゴリズムとどう統合できるか。 - 木構造への単純化(単一木・複数木サンプリング)によるバイアスは、因果構造がより密なグラフ(合流因果が多い場合)でどこまで拡大するか。 - 外部の意味情報・知識ベースを統合した重要アラートの自動解釈は、どのように貪欲近似の枠組みに組み込めるか。 ## 未編纂の観察 - **CAM は劣モジュラ最適化として NP 完全な問題を定式化し、影響最大化(influence maximization)分野の貪欲近似・枝刈り・サンプリングの道具立てをアラート因果グラフに転用している**。対象がソーシャルネットワークの拡散モデルではなくアラートの因果カスケードである点が異なる(Source: [[@2014__KDD__Towards Scalable Critical Alert Mining]])。 - **上下界による枝刈り(BnP)は局所 `h` ホップの情報だけで下界を計算でき、`h=3` で 95% のアラートを刈り取り質を落とさず 30 倍高速化する一方、`h` を増やしすぎると下界計算コストが支配的になり性能が劣化する**。局所探索の深さにトレードオフの山型があることが実データで確認されている(Source: [[@2014__KDD__Towards Scalable Critical Alert Mining]])。 - **木サンプリングに基づくヒューリスティクス(ST・単一木、MTS・複数木)は、厳密な近似アルゴリズムに対して最大 5,000 倍・80 倍の高速化を達成しつつ、解の質(Gain)を 80% 以上保つ**。100 万アラート・9,000 万超のエッジ規模まで線形にスケールする一方、厳密な近似アルゴリズム(Naive・BnP)は 10 万アラート規模でも 1 時間以内に完了しない(Source: [[@2014__KDD__Towards Scalable Critical Alert Mining]])。 ## 関連 - [[アラート相関]] — CAM が前提とするアラートグラフ(依存規則・因果関係)を構築する側の概念。 - [[根本原因分析]] — CAM は根本原因分析の下流にある「どれを直すか」という優先順位付け問題として位置づけられる。 ## 出典 - [[@2014__KDD__Towards Scalable Critical Alert Mining]]