(57)【特許請求の範囲】
【請求項１】
イベントログ列の集合からプロセスを抽出するプロセス抽出装置であって、
前記イベントログ列の集合に基づいて、前記プロセスの分岐点となる可能性のある１以上の分岐点候補を獲得する獲得部と、
前記分岐点候補ごとに前記各イベントログ列における分岐先の部分イベントログ列の集合を抽出し、抽出された部分イベントログ列の集合から分岐先のサブプロセスを獲得し、前記プロセスに関して要求される条件に対する最適化問題を、前記各分岐点候補と前記分岐点候補ごとに獲得されたサブプロセスとに関して解くことで、前記分岐点候補の中から前記プロセスの分岐点を選択する選択部と、
を有することを特徴とするプロセス抽出装置。
【請求項２】
前記選択部によって前記分岐点として選択された前記分岐点候補に関して抽出された前記部分イベントログ列の集合について、再帰的に分岐点を探索する、
ことを特徴とする請求項１記載のプロセス抽出装置。
【請求項３】
前記選択部は、前記部分イベントログ列をクラスタリングすることにより得られるクラスタごとに、前記サブプロセスを獲得する、
ことを特徴とする請求項１又は２記載のプロセス抽出装置。
【請求項４】
イベントログ列の集合からプロセスを抽出するプロセス抽出方法であって、
コンピュータが、
前記イベントログ列の集合に基づいて、前記プロセスの分岐点の候補である１以上の分岐点候補を獲得する獲得手順と、
前記分岐点候補ごとに前記各イベントログ列における分岐先の部分イベントログ列の集合を抽出し、抽出された部分イベントログ列の集合から分岐先のサブプロセスを獲得し、前記プロセスに関して要求される条件に対する最適化問題を、前記各分岐点候補と前記分岐点候補ごとに獲得されたサブプロセスとに関して解くことで、前記分岐点候補の中から前記プロセスの分岐点を選択する選択手順と、
を実行することを特徴とするプロセス抽出方法。
【請求項５】
前記選択手順において前記分岐点として選択された前記分岐点候補に関して抽出された前記部分イベントログ列の集合について、再帰的に分岐点を探索する、
ことを特徴とする請求項４記載のプロセス抽出方法。
【請求項６】
前記選択手順は、前記部分イベントログ列をクラスタリングすることにより得られるクラスタごとに、前記サブプロセスを獲得する、
ことを特徴とする請求項４又は５記載のプロセス抽出方法。
【請求項７】
請求項４乃至６いずれか一項記載のプロセス抽出方法を、コンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プロセス抽出装置、プロセス抽出方法、及びプログラムに関する。
【背景技術】
【０００２】
大規模化・構成機器の多様化が進むＩＴネットワークシステムにおいて、システム上で発生する故障事例が多様化しており、発生した異常の原因究明と対処判断とが従来よりも困難になっている。一方で、あらゆる故障事例を解決可能なエキスパートと呼ばれるオペレータは、運用管理すべきシステムの数と比較して圧倒的に少ない。また、近年では特に運用管理の対象となるシステムの大規模化と運用期間の長期化が進んだため、特定の個人のエキスパートのみの活動に依存したシステム運用は困難である。そのため、高いスキルを持つエキスパートによる故障回復手順を、オペレーションチーム全体へ共有する手段が求められている。ここでは、エキスパートを含むオペレータらによる、問題の見極めから対処完了までの一連の故障回復手順を、プロセスと定義する。
【０００３】
一般に、プロセスは、問題が複雑であるほど暗黙知であることが多い。そのため、プロセスの獲得には、オペレータ自身も把握していない情報を得る手段が必要となる。これに対し、オペレータの行動をイベントログと呼ばれるデータとして蓄積し、複数のイベントログの集合からオペレータ自身も把握していない定型的な一連の手順を特定のモデル形式で抽出する、プロセスマイニングと呼ばれる手法があり（例えば、非特許文献１参照）、マイニング用のアプリケーションが存在する（例えば、非特許文献２参照）。
【０００４】
非特許文献２に示されているプロセスマイニング手法は、イベントログから単一のプロセスのみを抽出することを前提としており、複数の異なる事象に対する問題解決の記録が含まれる、故障対応時の操作履歴のようなイベントログへの適用は困難である。例えば、あるＷｅｂサーバが接続不可となった場合の対処を考える。Ｗｅｂサーバに接続不可の場合、オペレータは、まず、ｐｉｎｇコマンド等で外部端末からＷｅｂサーバに疎通可能かどうかを確認する。疎通不可能であれば、オペレータは、Ｗｅｂサーバの配置場所に赴き原因確認を行う。疎通可能ならば、オペレータは、原因となるアプリケーションをログ確認等によって特定する。アプリケーションが原因であれば、オペレータは、当該アプリケーションに応じた負荷を下げる対処を行う。
【０００５】
上記の例の場合、Ｗｅｂサーバ接続不可という同一の異常発生であっても、複数の原因が存在し、また原因ごとに取るべき対処が異なる。これらの複数の原因と各原因に対する対処との違いを考慮して予めイベントログを原因別に分類することは、原因を特定する手段が無いために困難である。そのため、イベントログを蓄積するデータベースには、複数の原因事例と対処事例とが混在している。
【０００６】
一方で、異なるアプリケーションの故障回復手順であっても、同一の作業が含まれる場合がある。例えば、Ｗｅｂサーバ接続不可の原因が、暴走したアプリケーションである場合、再発防止の対処はアプリケーションごとに異なるが、いずれの場合でも「システムの再起動」という作業が含まれ得る。また、実際のシステム運用では、「装置起動ランプ点灯状態の確認」のような、故障原因に依らず実施が必要な作業も多く存在する。
【０００７】
更に、実際のイベントログにおいては、イベントログの欠損及びノイズとなる作業が含まれる。例えば、故障原因の特定時における、原因ではないアプリケーションのステータス確認等は、作業を実施するオペレータによって実施の有無が異なる。
【０００８】
上記のような事情を考慮せずに、図１に例示されるイベントログの集合を用いて非特許文献３に記載された手法でプロセスを構成した結果が、図２である。図２では、異常要因に対する異なる２つの対処が絡み合ったプロセスが生成されており、プロセスの途中で実施すべき対処について、２度の判断がオペレータに求められる。
【０００９】
図１のような、異なる対処が混在したイベントログに対して従来手法を適用した場合、異なるサブプロセスが混ざり、直感的な原因の違いの把握が困難となる。なお、非特許文献３に記載された手法は、イベントログの集合を入力にして、与えられたイベントログを出力可能な、状態及び遷移数の最も少ない状態遷移グラフを出力する、という手法である。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】W.M.P. van der Aalst, "Process Mining: Discovery, Conformance and Enhancement of Business Processes". Springer, Berlin (2011), pp.125-156
【非特許文献２】Process Mining, http://www.processmining.org/prom/start
【非特許文献３】W.M.P. van der Aalst; T. Weijters; L. Maruster, "Workflow mining: discovering process models from event logs," IEEE Transactions on Knowledge and Data Engineering, vol.16, no.9, pp.1128-1142, September 2004
【非特許文献４】A.J.M.M. Weijters; J.T.S. Ribeiro, "Flexible Heuristics Miner (FHM)," 2011 IEEE Symposium on Computational Intelligence and Data Mining (CIDM), pp.310-317, 11-15 April 2011
【非特許文献５】Ulrike Luxburg, A tutorial on spectral clustering, Statistics and Computing, vol. 17, Issue 4, pp. 395-416, December 2007
【非特許文献６】W.M.P. van der Aalst; Christian Stahl, "Modeling Business Processes: A Petri Net-Oriented Approach", MIT Press, 2011, pp.91-127
【非特許文献７】渡邉暁, 木村達明, 豊野剛, 石橋圭介, "トラブルチケットにおける作業手順の構造化手法", 電子情報通信学会ソサイエティ大会, 2014
【非特許文献８】Dan Pelleg; Andrew W. Moore, X-means: Extending K-means with Efficient Estimation of the Number of Clusters. In Proceedings of the Seventeenth International Conference on Machine Learning (ICML '00), pp. 727-734., 2000
【発明の概要】
【発明が解決しようとする課題】
【００１１】
故障対応業務のように、原因を特定し、各原因に応じた対処を行う業務の場合、サブプロセスへの分岐点は、図３に示されるような、エキスパートが原因を特定するに至った分岐点を陽に含み、原因特定後の対処に係るサブプロセスが合流しないようなプロセスが獲得されることが望ましい。しかしながら、そのようなプロセス中のサブプロセスへの分岐点を抽出するのは従来の技術では困難であった。
【００１２】
本発明は、上記の点に鑑みてなされたものであって、異なるサブプロセスが混在するイベントログからプロセスが変化する分岐点と分岐後のサブプロセスを獲得可能とすることを目的とする。
【課題を解決するための手段】
【００１３】
そこで上記課題を解決するため、イベントログ列の集合からプロセスを抽出するプロセス抽出装置は、前記イベントログ列の集合に基づいて、前記プロセスの分岐点となる可能性のある１以上の分岐点候補を獲得する獲得部と、前記分岐点候補ごとに前記各イベントログ列における分岐先の部分イベントログ列の集合を抽出し、抽出された部分イベントログ列の集合から分岐先のサブプロセスを獲得し、前記プロセスに関して要求される条件に対する最適化問題を、前記各分岐点候補と前記分岐点候補ごとに獲得されたサブプロセスとに関して解くことで、前記分岐点候補の中から前記プロセスの分岐点を選択する選択部と、を有する。
【発明の効果】
【００１４】
異なるサブプロセスが混在するイベントログからプロセスが変化する分岐点と分岐後のサブプロセスを獲得可能とすることができる。
【図面の簡単な説明】
【００１５】
【図１】イベントログ集合の一例を示す図である。
【図２】非特許文献３の手法でプロセスを構成した結果の一例を示す図である。
【図３】原因特定後の対処に係るサブプロセスが合流しないプロセスの一例を示す図である。
【図４】本実施の形態によって可能となるサブプロセス及び分岐点の獲得結果の一例を示す図である。
【図５】本発明の実施の形態におけるプロセス抽出装置のハードウェア構成例を示す図である。
【図６】本発明の実施の形態におけるプロセス抽出装置の機能構成例を示す図である。
【図７】プロセス抽出装置が実行する処理手順の一例を説明するためのフローチャートである。
【図８】分岐先サブプロセスの決定方法の一例を説明するためのフローチャートである。
【発明を実施するための形態】
【００１６】
以下、図面に基づいて本発明の実施の形態を説明する。本実施の形態において、プロセスとは、エキスパートを含むオペレータらによる、ネットワークシステム等のコンピュータシステムの故障派生時における、問題の見極めから対処完了までの一連の故障回復手順をいう。エキスパートとは、あらゆる故障事例を解決可能なエキスパートと呼ばれるオペレータである。
【００１７】
本実施の形態において、図５及び図６に示されるプロセス抽出装置１０は、エキスパート等の行動が記録されたイベントログから、当該行動が変化した、プロセスの分岐点を得る問題を、最適化問題として定式化し、最適な分岐点集合及びサブプロセス集合を獲得する。サブプロセスとは、プロセスを分岐点に区切ることにより形成される、プロセスの構成要素となる部分的なプロセスをいう。
【００１８】
まず、本実施の形態で解くべき問題を定式化する。
【００１９】
プロセス抽出装置１０に対する入力として、イベントログ列集合Ｌが与えられているとする。このとき、イベントログ列集合Ｌは以下に示すようなデータである。
Ｌ＝｛Ｔｒ（１），Ｔｒ（２），...，Ｔｒ（｜Ｌ｜）｝
但し、Ｔｒ（ｉ）はｉ番目の入力イベントログ列である。また、｜・｜は集合・の要素数を表す。入力イベントログ列Ｔｒ（ｉ）は、イベントログが並べられた以下のデータであり、例えば、或る一つの故障回復手順に対応する。
Ｔｒ（ｉ）＝ｅ（ｉ）１ｅ（ｉ）２...ｅ（ｉ）｜Ｔｒｉ｜
ｅ（ｉ）ｊ∈Ａは、ｉ番目の入力イベントログ列のｊ番目のイベントログを示し、Ｔｒ（ｉ）のイベントログ数を｜Ｔｒｉ｜とする。Ａ＝｛ａ１，...，ａ｜Ａ｜｝は、入力イベントログ列に含まれ得るイベントログの集合であり、イベントログの種類数、即ち、Ａの要素数は、｜Ａ｜である。
【００２０】
次に、イベントログを並べた列である、サブプロセス集合Ｐを以下に定義する。
Ｐ（ｋ）＝ｅ（ｋ）１ｅ（ｋ）２...ｅ（ｋ）｜Ｐｋ｜
ｅ（ｋ）ｘ∈Ａは、ｋ番目のサブプロセス集合Ｐ（ｋ）におけるｘ番目のイベントログを示す。また、｜Ｐｋ｜は、Ｐ（ｋ）のイベントログ数を示す。なお、ここでは、サブプロセスがイベントログの系列データとなっているが、実際のサブプロセス集合Ｐは、有限オートマトンやＰｅｔｒｉ−ｎｅｔ等で表現される、状態遷移であることも考えられる（非特許文献１、非特許文献６参照）。
【００２１】
本実施の形態の目的の一つは、イベントログ列集合Ｌを生成し得るサブプロセス集合Ｐ＝｛Ｐ（１），...，Ｐ（｜Ｐ｜）｝を獲得することである。但し、｜Ｐ｜はサブプロセスの数を表す。
【００２２】
また、入力イベントログ列Ｔｒｉ∈Ｌに対し、いずれのサブプロセスの後に、いずれのサブプロセスが実行されるかを示す、ｉ番目の入力イベントログ列に対応する分岐点集合Ｂ（ｉ）を、次のように定義する。
Ｂ（ｉ）＝｛（ｂ（ｉ）１，ｆ（ｉ）１，ｔ（ｉ）１），...，（ｂ（ｉ）｜Ｂｉ｜，ｆ（ｉ）｜Ｂｉ｜，ｔ（ｉ）｜Ｂｉ｜）｝
但し、ｂ（ｉ）ｊ∈｛１，...，Ｔｉ｝は、分岐点の直前のイベントログの番号を、ｆ（ｉ）ｊ∈Ｐは、分岐前のサブプロセスを、ｔ（ｉ）ｊ∈Ｐは、分岐後のサブプロセスを示す。なお、イベントログの番号とは、入力イベントログ列Ｔｒｉの先頭からの当該イベントログの位置（すなわち、何番目のイベントログであるのか）を示す数値である。
【００２３】
また、｜Ｂｉ｜は、ｉ番目の入力イベントログ列に対する分岐点の数である。本実施の形態は、入力されるイベントログ列集合Ｌから、サブプロセス集合Ｐを獲得するとともに、各イベントログ列に対する分岐点集合の集合Ｂ＝｛Ｂ（１），…，Ｂ（｜Ｌ｜）｝を獲得する。
【００２４】
以下に、プロセス抽出装置１０への入力情報及びプロセス抽出装置１０からの出力情報の一例を示す。
【００２５】
入力として、イベントログ列集合Ｌ＝｛Ｔｒ（１）＝ｕｖｗｘｙ，Ｔｒ（２）＝ｕｖｙｚ｝が与えられたとする。このとき、
｜Ｌ｜＝２，
ｅ（１）２＝ｖ，ｅ（１）３＝ｗ，ｅ（２）４＝ｚ，
Ａ＝｛ｕ，ｖ，ｗ，ｘ，ｙ，ｚ｝，｜Ａ｜＝６，
である。なお、ここでは符号化して表現しているが、実際には各イベントログが、ｕ＝"ＣＰＵ負荷状態を確認する"、ｖ＝"Ｗｅｂサーバのログを確認する"等のように、何らかの作業やシステムログを示す。
【００２６】
ここでは、イベントログ列集合Ｌからとり得るサブプロセス集合のうち、サブプロセス集合中のイベントログ数ΣＫｋ=１ｗｋが最も少ないサブプロセス集合を考え、サブプロセス集合Ｐ＝｛Ｐ（１）＝ｕｖ，Ｐ（２）＝ｗｘｙ，Ｐ（３）＝ｙｚ｝を得たとする。このとき、
｜Ｐ｜＝３，
Ｂ＝｛Ｂ（１），Ｂ（２）｝，
Ｂ（１）＝｛（２，Ｐ（１），Ｐ（２））｝，
Ｂ（２）＝｛（２，Ｐ（１），Ｐ（３））｝，
｜Ｂ１｜＝｜Ｂ２｜＝１，
と表記できる。
【００２７】
上記のイベントログ列集合Ｌ、サブプロセス集合Ｐ、及び分岐点集合Ｂを用いると、イベントログ列を示すプロセスは、図４のように表現可能となる。イベントログ列集合Ｌのみを用いてα−ａｌｇｏｒｉｔｈｍと呼ばれる非特許文献３の手法により生成される図２のプロセス等と比較すると、図４に示されるプロセスでは、異なるサブプロセスへの遷移が明確にプロセス上に表現される。
【００２８】
以上より、本実施の形態のプロセス抽出装置１０は、上記の例のような、入力となるイベントログ列Ｌ（ｉ）∈Ｌに対して、分岐点集合Ｂ及びサブプロセス集合Ｐを得るコンピュータある。本問題は、最適化問題として一般化可能である。
（Ｂ，Ｐ）＝ａｒｇｍａｘ（Ｂ＊，Ｐ＊）Ｓ（Ｌ，Ｂ＊，Ｐ＊）  ・・・（１）
なお、上記では、イベントログ数ΣＫｋ=１｜Ｐｋ｜が最も少ないサブプロセス集合を得ることを条件として、サブプロセス集合Ｐ及び分岐点集合Ｂが獲得されたが、本実施の形態の特長は、入力されるイベントログ列集合Ｌにおいて、抽出されるプロセスに関して要求される条件に対する分岐点集合Ｂ及びサブプロセス集合Ｐを自動的に得られるという点であり、要求される条件、並びに要求される条件に合ったサブプロセス及び分岐点を得る手法は問わない。式（１）のスコア関数Ｓの定義によって、獲得される分岐点集合Ｂ及びサブプロセス集合Ｐを自由に変化させることが可能である。例えば、任意のサブプロセス中のイベントログｐ（ｋ）ｘから全てのイベントログへの情報エントロピーを最大化する問題と定義して、スコア関数Ｓを次のように表せる。
Ｓ（Ｌ，Ｂ，Ｐ）＝Σｐ（ｋ１）ｘ１∈ＰΣｐ（ｋ２）ｘ２∈ＰＥ（ｐ（ｋ１）ｘ１，ｐ（ｋ２）ｘ２）
Ｅ（ｐ（ｋ１）ｘ１，ｐ（ｋ１）ｘ１）＝−Ｐｒ（ｐ（ｋ２）ｘ２｜ｐ（ｋ１）ｘ１）ｌｏｇＰｒ（ｐ（ｋ２）ｘ２｜ｐ（ｋ１）ｘ１）
Ｐｒ（ｐ（ｋ２）ｘ２｜ｐ（ｋ１）ｘ１）＝ｃｏｕｎｔ（ｐ（ｋ２）ｘ２，ｐ（ｋ１）ｘ１）／ｃｏｕｎｔ（ｐ（ｋ１）ｘ１）
但し、ｃｏｕｎｔ（ｐ（ｋ１）ｘ１）は、イベントログ列集合Ｌにおけるｐ（ｋ１）ｘ１の出現回数を、ｃｏｕｎｔ（ｐ（ｋ２）ｘ２，ｐ（ｋ１）ｘ１）は、ｐ（ｋ２）ｘ２とｐ（ｋ１）ｘ１とが共に出現するイベントログ列の回数を表すものとする。また、簡略化のためサブプロセス集合Ｐに含まれる任意のサブプロセスにおけるイベントログ全ての集合を、ｐ（ｋ）ｘ∈Ｐと表記している。
【００２９】
以下、プロセス抽出装置１０について、具体的に説明する。図５は、本発明の実施の形態におけるプロセス抽出装置のハードウェア構成例を示す図である。図５のプロセス抽出装置１０は、それぞれバスＢで相互に接続されているドライブ装置１００、補助記憶装置１０２、メモリ装置１０３、ＣＰＵ１０４、及びインタフェース装置１０５等を有する。
【００３０】
プロセス抽出装置１０での処理を実現するプログラムは、ＣＤ−ＲＯＭ等の記録媒体１０１によって提供される。プログラムを記憶した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００３１】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムに従ってプロセス抽出装置１０に係る機能を実行する。インタフェース装置１０５は、ネットワークに接続するためのインタフェースとして用いられる。
【００３２】
図６は、本発明の実施の形態におけるプロセス抽出装置の機能構成例を示す図である。図６において、プロセス抽出装置１０は、初期化部１１、分岐点存在判定部１２、分岐点候補獲得部１３、分岐点選択部１４、終了条件判定部１５、及び出力部１６等を有する。これら各部は、プロセス抽出装置１０にインストールされる１以上のプログラムが、ＣＰＵ１０４に実行させる処理により実現される。プロセス抽出装置１０は、また、イベントログ列集合記憶部１７を利用する。イベントログ列集合記憶部１７は、例えば、補助記憶装置１０２、又はプロセス抽出装置１０にネットワークを介して接続可能な記憶装置等を用いて実現可能である。
【００３３】
イベントログ列集合記憶部１７には、プロセスの抽出処理の入力となる、イベントログ列の集合（イベントログ列集合）が記憶されている。入力となるイベントログ列は、作業に該当するＩＤ化されたログの系列データであれば、どのようなものでも構わない。例えば、ＩＴマネジメントシステムにおける、或る故障に関して記録された、オペレータの入力コマンドの系列データ等がイベントログ列であってもよい。また、非特許文献７によって出力された、作業履歴の各作業がＩＤ化されたデータを用いて、自然言語のデータを元にしたイベントログが用いられてもよい。更に、システム動作が記録されたｓｙｓｌｏｇ等、人間の行動に対する記録でなく情報が、イベントログ列として用いられてよい。但し、イベントログ列集合は、異なるサブプロセスが混在するイベントログの集合であるとする。なお、プロセスの抽出処理とは、実質的に、プロセスの分岐点及びプロセスを構成するサブプロセスの抽出処理に相当する。
【００３４】
初期化部１１は、プロセスの抽出処理における初期化処理を実行する。例えば、初期化部１１によって、イベントログ列集合記憶部１７に記憶されているイベントログ列集合が読み込まれる。
【００３５】
分岐点存在判定部１２は、分岐点の探索対象内における、分岐点の有無を判定する。最初に分岐点の探索対象とされるのは、初期化部１１によって読み込まれたイベントログ列集合である。
【００３６】
分岐点候補獲得部１３は、イベントログ列集合に基づいて、プロセスの分岐点の候補である１以上の分岐点候補を獲得する。
【００３７】
分岐点選択部１４は、分岐点候補ごとに各イベントログ列における分岐先の部分イベントログ列の集合を抽出し、抽出された部分イベントログ列の集合から分岐先のサブプロセスを獲得し、抽出されるプロセスに関して要求される条件に対する最適化問題を、各分岐点候補と分岐点候補ごとに獲得されたサブプロセスとに関して解くことで、分岐点候補の中から前記プロセスの分岐点を選択する。なお、分岐点の選択によってサブプロセスも獲得される。すなわち、当該分岐点として選択された分岐点候補に関して獲得されたサブプロセスが、目的とされるサブプロセスである。
【００３８】
終了条件判定部１５は、分岐点存在判定部１２、分岐点候補獲得部１３、及び分岐点選択部１４による再帰的な処理について、終了条件が満たされたか否かを判定する。
【００３９】
出力部１６は、獲得された分岐点及びサブプロセスを示す情報を出力する。
【００４０】
以下、プロセス抽出装置１０が実行する処理手順について説明する。図７は、プロセス抽出装置が実行する処理手順の一例を説明するためのフローチャートである。上記の問題は、特にサブプロセス集合Ｐのとり得る組み合わせが指数的に増大するため、最適解を得るための計算量は膨大となる。そこで、以下では近似解の計算方法の一例として、図７に基づいて、分岐後のイベントログ列から再帰的に分岐点を探索し、分岐点集合Ｂを順次得る手法を、詳細に説明する。
【００４１】
ステップＳ１０１において、初期化部１１は、初期化処理を実行する。初期化処理において、イベントログ列集合記憶部１７からイベントログ列集合が読み込まれ、読み込まれたイベントログ列集合がＬとされる。また、分岐点探索対象Ｌ＊＝Ｌとされる。また、分岐点集合Ｂ＝｛｝、サブプロセス集合Ｐ＝｛｝とされる。更に、終了条件パラメータθ等が読み込まれる。
【００４２】
続いて、分岐点存在判定部１２は、分岐点探索対象Ｌ＊中に分岐点が存在する可能性の有無を判定する（ステップＳ１０２）。例えば、分岐点探索対象Ｌ＊のイベントログ列数｜Ｌ＊｜≦θならば、分岐点が無いと判定されてもよい。
【００４３】
分岐点が存在する可能性が無いと判定された場合（ステップＳ１０２でＮｏ）、分岐点選択部１４は、分岐点探索対象Ｌ＊からサブプロセスを獲得し、獲得されたサブプロセスをサブプロセス集合Ｐに追加する（ステップＳ１０８）。サブプロセス集合Ｐの獲得方法は、所定の方法に限定されない。例えば、非特許文献３や非特許文献４等のプロセスマイニング手法が適用されてサブプロセスが獲得されてもよい。
【００４４】
分岐点が存在する可能性が有ると判定された場合（ステップＳ１０２でＹｅｓ）、分岐点候補獲得部１３は、分岐点の候補（以下、「分岐点候補ｃ」とう。）の集合である分岐点候補集合Ｃを獲得する（ステップＳ１０３）。分岐点候補の獲得方法は、所定の方法に限定されない。例えば、イベントログ集合の要素ｅ∈Ａの全てが分岐点候補ｃとされてもよい。なお、分岐点候補集合Ｃを構成する各分岐点候補ｃの値は、ログ番号である。例えば、イベントログ列集合Ｌ＝｛Ｔｒ（１）＝ｕｖｗｘｙ，Ｔｒ（２）＝ｕｖｙｚ｝が与えられている場合において、イベントログ集合の要素ｅ∈Ａの全てが分岐点候補ｃとされる場合、分岐点候補集合Ｃ＝｛１，２，３，４｝となる。
【００４５】
続く、ステップＳ１０４及びＳ１０５において、分岐点選択部１４は、ステップＳ１０３において獲得された分岐点候補集合Ｃにおける各分岐点候補ｃの中から最適分岐点を選択するための処理を実行する。最適分岐点とは、分岐点として確定される分岐点候補ｃをいう。
【００４６】
最適分岐点の選択方法は、抽出されるプロセスに関して要求される条件によって異なる。当該条件は、図７の開始時に、パラメータとして入力されてもよい。ここでは、分岐後の各イベントログへの遷移確率エントロピーが最小化されれば、分岐後のサブプロセスがまとまりのあるイベントログの集合になるという仮定に基づき、情報エントロピーを最小化する分岐点候補ｃが最適分岐点として選択される例について説明する。
【００４７】
ステップＳ１０４において、分岐点選択部１４は、各分岐点候補ｃにおける分岐先サブプロセスを決定するための処理を実行する。各分岐点候補ｃにおける分岐先サブプロセスの決定方法の一例については、図８を用いて説明する。
【００４８】
図８は、分岐先サブプロセスの決定方法の一例を説明するためのフローチャートである。図８において、ステップＳ２０１〜Ｓ２０６は、分岐点候補ｃごとに実行される。以下、処理対象とされている分岐点候補ｃを、「対象候補」という。
【００４９】
ステップＳ２０１において、分岐点選択部１４は、各入力イベントログ列Ｔｒ（ｉ）から、対象候補以前の部分イベントログ列を抽出する。抽出された部分イベントログ列の集合を、Ｔｒ（ｉ）ｐｒｅ∈Ｌ＊ｐｒｅと表す。例えば、５つの入力イベントログ列Ｔｒ（ｉ）から抽出される部分イベントログ列の数は、５（すなわち、Ｔｒ（ｉ）ｐｒｅの要素数は、５）である。
【００５０】
続いて、分岐点選択部１４は、各入力イベントログ列Ｔｒ（ｉ）から、対象候補の直後以降の部分イベントログ列を抽出する。抽出された部分イベントログ列の集合を、Ｔｒ（ｉ）ｐｏｓ∈Ｌ＊ｐｏｓと表す。例えば、５つの入力イベントログ列Ｔｒ（ｉ）から抽出される部分イベントログ列の数は、５（Ｔｒ（ｉ）ｐｏｓの要素数は、５）である。
【００５１】
続いて、分岐点選択部１４は、Ｌ＊ｐｏｓの要素（Ｔｒ（ｉ）ｐｏｓ）をκ個にクラスタリングする（ステップＳ２０３）。各クラスタは、分岐後の各イベントログ列の遷移先サブプロセスに対応するイベントログ列である。ここで、分岐点候補ｃ（ｍ）におけるＴｒ（ｉ）ｐｏｓ∈Ｌ＊ｐｏｓのクラスタリング結果を、ＣＬ（ｍ）＝｛Ｌ（ｍ）１，…，Ｌ（ｍ）κ｝と表現する。
【００５２】
なお、クラスタ数κは、事前パラメータとして設定されてもよいし、非特許文献８に記載された手法等が用いられて自動的に決定されてもよい。また、クラスタリング方法も所定の方法に限定されない。例えば、グラフカットを最小化するクラスタリング手法として、Ｓｐｅｃｔｒａｌ  Ｃｌｕｓｔｅｒｉｎｇ（非特許文献５参照）等が利用されてもよい。
【００５３】
続いて、分岐点選択部１４は、各クラスタＬ（ｍ）κ∈ＣＬ（ｍ）それぞれについて、１つのサブプロセスＰ（ｍ）κを獲得する（ステップＳ２０４）。サブプロセスの獲得方法は、所定の方法に限定されない。例えば、非特許文献３や非特許文献４等に記載されたプロセスマイニング手法が利用されてもよい。
【００５４】
続いて、分岐点選択部１４は、イベントログ列集合Ｌ＊ｐｒｅについても、ステップＳ２０４と同様の方法で、１つのサブプロセスＰ（ｍ）ｐｒｅを獲得する（ステップＳ２０５）。すなわち、Ｌ＊ｐｒｅについては、クラスタリングは行われずに（或いは、Ｌ＊ｐｒｅが一つのクラスとして扱われて）、サブプロセスＰ（ｍ）ｐｒｅが獲得される。
【００５５】
続いて、分岐点選択部１４は、対象候補で分岐した場合の分岐点候補集合を、例えば、以下の演算によって全分岐点候補ｃ（ｍ）に関する分岐点候補集合Ｂ（ｉ）（ｍ）に追加することにより、分岐点候補集合Ｂ（ｉ）（ｍ）を更新する（ステップＳ２０６）。
Ｂ（ｉ）（ｍ）＝Ｂ（ｉ）（ｍ）∪｛（ｃ（ｍ），Ｐｐｒｅ，Ｐ（ｉ）（ｍ）κ）｝。
但し、Ｐ（ｉ）（ｍ）κは分岐点以降の部分イベントログ列Ｔｒ（ｉ）に該当するサブプロセスを示す。
【００５６】
したがって、例えば、ステップＳ２０４において獲得されるサブプロセスＰ（ｍ）ｐｒｅの数が、３であれば、３個の要素が、Ｂ（ｉ）（ｍ）に追加される。この３個の要素に関して、Ｐｐｒｅの値は、共通である。
【００５７】
上記したステップＳ２０１〜ステップＳ２０６が実行されることで、分岐点候補集合Ｂ（ｉ）（ｍ）には、各分岐点候補ｃで分岐した場合の情報が登録される。
【００５８】
図７に戻る。ステップＳ１０４に続いて、分岐点選択部１４は、分岐点候補集合Ｂ（ｉ）（ｍ）に属する各分岐点候補において分岐した場合のスコアを計算し、分岐点候補集合Ｂ（ｉ）（ｍ）の中から、最適分岐点を選択する（ステップＳ１０５）。すなわち、分岐を行なった場合のサブプロセス集合Ｐ（ｍ）＝｛Ｐ（ｍ）ｐｒｅ｝∪｛Ｐ（ｍ）１，…，Ｐ（ｍ）κ｝について、以下のスコア関数Ｓを最小化する最適分岐点Ｂ＊及びサブプロセスＰ＊が獲得される。
（Ｂ＊，Ｐ＊）＝ａｒｇｍａｘ（Ｂ（ｍ），Ｐ（ｍ））Ｓ（Ｌ，Ｂ（ｍ），Ｐ（ｍ））
続いて、終了条件判定部１５は、ステップＳ１０５において選択された最適分岐点Ｂ＊が、終了条件を満たすか否かを判定する（ステップＳ１０６）。終了条件は、所定のものに限定されない。例えば、Ｓ（Ｌ，Ｂ＊，Ｐ＊）が、閾値γを超えていなければ終了条件が充足されてもよい。また、分岐後のクラスタ数κ＝１であれば終了条件が充足されてもよい。
【００５９】
終了条件が満たされない場合（ステップＳ１０６でＮｏ）、終了条件判定部１５は、ステップＳ１０５において選択された最適分岐点Ｂ＊を分岐点集合Ｂに追加し、更に、サブプロセス集合ＰをＰ＝Ｐ∪｛Ｐ＊ｐｒｅ｝∪｛Ｐ＊１，…，Ｐ＊κ｝として更新する（ステップＳ１０７）。続いて、Ｌ＊κ∈ＣＬ＊全てに対し、再帰的にステップＳ１０２以降が実行される。すなわち、最適分岐点Ｂ＊として選択された分岐点候補に関して得られた各クラスタのそれぞれが、新たな探索対象Ｌ＊とされて、再帰的にステップＳ１０２以降が実行される。
【００６０】
一方、終了条件が満たされた場合（ステップＳ１０６でＹｅｓ）、分岐点集合Ｂ及びサブプロセス集合Ｐの更新は行われない。当該処理が再帰的に呼び出された処理であれば、呼び出し元の処理の制御が返却される。当該処理が、再帰的に呼び出された処理でない場合（大元の処理である場合）、出力部１６が、分岐点集合Ｂ及びサブプロセス集合Ｐの内容を出力してもよい。
【００６１】
例えば、各イベントログ列に対する、分岐点集合Ｂ及びサブプロセス集合Ｐがユーザに提示されてもよい。ユーザはイベントログ中に存在するサブプロセスと、サブプロセスを実行するための分岐条件を見ることが可能となり、提示された情報を、例えば、故障発生時の対応フローチャートの生成等に用いることができる。
【００６２】
なお、イベントログ列集合Ｌの入力と、分岐点集合Ｂ及びサブプロセス集合Ｐの提示は、同期的に行われなくてもよい。
【００６３】
上述したように、本実施の形態によれば、イベントログ中のプロセスの分岐点及びサブプロセスの抽出を実現し、複数の異なるサブプロセスが含まれるイベントログに対するプロセスマイニングを実現可能とすることができる。すなわち、異なるサブプロセスが混在するイベントログからプロセスが変化する分岐点と、分岐後のサブプロセスを獲得可能とすることができる。
【００６４】
なお、本実施の形態において、分岐点候補獲得部１３は、獲得部の一例である。分岐点選択部１４は、選択部の一例である。
【００６５】
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００６６】
１０          プロセス抽出装置
１１          初期化部
１２          分岐点存在判定部
１３          分岐点候補獲得部
１４          分岐点選択部
１５          終了条件判定部
１６          出力部
１７          イベントログ列集合記憶部
１００        ドライブ装置
１０１        記録媒体
１０２        補助記憶装置
１０３        メモリ装置
１０４        ＣＰＵ
１０５        インタフェース装置
Ｂ            バス
【図１】
0006263487.tif 000002
【図２】
0006263487.tif 000003
【図３】
0006263487.tif 000004
【図４】
0006263487.tif 000005
【図５】
0006263487.tif 000006
【図６】
0006263487.tif 000007
【図７】
0006263487.tif 000008
【図８】
0006263487.tif 000009