博碩士論文 etd-0728107-170024 詳細資訊


[回到前頁查詢結果 | 重新搜尋]

姓名 李健民(Chien-Ming Lee) 電子郵件信箱 m944020011@student.nsysu.edu.tw
畢業系所 資訊管理學系研究所(Information Management)
畢業學位 碩士(Master) 畢業時期 95學年第2學期
論文名稱(中) 從空間時間資料庫挖掘移動群組
論文名稱(英) Discovering Moving Clusters from Spatial-Temporal Databases
檔案
  • etd-0728107-170024.pdf
  • 本電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
    請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。
    論文使用權限

    電子論文:校內外都一年後公開

    論文語文/頁數 英文/63
    統計 本論文已被瀏覽 5365 次,被下載 1843 次
    摘要(中) 隨著電腦與通訊技術的進步,分析移動物件上的群集關係,近幾年逐漸吸引到各方的注意力。一個令人感到興趣的問題是找出移動群組,而移動群組裡的物件成員都必需在一起移動一段足夠長的時間。然而,一個移動群組因為每一個物件的目的地會有所不同,所以在一段時間之後,一個移動群組易於分裂拆散。為了能夠鑑別出一些移動群組,我們藉由明確的參數設定,進而定義正規的移動群組。接著我們以移動群組的定義為基礎,提出精確的方法來為這些移動物件做分群。而我們提出的方法將在兩種類型的資料情況下進行評估,分別為合成資料、潛在已知的資料。最後,我們藉由一整個實驗的評估與比較來驗證我們提出的方法。
    摘要(英) 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.
    關鍵字(中)
  • 空間時間資料庫
  • 移動群組
  • 關鍵字(英)
  • Spatial-Temporal Databases
  • Moving Clusters
  • 論文目次 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
    參考文獻 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.
    口試委員
  • 魏志平 - 召集委員
  • 楊婉秀 - 委員
  • 黃三益 - 指導教授
  • 口試日期 2007-06-22 繳交日期 2007-07-28

    [回到前頁查詢結果 | 重新搜尋]


    如有任何問題請與論文審查小組聯繫