Efficient ticket routing by resolution sequence mining

ABSTRACT

IT problem management calls for quick identification of resolvers to reported problems. The efficiency of this process highly depends on ticket routing---transferring problem ticket among various expert groups in search of the right resolver to the ticket. To achieve efficient ticket routing, wise decision needs to be made at each step of ticket transfer to determine which expert group is likely to be, or to lead to the resolver.

In this paper, we address the possibility of improving ticket routing efficiency by mining ticket resolution sequences alone, without accessing ticket content. To demonstrate this possibility, a Markov model is developed to statistically capture the right decisions that have been made toward problem resolution, where the order of the Markov model is carefully chosen according to the conditional entropy obtained from ticket data. We also design a search algorithm, called Variable-order Multiple active State search(VMS), that generates ticket transfer recommendations based on our model. The proposed framework is evaluated on a large set of real-world problem tickets. The results demonstrate that VMS significantly improves human decisions: Problem resolvers can often be identified with fewer ticket transfers.

REFERENCES

• 1: Rakesh Agrawal , Dimitrios Gunopulos , Frank Leymann, Mining Process Models from Workflow Logs, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.469-483, March 23-27, 1998
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 3: Jay Ayres , Jason Flannick , Johannes Gehrke , Tomi Yiu, Sequential PAttern mining using a bitmap representation, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775109]
• 4: C. Chatfield. Statistical inference regarding Markov chain models. Appl. Statist., 22:7--20, 1973.
• 5: Data mining for path traversal patterns in a web environment, Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96), p.385, May 27-30, 1996
• 6: Jonathan E. Cook , Alexander L. Wolf, Discovering models of software processes from event-based data, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.3, p.215-249, July 1998 [doi>10.1145/287000.287001]
• 7: Jonathan E. Cook , Alexander L. Wolf, Event-based detection of concurrency, Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering, p.35-45, November 01-05, 1998, Lake Buena Vista, Florida, United States
• 8: L. Finesso, C.-C. Liu, and P. Narayan. The optimal error exponent for Markov order estimation. IEEE Trans. on Information Theory, 42(5):1488--1497, 1996.
• 9: Walid Gaaloul , Sadek Alaoui , Karim Baina , Claude Godart, Mining Workflow Patterns through Event-Data Analysis, Proceedings of the 2005 Symposium on Applications and the Internet Workshops, p.226-229, January 31-February 04, 2005
• 10: W. Gaaloul, S. Bhiri, and C. Godart. Discovering workflow transactional behavior from event-based log. In Proc 12th Int'l Conf. CoopIS, pages 3--18, 2004.
• 11: W. Gaaloul and C. Godart. Mining workflow recovery from event based logs. In Proc. 3rd Int'l Conf. Business Process Management, pages 169--185, 2005.
• 12: Ron Kohavi , Llew Mason , Rajesh Parekh , Zijian Zheng, Lessons and Challenges from Mining Retail E-Commerce Data, Machine Learning, v.57 n.1-2, p.83-113, October-November 2004 [doi>10.1023/B:MACH.0000035473.11134.83]
• 13: H. Mannila and D. Rusakov. Decomposition of event sequences into independent components. In Proc. 1st SIAM Conf. Data Mining, pages 1--17, 2001.
• 14: Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo, Discovery of Frequent Episodes in Event Sequences, Data Mining and Knowledge Discovery, v.1 n.3, p.259-289, 1997 [doi>10.1023/A:1009748302351]
• 15: B. Mobasher, N. Jain, E. Han, and J. Srivastava. Web mining: Pattern discovery from world wide web transactions. In TR 96-050, Univ. of Minnesota, Dept. of Computer Science, 1996.
• 16: Jian Pei , Jiawei Han , Behzad Mortazavi-Asl , Helen Pinto , Qiming Chen , Umeshwar Dayal , Meichun Hsu, PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth, Proceedings of the 17th International Conference on Data Engineering, p.215-224, April 02-06, 2001
• 17: A. Rozinat and W. van der Aalst. Decision mining in ProM. In LNCS, pages 420--425, 2006.
• 18: Qihong Shao, Yi Chen, Shu Tao, Xifeng Yan, and Nikos Anerousis. Easyticket: A ticket routing recommendation engine for enterprise problem resolution. 34th Int'l Conf. VLDB, 2008.
• 19: R. Silva, J. Zhang, and J. G. Shanahan. Probablistic workflow mining. In Proc. 1998 Int'l Conf Knowledge Discovery and Data Mining, pages 469--483, 1998.
• 20: Jaideep Srivastava , Robert Cooley , Mukund Deshpande , Pang-Ning Tan, Web usage mining: discovery and applications of usage patterns from Web data, ACM SIGKDD Explorations Newsletter, v.1 n.2, January 2000 [doi>10.1145/846183.846188]
• 21: Wil van der Aalst , Ton Weijters , Laura Maruster, Workflow Mining: Discovering Process Models from Event Logs, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1128-1142, September 2004 [doi>10.1109/TKDE.2004.47]
• 22: Mohammed J. Zaki, SPADE: an efficient algorithm for mining frequent sequences, Machine Learning, v.42 n.1/2, p.31-60, Jan. 2001 [doi>10.1023/A:1007652502315]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Design

Keywords:
markov model, sequence mining, workflow mining and optimization