基于数据挖掘的移动轨迹预测方法
|
摘要
随着无线技术的发展和各种无线应用,尤其是需要QoS(Quality of Service)支持的无线应用的兴起和普及,移动预测技术越来越受到重视。移动预测可以在很多方面对无线网络产生影响,包括减小移动主机在移动切换时的切换延迟;更好地实施无线网络中的接纳控制、流量控制;减少无线网络系统中的能量消耗和改进AdHoc网络的组播协议等。
本文分析了移动轨迹预测的已有方案,指出了各方案存在的问题,提出了一种基于数据挖掘的移动设备位置预测方法:MPP (Mobile Path Prediction Based on Pattern Mining and Matching),避免了K阶Markov预测器存在的状态空间膨胀的问题,并在若干个WLAN用户的移动跟踪数据集上对K阶Markov预测器和本文提出的新预测器的预测精度进行了比较分析。实验结果表明,本文提出的MPP方法能够达到比较理想的预测效果,接近目前预测精度最高的二阶Markov预测器的预测精度。MPP方法分为三个部分:(1)基本的移动模式挖掘;(2)增量移动模式挖掘;(3)基于模式匹配的移动预测。其中,增量挖掘的实现使得该方法能够随着移动数据的增加而实现移动模式的更新,从而具有较高的实用价值。
最后又提出了挖掘移动用户活动的时间规律,进而与空间移动模式相结合来进行移动路径预测、通过定义年轻系数来刻画移动路径的新旧性,在移动模式挖掘过程中偏重较近时间段内的历史信息进行挖掘等方案,对MPP方法进行了改进。
With the development of wireless technology and kinds of wireless applications, especially those need QoS support, mobility prediction techniques become more and more important.
Mobility prediction impacts greatly on different aspects of wireless networks including reducing handoff delay of mobile hosts, improving admission control and flow control in wireless networks, reducing energy consumption of wireless network, improving the multicast routing protocols, and so on. Now the research on mobility prediction includes two different directions:
one uses real time coordinates to make prediction with the assistance of GPS, while the other only uses user mobile history, which contains the sequence of APs the mobile host has associated with. The latter is the focus of this research paper. The main contents and conclusions in this dissertation can be summarized as follows:
Among mobility prediction models in WLAN, Markov models are important for mobility prediction because of their simplicity and quite good prediction accuracy. But high_orders have the problem of high state space complexity.
In fact, the mobility patterns are key factors in the mobility prediction problem. Therefore, the paper brings forward a new mobility prediction scheme based on data mining, especially on time sequence mining. At first, regular mobility patterns are picked out by using data mining techniques. Then by pattern matching, mobility prediction is made. In order to trace the newer mobility patterns, an incremental data mining technique is used to enhance the whole scheme, especially to improve its online prediction ability. Simulation experiments proved that the incremental data mining technique really promoted the prediction accuracy of the scheme.
This paper puts forward a new method for predicting the mobile path based on pattern mining and matching, called MPP. Firstly Divide the historical record of user information into several transactions, and thus form the visiting transaction database. Having been given the minimum supportive degree threshold, we designed the algorithm Mm to mine the mobile patterns. Secondly we designed the algorithm named Mmp for the prediction of mobile user’s future path.
Advantages of method MPP:
a) This method can get a better prediction result than that of method Markov, if only we do the measurement of the matching of current path and the pattern accurately, this is because in the method Mmp, we take consideration of all kinds of cases with different orders for the current path by means of repeated unreeling, not like the Markov, which just does the prediction with single order, here ,order stands for the number of nodes in current user path when doing the prediction;
b) The method MPP occupied a smaller status space than Markov, because the pattern database includes only a few patterns. while the order_2 or order_k (k>2) Markov predictor possesses the disadvantage of space inflation, which means the status space increases exponentially as the AP number goes up.
As the time goes by, new mobile record is added to historical database, so, some of the old user mobile patterns may no longer satisfy the minimum degree threshold and there will be new patterns come up ,therefore, the mined results must be updated at the same time, to reflect the dynamic updating of the mobile record database. How to make full use of the original mined results is very important to the improvement of efficiency of mining. Here we use the algorithm named PDIU to implement the incremental updating of pattern database, and only the frequent sequences, their supportive degrees and | D B .k| have to be stored, while there are not too many frequent sequences, so it takes a much smaller space. Better predicting precision is got after an incremental mining is implemented in pattern mining, and from the figure we can see it is equal with that of the order_2 Markov predictor. If we make the parameters more reasonable the predicting precision can be further improved. By implementing the incremental updating of the pattern database we improve the efficiency of calculation greatly avoiding mining the whole updated historical records database again.
For improving the efficiency of MPP, this paper puts forward the design that using the technique of projection in the arithmetic of Mm and PDIU. General idea is: Given a visiting transaction database D, through the first scan, we will get all the frequent 1_sequences, assume them to be a,b,c,d,e,f, then the complete set of frequent sequences can be partitioned into the following six disjoint subsets according to the six prefixes: the ones having prefix a;the ones having prefix b;……the ones having prefix f.To mine the ones with prefix a, we just have to scan part of D but not the whole D, and this part that needs to be scanned is got by projecting D with prefix a, we call it a_projected database. It is the same when we mine other frequent sequences.
With the development of Pervasive Computing and applications supporting wireless QoS, mobility prediction will become more and more important and contribute more to the future wireless networks. The results of the dissertation will contribute to the study on mobility prediction algorithms and its applications.
本文分析了移动轨迹预测的已有方案,指出了各方案存在的问题,提出了一种基于数据挖掘的移动设备位置预测方法:MPP (Mobile Path Prediction Based on Pattern Mining and Matching),避免了K阶Markov预测器存在的状态空间膨胀的问题,并在若干个WLAN用户的移动跟踪数据集上对K阶Markov预测器和本文提出的新预测器的预测精度进行了比较分析。实验结果表明,本文提出的MPP方法能够达到比较理想的预测效果,接近目前预测精度最高的二阶Markov预测器的预测精度。MPP方法分为三个部分:(1)基本的移动模式挖掘;(2)增量移动模式挖掘;(3)基于模式匹配的移动预测。其中,增量挖掘的实现使得该方法能够随着移动数据的增加而实现移动模式的更新,从而具有较高的实用价值。
最后又提出了挖掘移动用户活动的时间规律,进而与空间移动模式相结合来进行移动路径预测、通过定义年轻系数来刻画移动路径的新旧性,在移动模式挖掘过程中偏重较近时间段内的历史信息进行挖掘等方案,对MPP方法进行了改进。
With the development of wireless technology and kinds of wireless applications, especially those need QoS support, mobility prediction techniques become more and more important.
Mobility prediction impacts greatly on different aspects of wireless networks including reducing handoff delay of mobile hosts, improving admission control and flow control in wireless networks, reducing energy consumption of wireless network, improving the multicast routing protocols, and so on. Now the research on mobility prediction includes two different directions:
one uses real time coordinates to make prediction with the assistance of GPS, while the other only uses user mobile history, which contains the sequence of APs the mobile host has associated with. The latter is the focus of this research paper. The main contents and conclusions in this dissertation can be summarized as follows:
Among mobility prediction models in WLAN, Markov models are important for mobility prediction because of their simplicity and quite good prediction accuracy. But high_orders have the problem of high state space complexity.
In fact, the mobility patterns are key factors in the mobility prediction problem. Therefore, the paper brings forward a new mobility prediction scheme based on data mining, especially on time sequence mining. At first, regular mobility patterns are picked out by using data mining techniques. Then by pattern matching, mobility prediction is made. In order to trace the newer mobility patterns, an incremental data mining technique is used to enhance the whole scheme, especially to improve its online prediction ability. Simulation experiments proved that the incremental data mining technique really promoted the prediction accuracy of the scheme.
This paper puts forward a new method for predicting the mobile path based on pattern mining and matching, called MPP. Firstly Divide the historical record of user information into several transactions, and thus form the visiting transaction database. Having been given the minimum supportive degree threshold, we designed the algorithm Mm to mine the mobile patterns. Secondly we designed the algorithm named Mmp for the prediction of mobile user’s future path.
Advantages of method MPP:
a) This method can get a better prediction result than that of method Markov, if only we do the measurement of the matching of current path and the pattern accurately, this is because in the method Mmp, we take consideration of all kinds of cases with different orders for the current path by means of repeated unreeling, not like the Markov, which just does the prediction with single order, here ,order stands for the number of nodes in current user path when doing the prediction;
b) The method MPP occupied a smaller status space than Markov, because the pattern database includes only a few patterns. while the order_2 or order_k (k>2) Markov predictor possesses the disadvantage of space inflation, which means the status space increases exponentially as the AP number goes up.
As the time goes by, new mobile record is added to historical database, so, some of the old user mobile patterns may no longer satisfy the minimum degree threshold and there will be new patterns come up ,therefore, the mined results must be updated at the same time, to reflect the dynamic updating of the mobile record database. How to make full use of the original mined results is very important to the improvement of efficiency of mining. Here we use the algorithm named PDIU to implement the incremental updating of pattern database, and only the frequent sequences, their supportive degrees and | D B .k| have to be stored, while there are not too many frequent sequences, so it takes a much smaller space. Better predicting precision is got after an incremental mining is implemented in pattern mining, and from the figure we can see it is equal with that of the order_2 Markov predictor. If we make the parameters more reasonable the predicting precision can be further improved. By implementing the incremental updating of the pattern database we improve the efficiency of calculation greatly avoiding mining the whole updated historical records database again.
For improving the efficiency of MPP, this paper puts forward the design that using the technique of projection in the arithmetic of Mm and PDIU. General idea is: Given a visiting transaction database D, through the first scan, we will get all the frequent 1_sequences, assume them to be a,b,c,d,e,f, then the complete set of frequent sequences can be partitioned into the following six disjoint subsets according to the six prefixes: the ones having prefix a;the ones having prefix b;……the ones having prefix f.To mine the ones with prefix a, we just have to scan part of D but not the whole D, and this part that needs to be scanned is got by projecting D with prefix a, we call it a_projected database. It is the same when we mine other frequent sequences.
With the development of Pervasive Computing and applications supporting wireless QoS, mobility prediction will become more and more important and contribute more to the future wireless networks. The results of the dissertation will contribute to the study on mobility prediction algorithms and its applications.
引文
[1] IEEE .Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Speci_cations[M]. IEEE Standard 802.11, 1999.
[2]余雪岗,刘衍珩.无线局域网中的移动预测研究及应用[D]. 2007年12月http://dlib.cnki.net/kns50/detail.aspx?dbname=CDFD2008&filename=2008020306.nh&filetitle=%e6%97%a0%e7%ba%bf%e5%b1%80%e5%9f%9f%e7%bd%91%e4%b8%ad%e7%9a%84%e7%a7%bb%e5%8a%a8%e9%a2%84%e6%b5%8b%e7%a0%94%e7%a9%b6%e5%8f%8a%e5%ba%94%e7%94%a8.
[3] H. Kim, J. Jung. A mobility prediction handover algorithm for effective channelassignment in wireless ATM[C]. In Proceedings of the 2001 Global Telecommunications Conference. 2001, 6: 3673-3680.
[4] Fei Yu, Victor Leung. Mobility-based predictive call admission control and bandwidth reservation in wireless cellular networks[J]. Computer Networks: The International Journal of Computer and Telecommunications Networking. 2002, 38(5): 577-589.
[5] W. S. Soh and H. S. Kim. Dynamic bandwidth reservation in cellular networks using road topology based mobility prediction[J]. IEEE INFOCOM. 2004, 4: 2766-2777.
[6] A. Aljadhai and TF Znati. Predictive mobility support for QoS provisioning in mobile wireless environments[J]. IEEE JSAC. 2001, 19(10): 1915-1930.
[7] S. Chakraborty, Y. Dong, DKY Yau and JCS Lui. On the effectiveness of movement prediction to reduce energy consumption in wireless communication[J]. IEEE Transactions on Mobile Computing. 2006, 5(2): 157-169.
[8] S. J. Lee, W. Su and M. Gerla. Ad hoc Wireless Multicast with Mobility Prediction[C]. In Proceedings of IEEE ICCCN’99. 1999: 4-9.
[9] N. Marmasse and C. Schmandt. A User-Centered Location Model. Personal and Ubiquitous Computing[J]. 2002, 6(5-6): 318-321.
[10]Z. R. Zaidi and B. L. Mark. Mobility estimation based onan autoregressive model[J]. IEEE Transactions. on Vehicular Technology. 2005.
[11]Park MH, Hong JH, Cho SB. Two-stage user mobility modeling for intention prediction for location-based services[J]. Lect. Notes Comput. Sci. 4224. 2006: 538-545.
[12]Wee-Seng Soh, Hyong S. Kim. QoS Provisioning in Cellular Networks Based on Mobility Prediction Techniques[C]. In Proceedings of World Telecommunications Congress 2002(WTC2002). 2002: 86-92.
[13]Shiang-Chun Liou , Yueh-Min Huang. Trajectory Predictions in Mobile Networks[J]. International Journal of Information Technology. 2005, 11(11): 109-122.
[14]J. Chan, S. Zhou and A. Seneviratne. A QoS Adaptive Mobility Prediction Scheme for Wireless Networks[C]. In Proceedings of IEEE GLOBECOM’98. 1998: 1414-1419.
[15]Amiya Bhattacharya, Sajal K Das. LeZi-Update: An information-theoretic approach to track mobile users in PCS networks[J]. ACM/Kluwer Wireless Networks. 2002, 8(2-3):121-135.
[16]J. G. Cleary and W. J. Teahan. Unbounded length contexts for PPM[J]. The Computer Journal. 1997, 40(2/3): 67-75.
[17]Philippe Jacquet, Wojciech Szpankowski, Izydor Apostol. An universal predictor based on pattern matching] [J]. IEEE Transactions on Information Theory. 2002, 48(6): 1462-1472.
[18]Christine Cheng, Ravi Jain, Eric Van Den Berg. Location prediction algorithms for mobile wireless systems[M]. Wireless internet handbook: technologies, standards, and application. CRC Press, 2003: 245-263.
[19]Libo Song, David Kotz, Ravi Jain, and Xiaoning He. Evaluating location predictors with extensive Wi-Fi mobility data[C]. In Proceedings of INFOCOM. 2004, 2: 1414-1424.
[20]Wen-Chih Peng, Ming-Syan Chen. Mining user moving patterns for personal data allocation in a mobile computing system[C]. In Proceedings of the2000 International Conference on Parallel Processing. 2000: 573-580.
[21]R. DeVaul, M. Sung, J. Gips and A. Pentland. Mithril 2003: Applications and Architecture[C]. In Proceedings of Seventh IEEE Int’l Symp on Wearable Computers. 2003: 4-11.
[22]N. Samaan and A. Karmouch. A mobility prediction architecture based on contextual knowledge and spatial conceptual maps[J]. IEEE Transactions on Mobile Computing. 2005, 4: 537-551.
[23]M. Deshpande and G. Karypis. Selective Markov models for predicting Web-page accesses[J]. ACM Transactions on Internet Technology. 2000, 4(2): 163-184.
[24]J. Pitkow, P. Pirolli. Mining longest repeating subsequences to predict world wide web surfing[C]. In Proceedings of 2nd USENIX Symposium on Internet Technologies and Systems. 1999: 139-150.
[25]Yu XG, Liu YH. Hybrid markov models used for path prediction[C]. In Proceedings of 15th International Conference on Computer Communications and Networks 2006, ICCCN 2006: 374-379.
[26]Cheung D. W. Maintenance of Discovered Association Rules in LargeDatabases: An Incremental Updating Technique[C]. In Proceedings of 12th Int. Conf. on Data Engineering. 1996: 106-114.
[27]冯玉才,冯剑琳.关联规则的增量式更新算法[J].软件学报, 1998, 9(4): 301-306.
[28]商志会,陶树平.一种高效的关联规则增量更新算法[J].计算机应用, 2005, 25(4): 830-832.
[29]Chang H L, Cheng R L, Ming S C. Sliding Window Filter: An Efficient Method for Incremental Mining on a Time-variant Database[J]. Information Systems. 2005, 30(3): 227-244.
[30]Ayan N F, Tansel A U, Arkun E. An efficient algorithm to update large itemsets with early pruning[C]. In Proceedings of 5th ACM SIGKDD Intl Conf on Knowledge Discovery and Data Mining. 1999: 287-291.
[31]Li Hao, Li Shan. A Newly FUP-Based Incremental Updating Algorithm ofAssociation Rules[J]. Computer Engineering & Science. 2005, 27(7): 74-76.
[32]Ni Weiwei, Zhou Xiaoyun, Gu Yu and Sun Zhihui. Research and Implementation of an Improved Updating Algorithm for Mining Association Rules[J]. Computer Engineering & Application. 2004, 18:174-176.
[33]田明,刘衍珩,余雪岗等.基于局部信息的WLAN位置预测器[J].计算机应用, 2006, 26(12): 2813-2816.
[34]Pei, J., Han, J., Mortazavi-Asl, B., Pinto, H., Chen, Q., Dayal, U., and Hsu, M.-C. 2001. PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth[C]. In Proceedings of the 2001 Int. Conf. Data Engineering (ICDE’01), Heidelberg, Germany. 2001: 215-224.
[2]余雪岗,刘衍珩.无线局域网中的移动预测研究及应用[D]. 2007年12月http://dlib.cnki.net/kns50/detail.aspx?dbname=CDFD2008&filename=2008020306.nh&filetitle=%e6%97%a0%e7%ba%bf%e5%b1%80%e5%9f%9f%e7%bd%91%e4%b8%ad%e7%9a%84%e7%a7%bb%e5%8a%a8%e9%a2%84%e6%b5%8b%e7%a0%94%e7%a9%b6%e5%8f%8a%e5%ba%94%e7%94%a8.
[3] H. Kim, J. Jung. A mobility prediction handover algorithm for effective channelassignment in wireless ATM[C]. In Proceedings of the 2001 Global Telecommunications Conference. 2001, 6: 3673-3680.
[4] Fei Yu, Victor Leung. Mobility-based predictive call admission control and bandwidth reservation in wireless cellular networks[J]. Computer Networks: The International Journal of Computer and Telecommunications Networking. 2002, 38(5): 577-589.
[5] W. S. Soh and H. S. Kim. Dynamic bandwidth reservation in cellular networks using road topology based mobility prediction[J]. IEEE INFOCOM. 2004, 4: 2766-2777.
[6] A. Aljadhai and TF Znati. Predictive mobility support for QoS provisioning in mobile wireless environments[J]. IEEE JSAC. 2001, 19(10): 1915-1930.
[7] S. Chakraborty, Y. Dong, DKY Yau and JCS Lui. On the effectiveness of movement prediction to reduce energy consumption in wireless communication[J]. IEEE Transactions on Mobile Computing. 2006, 5(2): 157-169.
[8] S. J. Lee, W. Su and M. Gerla. Ad hoc Wireless Multicast with Mobility Prediction[C]. In Proceedings of IEEE ICCCN’99. 1999: 4-9.
[9] N. Marmasse and C. Schmandt. A User-Centered Location Model. Personal and Ubiquitous Computing[J]. 2002, 6(5-6): 318-321.
[10]Z. R. Zaidi and B. L. Mark. Mobility estimation based onan autoregressive model[J]. IEEE Transactions. on Vehicular Technology. 2005.
[11]Park MH, Hong JH, Cho SB. Two-stage user mobility modeling for intention prediction for location-based services[J]. Lect. Notes Comput. Sci. 4224. 2006: 538-545.
[12]Wee-Seng Soh, Hyong S. Kim. QoS Provisioning in Cellular Networks Based on Mobility Prediction Techniques[C]. In Proceedings of World Telecommunications Congress 2002(WTC2002). 2002: 86-92.
[13]Shiang-Chun Liou , Yueh-Min Huang. Trajectory Predictions in Mobile Networks[J]. International Journal of Information Technology. 2005, 11(11): 109-122.
[14]J. Chan, S. Zhou and A. Seneviratne. A QoS Adaptive Mobility Prediction Scheme for Wireless Networks[C]. In Proceedings of IEEE GLOBECOM’98. 1998: 1414-1419.
[15]Amiya Bhattacharya, Sajal K Das. LeZi-Update: An information-theoretic approach to track mobile users in PCS networks[J]. ACM/Kluwer Wireless Networks. 2002, 8(2-3):121-135.
[16]J. G. Cleary and W. J. Teahan. Unbounded length contexts for PPM[J]. The Computer Journal. 1997, 40(2/3): 67-75.
[17]Philippe Jacquet, Wojciech Szpankowski, Izydor Apostol. An universal predictor based on pattern matching] [J]. IEEE Transactions on Information Theory. 2002, 48(6): 1462-1472.
[18]Christine Cheng, Ravi Jain, Eric Van Den Berg. Location prediction algorithms for mobile wireless systems[M]. Wireless internet handbook: technologies, standards, and application. CRC Press, 2003: 245-263.
[19]Libo Song, David Kotz, Ravi Jain, and Xiaoning He. Evaluating location predictors with extensive Wi-Fi mobility data[C]. In Proceedings of INFOCOM. 2004, 2: 1414-1424.
[20]Wen-Chih Peng, Ming-Syan Chen. Mining user moving patterns for personal data allocation in a mobile computing system[C]. In Proceedings of the2000 International Conference on Parallel Processing. 2000: 573-580.
[21]R. DeVaul, M. Sung, J. Gips and A. Pentland. Mithril 2003: Applications and Architecture[C]. In Proceedings of Seventh IEEE Int’l Symp on Wearable Computers. 2003: 4-11.
[22]N. Samaan and A. Karmouch. A mobility prediction architecture based on contextual knowledge and spatial conceptual maps[J]. IEEE Transactions on Mobile Computing. 2005, 4: 537-551.
[23]M. Deshpande and G. Karypis. Selective Markov models for predicting Web-page accesses[J]. ACM Transactions on Internet Technology. 2000, 4(2): 163-184.
[24]J. Pitkow, P. Pirolli. Mining longest repeating subsequences to predict world wide web surfing[C]. In Proceedings of 2nd USENIX Symposium on Internet Technologies and Systems. 1999: 139-150.
[25]Yu XG, Liu YH. Hybrid markov models used for path prediction[C]. In Proceedings of 15th International Conference on Computer Communications and Networks 2006, ICCCN 2006: 374-379.
[26]Cheung D. W. Maintenance of Discovered Association Rules in LargeDatabases: An Incremental Updating Technique[C]. In Proceedings of 12th Int. Conf. on Data Engineering. 1996: 106-114.
[27]冯玉才,冯剑琳.关联规则的增量式更新算法[J].软件学报, 1998, 9(4): 301-306.
[28]商志会,陶树平.一种高效的关联规则增量更新算法[J].计算机应用, 2005, 25(4): 830-832.
[29]Chang H L, Cheng R L, Ming S C. Sliding Window Filter: An Efficient Method for Incremental Mining on a Time-variant Database[J]. Information Systems. 2005, 30(3): 227-244.
[30]Ayan N F, Tansel A U, Arkun E. An efficient algorithm to update large itemsets with early pruning[C]. In Proceedings of 5th ACM SIGKDD Intl Conf on Knowledge Discovery and Data Mining. 1999: 287-291.
[31]Li Hao, Li Shan. A Newly FUP-Based Incremental Updating Algorithm ofAssociation Rules[J]. Computer Engineering & Science. 2005, 27(7): 74-76.
[32]Ni Weiwei, Zhou Xiaoyun, Gu Yu and Sun Zhihui. Research and Implementation of an Improved Updating Algorithm for Mining Association Rules[J]. Computer Engineering & Application. 2004, 18:174-176.
[33]田明,刘衍珩,余雪岗等.基于局部信息的WLAN位置预测器[J].计算机应用, 2006, 26(12): 2813-2816.
[34]Pei, J., Han, J., Mortazavi-Asl, B., Pinto, H., Chen, Q., Dayal, U., and Hsu, M.-C. 2001. PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth[C]. In Proceedings of the 2001 Int. Conf. Data Engineering (ICDE’01), Heidelberg, Germany. 2001: 215-224.