03_Scalable_process_discovery_with_guarantees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Scalable Process Discovery with Guarantees](http://www.padsweb.rwth-aachen.de/wvdaalst/publications/p825.pdf)\n",
    "\n",
    "> **Ref**:\n",
    "\n",
    "> Sander Leemans, Dirk Fahland, Wil van der Aalst: Scalable process discovery and conformance\n",
    "checking, Software & Systems Modeling."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Summary (partial)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Scalable $\\implies$ run time of process discovery algorithm is independent from number of traces in the log \n",
    "\n",
    "Independence of the number of activities cannot be achieved, as activities are part of the output of any technique. For such cases, it is better to adopt for decomposing process discovery\n",
    "\n",
    "**Scalable algorithms**: (that does not provide soundness guarantee)\n",
    "\n",
    "> **alpha miner and it's derivatives**: \n",
    "\n",
    ">> requires just a **single pass over the event log**.\n",
    "\n",
    ">> Guarantees rediscoverability\n",
    "\n",
    ">> But they **do not guarantee sound models**.\n",
    "\n",
    "**Non scalable algorithms**: (provides guarantees, but not scalable)\n",
    "\n",
    "> **Genetic process mining and Evolutionary tree miners** :\n",
    "\n",
    ">> Requires **multiple pass** over event log\n",
    "\n",
    ">> Guarantees soundness\n",
    "\n",
    ">> **No rediscoverability guarantee**\n",
    "\n",
    "> **Inductive miner**: \n",
    "\n",
    ">> Requires **multiple pass** over event log\n",
    "\n",
    ">> Guarantees both soundess and rediscoverability\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The technique described in the paper -- **Inductive miner directly-follows**($IM_D$) is **scalable and gaurentees both soundness and rediscoverability** \n",
    "\n",
    "> Adapts Inductive miner framework to recurse on **directly-follows graph** rather than event logs\n",
    "\n",
    "> **Directly-follows graphs** can be computed in a **single pass** over the event log, and their computation can even be **parallelised**.\n",
    "\n",
    "> The size of a **directly-follows** graph only **depends quadratically on the number of activities** in a log, and is **independent of the number of traces or events**\n",
    "\n",
    "> Therefore, this adaptation combines the scalability of directly-follows graphs, as used by the\n",
    "Heuristics Miner (HM) and the α-algorithm (α), with guarantees such as sound-\n",
    "ness and rediscoverability as provided by the IM framework"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### $IM_D$ Process discovery\n",
    "\n",
    "Let the petrinet be $N = (P,T,F)$\n",
    "\n",
    "Where\n",
    "\n",
    "> $P $: set of places\n",
    "\n",
    "> $T $: set of transitions\n",
    "\n",
    "> Arcs $F \\subseteq (P \\times T) \\cup (T \\times P)$\n",
    "\n",
    "Process discovery involves finding all the places $P$ and arcs $F$. In the $IM_D$ framework, the following steps are involved\n",
    "\n",
    "> 1) Finding the **directly follows graph** $D$\n",
    "\n",
    ">> Let graph $D = (\\mathbf{\\Sigma}, E)$ be obtained by identifying directly follows relations that occur more than $t_{freq}$ times in a log $L$\n",
    "\n",
    ">> Where\n",
    "\n",
    ">>> $\\mathbf{\\Sigma} : $ Set of **all activities** observed in log $L$\n",
    "\n",
    ">>> $E = \\{(a,b) \\in \\mathbf{\\Sigma} \\times \\mathbf{\\Sigma} \\ \\mid \\ \\#(a \\to b) \\geq t_{freq} \\}$\n",
    "\n",
    ">>> $D \\in \\mathcal{G} \\qquad$  where $\\mathcal{G}$ is a space of all directly follows graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 2) Directly follows graph is recursively **partitioned** by identifying **cuts**, until a **base case** is reached. Lets first define the terms,\n",
    "\n",
    ">> *Partition* : Non-overlapping division of activities in $D$\n",
    "\n",
    ">> *Cut* ($C$) : *Partition* combined with one of the following process tree operator. $C \\in \\{\\times, \\to, \\wedge,\\circlearrowright \\}$\n",
    "\n",
    ">>> $\\times$ : Exclusive choice, where the partitions are disconnected\n",
    "\n",
    ">>> $\\to$ : Sequential behaviour, where the partitions are sequentially connected\n",
    "\n",
    ">>> $\\wedge$ : Parallel behaviour, where the partitions can occur concurrently\n",
    "\n",
    ">>> $\\circlearrowright$ : Each partition should contain a clear set of start and end activities and the loop between partitions should go through these activities\n",
    "\n",
    ">>> <img src=\"files/cuts.png\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">> $IM_D$ **searches for cuts** that will **partition the graph** $D$ in accordance with one of the process tree operators.\n",
    "\n",
    ">> **Cut detection** ($CD$) has been implemented using standard graph algorithms (connected components, strongly connected components)\n",
    "\n",
    ">>> **Ref** : Leemans, S., Fahland, D., van der Aalst, W.: Discovering block-structured process models\n",
    "from event logs - a constructive approach. In: Petri Nets 2013. LNCS, vol. 7927, pp. 311–329. Springer (2013)\n",
    "\n",
    ">>> Cut detection $CD : D \\to (C, \\{D_1, D_2, ..., D_K\\})$ \n",
    "\n",
    ">>> where\n",
    "\n",
    ">>>> $C$ is a cut (one of the process tree operator)\n",
    "\n",
    ">>>> $D_i \\quad i \\in [1,K] \\quad$ are directly-follows graphs containing partitioned activites\n",
    "\n",
    ">>>> $D, D_i \\in \\mathcal{G}$\n",
    "\n",
    ">> $IM_D$ **recurses** on each of the new directly-follows graph $D_i$ **until** one of the following **base case** is reached:\n",
    "\n",
    ">>> 1) $D_i$ contains only **one activity**\n",
    "\n",
    ">>> 2) *Fall-through* : No cuts are possible. Any behaviours are possible consisting of activities in this partition. \n",
    "\n",
    ">> Each of these recursions **returns a process tree** that is **inserted as a child**. \n",
    "\n",
    ">> Places $P$ and arcs $F$ of a petri net can be derived from the **process tree**\n",
    "\n",
    "> Thus we have all the parameters required to build a process model\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Complexity of $IM_D$\n",
    "\n",
    "For $\\mid \\mathbf{\\Sigma} \\mid = n$, \n",
    "\n",
    "> **cut detection** is $O(n^2)$\n",
    "\n",
    "> Each recursion removes atleast one activity from the graph $\\implies IM_D$ is $O(n^3)$ \n",
    "\n",
    "> Directly follows graph requires just a single pass over event log $L$ and can be parallelized"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Guarantees of $IM_D$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Process trees are inherently sound\n",
    "\n",
    "> $IM_D$ guarantees rediscoverability on the same class of models, i.e. assuming\n",
    "that the model is representable by a process tree without using duplicate activities, and\n",
    "it is not possible to start loops with an activity they can also end with\n",
    "\n",
    ">> **Ref** : Leemans, S., Fahland, D., van der Aalst, W.: Discovering block-structured process models\n",
    "from event logs - a constructive approach. In: Petri Nets 2013. LNCS, vol. 7927, pp. 311–329. Springer (2013)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Handling infrequent behaviour\n",
    "\n",
    "> Infrequent behaviours may introduce edges which may make it impossible to detect an otherwise strong cut\n",
    "\n",
    "> Therefore, whenever *fall-through* occurs, **edges with frequency less** than certain threshold $t_{freq}$ are **removed** and **cuts** are **computed again**. \n",
    "\n",
    ">> $t_{freq}(a) = h \\times max_c(\\#(a \\to c)) \\qquad$ where $h \\in (0,1)$\n",
    "\n",
    ">> i.e, we keep edges $(a \\to b)$, which occur frequently enough compared to most occuring outgoing edge of $a$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Handling incomplete behaviour\n",
    "\n",
    "TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluation\n",
    "\n",
    "TODO"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}