(57)【要約】【課題】因果グラフによる要因推定の精度の低下を抑制可能なグラフ要約を実現すること。【解決手段】グラフ要約装置は、各ノードがグラフの状態に対する要因の度合いを示す要因度を有し、各辺がノード間の因果関係の強さを示す重みを有するグラフが変化すると、変化後の前記グラフの各ノードについて、変化前の前記グラフのノードの要因度に基づく重要度を計算する計算部と、前記重要度が閾値以下である第１のノードを削除の候補として選択する選択部と、前記第１のノードを削除する削除部と、を有する。【選択図】図２
2020119261.tif 000002
【特許請求の範囲】
【請求項１】
各ノードがグラフの状態に対する要因の度合いを示す要因度を有し、各辺がノード間の因果関係の強さを示す重みを有するグラフが変化すると、変化後の前記グラフの各ノードについて、変化前の前記グラフのノードの要因度に基づく重要度を計算する計算部と、
前記重要度が閾値以下である第１のノードを削除の候補として選択する選択部と、
前記第１のノードを削除する削除部と、
を有することを特徴とするグラフ要約装置。
【請求項２】
前記第１のノードごとに、当該第１のノードと、当該第１のノードからの辺の重みが最大である第２のノードとを１つのノードとして、当該第１のノードが削除された場合に前記グラフに付ける辺を決定し、当該第１のノードの削除前後における要因度が変化しないように当該辺の重みを決定する決定部、
を有することを特徴とする請求項１記載のグラフ要約装置。
【請求項３】
前記削除部は、前記第１のノードを削除した場合に前記グラフにサイクル構造が発生しない場合に当該第１のノードを削除する、
ことを特徴とする請求項１又は２記載のグラフ要約装置。
【請求項４】
各ノードがグラフの状態に対する要因の度合いを示す要因度を有し、各辺がノード間の因果関係の強さを示す重みを有するグラフが変化すると、変化後の前記グラフの各ノードについて、変化前の前記グラフのノードの要因度に基づく重要度を計算する計算手順と、
前記重要度が閾値以下である第１のノードを削除の候補として選択する選択手順と、
前記第１のノードを削除する削除手順と、
をコンピュータが実行することを特徴とするグラフ要約方法。
【請求項５】
前記第１のノードごとに、当該第１のノードと、当該第１のノードからの辺の重みが最大である第２のノードとを１つのノードとして、当該第１のノードが削除された場合に前記グラフに付ける辺を決定し、当該第１のノードの削除前後における要因度が変化しないように当該辺の重みを決定する決定手順、
を前記コンピュータが実行することを特徴とする請求項４記載のグラフ要約方法。
【請求項６】
前記削除手順は、前記第１のノードを削除した場合に前記グラフにサイクル構造が発生しない場合に当該第１のノードを削除する、
ことを特徴とする請求項４又は５記載のグラフ要約方法。
【請求項７】
請求項４乃至６いずれか一項記載のグラフ要約方法をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフ要約装置、グラフ要約方法及びプログラムに関する。
【背景技術】
【０００２】
システム運用において、オペレータの運用負荷低減のため、故障対応の自動化技術が検討されている。特に、障害発生時に障害の要因を特定することは人手では膨大な時間を要する場合が多く、障害要因推定技術に関する研究は重要である。これらの技術はＢａｙｅｓｉａｎ  Ｎｅｔｗｏｒｋ（非特許文献１）や決定木（非特許文献２）などの因果グラフを用いて行われるケースが多い。
【０００３】
将来的には、仮想化技術の浸透により、システムの大規模化・複雑化が見込まれる。このため、障害発生時のアラートや異常なイベントの数が増加し、それらの因果関係も複雑化すると見込まれる。これにより、上記のような要因推定技術において、大規模かつ複雑なグラフが生じると見込まれる。
【０００４】
グラフに関する一般的な技術として、グラフの重要な部分を抜き出して単純化する、グラフ要約の技術が提案されている。これを因果グラフに適用できれば、グラフ要約を用いて要約後のグラフで要因推定を行い、おおまかな要因を推定した上で、要因となったイベントの付近のみについて要約前の情報を戻し、もう一度要因推定を行うことで計算時間の削減が期待できる。要因推定の対象となるイベント数が削減されることで計算時間が削減され、さらに、２段階の推定により、精度も確保される。
【０００５】
グラフ要約に関しては、個人又はコミュニティ同士の関係性や論文の引用関係の解析を対象とした研究が行なわれてきたが（非特許文献３）、要因推定を目的として因果グラフに対して適用するための技術は少ない。非特許文献４では、構造的な情報からＢａｙｅｓｉａｎ  Ｎｅｔｗｏｒｋを単純化することで、推定を効率化する技術が提案されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】E. R. J. Hruschka, M. do Carmo Nicoletti, V. A. de Oliveira, and G. M. Bressan, "Markov-blanket based strategy for translating a bayesian classifier into a reduced set of classification rules," in Proceedings of the 7th International Conference on Hybrid Intelligent Systems (HIS '07), pp. 192-197, 2007.
【非特許文献２】A. X. Zheng, J. Lloyd, and E. Brewer, "Failure diagnosis using decision trees," in proceedings of the First International Conference on Autonomic Computing (ICAC '04), pp. 36-43, 2004.
【非特許文献３】Y. Liu, T. Safavi, A. Dighe and D. Koutra, "Graph Summarization Methods and Applications: A Survey, ACM Computing Surveys," 51(3), pp. 1-34, 2018.
【非特許文献４】M. Shiba, A. Takahashi, S. Aoki, H. Tsuji and S. Inoue, "Numerical experimentation on structure simplification in Bayesian network," 2009 IEEE International Conference on Systems, Man and Cybernetics, pp. 4698-4703, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
因果グラフに対してグラフ要約を適用することを考慮した方法は少ないながら存在するが、いずれの方法も、末端にあるノードを削除する、隣接ノードを共有している複数のノードをグルーピングするなど、グラフの構造的な情報しか用いていない。さらに、指針のみが示されており、削除するノードやグルーピングするノードの決定方法が明確に示されているわけではない。
【０００８】
一方、システム運用における各ノードの要因へのなりやすさは、グラフの構造的な情報に加えて、過去の障害においてそのノードが要因であったか否かの情報も考慮する必要があるため、従来技術では因果グラフの要因推定の精度が落ちてしまうという課題がある。  また、個人又はコミュニティ同士の関係性や論文の引用関係を対象とした技術は、それらの解析に特化した方法であるため、ノードの次数など各ノードの影響力を重視した要約を行う。
【０００９】
一方、因果グラフによる要因推定においては、各ノードの要因へのなりやすさが重要となるため、上記のような既存技術でも因果グラフの要因推定の精度が落ちてしまうという課題がある。
【００１０】
このように、システム運用における因果グラフによる要因推定に適したグラフ要約は、既存技術のみでは達成することができない。
【００１１】
本発明は、上記の点に鑑みてなされたものであって、因果グラフによる要因推定の精度の低下を抑制可能なグラフ要約を実現することを目的とする。
【課題を解決するための手段】
【００１２】
そこで上記課題を解決するため、グラフ要約装置は、各ノードがグラフの状態に対する要因の度合いを示す要因度を有し、各辺がノード間の因果関係の強さを示す重みを有するグラフが変化すると、変化後の前記グラフの各ノードについて、変化前の前記グラフのノードの要因度に基づく重要度を計算する計算部と、前記重要度が閾値以下である第１のノードを削除の候補として選択する選択部と、前記第１のノードを削除する削除部と、を有する。
【発明の効果】
【００１３】
因果グラフによる要因推定の精度の低下を抑制可能なグラフ要約を実現することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施の形態における障害要因推定装置１０のハードウェア構成例を示す図である。
【図２】本発明の実施の形態における障害要因推定装置１０の機能構成例を示す図である。
【図３】障害要因推定装置１０が実行する処理手順の一例を説明するためのフローチャートである。
【図４】重みの決定の説明に用いるグラフ構造の第１の例を示す図である。
【図５】重みの決定の説明に用いるグラフ構造の第２の例を示す図である。
【図６】本実施の形態の評価における要約前のグラフを示す図である。
【図７】本実施の形態の評価における要約後のグラフを示す図である。
【図８】要約後のグラフの任意のノード間の要因度の差のヒートマップを示す図である。
【発明を実施するための形態】
【００１５】
以下、図面に基づいて本発明の実施の形態を説明する。計算時間の増大と精度の低下という課題解決のため、本実施の形態では因果グラフの要約において重要なポイントを考慮したグラフ要約方法と、当該グラフ要約方法を実行する障害要因推定装置１０とが開示される。障害要因推定装置１０は、監視対象のＩＣＴ（Information and Communication Technology）システム（以下、単に「システム」という。）の障害の発生に応じて以下のフローを実行する。
【００１６】
ステップ１：現在（現在から過去の一定期間）においてシステムから出力されたログデータからイベントを抽出。ログデータから異常なイベントを抽出する場合、ログのテンプレート化を用いて異常なイベントが抽出されてもよい。また、システムが、明示的に異常なイベント（アラート）を出力する場合、ログデータからイベントを抽出するのではなく、各種類のアラートが、異常なイベントとして抽出されてもよい。なお、ログのテンプレート化については、例えば、「T. Kimura et. al., "Spatio-temporal Factorization of Log Data for Understanding Network Events," IEEE INFOCOM 2014, pp. 610-618, 2014.」等が参考とされてもよい。
【００１７】
ステップ２：過去の類似障害におけるイベント情報と、ステップ１において抽出されたイベントのイベント情報とを組み合わせて、イベントの因果関係を表す因果グラフを作成。イベントの因果関係を示す因果グラフの作成については、例えば、「P. Chen, Y. Qi, P. Zheng and D. Hou, "CauseInfer:Automatic and Distributed Performance Diagnosis with Hierarchical Causality Graph in Large Distributed Systems," IEEE INFOCOM 2014, pp. 1887-1895, 2014.」、あるいは、「B. Zong, Y. Wu, J. Song, A. K. Singh, H. Cam, J. Han, and X. Yan, "Towards scalable critical alert mining," in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '14), pp.1057-1066, 2014.」等が参考とされてもよい。
【００１８】
ステップ３：ステップ２で作成したグラフを要約。
【００１９】
ステップ４：要約後のグラフで要因推定。要因推定については、例えば、「B. Zong, Y. Wu, J. Song, A. K. Singh, H. Cam, J. Han, and X. Yan, "Towards scalable critical alert mining," in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '14), pp.1057-1066, 2014.」等が参考とされてもよい。
【００２０】
ステップ５：ステップ４で要因となったイベントの付近のみについて要約前の情報を戻し、もう一度要因推定。これにより、障害要因が推定される。
【００２１】
本実施の形態では、上記のステップ３のグラフ要約技術に焦点を当て、新技術を提案する。要因推定に用いる因果グラフの要約において重要なポイントとなるのは次の３つである。
（１）要因となる可能性が高いノードは要約後も残す。
（２）要約の前後で要因推定の結果に変化が少ない。
（３）要約後のグラフはサイクル構造を持たない。
【００２２】
本実施の形態の障害要因推定装置１０は、上記（１）〜（３）のポイントを考慮することで、因果グラフによる要因推定において適用可能なグラフ要約を行う。本実施の形態は以下のフローで実行される。
【００２３】
ステップ１：ポイント（１）を考慮し重要度の低いノードを検出
ステップ２：ポイント（２）を考慮し、該当ノード削除後のグラフの辺及び重みを決定
ステップ３：ポイント（３）を考慮し、検出したノードを削除するか否かを判断
［問題設定］
因果グラフＧは、Ｇ＝（Ｖ（Ｇ），Ｅ（Ｇ），ｆＧ）とする。但し、Ｖ（Ｇ）＝｛ｖ１，…，ｖＮ（Ｇ）｝は、グラフＧのノードの集合で、各ノードは障害時に発生したアラート、又は障害時にログデータから抽出したイベントを表し、それぞれが要因度を有する。要因度とは、因果グラフＧの現在の状態（構造）に対する要因である度合いを示す指標である。なお、本実施の形態では、障害時に発生したアラート及びログデータから抽出したイベントのいずれをも、イベントと呼ぶ。Ｎ（Ｇ）は、グラフＧのノード数、Ｅ（Ｇ）＝｛ｅｊ，ｋ｜ｊ，ｋ＝１，…，Ｎ（Ｇ）｝は、グラフＧの辺の集合で、ｅｊ，ｋは、ノードｖｊからノードｖｋへ向かう辺を表す。ｆＧ：Ｅ（Ｇ）→Ｒ＋は、Ｇの辺の重みを表す関数とする。ただし、Ｒ＋は０以上の実数全体の集合を表す。辺の重みは、当該辺によって接続されるノード間の因果関係の強さを示す。すなわち、辺の重みは、当該辺の先のノードに係るイベントの要因が、当該辺の元のノードに係るイベントである可能性の高さを示す。また、Ｇの隣接行列Ａ（Ｇ）を、Ａ（Ｇ）＝［ｆＧ（ｅｊ，ｋ）］ｊ，ｋで定める。
【００２４】
システム運用において、最初の障害が起こると、因果グラフＧ１が生成される。次に類似した障害が起こった場合、１度目の障害の情報に２度目の障害の情報が加わり、Ｖ（Ｇ１）⊆Ｖ（Ｇ２）を満たす因果グラフＧ２が生成される（グラフＧ１の状態（構造）がグラフＧ２に変化する）。障害が起こる度にこれが行われ、類似障害に対するグラフの列｛Ｇｉ｝ｉ＝１∞が生成される。また、ｉ度目の障害時に発生したイベントの集合をＲｉ⊆Ｖ（Ｇｉ）とし、集合列｛Ｒｉ｝ｉ＝１∞が生成されるとする。ｉが増加するにしたがって、イベント間の因果関係は定まり、真の因果関係を表す因果グラフへ収束していくとする。また、ｉが増加するにしたがって各発生イベントがノイズかどうかの判断が可能となり、真の発生イベントへ収束するとする。つまり、次を満たすＧ＝（Ｖ（Ｇ），Ｅ（Ｇ），ｆＧ）とＲが存在すると仮定する。
【００２５】
【数１】
2020119261.tif 000003
但し、集合列｛Ｓｉ｝ｉ＝１∞に対して、上極限∩ｋ＝１∞∪ｉ＝ｋ∞Ｓｉと、下極限∪ｋ＝１∞∩ｉ＝ｋ∞Ｓｉが一致するとき、∩ｋ＝１∞∪ｉ＝ｋ∞Ｓｉ＝∪ｋ＝１∞∩ｉ＝ｋ∞Ｓｉ＝ｌｉｍｉ→∞Ｓｉと表すこととする。
【００２６】
極限グラフＧにおいて、確率空間（Ω，Ｆ，ｐ）が定まるとする。但し、Ωは、Ｖ（Ｇ）の全ての部分集合からなる集合族とする。また、各ｖｊ∈Ｖ（Ｇ）に対して確率変数Ｘｊ：Ω→｛０，１｝を、ｖｊ∈ωのときＸｊ（ω）＝１、ｖｊ∈ωでないときＸｊ（ω）＝０で定める。ｆＧ（ｅｊ，ｋ）＝ｐ（｛Ｘｋ＝１｝｜｛Ｘｊ＝１｝）とする。各ｉに対してｆＧｉは、ｆＧを近似する関数で、既存手法により定める。
【００２７】
このとき、イベントｖｊ∈Ｖ（Ｇｉ）が起こった際に、イベントｖｌ∈Ｒｉが起こる確率の和Σｖｌ∈Ｒｉｐ（｛Ｘｌ＝１｝｜｛Ｘｊ＝１｝）の近似Ｐｉ（ｖｊ；Ｒｉ）をｖｊの要因度とし、この値が高いイベントが、ｉ度目の障害時の主要因であると推定することとする。但し、Ｐｉは次のように定める。
【００２８】
【数２】
2020119261.tif 000004
この数式に関しては、例えば、「B. Zong, Y. Wu, J. Song, A. K. Singh, H. Cam, J. Han, and X. Yan, "Towards scalable critical alert mining," in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '14), pp.1057-1066, 2014.」等が参考とされてもよい。
【００２９】
このとき、ｌｉｍｉ→∞Ｐｉ（・；Ｒｉ）＝Ｐ（・；Ｒ）（各点）が成り立つ。但し、
【００３０】
【数３】
2020119261.tif 000005
である。
【００３１】
類似障害が十分な回数起これば、Ｇ＊≒Ｇ、Ｒ＊≒Ｒを満たすＧ＊、Ｒ＊が得られ、そこからＰ＊（・；Ｒ＊）を計算することでその故障に対する主要因が確定する。しかし、Ｇ＊、Ｒ＊が得られるまでは、その時点で得られている情報を用いて要因推定を行い、出来るだけ高速、かつ、正確に主要因を推定する必要がある。そこで、Ｇ１，…，Ｇｉ−１の情報を用いてＧｉを要約し、Ｖ（Ｇ'ｉ）⊂Ｖ（Ｇｉ）を満たすＧ'ｉを作成した上でＧ'ｉに対して要因推定を行うことで、上記を達成することを考える。
【００３２】
［障害要因推定装置１０］
上記考えに基づく障害要因推定装置１０について説明する。図１は、本発明の実施の形態における障害要因推定装置１０のハードウェア構成例を示す図である。図１の障害要因推定装置１０は、それぞれバスＢで相互に接続されているドライブ装置１００、補助記憶装置１０２、メモリ装置１０３、ＣＰＵ１０４、及びインタフェース装置１０５等を有するコンピュータである。
【００３３】
障害要因推定装置１０での処理を実現するプログラムは、ＣＤ−ＲＯＭ等の記録媒体１０１によって提供される。プログラムを記憶した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００３４】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムに従って障害要因推定装置１０に係る機能を実行する。インタフェース装置１０５は、ネットワークに接続するためのインタフェースとして用いられる。
【００３５】
図２は、本発明の実施の形態における障害要因推定装置１０の機能構成例を示す図である。図２において、障害要因推定装置１０は、検出部１１、決定部１２及び削除部１３を有する。これら各部は、障害要因推定装置１０にインストールされた１以上のプログラムが、ＣＰＵ１０４に実行させる処理により実現される。
【００３６】
図３は、障害要因推定装置１０が実行する処理手順の一例を説明するためのフローチャートである。
【００３７】
ステップＳ１０１において、検出部１１は、ｉ度目の障害の発生に応じた変化後の因果グラフＧｉにおける各ノードの重要度を計算する。
【００３８】
Ｇｉにおいて要因推定を行う際、ｂｉ（ｖ）＝Ｐｉ−１（ｖ；Ｒｉ−１）（ｖ∈Ｖ（Ｇｉ−１）⊆Ｖ（Ｇｉ）のとき）、ｂｉ（ｖ）＝０（ｖ∈Ｖ（Ｇｉ）＼Ｖ（Ｇｉ−１）のとき）と定める。なお、Ｇｉ−１は、ｉ度目の障害の発生前（すなわち、変化前の）因果グラフである。
【００３９】
ｂｉ（ｖ）が大きい、つまり、Ｇｉ−１において要因度が大きかったイベントｖは、Ｇｉでも要因度が高くなると見込まれるが、新たに加わったイベントｕ∈Ｖ（Ｇｉ）＼Ｖ（Ｇｉ−１）については、当該イベントｕがＧｉ−１において要因度が大きかったイベントｖの要因となり得る場合、要因度が高くなる可能性がある。但し、Ｇｉにおける各ノードの要因度の計算の負荷は高い。そこで、検出部１１は、要因度の近似値であって（要因度の大小関係を近似できる値であって）、要因度よりも低い計算負荷によって計算可能な重要度を、Ｇｉ−１における要因度を用いてＧｉの各ノードについて計算する。
【００４０】
ｖ∈Ｖ（Ｇｉ）の重要度をｃｉ（ｖ）とおき、ｃｉ＝［ｃｉ（ｖ１），…，ｃｉ（ｖＮ（Ｇｉ））］Ｔ、と定める。さらに、ｂｉ＝［ｂｉ（ｖ１），…，ｂｉ（ｖＮ（Ｇｉ））］Ｔと定める。重要度は、時刻ｔ＝０においてｂｉであり、時刻ｔ＝１においてｃｉになるとする。ｂｉとｃｉを時刻ｔについて滑らかにつなぐ関数ｄｉ：［０，Ｔ］→Ｒ＋Ｎ（Ｇｉ）を考える。ｖｊを、Ｇｉにおいて新たに加わったイベントとする。微小時ｔ＝０からｔ＝ｈにおけるｄｉの第ｊ成分の変化量を考える。ｖｊに隣接しているノードの集合を
【００４１】
【数４】
2020119261.tif 000006
とする。ｔ＝ｈでのｄｉの第ｊ成分は、ｕｋ（ｋ＝１，…，ｄＧｉ（ｖｊ））の各要因度にｐ（｛Ｘｋ＝１｝｜｛Ｘｊ＝１｝）を掛け合わせ、ｋについて足し合わせたものと考える。これにより、Ｇｉにおける要因度が相対的に高くなる可能性があるイベントの重要度が相対的に低くならないようにすることができる。
【００４２】
具体的には、検出部１１は、次のようにしてＧｉにおける重要度ｃｉ：Ｖ（Ｇｉ）→Ｒ＋を計算する。
【００４３】
【数５】
2020119261.tif 000007
但し、Ａｉは、Ｇｉの隣接行列Ａ（Ｇｉ）を表す。
【００４４】
後述されるように、検出部１１は、（１）式により計算した重要度ｃｉ（ｖ）が相対的に小さくなるｖを、要因推定においてあまり重要ではないとみなし、削除の候補として選択する。以下が成立する。
【００４５】
【数６】
2020119261.tif 000008
但し、４行目の不等式は、Ａｉの成分は全て正であるため、ｄｉの各成分はｔに関して単調増加することを用いた。また、（Ａｉｄｉ）ｊは、Ａｉｄｉの第ｊ成分を表す。よって、重要度ｃｉ（ｖ）は、ｉ→∞において、真の要因度Ｐ（ｖ；Ｒ）以上の値になる。
【００４６】
また、ｄｉの各成分は単調増加するため、任意のｖ∈Ｖ（Ｇｉ）に対して、ｂｉ（ｖ）≦ｃｉ（ｖ）が成り立つから、Ｇｉ−１において要因度が相対的に高かったノードが削除されることはない。これにより、ポイント（１）を考慮した検出が可能となる。
【００４７】
続いて、検出部１１は、ｃｉ（ｖ）が一定の閾値ｃｍａｘ以下であるノードの集合を抽出し、抽出した集合をＤに代入する（Ｓ１０２）。すなわち、以下の演算が行われる。
Ｄ＝｛ｖ∈Ｖ（Ｇｉ）｜ｃｉ（ｖ）≦ｃｍａｘ｝
続いて、決定部１２は、該当ノード（Ｄに含まれるノード）の有無（Ｄが空であるか否か）を判定する（Ｓ１０３）。該当ノードが無い場合（Ｄが空である場合）（Ｓ１０３でＹｅｓ）、図３の処理は終了する。該当ノードが有る場合（Ｓ１０３でＮｏ）、決定部１２は、Ｄから一つのノードを取り出す（Ｓ１０４）。取り出されたノードは、Ｄから削除される。以下、取り出されたノードを、「ノードｖｊ」という。なお、ノードの取り出し順は、特定の順序に限定されない。例えば、重要度ｃｉ（ｖ）が最も低いノードが取り出されてもよいし、インデックスが最も小さいノードが取り出されてもよいし、ランダムにノードが取り出されてもよい。インデックスとは、ノードに付与される識別子であり、例えば、ノードが生成された順番を示す数値である。
【００４８】
続いて、決定部１２は、ノードｖｊを削除した際（削除した後）の辺の付け方を決定する（Ｓ１０５）。具体的には、決定部１２は、ノードｖｊに隣接するノードのうち、ｖｊからの辺の重みが最大になるノードｖｋを特定し、ｖｊとｖｋを１つのノードとみなすことにより、当該１つのノードにｖｊの辺及びｖｋの辺を付ける。
【００４９】
重みが最大になるノードを用いる理由は、以下で説明する方法で重みを決定した場合に、ノード削除前と削除後の要因度の計算における重みの変化の影響を最小にするためである。
【００５０】
続いて、決定部１２は、ステップＳ１０５において付け方が決定された各辺の重みを、次の３つの単純な構造において、ノード削除前後で各ノードの要因度が変化しないように決定する（Ｓ１０６）。以下では、ノードｖｊ削除前のグラフをＧＢ、削除後のグラフをＧＡと表す。
【００５１】
［木構造］
共通のノードからｖｊとｖｋの両方に辺が入っておらず、かつ、共通のノードにｖｊとｖｋ両方から辺がのびていない場合（すなわち、ノードｖｊがノードｖｋの親ノードである場合）、ｖｊからｖｋへ向かう辺の重みｆＧＢ（ｅｊｋ）を、ｖｋから出ている辺の重み全てに掛け合わせることにより、ｆＧＡを作成する。このようにして重みを決定することで、木に対してはノード削除前後で要因度が変化しないようにすることができる。
【００５２】
［図４の構造］
ＧＢにおいて共通のノードｖｌからｖｊとｖｋの両方に辺が入っている場合、ステップＳ１０５ではｅｊｋ、ｅｌｋ、ｅｌｊの３辺が、ＧＡにおいて一つの辺ｅｌｋとなる。重みは、ｆＧＡ（ｅｌｋ）＝ｆＧＢ（ｅｌｊ）・ｆＧＢ（ｅｊｋ）＋ｆＧＢ（ｅｌｋ）−ｆＧＢ（ｅｌｊ）・ｆＧＢ（ｅｊｋ）・ｆＧＢ（ｅｌｋ）により決定する。このように決定することで、図４のような構造に対してはノード削除前後で要因度が変化しないようにすることができる。なお、図４において、ａ＝ｆＧＢ（ｅｌｊ）、ｂ＝ｆＧＢ（ｅｌｋ）、ｃ＝ｆＧＢ（ｅｊｋ）である。
【００５３】
［図５の構造］
ＧＢにおいて共通のノードｖｌに、ｖｊとｖｋの両方から辺がのびている場合、ステップＳ１０５ではｅｊｋ、ｅｋｌ、ｅｊｌの３辺が、ＧＡにおいて一つの辺ｅｊｌとなる。重みは、ｆＧＡ（ｅｋｌ）＝ｆＧＢ（ｅｋｌ）・ｆＧＢ（ｅｊｋ）＋ｆＧＢ（ｅｊｌ）−ｆＧＢ（ｅｋｌ）・ｆＧＢ（ｅｊｋ）・ｆＧＢ（ｅｊｌ）により決定する。このように決定することで、図５のような構造に対してはノード削除前後で要因度が変化しないようにすることができる。なお、図５において、図４において、ａ＝ｆＧＢ（ｅｊｋ）、ｂ＝ｆＧＢ（ｅｊｌ）、ｃ＝ｆＧＢ（ｅｋｌ）である。
【００５４】
続いて、削除部１３は、ノードｖｊを削除するか否かを判断する（Ｓ１０７）。具体的には、削除部１３は、削除候補のｖｊの削除前のグラフをＧＢ、削除後のグラフをＧＡとした場合にＧＡの隣接行列の固有値を調べることで、ＧＡにサイクル構造があるか否かを調べる。一般に、グラフＧの隣接行列Ａ（Ｇ）に対して、次が成り立つ。
Ａ（Ｇ）の固有値が全て０
⇒Ａ（Ｇ）ｎ＝０
⇒Ｇに長さｎ以上のパスは無い。
⇒Ｇにサイクル構造が無い。
【００５５】
よって、削除部１３は、Ａ（ＧＡ）の固有値が全て０ならば（Ｓ１０８でＹｅｓ）、ｖｊを削除し、そうでなければ（Ｓ１０８でＮｏ）、ｖｊを削除しない。なお、削除部１３は、ｖｊを削除した場合、ステップＳ１０５及びＳ１０６の実行結果に従って、Ｇｉに対する辺の付与及び当該辺に対する重みを付与する。
【００５６】
ステップＳ１０４以降は、Ｄが空になるまで実行される。すなわち、各ｖｊ∈Ｄに対してステップＳ１０４以降が実行される。
【００５７】
一般の行列に対する固有値の計算は計算コストが高いが、次の理由により、今回の場合は計算コストが削減される。一般に、グラフＧにサイクル構造が無ければ、Ａ（Ｇ）は上三角行列にできる。よって、Ｇｉは上三角行列と仮定されてよい。Ａ（ＧＢ）からＡ（ＧＡ）への変化は、ｖｊに隣接するノードのうち、ｖｊからの辺の重みが最大になるノードｖｋに対応する行と列の変化と、ノードｖｊに対応する行と列の削除である。この変化の中で上三角行列の構造に変化を与えるのはノードｖｋに対応する行と列の変化のみであるから、ＧＡの上三角成分以外の成分の数は少ない。よって、ＧＡの固有値を数値的に求めるために必要なＱＲ分解に必要な計算量は少なくなる。
【００５８】
［評価結果］
ランダムに作成した小さなグラフに対して本実施の形態を適用することで、上記のポイント（１）〜（３）のうち、「（１）要因となる可能性が高いノードは要約後も残す」、「（２）要約の前後で要因推定の結果に変化が少ない」について評価を行った。
【００５９】
［設定］
以下のようにして、［問題設定］で述べた状況を模擬し、評価を行った。
１．ノード数が２５のランダムなグラフＧ１を作成。
２．Ｒ１＝Ｖ（Ｇ１）として、Ｇ１の各ノードｖ∈Ｖ（Ｇ１）に関して、要因度Ｐ１（ｖ；Ｒ１）を計算。
３．Ｇ１にノードを付け加えノード数を５０にし、ランダムに辺を付け加えてＧ２を作成。
４．図３に示した処理手順で要約を行い、要約後のグラフＧ'２を作成。
５．評価１：本実施の形態を用いて要約を行った際に、要約前後で各ノードの要因度の違いが小さいということを確認することを目的とし、各ｕ，ｖ∈Ｖ（Ｇ'２）に対し、Ｐ２（ｖ；｛ｕ｝）と、Ｇ'２において計算した要因度Ｐ'２（ｖ；｛ｕ｝）との差Ｐ２（ｖ；｛ｕ｝）−Ｐ'２（ｖ；｛ｕ｝）を計算。
６．Ｒ２を、Ｒ１の元のうちのランダムに選んだ５つを、Ｖ（Ｇ２）＼Ｒ１の元からランダムに選んだ５つによって交換したものをＲ２として設定。
７．評価２：本実施の形態を用いて要約を行った際に、要約前後で主な要因として抽出される上位５イベントに差異が少ないということを確認することを目的とし、Ｐ２（ｖ；Ｒ２）が大きくなる上位５つのｖ∈Ｖ（Ｇ２）と、Ｐ'２（ｖ；Ｒ２）が大きくなる５つのｖ∈Ｖ（Ｇ'２）を求め、両者を比較する。
【００６０】
［結果］
要約前のグラフＧ２の５０のノード数に対し、要約後のグラフＧ'２のノード数は４０となった。要約前のグラフＧ２を図６に示し、要約後のグラフＧ'２を図７に示す。
【００６１】
評価１：要約後のグラフＧ'２の任意のノードｕ，ｖ∈Ｖ（Ｇ'２）に対してノードｕのインデックスを縦軸、ノードｖのインデックスを横軸にとった時の｜Ｐ２（ｖ；｛ｕ｝）−Ｐ'２（ｖ；｛ｕ｝）｜の値をヒートマップで表すと図８のようになった。ほとんどのｕ，ｖのペアでは、｜Ｐ２（ｖ；｛ｕ｝）−Ｐ'２（ｖ；｛ｕ｝）｜の値は０．１以下となった。これは、Ｒ２＝｛ｖ｝とした際、グラフ要約の前後でイベントｕの要因度の差がほぼ０．１以内で収まっていることを表している。
【００６２】
評価２：Ｐ２（ｖ；Ｒ２）が大きくなる上位５つのｖ∈Ｖ（Ｇ２）のインデックスと、Ｐ'２（ｖ；Ｒ２）が大きくなる５つのｖ∈Ｖ（Ｇ'２）のインデックスとは表１のようになった。
【００６３】
【表１】
2020119261.tif 000009
多少の順序の入れ替わりはあるものの、上位５つのうち４つのインデックスは両方に現れており、要約前後で要因推定の結果はほぼ一致していることが分かる。
【００６４】
上述したように、本実施の形態によれば、過去の情報の伝播を因果グラフによる要因推定に適する形で行い、その結果を基に不要なノードを検出することでグラフを要約する。すなわち、過去の情報を用いて各ノードの重要度を決定することで、重要でない頂点を検出する。この重要度は真の要因度以上の値に収束することが示せるから、要因となる可能性が高いノードは要約後も残すことができる。その結果、システム運用における因果グラフによる要因推定の精度の低下を抑制可能なグラフ要約を実現することができる。
【００６５】
また、単純な構造において、ノード削除前後で要因度が変化しないように辺の重みを決定することで、要約の前後で要因推定の結果に変化が少なくなる。さらに、隣接行列の固有値を計算することで、要約後のグラフはサイクル構造を持たないことが達成できる。隣接行列の構造を考慮すると、この固有値計算は少ない計算量で達成できる。
【００６６】
すなわち、障害によって得られたイベントの因果関係を表す因果グラフを、できるだけ重要なイベントを残し、かつ、要因推定の結果に与える影響を出来るだけ小さくするように、かつ、グラフの構造を保って要約することで、ある程度の正確性を保ったまま要因推定を高速化できる。さらに、要約後のグラフで要因度が高かったノードの周辺のみ、削除した頂点を元に戻して再度要因推定を行えば、さらなる正確性を達成できる。これにより、障害発生時の対応を、正確性を保ったまま高速化できる。
【００６７】
なお、本実施の形態において、障害要因推定装置１０は、因果グラフ要約装置の一例である。検出部１１は、計算部及び選択部の一例である。
【００６８】
以上、本発明の実施の形態について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００６９】
１０          障害要因推定装置
１１          検出部
１２          決定部
１３          削除部
１００        ドライブ装置
１０１        記録媒体
１０２        補助記憶装置
１０３        メモリ装置
１０４        ＣＰＵ
１０５        インタフェース装置
Ｂ            バス
【図１】
2020119261.tif 000010
【図２】
2020119261.tif 000011
【図３】
2020119261.tif 000012
【図４】
2020119261.tif 000013
【図５】
2020119261.tif 000014
【図６】
2020119261.tif 000015
【図７】
2020119261.tif 000016
【図８】
2020119261.tif 000017