# Rule Discovery in Telecommunication Alarm Data Navigation: [[index]] | [[sources.base]] > [!abstract] 概要 > 障害管理はテレコミュニケーションネットワーク管理における重要だが困難な領域である。ネットワークは大量のアラーム情報を生成し、それらは障害の箇所を特定する前に分析・解釈されなければならない。いわゆるアラーム相関(alarm correlation)は、障害識別における中心的な技術である。アラーム相関システムの利用は非常に普及しており、相関を表現する手法も成熟しつつある一方、あるネットワークとその構成要素に対してアラーム相関システムを構築するために必要な知識をすべて獲得することは難しい。我々は、相関システムのための知識獲得タスクに対する新規な部分的解法を述べる。我々は、データベース中のアラームの再帰的なパターンを発見するための手法とツールを提示する。これらのパターン、すなわちエピソードルール(episode rules)は、リアルタイムのアラーム相関システムの構築に用いることができる。我々はまた、ネットワーク管理の専門家が生成された大量のルールを閲覧できるツールも提示する。これらのツールにより相関システムの構築は容易になる。エピソードルールはアラームストリーム中の再帰的な現象に関する豊富な統計情報を提供するためである。この方法論は TASA と呼ばれる研究システムに実装され、複数のテレコミュニケーション事業者によって利用されている。我々は TASA の利用経験についても簡潔に述べる。 ## 論文情報 - 著者: [[Mika Klemettinen]], [[Heikki Mannila]], [[Hannu Toivonen]] - 所属: [[wiki/entities/University of Helsinki|University of Helsinki]] Department of Computer Science(Mannilaは Nokia Research Center を現所属として併記、Toivonenは Rolf Nevanlinna Institute を現所属として併記) - 媒体: Journal of Network and Systems Management, Vol. 7, No. 4, 1999(pp. 395–423) - キーワード: Alarm correlation; fault identification; rule discovery; data mining; episodes. ## 概要 テレコミュニケーションネットワークの障害管理では、ネットワーク要素が大量のアラームを発する。これらを人手で解釈するのは困難であり、アラーム相関(複数のアラームを一つのまとまりとして解釈し、冗長を除去し原因を推定する技術)が中心的な対策として使われてきた。しかし、あるネットワークに対して相関パターン(相関ルール)を専門家の知識だけで洗い出すのは労力がかかり、専門家自身も気づいていない相関を見落とすことがある。本論文は、この知識獲得工程を助けるために、アラームデータベースから統計的に繰り返し出現するパターン(エピソードルールとアソシエーションルール)を半自動的に発見する手法と、発見された大量のルールを専門家が閲覧・絞り込むためのツールを提示する。これらは TASA(Telecommunication Alarm Sequence Analyzer)というシステムに実装され、1995年以降4社のテレコミュニケーション事業者でプロトタイプ運用されてきた。 ## 問題設定 - アラーム相関システムの構築は3段階に分けられる: (1) アラームパターンの半自動発見(オフライン)、(2) 相関システムの構築・修正(専門家の知識が中心的役割を果たす。発見されたパターンは専門家の想起・定式化を助けるだけ)、(3) 相関システムのリアルタイム適用。本論文が寄与するのは (1) の段階のみである。 - アラームは三つ組 a = (t, s, m)(時刻・送信元・アラームメッセージ)として形式化される。ネットワーク要素は自身の限定的な視点からしか障害の兆候を報告できず、一つの障害が複数の要素から複数のアラームを引き起こしうる。 **Figure 1** ![[Rule-Discovery-in-Telecommunication-Alarm-Data/fig01-alarm-format.png]] (Figure 1. 実際のアラームのフォーマット例。日時フィールドが時刻 t、alarming element フィールドが送信元 s に対応する。) - 管理センターはネットワークから受信したアラーム列を相関させ、冗長情報の除去・低優先度アラームの抑制・新規情報への置換などの操作を行う。 **Figure 2** ![[Rule-Discovery-in-Telecommunication-Alarm-Data/fig02-alarm-flow.png]] (Figure 2. テレコミュニケーションネットワークからアラーム相関システムへのアラームの流れ。) - 相関パターンには対応する相関アクションが結び付けられ、時間窓内でパターンの出現が認識されるとアクションが実行される(例: アラーム型 A と B の共起から、警告メッセージ C を生成し元のアラームを抑制する)。 **Figure 3** ![[Rule-Discovery-in-Telecommunication-Alarm-Data/fig03-correlation-action.png]] (Figure 3. 相関アクションの例。アラーム型 A と B の共起(co-occurrence)から新たな情報 C を生成する。) - ネットワークと構成要素は絶えず進化するため、アラームデータの性質も変化し続け、相関システムは常に不完全である。遅延・欠落・誤った時刻スタンプへの頑健性も課題となる。 ## 提案手法 - アラームデータベースから発見されたルールは、専門家による相関システムの構築・修正段階への入力として使われる。 **Figure 4** ![[Rule-Discovery-in-Telecommunication-Alarm-Data/fig04-rule-discovery-usage.png]] (Figure 4. アラームデータベースで発見されたルールをアラーム相関システムの構築に用いる流れ。) - **エピソードルール**: 「あるアラーム集合が時間窓内に生起すれば、別のアラーム集合が時間窓内に確率 p で生起する」という形式のルール。系列を考慮する **serial episode**(アラーム述語の順序付き列)と、順序を無視する **unordered episode** の2種を区別する。エピソードルールは `β[win1] ⇒ α[win2]` の形式で表され、β は α の部分エピソードである。ルールの **信頼度(confidence)** は条件付き確率、**頻度(frequency)** はデータベース中の絶対出現回数として定義される。 **Figure 5** ![[Rule-Discovery-in-Telecommunication-Alarm-Data/fig05-event-sequence-example.png]] (Figure 5. イベント型の系列の例。serial episode(順序付き部分列)と unordered episode(順序を無視した部分集合)の違いを示す。) - **アソシエーションルール**: `X ⇒ Y`(X, Y はアラーム述語の集合)の形式で、時間的な順序関係を考慮せず、個々のアラームが持つ属性間の共起確率を表す。 - 両ルールとも、Mannila, Toivonen, Verkamo(1997年)の頻出パターン発見アルゴリズム(レベルワイズ探索。候補生成→頻度カウント→再帰的候補構築)を用いて、まず「頻出エピソード/頻出述語集合」を列挙し、そこからルールを生成する2段階の手続きで動作する。頻出性の反単調性(部分エピソードが頻出でなければ全体も頻出になり得ない)を使って候補集合を刈り込む。 - ユーザーはアラーム述語の集合 E、時間窓の集合 W、頻度閾値 c、信頼度閾値 d を指定する。時間窓の粒度が細かいほどルール数は増えるが実行時間への影響は小さい。頻度閾値は実行時間に強く影響する。 **Figure 6** ![[Rule-Discovery-in-Telecommunication-Alarm-Data/fig06-tasa-environment.png]] (Figure 6. TASAシステムの環境。左側はアラームログからアラームデータベースを構築する流れ、右側はアラーム述語・時間窓・頻度閾値・信頼度閾値からTASAを経てルールを生成する流れ。) - 発見された大量のルールに対し、**テンプレート**(アラーム述語を用いた正規表現的なフィルタ式)による**フォーカシング**(選択・除外)、**ソート**、**クラスタリング**という3種の対話的操作を提供する。テンプレートは肯定・否定の両方を同時に複数適用でき、専門家ごとに異なる「自明な知識」をフィルタで除去できる。 **Figure 8** ![[Rule-Discovery-in-Telecommunication-Alarm-Data/fig08-tasa-rule-viewer.png]] (Figure 8. TASAシステムのルール閲覧ウィンドウ。テンプレートによる選択条件とソート済みのルール一覧を表示する。) - 可視化として、あるルールの左辺出現から右辺出現までの時間差のヒストグラムを提示し、周期的な関係の発見を助ける。 **Figure 7** ![[Rule-Discovery-in-Telecommunication-Alarm-Data/fig07-distance-histogram.png]] (Figure 7. ルール「1234⇒5678」の左辺・右辺間の距離ヒストグラム。x軸は秒単位の時間差、y軸はアラーム1234の後にアラーム5678がx秒後に生起した回数。) ## 新規性 - 一つの目的固有パターンだけを探す従来の機械学習的アプローチ(1つの target concept に対する規則発見)とは異なり、TASA はユーザ指定の条件を満たす**すべての**頻出パターンを一括発見し、その後の対話的な絞り込みでさまざまな視点を提供する。これにより新しい発見のたびに再探索が不要になる。 - 系列データ(時間的順序を持つイベント列)への頻出パターン発見の適用は、当時のKDD分野では非unordered(順序なし)データへの適用が主流だった中で新しい方向だった。 - テンプレートによるルール絞り込みの発想は Hoschka & Kløsgen の先行研究に着想を得つつ、固定的な文タイプではなく正規表現的なテンプレートで一般化した点が新しい。 ## 実験設定 - 性能評価は、固定・セルラー両ネットワークの複数のアラームデータベースを用いた。代表例として、73,679件のアラーム・287種のアラーム型・7週間分のデータベースを対象に、Pentium 166MHz・メモリ32MB・Linux上で計測した。 - 実データセットを用いた事例研究(Example 8, Table IV)では4つのデータセットを分析し、アラーム件数19,429〜98,413件、アラーム型数41〜1,982種、観測期間2〜253日という多様な規模・性質のデータで動作を確認した。 ## 実験結果 - serial episode・unordered episode の頻出パターン発見は、頻度閾値50〜2000の範囲で12〜30秒程度で完了する(表I・表II)。反復回数は最大エピソードサイズに一致する。 - 時間窓の数を1から60まで増やすと、ルール数は1,221から79,055まで指数的に増加する一方、ルール生成にかかる時間は13秒から43秒への線形的な増加にとどまる(表III)。時間窓を無視すれば実質的に区別されるルールは1,221件のみであり、残りは時間窓の粒度違いにすぎない。 - 信頼度閾値を上げるとルール数は急速に減少する。 **Figure 9** ![[Rule-Discovery-in-Telecommunication-Alarm-Data/fig09-rules-vs-confidence.png]] (Figure 9. 信頼度閾値ごとの発見される個別ルール数(最大時間窓60秒、頻度閾値100)。) - 4つの実データセット(表IV・表V)では、得られたルール数がデータセットごとに325〜9,406件と大きく異なった。 - アルゴリズムの実行時間はアラーム数に対して線形であり、より大規模なデータベースにも許容可能な応答時間で適用できる。 ## 考察 - 現場のフォールトマネジメント専門家は、TASA を (1) 長期的で頻度の高い依存関係の発見、(2) 短期的なアラーム系列の概観作成、(3) アラームデータベースの一貫性・正しさの評価、に有用と評価した。 - 発見された依存関係の中には、ネットワークトポロジー上は近くない要素間の予期しない依存関係も含まれており、広い領域を分析することで初めて可視化された例が報告されている。 - 一方、発見されたルールの多くは専門家にとって自明であった。自明さは専門家ごとに異なるため、テンプレートによる個人ごとのフィルタリングが有効に機能した。 - 長いバースト期間を含むイベント系列の解析にはアルゴリズムが不向きであり、そのような期間を切り出して別途分析する方が実用的であるという経験が報告されている。 - ユーザビリティ評価(ヘルシンキ工科大学のユーザビリティ研究室、フォールトマネジメント専門家4名によるテスト)では、視覚的・環境的には好評だったが、初回利用者は知識発見分野の用語に不慣れであったと報告されている。 - 結論として、エピソードルールは相関ルールの初期草案として、アソシエーションルールは短期概観の作成として、それぞれ異なる用途で実運用に組み込まれつつある。エピソードルールは異常検知への応用可能性も持つと述べられている。 ## 強み / 弱点・課題 - 強み: (1) 単一目的のパターン探索と異なり、すべての頻出パターンを一括発見してから対話的に絞り込む設計により、専門家の新たな疑問のたびに再探索が不要。(2) 実行時間がアラーム数に対して線形。(3) 4社での長期プロトタイプ運用という実データでの検証実績。 - 弱点・課題: (1) 長いバースト期間を含む系列の解析に弱い。(2) 発見されるルールの多くが専門家にとって自明であり、有用なルールの選別はテンプレート機能によるユーザ側の負担に依存する。(3) 相関システムの構築(ステップ2)自体は自動化されておらず、専門家の判断に強く依存する。(4) 遅延・欠落・不正確な時刻スタンプへの対処は個別ケース依存であり、一般的な解法は提示されていない。 ## 出典 - [[.raw/papers/Rule-Discovery-in-Telecommunication-Alarm-Data.pdf]] - [[.raw/papers/Rule-Discovery-in-Telecommunication-Alarm-Data.txt]]