Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/32655
|
| Title: | 應用在空間認知發展的學習歷程分析之高效率空間探勘演算法
Efficient Mining of Spatial Co-orientation Patterns for Analyzing Portfolios of Spatial Cognitive Development |
| Authors: | 魏綾音
WEI, LING-YIN |
| Contributors: | 沈錳坤
SHAN, MAN-KWAN
魏綾音
WEI, LING-YIN |
| Keywords: | 空間認知
認知圖
空間資料探勘
時空資料探勘
Spatial Cognition
Cognitive Map
Spatial Data Mining
Spatio-temporal Data Mining |
| Date: | 2005 |
| Issue Date: | 2009-09-17 13:57:45 (UTC+8) |
| Abstract: | 空間認知(Spatial Cognition)指出人所理解的空間複雜度，也就是人與環境互動的過程中，經由記憶與感官經驗，透過內化與重建產生物體在空間的關係認知。認知圖(Cognitive Map)是最常被使用在評估空間認知。分析學生所畫的認知圖有助於老師們瞭解學生的空間認知能力，進而擬定適當的地理教學設計。我們視空間認知發展的學習歷程檔案是由這些認知圖所構成。隨著數位學習科技的進步，我們可以透過探勘認知圖的方式，探討空間認知發展的學習歷程檔案。因此，我們藉由透過圖像的空間資料探勘，分析學生空間認知發展的學習歷程。
空間資料探勘(Spatial Data Mining)主要是從空間資料庫或圖像資料庫中找出有趣且有意義的樣式。在論文中，我們介紹一種空間樣式(Spatial Co-orientation Pattern)探勘以提供空間認知發展學習歷程的分析。Spatial Co-orientation Pattern是指圖像資料庫中，具有共同相對方向關係的物體(Object)常一起出現。例如，我們可以從圖像資料庫中發現物體P常出現在物體Q的左邊，我們利用二維字串(2D String)來表示物體分佈在圖像中的空間方向關係。我們透過Pattern-growth的方法探勘此種空間樣式，藉由實驗結果呈現Pattern-growth的方法與過去Apriori-based的方法[14]之優缺點。
我們延伸Spatial Co-orientation Pattern的概念至時空資料庫(Spatio-temporal Database)，提出從時空資料庫中，探勘Temporal Co-orientation Pattern。Temporal Co-orientation Pattern是指Spatial Co-orientation Pattern隨著時間的變化。論文中，我們提出兩種此類樣式，即是Coarse Temporal Co-orientation Pattern與Fine Temporal Co-orientation Pattern。針對此兩種樣式，我們提出三階段(three-stage)演算法，透過實驗分析演算法的效率。
Spatial cognition means how human interpret spatial complexity. Cognitive maps are mostly used to test the spatial cognition. Analyzing cognitive maps drawn by students is helpful for teachers to understand students’ spatial cognitive ability and to draft geography teaching plans. Cognitive maps constitute the portfolios of spatial cognitive development. With the advance of e-learning technology, we can analyze portfolios of spatial cognitive development by spatial data mining of cognitive images. Therefore, we can analyze portfolios of spatial cognitive development by spatial data mining of images.
Spatial data mining is an important task to discover interesting and meaningful patterns from spatial or image databases. In this thesis, we investigate the spatial co-orientation patterns for analyzing portfolios of spatial cognitive development. Spatial co-orientation patterns refer to objects that frequently occur with the same spatial orientation, e.g. left, right, below, etc., among images. For example, an object P is frequently left to an object Q among images. We utilize the data structure, 2D string, to represent the spatial orientation of objects. We propose the pattern-growth approach for mining co-orientation patterns. An experimental evaluation with synthetic datasets shows the advantages and disadvantages between pattern-growth approach and Apriori-based approach proposed by Huang [14].
Moreover, we extend the concept of spatial co-orientation pattern to that of temporal patterns. Temporal co-orientation patterns refer to the change of spatial co-orientation patterns over time. Two temporal patterns, the coarse temporal co-orientation patterns and fine temporal co-orientation patterns are introduced to be extracted from spatio-temporal databases. We propose the three-stage algorithms, CTPMiner and FTPMiner, for mining coarse and fine temporal co-orientation patterns, respectively. An experimental evaluation with synthetic datasets shows the performance of these algorithms. |
| Reference: | [1] R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules,” Proc. of 20th International Conference on Very Large Data Bases VLDB, 1994.
[2] R. Agrawal and R. Srikant, “Mining Sequential Patterns,” Proc. of 7th IEEE International Conference on Data Engineering ICDE, 1995.
[3] J. F. Allen and G. Ferguson, “Actions and Events in Interval Temporal Logic,” Journal of Logic and Computation, 4(5):531-579, 1994.
[4] S. K. Chang, Q. Y. Shi, and C. W. Yan, “Iconic Indexing by 2D Strings,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 9, No. 3, 1987.
[5] R. M. Downs and D. Stea, “Cognitive Maps and Spatial Behavior: Process and Products,” R. M. Downs and D. Stea (Eds), Image and Environment. Chicago, Aldine Publishing Company, pp. 8-26, 1973.
[6] M. Ester, A. Frommelt, H. Kriegel, and J. Sander, “Spatial Data Mining: Database Primitives, Algorithms and Efficient DBMS Support,” Data Mining and Knowledge Discovery, Vol 4, No. 2/3, 2000.
[7] J. Gudmundsson, M. Kreveld, and B. Speckmann, “Efficient Detection of Motion Patterns in Spatio-Temporal Data Sets,” Proc. of 12th ACM International Workshop on Geographic Information Systems ACMGIS, 2004.
[8] J. Han, J. Pei, B. Mortazavi-Asl, Q. Chen, U. Dayal, and M. C. Hsu, “FreeSpan: Frequent Pattern-Projected Sequential Pattern Mining,” Proc. of 6th ACM International Conference on Knowledge Discovery and Data Mining SIGKDD, 2000.
[9] R. A. Hart and G. T. Moore, “The Development of Spatial Cognition: A Review,” R. M. Downs and D. Stea (Eds), Image and Environment. Chicago, Aldine Publishing Company, pp. 246-248, 1973.
[10] R. M. Haynes, Geographical Images and Mental Maps, Macmillan Education, 1980.
[11] M. Hsu, “The Cognitive Development of Primary School Students in Two Spatial Elements - Direction and Location (II) A Study of Cognitive Development of North, East, South and West Direction at Middle Grade Students of Primary School,” Journal of National Taipei University of Education, 26:213-244, 1995.
[12] M. Hsu, G. Teng, J. Zhuo, K. Lee, and J. Yin, “The Cognitive Development of Primary School Students in Two Spatial Elements - Direction and Location,” Journal of National Taipei University of Education, 25:91-120, 1994.
[13] W. Hsu, J. Dai, and M. Lee, “Mining Viewpoint Patterns in Image Databases,” Proc. of 9th ACM International Conference on Knowledge Discovery and Data Mining SIGKDD, 2003.
[14] Y. C. Huang, “Mining Frequent Spatial Co-relation Pattern,” Master Thesis, Department of Computer Science, National Chengchi University, Taiwan, 2004.
[15] Y. Huang, S. Shekhar, and H. Xiong, “Discovering Co-location Patterns from Spatial Datasets: A General Approach,” IEEE Transactions on Knowledge and Data Engineering, Vol. 16, No. 12, 2004.
[16] S. Hwang, Y. Liu, J. Chiu, and E. Lim, “Mining Mobile Group Patterns: A Trajectory-Based Approach,” Proc. of 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining PAKDD, 2005.
[17] K. Koperski, J. Adhikary, and J. Han, “Spatial Data Mining: Progress and Challenges Survey paper,” Proc. of ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery DMKD, 1996.
[18] P. Laube and S. Imefeld, “Analyzing Relative Motion within Groups of Trackable Moving Point Objects,” MJ Egenhofer and DM Mark (Eds.), GIScience 2002, Boulder, CO, USA, Springer-Verlag Berlin Heidelberg, pp. 132–144, 2002.
[19] J. Lin, “A Study on Middle School Students’ Differences of Spatial Cognition through Mapping,” Master Thesis, Department of Geography, National Taiwan University, 2003.
[20] M. Y. Lin, S. C. Hsueh, and C. W. Chang, “Fast Discovery of Time-constrained Sequential Patterns,” Proc. of 2nd Advanced Data Mining and Applications, 2006.
[21] C. N. Liu, “Mining Painting Color Style from Fine Arts,” Master Thesis, Department of Computer Science, National Chengchi University, Taiwan, 2003.
[22] K. Loperski and J. Han, “Discovery of Spatial Association Rules in Geographic Information Databases,” Proc. of 4th International Symposium on Large Spatial Databases, 1995.
[23] Y. Lu, “Constructing Cognitive Map: The Involvement of Direction and Distance,” Master Thesis, Department of Psychology, National Chung Cheng University, 1996.
[24] N. Mamoulis, H. Cao, G. Kollios, M. Hadjieleftheriou, Y. Tao, and D. W. Cheung, “Mining, Indexing, and Querying Historical Spatiotemporal Data,” Proc. of 10th ACM International Conference on Knowledge Discovery and Data Mining SIGKDD, 2004.
[25] D. M. Mark, “Human Spatial Cognition,” D. Medyckyj-Scott and H. M. Hearnshaw (Eds.), Human Factors in Geographical Information Systems, pp.51-60, 1993.
[26] D. R. Montello, “Spatial Cognition,” N. J. Smelser and P.B. Baltes (Eds.), International Encyclopedia of the Social and Behavioral Sciences, 2001.
[27] Y. Morimoto, “Mining Frequent Neighboring Class Sets in Spatial Databases,” Proc. of 7th ACM International Conference on Knowledge Discovery and Data Mining SIGKDD, 2001.
[28] R. Munro, S. Chawla, and P. Sun, “Complex Spatial Relationships,” Proc. of 3th IEEE International Conference on Data Mining ICDM, 2003.
[29] K. Okamoto, K. Okunuki, and T. Takai, “Sketch Map Analysis Using GIS Buffer Operation,” Spatial Cognition, pp. 227-244, 2004.
[30] Z. Ou-yang, “Spatial Conception Development in School-Children,” Master Thesis, Department of Geography, National Taiwan Normal University, 1982.
[31] P. Papapetrou, G. Kollios, S. Sclaroff, and D. Gunopulos, “Discovering Frequent Arrangements of Temporal Intervals,” Proc. of 5th IEEE International Conference on Data Mining ICDM, 2005.
[32] J. Pei, J. Han, B. Mortazavi-Asl, J. Wang, H. Pinto, and Q. Chen, “Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach,” IEEE Transactions on Knowledge and Data Engineering, Vol. 16, No. 11, 2004.
[33] S. Rinzivillo and F. Turini, “Extracting Spatial Association Rules from Spatial Transactions,” Proc. of 13th ACM International Workshop on Geographic Information Systems ACMGIS, 2005.
[34] J. F. Roddick, M. J. Egenhofer, E. Hoel, and D. Papadias, “Spatial, Temporal and Spatio-Temporal Databases – Hot Issues and Directions for PhD Research,” ACM SIGMOD Record, Vol. 33, No. 2, 2004.
[35] L. K. Sharama, O. P. Vyas, U. S. Tiwary, and R. Vyas, “A Novel Approach of Multilevel Positive and Negative Association Rule Mining for Spatial Databases,” Proc. of 4th International Conference on Machine Learning and Data Mining MLDM, 2005.
[36] S. Shekhar and S. Chawla, Spatial Databases: A Tour, Prentice Hall, 2003.
[37] S. Shekhar and Y. Huang, “Discovering Spatial Co-location Patterns: A Summary of Results,” Proc. of 7th International Symposium on Spatial and Temporal Databases, 2001.
[38] R. Srikant and R. Agrawal, “Mining Sequential Patterns: Generalizations and Performance Improvements” Proc. of 5th International Conference on Extending Database Technology EDBT, 1996.
[39] F. Verhein and S. Chawla, “Mining Spatio-temporal Association Rules, Sources, Sinks, Stationary Regions and Thoroughfares in Object Mobility Databases,” Proc. of 11th International Conference on Database Systems for Advanced Applications DASFAA, 2006.
[40] J. Wang, W. Hsu, and M. L. Lee, “A Framework for Mining Topological Patterns in Spatio-temporal Databases,” Proc. of 14th ACM Conference on Information and Knowledge Management CIKM, 2005.
[41] J. Wang, W. Hsu, and M. L. Lee, “Mining Generalized Spatio-Temporal Patterns,” Proc. of 10th International Conference on Database Systems for Advanced Applications DASFAA, 2005.
[42] J. Wang, W. Hsu, M. L. Lee, and J. Wang, “FlowMiner: Finding Flow Patterns in Spatio-Temporal Databases,” Proc. of 16th IEEE International Conference on Tools with Artificial Intelligence ICTAI, 2004.
[43] J. R. Wang and N. Parameswaran, “Survey of Sports Video Analysis: Research Issues and Applications,” Proc. of 9th International Conference on Database Systems for Advanced Applications DASFAA, 2004.
[44] P. Wang, “Spatial Knowledge Acquisition by Junior High School Students,” Master Thesis, Department of Social Studies Education, National Taipei University of Education, 2004.
[45] Y. Wang, E. Lim, and S. Hwang, “On Mining Group Patterns of Mobile Users,” Proc. of 14th International Conference on Database and Expert Systems Applications DEXA, 2003.
[46] Y. Wang, E. Lim, and S. Hwang, “Efficient Group Pattern Mining Using Data Summarization,” Proc. of Pan-Sydney Area Workshop on Visual Information Processing VIP, 2004.
[47] H. Xiong, S. Shekhar, Y. Huang, V. Kumar, X. Ma, and J. S. Yoo, “A Framework for Discovering Co-location Patterns in Data Sets with Extended Spatial Objects,” Proc. of 4th SIAM International Conference on Data Mining SDM, 2004.
[48] J. S. Yoo and S. Shekhar, “A Partial Join Approach for Mining Co-location Patterns,” Proc. of 12th ACM International Workshop on Geographic Information Systems ACMGIS, 2004.
[49] The official site of the National Basketball Association, http://www.nba.com/. |
| Description: | 碩士
國立政治大學
資訊科學學系
93753015
94 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0093753015 |
| Data Type: | thesis |
| Appears in Collections: | [資訊科學系] 學位論文
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
