(57)【特許請求の範囲】
【請求項１】
オペレータの一連の操作によって記録された作業ログに基づき、コンピュータの処理によってワークフローを生成する方法であって、
前記コンピュータの処理によって、前記作業ログに基づき、作業グラフを生成するステップと、
前記コンピュータの処理によって、前記生成された作業グラフから、冗長グラフを特定して除去するステップと、
前記コンピュータの処理によって、前記除去された冗長グラフに対応して、前記作業ログからエントリを削除することにより、前記作業ログを簡易化するステップと、
前記コンピュータの処理によって、各ログ・エントリが満たすべき制約の集合を読み取るステップであって、該各制約は、変数をもつ正規表現を含む式を定義するものであるステップと、
前記コンピュータの処理により、用意された正規表現の初期値に対して前記制約を適用することによって、該正規表現を変形させるステップと、
前記コンピュータの処理により、前記簡易化されたログに対して、前記変形された正規表現が妥当かどうかを判断するステップと、
前記コンピュータの処理によって、前記変形された正規表現が妥当であると判断されたことに応答して、前記変形された正規表現に基づき、有限状態遷移系を生成することによって、ワークフローのグラフを生成するステップを有する、
ワークフローの生成方法。
【請求項２】
前記変形された正規表現が妥当かどうかを判断するステップは、前記簡易化されたログが含む複数のログ・トレースのうち、前記変形された正規表現が受理するログ・トレースの割合が、所定の閾値よりも大きいことに基づき妥当と判断する、請求項１に記載の方法。
【請求項３】
前記正規表現を変形させるステップは、前記適用される制約の変数を消すように前記正規表現を変形させる、請求項１に記載の方法。
【請求項４】
前記用意された正規表現の初期値が、.*である、請求項１に記載の方法。
【請求項５】
オペレータの一連の操作によって記録された作業ログに基づき、コンピュータの処理によってワークフローを生成するプログラムであって、
前記コンピュータをして、
前記作業ログに基づき、作業グラフを生成するステップと、
前記生成された作業グラフから、冗長グラフを特定して除去するステップと、
前記除去された冗長グラフに対応して、前記作業ログからエントリを削除することにより、前記作業ログを簡易化するステップと、
各ログ・エントリが満たすべき制約の集合を読み取るステップであって、該各制約は、変数をもつ正規表現を含む式を定義するものであるステップと、
用意された正規表現の初期値に対して前記制約を適用することによって、該正規表現を変形させるステップと、
前記簡易化されたログに対して、前記変形された正規表現が妥当かどうかを判断するステップと、
前記変形された正規表現が妥当であると判断されたことに応答して、前記変形された正規表現に基づき、有限状態遷移系を生成することによって、ワークフローのグラフを生成するステップを実行させる、
ワークフローの生成プログラム。
【請求項６】
前記変形された正規表現が妥当かどうかを判断するステップは、前記簡易化されたログが含む複数のログ・トレースのうち、前記変形された正規表現が受理するログ・トレースの割合が、所定の閾値よりも大きいことに基づき妥当と判断する、請求項５に記載のプログラム。
【請求項７】
前記正規表現を変形させるステップは、前記適用される制約の変数を消すように前記正規表現を変形させる、請求項５に記載のプログラム。
【請求項８】
前記用意された正規表現の初期値が、.*である、請求項５に記載のプログラム。
【請求項９】
オペレータの一連の操作によって記録された作業ログに基づき、コンピュータの処理によってワークフローを生成するシステムであって、
前記作業ログに基づき、作業グラフを生成する手段と、
前記生成された作業グラフから、冗長グラフを特定して除去する手段と、
前記除去された冗長グラフに対応して、前記作業ログからエントリを削除することにより、前記作業ログを簡易化する手段と、
各ログ・エントリが満たすべき制約の集合を読み取る手段であって、該各制約は、変数をもつ正規表現を含む式を定義するものである手段と、
用意された正規表現の初期値に対して前記制約を適用することによって、該正規表現を変形させる手段と、
前記簡易化されたログに対して、前記変形された正規表現が妥当かどうかを判断する手段と、
前記変形された正規表現が妥当であると判断されたことに応答して、前記変形された正規表現に基づき、有限状態遷移系を生成することによって、ワークフローのグラフを生成する手段を有する、
ワークフローの生成システム。
【請求項１０】
前記変形された正規表現が妥当かどうかを判断する手段は、前記簡易化されたログが含む複数のログ・トレースのうち、前記変形された正規表現が受理するログ・トレースの割合が、所定の閾値よりも大きいことに基づき妥当と判断する、請求項９に記載のシステム。
【請求項１１】
前記正規表現を変形させる手段は、前記適用される制約の変数を消すように前記正規表現を変形させる機能をもつ、請求項９に記載のシステム。
【請求項１２】
前記用意された正規表現の初期値が、.*である、請求項９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、コンピュータ可読媒体に記録された作業ログを解析して、業務プロセスを抽出するための業務プロセス解析方法、システム及びプログラムに関するものである。
【背景技術】
【０００２】
近年、ビジネスが不可避的にグローバル化し、クラウド上でサービス向けの計算が普及してくると、ビジネスの処理手順が、利害関係者にとって一層みえにくいものとなってる。一方、ビジネス・プロセス管理（ＢＰＭ）が、より一層、企業の執行役員の注目を浴びつつある。例えば、企業の最高情報責任者のトップ・プライオリティは、業務プロセス改善である。
【０００３】
従来の商用ＢＰＭ解決ツールは主として、構造化された業務プロセス、すなわち、定形且つ具体的なルールに従うワークフローをサポートするものである。このようなツールは、経費管理や購買処理などの形式が決まったワークフローを自動化するのに適している。
【０００４】
ＢＰＭ技術は、そのような定形のワークフローによって生成されたイベント・ログを解析して、実際の業務の状況を可視化することが可能である。
【０００５】
しかしながら、定形ワークフローとしてモデル化することが容易でないさまざまな適用業務分野が存在する。すなわち、業務がほとんど、あるいは全く構造化されておらず、きわめて動的で、人への依存性が高く、その場しのぎの要素が大きいものである。
【０００６】
ケース・マネジメント(Case Management)や適応的ワークフローの概念は、ユーザーが動的にプロセスを変更し、恣意的な態様で新しいプロセスを作成するような迅速(agile)プロセスに対応するソリューションを代表するものである。例えば、事業、医務査定、及び保険査定におけるさまざまなリスク評価は、リスク管理者、現場の査定者、審査担当者、医師、法律家、査定人等の様々な役割の人による、動的且つ人中心の判断を要する、典型的な実世界の業務の一つである。
【０００７】
ほとんど、または全く構造化されていないプロセスに関する最も主要な問題点は、実際に起こっていること、すなわち、誰がどのタスクをどの順序で行っているかをを視覚化することが難しいということである。もしそのようなプロセスが、ある一元化された業務エンジンによって管理されているなら、視覚化も、さほど困難ではない。しかし、現実的には、人々は、電子メール、チャット、及び個別の業務ツールを使って協業する傾向がある。
【０００８】
従来知られているα−アルゴリズムのようなプロセス・マイニング技法は、所与のイベント・ログから構造化されたビジネス・プロセスを視覚化するには有効であるが、構造化されていないビジネス・プロセスにはあまり有効ではない。すなわち、構造化されていないビジネス・プロセスにプロセス・マイニングを適用しても、単に複雑で整理されていない結果が得られるだけで、アナリストが期待するものからはるかに隔たったものであるにすぎない。
【０００９】
そこで最近になって、HeuristicMinerと呼ばれるプロセス・マイニング技法が、A. J. M. M. Weijin, W. M. P. van der Aalst and  A. K. Alves de Medeirons, Process mining with the heuristicsminer algorithm, Research School for Operations Management and Logistics, 2006によって提示された。
【００１０】
また、Christian W. Gunther and Wil M. P. van der Aalst. Fuzzy mining - adaptive process simplification based on multi-perspective metrics. In proceedings of the 5th International Conference on Business Process Management, 2007. 及びWil M. P. van der Aalst and Christian W. Gunther. Finding structure in unstructured processed: The case for process mining. In Proceedings of the 7th International Conference on Application of Concurrency to System Design, 2007は、Fuzzy Miningという技法を開示する。
【００１１】
これらの技法によって提供されるアルゴリズムは、依存性確率、重要度、及び相関などの尺度を用いて、ノードを寄せ集め、リンクを切断することによって、非構造化プロセスに構造を与えようとする。これらのアルゴリズムは、ログに含まれる例外やノイズを効率的に処理することができるが、ある種のタイプの実際のアプリケーションでは、限定された効果しか得られない。
【００１２】
さらに、特許文献としては、次のものが知られている。
特開２００３−１０８５７４号公報は、購買履歴を記録したデータベースから、購買品を特定記号に対応させた記号リストを別のデータベースをを用いて、顧客の購買記録を記号列に変換するシステムを開示する。その変換した記号列は、元の記号と同じか、少ない記号で置換えて、インデックス化を図る。そのインデックス化した記号列に、前記記号列に用いた記号を適宜組合せて生成した複数の正規表現候補のどの候補が含まれるかを評価して、購買履歴の中に含まれる有用な購買ルールやパターンを発見することにより、精度の高い購買ルールモデルの構築をエキスパートの能力に頼らずに行なえるようにする。
【００１３】
特開２００６−２３６２６２号公報は、タグの解析や抽出ルールの作成をしないでも、一般のユーザが有益な情報を持つテキストコンテンツを容易に取り出して活用することができるようにするために、正規表現を持つパターンフォーマットを記憶する記憶部と、前記ＨＴＭＬページから前記パターンフォーマットと一致するテキストコンテンツを取り出す抽出ルールを生成する抽出ルール生成部と、前記抽出ルールから所定のフォーマットに変換するフォーマット変換部を有するシステムを開示する。
【００１４】
しかし、これらの特許文献も、構造化されていないビジネス・プロセスのログから、意味があるルールを抽出する技法については開示するものではない。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特開２００３−１０８５７４号公報
【特許文献２】特開２００６−２３６２６２号公報
【非特許文献】
【００１６】
【非特許文献１】A. J. M. M. Weijin, W. M. P. van der Aalst and  A. K. Alves de Medeirons, Process mining with the heuristicsminer algorithm, Research School for Operations Management and Logistics, 2006
【非特許文献２】Christian W. Gunther and Wil M. P. van der Aalst. Fuzzy mining - adaptive process simplification based on multi-perspective metrics. In proceedings of the 5th International Conference on Business Process Management, 2007.
【非特許文献３】Wil M. P. van der Aalst and Christian W. Gunther. Finding structure in unstructured processed: The case for process mining. In Proceedings of the 7th International Conference on Application of Concurrency to System Design, 2007
【発明の概要】
【発明が解決しようとする課題】
【００１７】
従って、この発明の目的は、業務プロセスの構造化されていないログからも、有意義なワークフローを抽出し、あるいは視覚化可能な業務プロセス解析技法を提供することにある。
【課題を解決するための手段】
【００１８】
この発明は、上記目的を達成するためになされたものであり、コンピュータの処理により、(1) ログを簡単化する処理と、(2) 簡易化されたログに基づき正規文法を改良する処理と、(3) 結果の改良された正規文法に基づき、ワークフローを生成する処理からなる。
ログを簡単化する処理は、所与のログ・トレース、すなわち、ログにおける時間順の処理の並びから、グラフを生成するステップと、生成されたグラフのトポロジカルな特徴を計算することによってノードを特定し、特定したノードを削除することによってグラフを簡易化するステップを繰り返すことによって簡易化を行うステップを有する。
簡易化されたログに基づき正規文法を改良する処理は、ユーザーが予め複数の制約を用意するステップと、正規文法の初期値を与えるステップと、正規文法に対して制約を作用させて改良するステップと、改良された正規文法に対して簡易化されたログを適用することにより、そのログに対する適合性が所定の値以上であることに応答して、改良された正規文法を受け入れるステップを有する。
本発明の一側面によれば、正規文法は変数を含み、正規文法を改良するステップは、正規文法に含まれている変数を置き換えて、変数を含まない正規文法を得るステップを有する。
ワークフローを生成する処理は、結果の正規文法から有限状態遷移系を生成し、次に有限状態遷移系をワークフローに変換するステップを有する。
【発明の効果】
【００１９】
この発明によれば、業務プロセスのログからノイズとみなされるノードを除去して先ず簡易化されたログを用意し、続いてその簡易化されたログに適合するように正規文法を制約に基づき改良するという処理を行うことで、ログを正規文法に当て嵌めるので、構造化されていない業務プロセスのログからでも、適切なワークフローが生成できるという効果が得られる。
【図面の簡単な説明】
【００２０】
【図１】本発明を実施するためのハードウェア構成の一例を示すブロック図である。
【図２】本発明の実施例に係る機能ブロック図である。
【図３】業務ログの例を示す図である。
【図４】本発明の実施例の全体的な処理のフローチャートを示す図である。
【図５】ログ簡易化の例を示す図である。
【図６】Ｎ−Ｎノード・タイプのグラフを示す図である。
【図７】ログ簡易化における、Ｎ−Ｎノード・タイプ検出処理のフローチャートを示す図である。
【図８】サブルーチン・タイプのグラフを示す図である。
【図９】スイッチ・タイプのグラフを示す図である。
【図１０】マージ・タイプのグラフを示す図である。
【図１１】ブランチ・タイプのグラフを示す図である。
【図１２】getMerge処理のフローチャートを示す図である。
【図１３】getBranch処理のフローチャートを示す図である。
【図１４】getDistance処理のフローチャートを示す図である。
【図１５】サブルーチン・タイプ検出処理のフローチャートを示す図である。
【図１６】スイッチ・タイプ検出処理のフローチャートを示す図である。
【図１７】ノード除去の典型的なパターンを示す図である。
【図１８】スコア計算処理のフローチャートを示す図である。
【図１９】業務ログの簡易化処理の推移の例を示す図である。
【図２０】業務ログの簡易化処理の推移における、ノードの数、リンクの数、及びスコアを示す図である。
【図２１】ログ改良処理の概要のフローチャートを示す図である。
【図２２】改良サブモジュールの処理のフローチャートを示す図である。
【図２３】検査サブモジュールの処理のフローチャートを示す図である。
【図２４】変換サブモジュールの処理のフローチャートを示す図である。
【図２５】置き換えサブモジュールの処理のフローチャートを示す図である。
【図２６】ε-NFAからDFAに変換する処理のフローチャートを示す図である。
【図２７】DFAから擬似ワークフローを生成する処理のフローチャートを示す図である。
【図２８】ワークフローから擬似ワークフローを生成する処理のフローチャートを示す図である。
【図２９】正規表現に基づき生成される状態遷移系の例を示す図である。
【図３０】状態遷移系に基づき生成されたワークフローの例を示す図である。
【発明を実施するための形態】
【００２１】
以下、図面に基づき、この発明の実施例を説明する。特に断わらない限り、同一の参照番号は、図面を通して、同一の対象を指すものとする。尚、以下で説明するのは、本発明の一実施形態であり、この発明を、この実施例で説明する内容に限定する意図はないことを理解されたい。
【００２２】
図１を参照すると、本発明の一実施例に係るシステム構成及び処理を実現するためのコンピュータ・ハードウェアのブロック図が示されている。図１において、システム・パス１０２には、ＣＰＵ１０４と、主記憶（ＲＡＭ）１０６と、ハードディスク・ドライブ（ＨＤＤ）１０８と、キーボード１１０と、マウス１１２と、ディスプレイ１１４が接続されている。ＣＰＵ１０４は、好適には、３２ビットまたは６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のＰｅｎｔｉｕｍ（商標）  ４、Ｃｏｒｅ（商標）２  Ｄｕｏ、Ｘｅｏｎ（商標）、ＡＭＤ社のＡｔｈｌｏｎ（商標）などを使用することができる。主記憶１０６は、好適には、２ＧＢ以上の容量をもつものである。ハードディスク・ドライブ１０８は、好適には例えば、３２０ＧＢ以上の容量をもつものである。
【００２３】
ハードディスク・ドライブ１０８には、個々に図示しないが、オペレーティング・システムが、予め格納されている。オペレーティング・システムは、Ｌｉｎｕｘ（商標）、マイクロソフト社のＷｉｎｄｏｗｓ（商標）７、Ｗｉｎｄｏｗｓ  ＸＰ（商標）、Ｗｉｎｄｏｗｓ（商標）２０００、アップルコンピュータのＭａｃ  ＯＳ（商標）などの、ＣＰＵ１０４に適合する任意のものでよい。
【００２４】
ハードディスク・ドライブ１０８にはさらに、後述する業務ログのファイル、ログを簡易化する目的のログ処理モジュール群、簡易化されたログに基づき、適切な正規文法を得るためのログ・パターン改良モジュール群、得られた正規文法を有限遷移系に変換するモジュール、及び、有限遷移系からワークフローを生成するモジュールなどが格納されている。これらのモジュールは、Ｃ、Ｃ＋＋、Ｃ＃、Ｊａｖａ(R)などの既存のプログラミング言語処理系で作成することができ、オペレーティング・システムの働きで、これらのモジュールは適宜主記憶１０６にロードされて実行される。これらのモジュールの動作の詳細は、図２の機能ブロック図を参照して、より詳細に説明する。
【００２５】
キーボード１１０及びマウス１１２は、上述の業務ログのファイル、ログを簡易化する目的のログ処理モジュール群、簡易化されたログに基づき、適切な正規文法を得るためのログ・パターン改良モジュール群、得られた正規文法を有限遷移系に変換するモジュール、及び、有限遷移系からワークフローを生成するモジュールなどを起動したり、文字を打ち込んだりするために使用される。
【００２６】
ディスプレイ１１４は、好適には、液晶ディスプレイであり、例えば、ＸＧＡ（１０２４×７６８の解像度）、またはＵＸＧＡ（１６００×１２００の解像度）などの任意の解像度のものを使用することができる。ディスプレイ１１４は、業務ログから生成されたグラフを表示するためなどに使用される。
【００２７】
図１のシステムは更に、バス１０２に接続された通信インターフェース１１６を介して、ＬＡＮ、ＷＡＮなどの外部ネットワークに接続されている。通信インターフェース１１６は、イーサネット（商標）などの仕組みにより、外部ネットワーク上にあるサーバなどのシステムとデータのやりとりを図る。
【００２８】
サーバ（図示しない）には、業務オペレータが操作するクライアント・システム（図示しない）が接続され、業務オペレータが操作した結果によりサーバに保存された業務ログのファイルが、ネットワークを介して、解析のために、図１のシステムに集められる。
【００２９】
次に、図２を参照して、本発明に関連して、ハードディスク・ドライブ１０８に保存されたファイル及び機能モジュールの働きを説明する。
【００３０】
図２において、業務ログ２０２は、業務オペレータが操作した結果を記録したファイルであり、図３に示すように、複数のログ・ファイル３０２及び３０４からなる。実際はより多くのログ・ファイルを含むが、ここでは例示的に、２個のログ・ファイルだけが示されている。
【００３１】
図３に示すように、各ログ・ファイルは、一意的なケースＩＤを付与されている。各ログ・ファイルは少なくとも、時間と処理のフィールドをもち、さらに好適には、担当者のフィールドをもつ。時間のフィールドには、好適には、処理を記録したシステム時間が入力されるが、本発明の目的のためには、最低でも、処理の前後関係が分かればよい。処理のフィールドには、「起票開始」「起票完了」「機械査定」「点検開始」などの、予め定義された処理の処理ＩＤが格納される。
【００３２】
図２に戻って、ログ処理モジュール２０４は、業務ログ２０２の冗長なエントリを見出して、簡易化するための機能をもつものであり、グラフ作成２０６、ノイズ検出２０８、ログ削除２１０、スコア計算２１２、及び表示２１４のサブモジュールを有する。グラフ作成サブモジュール２０６は、業務ログ２０２を読み取って、処理内容をノードとし、処理内容間の時間の前後関係を有向きリンクとするグラフを作成する。この技法は、例えば、Wil M. P. van der Aalst, B. F. van Dongen, "Discovering Workflow Performance Models from Timed Logs", Proceedings of the International Conference on Engineering and Deployment of Cooperative Information Systems, 2002のp9, Definition 3.6に記述されているアルゴリズムを利用する。
【００３３】
ノイズ検出サブモジュール２０８は、グラフ作成サブモジュール２０６によって作成されたグラフにおける、例外的な処理のノードを、ノイズとして認識する。
【００３４】
図５は、ログ簡易化処理を模式的に示す図である。図５において、ログ５０２とログ５０４から、グラフ作成サブモジュール２０６によって、グラフ５０６が形成されたとする。このとき、ログ５０２のようなログが１０個あり、一方、ログ５０４のようなログが１個あったとする。すると、ノイズ検出サブモジュール２０８は、処理４のノードを削除対象と認識する。これに対応して、ログ５０４の処理４のエントリが、削除対象と認識される。ノイズ検出サブモジュール２０８のより詳細な処理は、図７のフローチャートなどに関連して、あとで詳細に説明する。
【００３５】
ログ削除サブモジュール２１０は、ノイズ検出サブモジュール２０８によってノイズとして認識されたノードに対応するログのエントリを削除する。図５の例で示すと、ログ削除サブモジュール２１０は、ノイズ検出サブモジュール２０８で削除対象にされた、ログ５０４の処理４のエントリを削除する。その結果グラフ作成サブモジュール２０６によって再度作成されると、グラフ５０８になる。
【００３６】
スコア計算サブモジュール２１２は、ノイズを削除した後の業務ログから再度グラフ作成サブモジュール２０６によって作成されたグラフに対して、さまざまなバリエーションを与えて、その各々にスコアを計算する機能を有する。スコア計算サブモジュール２１２のより詳細な処理は、あとで説明する。
【００３７】
表示サブモジュール２１４は、グラフ作成サブモジュール２０６で作成されたグラフ、またはスコア計算サブモジュール２１２によってバリエーションを与えられたグラフを、ディスプレイ１１４に表示する機能を有する。
【００３８】
ログ処理モジュール２０４は、処理の結果である簡易化されたログを、ログ・パターン改良モジュール２１６に渡す。
【００３９】
ログ・パターン改良モジュール２１６は、改良２１８、検査２２０、置き換え２２２、変換２２４のサブモジュールをもち、ユーザによって定義され、ハードディスク・ドライブ１０８または主記憶１０６に保存された制約条件２２６のデータを用いて、受け取った簡易化されたログから正規文法を出力する機能を有する。ログ・パターン改良モジュール２１６のより詳細な処理は、あとで説明する。
【００４０】
有限状態遷移系生成モジュール２２８は、ログ・パターン改良モジュール２１６から出力された正規文法を入力して、有限状態遷移系に変換する機能をもつ。
【００４１】
ワークフロー変換モジュール２３０は、有限状態遷移系生成モジュール２２８から入力した有限状態遷移系のデータから、ワークフローを生成する機能をもつ。
【００４２】
次に、図４のフローチャートを参照して、本発明の処理の全体的な概要を説明する。図４において、ログ４０２は、図２で業務ログ２０２と示されているものと同じものである。
【００４３】
ステップ４０４では、グラフ作成サブモジュール２０６が、ログ４０２を読み取って、グラフを生成する。
【００４４】
ステップ４０６では、ノイズ検出サブモジュール２０８が、グラフ作成サブモジュール２０６によって生成されたログに基づき、ノイズ検出を行う。
【００４５】
ステップ４０８では、ログ削除サブモジュール２１０が、ノイズ検出サブモジュール２０８によってノイズと認識されたログのエントリを削除する。
【００４６】
ステップ４１０では、グラフ作成サブモジュール２０６が、エントリを削除された後のログ４０２を読み取って、グラフを生成する。
【００４７】
ステップ４１２では、スコア計算サブモジュール２１２がスコア計算して、グラフのさまざまなバリエーションのスコアを表示する。ステップ４１４では、ログ処理モジュール２０４が、スコア計算サブモジュール２１２によって計算されたバリエーションとそのスコアをディスプレイ１１４に表示して、ユーザーに選択させる。
【００４８】
ステップ４１６でのユーザー判断で、ユーザーがどれかのバリエーションを受け入れて選択すれば、その結果に対応する簡易化されたログ４１８が、次のログ改良ステップに送られることになる。
【００４９】
ステップ４１６でのユーザー判断で、更なる簡易化が必要であるとの判断がなされると、処理はステップ４０６のノイズ検出に戻る。
【００５０】
ステップ４１６でのユーザー判断で、ユーザーが手動操作での削除すべきログの選択を要望するなら、ステップ４２０で、ログ処理モジュール２０４は、ディスプレイ１１４にグラフを表示し、ユーザーに、マウス１１２などの操作によって、削除すべきグラフのノードを選択させる。その後は、ステップ４０８で、選択されたグラフのノードに対応するログのエントリが削除されて、ステップ４１０以下処理が続く。
【００５１】
こうして結局、簡易化されたログ４１８が確定すると、ステップ４２２で、ログ・パターン改良モジュール２１６が、ユーザーによって定義され、あるいは予めシステムとして予定された初期ログ・パターンを提供する。
【００５２】
ステップ４２４では、ログ・パターン改良モジュール２１６が、ユーザーが定義した制約条件２２６であるφを読み込む。
【００５３】
ステップ４２６では、ログ・パターン改良モジュール２１６が、まだ処理していない制約条件φがあるかどうかを判断し、もしあるなら、改良サブモジュール２１８をステップ４２８で呼び出して、ログ・パターンを改良する。ログ・パターン改良モジュール２１６は次に、検査サブモジュール２２０をステップ４３０で呼び出し、簡易化されたログ４１８から得られた、処理の並びであるトレースに対して、妥当性を判断し、妥当てあると判断したなら、結果のログ・パターンを受け入れる。そうでなければ、結果のログ・パターンを棄却する。
【００５４】
ステップ４２６に戻って、処理していない制約条件φはもうないと判断されたなら、結果のログ・パターンを出力される正規文法として、ステップ４３２に進み、そこで、有限状態遷移系生成モジュール２２６が、正規文法を有限状態遷移系に変換する。次に、ステップ４３４では、ワークフロー変換モジュール２３０が、得られた有限状態遷移系を、ワークフローに変換する。
【００５５】
次に、図６乃至図１７を参照して、図２のノイズ検出サブモジュール２０８の機能を、より詳しく説明する。ノイズ検出サブモジュール２０８は、生成されたグラフの様々な特徴を検出して、所定のノードまたは処理を検出し、その後、ログ削除サブモジュール２１０が、検出されたノードを削除する。
【００５６】
図６に示すパターンは、この実施例でＮ−Ｎノード・タイプと呼ぶもので、単一のノードと、それ以外の複数のノードの間にリンクが張られている場合である。図６(a)の例では、ノード６０２が、除去すべきノードとして検出され、その結果、図６(b)のように、ノード６０２が除去された平坦なグラフになる。
【００５７】
このようなＮ−Ｎノード・タイプのグラフを検出するための処理を、図７のフローチャートを参照して説明する。ノイズ検出サブモジュール２０８は、ステップ７０２で、グラフとリンク情報を入力する。具体的には、Vを、ノードの特徴量をストアする変数viの集合とする。またNを、ノードの入出力リンク数をストアする変数niの集合とする。集合V及びNは、構造体の配列などの形式で実装することができる。
【００５８】
ステップ７０４から、ステップ７１２までは、Nの要素niにつき、i = 1 to max_nodeまでの順次処理をあらわす。ここで、max_nodeは、処理するノードの数である。
【００５９】
ステップ７０６では、inNum = get_in(ni)の関数呼び出しにより、ノードniの入力リンクの数が、inNumに代入される。
【００６０】
ステップ７０８では、outNum = get_out(ni)の関数呼び出しにより、ノードniの出力リンクの数が、outNumに代入される。
【００６１】
ステップ７１０では、vi = min(inNum, outNum)により、inNumとoutNumのうちの小さい方の値が、viに代入される。
【００６２】
ステップ７１２でループを抜けたときは、viの値が、i = 1 〜 max_numまで揃っている。そこで、ステップ７１４で、ノイズ検出サブモジュール２０８は、Vを降順ソートする。そして、ステップ７１６でノイズ検出サブモジュール２０８がVを出力すると、Vのトップには、入力リンクの数と出力リンクの数のうちの小さい方の値が最大であるノードがくる。
【００６３】
このようなVのトップにあるノードが削除すべきノードであると認識されて、実際に、業務ログ２０２から、ログ削除サブモジュール２１０によって、対応するエントリが削除される。
【００６４】
ノイズ検出サブモジュール２０８が削除すべきと認識するさらに別のタイプのグラフとして、図８に示すサブルーチン・タイプと、図９に示すスイッチ・タイプがある。
【００６５】
これらを検出する処理はそれぞれ、図１５及び図１６のフローチャートを参照して後で説明するが、その前に、図１５及び図１６のフローチャートで呼び出される関数またはサブルーチンである、getMerge()、getBranch()及びgetDistance()について説明する。
【００６６】
getMerge()は、図１０に示すように、ノードに入るリンクよりも、ノードから出るリンクの方が少ない場合のパターンを検出する。
【００６７】
また、getBranch()は、図１１に示すように、ノードに入るリンクよりも、ノードから出るリンクの方が多い場合のパターンを検出する。
【００６８】
図１２は、getMerge()の処理を示すフローチャートである。ノイズ検出サブモジュール２０８は、ステップ１２０２で、グラフとリンク情報を入力する。具体的には、Mを、ノードの特徴量をストアする変数miの集合とする。またNを、ノードの入出力リンク数をストアする変数niの集合とする。集合M及びNは、構造体の配列などの形式で実装することができる。
【００６９】
ステップ１２０４から、ステップ１２１２までは、Nの要素niにつき、i = 1 to max_nodeまでの順次処理をあらわす。ここで、max_nodeは、処理するノードの数である。
【００７０】
ステップ１２０６では、inNum = get_in(ni)の関数呼び出しにより、ノードniの入力リンクの数が、inNumに代入される。
【００７１】
ステップ１２０８では、outNum = get_out(ni)の関数呼び出しにより、ノードniの出力リンクの数が、outNumに代入される。
【００７２】
ステップ１２１０では、mi = inNum / outNumにより、inNumをoutNumで割った値が、miに代入される。
【００７３】
ステップ１２１２でループを抜けたときは、miの値が、i = 1 〜 max_numまで揃っている。そこで、ステップ１２１４で、ノイズ検出サブモジュール２０８は、Mを降順ソートする。そして、ステップ１２１６でノイズ検出サブモジュール２０８がMを出力すると、Mのトップには、入力リンクの数を出力リンクの数で割った値が最大であるノードがくる。
【００７４】
図１３は、getBranch()の処理を示すフローチャートである。ノイズ検出サブモジュール２０８は、ステップ１３０２で、グラフとリンク情報を入力する。具体的には、Bを、ノードの特徴量をストアする変数biの集合とする。またNを、ノードの入出力リンク数をストアする変数niの集合とする。集合M及びNは、構造体の配列などの形式で実装することができる。
【００７５】
ステップ１３０４から、ステップ１３１２までは、Nの要素niにつき、i = 1 to max_nodeまでの順次処理をあらわす。ここで、max_nodeは、処理するノードの数である。
【００７６】
ステップ１３０６では、inNum = get_in(ni)の関数呼び出しにより、ノードniの入力リンクの数が、inNumに代入される。
【００７７】
ステップ１３０８では、outNum = get_out(ni)の関数呼び出しにより、ノードniの出力リンクの数が、outNumに代入される。
【００７８】
ステップ１３１０では、bi = outNum / inNumにより、outNumをinNumで割った値が、biに代入される。
【００７９】
ステップ１３１２でループを抜けたときは、biの値が、i = 1 〜 max_numまで揃っている。そこで、ステップ１３１４で、ノイズ検出サブモジュール２０８は、Bを降順ソートする。そして、ステップ１３１６でノイズ検出サブモジュール２０８がBを出力すると、Bのトップには、出力リンクの数を入力リンクの数で割った値が最大であるノードがくる。
【００８０】
次に、図１４を参照して、getDistance(node1, node2)の処理について説明する。ステップ１４０２で、Caseを、全てのケース1 〜 caseMaxまでストアする集合とする。ステップ１４０４では、Logを、全てのログ・トレース・データLi (i = 1 〜 logMax)をストアする集合とする。
【００８１】
ステップ１４０６では、d_all = 0, d_new = 0, target = 0と変数がセットされる。
【００８２】
ステップ１４０８からステップ１４３０までは、Caseのケースi = 1から、CaseMaxまでiについて順に処理が行われる。
【００８３】
ステップ１４１０では、d_new = 0, flag = falseのセットが行われる。
【００８４】
次にステップ１４１２からステップ１４２６までは、Logのログ・トレース・データLjを、j = 1からlogMaxまで、jについて順に処理が行われる。
【００８５】
ステップ１４１４では、getNode(Lj) = node1かどうか、すなわち、getDistance()の第１引数に与えられたノードが、Ljに含まれているかどうかが判断される。
【００８６】
もしそうなら、ステップ１４１６で、flag = trueとセットされる。
【００８７】
ステップ１４１８では、flag = trueかどうかが判断され、もしそうなら、ステップ１４２０で、d_new = d_new + 1と、d_newが増分される。
【００８８】
ステップ１４２２では、getNode(Lj) = node2かどうか、すなわち、getDistance()の第２引数に与えられたノードが、Ljに含まれているかどうかが判断される。もしそうなら、ステップ１４２４で、target = target + 1と、targetが増分され、また、flag = falseとされる。
【００８９】
ステップ１４２６でのjのループから出ると、ステップ１４２８では、d_all = d_all + d_newと、d_allにd_newが足される。
【００９０】
ステップ１４３０でのiのループから出ると、ステップ１４３０では、d = d_all / targetとdが計算され、ステップ１４３４で、getDistance(node1, node2)は、計算された値dを返す。
【００９１】
次に、図１５のフローチャートを参照して、getMerge()、getBranch()、及びgetDistance()を使って、グラフにおけるサブルーチン・タイプを検出する処理について説明する。
【００９２】
ステップ１５０２では、予め、変数に値を読む込む処理が行われる。すなわち、Lは、全てのログ・トレース・データをストアする集合、Mは、マージ・タイプ検出アルゴリズムからの出力、Bは、ブランチ・タイプ検出アルゴリズムからの出力、Dijは、ノードniとノードnjの間の距離、Tは、ターゲット・サブルーチン・ノードをフィルタするための閾値としての回数である。
【００９３】
ステップ１５０４では、M = getMerge()、B = getBranch()により、それぞれ、図１２と図１３のフローチャートの処理を呼び出して、M, Bの値を取得する。
【００９４】
ステップ１５０６からステップ１５１８までは、Mの要素について、i = 1からTまでの処理が行われる。
【００９５】
ステップ１５０８からステップ１５１６までは、Bの要素について、j = 1からTまでの処理が行われる。
【００９６】
ステップ１５１０では、ni = getNode(M,i)により、Mのi番目のノードを、niとして取り出す。
【００９７】
ステップ１５１２では、nj = getNode(B,j)により、Bのj番目のノードを、njとして取り出す。
【００９８】
ステップ１５１４では、Dij = getDistance(ni,nj)により、ノードniからnノードjへの距離が計算されて、Dijに代入される。
【００９９】
ステップ１５１６でjのループを抜け、ステップ１５１８でiのループを抜けると、Dijを要素として含むDが、ステップ１５２０で降順ソートされる。
【０１００】
ステップ１５２２では、Dが出力される。
【０１０１】
次に、図１６のフローチャートを参照して、getMerge()、getBranch()、及びgetDistance()を使って、グラフにおけるスイッチ・タイプを検出する処理について説明する。
【０１０２】
ステップ１６０２では、予め、変数に値を読む込む処理が行われる。すなわち、Lは、全てのログ・トレース・データをストアする集合、Mは、マージ・タイプ検出アルゴリズムからの出力、Bは、ブランチ・タイプ検出アルゴリズムからの出力、Dijは、ノードniとノードnjの間の距離、Tは、ターゲット・スイッチ・ノードをフィルタするための閾値としての回数である。
【０１０３】
ステップ１６０４では、M = getMerge()、B = getBranch()により、それぞれ、図１２と図１３のフローチャートの処理を呼び出して、M, Bの値を取得する。
【０１０４】
ステップ１６０６からステップ１６１８までは、Bの要素について、i = 1からTまでの処理が行われる。
【０１０５】
ステップ１６０８からステップ１６１６までは、Mの要素について、j = 1からTまでの処理が行われる。
【０１０６】
ステップ１６１０では、ni = getNode(M,i)により、Mのi番目のノードを、niとして取り出す。
【０１０７】
ステップ１６１２では、nj = getNode(B,j)により、Bのj番目のノードを、njとして取り出す。
【０１０８】
ステップ１６１４では、Dij = getDistance(ni,nj)により、ノードniからnノードjへの距離が計算されて、Dijに代入される。
【０１０９】
ステップ１６１６でjのループを抜け、ステップ１６１８でiのループを抜けると、Dijを要素として含むDが、ステップ１６２０で降順ソートされる。
【０１１０】
ステップ１６２２では、Dが出力される。
【０１１１】
図１７は、グラフにおけるノード検出と除去の典型的なパターンを示す図である。図１７(a)は、図６にも示したＮ−Ｎタイプのノード除去と同じものである。この場合、図７に示すフローチャートの処理によって、除去すべきノードが検出される。
【０１１２】
図１７(b)は、作業者割当て処理(worker allocation activiry)ノードを除去するタイプの処理である。この場合は、図７に示すフローチャートの処理が２回適用される。
【０１１３】
図１７(c)は、サブルーチン・タイプのノード検出の例を示す。図１５のフローチャートの処理によって、除去すべきノードが検出される。
【０１１４】
図１８は、図２で示されている、スコア計算サブモジュール２１２が実行する処理のフローチャートである。これは、図４のフローチャートにおけるステップ４１２にも対応する。
【０１１５】
図１８のフローチャートの処理は、処理の試行が繰り返され、与えられたグラフから、ノイズ検出サブモジュール２０８とログ削除サブモジュール２１０を呼び出して、次第にノードを減らされるにつれて、その都度スコアを計算するアルゴリズムを実行するものである。ここで言う試行は、図４における、ステップ４０６、４０８、４１０、４１２及び４１４からなるループである。ステップ４１６でユーザが更なる簡易化を選ぶことで、次の試行に進む。また、手動ログ選択４２０を選んだ場合も、ステップ４０８から、試行のループに戻る。
【０１１６】
尚、好適には、１回の処理ループで、グラフのノードが１つだけ削除されるように、上述の複数のノイズ検出アルゴリズムのどれかが適用されるようにする。このとき、どのノイズ検出アルゴリズムのうちのどれを適用するか、オペレータに対話的に選ばせてもよいし、ランダムに１つのノイズ検出アルゴリズムを適用してもよい。あるいは、ノイズ検出アルゴリズムを適用した結果の有効性に従い、より有効なノイズ検出アルゴリズムを適用してもよい。例えば、図７のN-Nノード・タイプの検出の場合、結果のソートされた集合Vのトップの要素の特徴量がある閾値を超えている場合にのみ、ログ削除サブモジュール２１０を適用するようにしてもよい。
【０１１７】
また特に、図１５に示すサブルーチン・タイプのノイズ検出の場合は、図１７(c)のように認識されたサブルーチン・ノードの集まりを削除してよいかどうかは、場合による。従って、サブルーチン・タイプのノイズ検出の場合は、システムの自動削除処理に任せず、オペレータの対話的判断を待って、サブルーチン・ノードの集まりを削除するかどうかを決定することが望ましい。
【０１１８】
ステップ１８０２では、Piを、i番目の試行の結果のパターンをあらわす変数とする。また、Sを、全ての計算のスコアの集合とする。
【０１１９】
ステップ１８０４から、ステップ１８１６までは、Sについて、i = 1からmax_iterationまでの繰り返しである。
【０１２０】
ステップ１８０６では、i1 = getLinkNum(Pi)の計算が行われる。getLinkNum(Pi)は、Piのリンクの数を返す関数である。
【０１２１】
ステップ１８０８では、i0 = getLinkNum(Pi-1)の計算が行われる。
【０１２２】
ステップ１８１０では、s_1i = (i0 - i1) / i1が計算される。
【０１２３】
ステップ１８１２では、c = getCaseCoverage(Pi)が計算される。ここで、getCaseCoverage(Pi)とは、Piに残っているノードでカバーできるCaseの件数を返す関数である。
【０１２４】
ステップ１８１４では、s_2i = c / max_iterationが計算され、ステップ１８１６では、si = normalize(s_1i) * normalize(s_2i)が計算される。ここで、normalize(s_1i)とは、s_1jにつき、j = 1から、max_iteratioonまで合計し、その合計値でs_1iを割った値である。normalize(s_2i)も同様に計算される。
【０１２５】
ステップ１８１８でiのループを抜けると、ステップ１８２０で、Sが降順ソートされる。ステップ１８２０では、Sが出力される。
【０１２６】
図１９は、図１８のフローチャートで、試行を行う度にグラフが簡易化されていく様子を示す例である。その都度、スコアも異なってくる。
【０１２７】
図２０は、試行の度に、ノードの数、リンクの数、及びスコアが変化して行く様子を数値で示す。スコア値が高いというのは、グラフ簡易化の程度が望ましいことを示唆する。従って、スコア値は、ユーザが次のログ・バターン改良ステップに移行する判断を行うための目安を与える。
【０１２８】
次に、図２１以下を参照して、ログ・バターン改良ステップを説明するが、その前提として、イベント集合、正規文法、及び制約について説明する。
【０１２９】
先ず、イベントとは、図３の作業ログを例にとると、処理の内容のことである。そこで、イベントの集合Σは、例えば、次のようなものである。
Σ = {{起票開始},{起票完了},{点検開始},{点検完了},{機械査定}}
【０１３０】
次に、正規文法rとは、次のようなものである。
r ::= e|x|r・r|r*|r∩r|r∪r|rc
【０１３１】
ここで、eは、Σの要素、xは変数、r・rは正規文法の連接、r*は、正規文法の０回以上の繰り返し、r∩rは連言すなわち両方の正規文法が受け入れられるべきとする条件、r∪rは選言すなわちどちらかのの正規文法が受け入れらればよいとする条件、rcは、否定すなわち、rを受け入れられないという条件である。
【０１３２】
例えば、{起票開始}.*{機械査定}という正規文法は、{起票開始}の後、いつか必ず{機械査定}が起こるというトレースを示す。
【０１３３】
次に、制約φについて説明する。制約φとは、正規文法が満たすべき条件を定めるものであり、その定義は次のとおりである。
φ0 ::= x = r|φ0∧φ0
φ ::= φ0|φ0 ⇒φ
【０１３４】
例えば、次のような制約が記述される。
x = y・{機械査定}.* ⇒ y = .*{起票完了}.*
この制約は、{機械査定}があるなら、その前に必ず{起票完了}がなくてはならない、という条件を示す。
【０１３５】
それ以外の制約として、次のようなものがある。
x = y・{機械査定} ⇒ y =[^{点検完了}]+
この制約は、{機械査定}で査定が終わるなら、{点検完了}は含まれない、という条件を示す。
【０１３６】
更に別の制約の例として、次のようなものがある。
x = y・z ⇒ (y = .*{コード照会}.* ⇒ z = .*{コード照会}.*)
これは、上記の制約も併せて考慮するとすると、起票とその後の点検で査定が終わるものについては、もし起票の中でコード照会が行われていれば、点検の中でもコード照会が行われる、
【０１３７】
このような制約は、予めユーザにより記述されて、図２の制約２２６に示されるように、ログ・パターン改良モジュール２１６から呼び出し可能であるように、主記憶１０６またはハードディスク・ドライブ１０８に保存されている。
【０１３８】
過去の同種の業務ログを眺めたり、解析するしてルールを見出すことにより、作成される。
【０１３９】
次に、図２１のフローチャートを参照して、ログ・パターン改良モジュール２１６の処理を説明する。図２１のフローチャートの処理の入力は、上述した制約と、ログ処理モジュール２０４の処理の結果としての簡易化されたログ４１８である。
【０１４０】
簡易化されたログ４１８は、複数のログ・トレースからなる。ここでログ・トレースとは、処理の開始から終了までの一連の流れからなるものである。そのようなログ・トレースの集合Tが、下記のような６個の要素をからなるとする。
T = {τ1,τ2,τ3,τ4,τ5,τ6}
【０１４１】
さらにその要素の内容は、次のとおりであるとする。
τ1 = {起票開始}{起票完了}{点検開始}{機械査定}{決了登記}
τ2 = {起票開始}{点検開始}{機械査定}{点検完了}
τ3 = {コード照会}{起票完了}{機械査定}
τ4 = {点検開始}{点検完了}{機械査定}
τ5 = {コード照会}{起票完了}{コード照会}{機械査定}
τ6 = {点検開始}{コード照会}{機械査定}
【０１４２】
さて、図２のステップ２１０２では、ログ・パターン改良モジュール２１６は、正規文法rの初期値を設定する。これは、予め、r = .* と、所与の正規文法として与えてもよいし、ユーザが適宜に与えてもよい。ここでは、r = .*であるとする。
【０１４３】
ステップ２１０４では、ログ・パターン改良モジュール２１６が、予めユーザにより用意された制約２２６のうち、１つの制約φを読み込む。
【０１４４】
ステップ２１０６では、制約φを読み込むことができたかどうかが判断し、もしそうなら、ログ・パターン改良モジュール２１６は、改良サブモジュール２１８を呼び出して、ステップ２１０８で、正規文法rを、制約φに基づき改良する。
【０１４５】
具体的には、refine()という関数を呼び出し、r' = refine(r,{φ})を実行する。改良サブモジュール２１８であるrefine()という関数の処理は、後で図２２のフローチャートを参照して説明する。
【０１４６】
ステップ２１０８の処理の結果、r'が得られるので、ステップ２１１０では、ログ・パターン改良モジュール２１６は、検査サブモジュール２２０を呼び出して、正規文法r'を、トレース集合Tに基づき検査する。具体的には、r'とTを引数として、examine(r',T)という関数を呼び出す。検査サブモジュール２２０であるexamine()という関数の処理は、後で図２３のフローチャートを参照して説明する。
【０１４７】
ステップ２１１０で、examine(r',T)がtrueを返すと、rがr'に置き換えられる。一方、ステップ２１１０で、examine(r',T)がfalseを返すと、rの置き換えは行われない。
【０１４８】
そうしてステップ２１０４に戻り、ステップ２１０６判断で、全ての制約φが尽きたと判断されると、ログ・パターン改良モジュール２１６は、ステップ２１１４でrを返す。この正規文法rは、有限状態遷移系生成モジュール２２８に渡される。
【０１４９】
次に、図２２のフローチャートを参照して、改良サブモジュール２１８が実行するrefine(r,Φ)の処理について説明する。refine(r,Φ)は、制約の集合Φを使って、正規文法rを改良(refine)する。図２２のステップ２２０２から、ステップ２２１０までは、φ∈Φであるφについて、順次繰り返される。但し、図２１のステップ２１０８で呼び出される場合は、Φ={φ}であるので、ステップ２２０２から、ステップ２２１０までは１回しか呼び出されない。
【０１５０】
ステップ２２０４では、改良サブモジュール２１８が、φの最初に表れる等式x = r0を対(x,r0)として取り出す。
【０１５１】
ステップ２２０６では、改良サブモジュール２１８は、transform(φ,x,r0,空集合)を呼び出して、その戻り値をrφに代入する。transform()は、変換サブモジュール２２４によって実行される。その処理の詳細は、図２４のフローチャートを参照して、後で説明する。
【０１５２】
ステップ２２０８では、改良サブモジュール２１８は、r = r∩rφにより、正規文法rを狭める。
【０１５３】
所定の繰り返しの後ステップ２２１０を抜けると、改良サブモジュール２１８は、ステップ２２１２でrを返す。
【０１５４】
次に、図２３のフローチャートを参照して、検査サブモジュール２２０が実行するexamine(r,T)の処理について説明する。examine(r,T)は、refineしてできた文法を評価する。refineが、Tに鑑み適切であると判断するとtrueを返し、そうでなければ、falseを返す。検査サブモジュール２２０は、ステップ２３０２では、変数naccとnrejの両方をゼロにセットする。
【０１５５】
ステップ２３０４からステップ２３１２までは、τ∈Tの各要素について繰り返される。
【０１５６】
ステップ２３０６では、match(r,τ)、すなわち、ログ・トレースの要素τをrが受理するかどうかが判断される。
【０１５７】
ステップ２３０６で、τをrが受理すると判断されると、naccが1だけ増分され、そうでなければ、nrejが1だけ増分される。
【０１５８】
こうして、ステップ２３１４では、nacc/(nacc+nrej) > thresholdという論理値が返される。すなわち、nacc/(nacc+nrej) > thresholdなら、examine(r,T)は、受理されるトレースの割合が、予め定めた閾値より大きいとしてtrueを返し、そうでなければ、falseを返す。
【０１５９】
次に、図２４のフローチャートを参照して、変換サブモジュール２２４が実行するtransform(φ,x,r0,Γ)の処理について説明する。transform()は、制約φを、等価な正規文法rφに変換する機能を有する。引数のうち、xは、これから改良(refine)に使用される文法をあらわし、r0はその初期値である。Γは、変数と正規文法の対応表である。
【０１６０】
ステップ２４０２で、変換サブモジュール２２４が、φ=(y=r)かどうか判断し、もしそうなら、ステップ２４０２で、Γ=Γ∪{(y,r)}で、Γに対応表が追加される。そうして、ステップ２４０６で、変換サブモジュール２２４は、substr(r0,空集合)c∪substr(x,Γ))を返す。なお、substr()の処理については、図２５のフローチャートを参照して、後で説明する。
【０１６１】
一方、ステップ２４０２で、変換サブモジュール２２４が、φ=(y=r)でないと判断すると、ステップ２４０８に進み、そこで、φ=(y=r⇒ψ)かどうかが判断される。もしそうなら、ステップ２４１０で、Γ=Γ∪{(y,r)}で、Γに対応表が追加される。そうして、ステップ２４１２で、変換サブモジュール２２４は、transform(φ,x,r0,Γ)を再帰呼び出しして、その結果を返す。
【０１６２】
ステップ２４０８で、φ=(y=r⇒ψ)でないと判断すると、変換サブモジュール２２４は、ステップ２４１４で、rを返す。
【０１６３】
次に、図２５のフローチャートを参照して、置き換えサブモジュール２２２が実行するsubstr(r,Γ)の関数の処理について説明する。
【０１６４】
ステップ２５０２では、置き換えサブモジュール２２２は、rにxが含まれるかどうか判断する。もしそうなら、置き換えサブモジュール２２２は、ステップ２５０４で、(x,s)∈Γ、すなわち、(x,s)という対がΓに含まれているかどうか判断する。もしそうなら、ステップ２５０６で、rの中のxをsで置換したものがr'に代入され、そうでなければ、ステップ２５０８で、rの中のxを.*で置換したものがr'に代入され、どちらにしても、ステップ２５１０で、substr(r',Γ)が再帰呼び出しされて、その戻り値が返される。
【０１６５】
ステップ２５０２で、置き換えサブモジュール２２２が、rにxが含まれていないと判断した場合は、置き換えサブモジュール２２２は、ステップ２５１２で、単にrを返す。
【０１６６】
上記関数による処理をよりよく理解するために、前述の制約を再掲する。
そこで、r = .*という文法の初期値に、この制約をφとして、refine(r,{φ})を実行すると、それぞれ、次のようになる。
(1)  x = y・{機械査定}.* ⇒ y = .*{起票完了}.*
これは、
rφ = (.*{機械査定}.*}c∪(.*{起票完了}.*{機械査定}.*)
となる。
(2)  x = y・{機械査定} ⇒ y =[^{点検完了}]+
これは、
rφ = (.*{機械査定}.*}c∪(.*[^起票完了}]+{機械査定})
となる。
(3)  x = y・z ⇒ (y = .*{コード照会}.* ⇒ z = .*{コード照会}.*)
これは、
rφ = (.*{コード照会}.*}c∪(.*{コード照会}.*{コード照会}.*)
となる。
このとき、どのrφにおいても、変数x,yは消去されていることに留意されたい。
【０１６７】
そこで、前述のTを再掲すると、次のとおりである。
T = {τ1,τ2,τ3,τ4,τ5,τ6}で、但し、
τ1 = {起票開始}{起票完了}{点検開始}{機械査定}{決了登記}
τ2 = {起票開始}{点検開始}{機械査定}{点検完了}
τ3 = {コード照会}{起票完了}{機械査定}
τ4 = {点検開始}{点検完了}{機械査定}
τ5 = {コード照会}{起票完了}{コード照会}{機械査定}
τ6 = {点検開始}{コード照会}{機械査定}
【０１６８】
すると、次のことが分かる。
(1)のrφが、τ1、τ3、τ5を受理し、τ2、τ4、τ6を拒否する。
(2)のrφが、τ1、τ2、τ3、τ5、τ6を受理し、τ4を拒否する。
(3)のrφが、τ1、τ2、τ4、τ5を受理し、τ3、τ6を拒否する。
【０１６９】
このような制約を適用して、ログ・トレースTに対する受理率を検査(examine)して、次第に正規文法を改良(refine)するのが、ログ・パターン改良モジュールの役割である。その際、変換(transform)サブモジュール２２４と、置き換え(substr)サブモジュール２２２は、改良(refine)処理のため、改良サブモジュール２１８から呼ばれる。
【０１７０】
こうして最終的に得られた正規文法は、有限状態遷移系生成モジュール２２８に渡される。
【０１７１】
ここで改めて、有限状態遷移系生成モジュール２２８の処理を説明するための用語を定義する。
【０１７２】
すなわち、Σ= アルファベット集合、Σ* = アルファベットを任意個つなげた語の集合とする。
正規表現rの定義は、r::=ε|a|r∪r|r∩r|rc|r・r|r* であり、
ここで、a はアルファベット集合Σ の任意の元であり、
εは、Σに属さない特別な記号である。
なお、正規表現rは、正規文法とも呼ばれる。
【０１７３】
さらに、ε-遷移を含む非決定性有限状態遷移機械(ε-NFA)Mを次のように定義する。
Q= 状態集合= {q0, q1,q2, ...} 
Σ= アルファベット集合, ε =Σに属さない特別な遷移
Δ= 状態遷移の集合 (Δ⊂Q×(Σ∪{ε})×Q)
q0 = 初期状態, F = 終了状態の集合
また、L(M) = ε-NFA Mよって受理される語の集合とする。
【０１７４】
そこで、M1 = (Q,Σ∪{ε},Δ1,q1,F1), M2=(Q2,Σ∪{ε},Δ2,q2,F2)とする。このようなM1とM2があったとき、使用される関数を次のとおり定義する。
disj(M1,M2) = L(M1)∪L(M2) を受理するε-NFA
ε-遷移によって、M1またはM2に分岐するようにε-NFAを定義したものの集合である。
conj(M1,M2) = L(M1)∩L(M2) を受理するε-NFA
状態集合の直積Q1×Q2に対し、(q1,a,q'1) ∈ Δ1かつ(q2,a, q'2)∈Δ2の時(q1,q2),a,(q'1,q'2))がconj(M1,M2)の遷移になるように定める。
neg(M1) = Σ*＼L(M1)を受理するε-NFA
受理と非受理 (拒絶) を反転させたε-NFAである。
concat(M1,M2) = {w1 ・w2 | w1 ∈ L(M1), w2 ∈ L(M2) } を受理するε-NFA
F1からq2へのε-遷移を追加してM1とM2をつなげたε-NFAである。
rep(M1) = {w*|w ∈ L(M1)} を受理するε-NFA
F1からq1へのε-遷移とM1を経ずに終了するε-遷移を追加したε-NFAである。
【０１７５】
これらの関数を用いて、有限状態遷移系生成モジュール２２８が使用する、正規表現を等価なε-NFA(非決定性オートマトン)に変換する関数RE_to_eNFA(r)の処理の擬似コードは、次のように記述される。これは、見て取れるように、再帰的な処理である。
procedure RE_to_eNFA(r)
begin  
case r in
ε :  return( M = ({q0}, {}, {}, q0, {q0}))  
a :  return( M = ({q0, q1}, {a}, {(q0, a, q1)}, q0, {q1}) )  
r1 ∪ r2 :  return(disj(RE_to_eNFA(r1), RE_to_eNFA(r2)))  
r1 ∩ r2 :  return(conj(RE_to_eNFA(r1), RE_to_eNFA(r2)))  
rc :  return(neg(RE_to_eNFA(r)))  
r1・r2  :  return(concat(RE_to_eNFA(r1), RE_to_eNFA(r2))) 
r * :  return(rep(RE_to_eNFA(r)))  
endcase
end
【０１７６】
次に、有限状態遷移系生成モジュール２２８のさらに別の機能は、RE_to_eNFA(r)によって得られたε-NFA(非決定性オートマトン)を、DFA(決定性有限オートマトン)に変換することである。
【０１７７】
ここで定義を与えると、
ε-遷移を含む非決定性有限状態遷移機械 (ε-NFA)M = (Q,Σ∪{ε},Δ,q0,F)としたとき、
Q = 状態集合 = {q0,q1,q2, ...} 
Σ= アルファベット集合, ε = Σ に属さない特別な遷移
Δ= 状態遷移の集合 (Δ ⊂ Q×(Σ∪{ε})×Q) 
q0 = 初期状態,F = 終了状態の集合
である。
【０１７８】
一方、決定性有限状態遷移機械(DFA) M = (Q,Σ,Δ,q0,F)
ここで、使用される関数を次のとおり定義する。
ε-closure(q) =ε-遷移以外の遷移を除去した時にq から到達可能な状態の集合である。すなわち、q ∈ ε-closure(q), (q,ε,q') ∈ Δ ⇒ ε-closure(q') ⊂ ε-closure(q)である。
t(q,a) =q から(任意回の)ε-遷移とa-遷移で到達可能な状態の集合= ∪ { ε-closure(q'') | q' ∈ ε-closure(q), (q', a, q'') ∈Δ}
【０１７９】
次に、図２６のフローチャートを参照して、ε-NFAからDFAに変換する処理について、説明する。この処理の入力は、ε-NFA M=(Q, Σ∪{ε},Δ,q,F)であり、出力は、DFA M' = (Q', Σ,Δ', X, F')  ここで、F' = {X ∈ Q'|X∩F ≠ {}}である。
【０１８０】
図２６のステップ２６０２では、有限状態遷移系生成モジュール２２８は、X0 = ε-closure(q0)，Q' = {X0}, Δ' = {｝と代入する。
【０１８１】
ステップ２６０４では、有限状態遷移系生成モジュール２２８は、Xがaで遷移する先で未チェックのものを見つける。具体的には、任意のY ∈ Q'で、(X,a,Y)がΔ'の要素でないようなX ∈ Q'と、a ∈ Σを見つける。
【０１８２】
ステップ２６０６で、見つかったかどうかの判断が行われ、もし見つからなければ、処理は終了する。
【０１８３】
ステップ２６０６で、見つかったと判断されると、ステップ２６０８で、
Y = ∪{t(q,a)|q∈X}, Q' = Q' ∪ {Y}, Δ' = Δ' ∪ {(X,a,Y)}として、ステップ２６０４に戻る。
【０１８４】
このように、正規表現rからDFAを生成するところまでが有限状態遷移系生成モジュール２２８の機能であり、以下、生成されたDFAから、ワークフローを生成する、ワークフロー変換モジュール２３０の機能を説明する。
【０１８５】
ワークフロー変換モジュール２２８は、アルゴリズムの都合上、DFAから直接ワークフローではなく、一旦、擬似ワークフローを生成する。
【０１８６】
以下、アルゴリズムを説明するために、変数と関数を定義する。
決定性有限状態機械 DFA M = (Q,Σ,Δ,q0, F) 
Q = 状態集合 = {q0,q1,q2, ...} 
Σ= アルファベット集合,Δ = 状態遷移の集合 (Δ ⊂ Q × Σ × Q) 
q0 = 初期状態, F = 終了状態
擬似ワークフローpWF = (N, E) DFAの遷移 a(∈Σ) をノードとしてとる有向グラフ。ワークフロー生成の前段階として用いられる。
タスク・ノード n= a(i,j), N = タスク・ノードの集合
a = Σの元
i= タスク・ノード n の入口に対して付与した番号
j= タスク・ノード n の出口に対して付与した番号
エッジをeとし、 E = エッジの集合
使用する関数として、次のものを定義する。
count(a) = N の中の a(_,_) という形のタスク・ノードの数
init(e) = エッジeの始点 (開始ノード) 
term(e) = エッジeの終点(終点ノード) 
【０１８７】
次に、図２７のフローチャートを参照して、DFAから擬似ワークフローを生成する処理について、説明する。この処理の入力は、DFAM = (S, Σ,Δ, s0, F)であり、出力は、擬似ワークフローpWF = (N, E)である。
【０１８８】
図２７のステップ２７０２では、ワークフロー変換モジュール２２８は、NとEに空集合をセットする。
【０１８９】
ステップ２７０４では、ワークフロー変換モジュール２２８は、Δの全ての要素(qi,a,qj)について、N = N∪{a(i,j)}を処理することによって、ノード集合Nを生成する。
【０１９０】
ステップ２７０６では、ワークフロー変換モジュール２２８は、Nの全ての要素a(i,j),b(j,k)について、E = E∪{a(i,j),b(j,k)}を処理することによって、エッジ集合Eを生成する。
【０１９１】
次に、擬似ワークフローから、ワークフローを生成する処理について説明する。
【０１９２】
ワークフローWF = (N,E,X)
ここでは、フローチャートに近い構造として、ワークフローを定める。ワークフローには変数の集合 X が付随し、x ∈ X の更新ノード (x := ...) や x の値に応じた分岐ノードをもちうる。
ノードnは、以下のいずれかである。
- update(x,v): 変数x の値を v に更新
- label(a): a をラベルにもつ。(a はDFA のアルファベット) 
但し、ワークフロー中にaをラベルにもつノードは二つ以上存在しない
- 分岐
【０１９３】
エッジeは、ノードnとn' を結ぶ。処理の流れを表わす。
特に分岐ノードから出るエッジには条件「x=v 」が付随する。
(x の値がvのとき、そのエッジが選択される)
combine(A)は、擬似ワークフローのノードのうち、A = {a(i1, j1), a(i2, j2), .., a(im, jm) } をまとめたものに対応するWFノードとエッジをつくる。
【０１９４】
次に、図２８のフローチャートを参照して、ワークフローから擬似ワークフローを生成する処理について、説明する。この処理の入力は、擬似ワークフロー (N, E) であり、出力は、ワークフロー(N', E', {st}) である。
【０１９５】
図２８のステップ２８０２では、ワークフロー変換モジュール２２８は、N' = {}, E' = E. X = {st}, k = 0と初期化する。
【０１９６】
ステップ２８０４では、ワークフロー変換モジュール２２８は、Σの全てのaについて、
A = {a(i1, j1), a(i2, j2), .., a(im, jm)}
(N'',E'') = combine(A)
N' = N'∪N''
E' = E'∪E''
の処理を行い、処理を終了する。こうしてワークフロー(N', E', {st}) のデータが得られると、これらのデータを以って、適当な描画処理によって、ディスプレイ１１４にワークフローを表示することができる。
【０１９７】
例として、r = ([^<機械査定>]*)c∪([^<機械査定>]*<起票完了>[^<機械査定>]*.*<機械査定>.*)という正規表現を考える。
【０１９８】
すると、図２９は、有限状態遷移系生成モジュール２２８によって生成された状態遷移系を示す図である。
【０１９９】
図３０は、この状態遷移系を以って、ワークフロー変換モジュール２３０が最終的に生成したワークフローである。
【０２００】
以上のように、特定の実施例に従い、本発明を説明してきたが、本発明は、特定のオペレーティング・システムやプラットフォームに限定されず、任意のコンピュータ・システム上で実現可能である。
【０２０１】
また、解析のベースとなる業務ログも、保険業務などの特定の業務のログに限定されず、業務内容または作業内容またはそのＩＤが時系列的に配列され、コンピュータ読取り可能に保存されているなら、任意のログに適用可能である。
【符号の説明】
【０２０２】
１０２  システム・パス
１０２  バス
１０４  ＣＰＵ
１０６  主記憶
１０８  ハードディスク・ドライブ
１１０  キーボード
１１２  マウス
１１４  ディスプレイ
１１６  通信インターフェース
２０２  業務ログ
２０４  ログ処理モジュール
２０６  グラフ作成サブモジュール
２０８  ノイズ検出サブモジュール
２１０  ログ削除サブモジュール
２１２  スコア計算サブモジュール
２１４  表示サブモジュール
２１６  ログ・パターン改良モジュール
２１８  改良サブモジュール
２２０  検査サブモジュール
２２４  変換サブモジュール
２２６  制約
２２８  有限状態遷移系生成モジュール
２３０  ワークフロー変換モジュール
３０２  ログ・ファイル
【図１】
0005431256.tif 000002
【図２】
0005431256.tif 000003
【図３】
0005431256.tif 000004
【図４】
0005431256.tif 000005
【図５】
0005431256.tif 000006
【図６】
0005431256.tif 000007
【図７】
0005431256.tif 000008
【図８】
0005431256.tif 000009
【図９】
0005431256.tif 000010
【図１０】
0005431256.tif 000011
【図１１】
0005431256.tif 000012
【図１２】
0005431256.tif 000013
【図１３】
0005431256.tif 000014
【図１４】
0005431256.tif 000015
【図１５】
0005431256.tif 000016
【図１６】
0005431256.tif 000017
【図１７】
0005431256.tif 000018
【図１８】
0005431256.tif 000019
【図１９】
0005431256.tif 000020
【図２０】
0005431256.tif 000021
【図２１】
0005431256.tif 000022
【図２２】
0005431256.tif 000023
【図２３】
0005431256.tif 000024
【図２４】
0005431256.tif 000025
【図２５】
0005431256.tif 000026
【図２６】
0005431256.tif 000027
【図２７】
0005431256.tif 000028
【図２８】
0005431256.tif 000029
【図２９】
0005431256.tif 000030
【図３０】
0005431256.tif 000031