臺灣博碩士論文加值系統

目前循序樣式探勘的發展，除了改進以往較為被忽略的探勘程序之外，演算法的設計也開始針對資料本身屬性打造客製化的探勘方法。連續項目循序樣式的探勘，即是針對單一項目的序列資料庫，探勘出項目彼此鄰接的頻繁樣式，普遍應用在生物基因序列以及網頁路徑這種單一項目的資料類別，然而，針對這種限定條件的探勘研究為數不多。

本研究針對連續項目循序樣式探勘提出TPGP演算法。TPGP利用兩階段圖形投射，在圖形結構中存放充分的資訊後，串連出數條可以包含所有頻繁單一項目樣式的超級連續單一項目序列，並將之建構成序列樹，然後，一一尋訪序列樹的頻繁節點，即可探勘出所有連續單一項目循序樣式。整個探勘過程只需要掃描資料庫兩次。

在實驗部分，利用IBM資料產生器來產生連續單一項目的實驗資料，並與UDtree演算法做一系列的比較。在實驗結果中，可以發現TPGP演算法在效能與記憶體的使用上，皆有很好的表現。

In the research fields of the sequential pattern mining, many proposed algorithms made efforts on improving the mining efficiency as well as customized the mining algorithms for specific application domains. Contiguous item sequential pattern mining is a novel technique to extract single-item sequential patterns where each pair of adjacent elements in the patterns is connected in the original sequences. The contiguous item sequential patterns can be used widely in many popular data mining research fields such as the biological data mining, movement pattern mining, and web usage mining.

In this study, we propose a new algorithm termed TPGP(Two-Phase Graph Projection). In the beginning, TPGP scans the sequence database once and connected the information which between entries in the sequences is saved in the projected map. By traversing the projected map, we can find the supersets of contiguous single item sequential patterns. Then, the algorithm constructs a tree structure based on the sequences in the supersets found in the first stage and traverses the tree to discover all of the contiguous single item sequential patterns.

We conducted a series of experiments on the synthetic datasets generated by the IBM data generator. The Up-Down tree algorithm is compared with the proposed TPGP algorithm. The experimental results show that TPGP outperforms the UDtree method in both CPU and memory usages.

摘要 i
Abstract ii
致謝 iii
目錄 iv
表目錄 v
圖目錄 vi
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機及目的 1
1.3 論文架構 2
第二章 文獻探討 4
2.1. 循序樣式探勘 4
2.2. 連續項目循序樣式探勘 9
第三章 探勘超級連續單一項目序列 15
3.1. 問題定義 15
3.2. 研究架構 16
3.3. 探勘超級連續單一項目序列流程 17
3.3.1. 建構節點地圖 21
3.3.2. 探勘超級連續單一項目序列 25
3.3.3. scsis_gen函式 27
第四章 探勘連續單一項目循序樣式 32
4.1. 建構序列樹 32
4.2. 刪除子樣式 35
第五章 實驗分析 38
5.1 資料來源 38
5.2 實驗結果與分析 39
第六章 結論與未來發展 49
6.1 結論 49
6.2 未來發展 49
參考文獻 50

中文參考文獻
[1].吳鎮成，「PMSPM:夾擊最長循序樣式探勘演算法」，淡江大學，碩士論文，民國97年。
[2].柯常恩，「以樹狀拆解為基礎探勘連續序列型樣之研究」，南台科技大學，碩士論文，民國97年。
[3].張和逸，「高效率探勘連續路徑序列型樣之研究」，南台科技大學，碩士論文，民國97年。
[4].曾憲雄、蔡秀滿、蘇東興、曾秋蓉、王慶堯，資料探勘 Data Mining，旗標出版股份有限公司，台北，2005。
英文參考文獻
[5].T.M. Anwar, H.W. Beck, S.B. Navathe, “Knowledge Mining by Imprecise Querying: A Classification-based Approach,” Proceedings of the 8th International Conference on Data Engineering, pp. 622-630, 1992.
[6].R. Agrawal, S. Ghosh, T. Imielinski, B. Iyer, A. Swami, “An Interval Classifier for Database Mining Applications,” Proceedings of the 18th International Conference on Very Large Data Bases, pp. 560-573, 1992.
[7].R. Agrawal, T. Imielinski, A. Swami, “Mining Association Rules between Sets of Items in Large Databases,” Proceedings of the ACM SIGMOD International Conference on Management of Data, ACM Press, pp. 207–216, 1993.
[8].R. Agrawal, R. Srikant, “Fast Algorithms for Mining Association Rules,” Proceedings of the 20th International Conference Very Large Data Bases (VLDB’94), pp. 487-499, 1994.
[9].R. Agrawal, R. Srikant, “Mining Sequential Patterns,” Proceedings of the 11th International Conference on Data Engineering, pp. 3-14, 1995.
[10].J. Ayres, J. Gehrke, T. Yu, J. Flannick, “Sequential PAttern Mining using a Bitmap Representation,” International Conference Knowledge Discovery and Data Mining, pp. 429-435, 2002.
[11].Y.H. Cho, J.K. Kim, S.H. Kim, “A Personalized Recommender System Based on Web Usage Mining and Decision Tree Induction,” Expert Systems with Applications, pp. 329-342, 2002.
[12].J.S. Coker, E. Davies, “Identifying Adaptor Contamination When Mining DNA Sequence Data,” BioTechniques, pp. 194-198, 2004.
[13].X. Chang, C. Zhou, Z. Wang, P. Hu, “A Novel Method for Mining Sequential Patterns in Datasets,” Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications (ISDA''06), pp. 611-615, 2006.
[14].J. Chen, “Contiguous Item Sequential Pattern Mining Using UpDown Tree,” Intelligent Data Analysis 12, pp. 25-49, 2008.
[15].M. Ester, H.P. Kriegel, X. Xu, “A Database Interface for Clustering in Large Spatial Databases,” International Conference on Knowledge Discovery in Databases and Data Mining (KDD 95), pp. 94-99, 1995.
[16].M. Ester, H.P. Kriegel, J. Sander, X. Xu, “A Density-based Algorithm for Discovering Clusters in Large Spatial Database with Noise,” International Conference on Knowledge Discovery in Databases and Data Mining (KDD 96), pp. 226-231, 1996.
[17].C.I. Ezeife, Yi Liu, “Fast Incremental Mining of Web Sequential Patterns with PLWAP Tree, ” Knowledge Discovery and Data Mining, 19, pp. 376-416, 2009.
[18].X. Fu, J. Budzik, K.J. Hammond, “Mining Navigation History for Recommendation”, IUI ''00 Proceedings of the 5th international conference on Intelligent user interfaces, pp. 106-112, 2000.
[19].S. Guha, R. Rastogi, K. Shim, “CURE: A Clustering Algorithm for Large Databases,” Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 73-84, 1998.
[20].W. Gaul, L.S. Thieme, “Mining Web Navigation Path Fragments,” Proceedings of the Workshop on Web Mining for E-Commerce, 2000.
[21].J. Han, Y. Cai, N. Cercone, “Knowledge Discovery in Databases: An Attribute-oriented Approach,” Proceedings of the 18th International Conference on Very Large Data Bases, pp. 547-559, 1992.
[22].C.C. Hsieh, C.Y. Chang, “An Enhanced Transaction Identification Module on Web Usage Mining,” Asia Pacific Management, pp. 241-252, 2001.
[23].H.C. Kum, J. Pei, W. Wang, D. Duncan, “ApproxMAP: Approximate Mining of Consensus Sequential Patterns,” 3rd SIAM International Conference on Data Mining (SDM), pp. 311-315, 2003.
[24].M.Y. Lin, S.Y. Lee, “Fast Discovery of Sequential Patterns through Memory Indexing and Database Partitioning,” Journal of Information Science and Engineering 21, pp. 109-128, 2005.
[25].F. Masseglia, F. Cathala, P. Poncelet, “The PSP Approach for Mining Sequential Patterns,” Proceedings of 1998 European Symp. Principle of Data Mining and Knowledge Discovery (PKDD’98), pp. 176-184, 1998 .
[26].F. Masseglia, F. Poncelet, M. Teisseire, “Efficient Mining of Sequential Patterns with Time Constraints:Reducing the Combinations,” Expert Systems with Applications: An International Journal, pp. 2677-2690, 2009.
[27].R.T. Ng, J. Han, “Efficient and Effective Clustering Methods for Spatial Data Mining,” Proceedings of the VLDB Conference, pp. 144-155, 1994.
[28].S. Orlando, R. Perego, C. Silvestri, “A New Algorithm for Gap Constrained Sequence Mining,” Symposim on Applied Computing(SAC’04), pp. 540-547, 2004.
[29].J.S. Park, M.S. Chen, P.S. Yu, “An Effective Hash Based Algorithm for Mining Association Rules,” Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 175-186, 1995.
[30].J. Pei, J. Han, B. Mortazavi-Asl, H. Zhu, “Mining Access Pattern Efficiently from Web Logs,” Knowledge Discovery and Data Mining(KDD’00), pp. 396-407, 2000.
[31].J. Pei, J. Han, B. Mortazavi-Asl, J. Wang, H. Pinto, Q. Chen, U. Dayal and M.C. Hsu, “Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach,” IEEE Transactions on Knowledge and Data Engineering 16, pp. 1424-1440, 2004.
[32].C. Raïssi, T. Calders, P. Poncelet, “Mining Conjunctive Sequential Patterns,” Data Mining and Knowledge Discovery, pp.77-93, 2008.
[33].R. Srikant, R. Agrawal, “Mining Sequential Patterns: Generalizations and Performance Improvements,” International Conference Extending Database Technology, pp. 3-17, 1996.
[34].C. Shahabi, A.M. Zarkesh, J. Adibi, V. Shah, “Knowledge Discovery from Users Web-page Navigation,” Proceedings of the Seventh International Workshop on Data Engineering, pp. 20-29, 1997.
[35].J. Srivastava, R. Cooley, M. Deshpande, P.N. Tan, “Web Usage Mining: Discovery and Applications of Usage Patterns from Web Data,” SIGKDD Explorations, pp. 12-23, 2000.
[36].M.E. Sayed, C. Ruiz, E.A. Rundensteiner, “FS-Miner: Efficient and Incremental Mining of Frequent Sequence Patterns in Web logs,” WIDM’04, pp. 128-135, 2004.
[37].M.L. Shyu, C. Haruechaiyasak, S.C. Chen, “Mining User Access Patterns with Traversal Constraint for Predicting Web Page Requests,” Knowledge and Information Systems, pp. 515-528, 2006.
[38].V.S. Tseng, K.W. Lin, “Efficient Mining and Prediction of User Behavior Patterns in Mobile Web Systems,” Information and Software Technology 48, pp. 357-369, 2006.
[39].J. Wang, J. Han, “BIDE: Efficient Mining of Frequent Closed Sequences,” Proceedings of the Twentieth International Conference on Data Engineering, pp. 79–90, 2004.
[40].Y. Xu, Z. Ma, L. Li, “Effective Pruning Strategies for Sequential Pattern Mining,” Workshop on Knowledge Discovery and Data Mining, pp. 21-24, 2008.
[41].C.H. Yun, M.S. Chen, “Mining Mobile Sequential Patterns in a Mobile Commerce Environment,” IEEE Transactions on Systems, Man, and Cybernetics, pp. 278-295, 2007.
[42].U. Yun, “A New Framework for Detecting Weighted Sequential Patterns in Large Sequence Databases,” Knowledge-Based Systems 21, pp. 110-122, 2008.
[43].M. Zaki, “SPADE: An Efficient Algorithm for Mining Frequent Sequences,” Machine Learning 40, pp. 31-60, 2001.
[44].B. Zhou, S.C. Hui, A.C.M. Fong, “Efficient Sequential Access Pattern Mining for Web Recommendations”, International Journal of Knowledge-Based and Intelligent Engineering Systems, pp. 155-168, 2006.