Responsive image
博碩士論文 etd-0728107-170024 詳細資訊
Title page for etd-0728107-170024
論文名稱
Title
從空間時間資料庫挖掘移動群組
Discovering Moving Clusters from Spatial-Temporal Databases
系所名稱
Department
畢業學年期
Year, semester
語文別
Language
學位類別
Degree
頁數
Number of pages
63
研究生
Author
指導教授
Advisor
召集委員
Convenor
口試委員
Advisory Committee
口試日期
Date of Exam
2007-06-22
繳交日期
Date of Submission
2007-07-28
關鍵字
Keywords
空間時間資料庫、移動群組
Spatial-Temporal Databases, Moving Clusters
統計
Statistics
本論文已被瀏覽 6087 次,被下載 1982
The thesis/dissertation has been browsed 6087 times, has been downloaded 1982 times.
中文摘要
隨著電腦與通訊技術的進步,分析移動物件上的群集關係,近幾年逐漸吸引到各方的注意力。一個令人感到興趣的問題是找出移動群組,而移動群組裡的物件成員都必需在一起移動一段足夠長的時間。然而,一個移動群組因為每一個物件的目的地會有所不同,所以在一段時間之後,一個移動群組易於分裂拆散。為了能夠鑑別出一些移動群組,我們藉由明確的參數設定,進而定義正規的移動群組。接著我們以移動群組的定義為基礎,提出精確的方法來為這些移動物件做分群。而我們提出的方法將在兩種類型的資料情況下進行評估,分別為合成資料、潛在已知的資料。最後,我們藉由一整個實驗的評估與比較來驗證我們提出的方法。
Abstract
Owing to the advances of computer and communication technologies, clustering analysis on moving objects has attracted increasing attention in recent years. An interesting problem is to find the moving clusters composed of objects which move along for a sufficiently long period of time. However, a moving cluster inclines to break after some time because of the goal change in each individual object. In order to identify the set of moving clusters, we propose the formal definition of moving clusters with semantically clear parameters. Based on the definition, we propose delicate approaches to cluster moving objects. The proposed approaches are evaluated using data generated with and without underlying model. We validate our approaches with a through experimental evaluation and comparison.
目次 Table of Contents
CHAPTER 1 - Introduction 1
1.1 Background 1
1.2 Motivation 1
1.3 Organization of this thesis 3
CHAPTER 2 - Literature Review 4
2.1 Mobile Group Pattern Mining 4
2.2 Static Spatial Data Clustering 5
2.2.1 Partitioning Methods 6
2.2.2 Hierarchical Methods 6
2.2.3 Density-based Methods 7
2.2.4 Grid-based Methods 7
2.2.5 Evaluations of Spatial Clustering Methods 7
2.3 Spatial-Temporal Data Clustering 8
2.3.1 ST-DBSCAN 8
2.4 Moving Objects Clustering 9
2.4.1 Moving Objects Trajectories 9
2.4.2 Moving Clusters 10
2.4.3 Moving Micro-clusters 11
2.5 Moving Objects and Queries Clustering 13
2.5.1 Motion Model 13
2.5.2 The SCUBA Algorithm 14
CHAPTER 3 - Problem Statement 16
3.1 Object Movement Database 16
3.2 Cluster Validity 17
CHAPTER 4 - Our Approach 21
4.1 Time-point-clustering 21
4.2 Time-window-clustering 23
CHAPTER 5 - Performance Evaluation 28
5.1 Data Generation with a Underlying Model 28
5.2 Data Generation without Underlying Model 29
5.2.1 IBM City Simulator 29
5.2.2 Translation to Trajectory Data 30
5.3 Experimental Results on Data with Underlying Model 31
5.3.1 Parameter Settings 32
5.3.2 Quality 32
5.3.3 Summary 38
5.4 Experimental Results on Synthetic Data 38
5.4.1 Parameter Settings 38
5.4.2 Execution Time 38
5.4.3 Quality 43
5.4.4 Summary 47
CHAPTER 6 - Conclusions 49
6.1 Summary 49
6.2 Future Work 49
References 50
參考文獻 References
Agrawal, R., Gehrke, J., Gunopulos, D., & Raghavan, P. (2005). Automatic subspace clustering of high dimensional data. Data Mining and Knowledge Discovery, 11(1), 5-33.
Basch, J., Guibas, L. J., & Hershberger, J. (1999). Data structures for mobile data. Journal of Algorithms, 31(1), 1-28.
Birant, D., & Kut, A. (2006). An algorithm to discover spatial-temporal distributions of physical seawater characteristics and a case study in turkish seas. Journal of Marine Science and Technology, 11(3), 183-192.
Chudova, D., Gaffney, S., Mjolsness, E., & Smyth, P. (2003). Translation-invariant mixture models for curve clustering. Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, 79–88.
Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of 2nd international conference on Knowledge Discovery and Data Mining, 226-231.
Gafney, S., & Smyth, P. (1999). Trajectory clustering with mixtures of regression models. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 63-72.
Guha S., Rastogi R., & Shim K. (2001). Cure: An efficient clustering algorithm for large databases. Information Systems, 26, 35-58.
Hadjieleftheriou, M., Kollios, G., Gunopulos, D., & Tsotras, V. J. (2003). On-line discovery of dense areas in spatio-temporal databases. Proceedings of the 8th International Symposium on Spatial and Temporal Databases (SSTD) Conference, 306–324.
Halkidi, M., Batistakis, Y., & Vazirgiannis, M. (2001). On clustering validation techniques. Journal of Intelligent Information Systems, 17(2), 107-145.
Han, J., & Kamber, M. (2000). Data mining: Concepts and techniques. Morgan Kaufmann.
Hirano, S., & Tsumoto, S. (2003). An indiscernibility-based clustering method with iterative refinement of equivalence relations. Proceedings of the 7th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD), Cavtat-Dubrovnik, Croatia, September, 22-26.
Hirano, S., & Tsumoto, S. (2005). A clustering method for spatio-temporal data and its application to soccer game records. Proceedings of the Fifth International Conference on Hybrid Intelligent Systems, 3641, 612-621.
Kalnis, P., Mamoulis, N., & Bakiras, S. (2005). On discovering moving clusters in spatio-temporal data. Proceedings of the 9th International Symposium on Spatial and Temporal Databases, 364–381.
Kaufman, J., Myllymaki, J. & Jackson, J. (2001). City simulator V 2.0.
Kaufman, L., & Rousseeuw, P. J. (1990). Finding groups in data: An introduction to cluster analysis. Wiley Series in Probability and Mathematical Statistics. Applied Probability and Statistics, New York: Wiley, 1990.
Li, Y., Han, J., & Yang, J. (2004). Clustering moving objects. Proceedings of the 2004 ACM SIGKDD international conference on Knowledge discovery and data mining, 617-622.
Mane, S., Murray, C., Shekhar, S., Srivastava, J., & Pusey, A. (2005). Spatial clustering of chimpanzee locations for neighborhood identification. Fifth IEEE International Conference on Data Mining, 737-740.
Nanni, M., & Pedreschi, D. (2006). Time-focused clustering of trajectories of moving objects. Journal of Intelligent Information Systems, 27(3), 267-289.
Nehme, R. V., & Rundensteiner, E. A. (2006). SCUBA: Scalable cluster-based algorithm for evaluating continuous spatio-temporal queries on moving objects. LECTURE NOTES IN COMPUTER SCIENCE, 3896, 1001-1018.
Pokrajac, D., Zeljkovic, V., & Latecki, L. J. (2005). Noise-resilient detection of moving objects based on spatial-temporal blocks. 47th International Symposium, 91-94.
Šaltenis, S., Jensen, C. S., Leutenegger, S. T., & Lopez, M. A. (2000). Indexing the positions of continuously moving objects. ACM SIGMOD Record, 29(2), 331-342.
Sheikholeslami, G., Chatterjee, S., & Zhang, A. (1998). WaveCluster: A multi-resolution clustering approach for very large spatial databases. Proceedings of the 24th International Conference on Very Large Data Bases, 428-439.
Tao, Y., & Papadias, D. (2002). Time-parameterized queries in spatio-temporal databases. Proceedings of the 2002 ACM SIGMOD international conference on Management of data, 334-345.
Wang, W., Yang, J., & Muntz, R. (1997). STING: A statistical information grid approach to spatial data mining. Proceedings of the 23th International Conference on Very Large Data Bases, 186-195.
Wang, Y., Lim, E. P., & Hwang, S. Y. (2003). On mining group patterns of mobile users. 14th International Conference on Database and Expert Systems Applications (DEXA2003), Prague, Czech Republic, September, 287-296.
Yanagisawa, Y., & Satoh, T. (2006). Clustering multidimensional trajectories based on shape and velocity. Proceedings of the 22nd International Conference on Data Engineering Workshops, 12-21.
Zhang, T., Ramakrishnan, R., & Livny, M. (1996). BIRCH: An efficient data clustering method for very large databases. Proceedings of the 1996 ACM SIGMOD international conference on Management of data, 103-114.
電子全文 Fulltext
本電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。
論文使用權限 Thesis access permission:校內外都一年後公開 withheld
開放時間 Available:
校內 Campus: 已公開 available
校外 Off-campus: 已公開 available


紙本論文 Printed copies
紙本論文的公開資訊在102學年度以後相對較為完整。如果需要查詢101學年度以前的紙本論文公開資訊,請聯繫圖資處紙本論文服務櫃台。如有不便之處敬請見諒。
開放時間 available 已公開 available

QR Code