A framework based on sparse representation model for time series prediction in smart city

Abstract

Smart city driven by Big Data and Internet of Things (IoT) has become a most promising trend of the future. As one important function of smart city, event alert based on time series prediction is faced with the challenge of how to extract and represent discriminative features of sensing knowledge from the massive sequential data generated by IoT devices. In this paper, a framework based on sparse representation model (SRM) for time series prediction is proposed as an efficient approach to tackle this challenge. After dividing the over-complete dictionary into upper and lower parts, the main idea of SRMis to obtain the sparse representation of time series based on the upper part firstly, and then realize the prediction of future values based on the lower part. The choice of different dictionaries has a significant impact on the performance of SRM. This paper focuses on the study of dictionary construction strategy and summarizes eight variants of SRM. Experimental results demonstrate that SRM can deal with different types of time series prediction flexibly and effectively.

Keywords

sparse representation / smart city / time series prediction / dictionary construction

References

[1] Zheng Y. Urban computing: enabling urban intelligence with big data. Frontiers of Computer Science, 2017, 11(1): 1–3

[2] Su K, Li J, Fu H. Smart city and the applications. In: Proceedings of International Conference on Electronics, Communications and Control. 2011, 1028–1031

[3] Yi F, Yu Z, Chen H, Du H, Guo B. Cyber-physical-social collaborative sensing: from single space to cross-space. Frontiers of Computer Science, 2018, 12(4): 609–622

[4] Yu Z, Yi F, Lv Q, Guo B. Identifying on-site users for social events: mobility, content, and social relationship. IEEE Transactions on Mobile Computing, 2018, 17(9): 2055–2068

[5] Yu Z, Wang H, Guo B, Gu T, Mei T. Supporting serendipitous social interaction using human mobility prediction. IEEE Transactions on Human- Machine Systems, 2015, 45(6): 811–818

[6] Yu Z, Yu Z, Chen Y. Multi-hop mobility prediction. Mobile Networks and Applications, 2016, 21(2): 367–374

[7] Yu Z, Xu H, Yang Z, Guo B. Personalized travel package with multipoint- of-interest recommendation based on crowdsourced user footprints. IEEE Transactions on Human-Machine Systems, 2015, 46(1): 151–158

[8] Wang L, Yu Z, Guo B, Ku T, Yi F. Moving destination prediction using sparse dataset: a mobility gradient descent approach. ACM Transactions on Knowledge Discovery from Data, 2017, 11(3): 1–33

[9] Yu C N, Mirowski P, Ho T K. A sparse coding approach to household electricity demand forecasting in smart grids. IEEE Transactions on Smart Grid, 2016, 8(2): 738–748

[10] Fu T C. A review on time series data mining. Engineering Applications of Artificial Intelligence, 2011, 24(1): 164–181

[11] Zhang Z, Xu Y, Yang J, Li X, Zhang D. A survey of sparse representation: algorithms and applications. IEEE Access, 2015, 3: 490–530

[12] Fakhr MW. Online nonstationary time series prediction using sparse coding with dictionary update. In: Proceedings of IEEE International Conference on Information and Communication Technology Research. 2015, 112–115

[13] Rosas-Romero R, Díaz-Torres A, Etcheverry G. Forecasting of stock return prices with sparse representation of financial time series over redundant dictionaries. Expert Systems with Applications, 2016, 57: 37–48

[14] Helmi A, Fakhr MW, Atiya A F. Multi-step ahead time series forecasting via sparse coding and dictionary based techniques. Applied Soft Computing, 2018, 69: 464–474

[15] De Gooijer J G, Hyndman R J. 25 years of time series forecasting. International Journal of Forecasting, 2006, 22(3): 443–473

[16] Dijk D, Teräsvirta T, Franses P H. Smooth transition autoregressive models—a survey of recent developments. Econometric Reviews, 2002, 21(1): 1–47

[17] Anand N C, Scoglio C, Natarajan B. GARCH—non-linear time series model for traffic modeling and prediction. In: Proceedings of IEEE Network Operations and Management Symposium. 2008, 694–697

[18] Bontempi G, Taieb S, Borgne Y L. Business Intelligence. Berlin, Springer, 2013

[19] Ahmed N K, Atiya A F, Gayar N E, Shishiny H E. An empirical comparison of machine learning models for time series forecasting. Econometric Reviews, 2010, 29(5–6): 594–621

[20] Kumar M, Thenmozhi M. Forecasting stock index movement: a comparison of support vector machines and random forest. In: Proceedings of the 9th Capital Markets Conference on Indian Institute of Capital Markets. 2006, 1–16

[21] Längkvist M, Karlsson L, Loutfi A. A review of unsupervised feature learning and deep learning for time-series modeling. Pattern Recognition Letters, 2014, 42: 11–24

[22] Zheng J, Xu C, Zhang Z, Li X. Electric load forecasting in smart grids using long-short-term-memory based recurrent neural network. In: Proceedings of the 51st IEEE Annual Conference on Information Sciences and Systems. 2017, 1–6

[23] Fu R, Zhang Z, Li L. Using LSTM and GRU neural network methods for traffic flow prediction. In: Proceedings of the 31st IEEE Youth Academic Annual Conference of Chinese Association of Automation. 2016, 324–328

[24] Zhou G B, Wu J, Zhang C L, Zhou Z H. Minimal gated unit for recurrent neural networks. International Journal of Automation and Computing, 2016, 13(3): 226–234

[25] Guo W, Li J, Chen G, Niu Y, Chen C. A PSO-optimized real-time fault-tolerant task allocation algorithm in wireless sensor networks. IEEE Transactions on Parallel and Distributed Systems, 2014, 26(12): 3236–3249

[26] Ye D, Chen Z. A new approach to minimum attribute reduction based on discrete artificial bee colony. Soft Computing, 2015, 19(7): 1893–1903

[27] Qiu X, Zhang L, Ren Y, Suganthan P N, Amaratunga G. Ensemble deep learning for regression and time series forecasting. In: Proceedings of IEEE Symposium on Computational Intelligence in Ensemble Learning. 2014, 1–6

[28] Zhang G P. Time series forecasting using a hybrid ARIMA and neural network model. Neurocomputing, 2003, 50: 159–175

[29] Duan Z, Yang Y, Zhang K, Ni Y, Bajgain S. Improved deep hybrid networks for urban traffic flow prediction using trajectory data. IEEE Access, 2018, 6: 31820–31827

[30] Donoho D L. Compressed sensing. IEEE Transactions on Information Theory, 2006, 52(4): 1289–1306

[31] Lewicki M S, Sejnowski T J. Learning overcomplete representations. Neural Computation, 2000, 12(2): 337–365

[32] Wang S, Guo W. Sparse multigraph embedding for multimodal feature representation. IEEE Transactions on Multimedia, 2017, 19(7): 1454–1466

[33] Rubinstein R, Bruckstein A M, Elad M. Dictionaries for sparse representation modeling. Proceedings of the IEEE, 2010, 98(6): 1045–1057

[34] Batal I, Hauskrecht M. A supervised time series feature extraction technique using DCT and DWT. In: Proceedings of IEEE International Conference on Machine Learning and Applications. 2009, 735–739

[35] Stanković R S, Falkowski B J. The Haar wavelet transform: its status and achievements. Computers & Electrical Engineering, 2003, 29(1): 25–44

[36] Qayyum A, Malik A S, Naufal M, Saad M, Mazher M, Abdullah F, Abdullah T A R B T. Designing of overcomplete dictionaries based on DCT and DWT. In: Proceedings of IEEE Student Symposium in Biomedical Engineering & Sciences. 2015, 134–139

[37] Aharon M, Elad M, Bruckstein A. K-SVD: an algorithm for designing overcomplete dictionaries for sparse representation. IEEE Transactions on Signal Processing, 2006, 54(11): 4311–4322

[38] Ertugrul Ö F. Forecasting electricity load by a novel recurrent extreme learning machines approach. International Journal of Electrical Power & Energy Systems, 2016, 78: 429–435

[39] Natarajan B K. Sparse approximate solutions to linear systems. SIAM Journal on Computing, 1995, 24(2): 227–234

[40] Mallat S G, Zhang Z. Matching pursuits with time-frequency dictionaries. IEEE Transactions on Signal Processing, 1993, 41(12): 3397–3415

[41] Pati Y C, Rezaiifar R, Krishnaprasad P S. Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition. In: Proceedings of the 27th IEEE Asilomar Conference on Signals, Systems and Computers. 1993, 40–44

[42] Needell D, Tropp J A. CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis, 2009, 26(3): 301–321

[43] Donoho D L, Tsaig Y, Drori I, Starck J L. Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit. IEEE Transactions on Information Theory, 2012, 58(2): 1094–1121

[44] Dai W, Milenkovic O. Subspace pursuit for compressive sensing signal reconstruction. IEEE Transactions on Information Theory, 2009, 55(5): 2230–2249

[45] Karahanoglu N B, Erdogan H. Compressed sensing signal recovery via forward–backward pursuit. Digital Signal Processing, 2013, 23(5): 1539–1548

[46] Donoho D L. For most large underdetermined systems of linear equations the minimal l₁-norm solution is also the sparsest solution. Communications on Pure and Applied Mathematics, 2006, 59(6): 797–829

[47] Chen S S, Donoho D L, Saunders M A. Atomic decomposition by basis pursuit. SIAM Review, 2001, 43(1): 129–159

[48] Efron B, Hastie T, Johnstone I, Tibshirani R. Least angle regression. The Annals of Statistics, 2004, 32(2): 407–499

[49] Figueiredo MA T, Nowak R D, Wright S J. Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4): 586–597

[50] Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2009, 2(1): 183–202

[51] Qiu K, Dogandzic A. Variance-component based sparse signal reconstruction and model selection. IEEE Transactions on Signal Processing, 2010, 58(6): 2935–2952

[52] Guo S, Wang Z, Ruan Q. Enhancing sparsity via l_p (0<_p<1) minimization for robust face recognition. Neurocomputing, 2013, 99: 592–602

[53] Chartrand R. Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Processing Letters, 2007, 14(10): 707–710

[54] Zeng J, Xu Z, Zhang B, Hong W, Wu Y. Accelerated L_1/2 regularization based SAR imaging via BCR and reduced Newton skills. Signal Processing, 2013, 93(7): 1831–1844

[55] Foucart S, Lai M J. Sparsest solutions of underdetermined linear systems via l_q-minimization for 0<q≤1. Applied and Computational Harmonic Analysis, 2009, 26(3): 395–407

[56] Daubechies I, DeVore R, Fornasier M, Güntürk C S. Iteratively reweighted least squares minimization for sparse recovery. Communications on Pure and Applied Mathematics, 2010, 63(1): 1–38

[57] Xu Z, Chang X, Xu F, Zhang H. L1/2 regularization: a thresholding representation theory and a fast solver. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(7): 1013–1027

[58] Chen B J, Chang M, Lin C J. Load forecasting using support vector machines: a study on EUNITE competition 2001. IEEE Transactions on Power Systems, 2004, 19(4): 1821–1830

[59] Makridakis S, Hibon M. The M3-Competition: results, conclusions and implications. International Journal of Forecasting, 2000, 16(4): 451–476

[60] Makridakis S, Spiliotis E, Assimakopoulos V. The accuracy of machine learning (ML) forecasting methods versus statistical ones: extending the results of the M3-Competition. Working Paper, University of Nicosia, Institute for the Future, Greece, 2017

[61] Makridakis S, Spiliotis E, Assimakopoulos V. Statistical and machine learning forecasting methods: concerns and ways forward. PloS One, 2018, 13(3): e0194889

[62] Taieb S B, Atiya A F. A bias and variance analysis for multistep-ahead time series forecasting. IEEE Transactions on Neural Networks and Learning Systems, 2015, 27(1): 62–76

RIGHTS & PERMISSIONS

Higher Education Press