請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/64074完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 李瑞庭 | |
| dc.contributor.author | Chuan-Yuan Lin | en |
| dc.contributor.author | 林傳淵 | zh_TW |
| dc.date.accessioned | 2021-06-16T17:28:56Z | - |
| dc.date.available | 2015-08-27 | |
| dc.date.copyright | 2012-08-27 | |
| dc.date.issued | 2012 | |
| dc.date.submitted | 2012-08-15 | |
| dc.identifier.citation | [1] R. Agrawal and R. Srikant, Fast algorithms for mining association rules, Proceedings of the International Conference on Very Large Data Bases, 1994, pp. 487-499.
[2] M. Berlingerio, F. Bonchi, B. Bringmann, and A. Gionis, Mining graph evolution rules, Proceedings of European Conference on Principles and Practice of Knowledge Discovery in Databases, 2009, pp. 115-130. [3] C. Borgelt and M. R Berthold, Mining molecular fragments: Finding relevant substructures of molecules, Proceedings of IEEE International Conference on Data Mining, 2002, pp. 51-58. [4] K. M. Borgwardt, H. Kriegel, and P. Wackersreuther, Pattern mining in frequent dynamic subgraphs, Proceedings of IEEE International Conference on Data Mining, 2006, pp. 818-822. [5] N. Eagle, A. Pentland, and D. Lazer, Inferring social network structure using mobile phone data, Proceedings of the National Academy of Sciences, 2009, Vol. 106 (36), pp. 15274-15278. [6] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co, San Francisco, 1979. [7] J. Han, J. Pei, and Y. Yin, Mining frequent patterns without candidate generation, Proceedings of ACM SIGMOD Conference on Management of Data, 2000, pp. 1-12. [8] J. Huan, W. Wang, and J. Prins, Efficient mining of frequent subgraphs in the presence of isomorphism, Proceedings of IEEE International Conference on Data Mining, 2003, pp. 549-552. [9] A. Inokuchi and T. Washio, Mining frequent graph sequence patterns induced by vertices, Proceedings of SIAM Conference on Data Mining, 2010, pp. 466-477. [10] A. Inokuchi, T. Washio, and H. Motoda, An Apriori-based algorithm for mining frequent substructures from graph data, Proceedings of European Conference on Principles of Data Mining and Knowledge Discovery, 2000, pp. 13-23. [11] M. Kuramochi and G. Karypis, Frequent subgraph discovery, Proceedings of IEEE International Conference on Data Mining, 2001, pp. 313-320. [12] M. Lahiri and T. Y .Berger-Wolf, Mining periodic behaviour in dynamic social networks, Proceedings of IEEE International Conference on Data Mining, 2008, pp. 373-382. [13] S. Nijssen and J. N Kok, A quickstart in frequent structure mining can make a difference, Proceedings of European Conference on Principles of Data Mining and Knowledge Discovery, 2004, pp. 647-652. [14] N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal, Efficient mining of association rules using closed itemset lattices, Journal of Information Systems, Vol. 24, No. 1, 1999, pp. 25-46. [15] J. Pei, J Han, B Mortazavi-Asl, H Pinto, Q Chen, U Dayal, and M Hsu, PrefixSpan: Mining sequential patterns by prefix-projected growth, Proceedings of IEEE International Conference on Data Engineering, 2001, pp. 215-224. [16] C. Robardet, Constraint-based pattern mining in dynamic graphs, Proceedings of IEEE International Conference on Data Mining, 2009, pp. 950-955. [17] J. Wang and J. Han, BIDE: Efficient mining of frequent closed sequences, Proceedings of IEEE International Conference on Data Engineering, 2004, pp. 79-90. [18] X. Yan and J. Han, CloseGraph: Mining closed frequent graph patterns, Proceedings of ACM International Conference on Knowledge Discovery and Data Mining, 2003, pp. 286-295. [19] X. Yan and J. Han, gSpan: Graph-based substructure pattern mining, Proceedings of IEEE International Conference on Data Mining, 2002, pp. 721-724. [20] X. Yan, J. Han, and R. Afshar, CloSpan: Mining closed sequential patterns in large databases, Proceedings of SIAM Conference on Data Mining, 2003, pp. 166-177. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/64074 | - |
| dc.description.abstract | 在社群網站中，人們在某段時間中的互動關係可以用一個圖形來表示，其中，每個點代表一個人，兩點之間的邊代表人與人之間的互動關係。然而，點和邊會因為時間變化而有所不同，而這種會隨著時間改變的網路稱作動態網路。從動態網路中探勘頻繁樣式，可以幫助我們分析社群網站中的互動行為。因此，在這篇論文中，我們提出一個有效率的探勘演算法叫「SGP-Mine」，以找出在圖形資料庫中封閉性頻繁圖形序列樣式。SGP-Mine演算法主要可分成兩個階段。第一階段，我們先找出所有長度為一的頻繁樣式。在第二階段，我們以深度優先搜尋的方式遞迴產生所有的頻繁樣式。在產生的過程中，我們利用修剪策略刪除不必要的候選樣式，並用封閉性檢查移除非封閉性的樣式。因此，SGP-Mine能有效率地從圖形資料庫中找出封閉性頻繁圖形序列樣式。實驗結果顯示，不論在合成或真實資料庫中，我們所提出的方法皆優於改良式的Apriori演算法。 | zh_TW |
| dc.description.abstract | In social networks, a snapshot of interactions among users can be modeled by a graph, where a vertex stands for a user and an edge denotes an interaction between two users. The users and interactions may change over time and form a dynamic network. Mining sequential graph patterns from a dynamic network can help us analyze interaction behaviors on social networks. Therefore, in this thesis, we propose a novel algorithm, SGP-Mine (Sequential Graph Pattern-Mine), to mine the closed frequent sequential graph patterns in graph databases. The proposed algorithm consists of two phases. First, we use gSpan to find all frequent SGPatterns of length one (1-SGPatterns) from the database and record the occurrences for each 1-SGPattern found. Second, we recursively generate frequent SGPatterns in a DFS manner until no more frequent SGPatterns can be found. During the mining process, we employ three pruning strategies to prune unnecessary candidates and a closure checking scheme to eliminate non-closed patterns. Therefore, the proposed method can efficiently mine closed frequent sequential graph patterns in a graph database. The experiment results show the SGP-Mine algorithm outperforms the modified Apriori algorithm. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-16T17:28:56Z (GMT). No. of bitstreams: 1 ntu-101-R99725013-1.pdf: 592242 bytes, checksum: 05f37885b9e9a6f57d1682a0340bcf78 (MD5) Previous issue date: 2012 | en |
| dc.description.tableofcontents | List of Figures ii
List of Tables iii Chapter 1 Introduction 1 Chapter 2 Related Work 4 Chapter 3 Preliminary Concepts and Problem Definitions 7 Chapter 4 The Proposed Algorithm 12 4.1 Frequent GPattern generation 12 4.2 Frequent SGPattern generation 13 4.3 Pruning strategies and closure checking 14 4.4 The SGP-Mine algorithm 14 4.5 An example 18 Chapter 5 Performance Analysis 20 5.1 Synthetic datasets 20 5.2 Performance evaluation on synthetic datasets 21 5.3 Performance evaluation on the real dataset 24 Chapter 6 Conclusions and Future Work 28 References 30 | |
| dc.language.iso | zh-TW | |
| dc.subject | 資料探勘 | zh_TW |
| dc.subject | 圖形序列樣式 | zh_TW |
| dc.subject | 動態網路 | zh_TW |
| dc.subject | dynamic networks | en |
| dc.subject | sequential graph patterns | en |
| dc.subject | data mining | en |
| dc.title | 圖形資料庫中封閉性頻繁圖形序列樣式之資料探勘 | zh_TW |
| dc.title | Mining Closed Frequent Sequential Graph Patterns in Graph Databases | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 100-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 陳建錦,盧信銘 | |
| dc.subject.keyword | 動態網路,圖形序列樣式,資料探勘, | zh_TW |
| dc.subject.keyword | dynamic networks,sequential graph patterns,data mining, | en |
| dc.relation.page | 31 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2012-08-16 | |
| dc.contributor.author-college | 管理學院 | zh_TW |
| dc.contributor.author-dept | 資訊管理學研究所 | zh_TW |
| 顯示於系所單位： | 資訊管理學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-101-1.pdf 未授權公開取用 | 578.36 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。