臺灣博碩士論文加值系統

近幾年來，由於行動設備的普及，以及相關設備軟硬體的發展，行動資料已可廣泛取得，根據地理資訊判斷物體是否為同一群組是一個新興的研究。本研究考量在時間與空間兩個面向上，移動群組的發掘。先前的研究將時間視為整段區塊或是簡單的時間循環，但是考慮到一般群組的聚集情況往往遵循某個時間型態，尤其是人類的群組的出現情況，常與約定俗成的時間曆有關，但卻又不一定嚴格遵守特定的規律。所以我們提出一個更具彈性的時間曆表示法(flexible calendar pattern)，並針對建構在新的時間面向表示法上的移動群組發掘發展出有效率的演算法。本文以IBM City Simulator產生的合成資料進行演算法的效率評估。實驗結果證明本研究所提出的方法可以有效的降低所需的執行時間。

In the past few years, due to the development of the mobile devices and the improvement of database technology, the geometric information has become widely available. Identifying object groups based on spatial-temporal dimension is an emerging research topic. Previous work has incorporating the spatial and temporal information pertaining to moving objects in finding mobile groups. Considering that mobile groups tend to exhibit some calendar-like temporal features, we define a new temporal presentation mechanism called flexible calendar pattern, which allows users to specify the desired calendar patterns at a coarse level. In addition, we developed efficient algorithms for mining mobile groups pertaining some user-specified flexible calendar pattern. The proposed algorithms are evaluated via the synthetic data generated by IBM City Simulator. The results show that our approaches prove to perform more efficiently than other intuitive approaches.

CHAPTER 1 INTRODUCTION 5
1.1 BACKGROUND 5
1.2 MOTIVATION 6
1.3 THESIS OUTLINE 6
CHAPTER 2 LITERATURE REVIEW 9
2.1 MOBILE GROUP MINING 9
2.2 TEMPORAL ASSOCIATION RULE MINING 10
2.3 CALENDAR-BASED SPATIO-TEMPORAL ASSOCIATION RULE MINING 12
CHAPTER 3 THE PROBLEM 20
3.1 AUXILIARY DEFINITIONS 20
3.2 THE MINING PROBLEM 23
CHAPTER 4 THE MINING ALGORITHMS 26
4.1 CAGP 26
4.2 CVG-GROWTH 33
CHAPTER 5 PERFORMANCE EVALUATION 39
5.1 EXPERIMENTAL DESIGN 39
5.2 EVALUATING CAGP 42
5.3 EVALUATING CVG-GROWTH 46
5.4 COMPARING CAGP AND CVG-GROWTH 49
CHAPTER 6 CONCLUSIONS 52
REFERENCES 53

[AIS93] R. Agrawal, T. Imilienski, and A. Swami, “Mining association rules between sets of items in large databases,” In Proceedings of the ACM SIGMOD International Conference on Management of Database, pp. 207-216, 1993.
[AS94] R. Agrawal and R. Srikant, “Fast algorithms for mining association rules,” In Proceedings of the VLDB Conference, pp. 478-499, Sept 1994.
[AS95] R. Agrawal and R. Srikant. Mining Sequential Patterns. In Proc. of 11th ICDE,
1995.
[BJW00] C. Bettini, S. G. Jajodia, and S. X. Wang, Time Granularities in Databases, Data Mining and Temporal Reasoning, Springer-Verlag New York Inc, 2000.
[BS00] C. Bettini and R. D. Sibi. “Symbolic representation of user-defined time granularities.” Annals of Mathematics and Artificial Intelligence, 30, 53–92, 2000.
[Chou05] Y. P. Chou “The Discovery of Calendar-Based Mobile Groups,” master thesis, National Sun Yat-sen University, Kaohsiung, Taiwan, 2005.
[DRF05] D. R. Forsyth, Group dynamics. Belmont: Brooks & Cole.
[FLM86] D. Foster, B. Leban and D. McDonald. “A representation for collections of temporal intervals.” In Proceedings of the American National Conference on Artificial Intelligence, pp. 367–371, 1986.
[GT04] John Goh, David Taniar, “Mining Frequency Pattern from Mobile Users,” Proc. Knowledge-Based Intelligent Information & Eng. Sys, LNCS( 3215), Jan 2004, pp 795 – 801.
[HLC05] S. Y. Hwang, Y. H. Liu, J. K. Chiu and E. P. Lim, “Mining Mobile Group Patterns: A Trajectory-based Approach,” In Proceedings of the 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD05), Hanoi, Vietnam, 2005.
[IS03] G. S. Iwerks, H. Samet, and K. Smith. “Continuous k-nearest neighbor queries for continuously moving points with updates.” In Proceedings of the 2003 International Conference on Very Large Data Base, 2003.
[LMF86] B. Leban, D. McDonald, and D. Foster, “A representation for collections of temporal intervals,” In Proceedings of the 5th International Conference on Artificial Intelligence, pp. 367-371, 1986.
[LN03] Y. Li, P. Ning, X. S. Wang, and S. Jajodia, “Discovering Calendar-based Temporal Association Rules,” Data and Knowledge Engineering, pp. 192-218, 2003.
[LWOH03] E.-P. Lim, Y. Wang, K.-L. Ong, and San-Yih Hwang. “In Search of Knowledge About Mobile Users.” ERCIM News, vol. 1, no. 54, pp. 10, 2003.
[NS93] M. Niezette and J. Stevenne. “An efficient symbolic representation of periodic time.” In Proceeding of the International Conference on Information and Knowledge Management, LNCS( 752), pp. 161–168, 1993.
[NWJ02] Peng Ning, Xiaoyang Sean Wang and Sushil Jajodia “An Algebraic Representation of Calendars”, Annals of Mathematics and Artificial Intelligence 36: pp. 5–38, 2002.
[ORS98] B. Özden, S. Ramaswamy, and A. Sillberschatz, “Cyclic association rules,” In Proceedings of the 14th International Conference on Data Engineering, pp. 412-421, Feb 1998.
[RMS98] S. Ramaswamy, S. Mahajan, and A. Sillberschatz, “On the discovery of interesting patterns in association rules,” In Proceedings of the 1998 International Conference on Very Large Data Base, pp. 368-379, Aug 1998.
[SJL00] S. Saltenis, C.S. Jensen, S.T. Leutenegger, M.A. Lopez, “Indexing the positions of continuously moving objects,” In Proceedings. of 2000 ACM SIGMOD Conference, 2000.
[TP02] Y. Tao and D. Papadias. “Time-parameterized queries in spatial-temporal databases.” In Proceedings. of 2002 ACM SIGMOD Conference, 2002.
[WLH03] Y. Wang, E. P. Lim, and S.Y. Hwang, “On Mining Group Patterns of Mobile Users,” In Proceedings Of the 14th International Conference on Database and Expert Systems Applications (DEXA 2003), pp. 1-5, 2003.
[WLH04]Y. Wang, E. P. Lim, and S. Y. Hwang, “Efficient Group Pattern Mining Using Data Summarization,” In Proceedings of the 9th International Conference on Database Systems for Advanced Application (DASFAA2004), Seoul, Korea, 2004.
[WSCY99]O. Wolfson, A. P. Sistla, S. Chamberlain, Y. Yesha, “Updating and querying databases that track mobile units,” Distributed and Parallel Databases, vol. 7, no. 3, 1999.
[ZSA02] G. Zimbrão, J. M. de Souza, V. T. de Almeida, W. A. da Silva, “An algorithm to discover calendar-based temporal association rules with item''s lifespan restriction”, In Proceedings of the Eight ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - 2nd Workshop on Temporal Data Mining, pp. 701–706, 2002.