Title page for 88423038


[Back to Results | New Search]

Student Number 88423038
Author Hung-Ping Kao(高鴻斌)
Author's Email Address No Public.
Statistics This thesis had been viewed 1834 times. Download 1010 times.
Department Information Management
Year 2000
Semester 2
Degree Master
Type of Document Master's Thesis
Language zh-TW.Big5 Chinese
Title 於不循環有向圖結構的資料中進行樣式探勘-以樹狀結構樣式為例
Date of Defense 2001-07-09
Page Count 52
Keyword
  • Data Mining
  • Directed Acyclic Graph
  • Abstract 圖型結構的資料可以表現出記錄間交互影響的關系和其他豐富的資訊,如生物特徵交互影響,各股之間連動因素,社群中個體之間的關聯等,而在抽象的概念層次上,我們可以利用「不循環有向圖(Directed Acyclic Graph, DAG)」來表達這種資料所具有的圖型結構,對於這種資料,我們稱之為「DAG結構資料(DAG-Structured Data)」,如果能夠在DAG結構資料中找到有趣的子結構 - 「DAG結構樣式(DAG-Structured Pattern)」,這些子結構將有助於分析、解釋整體資料的特性,也可以用來預測和推論同類的資料,而本文的目的就是要研究於DAG結構資料中尋找DAG結構樣式的問題,一方面我們會定義DAG結構樣式探勘問題,另一方面我們提出一個探勘方法以尋找Pyramid Pattern與Inversed Pyramid Pattern這兩種特殊結構的樣式,最後再透過實作與測試該探勘系統以證明本文提出的架構與方法的可用性。
    Table of Content 1.緒論
    1.1.相關研究
    1.1.1.資料的順序性研究
    1.1.2.資料的結構性研究
    1.2.研究動機與論文架構
    2.DAG結構資料的探勘問題
    2.1.DAG結構資料
    2.2.DAG結構樣式
    2.3.DAG結構規則
    3.DAG結構資料的探勘
    3.1.探勘目標與挑戰
    3.2.探勘程序
    3.2.1.DAG結構資料的準備工作
    3.2.2.頻繁特徵集合的探勘
    3.2.3.過濾不必要的資料
    3.2.4.線型的DAG結構樣式的探勘
    3.2.5.樹狀的DAG結構樣式的探勘
    4.效能
    4.1.模擬資料的產生
    4.2.效能測試
    4.2.1.測試一
    4.2.2.測試二
    4.2.3.測試三
    4.2.4.測試四
    5.結論
    參考文獻
    Reference [ABS99]R. Agrawal, R. J. Bayardo Jr. and R. Srikant., "Athena: Mining-based Interactive Management of Text Databases", IBM Research Report RJ10153, July 1999.
    [AFS93]R. Agrawal, C. Faloutsos, A. Swami, "Efficient Similarity Search in Sequence Databases", Proc. of the 4th Int'l Conference on Foundations of Data Organization and Algorithms, Chicago, Oct. 1993, Also in Lecture Notes in Computer Science 730, Springer Verlag, 69-84, 1993.
    [ALSS95]R. Agrawal, K. Lin, H. S. Sawhney, K. Shim, "Fast Similarity Search in The Presence of Noise, Scaling, and Translation in Time-Series Databases," Proc. of the 21st Int'l Conference on Very Large Databases, Zurich, Switzerland, September 1995
    [AS94]R. Agrawal, R. Srikant. "Fast Algorithms for Mining Association Rules," Proc. of the 20th Int'l Conference on Very Large Databases, Santiago, Chile, Sept. 1994.
    [AS95]R. Agrawal, R. Srikant, "Mining Sequential Patterns," Proc. of the Int'l Conference on Data Engineering (ICDE), Taipei, Taiwan, March 1995. Expanded version available as IBM Research Report RJ9910, October 1994.
    [B95]R. J. Bayardo Jr., " Efficiently Mining Long Patterns from Databases," In Proc. of the 1998 ACM-SIGMOD Int'l Conf. on Management of Data, 85-93, 1998.
    [BM76]J. A. Bondy, U. S. R. Murty, "Graph Theory with Applications," American Elsevier Publishing Co., Inc., 33-47, 1976.
    [BMUT97]Sergey Brin, Rajeev Motwani, Jeffrey D. Ullman, Shalom Tsur. "Dynamic Itemset Counting and Implication Rules for Market Basket Data," SIGMOD Conference 1997, 255-264.
    [BWJL98]Bettini, C., Wang, X.S., Jajodia, S., Lin, J.L., "Discovering Frequent Event Patterns with Multiple Granularities in Time Sequences," IEEE Transactions on Knowledge and Data Engineering, Volume: 10 Issue: 2, 222 —237, March-April 1998.
    [CDAR97]S. Chakrabarti, B. Dom, R. Agrawal, P. Raghavan, "Using Taxonomy, Discriminants, and Signatures for Navigating in Text Databases", Proc. of the 23rd Int'l Conference on Very Large Data Bases, Athens, Greece, August 1997.
    [CH00]Cook, D.J., Holder, L.B.. "Graph-Based Data Mining," IEEE Intelligent Systems [see also IEEE Expert], Volume: 15 Issue: 2, 32 —41, March-April 2000.
    [CHY96]M.S. Chen, J. Han, and P.S. Yu, "Data Mining: An Overview from a Database Perspective," IEEE Transactions on Knowledge and Data Engineering, 8(6): 866-883, 1996.
    [CMS97a]Robert Cooley, Bamshad Mobasher, and Jaideep Srivastava, "Web Mining: Information and Pattern Discovery on The World Wide Web," (A Survey Paper) (1997), in Proceedings of the 9th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'97), November 1997.
    [CMS97b]Robert Cooley, Bamshad Mobasher, and Jaideep Srivastava, "Grouping Web Page References into Transactions for Mining World Wide Web Browsing Patterns," Proceedings of the 1997 IEEE Knowledge and Data Engineering Exchange Workshop (KDEX-97), November 1997.
    [CMS99]Robert Cooley, Bamshad Mobasher, and Jaideep Srivastava, "Data Preparation for Mining World Wide Web Browsing Patterns," Journal of Knowledge and Information Systems, Vol. 1, No. 1, 1999.
    [CPY98]M.S. Chen, J.S. Park and P.S. Yu, "Efficient Data Mining for Path Traversal Patterns," IEEE Trans. on Knowledge and Data Engineering, Vol. 10, No. 2, 209-221, April 1998.
    [CW99]Chen Enhong, Wang Xufa, "Semi-Structured Data Extraction and Schema Knowledge Mining," EUROMICRO Conference, 1999. Proceedings. 25th, Volume: 2, 310 —317, 1999.
    [FLW98]Ling Feng, Hongjun Lu, Allan Wong, "A Study of Database Buffer Management Approaches: Towards The Development of A Data Mining Based Strategy," 1998 IEEE International Conference on Systems, Man, and Cybernetics, Volume: 3, 1998.
    [FRM94]Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos, "Fast Subsequence Matching in Time-Series Databases," SIGMOD Conference 1994: 419-429.
    [J93]Richard J. Jrudeau. "Introduction to Graph Theory," NewYork: Dover Publications, Inc., 1993.
    [LAS97]B. Lent, R. Agrawal, R. Srikant, "Discovering Trends in Text Databases", Proc. of the 3rd Int'l Conference on Knowledge Discovery in Databases and Data Mining, Newport Beach, California, August 1997.
    [LC00]盧靜婷, 陳彥良, "在DAG中挖掘家族特微規則," 中央大學資訊管理系碩士論文, 民89.
    [LGFM00]Lee, J., Grossman, D., Frieder, O., McCabe, M.C., "Integrating Structured Data And Text: A Multi-Dimensional Approach," Information Technology: Coding and Computing, 2000. Proceedings. International Conference on, 2000, 264 —269.
    [LL98]Ming-Yen Lin, Suh-Yin Lee, "Incremental Update on Sequential Patterns in Large Databases," Proceedings. Tenth IEEE International Conference on Tools with Artificial Intelligence, 24 —31, 1998.
    [LLZZ99]Xuemin Lin, Chengfei Liu, Yanchun Zhang, Xiaofang Zhou. "Efficiently Computing Frequent Tree-Like Topology Patterns in a Web Environment," Technology of Object-Oriented Languages and Systems, 1999. TOOLS 31. Proceedings, 1999.
    [LZO00]Lesh, N., Zaki, M.J., Oglhara, M., "Scalable Feature Mining for Sequential Data," IEEE Intelligent Systems, Volume: 15 Issue: 2, 48—56, March-April 2000.
    [M90]James A. McHugh, "Algorithmic graph theory," Englewood Cliffs, N.J.: Prentice Hall Inc., 1990.
    [MJHS96]B. Mobasher, N. Jain, E. Han and J. Srivastava, "Web Mining: Pattern Discovery from World Wide Web Transactions," Technical Report TR96-050, Department of Computer Science, University of Minnesota, 1996.
    [MTK99]Mannila, H.; Toivonen, H., Klemettinen, M., "Interactive exploration of interesting findings in the Telecommunication Network Alarm Sequence Analyzer (TASA)," Information and Software Technology, Volume: 41,Issue: 9, June 25, 1999, 557-567.
    [MTV97]Heikki Mannila, Hannu Toivonen, and A. Inkeri Verkamo.,"Discovery of frequent episodes in event sequences," Data Mining and Knowledge Discovery, 1(3): 259 -289, November 1997.
    [PCY97]J.-S. Park, M.-S. Chen and P. S. Yu. "Using a Hash-Based Method with Transaction Trimming for Mining Association Rules," IEEE Trans. on Knowledge and Data Engineering, Vol. 9, No. 5, 813-825, October 1997.
    [PHMZ00]J. Pei, J. Han, B. Mortazavi-Asl, and H. Zhu "Mining Access Pattern efficiently from Web logs,' Proc. 2000 Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD'00), Kyoto, Japan, April 2000.
    [PLC99]Park, S., Lee, D., Chu, W.W., "Fast Retrieval of Similar Subsequences in Long Sequence Databases," Proceedings. 1999 Workshop on Knowledge and Data Engineering Exchange, 60 —67, 1999.
    [R91]L. R. Roulds, "Graph Theory Applications," New York: Springer-Verlag, 171-173, 1991.
    [RCPP00]Ramirez, J.C.G.., Cook, D.J., Peterson, L.L., Peterson, D.M., "Temporal Pattern Discovery in Course-Of-Disease Data," IEEE Engineering in Medicine and Biology Magazine, Volume: 19 Issue: 4, 63 —71, July-Aug. 2000.
    [SI99]Sadakane, K.; Imai, H., "Text Retrieval by Using K-Word Proximity Search," Database Applications in Non-Traditional Environments, 1999. (DANTE '99). Proceedings. 1999 International Symposium on, 2000, 183 —188.
    [SKM00]Sartipi, K., Kontogiannis, K., Mavaddat, F. "A Pattern Matching Framework for Software Architecture Recovery and Restructuring," Program Comprehension, 2000. Proceedings. IWPC 2000. 8th International Workshop on, 2000, 37 —47.
    [SNGA99]Tsechansky Maytal Saar, Pliskin Nava, Rabinowitz Gadi, Porath Avi, "Mining Relational Patterns from Multiple Relational Tables," Decision Support Systems (27)1-2 (1999), 177-195.
    [SS99]Srinivasa, S., Spiliopoulou, M., "Modeling interactions based on consistent patterns," International Conference on Cooperative Information Systems, 92 —101, 1999.
    [SSC99]Shen, Li; Shen, Hong; Cheng, Ling. "New Algorithms for Efficient Mining of Association Rules," Information Sciences, Volume: 118, Issue: 1-4, 251-268, September 1999.
    [TM00]Feng Tao, Murtagh, K., "Towards Knowledge Discovery from WWW Log Data," Proceedings. International Conference on Information Technology: Coding and Computing, 302 —307, 2000.
    [WADJOGH99]Weiss, S.M., Apte, C., Damerau, F.J., Johnson, D.E., Oles, F.J., Goetz, T., Hampp, T., "Maximizing text-mining performance," IEEE Intelligent Systems [see also IEEE Expert], Volume: 14 Issue: 4, 63 —69, July-Aug 1999.
    [WCMSSZ94]Wang, J. T-L., Chirn, G. W., Marr, T. G., Shapiro, B., Shasha, D. and Zhang, K. "Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results," Proceedings of ACM SIGMOD, pp. 115-125, 1994.
    [WL00]Ke Wang, Huiqing Liu. "Discovering Structural Association of Semistructured Data," Knowledge and Data Engineering, IEEE Transactions on, Volume: 12 Issue: 3, 353 —371, May-June 2000.
    [YSJJFB00]Yi, B.K., Sidiropoulos, N.D., Johnson, T., Jagadish, H.V., Faloutsos, C., Biliris, A., "Online Data Mining for Co-Evolving Time Sequences," Proceedings. 16th International Conference on Data Engineering 2000, 13 —22.
    [Z98]Mohammed J. Zaki, "Efficient Enumeration of Frequent Sequences," 7th International Conference on Information and Knowledge Management, 68-75, Washington DC, November 1998.
    [ZLO99]Mohammed J. Zaki, Neal Lesh, Mitsunori Ogihara, "PlanMine: Predicting Plan Failures Using Sequence Mining," Artificial Intelligence Review, special issue on the Application of Data Mining, 1999.
    [ZPOL97]Mohammed J. Zaki, Srinivasan Parthasarathy, Mitsunori Ogihara, Wei Li. "New Algorithms for Fast Discovery of Association Rules," 3rd International Conference on Knowledge Discovery and Data Mining (KDD), 283-286, Newport, California, August, 1997.
    [ZXH98]O. R. Zaiane, M. Xin, J. Han, "Discovering Web Access Patterns and Trends by Applying OLAP and Data Mining Technology on Web Logs," Proc. Advances in Digital Libraries Conf. (ADL'98), Santa Barbara, CA, 19-29, April 1998.
    Advisor
  • Yen-Liang Chen(陳彥良)
  • Files
  • 88423038.pdf
  • approve immediately
    Date of Submission 2001-07-09

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have dissertation-related questions, please contact with the NCU library extension service section.
    Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.