隨著無線通訊以及微電子裝置技術的進步，近年來行動計算吸引了許多的注意已成為一新興之研究。然而，一些本質上的限制像是有限電源、移動的使用者、以及有限的網路頻寬等等，都是必須被仔細處理的問題。在過去數年，許多的研究都是專注於解決基礎建設上的問題，而沒有考慮到使用者本身的行為以提供更佳的服務。於此論文中，我們提出了高效率以及有效地探勘方式能夠從使用者過往紀錄中探勘隱藏的行為樣式以改善行動網絡與物體追蹤無線感測器網路的效能。我們也設計了整合所探勘之行為樣式的系統，與過去的研究相比，證明了其可行性以及高效性。
對於行動網絡的效能問題，許多研究學者應用使用者共同的行為樣式對資料以預取以及暫存之方式以達到快速的存取，但是這些現有的研究都只考慮到單一個行動特徵，也就是單考慮位置或是存取服務而已。我們於此論文中，提出一新穎的行動網絡架構，其能利用使用者過往的共同行為樣式支援行為感測以及個人化行動服務等智慧型之功能。由於在行動網絡系統中，使用者的行為比傳統網際網絡複雜許多，因此我們亦提出一新式探勘方法，能夠探勘出使用者的連續移動路徑以及其存取之服務，以及提出相對應之預測方法。經由實驗證明了我們所提之方法是準確的、有效率的、以及可延展的。
對於物體追蹤無線感測器網路之效能，我們認為在現實生活的應用中，物體的移動是根據某種事件而非完全地隨意行走。因此，我們提出其資料探勘方法以及特殊資料結構以有效率地探勘物體之移動樣式。於此論文中，我們探討了兩種移動樣式: 「具時間間隔性之移動路徑樣式」以及「具時間間隔性之區域移動樣式」。就「具時間間隔性之移動路徑樣式」之探勘而言，這是在物體追蹤無線感測器網路中，第一個同時考慮到時間間隔以及移動路徑之探勘方法。此外，「具時間間隔性之區域移動樣式」的探勘方式，其運作並不需要預先訂定區域的結構。我們亦設計了一系列位置預測機制，其應用探勘出之移動樣式以減低預測失敗，達到節省能源之目的。經由實驗證明，我們的方法是可延展的、準確的、以及節省能源的。

With the advances in wireless communication and microelectronic device technologies, mobile computing has become an emerging research field that attracts a lot of attention recently. However, several intrinsic restrictions like power constraints, mobile clients and limited bandwidth need to be carefully handled. In the past years, most of the studies focused on solving the infrastructure problems and did not consider the users’ behavior so as to provide better solutions. In this dissertation, we propose a set of efficient and effective data mining algorithms that can discover the hidden patterns from users’ log databases for improving the performance of mobile web systems and object tracking sensor networks (OTSNs). We also design the systems that integrate the discovered patterns so as to demonstrate the feasibility and excellence of the proposed algorithms as compared with the past studies.
As to the performance issue of mobile web systems, many researchers tried to apply the common patterns to prefetching and caching data for fast accessing, but the existing studies considered only one of the mobility characteristics, i.e., location or service requested while not both of them simultaneously. We propose a novel framework to support intelligent functionalities like behavior-aware and personalized mobile services, where the behavior-aware functionality is provided by analyzing the historical behavior log of users and the personalization functionality is provided by integrating user profile with frequent mobility patterns. Since the mobility patterns in the mobile web systems are more complex than the traditional WWW access patterns, we propose a set of novel data mining methods that can efficiently discover mobile users’ sequential mobility patterns associated with requested services, and design the corresponding prediction strategies. Through empirical evaluation under various simulation conditions, the proposed framework and methods are shown to deliver excellent performance in terms of accuracy, execution efficiency and scalability.
For improving the performance of OTSNs, we consider that in some real applications the object movement behavior is often based on certain underlying events instead of randomness completely. Therefore, a set of novel data mining algorithms with a special data structure for efficiently discovering the mobility patterns of objects in sensor networks are proposed. Two kinds of mobility patterns are explored, namely 1) temporal mobility patterns (TMPs) in which the patterns are associated with time intervals, and 2) temporal region based mobility patterns. In the dissertation, we propose a novel data mining method named TMP-Mine with a special data structure for efficiently discovering TMPs, and propose the first method to discover the region based patterns without predefined region architecture. Moreover, the accompanying prediction strategies that utilize the discovered mobility patterns are designed so as to reduce the prediction errors for energy savings. Through empirical evaluation on various simulation conditions, the proposed mining method and prediction strategies are shown to deliver excellent performance in terms of scalability, accuracy and energy efficiency.

[1] R. Agrawal and R. Srikant, "Fast Algorithms for Mining Association Rules in Large Databases," in Proc. 20th Int. Conf. Very Large Data Bases, 1994, pp. 487-499.
[2] R. Agrawal and R. Srikant, "Mining Sequential Patterns," in Proc. 11th Int. Conf. Data Engineering, 1995, pp. 3-14.
[3] I. F. Akyildiz, J. Mcnair, J. S. M. Ho, H. Uzunalioglu, and W. Wang, "Mobility Management in Next-Generation Wireless System," in Proc. IEEE, vol. 87, no. 8, pp. 1347-1384, 1999
[4] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, Wireless Sensor Networks: A Survey, Computer Networks 38(4), 2002, pp. 393-422.
[5] J. M. Ale, G. H. Rossi. An Approach to Discovering Temporal Association Rules, in: Proceedings of the 2000 ACM Symposium on Applied Computing, 2000, pp. 294-300.
[6] R. J. Bayardo Jr., "Efficiently Mining Long Patterns from Databases," in Proc. ACM Int. Conf. Management of Data, 1998, pp. 85-93.
[7] J. Borges and M. Levene, "Data Mining of User Navigation Patterns," in Proc. Workshop on Web Usage Analysis and User Profiling (WEBKDD'99), 1999, pp. 31-36.
[8] G. Cabri, L. Leonardi, M. Mamei, and F. Zambonelli, "Location-dependent services for mobile users," IEEE Trans. Syst., Man, and Cybern. A, vol. 33, no. 6, pp. 667-681, 2003
[9] J. Carle, D. Simplot, Energy-Efficient Area Monitoring for Sensor Networks, IEEE Computer 37(2), 2004, pp. 40-46.
[10] A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, J. Zhao, Habitat Monitoring: Application Driver for Wireless Communications Technology, in: Proceedings of the 1st ACM SIGMOMM Workshop on Data Communications in Latin America and the Caribbean, 2001
[11] C. Y. Chang and M.S. Chen, "Integrating Web Caching and Web Prefetching in Client-Side Proxies," in Proc. ACM 11th Int. Conf. Information and Knowledge Management, 2002
[12] Z. Chen and A. W. C. Fu, "Linear Time Algorithms for Finding Maximal Forward References," in Proc. 2003 IEEE Intl Conf On Info Tech: Coding and Computing, 2003
[13] J. L. Chen, "Resource Allocation for Cellular Data Services Using Multiagent Schemes," IEEE Trans. Syst., Man, and Cybern. B, vol. 31, no. 6, pp. 864-869, 2001
[14] M. S. Chen, J. S. Park and P. S. Yu, "Efficient Data Mining for Path Traversal Patterns," IEEE Trans. Knowledge and Data Eng., vol. 10, no. 2, pp. 209-221, 1998
[15] D. K. W. Chiu, S. C. Cheung, E. Kafeza, and H. F. Leung, "A Three-Tier View-Based Methodology for M-Services Adaptation," IEEE Trans. Syst., Man, and Cybern. A, vol. 33, no. 6, pp. 725-741, 2003
[16] M. Ester, H. P. Kriegel, Jo"rg Sander, Xiaowei Xu: A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. KDD 1996:00:00 226-231
[17] S. Goel, T. Imielinski, Prediction-based Monitoring in Sensor Networks: Taking Lessons from MPEG, ACM Computer Communication Review, 31(5), 2001
[18] F. Guil, A. Bosch, R.Marin, TSET MAX: An Algorithm for Mining Frequent Maximal Temporal Patterns, in: Proceedings of the Workshop on Temporal Data Mining: Algorithms, Theory and Applications (TDM'04), 2004, pp 71-77
[19] J. Han, J. Pei, and Y. Yin, "Mining Frequent Patterns without Candidate Generation," in Proc. ACM Int. Conf. Management of Data, 2000
[20] T. Hara, N. Murakami, S. Nishio, Replica Allocation for Correlated Data Items in ad hoc Sensor Networks, SIGMOD Record 33(1), 2004, pp. 38-43.
[21] W. R. Heinzelman, A. Chandrakasan, H. Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, in: Proceedings of the 33rd Hawaii International Conference on System Sciences, 2000
[22] G. Hooker and M. Finkelman, "Sequential Analysis for Learning Modes of Browsing," in Proc. WebKDD 2004:00:00 KDD Workshop on Web Mining and Web Usage Analysis, 2004
[23] J. L. Huang, M. S. Chen, and W. C. Peng, "Exploring group mobility for replica data allocation in a mobile environment," in Proc. ACM Int. Conf. Information and Knowledge Management, 2003, pp. 161-168.
[24] Java Message Service (JMS). http://java.sun.com/products/jms/
[25] Java Server Pages Technology. http://java.sun.com/products/jsp/
[26] Java Servlet Technology. http://java.sun.com/products/servlet/
[27] R. Jose, A. J. C. Moreira, H. Rodrigues, and N. Davies, "The AROUND Architecture for Dynamic Location-Based Services," Mobile Networks and Applications, vol. 8, no. 4, pp. 377-387, 2003
[28] T. G. Kanter, "Attaching context-aware services to moving locations," IEEE Internet Computing, vol. 7, no. 2, pp. 43-51, 2003
[29] M. Kyriakakos, S. Hadjiefthymiades, N. Frangiadakis, and L. F. Merakos, "Multi-user Driven Path Prediction Algorithm for Mobile Computing," in Proc. 14th Int. Workshop on Database and Expert Systems Applications, 2003, pp. 191-195.
[30] A. J. T. Lee and Y. T. Wang, "Efficient data mining for calling path patterns in GSM networks," Information Systems, vol. 28, no. 8, pp. 929-948, 2003
[31] G. H. Li, K. Y. Lam, and T. W. Kuo, "Location Update Generation in Cellular Mobile Computing Systems," in Proc. Int. Workshop on Parallel and Distributed Real-time Systems, 2001
[32] Y. Li, P. Ning, X. S. Wang, S. Jajodia, Discovering Calendar-based Temporal Association Rules, Data and Knowledge Engineering, vol. 44, 2003, pp.193-218.
[33] K. W. Lin and S. M. Tseng, "A Data Generator for Mobile Web Environments," Technical Report, CSIE Dept, National Cheng Kung University, Taiwan, 2002
[34] S. W. Loke, A. Rokotonirainy, and K. Schulz, "Location-Based Personal Agents: A Metaphor for Situated Computing," in Proc. IEEE Int. Workshop on Parallel Processing, 2000, pp. 17-22.
[35] Z. Maamar, B. Benatallah, and Q. Sheng, "Towards a Unified Framework for Composing E-/M-Services," in Proc. Int. Workshop on M-Services, 2002,
[36] Z. Maamar, E. Dorion, and C. Daigle, "Toward virtual marketplaces for E-commerce," Comm. ACM, vol. 44, no. 12, pp. 35-38, 2001
[37] Z. Maamar, G. AlKhatib, S. K. Most?faoui, M. Lahkim, and W. Mansoor, "Context-based Personalization of Web Services Composition and Provisioning," in Proc. 30th Conf. EUROMICRO, 2004, pp. 396-403.
[38] M. Mani, Understanding the Semantics of Sensor Data, ACM SIGMOD Record 32(4), 2003
[39] Microsoft Visual Studio .NET 2003 http://msdn.microsoft.com/vstudio/productinfo/
[40] A. Nanopoulos, D. Katsaros, and Y. Manolopoulos, "Exploiting Web Log Mining for Web Cache Enhancement," in Proc. WebKDD 2001:00:00 KDD Workshop on Web Mining and Web Usage Analysis, 2001, pp. 68-87.
[41] B. Padmanabhan, A. Tuzhilin, Pattern Discovery in Temporal Databases: A Temporal Logic Approach, In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, 1996, pp. 351-354.
[42] V. Padmanabhan and J. Mogul, "Using Predictive Prefetching to Improve World Wide Web Latency," ACM SIGCOMM Computer Comm. Rev., vol. 26, no. 3, 1996
[43] T. Palpanas and A. Mendelzon. "Web Prefetching Using Partial Match Prediction," in Proc. Fourth Web Caching Workshop, 1999
[44] A. Papoulis. "Probability, Random Variables, and Stochastic Processes," McGraw Hill,1991.
[45] J. Pei, J. Han, B. Mortazavi-Asl, and H. Zhu, "Mining Access Patterns Efficiently from Web Logs," in Proc. 4th Pacific Asia Conf. Knowledge Discovery and Data Mining, 2000, pp. 396-407.
[46] W. C. Peng and M. S. Chen, "Mining User Moving Patterns for Personal Data Allocation in a Mobile Computing System," in Proc. Int. Conf. Parallel Processing, 2000, pp. 573-580.
[47] W. C. Peng and M. S. Chen, "Allocation of Shared Data Based on Mobile User Movement," in Proc. 3rd Int. Conf. Mobile Data Management, 2002, pp. 105-112.
[48] PersonalJava. http://java.sun.com/products/personaljava/
[49] J. Pitkow and P. Pirolli, "Mining Longest Repeating Subsequences to Predict World Wide Web Surfing," in Proc. USENIX Symp. Internet Technologies and Systems, 1999
[50] I. Pramudiono, T. Shintani, K. Takahashi, and M. Kitsuregawa, "User Behavior Analysis of Location Aware Search Engine," in Proc. 3rd Int. Conf. Mobile Data Management, 2002, pp. 139-145.
[51] V. Raghunathan, C. Schurgers, S. Park, M. B. Srivastava, Energy Aware Wireless Microsensor Networks, IEEE Signal Processing Magazine, 19(2), 2002, pp. 40-50.
[52] J. F. Roddick, M. Spiliopoulou, A Survey of Temporal Knowledge Discovery Paradigms and Methods, IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 4, 2002, pp. 750-767.
[53] G. C. Roman, C. Julien, and Q. Huang, "Network abstractions for context-aware mobile computing," in Proc. 24th Int. Conf. Software Engineering, 2002, pp. 363-373.
[54] Y. Saygin and O. Ulusoy, "Exploiting Data Mining Techniques for Broadcasting Data in Mobile Computing Environments," IEEE Trans. Knowledge and Data Eng., vol. 14, no. 6, pp. 1387-1399, 2002
[55] E. Shih, S. Cho, N. Ickes, R. Min, A. Sinha, A. Wang, A. Chandrakasan, Physical Layer Driven Protocol and Algorithm Design for Energy-Efficient Wireless Sensor Networks, in: Proceedings of 7th ACM International Conference on Mobile Computing and Networking (Mobicom'01), 2001, pp. 272-287. pp. 272-287.
[56] R. Srikant, R. Agrawal, Mining Sequential Patterns: Generalizations And Performance Improvements, in: Proceedings of the 5th International Conference on Extending Database Technology (EDBT'06), 1996
[57] Z. Su, Q. Yang, Y. Lu, and H. Zhang, "WhatNext: A Prediction System for Web Requests Using N-gram Sequence Models," in Proc. First Int. Conf. Web Information Systems and Engineering, 2000, pp 200-207.
[58] P. N. Tan and V. Kumar, "Mining Indirect Associations in Web Data," in Proc. WebKDD 2001:00:00 KDD Workshop on Web Mining and Web Usage Analysis, 2001, pp 145-166
[59] The World Wide Web Consortium, "Composite Capability/Preference Profiles (CC/PP): A user side framework for content negotiation," http://www.w3.org/TR/NOTE-CCPP/, 1999
[60] S. M. Tseng and W. C. Chan, "Mining Complete User Moving Paths in a Mobile Environment," in Proc. Int. Workshop on Databases and Software Engineering (held with ICS), 2002
[61] S. M. Tseng and C. F. Tsui, "An Efficient Method for Mining Associated Service Patterns in Mobile Web Environments," in Proc. ACM Symp. on Applied Computing, 2003, pp. 455-459.
[62] S. M. Tseng and C. F. Tsui, "Mining Multi-Level and Location-Aware Associated Service Patterns in Mobile Web Environments," IEEE Trans. Syst., Man, Cybern., B, vol. 34, no. 6, 2004
[63] V.S. Tseng, K.W. Lin, Mining Temporal Moving Patterns in Object Tracking Sensor Networks, in: Proceedings of the International Workshop on Ubiquitous Data Management (held with ICDE'05), 2005, pp. 105-112.
[64] V.S. Tseng, K.W. Lin, Efficient Mining and Prediction of User Behavior Patterns in Mobile Web Systems", Information and Software Technology, to appear.
[65] Y. Wang, E. P. Lim and S. Y. Hwang, "Efficient Group Pattern Mining Using Data Summarization," in Proc. Database Systems for Advances Applications, 2004, pp. 895-907.
[66] WINS project, Rockwell Science Center. Available:
[67] A. Woo and D. Culler, A Transmission Control Scheme for Media Access in Sensor Networks, in: Proceedings of 7th ACM Annual International Conference on Mobile Computing and Networking (Mobicom'01), 2001, pp. 221-235.
[68] Y. Xu, J. Winter, W.C. Lee, Prediction-Based Strategies for Energy Saving in Object Tracking Sensor Networks, in: Proceedings of the 5th IEEE International Conference on Mobile Data Management (MDM'04), 2004, pp. 346-357.
[69] Q. Yang, T. Li, and K. Wang, Building Association Rule Based Sequential Classifiers for Web Document Prediction, Journal of Data Mining and Knowledge Discovery, vol. 8, no. 3, pp. 253-273, 2004
[70] G. Yavas, D. Katsaros, ?. Ulusoy, Y. Manolopoulos, A Data Mining Approach for Location Prediction in Mobile Environments, Data and Knowledge Engineering, vol.54, no.2, 2005
[71] W. Ye, J. Heidemann, D. Estrin, An Energy-Efficient MAC Protocol for Wireless Sensor Networks, in: Proceedings of the 21st IEEE Infocom, 2002, pp. 1567-1576.