在行動系統中，對使用者位置之分析與預測是一項重要課題，因其在通訊應用領域中具有高度而廣泛之應用價值。且由於此環境的特性，我們必須先解決處理大量資料與複雜移動樣式等問題，才能繼續探討預測使用者的行為。然而，針對此方面的相關研究仍然極為有限。而在本論文中，我們提出一高效性之位置探勘與預測機制，不僅可處理大量資料與複雜樣式等問題，更可有效地預測使用者位置。而該機制主要包含兩個部分：1)完整移動樣式演算法。2)位置預測方法。在第一部份，我們提出一個新的資料探勘演算法，可以有效地找出完整移動樣式，並且進一步產生完整移動規則。第二部分則是利用完整移動規則，來預測使用者位置。我們所提出的方法主要特色有：1)找出完整移動樣式，可完整地描述使用者的複雜移動樣式。2)利用資料探勘技術，有效率地針對大量資料作處理。3)和之前相關研究相比，在預測方面擁有較高的正確率。而藉由實驗的觀察，我們所提出的機制在各種系統狀況下，均比之前相關研究有較佳的效能。

In the mobile systems, analyzing mobile user’s moving location and predication is an important topic due to the wide applications. The main challenge in this research topic is to effectively deal with large databases and complex patterns of users’ locations. However, there exist very limited studies which provide efficient methods for analyzing user’s moving behavior in a mobile system. In this thesis, we proposed effective location mining and prediction mechanisms that can resolve the above problems. The mechanisms are composed of two parts: 1) Complete Moving Patterns (CMP)-mining, 2) Predication Method. For the data mining part, we developed a novel data mining algorithm that can efficiently discover user’s complete moving patterns. For the prediction part, we proposed a method for effective predicting user’s further locations based on the discovered moving patterns. The main features of our mechanisms are: 1) Finding the complete moving patterns that could totally describe the user’s moving behavior, 2) Using data mining algorithms to handle the large databases efficiently, 3) Providing higher precision than other methods. Through empirical evaluation, the proposed mechanisms were shown to deliver excellent performance under various system conditions.

[1] R. Agrawal, T. Imieliński, and A. Swami. Mining Association Rules between Sets
of Items in Large Databases. Proceedings of the ACM SIGMOD Conference on
Management of Data, pages 207-216, Washington, D.C., May 1993.

[2] R. Agrawal and R. Srikent. Fast Algorithms for Mining Association Rules.
Proceedings of the 20th International Conference on Very Large Data Bases, pages
478-499, Santiago, Chile, September 1994.

[3] R. Agrawal and R. Srikent. Mining Sequential Patterns. Proceedings of the 11th
International Conference on Data Engineering, pages 3-14, Taipei, Taiwan, March
1995.

[4] J. Ayres, J. E. Gehrke, T. Yiu, and J. Flannick. Sequential Pattern Mining Using
Bitmaps. Proceedings of the 8th ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, Edmonton, Alberta, Canada, July 2002.

[5] B. Bruegge and B. Bennington. Applications of Mobile Computing and
Communication. IEEE Personal Communications, Special Issue on Mobile
Computing, pages 64-71, February 1996.

[6] M.-S. Chen, J. Han and P. S. Yu. Data Mining: An Overview from Database
Perspective. IEEE Transactions on Knowledge and Data Engineering, vol. 8, no. 6,
pages 866-883, December 1996.

[7] M.-S. Chen, J.-S. Park and P. S. Yu. Efficient Data Mining for Path Traversal
Patterns. IEEE Transactions on Knowledge and Data Engineering, vol. 10, no. 2,
pages 209-221, March 1998.

[8] N. Davies, G.S. Blair, K. Cheverst, and A. Friday. Supporting Collaborative
Applications in a Heterogeneous Mobile Environment. Computer Communication
Special Issues on Mobile Computing, 1995.

[9] ELA/TLA. Cellular Radio Telecommunication Intersystem Operations. 1991.

[10] A. Elmagarmid, J. Jain, and T. Furukawa. Wireless Client/Server Computing for
Personal Information Service and Applications. ACM SIGMOD RECORD, vol. 24,
no. 4, pages 16-21, December 1995.

[11] G. H. Forman and J. Zahorjan. The Challenges of Mobile Computing. IEEE
Computer, vol. 27, no. 4, pages 28-47, April 1994.

[12] J. Han, J. Pei, and Y. Yin. Mining Frequent Patterns without Candidate Generation.
Proceedings 2000 ACM SIGMOD International Conference on Management of
Data, vol. 29, no. 2, pages 1-12, Dallas, Texas, USA, May 2000.

[13] J. Jannink, D. Lam, N. Shivakumar, J. Widom, and D. Cox. Efficient and Flexible
Location Management Techniques for Wireless Communication Systems.
ACM/Baltzer Journal of Mobile Networks and Applications, vol. 3, no. 5, pages
361-374, October 1997.

[14] Y.-B. Lin. GSM Network Signaling. ACM Mobile Computing and Communication,
vol. 1, no. 2, pages 11-16, 1997.

[15] C. Lee and C.-C. Chen. A Data Delivery Strategy in Ubiquitous Computing
Systems. Proceedings of the 7th International Conference on Database Systems for
Advanced Applications, pages 210-217, April 2001.

[16] F. Masseglia, P. Poncelet and M. Teisseire. Incremental Mining of Sequential
Patterns in Large Databases. Actes des 16imes Journes Bases de Donnes Avances
(BDA'00), Blois, France, October 2000.

[17] J.-S. Park, M.-S. Chen and P. S. Yu. An Effective Hash Based Algorithm for Mining
Association Rules. Proceedings of the ACM SIGMOD Conference on Management
of Data, pages 157-186, May 1995.

[18] W.-C. Peng and M.-S. Chen. A Dynamic and Adaptive Cache Retrieval Scheme for
Mobile Computing Systems. Proceedings 3rd IFCIS Conference on Cooperative
Information Systems (CoopIS ’98), pages 251-258, August 1998.

[19] J. Pei, J. Han, B. Mortazavi-Asl, and H. Zhu. Mining Access Patterns Efficiently
from Web Logs. Proceedings 2000 Pacific-Asia Conference on Knowledge
Discovery and Data Mining, pages 396-407, Kyoto, Japan, April 2000.

[20] W.-C. Peng and M.-S. Chen. Mining User Moving Patterns for Personal Data
Allocation in a Mobile Computing System. Proceedings of the 2000 International
Conference on Parallel Processing, pages 573-580, Toronto, Canada, August 2000.

[21] M. Satyanarayanan. Mobile Information Access. IEEE Personal Communications,
pages 26-33, February 1996.

[22] R. Srikant and R. Agrawal. Mining Sequential Patterns: Generalizations and
Performance Improvements. Proceedings of the 5th International Conference on
Extending Database Technology (EDBT), pages 3-17, Avignon, France, March
1996.

[23] N. Shivakumar, J. Jannink, and J. Widom. Per-User Profile Replication in Mobile
Environments: Algorithms, Analysis and Simulation Results. ACM/Baltzer Journal
on Special Topics in Mobile Networks and Applications, vol. 2, no. 2, pages
129-140, 1997.

[24] Y. Saygin, O. Ulusoy, and A. Elmagarmid. Association Rules For Supporting
Hoarding in Mobile Computing Environments. Proceedings of the 10th
International Workshop on Research Issues in Data Engineering, IEEE Computer
Society Digital Library, pages 71-78, fall 2000.

[25] M.-K. Shan and H.-F. Li. Fast Discovery of Structure Navigation Patterns from
Web User Traversals. SPIE Conference on Data Mining and Knowledge Discovery:
Theory, Tools, and Technology IV, 2002.

[26] Y. Saygin and O. Ulusoy. Exploiting Data Mining Techniques for Broadcasting
Data in Mobile Computing Environments. IEEE Transactions on Knowledge and
Data Engineering, vol. 14, no. 6, November 2002.

[27] O. Wolfson, S. Jajodia, and Y. Huang. An Adaptive Data Replication Algorithm.
ACM Transaction Database Systems, vol. 22, no. 4, pages 255-314, June 1997.

[28] A. Zaslavsky and Z. Tari. Mobile Computing: Overview and Current Status.
Australian Computer Journal, vol. 30, no. 2, May 1998.