請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/22794
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 李瑞庭(Jui-Ting Lee) | |
dc.contributor.author | Wen-Kwang Tsao | en |
dc.contributor.author | 曹文光 | zh_TW |
dc.date.accessioned | 2021-06-08T04:28:27Z | - |
dc.date.copyright | 2010-02-04 | |
dc.date.issued | 2010 | |
dc.date.submitted | 2010-01-29 | |
dc.identifier.citation | [1] R. Agrawal, R. Srikant, Fast algorithms for mining association rules, Proceedings of the International Conference on Very Large Data Bases, Santiago, Chile, 1994, pp. 487-499.
[2] R. Agarwal, C. Aggarwal, V. Prasad, A tree projection algorithm for generation of frequent itemsets, Parallel and Distributed Computing, 2001. [3] R. Agrawal, R. Srikant, Fast algorithms for mining association rules, Proceedings of the International Conference on Very Large Data Bases, Santiago, Chile, 1994, pp. 487-499. [4] R. Agrawal, R. Srikant, Mining sequential patterns, Proceedings of the International Conference on Data Engineering, Taipei, Taiwan, 1995, pp. 3-14. [5] H. Arimura, Takeaki Uno, Shinichi Shimozono, Time and space efficient discovery of maximal geometric graphs, LNCS (LNAI), Vol. 4755, Springer, Heidelberg, 2007, pp. 42-55. [6] R.J. Bayardo. Jr, Efficiently mining long patterns from databases, Proceeding of the 1998 ACM-SIGMOD International Conference on Management of Data, Seattle,WA 1998, pp. 85-93. [7] M. Boley, T. Horvath, A. Poigne, S. Wrobel, Efficient closed pattern mining in strongly accessible set systems (extended abstract), Proceedings of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases, 2007, pp. 382-389. [8] D. Burdick, M. Calimlim, J. Gehrke, MAFIA: A maximal frequent itemset algorithm for transactional databases, Proceedings of the 17th International Conference on Data Engineering, 2001, pp. 443-452. [9] J. Cheng, Y. Ke, W. Ng, δ-tolerance closed frequent itemsets, Proceedings of the IEEE International Conference on Data Mining, Hong Kong, China, 2006, pp. 139-148. [10] J.D. Chung, O.H. Paek, J.W. Lee, K.H. Ryu, Temporal moving pattern mining for location-based service, Proceedings of the International Conference on Database and Expert Systems Applications, Aix-en-Provence, France, 2002, pp. 331-340. [11] G.L. Foresti, L. Marcenaro, C.S. Regazzoni, Automatic detection and indexing of video-event shots for surveillance application, IEEE Transactions on Multimedia, Vol. 4, No. 4, 2002, pp. 459-471. [12] F. Giannotti, D. Pedreschi, Mobility, Data Mining and Privacy, Springer Publishing Company, New York, 2008. [13] F. Giannotti, M. Nanni, F. Pinelli, D. Pedreschi, Trajectory pattern mining, Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, California, USA, 2007, pp. 330-339. [14] G. Grahne, J. Zhu, Fast algorithms for frequent itemset mining using FP-trees, IEEE Transactions on Knowledge and Data Engineering Vol. 17, No. 10, 2005, pp. 1347-1362. [15] G. Grahne, J. Zhu, Efficiently using prefix-trees in mining frequent itemsets, Proceedings of the IEEE ICDM Workshop in Frequent Itemset Mining Implementations, 2003, pp. 123-132. [16] E. Gudes, E. Shimony N. Vanetik, Discovering frequent graph patterns using disjoint paths, IEEE Transactions on Knowledge and Data Engineering Vol. 18 No. 11, 2006, pp.1441-1456. [17] J. Han, J. Wang, Y. Lu, P. Tzvetkov, Mining top-k frequent closed patterns without minimum support, Proceedings of the IEEE International Conference on Data Mining, Maebashi City, Japan, 2002, pp. 211-218. [18] J. Han, J. Pei, Y. Yin, R. Mao, Mining frequent patterns without candidate generation: A frequnet-pattern tree approach, Data Mining and Knowledge Discovery, 2004, pp. 53-87. [19] J. Han, M. Kamber, Data Mining: Concept and Techniques, second edition, Morgan Kaufmann Publishers, San Francisco, CA, U.S.A , 2006. [20] R.M. Haralick, K. Shanmugam, I.Dinstein, Texture features for image classification, IEEE Transaction on Systems Man Cyber net. Vol. 3, No. 6, 1973, pp. 610-621. [21] W. Hsu, M.L. Lee, J.Zhang, Image mining: trends and developments, Intelligent Information Systems, Vol. 19, No.1, 2002, pp. 7–23. [22] J. Huan, W. Wang, J. Prins, Efficient mining of frequent subgraphs in the presence of isomorphism, Proceedings of the IEEE International Conference on Data mining, 2003, pp. 549-552. [23] J. Huang, R. Zabih, Combining color and spatial information for content-based image retrieval, Proceeding of European Conference on Digital Libraries, 1998, pp. 234-270. [24] S.Y. Hwang, Y.H. Liu, J.K. Chiu, E.P. Lim, Mining mobile group patterns: a trajectory-based approach, Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining, Hanoi, Vietnam, 2005, pp. 713-718. [25] A. Inokuchi, T. Washio, H. Motoda, An Apriori-based algorithm for mining frequent substructures from graph data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, Lyon, France, 2000, pp. 13-23. [26] R. Jin, C. Wang, D. Polshakov, S. Parthasarathy, G. Agarwal, Discovery frequent topological structures from graph datasets, Proceeding of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, USA, 2005, pp. 606-611. [27] R.A. Joyce, B. Liu, Temporal segmentation of video using frame and histogram space, IEEE Transactions on Multimedia, Vol. 8, No. 1, 2006, pp.130-140. [28] M. Kuramochi, G. Karypis, Frequent subgraph discovery, Proceedings of the IEEE International Conference on Data Mining, California, USA, 2001, pp. 313-320. [29] M. Kuramochi, G. Karypis, Discovering frequent geometric subgraphs, Information Systems, Vol. 32, 2007, pp. 1101-1120. [30] A.J.T. Lee, R.W. Hong, W.M. Ko, W.K. Tsao, H.H. Lin, Mining spatial association rules in image databases, Information Sciences, 2007, pp.1593-1608. [31] A.J.T. Lee, W.K. Tsao, P.Y. Chen, M.C. Lin, S.H. Yang, Mining frequent closed patterns in pointset databases, Information Systems, for the coming, 2010. [32] C. Lucchese, S. Orlando, R. Perego, Fast and memory efficient mining of frequent closed itemsets, IEEE Transactions on Knowledge and Data Engineering, Vol. 18, No. 1, 2006, pp. 21-36. [33] W.Y. Ma, B.S. Manjunath, A comparison of wavelet transform features for texture image annotation, Proceeding of IEEE International Conference on Image Processing, 1995. [34] A. Manzanera, J.C. Richefeu, A new motion detection algorithm based on [Sigma]-[Delta] background estimation, Pattern Recognition Letters in Advances in Visual information Processing, Special Issue of Pattern Recognition Letters on Advances in Visual Information Processing, Vol. 28, No. 3, pp. 320-328. [35] T.A. Monem, A.A. Oloufa, H. Mahgoub, Asphalt crack detection using thermography, Proceedings of the InfraMation Conference, 2005. [36] H.D.K. Moonesinghe, S. Fodeh, P-N. Tan, Frequent closed itemset mining using prefix graphs with an efficient flow-based pruning strategy, Proceedings of the IEEE International Conference on Data Mining, Hong Kong, China, 2006, pp. 426-435. [37] V.T.H. Nhan, J.H. Chi, K. H. Ryu, Discovery of spatiotemporal patterns in mobile environment, Proceedings of the Asia-Pacific Web Conference, Harbin, China, 2006, pp. 949-954. [38] J.S. Park, M.S. Chen, P.S. Yu, An effective hash-based algorithm for mining association rules, Proceedings of ACM SIGMOD International Conference on Management of Data, 1995, pp. 175-186. [39] N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Discovering frequent closed itemsets for association rules, Proceedings of the 7th International Conference on Database Theory, Jerusalem, Israel, 1999, pp. 398-416. [40] N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Discovering frequent closed itemsets for association rules, Proceedings of the 5th International Conference on Database Theory, 1999, pp. 398-416. [41] N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Efficient mining of association rules using closed itemset lattices, Information Systems, Vol. 24, No. 1, 1999, pp.25-46. [42] J. Pei, J. Han, R. Mao, CLOSET: an efficient algorithm for mining frequent closed itemsets, Proceedings of the 5th ACM-SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, Dallas, USA, 2000, pp. 11-20. [43] W. Rena, S.Singhb, M.Singhb, Y.S.Zhua, State-of-the-art on spatio-temporal information-based video retrieval, Pattern Recognition, Vol. 42, 2009, pp 267-282. [44] A. Savasere, E. Omiecinski, S. Navathe An efficiant algorithms for mining association rules in large database, Proceedings of the 21th International Conference of Very Large Data Bases 1995, pp. 432-444. [45] N.G. Singh, S.R. Singh, A.K. Mahanta, closeMiner: discovering frequent closed itemsets using frequent closed tidsets, Proceedings of the IEEE International Conference on Data Mining, Houston, USA, 2005, pp. 633-636. [46] M. Stricker, A. Dimai, Color indexing with weak spatial constraints, Proceeding of Storage and Retrieval for Image and Video Databases IV, SPIE, Vol. 2670, 1996, pp. 29-40. [47] W.K. Tsao, A.J.T. Lee, Y.H. Liu, T.W. Chang, H.H. Lin, A data mining approach to face detection, Pattern Recognition, Vol. 43, No. 3, 2010, pp. 1039-1049. [48] I. Tsoukatos, D. Gunopulos, Efficient mining of spatiotemporal patterns, Proceedings of the International Symposium on Advances in Spatial and Temporal Databases, Redondo Beach, CA, USA, 2001, pp. 425-442. [49] T. Uno, T. Asai, Yuzo. Uchida, H. Arimura, An efficient algorithm for enumerating closed patterns in transaction databases, Proceedings of the 7th International Conference on Discovery Science, Padova, Italy, 2004, pp. 16-31. [50] J. Wang, J. Han, J. Pei, CLOSET+: searching for the best strategies for mining frequent closed itemsets, Proceedings of the International Conference on Knowledge Discovery and Data Mining, Washington, D.C., USA, 2003, pp. 236-245. [51] S. B. Yahia, T. Hamrouni, E. M. Nguifo, Frequent closed itemset based algorithms: A thorough structural and analytical survey, ACM SIGKDD Explorations Newsletter, Vol. 8, No. 1, 2006, pp. 93-104. [52] X. Yan, J. Han, gSpan: graph-based substructure pattern mining, Proceedings of the IEEE International Conference on Data Mining, Maebashi City, Japan, 2002, pp. 721-724. [53] M.J. Zaki, K. Gouda, Fast vertical mining using diffsets, Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, D.C., USA, 2003, pp. 326-335. [54] M.J. Zaki, C-J. Hsiao, Efficient algorithms for mining closed itemsets and their lattice structure, IEEE Transactions on Knowledge and Data Engineering, Vol. 17 No. 4 , 2005, pp. 462-478. [55] F. Zhu, X. Yan, J. Han, P. Yu, H. Cheng Mining colossal frequent patterns by core pattern fusion, Proceedings of the IEEE International Conference on Data Engineering, 2007, pp 706-715. [56] WIKI, Introduction to Ampelmännchen, available at http://en.wikipedia.org/wiki /Ampelmännchen, accessed 21 November 2009. [57] WIKI, Mathematical morphology, available at http://en.wikipedia.org/wiki/ Mathematical_morphology, accessed 21 November 2000. [58] WIKI, Signal-to-noise ratio, available at http://en.wikipedia.org/wiki/ Signal-to-noise_ratio, accessed 21 November 2000. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/22794 | - |
dc.description.abstract | 本論文提出一個新的資料表示方式與三種探勘頻繁樣式的演算法:MaxFSP、PCP 及CVP。MaxFSP演算法從二維點集合資料庫中探勘最大頻繁空間樣式;PCP演算法從二維點集合資料庫中探勘封閉性頻繁空間樣式;CVP演算法則從視訊點集合資料庫中探勘封閉性頻繁時空樣式。在MaxFSP 及PCP 演算法中,我們除了運用Apriori 演算法所提出之反單調修剪原則,修剪不可能的候選樣式外,我們還針對空間關係的特性,提出快速修剪方法。並參考MAFIA與CHARM演算法,各別加入最大頻繁樣式與封閉性頻繁樣式所需的修剪方法。透過這些方法,我們可以在探勘過程中有效刪除不可能的候選樣式。CVP演算法更進一步考慮了時間軸上的關係,探勘視訊資料庫中封閉性頻繁時空樣式。CVP 演算法除了應用了空間中修剪方法之外,並提出「快速成長」(fast-grow)的策略,可有效地在樣式索引樹中標示不須延展的節點,進而避免重複檢查的運算,減少耗時的候選樣式產生時間。實驗結果顯示,MaxFSP 演算法的執行效率優於改良式的MAFIA演算法;PCP演算法的執行效率優於改良式的Apriori演算法、SASMiner演算法與MaxGeo演算法;CVP演算法的執行效率優於改良式的Apriori演算法。 | zh_TW |
dc.description.abstract | In this dissertation, we propose a novel data representation and three algorithms, MaxFSP, PCP, and CVP algorithms. The MaxFSP algorithm is proposed to find the maximal frequent spatial patterns in image databases. The PCP algorithm is designed to find the frequent closed spatial patterns in image databases. The CVP algorithm is developed to find the frequent closed spatial-temporal patterns in video databases. In the MaxFSP and PCP algorithms, in addition to using the anti-monotone pruning strategy to prune unnecessary candidate patterns, we utilize the characteristics of the spatial relationships to design the pruning strategies. Specifically, we design pruning strategies based on the MAFIA and CHARM algorithms respectively to prune non-maximal and non-closed candidates. By using these strategies, we can prune a large number of unnecessary candidate patterns. The CVP algorithm is further considering temporal information to mine all frequent closed spatial-temporal patterns in video databases. In the CVP algorithm, we not only use the spatial relationship to prune unnecessary candidate patterns, we also propose a fast-grow pruning strategy, which can speed up the mining process in the temporal dimension. Therefore, the CVP algorithm can effectively prune the unnecessary branches in the frequent pattern tree and avoid the costly candidates’ generation. The experimental results show that the MaxFSP algorithm outperforms the modified MAFIA algorithm; the PCP algorithm outperform the modified Apriori, SASMiner, and MaxGeo algorithms; and the CVP algorithm outperform the modified Apriori algorithm | en |
dc.description.provenance | Made available in DSpace on 2021-06-08T04:28:27Z (GMT). No. of bitstreams: 1 ntu-99-D93725001-1.pdf: 1352976 bytes, checksum: bac1e15ae77f31a65870db993bb0c2a0 (MD5) Previous issue date: 2010 | en |
dc.description.tableofcontents | Table of Contents i
List of Figures iii List of Tables vi Chapter 1 Introduction 1 1.1 Motivations 1 1.2 Contributions 4 1.3 Dissertation Layout 5 Chapter 2 Literature Survey 6 2.1 Frequent Itemset Mining 6 2.2 Frequent Closed Pattern Mining 7 2.3 Maximal Frequent Itemset Mining 9 2.4 Frequent Graph Mining 9 2.5 Spatial and Temporal Pattern Mining 10 2.6 Discussion 10 Chapter 3 Mining Maximal Frequent Spatial Patterns 12 3.1 Preliminary Concepts and Problem Definitions 12 3.2 Frequent Spatial Pattern Enumeration 14 3.3 Pruning Strategies 20 3.4 The MaxFSP Algorithm 21 3.5 An Example 25 Chapter 4 Mining Frequent Closed Spatial Patterns 27 4.1 The Closure Checking and Pruning Strategies 27 4.2 The PCP Algorithm 29 4.3 An Example 33 Chapter 5 Mining Frequent Closed Spatial-Temporal Patterns 36 5.1 Preliminary Concepts and Problem Definitions 36 5.2 CV-tree and Joinable Class 38 5.3 Pruning Strategies 42 5.4 The CVP Algorithm 45 5.5 An Example 49 Chapter 6 Performance Analysis 52 6.1 Synthetic Datasets 52 6.2 Performance Evaluation on the MaxFSP Algorithm 53 6.3 Performance Evaluation on the PCP Algorithm 58 6.4 Performance Evaluation on the CVP Algorithm 65 Chapter 7 Conclusions and Future Work 74 References 78 | |
dc.language.iso | en | |
dc.title | 點集合資料庫之時空樣式探勘 | zh_TW |
dc.title | Mining Spatial and Temporal Patterns in Pointset Databases | en |
dc.type | Thesis | |
dc.date.schoolyear | 98-1 | |
dc.description.degree | 博士 | |
dc.contributor.oralexamcommittee | 陳建錦(Chien-Chin Chen),諶家蘭(Jia-Lang, Seng),魏志平(C. Wei),呂永和(Yung-ho Leu) | |
dc.subject.keyword | 資料探勘,點集合資料庫,時空資料樣式, | zh_TW |
dc.subject.keyword | data mining,pointset databases,spatial-temporal patterns, | en |
dc.relation.page | 84 | |
dc.rights.note | 未授權 | |
dc.date.accepted | 2010-01-29 | |
dc.contributor.author-college | 管理學院 | zh_TW |
dc.contributor.author-dept | 資訊管理學研究所 | zh_TW |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 1.32 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。