基于日志完备性的过程漂移检测方法
|
摘要
过程挖掘中漂移检测的目的是通过检测日志的变化来断定模型是否发生了改变,然而现有方法存在抽取特征量大、检测延迟及无法准确定位变化区域的局限。针对突发漂移检测提出一种基于完备性的漂移检测算法。首先,将突发漂移检测转换为日志中局部完备性计算问题;然后,利用切比雪夫不等式推断完备性表达式;进一步,通过可选参数的窗口来训练完备性初始值,避免选择及并发结构的干扰;最后,定义了切割操作对漂移之前的完备值进行清除,进而对日志进行迭代检测。通过多组模型数据进行了实验评估,并与已有方法进行对比,验证了所提方法的有效性。
The purpose of is to assert whether the model has changed by detecting changes in the given log.However,Aiming at the limitations of existing drift detection methods in process mining that were large feature extraction,detection delay and inability to locate changing region accurately,a novel method for sudden drift detection was proposed.The problem of sudden drift detection was transformed into local completeness computing problem of the given log.Then Chebyshev inequality was used to deduce the expression of local completeness based on direct succession and frequency.To avoid the interference of exclusiveness and concurrency,a training window was adopted to calculate the initial value of local completeness.In addition,the cutting operation was defined to ensure that the algorithm could run iteratively until all traces in log had been detected.Experiments on synthetic logs showed that the proposed method was effective in detecting sudden drift.
The purpose of is to assert whether the model has changed by detecting changes in the given log.However,Aiming at the limitations of existing drift detection methods in process mining that were large feature extraction,detection delay and inability to locate changing region accurately,a novel method for sudden drift detection was proposed.The problem of sudden drift detection was transformed into local completeness computing problem of the given log.Then Chebyshev inequality was used to deduce the expression of local completeness based on direct succession and frequency.To avoid the interference of exclusiveness and concurrency,a training window was adopted to calculate the initial value of local completeness.In addition,the cutting operation was defined to ensure that the algorithm could run iteratively until all traces in log had been detected.Experiments on synthetic logs showed that the proposed method was effective in detecting sudden drift.
引文
[1]VAN DER AALST W M P.Process mining:discovery,conformance and enhancement of business proceses[M].Berlin,Germany:Springer-Verlag,2014.
[2]VAN DER AALST W M P,WEIJTERS T,MARUSTER L.Workflow mining:discovering process models from event logs[J].IEEE Transactions on Knowledge&Data Engineering,2004,16(9):1128-1142.
[3]GUO Q,WEN L,WANG J,et al.Mining invisible tasks in non-free-choice constructs[C]//Proceedings of the International Conference on Business Process Management.Berlin,Germany:Springer-Verlag,2015:109-125.
[4]WEIJTERS A J M M,AALST W M P,MEDEIROS A K A.Process mining with the heuristics miner algorithm[EB/OL].[2018-06-28].http://alexandria.tue.nl/repository/books/615595.pdf.
[5]MEDEIROS A K A D,WEIJTERS A J M M,VAN DERAALST W M P.Genetic process mining:an experimental evaluation[J].Data Mining&Knowledge Discovery,2007,14(2):245-304.
[6]VAN DER WERF J M E M,DONGEN B F V,HURKENS CA J,et al.Process discovery using integer linear programming[J].Fundamenta Informaticae,2008,94(3):368-387.
[7]BOSE R P J C,AALST W M P V D,LIOBAITE I,et al.Handling concept drift in process mining[J].Lecture Notes in Computer Science,2011,4(1):391-405.
[8]JAGADEESH R P,BOSE C,VAN DER AALST W M P,et al.Dealing with concept drifts in process mining[J].IEEETransactions on Neural Networks and Learning Systems,2014,25(1),154-171.
[9]MAARADJI A,DUMAS M,ROSA M L,et al.Fast and accurate business process drift detection[M].Business Process Management.Berlin,Germany:Springer-Verlag,2015:406-422.
[10]MAARADJI A,DUMAS M,ROSA M L,et al.Detecting sudden and gradual drifts in business processes from execution traces[J].IEEE Transactions on Knowledge&Data Engineering,2017,29(10):2140-2154.
[11]ZHENG C,WEN L,WANG J.Detecting process concept drifts from event logs[C]//Proceedings of the International Conference on the Move to Meaningful Internet Systems.Berlin,Germany:Springer-Verlag,2017:524-542.
[12]WIDMER G,KUBAT M.Learning in the presence of concept drift and hidden contexts[J].Machine Learning,1996,23(1):69-101.
[13]CARMONA J,GAVALDR.Online techniques for dealing with concept drift in process mining[C]//Proceedings of the International Conference on Advances in Intelligent Data A-nalysis.Berlin,Germany:Springer-Verlag,2012:90-102.
[14]LUENGO D,SEPLVEDA M.Applying clustering in process mining to find different versions of a business process that changes over time[C]//Proceedings of Business Process Management Workshops.Berlin,Germany:Springer-Verlag,2011:153-158.
[15]LOHMANN N,VERBEEK E,DIJKMAN R.Petri net transformations for business processes-a survey[M]//Transactions on Petri Nets&Other Models of ConcurrencyⅡ.Berlin,Germany:Springer-Verlag,2009:46-63.
[16]YUAN Chongyi.Petri net application[M].Beijing:Science Press,2103(in Chinese).[袁崇义.Petri网应用[M].北京:科学出版社,2013.]
[17]YANG H,WEN L J,WANG J M.An approach to evaluate the local completeness of an event log[C]//Proceedings of the12th IEEE International Conference on Data Mining.Washington,D.C.,USA:IEEE,2012:1164-1169.
[18]ROSS S M.Introduction to probability models[M].10th ed.Salt Lake City,Utah,USA:Academic Press,2009.
[19]MILNER R.Communicating and mobile systems the Pi-calculus[M].Cambridge,UK:Cambridge University Press,1999.
[2]VAN DER AALST W M P,WEIJTERS T,MARUSTER L.Workflow mining:discovering process models from event logs[J].IEEE Transactions on Knowledge&Data Engineering,2004,16(9):1128-1142.
[3]GUO Q,WEN L,WANG J,et al.Mining invisible tasks in non-free-choice constructs[C]//Proceedings of the International Conference on Business Process Management.Berlin,Germany:Springer-Verlag,2015:109-125.
[4]WEIJTERS A J M M,AALST W M P,MEDEIROS A K A.Process mining with the heuristics miner algorithm[EB/OL].[2018-06-28].http://alexandria.tue.nl/repository/books/615595.pdf.
[5]MEDEIROS A K A D,WEIJTERS A J M M,VAN DERAALST W M P.Genetic process mining:an experimental evaluation[J].Data Mining&Knowledge Discovery,2007,14(2):245-304.
[6]VAN DER WERF J M E M,DONGEN B F V,HURKENS CA J,et al.Process discovery using integer linear programming[J].Fundamenta Informaticae,2008,94(3):368-387.
[7]BOSE R P J C,AALST W M P V D,LIOBAITE I,et al.Handling concept drift in process mining[J].Lecture Notes in Computer Science,2011,4(1):391-405.
[8]JAGADEESH R P,BOSE C,VAN DER AALST W M P,et al.Dealing with concept drifts in process mining[J].IEEETransactions on Neural Networks and Learning Systems,2014,25(1),154-171.
[9]MAARADJI A,DUMAS M,ROSA M L,et al.Fast and accurate business process drift detection[M].Business Process Management.Berlin,Germany:Springer-Verlag,2015:406-422.
[10]MAARADJI A,DUMAS M,ROSA M L,et al.Detecting sudden and gradual drifts in business processes from execution traces[J].IEEE Transactions on Knowledge&Data Engineering,2017,29(10):2140-2154.
[11]ZHENG C,WEN L,WANG J.Detecting process concept drifts from event logs[C]//Proceedings of the International Conference on the Move to Meaningful Internet Systems.Berlin,Germany:Springer-Verlag,2017:524-542.
[12]WIDMER G,KUBAT M.Learning in the presence of concept drift and hidden contexts[J].Machine Learning,1996,23(1):69-101.
[13]CARMONA J,GAVALDR.Online techniques for dealing with concept drift in process mining[C]//Proceedings of the International Conference on Advances in Intelligent Data A-nalysis.Berlin,Germany:Springer-Verlag,2012:90-102.
[14]LUENGO D,SEPLVEDA M.Applying clustering in process mining to find different versions of a business process that changes over time[C]//Proceedings of Business Process Management Workshops.Berlin,Germany:Springer-Verlag,2011:153-158.
[15]LOHMANN N,VERBEEK E,DIJKMAN R.Petri net transformations for business processes-a survey[M]//Transactions on Petri Nets&Other Models of ConcurrencyⅡ.Berlin,Germany:Springer-Verlag,2009:46-63.
[16]YUAN Chongyi.Petri net application[M].Beijing:Science Press,2103(in Chinese).[袁崇义.Petri网应用[M].北京:科学出版社,2013.]
[17]YANG H,WEN L J,WANG J M.An approach to evaluate the local completeness of an event log[C]//Proceedings of the12th IEEE International Conference on Data Mining.Washington,D.C.,USA:IEEE,2012:1164-1169.
[18]ROSS S M.Introduction to probability models[M].10th ed.Salt Lake City,Utah,USA:Academic Press,2009.
[19]MILNER R.Communicating and mobile systems the Pi-calculus[M].Cambridge,UK:Cambridge University Press,1999.