Process Mining Discovery, Conformance and Enhancement of Business Processes.PDF

1、Process MiningWil M.P.van der AalstProcessMiningDiscovery,Conformance andEnhancement of Business ProcessesWil M.P.van der AalstDepartment Mathematics&Computer ScienceEindhoven University of TechnologyDen Dolech 25612 AZ EindhovenThe Netherlandsw.m.p.v.d.aalsttue.nlISBN 978-3-642-19344-6e-ISBN 978-3-

2、642-19345-3DOI 10.1007/978-3-642-19345-3Springer Heidelberg Dordrecht London New YorkLibrary of Congress Control Number:2011926240ACM Computing Classication(1998):H.4.1,H.2.8,I.2.6,F.3.2,D.2.2,J.1 Springer-Verlag Berlin Heidelberg 2011This work is subject to copyright.All rights are reserved,whether

3、 the whole or part of the material isconcerned,specically the rights of translation,reprinting,reuse of illustrations,recitation,broadcasting,reproduction on microlm or in any other way,and storage in data banks.Duplication of this publicationor parts thereof is permitted only under the provisions o

4、f the German Copyright Law of September 9,1965,in its current version,and permission for use must always be obtained from Springer.Violationsare liable to prosecution under the German Copyright Law.The use of general descriptive names,registered names,trademarks,etc.in this publication does notimply

5、,evenintheabsenceof aspecic statement,that suchnames areexempt from therelevantprotectivelaws and regulations and therefore free for general use.Cover design:deblikPrinted on acid-free paperSpringer is part of Springer Science+Business Media()Thanks to Karin for understanding thatscience is more rew

6、arding than runningerrandsThanks to all people that contributed toProM;the fruits of their efforts demonstratethat sharing a common goal is moremeaningful than“cashing in the nextpublon”1In remembrance of Gerry Straatman-Beelen(19322010)1publon=smallest publishable unitPrefaceProcess mining provides

7、 a new means to improve processes in a variety of applica-tion domains.There are two main drivers for this new technology.On the one hand,more and more events are being recorded thus providing detailed information aboutthe history of processes.Despite the omnipresence of event data,most organization

8、sdiagnose problems based on ction rather than facts.On the other hand,vendors ofBusiness Process Management(BPM)and Business Intelligence(BI)software havebeen promising miracles.Although BPM and BI technologies received lots of atten-tion,they did not live up to the expectations raised by academics,

9、consultants,andsoftware vendors.Process mining is an emerging discipline providing comprehensive sets of toolsto provide fact-based insights and to support process improvements.This new disci-pline buildson process model-drivenapproachesanddata mining.However,processmining is much more than an amalg

10、amation of existing approaches.For example,existing data mining techniques are too data-centric to provide a comprehensive un-derstanding of the end-to-end processes in an organization.BI tools focus on sim-ple dashboards and reporting rather than clear-cut business process insights.BPMsuites heavil

11、y rely on experts modeling idealized to-be processes and do not helpthe stakeholders to understand the as-is processes.This book presents a range of process mining techniques that help organizationsto uncover their actual business processes.Process mining is not limited to pro-cess discovery.By tigh

12、tly coupling event data and process models,it is possible tocheck conformance,detect deviations,predict delays,support decision making,andrecommend process redesigns.Process mining breathes life into otherwise staticprocess models and puts todays massive data volumes in a process context.Hence,manag

13、ements trends related to process improvement(e.g.,Six Sigma,TQM,CPI,and CPM)and compliance(SOX,BAM,etc.)can benet from process mining.Process mining,as described in this book,emerged in the last decade 102,106.However,the roots date back about half a century.For example,Anil Nerode pre-sented an app

14、roach to synthesize nite-state machines from example traces in 195871,Carl Adam Petri introduced the rst modeling language adequately capturingconcurrency in 1962 73,and Mark Gold was the rst to systematically exploreviiviiiPrefacedifferent notions of learnability in 1967 45.When data mining started

15、 to our-ish in the nineties,little attention was given to processes.Moreover,only recentlyevent logs have become omnipresent thus enabling end-to-end process discovery.Since the rst survey on process mining in 2003 102,progress has been spectacu-lar.Process mining techniques have become mature and s

16、upported by various tools.Moreover,whereas initially the primary focus was on process discovery,the pro-cess mining spectrum has broadened markedly.For instance,conformance check-ing,multi-perspectiveprocessmining,andoperationalsupporthave becomeintegralparts of ProM,one of the leading process minin

17、g tools.This is the rst book on process mining.Therefore,the intended audience isquite broad.The book provides a comprehensive overview of the state-of-the-artin process mining.It is intended as an introduction to the topic for practitioners,students,and academics.On the one hand,the book is accessi

18、ble for people that arenew to the topic.On the other hand,the book does not avoid explaining importantconcepts on a rigorous manner.The book aims to be self-contained while coveringthe entire process mining spectrum from process discovery to operational support.Therefore,it also serves as a referenc

19、e handbook for people dealing with BPM orBI on a day-to-day basis.The reader can immediately put process mining into practice due to the applica-bility of the techniques,the availability of(open-source)process mining software,and the abundance of event data in todays information systems.I sincerely

20、hopethat you enjoy reading this book and start using some of the amazing process min-ing techniques available today.Wil M.P.van der AalstSchleiden,GermanyDecember 2010AcknowledgementsMany individuals and organizations contributed to the techniques and tools de-scribed in this book.Therefore,it is im

21、portant to acknowledge their support,efforts,and contributions.All of this started in 1999 with a research project named“Process Design byDiscovery:Harvesting Workow Knowledge from Ad-hoc Executions”initiated byTon Weijters and myself.At that time,I was still working as a visiting professorat the Un

22、iversity of Colorado in Boulder.However,the research school BETA hadencouraged me to start collaborating with existing staff in my new research groupat TU/e(Eindhoven University of Technology).After talking to Ton it was clearthat we could benet from combining his knowledge of machine learning with

23、myknowledge of workow management and Petri nets.Process mining(at that time wecalled it workow mining)was the obvious topic for which we could combine ourexpertise.This was the start of a very successful collaboration.Thanks Ton!Since then many PhD students have been working on the topic:Laura Marus

24、ter,Ana Karla Alves de Medeiros,Boudewijn van Dongen,Minseok Song,Chris-tian Gnther,Anne Rozinat,Carmen Bratosin,R.P.Jagadeesh Chandra(JC)Bose,Ronny Mans,Maja Pesic,Joyce Nakatumba,Helen Schonenberg,Arya Adriansyah,and Joos Buijs.Im extremely grateful for their efforts.Ana Karla Alves de Medeiros wa

25、s the rst PhD student to work on the topicunder my supervision(genetic process mining).She did a wonderful job;her thesison genetic process mining was awarded with the prestigious ASML 2007 Promo-tion Prize and was selected as the best thesis by the KNAW research school BETA.Also Boudewijn van Donge

26、n has been involved in the development of ProM rightfrom the start.As a Master student he already developed the process mining toolEMiT,i.e.,the predecessor of ProM.He turned out to be a brilliant PhD student anddeveloped a variety of process mining techniques.Eric Verbeek did a PhD on work-ow veric

27、ation,but over time he got more and more involved in process miningresearch and the development of ProM.Many people underestimate the importanceof a scientic programmer like Eric.Tool development and continuity are essen-tial for scientic progress!Boudewijn and Eric have been the driving force behin

28、dixxAcknowledgementsProM and their contributions have been crucial for process mining research at TU/e.Moreover,they are always willing to help others.Thanks guys!Christian Gnther and Anne Rozinat joined the team in 2005.Their contributionshave been of crucial importance for extending the scope of p

29、rocess mining and lift-ing the ambition level.Christian managed to make ProM look beautiful while sig-nicantly improving its performance.Moreover,his Fuzzy miner facilitated dealingwith Spaghetti processes.Anne managed to widen the process mining spectrum byadding conformance checking and multi-pers

30、pective process mining to ProM.It isgreat that they succeeded in founding a process mining company(Fluxicon).An-other person crucial for the development of ProM is Peter van den Brand.He set upthe initial framework and played an important role in the development of the archi-tecture of ProM 6.Based

31、on his experiences with ProM,he set up a process miningcompany(Futura Process Intelligence).It is great to work with people like Peter,Christian,and Anne;they are essential for turning research results into commercialproducts.I sincerely hope that Fluxicon and Futura Process Intelligence continue to

32、be successful(not only because of prospective sports cars.).Academicsof various universitiescontributed to ProM and supportedour processmining research.We are grateful to the Technical University of Lisbon,KatholiekeUniversiteit Leuven,Universitat Politcnica de Catalunya,Universitt Paderborn,Univers

33、ity of Rostock,Humboldt-Universitt zu Berlin,University of Calabria,Queensland University of Technology,Tsinghua University,Universitt Innsbruck,Ulsan National Institute of Science and Technology,Universit di Bologna,Zhe-jiang University,Vienna University of Technology,Universitt Ulm,Open Univer-sit

34、y,Jilin University,University of Padua,and University of Nancy for their help.I would also like to thank the members of the IEEE Task Force on Process Miningforpromotingthetopic.Wearegratefultoallotherorganizationsthatsupportedpro-cess mining research at TU/e:NWO,STW,EU,IOP,LOIS,BETA,SIKS,StichtingE

35、IT Informatica Onderwijs,Pallas Athena,IBM,LaQuSo,Philips Healthcare,ESI,Jacquard,Nufc,BPM Usergroup,and WWTF.Special thanks go to Pallas Athenafor promoting the topic of process mining and their collaboration in a variety ofprojects.More than 100 organizations provided event logs that helped us to

36、improveour process mining techniques.Here,I would like to explicitly mention the AMChospital,Philips Healthcare,ASML,Ricoh,Vestia,Catharina hospital,Thales,Oc,Rijkswaterstaat,Heusden,Harderwijk,Deloitte,and all organizations involved inthe SUPER,ACSI,PoSecCo,and CoSeLoG projects.We are grateful for

37、allowingus to use their data and for providing feedback.It is impossible to name all of the individuals that contributed to ProM or helpedtoadvanceprocessmining.Nevertheless,Iwouldliketomakea modestattempt.Be-sides the people mentioned earlier,I would like to thank Piet Bakker,Huub de Beer,Tobias Bl

38、ickle,Andrea Burattin,Riet van Buul,Toon Calders,Jorge Cardoso,JosepCarmona,Alina Chipaila,Francisco Curbera,Marlon Dumas,Schahram Dustdar,Paul Eertink,Dyon Egberts,Dirk Fahland,Diogo Ferreira,Walid Gaaloul,StijnGoedertier,Adela Grando,Gianluigi Greco,Dolf Grnbauer,Antonella Guzzo,Kees van Hee,Joach

39、im Herbst,Arthur ter Hofstede,John Hoogland,Ivo de Jong,Ivan Khodyrev,Thom Langerwerf,Massimiliano de Leoni,Jiafei Li,Ine van derAcknowledgementsxiLigt,Zheng Liu,Niels Lohmann,Peter Hornix,Fabrizio Maggi,Jan Mendling,Frits Minderhoud,Arnold Moleman,Marco Montali,Michael zur Muehlen,JorgeMunoz-Gama,M

40、ariska Netjes,Andriy Nikolov,Mykola Pechenizkiy,Carlos Pedri-naci,Viara Popova,Silvana Quaglini,Manfred Reichert,Hajo Reijers,RemmertRemmerts de Vries,Stefanie Rinderle-Ma,Marcello La Rosa,Michael Rosemann,Vladimir Rubin,Stefania Rusu,Eduardo Portela Santos,Natalia Sidorova,Alessan-dro Sperduti,Chri

41、stian Stahl,Keith Swenson,Nikola Trcka,Kenny van Uden,IreneVanderfeesten,George Varvaressos,Marc Verdonk,Sicco Verwer,Jan Vogelaar,Hans Vrins,Jianmin Wang,Teun Wagemakers,Barbara Weber,Lijie Wen,Jan Mar-tijn van der Werf,Mathias Weske,Michael Westergaard,Moe Wynn,Bart Ydo,andMarco Zapletal for their

42、 support.Thanks to all that read earlier drafts of this book(special thanks go to Christian,Eric,and Ton for their detailed comments).Thanks to Springer-Verlag for publishing this book.Ralf Gerstner encouragedme to write this book and handled things in a truly excellent manner.Thanks Ralf!More than

43、95%of book was written in beautiful Schleiden.Despite my sabbat-ical,there were many other tasks competing for attention.Thanks to my weeklyvisits to Schleiden(without Internet access!),it was possible to write this book in athree month period.The excellent coffee of Seran helped when proofreading t

44、heindividual chapters,the scenery did the rest.As always,acknowledgements end with thanking the people most precious.Lions share of credits should go to Karin,Anne,Willem,Sjaak,and Loes.Theyoften had to manage without me under difcult circumstances.Without their con-tinuing support,this book would h

45、ave taken ages.Wil M.P.van der AalstSchleiden,GermanyDecember 2010Contents1Introduction.11.1Data Explosion.11.2Limitations of Modeling.31.3Process Mining.71.4Analyzing an Example Log.111.5Play-in,Play-out,and Replay.181.6Trends.211.7Outlook.23Part IPreliminaries2Process Modeling and Analysis.292.1Th

46、e Art of Modeling.292.2Process Models.312.2.1Transition Systems.312.2.2Petri Nets.332.2.3Workow Nets.382.2.4YAWL.402.2.5Business Process Modeling Notation(BPMN).422.2.6Event-Driven Process Chains(EPCs).442.2.7Causal Nets.462.3Model-Based Process Analysis.522.3.1Verication.522.3.2Performance Analysis

47、.552.3.3Limitations of Model-Based Analysis.573Data Mining.593.1Classication of Data Mining Techniques.593.1.1Data Sets:Instances and Variables.603.1.2Supervised Learning:Classication and Regression.623.1.3Unsupervised Learning:Clustering and Pattern Discovery.643.2Decision Tree Learning.64xiiixivCo

48、ntents3.3k-Means Clustering.703.4Association Rule Learning.743.5Sequence and Episode Mining.773.5.1Sequence Mining.773.5.2Episode Mining.783.5.3Other Approaches.813.6Quality of Resulting Models.823.6.1Measuring the Performance of a Classier.833.6.2Cross-Validation.853.6.3Occams Razor.88Part IIFrom E

49、vent Logs to Process Models4Getting the Data.954.1Data Sources.954.2Event Logs.984.3XES.1074.4Flattening Reality into Event Logs.1145Process Discovery:An Introduction.1255.1Problem Statement.1255.2A Simple Algorithm for Process Discovery.1295.2.1Basic Idea.1295.2.2Algorithm.1335.2.3Limitations of th

50、e-Algorithm.1365.2.4Taking the Transactional Life-Cycle into Account.1395.3Rediscovering Process Models.1405.4Challenges.1445.4.1Representational Bias.1455.4.2Noise and Incompleteness.1475.4.3Four Competing Quality Criteria.1505.4.4Taking the Right 2-D Slice of a 3-D Reality.1536Advanced Process Dis