(3.238.186.43) 您好!臺灣時間:2021/02/26 12:59
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:周燕絲
研究生(外文):Yen-ssu Chou
論文名稱:行動服務環境下探勘使用者移動行為樣式
論文名稱(外文):Mining User Movement Behavior Patterns in a Mobile Service Environment
指導教授:陳宗禧陳宗禧引用關係
指導教授(外文):Tzung-Shi Chen
學位類別:碩士
校院名稱:國立臺南大學
系所名稱:數位學習科技學系碩士班
學門:教育學門
學類:教育科技學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:英文
論文頁數:62
中文關鍵詞:移動行為樣式時空探勘行動服務環境移動性預測行動存取樣式
外文關鍵詞:Movement Behavior PatternsMobile Access PatternsSpatio-Temporal MiningMobile Service EnvironmentMobility prediction
相關次數:
  • 被引用被引用:0
  • 點閱點閱:296
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著無線網路技術的快速進步,使得行動用戶能夠在任何時間和任何地點透過行動載具請求各種服務。有效的從行動網路系統提供用戶獲得所需的資訊是一個重要的議題。這個研究議題主要是去有效的處理各種用戶移動行為的樣式以及大量的資料。然而,就我們所知,目前沒有研究在探勘行動存取樣式的問題時,同時考慮行動用戶、移動位置、停留時間以及請求服務這四者的關係,這主要是為了找出每個行動用戶移動行為樣式的更多完整資訊。在這篇論文中,我們提出一個新的資料探勘方法(即MMAP-Mine)可以在每個時間間格有效的找出用戶移動樣式和請求服務的關聯。找到的用戶移動行為樣式可以用來預測每個時間間隔的不同位置和相關的服務。此外,適當的預測策略亦被提出。此時,我們提出一個有效的預測機制藉由將用戶的移動行為樣式模組化來做關聯樹(Associated Trees)架構探勘,透過最大權重二項圖配對(Bipartite Graph Matching),可以清楚的在行動用戶、移動位置、停留時間以及請求服務之間找出最強大的關聯性。最後,根據實驗評估透過使用综合數據產生器於各種模擬情況下得知,我們所提出的方法具有較高的執行效率。
The rapid advances of wireless and web technologies enable the mobile users to request various kinds of services via mobile devices at anytime and anywhere. To provide the users obtain needed information effectively is an important issue in the mobile service systems. The main challenge in this research issue is to effectively deal with diverse user movement behavior patterns and the huge amount of data. However, to our best knowledge, no studies have been done on the problem of mining mobile access patterns with four relations of mobile users (taken as U), moving locations (taken as L), staying time in timestamps (taken as T), and service requests (taken as S) considered simultaneously in order to discover more complete information of each mobile user’s movement behavior patterns. In this thesis, we propose a novel data mining method, namely MMAP-Mine that can efficiently discover each mobile user movement patterns associated with requested services of each time interval. The discovery of mobile users’ movement behavior patterns can be used for predicting different locations with associated services of each time interval. Moreover, the corresponding prediction strategies are also proposed. Meanwhile, we present an effective prediction mechanism by modeling the user’s movement behavior pattern for mining the associated tree structure via the maximum weight bipartite graph matching that can be clear to find out the strongly relationships among mobile users, moving locations, staying time in timestamps T, and service requests. Finally, through experimental evaluation under various simulation conditions of the proposed methods using synthetically generated data shown to deliver excellent performance in terms of execution efficiency and scalability.
摘 要 i
ABSTRACT ii
誌 謝 iii
Contents iv
Lists of Tables v
Lists of Figures vi
1. Introduction 1
1.1 Background 1
1.2 Motivation 2
2. Related Work 5
3. System Overview 8
3.1 System Architecture for Mobile Access patterns 8
3.2 Mobile Access Patterns in Object Trajectories 9
4. Identifying Match joins for Mobile Access patterns 15
4.1 Match Joins between Users and Locations 17
4.2 Match Joins between Locations and Timestamps 18
4.3 Match Joins between Timestamps and Services 22
5. Mining Matching Mobile Access patterns 26
5.1 Match Joins Using Max Flow 26
5.2 Match Joins Using Sort Combination 31
5.3 Match Joins Using Associated Trees 38
6. Experimental Results 50
6.1 Experimental Design and Data Generation 50
6.2 Simulation Results 52
6.2.1 Impact of Different Simulation Time 52
6.2.2 Impact of Different Candidate Dataset 53
6.2.3 Impact of Different Node Counts 54
6.2.4 Impact of Different Item Counts 55
6.2.5 Impact of Different Mobile Access Patterns 57
7. Conclusion and Future Work 59
References 60
[1] R. Agrawal and R. Srikant, “Fast algorithms for mining association rules in large databases,” in Proceedings of the 20th International Conference Very Large Data Bases, pp. 487-499, 1994.
[2] R. Agrawal and R. Srikant, “Mining sequential patterns,” in Proceedings of the 11th International Conference Data Engineering, pp. 3-14, 1995.
[3] R. Agrawal and H. V. Jagadish, “Materialization and Incremental Update of Path Information,” in Proceedings of the 5th International Conference on Data Engineering (ICDE), pp.374-383, 1989.
[4] R. Agrawal and E. Wimmers, “A Framework for Expressing and Combining Preferences,” in Proceedings of ACM SIGMOD Record, Vol. 29, Issue 2, pp. 297-306, June 2000.
[5] R. Agrawal, T. Imielinski, and A. Swami, “Mining association rules between sets of items in large databases,” in Proceedings of the 1993 ACM SIGMOD international conference on Management of data, Washington, D.C., USA, pp 207-216, 1993.
[6] R. K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, New Jersey, USA, 1993.
[7] I. F. Akyildiz, J. Mcnair, J. S. M. Ho, H. Uzunalioglu, and W. Wang, “Mobility Management in Next-Generation Wireless System,” in Proceedings of the IEEE, Vol. 87, No. 8, pp. 1347-1384, August 1999.
[8] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless Sensor Networks: A Survey,” Computer Networks: The International Journal of Computer and Telecommunications Networking, Vol. 38, No. 4, pp. 393-422, March 2002.
[9] I. F. Akyildiz, J. Mcnair, J. S. M. Ho, H. Uzunalioglu, and W. Wang, “Mobility management in next-generation wireless system,” in Proceedings of the IEEE, Vol. 87, No. 8, pp. 1347-1384, August 1999.-
[10] U. Bellur and R. Kulkarni, “Improved Matchmaking Algorithm for Semantic Web Services Based on Bipartite Graph Matching,” in Proceedings of the IEEE International Conference on Web Services (ICWS 2007), pp. 86-93, Salt Lake City, Utah, USA, July 2007.
[11] C. Berge, “Two Theorems in Graph Theory,” in Proceedings of the National Academy of Science, pp. 842-844, USA, 1957.
[12] M. J. Berry and G. S. Linoff, Data mining techniques for marketing, sales and customer support, John Wiley & Sons, New York, USA, 1997.
[13] J. Borges and M. Levene, “Data mining of user navigation patterns,” in Proceedings of the Workshop on Web Usage Analysis and User Profiling (WEBKDD’99), pp. 31-36, 1999.
[14] C. Y. Chang and M. S. Chen, “Integrating web caching and web prefetching in client-side proxies,” in IEEE Transactions on Parallel and Distributed Systems, Vol. 16, Issue 5, pp. 444-455, May 2002.
[15] Y. C. Chang, L. D. Bergman, V. Castelli, C. S. Li, M. L. Lo, and J. R. Smith, “The Onion Technique: Indexing for Linear Optimization Queries,” in Proceedings of 2000 ACM SIGMOD International Conference, pp. 391-402, 2000.
[16] M. S. Chen, J. S. Park, and P. S. Yu, “Efficient data mining for path traversal patterns,” in IEEE Transactions On Knowledge And Data Engineering, Vol. 10, No. 2, pp. 209-221, 1998.
[17] J. L. Chen, “Resource Allocation for Cellular Data Services Using Multiagent Schemes,” in IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, Vol. 31, No. 6, pp. 864-869, December 2001.
[18] S. K. Das and S. K. Sen, “Adaptive location prediction strategies based on a hierarchical network model in cellular mobile environment,” in Proceedings of the 2nd International Mobile Computing Conference, pp. 131-140, Taiwan, R.O.C., 1996.
[19] M. Fayyazi, D. Kaeli, and W. Meleis, “Parallel Maximum Weight Bipartite Matching Algorithms for Scheduling in Input-Queued Switches,” in Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS’04), pp. 4-11, 2004.
[20] J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang, “On Graph Problems in a Semi-Streaming Model,” in Proceedings of Theoretical Computer Science, Vol. 348, Issue 2, pp. 207-216, December 2005.
[21] L. Gravano and S. Chaudhuri, “Evaluating Top-k Selection Queries,” in Proceedings of the 25th international conference on Very large data bases (VLDB), pp. 397-410, Edinburgh, Scotland, 1999.
[22] A. V. Goldberg and R. E. Tarjan, “A new approach to the maximum-flow problem,” in Journal of the ACM (JACM), Vol. 35, Issue. 4, pp. 921-940, October 1988.
[23] S. Guha, D. Gunopulos, N. Koudas, D. Srivastava, and M. Vlachos, “Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints,” in Proceedings of the 29th international conference on Very large data bases (VLDB), Vol. 29, pp. 778-789, 2003.
[24] J. Han, J. Pei, and Y. Yin, “Mining frequent patterns without candidate generation,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 1-12, 2000.
[25] J. Hopcroft and R. Karp, “An n5/2 Algorithm for Maximum Matching in Bipartite Graphs,” Society for Industrial and Applied Mathematics Journal of Computing, pp. 225-231, 1975.
[26] J. L. Huang, M. S. Chen, and W. C. Peng, “Exploring group mobility for replica data allocation in a mobile environment,” in Proceedings of the ACM International Conference Information and Knowledge Management, pp. 161-168, 2003.
[27] I. F. Ilyas, W. G. Aref, and A. K. Elmagarmid, “Supporting Top-k Join Queries in Relational Databases,” in Journal of Very large data bases, Vol. 13, No. 3, pp. 207-221, September 2004.
[28] R. M. Karp, U. V. Vazirani, and V.V. Vazirani, “An optimal algorithm for online bipartite matching,” in Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pp. 352-358, Baltimore, Maryland, USA, 1990.
[29] G. H. Li, K. Y. Lam, and T. W. Kuo, “Location update generation in cellular mobile computing systems,” in Proceedings of the 15th International Parallel And Distributed Processing Symposium, pp. 96, 2001.
[30] A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani, “AdWords and Generalized Online Matching,” in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 264-273, 2005.
[31] J. Monnot and S. Toulouse, “The path partition problem and related problems in bipartite graphs,” Operations Research Letters, Vol. 35, Issue 5, pp. 677-684, September 2007.
[32] A. Nanopoulos, D. Katsaros, and Y. Manolopoulos, “Exploiting web log mining for web cache enhancement,” in Proceedings of the WebKDD 2001: KDD Workshop on Web Mining and Web Usage Analysis, pp. 68-87, 2001.
[33] J. Pei, J. Han, B. Mortazavi-Asl, and H. Zhu, “Mining access patterns efficiently from web logs,” in Proceedings of the Fourth Pacific Asia Conference Knowledge Discovery and Data Mining, pp. 396-407, 2000.
[34] W. C. Peng and M. S. Chen, “Mining user moving patterns for personal data allocation in a mobile computing system,” in Proceedings of the International Conference Parallel Processing, pp. 573-580, 2000.
[35] W. C. Peng and M. S. Chen, “Allocation of shared data based on mobile user moving,” in Proceedings of the Third International Conference Mobile Data Management, pp. 105-112, 2002.
[36] W. C. Peng and M. S. Chen, “Developing Data Allocation Schemes by Incremental Mining of User Moving Patterns in a Mobile Computing System,” in Proceedings of the IEEE Transactions On Knowledge And Data Engineering, pp.70-85, 2003.
[37] I. Pramudiono, T. Shintani, K. Takahashi, and M. Kitsuregawa, “User Behavior Analysis of Location Aware Search Engine,” in Proceedings of the 3rd International Conference Mobile Data Management, pp. 139-145, 2002.-
[38] U. Rückert and S. Kramer, “Frequent free tree discovery in graph data,” in Proceedings of the 2004 ACM Symposium on Applied Computing (SAC 2004), pp. 564-570, Nicosia, Cyprus, March 2004.
[39] Y. Saygin and O. Ulusoy, “Exploiting Data Mining Techniques for Broadcasting Data in Mobile Computing Environments,” in IEEE Transactions on Knowledge and Data Engineering, Vol. 14, No. 6, pp. 1387-1399, 2002.
[40] C. Schlup, “Automatic Game Matching,” http://dcg.ethz.ch/theses/ws0203/OnlineMatching_abstract.pdf
[41] J. Schiller and A. Voisard, Location-Based Services, Morgan Kaufmann, San Francisco, California, USA, 2004.
[42] P. Tsaparas, T. Palpanas, Y. Kotidis, N. Koudas, and D. Srivastava, “Ranked Join Indices,” in Proceedings of the 19th International Conference on Data Engineering (ICDE''03), pp. 277-288, 2003.
[43] S. M. Tseng and W. C. Chan, “Efficiently Mining Complete User Moving Path in Mobile System,” in Proceedings of the International Workshop on Databases and Software Engineering (held with ICS), pp. 102-107, Taiwan, R.O.C., 2002.
[44] H. K. Wu, M. H. Jin, J. T. Horng, and C. Y. Ke, “Personal Paging Area Design Based On Mobile’s Moving Behaviors,” in Proceedings of the IEEE Conference on Computer and Communications, pp. 21-30, 2001.
[45] M. J. Zaki, “Efficiently mining frequent trees in a forest,” in Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 71-80, Edmonton, Alberta, Canada, July 2002.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
系統版面圖檔 系統版面圖檔