{"id":140,"date":"2020-02-28T12:00:11","date_gmt":"2020-02-28T11:00:11","guid":{"rendered":"https:\/\/blog.rwth-aachen.de\/pads\/?p=140"},"modified":"2020-03-09T08:41:30","modified_gmt":"2020-03-09T07:41:30","slug":"prediction-based-recommendation-in-process-mining","status":"publish","type":"post","link":"https:\/\/blog.rwth-aachen.de\/pads\/2020\/02\/28\/prediction-based-recommendation-in-process-mining\/","title":{"rendered":"Prediction-based recommendation in process mining"},"content":{"rendered":"\n<p><em>This post is by <a href=\"https:\/\/www.pads.rwth-aachen.de\/cms\/PADS\/Der-Lehrstuhl\/Team\/Wissenschaftliche-Mitarbeiter\/~eavji\/Gyunam-Park\/lidx\/1\/\">Gyunam Park<\/a>, Scientific Assistant in the Process And Data Science group at RWTH Aachen University. Contact him via email for further inquiries.<\/em><\/p>\n\n\n\n<p>Process mining has provided effective\ntechniques to extract in-depth insights into business processes such\nas process discovery, conformance checking, and enhancement.\nNowadays, with the increasing availability of real-time data and\nsufficient computing power, practitioners are more interested <strong>in\n<\/strong><em><strong>forward looking<\/strong><\/em><strong> techniques whose insights can be\nused to improve performances and mitigate risks of running process\ninstances<\/strong>.<\/p>\n\n\n\n<p>Research on these <em>forward looking<\/em>\ntechniques has been actively done in the field of process mining.\n<em>Predictive business process monitoring<\/em> is one of those\napproaches, whose aim is to improve business processes <strong>by offering\ntimely information<\/strong> (e.g., remaining time of running instances)\nthat enables proactive and corrective actions.<\/p>\n\n\n\n<p>However, these techniques do not suggest how the predictions are\nexploited to improve business processes, leaving it up to the\nsubjective judgment of practitioners. The transformation from\npredictions to concrete actions remain as <strong>missing link to achieve\nthe goal of process improvement<\/strong>.<\/p>\n\n\n\n<p>A recent paper, <a href=\"https:\/\/ieeexplore.ieee.org\/document\/8786063\">\u201c<em>Prediction-based Resource Allocation using LSTM and Minimum Cost and Maximum Flow Algorithm<\/em>\u201d<\/a>, demonstrate an effort to connect the missing link between the predictive insights to concrete recommendations, which enables process improvement. In the paper, authors exploit the <strong>prediction results from predictive business process monitoring techniques to recommend optimal resource allocations in business processes<\/strong>.<\/p>\n\n\n\n<p>In the following, I will explain 1) Predictive business process monitoring, 2) Resource allocation in business process, and 3) Prediction-based recommendation (specifically for resource allocation).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\n1. Predictive business process monitoring<\/h3>\n\n\n\n<p>Predictive business process monitoring\ntechniques provide insightful predictions on running instances in\nbusiness processes. The techniques can be divided into several\ncategories depending on the type of values they aim to predict. The\nprimary types of predictions include<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>\nremaining time (i.e., how much time is left\n\tto complete a case),\n\t<\/li><li>\nrisk probability (i.e., how probable it is\n\tfor a case to fail at the end),\n\t<\/li><li>\nnext event (i.e., the property of the next\n\tevent (e.g., next activity) of a case).\n<\/li><\/ul>\n\n\n\n<p>How can we predict those values? There\nexist several different approaches, but in a simple way, we can think\nof them as <strong>finding a correlation between features (i.e.,\n<\/strong><em><strong>predictors<\/strong><\/em><strong>) and the target values (i.e.,\n<\/strong><em><strong>predictand<\/strong><\/em><strong>)<\/strong>.<\/p>\n\n\n\n<p>There are mainly two types of <em>predictors<\/em> that can be used\nto describe <em>predictand<\/em>. The first type is the <em>case\nproperty<\/em>, which indicates the case attributes (e.g., the\nmembership of a customer) or the event attributes that are related to\nthe case (e.g., the previous treatments a customer went through in\nthe process). The second type is the <em>context of a business\nprocess<\/em>, which describes the status of the process at the time\npredictions are made (e.g., the total number of ongoing cases in the\nprocess and the total number of resources in the process, etc.).<\/p>\n\n\n\n<p>Let\u2019s have a look at the example showing how we derive the correlation between <em>predictors<\/em> and <em>predictand<\/em>.<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"455\" src=\"https:\/\/blog.rwth-aachen.de\/pads\/files\/2020\/03\/image-2-1024x455.png\" alt=\"\" class=\"wp-image-141\" srcset=\"https:\/\/blog.rwth-aachen.de\/pads\/files\/2020\/03\/image-2-1024x455.png 1024w, https:\/\/blog.rwth-aachen.de\/pads\/files\/2020\/03\/image-2-300x133.png 300w, https:\/\/blog.rwth-aachen.de\/pads\/files\/2020\/03\/image-2-768x341.png 768w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Assume that we are interested in building a model to find the\ncorrelation between the <strong>activity records that a patient went\nthrough in the past (<\/strong><em><strong>predictor-case property<\/strong><\/em><strong>)\nand the number of ongoing patients in the process (<\/strong><em><strong>predictor-context\nof a business process<\/strong><\/em><strong>)<\/strong> and <strong>the remaining time\n(<\/strong><em><strong>predictand<\/strong><\/em><strong>)<\/strong>. In <em>context1<\/em> with 100\nongoing patients, <em>Patient1<\/em> went through <em>Triage<\/em>, <em>MRI<\/em>,\n<em>Blood Test<\/em> in the past, and the remaining time was 6 hours. On\nthe other hand, <em>Patient2<\/em> was in the same context as <em>Patient1<\/em>\nwhile skipping <em>MRI<\/em> compared to <em>Patient1<\/em>, and the\nremaining time was 4 hours. From these observations, we are able to\nfind that the existence of an MRI operation is <strong>positively\ncorrelated<\/strong> to the remaining time (possibly due to the following\nadditional operations like MRI evaluation, etc.).<\/p>\n\n\n\n<p><em>Patient3<\/em> was in <em>context2<\/em> with 50 ongoing patients\nand went through the same activities as <em>Patient1<\/em>, but the\nremaining time was 3 hours. Based on this, we can conclude that the\nnumber of ongoing patients in the process is <strong>negatively correlated<\/strong>\nto the remaining time. The discovered correlations can be used to\npredict the remaining times of any given running instances with its\nvalues of <em>predictors<\/em>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\n2. Resource allocation in business process<\/h3>\n\n\n\n<p>Resource allocation is to <strong>allocate\nappropriate resources to tasks at the correct time<\/strong>, which enables\nto improve productivity, balance resource usage, and reduce execution\ncosts. Resource allocation in business process management shares\ncommonalities with the Job Shop Scheduling Problem (JSSP). JSSP is to\nfind the job sequences on machines to achieve a goal (e.g.,\nminimizing makespans), while the machine sequence of the jobs is\nfixed.<\/p>\n\n\n\n<p>A huge amount of approaches has been suggested to solve JSSP in\nthe field of operations research. One of the promising approaches is\n<em>dispatching rules<\/em> due to its computing efficiency and\nrobustness to uncertainty.<\/p>\n\n\n\n<p>However, <strong>those techniques require parameters<\/strong> such as the\nrelease time, the processing time, and the sequence of operations of\njobs. Indeed, in many cases of business processes, we have limited\ninformation that prohibits the deployment of them. For instance, in\nan emergency department of a hospital, we do not know when and why a\npatient would come into the department before the visit happens,\nclinical procedures of the patient, and the processing time taken for\nresources to finish an operation.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"> 3. Prediction-based resources allocation<\/h3>\n\n\n\n<p>You may expect what comes next. Yes, we can exploit the techniques from predictive business process monitoring to deal with resource allocation in business processes where required parameters for scheduling are missing. <strong>To this end, first, we predict the relevant parameters (e.g., the subsequent activities of the patients and their processing times) and then utilize them to optimize resource allocation<\/strong>.<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"538\" src=\"https:\/\/blog.rwth-aachen.de\/pads\/files\/2020\/03\/image-3-1024x538.png\" alt=\"\" class=\"wp-image-142\" srcset=\"https:\/\/blog.rwth-aachen.de\/pads\/files\/2020\/03\/image-3-1024x538.png 1024w, https:\/\/blog.rwth-aachen.de\/pads\/files\/2020\/03\/image-3-300x158.png 300w, https:\/\/blog.rwth-aachen.de\/pads\/files\/2020\/03\/image-3-768x404.png 768w, https:\/\/blog.rwth-aachen.de\/pads\/files\/2020\/03\/image-3.png 1758w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Suppose we optimize the resource allocation at time  in MRI operation, as shown in Figure 2, with respect to the total weighted completion time. Note that we use the urgency of patients, described in Table 1, as weights. The higher the urgency of a patient is, the more weight he\/she is assigned to. In other words, we want to assign resources to patients in a way that minimizes the processing time, and, at the same time, treat urgent patients earlier than others.<\/p>\n\n\n\n<p>Let\u2019s first consider the initial setting where we don\u2019t have any information for resource allocation. In this case, there is no option but to randomly assign patients to resources. Next, suppose we have the information about processing time required for resources to treat different patients. In this case, we can assign the most efficient resource to each patient, i.e., <em>p1<\/em> to <em>r2<\/em> and <em>p2<\/em> to <em>r1<\/em>. Finally, assume that we predict that an urgent patient, <em>p3<\/em>, is about to require MRI operation at time <em>t+1<\/em>. In this case, we can reserve a resource to wait for this patient since it is more efficient in terms of total weighted completion time, i.e., at <em>t<\/em>, <em>p1 <\/em>to <em>r2 <\/em>and at <em>t+1<\/em>, <em>p3<\/em> to <em>r1<\/em>. <strong>To sum up, if we predict the processing time and the next activity of a patient, we can tremendously improve the scheduling performance.<\/strong><\/p>\n\n\n\n<p>Then, how can we solve it in an algorithmic way? For this, we formulate the resource allocation problem into <em>minimum cost and maximum flow problem<\/em>, where we aim at maximizing the number of flows while minimizing the cost of flows. This problem is solved in <strong>polynomial time<\/strong> by <em>network simplex method<\/em>, so the algorithm for resource allocation is.<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"376\" src=\"https:\/\/blog.rwth-aachen.de\/pads\/files\/2020\/03\/image-4-1024x376.png\" alt=\"\" class=\"wp-image-143\" srcset=\"https:\/\/blog.rwth-aachen.de\/pads\/files\/2020\/03\/image-4-1024x376.png 1024w, https:\/\/blog.rwth-aachen.de\/pads\/files\/2020\/03\/image-4-300x110.png 300w, https:\/\/blog.rwth-aachen.de\/pads\/files\/2020\/03\/image-4-768x282.png 768w, https:\/\/blog.rwth-aachen.de\/pads\/files\/2020\/03\/image-4.png 1562w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Figure 3 shows how we formulate it. Based on the parameters we predicted (the leftmost), we add source node  and sink node . Besides, we annotate  on each arc. The arcs coming from source node and to source node always has <em>(0, 1)<\/em>, while <em>cost<\/em> of other arcs are designed to be proportional to the processing time. By applying <em>network simplex method<\/em> in this graph, we get the optimal resource allocations as depicted as green arcs in the rightmost.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">For more\ninformation,<\/h3>\n\n\n\n<p>Check out <a href=\"https:\/\/icpmconference.org\/2019\/wp-content\/uploads\/sites\/6\/2019\/09\/ICPM-20190626-gnpark_f.pdf\">slides\nof ICPM 2019<\/a><\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>\nG. Park and M. Song, <a href=\"https:\/\/ieeexplore.ieee.org\/document\/8786063\">\u201c<em>Prediction-based\n\tResource Allocation using LSTM and Minimum Cost and Maximum Flow\n\tAlgorithm<\/em>\u201d<\/a>, 2019\n\tInternational Conference on Process Mining (ICPM), Aachen, Germany,\n\t2019, pp.&nbsp;121-128.\n<\/li><\/ol>\n","protected":false},"excerpt":{"rendered":"<p>This post is by Gyunam Park, Scientific Assistant in the Process And Data Science group at RWTH Aachen University. Contact him via email for further inquiries. Process mining has provided [&hellip;]<\/p>\n","protected":false},"author":1679,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"c2c_always_allow_admin_comments":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-140","post","type-post","status-publish","format-standard","hentry","category-allgemein"],"_links":{"self":[{"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/posts\/140","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/users\/1679"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/comments?post=140"}],"version-history":[{"count":1,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/posts\/140\/revisions"}],"predecessor-version":[{"id":144,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/posts\/140\/revisions\/144"}],"wp:attachment":[{"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/media?parent=140"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/categories?post=140"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.rwth-aachen.de\/pads\/wp-json\/wp\/v2\/tags?post=140"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}