アルファアルゴリズム

αアルゴリズムまたはαマイナーは、プロセスマイニングで使用されるアルゴリズムであり、一連のイベントシーケンスから因果関係を再構築することを目的としています。これは、 van der Aalst、Weijters、Măruşterによって最初に提唱されました。 ^[1] Alphaマイナーの目標は、イベントログ内のさまざまなアクティビティ間の関係に基づいて、イベントログをワークフローネットに変換することです。イベントログはトレースのマルチセットであり、トレースはアクティビティ名のシーケンスです。その後、いくつかの拡張または変更が提示されており、以下にリストします。

アルファマイナーは、これまでに提案された最初のプロセス発見アルゴリズムであり、プロセス発見の目的とプロセス内のさまざまなアクティビティの実行方法の概要をわかりやすく示しています。アルファマイナーは、ヒューリスティックマイナーなど、他の多くのプロセスマイニング技術の開発の基礎でもあり、遺伝的マイニングはアルファマイナーの基盤となっているアイデアに基づいて開発されました。^[2]

このアルゴリズムはワークフロー ログを入力として受け取り、ワークフロー ネットを構築します。 ${\displaystyle W\subseteq T^{*}}$

これは、タスク間で観察された因果関係を調べることによって行われます。たとえば、特定のタスクはすべての実行トレースで常に別の特定のタスクに先行する可能性があり、これは有用な情報になります。

• ワークフロー トレースまたは実行トレースは、タスクのアルファベットの文字列です。 ${\displaystyle T}$
• ワークフロー ログは、ワークフロー トレースのセットです。

イベント ログは、プロセス検出アルゴリズムを適用するための主な要件です。イベント ログは、ケースの一意の識別子、プロセスで発生するアクションを説明するアクティビティ名、およびタイムスタンプで構成されます。イベント ログは、複数のアクティビティ セットとして表すことができます。わかりやすくするために、次の例ではアルファベットを使用してアクティビティを表します。次の図に示すイベント ログの例を検討してください。

イベント ログは複数のトレースのセットであり、トレースは一連のアクティビティです。したがって、上記のようなイベント ログは、次の表記法を使用して表すことができます。

${\displaystyle L1=[<A,B,C,D>,<A,C,B,D>,<A,E,D>]}$

すべてのイベントログは複数のトレースのセットに要約することができ、そのようなトレースはさらにプロセス内のさまざまなアクティビティ間の関係を分解するために使用できます。アルファマイナーのルールによると、さまざまなケースに属するアクティビティは、それらの間に4種類の関係を持つことができます。^[2]

• 直接継承:何らかの関係 x が y に直接続く場合のみ、 x > y となります。この例では、A > B、A > E、A > Cと見なすことができます。
• 因果関係: x → y はx > y かつ y > x でない場合に限ります。この例では、A → Eと考えることができます。
• 並列: x || yただし x > y かつ y > x。この例では、 B || Cです。
• 選択肢: x # yの場合、x > y でなく、y > x でもありません。この例では、A # Dです。

シーケンスパターン: A → B

XOR 分割パターン: A → B、A → C、 B # C

AND 分割パターン: A → B、A → C、 B || C

アルファ マイナーは、イベント ログを直接フォロー、シーケンス、並列、および選択関係に変換し、それらを使用してプロセス モデルを記述するペトリ ネットを作成することから開始します。最初に、アルゴリズムはフットプリント マトリックスを構築します。フットプリント マトリックスと上記のパターンを使用して、プロセス モデルを構築できます。前述の 4 つの関係に基づいて、最初にフットプリント ベースのマトリックスが検出されます。フットプリント ベースのマトリックスを使用して、場所が検出されます。場所の数を少なく抑えるために、各場所はタスク のセットのペアで識別されます。

• ${\displaystyle Y_{W}}$は、以下の条件を満たすタスクの最大集合の すべてのペアの集合である。${\displaystyle (A,B)}$
  • とには>と のメンバーは含まれません。${\displaystyle A\times A}$${\displaystyle B\times B}$
  • ${\displaystyle A\times B}$は→のサブセットです
• ${\displaystyle P_{W}}$の各要素に対して1つの場所と、入力場所および出力場所が含まれます。${\displaystyle p_{(A,B)}}$${\displaystyle Y_{W}}$${\displaystyle i_{W}}$${\displaystyle o_{W}}$

フロー関係は次のものの和集合です。 ${\displaystyle F_{W}}$

• ${\displaystyle \{(a,p_{(A,B)})|(A,B)\in Y_{W}\wedge a\in A\}}$
• ${\displaystyle \{(p_{(A,B)},b)|(A,B)\in Y_{W}\wedge b\in B\}}$
• ${\displaystyle \{(i_{W},t)|t\in T_{I}\}}$
• ${\displaystyle \{(t,i_{O})|t\in T_{O}\}}$

結果は

• ペトリネット構造${\displaystyle \alpha (W)=(P_{W},T_{W},F_{W})}$
• 入力場所が1つ、出力場所が1つ${\displaystyle i_{W}}$${\displaystyle o_{W}}$
• のすべての遷移は から への -パス上にあるため、これは確かにワークフロー ネットです。${\displaystyle T_{W}}$${\displaystyle F_{W}}$${\displaystyle i_{W}}$${\displaystyle o_{W}}$

上記の例では、アルファマイナーを適用すると次のペトリネットが生成されます。

^[3]によれば、健全な SWF ネットによって生成された完全なワークフロー ログの場合、それを生成したネットを再構築できることがわかります。完全とは、その関係が最大であることを意味します。すべての可能なトレースが存在する必要はありません(ループのあるネットの場合は可算無限になります)。 ${\displaystyle \succ_{W}}$

• 暗黙の場所: Alpha Minerは暗黙の場所と必須の場所を区別できないため、発見されたペトリネットに不要な場所が追加される可能性があります。^[4]
• ループ：アルファマイナーはプロセスモデル内の長さ1と2のループを発見できない。^[5]
• アルファマイナーではローカル依存関係が見落とされることが多い。^[5]
• 表現バイアス：アルファマイナーはペトリネットしか発見できないため、遷移ごとに一意の表示ラベルを要求するなどの表現バイアスが追加されます。^[5]