Process Mining: Data science in Action の第4週終わった。 内容は第3週で扱いきれなかったマイニングアルゴリズムの残りの話を少しと、メインの Conformance Checking の話、それからイベントデータ自体の分析の話。

マイニングアルゴリズムの話は以下の4つ:
(1) 第3週で扱った、transition system を生成して、そこからリージョンに基づいて並行性を求めることでペトリネットを学習する二段階のアプローチの限界と拡張、
(2) language-based region という概念を使うアプローチ
(3) genetic mining
(4) inductive mining

language-based region を使うアプローチは、プレースのトークン数が負になりえないことを利用し、「そのプレースの初期トークン数」(c)、「各遷移からそのプレースへのアーク」(x)、「そのプレースから各遷移へのアーク」(y)を変数、各トレースの各段階でトークン数が非負でであることを制約条件として、整数線形計画問題(integer linear programming)を解くことで、条件を満たす(c,x,y)の値を求める。それぞれの解はプレースとしてfeasbileなもの。 ただ、無数にある解のなかからどの解を選ぶかについては「Goal function can be used to select the most interesting places」としか言っていなくて、また実際にはプレースを複数求めていく必要があると思うが、その辺りを実際にどうやっていくのか気になった。ProMだと ILP Miner がこれを実装している。そういえば、ILP Miner という名前を最初に見た時は帰納論理プログラミング(Inductive Logic Programming)の方のILPだと思ったけど、整数線形計画の方のILPだったのね。 あと、どの辺りがlanguage-basedなのかとちょっと思ったけれど、トレース集合の prefix closure を言語としているからか。

genetic mining は詳しく説明されてはいなかったが、普通の遺伝的アルゴリズムっぽい。

inductive mining は、トレース(の集合)を xor, seq, par などを使って異なる部分に分解していって、プロセスの帰納的な構造を得るような方法。ループの導出とかどうやるんだろうなぁ、と思ったけれど、それも説明されておらずちょっと残念。

メインの Conformance Checking の話については以下の３つの解説
(1) イベントログとプロセスモデルの双方からfootprintを生成して、一致しているセルの割合でfitnessを定義する方法 (Conformance Checking Using Causal Footprints)
(2) トークンを流してみて、生成・消費したトークンのうち、どれだけが残留したり欠けていたかでfitnessを定義する方法 (Conformance Checking Using Token-Based Replay)
(3) イベントログと、プロセスモデル上でそれに出来るだけ近いトレースを並べて、不一致箇所によってfitnessを定義する方法 (Aligning Observed and Modeled Behavior)

footprintを使う手法に関しては、任意のペトリネットからのfootprintの生成をアルゴリズム的にどうやるのかが分からなかった。これどっかでやってたかなぁ。構造化されたペトリネットなら自明に出来そうではあるが。

それからイベントデータ自体の分析の話。まずは、activity instance = event ではなく、１つの activity instance に対して、「開始」「中断」「再開」「終了」などの複数のイベントがあり得るという話。これは自分気になってはいたが、実際にProMやDiscoで実際にどうやって扱うのかという話はなかった。それから、イベントログの集まりの全体的な傾向を見るための dotted chart の話。

クイズは、実際に手で計算しなくちゃいけない問題が多く、かなりかったるかったが、何とか一回で満点をゲット。

Process Mining: Data science in Action
https://www.coursera.org/course/procmin

#procmin