臺灣博碩士論文加值系統

現今網際服務（Web Service）已經成為許多大型企業用來整合商業流程的主
要技術，如何從現有的服務中發現複合服務的議題成為熱門的研究領域。本篇論
文主要是利用資料探勘領域中兩種方法來探勘網際服務使用者記錄，以分析網際
服務之間的關係，第一種方法，多層關聯規則探勘方法（Multilevel Association
Rules Mining）可探勘出常用的服務組合，且可發現服務間較高層次上的關係；
第二種方法，序列模式探勘（Sequential Pattern Mining）可探勘出常用序列的服
務組合關係。前者產出結果為無順序性的相關服務組合，可作為一種建議，讓使
用者自行選擇使用；後者產出結果為具有順序性相關的服務組合，並有助於整合
成真實的商業流程。實驗顯示我們提出的方法具有實用性、彈性及效率，根據本
方法探勘的結果促使容易整合複合服務組合。

Web Service Technology is being applied to organizing business
process in many large-scale enterprises. Discovery of Composite Service, therefore, has become an active research area. In this paper, we propose
two methodologies in data mining area to analyze the relationship among
these web services from web service usage log. First, Multilevel
Association Rules Mining is used for discovery of frequently used sets of
web services. Additionally, it can extract high-level relationships among
web services. Second, Sequential Pattern Mining is used for discovery of
the sequence of web services. The former produces unordered sets of web
services which can be used as suggestions to the user. The latter generates
time-ordered sets of web services which can be exploited to integrate into
a real business process. The empirical result shows the proposed
methodologies are useful, flexible, and efficient. It is able to integrate
simple web services into a composite service according to the mining
result of the proposed approach.

Chinese Abstract……………………………………………… i
English Abstract……………………………………………… ii
Table of Contents …………………………………………… iii
List of Figures………………………………………………… v
List of Tables ……………………………………………… vii
Chapter 1 Introduction ……………………………………… 1
Chapter 2 Related Work……………………………………… 5
Chapter 3 System Architecture……………………………… 8
3-1 Web Logging……………………………………………………………10
3-2 Pre-processing……………………………………………………………12
3-3 Concept Hierarchy………………………………………………………15
3-4 Pattern Discovery…………………………………………………………17
Chapter 4 Service Mining for Composite Service Discovery…18
4-1 Multilevel Association Rule Mining ……………………………………19
4-1-1 Association Rule Mining…………………………………………20
4-1-2 Multilevel Association Rule Mining……………………………21
4-2 Sequential Pattern Mining………………………………………………36
4-2-1 WAP-tree Algorithm……………………………………………36
iii
4-2-2 PLWAP-tree Algorithm…………………………………………36
Chapter 5 Experiment Result……………………………… 51
5-1 Two Cases……………………………………………………………… 51
5-1-1 Case 1 …………………………………………………………51
5-1-2 Case 2 …………………………………………………………52
5-2 The Generation of Web Usage Log…………………………………… 53
5-3 Performance…………………………………………………………… 54
5-3 Performance…………………………………………………………… 54
5-3-1 Comparison of Execution Time……………………………54
5-3-2 Comparison of the Number of Patterns…………………………56
5-4 Pattern Analysis………………………………………………………… 58
Chapter 6 Conclusion……………………………………… 66
Reference…………………………………………………… 67

[1] Q. Liang, S. Miller and J. Chung, "Service Mining for Web Service Composition", by IEEE International Conference on Information Reuse and Integration (IEEE IRI-2005), Las Vegas, Nevada, USA, 2005.
[2] http://www.w3.org/TR/wsdl
[3] http://www.uddi.org/
[4] http://www.w3.org/TR/soap
[5] http://www.w3.org/2001/sw
[6] Meng-Feng Tsai and Yi-Ming Lee, "Mining Self-derivable Multilevel FP-tree From a Transactional Database", National Central University, Taiwan, Master Thesis, 2006.
[7] Lu, Yi., Ezeife, C.I., "Position Coded Pre-Order Linked WAP-Tree for Web Log Sequential Pattern Mining, " by Proceedings of The 7th Pacific- Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2003), Seoul, Korea, 2003.
[8] R.Agrawal, D.Gunopulos, and F.Leymann, "Mining process models from workflow logs," by Proc of 6th international Conference on Extending Database Technology, pages 469-483, 1998.
[9] Wil van der Aalst, Ton Weijters, and Laura Maruster, "Workflow Mining: Discovering Process Models from Event Logs," IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 9, pp. 1128-1142, Sept. 2004. - 67 -
[10] Ricardo Silva, Jiji Zhang and James G.Shanahan, "Probabilistic Workflow Mining," Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining (KDD ''05), Chicago, Illinois, USA, 2005.
[11] Sami Bhiri, Olivier Perrin and Claude Godart, "Extending workflow patterns with transactional dependencies to define reliable composite Web services," Proceedings of the Advanced International Conference on Telecommunications and International Conference on Internet and Web Applications and Services, 2006.
[12] Robert Gombotz and Schahram Dustdar, "On Web Services Workflow Mining," BPM2005 Workshops, LNCS 3812, 2005.
[13] Mobasher B., Honghua Dai, Tao Luo, and Nakagawa M., "Using sequential and non-sequential patterns in predictive Web usage mining tasks, " by Proceedings of the IEEE International Conference on Data Mining (ICDM＇02), Maebashi City, Japan, December 2002.
[14] M. Hogo, M. Snorek, P. Lingras, "Temporal Cluster Migration Matrices for Web Usage Mining," by Proceedings of 2004 IEEE/WIC International Conference on Web Intelligence, WI2004, Beijing, China, 2004.
[15] F. Masseglia, D. Tanasa, B. Trouses, "Web Usage Mining: Sequential Pattern Extraction with a Very Low Support," by Proceedings of the 6th Asia-Pacific Web Conference, Hangzhou, China, 2004.
- 68 -
[16] Q. Liang, J. Chung, S. Miller, O. Yang, "Service Pattern Discovery of Web Service Mining in Web Service Registry-Repository," by Proc. IEEE International Conference on E-Business Engineering, Shanghai China, 2006.
[17] http://ws.apache.org/axis/
[18] http://www.opentravel.org/
[19] Jiawei H., Yongjian F., "Discovery of Multiple-Level Association Rules from Large Databases, " by Proc. of 1995 Int''l Conf. on Very Large Data Bases (VLDB''95).
[20] Agrawal R.and Srikant R., "Fast algorithm for mining association rules, " by Proc. of 1994 Int. Conf.on Very Large Data Bases (VLDB''94), pages 487-499, Santiago, Chile, Sept. 1994.
[21] Klemettinen M., Mannila H., Ronkainen P., Toivonen H., and Verkamo I., "Finding interesting rules from large sets of discovered association rules, " by Proc. 3rd Int. Conf. Information and Knowledge Management (CIKM''94), pages 401-408, Gaithersburg, MD, Nov. 1994.
[22] Han J., Pei J., and Yin Y., "Mining frequent patterns without candidate generation, “ by Proc. 2000 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD''00), pages 1-12, Dallas, TX, May 2000.