工作流程（workflow）是商業流程自動化的一部份。一個工作流程是由完成一件工作所有可能執行的活動（activity）以及活動間在執行時的前後關係所構成。而工作流程的設計或改進舊有的工作流程是商業上很重要的工作，因為工作流程的好與壞會影響企業的競爭力。工作流程探勘（workflow mining）是利用資料探勘的技術，分析工作流程執行時所留下的流程執行記錄，還原出一個能夠產生這些記錄的工作流程模型（workflow model），而這個工作流程模型可做為設計新模型或改進既有模型的參考。
本研究針對我們所定義的工作流程模型，以一個未知的工作流程模型所產生的流程執行記錄（workflow log）當做輸入資料（input data），提出方法利用輸入資料還原一個能夠產生輸入資料中所有資料工作流程模型，且希望這個工作流程模型能與產生流程執行記錄之未知模型越相似越好。我們提出兩個還原工作流程模型的演算法，並利用precision和recall來評估還原的模型與未知模型間的相似程度，驗證我們所提出方法的效果。實驗結果顯示，我們的方法所還原的工作流程模型precision和recall值都能達到80%以上。

The workflow plays an important role in business process automation. A workflow is composed of activities and causal relations between activities to complete a task. Workflow design and refinement are important tasks in business process reengineering. As a workflow is executed, the orders of the executed activities are recorded in workflow logs. Workflow mining utilizes the technology of data mining to analyze these workflow logs, and reconstruct a workflow model.
In this thesis, we investigate the workflow mining problem to reconstrcuct the workflow model. Two algorithms are proposed to reconstruct a workflow model. We evaluate our proposed algorithms by precision and recall to measure the similarity between the constructed and the groundtruth models. The result of the experiment shows that our proposed methods can achieve 80% precision and 80% recall for the reconstruction of workflow models.

[1] A. Inokuchi, T. Washio, and H. Motoda. An Apriori-based Algorithm for MiningFrequent Substructures from Graph Data. Proceedings of the European Conference on Principles of Data Mining and Knowledge Discovery, 2000.
[2] M. Kuramochi, and G. Karypis. Frequent Subgraph Discovery. Proceedings of IEEE International Conference on Data Mining, 2001.
[3] X. Yan, and J. Han. gSapn: Graph-based Substructure Pattern Mining. Proceedings of IEEE International Conference on Data Mining, 2002.
[4] X. Yan, and J. Han. CloseGraph: Mining Closed Frequent Graph Patterns. Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003.
[5] R. Agrawal, and R. Srikant. “Mining Sequential Patterns,” Proceedings of International Conference on Data Engineering, 1995.
[6] R. Srikant, and R. Agrawal. Mining Sequential Patterns: Generalizations and Performance Improvements. Proceedings of International Conference on Extending Database Technology, 1996.
[7] J. Han, J. Pei, B. Mortazavi-Asl, Q. Chen, U. Dayal, and M. C. Hsu. FreeSpan: Frequent Pattern-Projected Sequential Pattern Mining. Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2000.
[8] J. Pei, J. Han, B. Mortazavi-Asl, and H. Pinto. PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth. Proceedings of International Conference on Data Engineering, 2001.
[9] G. Greco, A. Guzzo, G. Manco, and D. Saccà. Mining Frequent Instances on Workflows. Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2003.
[10] G. Greco, A. Guzzo, G. Manco, and D. Saccà. Mining and Reasoning on Workflows. IEEE Transactions on Knowledge and Data Engineering, Vol. 17, No.4, pp. 519-534, 2005.
[11] R. Agrawal, and R. Srikant. Fast Algorithms for Mining Association Rules. Proceedings of International Conference on Very Large Data Bases, 1994.
[12] A. K. A. de Medeiros, W. M. P. van der Aalst, and A. J. M. M. Weijters. Workflow Mining: Current Status and Future Directions. Proceedings of International Conference on Cooperative Information Systems, 2003.
[13] G. Greco, A. Guzzo, G. Manco, L. Pontieri, and D. Saccà. Mining Constrained Graphs: The Case of Workflow Systems. Constraint-Based Mining and Inductive Databases, pp. 155-171, 2004.
[14] R. Agrawal, D. Gunopulos, and F. Leymann. Mining Process Models from Workflow Logs. Proceedings of International Conference on Extending Database Technology, 1998.
[15] G. Greco, A. Guzzo, L. Pontieri, and D. Saccà. On the Mining of Complex Workflow Schemas. Proceedings of Italian Conference on Advanced Database Systems, 2004.
[16] G. Greco, A. Guzzo, L. Pontieri, and D. Saccà. Mining Expressive Process Models by Clustering Workflow Traces. Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2004.
[17] W. M. P. van der Aalst, B. F. van Dongena, J. Herbst, L. Marustera, G. Schimm, and A. J. M. M. Weijters. Workflow Mining: A Survey of Issues and Approach. Data & Knowledge Engineering, Volume 47, Issue 2, pp. 237-267, 2003.
[18] S. Y. Hwang, C. P. Wei, and W. S. Yang. Discovery of Temporal Patterns from Process Instances. Computers in Industry, Volume 53, Issue 3, pp. 345-364, 2004.
[19] W. M. P. van der Aalst, and A. J. M. M. Weijters. Process Mining: A Research Agenda. Computers in Industry, Volume 53, Issue 3, pp. 231-244, 2004.
[20] G. Schimm. Mining Exact Models of Concurrent Workflows. Computers in Industry, Volume 53 , Issue 3, pp. 265-281, 2004.
[21] L. Maruster, W. M. P. van der Aalst, T. Weijters, A. van der Bosch, and W. Daelemans. Automated Discovery of Workflow Models from Hospital Data. Proceeding of Belgium-Netherlands Conference on Artificial Intelligence, 2001.
[22] S. S. Pinter, and M. Golani. Discovering Workflow Models from Activities’ Lifespans. Computers in Industry, Volume 53, Issue 3, pp. 283-296, 2004.
[23] R. J. van Glabbeek, and W. P. Weijland. Branching Time and Abstraction in Bisimulation Semantics. Journal of ACM, Vol. 43, No. 3, pp. 555-600, 1996.
[24] H. Mannila, and D. Rusakov. Decomposition of Event Sequences into Independent Components. Proceeding of SIAM International Conference on Data Mining, 2001.
[25] J. E. Cook, and A. L. Wolf. Discovering Models of Software Processes from Event-based Data. ACM Transactions on Software Engineering and Methodology, Vol. 7, No. 3, pp. 215-249, 1998.
[26] W. M. P. van der Aalst, and B. F. van Dongen. Discovering Workflow Performance Models from Timed Logs. Proceedings of International Conference on Engineering and Deployment of Cooperative Information Systems, 2002.
[27] D. Grigori, F. Casati, U. Dayal, and M. C. Shan. Improving Business Process Quality through Exception Understanding, Prediction, and Prevention. Proceeding of International Conference on Vary Large Data Bases, 2001.
[28] G. Schimm. Process Miner-A Tool for Mining Process Schemes from Event-based Data. Proceeding of European Conference on Artificial Intelligence, 2002.
[29] L. Maruster, A. J. M. M. Weijters, W. M. P. van der Aalst, and A. van den Bosch. Process Mining：Discovering Direct Successors in Process Logs. Proceedings of International Conference on Discovery Science, 2002.
[30] W. M. P. van der Aalst, A. J. M. M. Weijters, and L. Maruster. Workflow Mining：Which Process can be Rediscovered？. BETA Working Paper Series, WP 74, Eindhoven University of Technology, 2002.
[31] J. E. Cook, and A. L. Wolf. Event-Based Detection of Concurrency. ACM SIGSOFT Software Engineering Notes, Vol. 23, Issue 6, pp. 35-45, 1998.
[32] J. E. Cook, and A. L. Wolf. Software Process Validation：Quantitatively Measuring the Correspobdence of a Process to a Model. ACM Transactions on Software Engineering and Methodology, Vol. 8, No. 2, pp. 147-176, 1999.
[33] G.. Greco, A. Guzzo, G.. Manco, and D. Saccà. Mining Unconnected Patterns in Workflows. Proceeding of SIAM International Conference on Data Mining, 2005.
[34] B. F. van Dongen, and W. M. P. van der Aalst. Multi-phase Process Mining：Building Instance Graphs. Proceeding of International Conference on Conceptual Modeling, 2004.
[35] E. Liu, A. Kumar, and W. M. P. van der Aalst. A Formal Modeling Approach for Supply Chain Event Management. Workshop on Issues in the Theory of Security, 2004.
[36] S. Dustdar, T. Hoffmann, and W. M. P. van der Aalst. Mining of Ad-hoc Business Processes with TeamLog. Technical Report TUV-1841-2004-07, Vienna University of Technology, 2004.
[37] J. Herbst, and D. Karagiannis. Workflow Mining with InWoLvE. Computers in Industry, Volume 53 , Issue 3, pp. 245-264, 2004.
[38] L. Dehaspe, and H. Toivonen. Discovery of Frequent DATALOG Patterns. Data Mining and Knowledge Discovery, Volumn 3, Issue 1, pp. 7-36, 1999.
[39] C. Faloutsos, K. S. McCurley, and A. Tomkins. Fast Discovery of Connection Subgraphs. Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004.
[40] J. Huan, W. Wang, and J. Prins. Efficient Mining of Frequent Subgraph in the Presence of Isomorphism. Proceedings of IEEE International Conference on Data Mining, 2003.
[41] J. E. Cook, and A. L. Wolf. Automating Process Discovery through Event-data Analysis. Proceedings of International Conference on Software Engineering, 1995.
[42] W. S. Yang. Mining Workflow Instances to Support Workflow Schema Design. Master Thesis, National Sun Yat-sen University, 1998.
[43] S. Y. Hwang, and W. S. Yang. On the Discovery of Workflow Models from Their Instances. Decision Support System, Vol. 34, Issue 1, pp. 41-57, 2002.
[44] W. M. P. van der Aalst, A. P. Barros, A.H.M ter Hofstede, and B. Kiepuszewski. Advance Workflow Patterns. Proceedings of International Conference on Cooperative Information System, 2000.