:::

詳目顯示

回上一頁
題名:大量時間序列之預測與叢聚分析
作者:瑪 莎
作者(外文):Ashouri, Mahsa
校院名稱:國立清華大學
系所名稱:服務科學研究所
指導教授:徐茉莉
學位類別:博士
出版日期:2019
主題關鍵詞:10時間序列預測與集群基於模型的分區樹線性回歸ARIMAETS分層預測分組預測協調預測10Time seriesForecastingClusteringModel-based partitioning treeLinear regressionARIMAETSHierarchical forecastingGrouped forecastingReconciling forecast
原始連結:連回原系統網址new window
相關次數:
  • 被引用次數被引用次數:期刊(0) 博士論文(0) 專書(0) 專書論文(0)
  • 排除自我引用排除自我引用:0
  • 共同引用共同引用:0
  • 點閱點閱:2
本論文主要聚焦於兩個與時間序列大集合分析的主要主題:預測(forecasting)與集群(clustering)。我們首先提出一個快速且易於使用的普通最小二乘線性回歸(OLS-LR)模型,該模型在應用於預測時間序列的大量集合時,可以很好地近似於諸如自回歸積分移動平均(ARIMA)、指數平滑(ETS)、和狀態空間模型等更複雜的方法。本論文使用此OLS-LR模型作為幾種預測和集群時間序列方法的基礎。
此OLS-LR模型可用於分別預測每個時間序列,也可透過預處理(如資料清理和集群)作為單一模型用以預測多個時間序列。在本論文中,我們使用OLS-LR模型來預測多個短時間序列(short time series)。這個的方法將所有序列組合在一起,並使用單一估計模型(estimated model)分別預測每個序列。為了演示和評估這著方法,我們針對臺灣每所學校的一年級學生人數進行建模。利用2014年之前的資料,我們為2015-2019年間臺灣每所學校一年級教室每年的數量建立了預測模型。
接下來,我們採用OLS-LR模型來預測分層和分組時間序列。預測分層時間序列或分組時間序列包括兩個步驟:計算基本預測和調整預測,以使分解序列的值加起來成為相應的聚合值。基本預測可以透過普遍的時間序列預測方法(例如ETS和ARIMA模型)進行計算。對帳步驟(reconciliation step)則是一個可調整基本預測的線性過程,以確保它們的一致性。然而,因為每個模型必須針對每個序列進行數值優化,當要預測的序列數量龐大時,使用ETS或ARIMA進行基本預測可能會在計算上面臨挑戰。我們提出一種基於OLS-LR模型的解決方案以避免此計算問題,並且使用單步法(single-step approach)來獲得已對帳的預測結果,而非一般情況下的兩步法(two-step approach)。本論文所提出的方法透過允許合併外部資料和處理缺失值增加了靈活性,並使用兩個資料集來進行演示:澳大利亞每月的國內旅遊和每日Wikipedia頁面的流覽量。本論文比較了使用ETS和ARIMA進行對帳的方法,發現我們所提出的方法速度更快,且具備相近的預測準確性。
為了對許多時間序列進行集群,我們提出了一套奠基於OLS-LR模型的兩種新方法,以擷取時間資訊(如趨勢,季節性和自相關)以及與領域相關(domain-relevant)的橫斷面屬性(cross-sectional attributes)。這些方法基於模型的分區(MOB)樹,可以作為對大量時間序列進行集群的自動化但透明的工具。我們提出了單步法和兩步法。單步法使用單一OLS-LR模型、使用趨勢、季節性、時間序列延遲(lag)和領域相關的橫斷面屬性對序列進行集群。兩步法則先根據趨勢、季節性和與領域相關的橫斷面屬性進行集群,然後通過自相關和與領域相關的橫斷面屬性對殘差序列進行進一步的集群。兩種方法均能產生可由領域專家解釋的集群。我們透過考量Wikipedia文章綜合流覽量時間序列的預測應用來演示所提出的集群方法的有用性。我們比較所提出的集群方法與替代方法,顯示基於樹的方法(tree-based approach)所產生的預測結果與適用於各個序列的ARIMA模型相當,但預測速度更快且效率更高,因此適合於擴展到大量的時間序列。此外,我們的方法也產生可用以解釋時間序列簇生成的簡單參數預測模型。
In this thesis, we focus on two main topics related to the analysis of large collections of time series: forecasting and clustering. We start by proposing a fast and user-friendly Ordinary Least Squares Linear Regression (OLS-LR) model, which can be a good approximation for more complex methods such as Auto-regressive Integrated Moving Average (ARIMA), Exponential Smoothing (ETS) and state-space models, for forecasting large collections of time series. We use this OLS-LR model as the basis for several methods for forecasting and clustering time series.
This OLS-LR model can be used for forecasting each time series individually and also by some pre-processing (data cleaning and clustering) can be used as a single model for forecasting multiple time series. We use the OLS-LR model for forecasting many short time series. Our approach combines all the series together and uses a single estimated model to forecast each series individually. To illustrate and evaluate this approach we model the number of first grade students in each school in Taiwan. Using data until 2014, we developed a forecasting model for the annual number of first grade classrooms at each school in Taiwan in 2015-2019.
Next we adopt the OLS-LR model for forecasting hierarchical and grouped time series. Forecasting hierarchical or grouped time series involves two steps: computing base forecasts and reconciling the forecasts so that values of disaggregated series add up to the corresponding aggregated values. Base forecasts can be computed by popular time series forecasting methods such as ETS and ARIMA models. The reconciliation step is a linear process that adjusts the base forecasts to ensure they are coherent. However using ETS or ARIMA for base forecasts can be computationally challenging when there is a large number of series to forecast, as each model must be numerically optimized for each series. We propose a solution based on the OLS-LR model that avoids this computational problem, and uses a single-step approach to obtain the reconciled forecasts, rather than the usual two-step approach. The proposed method adds flexibility by allowing in incorporating external data and handling missing values. We illustrate our approach using two datasets: monthly Australian domestic tourism and daily Wikipedia pageviews. We compare our approach to reconciliation using ETS and ARIMA, and show that our approach is much faster while providing similar levels of forecast accuracy.
For clustering many time series we propose a set of two new methods based on the OLS-LR model that captures temporal information (trend, seasonality and autocorrelation) as well as domain-relevant cross-sectional attributes. The methods are based on model-based partitioning (MOB) trees and can be used as an automated yet transparent tool for clustering a large collection of time series. We propose a single-step approach and a two-step approach. The single-step method clusters series using trend, seasonality, time series lags and domain-relevant cross-sectional attributes, using a single OLS-LR model. The two-step method first clusters by trend, seasonality and domain-relevant cross-sectional attributes, and then further clusters the residuals series by autocorrelation and the domain-relevant cross-sectional attributes. Both methods produce clusters that are interpretable by domain experts. We illustrate the usefulness of the proposed clustering approaches by considering a forecasting application of Wikipedia article pageviews time series. We compare the proposed clustering approach to alternatives and show that the tree-based approach produces forecasts that are practically on par with ARIMA models fitted to the individual series, yet are significantly faster and more efficient, thereby suitable for scaling to large collections of time-series. Moreover, our method produces simple parametric forecasting models for interpretable clusters of time series.
- Akaike, H. (1998). Information theory and an extension of the maximum likelihood principle. In Selected Papers of Hirotugu Akaike, pages 199-213. Springer Series in Statistics (Perspectives in Statistics). Springer.
- Armstrong, J. S. (2001). Principles of forecasting: a handbook for researchers and practitioners, volume 30. Springer Science & Business Media.
- Ashouri, M., Cai, K., Lin, F., and Shmueli, G. (2018). Assessing the value of an information system for developing predictive analytics: The case of forecasting school-level demand in taiwan. Service Science, 10(1):58-75.
- Ashouri, M., Shmueli, G., and Sin, C.-Y. (2019). Tree-based methods for clustering time series using domain-relevant attributes. Journal of Business Analytics, pages 1-23.
- Abfalg, J., Kroegel, H.-P., Kroger, P., Kunath, P., Pryakhin, A., and Renz, M. (2006). Similarity search on time series based on threshold queries. In EDBT, pages 276-294. Springer.
- Athanasopoulos, G., Ahmed, R. A., and Hyndman, R. J. (2009). Hierarchical forecasts for australian domestic tourism. International Journal of Forecasting, 25(1):146- 166.
- Australia, T. R. (2005). Travel by australians, september quarter 2005. Tourism Australia.
- Berndt, D. J. and Clifford, J. (1994). Using dynamic time warping to and patterns in time series. In KDD workshop, volume 10, pages 359-370. Seattle.
- Bertrand, P. and Goupil, F. (2000). Descriptive statistics for symbolic data. In Analysis of symbolic data, pages 106-124. Springer.
- Bezdek, J. C. (2013). Pattern recognition with fuzzy objective function algorithms. Springer Science & Business Media.
- Bhargava, A. (1986). On the theory of testing for unit roots in observed time series. The Review of Economic Studies, 53(3):369-384.
- Bork, L. and Moller, S. V. (2015). Forecasting house prices in the 50 states using dynamic model averaging and dynamic model selection. International Journal of Forecasting, 31(1):63-78.
- Chen, L. and Ng, R. (2004). On the marriage of lp-norms and edit distance. In Proceedings of the Thirtieth international conference on Very large data bases-Volume 30, pages 792-803. VLDB Endowment.
- Chen, L., Ozsu, M. T., and Oria, V. (2005). Robust and fast similarity search for moving object trajectories. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pages 491-502. ACM.
- Chen, Y., Nascimento, M. A., Ooi, B. C., and Tung, A. K. (2007). Spade: On shapebased pattern detection in streaming time series. In Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on, pages 786-795. IEEE.
- Chow, G. C. (1960). Tests of equality between sets of coefficients in two linear regressions. Econometrica: Journal of the Econometric Society, pages 591-605.
- Coates, D. and Diggle, P. (1986). Tests for comparing two estimated spectral densities. Journal of Time Series Analysis, 7(1):7-20.
- Croston, J. D. (1972). Forecasting and stock control for intermittent demands. Journal of the Operational Research Society, 23(3):289-303.
- Dasu, T., Swayne, D. F., and Poole, D. (2005). Grouping multivariate time series: A case study. In Proceedings of the IEEE Workshop on Temporal Data Mining: Algorithms, Theory and Applications, in conjunction with the Conference on Data Mining, Houston, pages 25-32.
- Dauphin, Y. N., Fan, A., Auli, M., and Grangier, D. (2017). Language modeling with gated convolutional networks. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 933-941. JMLR. org.
- De Gooijer, J. G. and Hyndman, R. J. (2006). 25 years of time series forecasting. International journal of forecasting, 22(3):443-473.
- Diggle, P. J. (1990). Time series; a biostatistical introduction. Technical report.
- Ding, H., Trajcevski, G., Scheuermann, P., Wang, X., and Keogh, E. (2008). Querying and mining of time series data: experimental comparison of representations and distance measures. Proceedings of the VLDB Endowment, 1(2):1542-1552.
- Faloutsos, C., Ranganathan, M., and Manolopoulos, Y. (1994). Fast subsequence matching in time-series databases, volume 23. ACM.
- Fliedner, G. (2001). Hierarchical forecasting: issues and use guidelines. Industrial Management & Data Systems, 101(1):5-12.
- Flunkert, V., Salinas, D., and Gasthaus, J. (2017). Deepar: Probabilistic forecasting with autoregressive recurrent networks. arXiv preprint arXiv:1704.04110.
- Fokianos, K. and Promponas, V. J. (2012). Biological applications of time series frequency domain clustering. Journal of Time Series Analysis, 33(5):744-756.
- Fokianos, K. and Savvides, A. (2008). On comparing several spectral densities. Technometrics, 50(3):317-331.
- Frentzos, E., Gratsias, K., and Theodoridis, Y. (2007). Index-based most similar trajectory search. In Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on, pages 816-825. IEEE.
- Gfferon, A. (2017). Hands-on machine learning with Scikit-Learn and TensorFlow: concepts, tools, and techniques to build intelligent systems. " O'Reilly Media, Inc.".
- Giordano, F., Rocca, M. L., and Parrella, M. L. (2017). Clustering complex time-series databases by using periodic components. Statistical Analysis and Data Mining: The ASA Data Science Journal, 10(2):89-106.
- Granger, C. W. (1969). Investigating causal relations by econometric models and cross-spectral methods. Econometrica: Journal of the Econometric Society, pages 424-438.
- Gross, C. W. and Sohl, J. E. (1990). Disaggregation methods to expedite product line forecasting. Journal of Forecasting, 9(3):233-254.
- Hibon, M., Makridakis, S., and Ord, K. (1999). M3-competition. Retrieved October 14, 2016, https://flora.insead.edu/fichiersti_wp/inseadwp1999/99-70.pdf.
- Holan, S. H. and Ravishanker, N. (2018). Time series clustering and classification via frequency domain methods. Wiley Interdisciplinary Reviews: Computational Statistics, 10(6):e1444.
- Huang, N. E., Shen, Z., Long, S. R., Wu, M. C., Shih, H. H., Zheng, Q., Yen, N.-C., Tung, C. C., and Liu, H. H. (1998). The empirical mode decomposition and the hilbert spectrum for nonlinear and non-stationary time series analysis. In Proceedings of the Royal Society of London A: mathematical, physical and engineering sciences, volume 454, pages 903-995. The Royal Society.
- Hyndman, R. J., Ahmed, R. A., Athanasopoulos, G., and Shang, H. L. (2011). Optimal combination forecasts for hierarchical time series. Computational Statistics & Data Analysis, 55(9):2579-2589.
- Hyndman, R. J. and Athanasopoulos, G. (2014). Forecasting: principles and practice. OTexts.
- Hyndman, R. J. and Athanasopoulos, G. (2018). Forecasting: principles and practice. OTexts, Melbourne, Australia.
- Jacoby, W. G. (2000). Loess:: a nonparametric, graphical tool for depicting relationships between variables. Electoral Studies, 19(4):577-613.
- Jacques, J. and Preda, C. (2014). Functional data clustering: a survey. Advances in Data Analysis and Classi_cation, 8(3):231-255.
- Jank, W. and Shmueli, G. (2009). Studying heterogeneity of price evolution in ebay auctions via functional clustering. Handbook of information systems series: Business computing, pages 237-261.
- Jank, W. and Shmueli, G. (2010). Modeling online auctions, volume 91. John Wiley & Sons.
- Kahn, K. B. (1998). Revisiting top-down versus bottom-up forecasting. The Journal of Business Forecasting, 17(2):14.
- Kalpakis, K., Gada, D., and Puttagunta, V. (2001). Distance measures for effective clustering of arima time-series. In Data Mining, 2001. ICDM 2001, Proceedings IEEE International Conference on, pages 273-280. IEEE.
- Kaneko, T., Kameoka, H., Hiramatsu, K., and Kashino, K. (2017). Sequence-to-sequence voice conversion with similarity metric learned using generative adversarial networks. In INTERSPEECH, pages 1283-1287.
- Khadivi, P. and Ramakrishnan, N. (2016). Wikipedia in the tourism industry: Forecasting demand and modeling usage behavior. In AAAI'16 Proceedings of the Thirtieth AAAI Conference on Arti_cial Intelligence, pages 4016-4021.
- Kirshners, A. and Borisov, A. (2012). A comparative analysis of short time series processing methods. Information Technology and Management Science, 15(1):65-69.
- Kumar, M., Patel, N. R., and Woo, J. (2002). Clustering seasonality patterns in the presence of errors. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 557-563. ACM.
- Kunst, R. M. (2012). Econometric forecasting. Institute for Advanced Studies Vienna and University of Vienna. http://homepage. univie. ac. at/robert. kunst/progpres.pdf.
- Lee, A. J., Lin, M.-C., Kao, R.-T., and Chen, K.-T. (2010). An effective clustering approach to stock market prediction. In PACIS, page 54.
- Liao, T. W. (2005). Clustering of time series data|a survey. Pattern recognition, 38(11):1857-1874.
- Liu, H., Ni, Z., and Li, J. (2006). Time series similar pattern matching based on empirical mode decomposition. In Intelligent Systems Design and Applications, 2006. ISDA'06. Sixth International Conference on, volume 1, pages 644-648. IEEE.
- Liu, N., Ren, S., Choi, T.-M., Hui, C.-L., and Ng, S.-F. (2013). Sales forecasting for fashion retailing service industry: a review. Mathematical Problems in Engineering, 2013.
- Makridakis, S. and Hibon, M. (2000). The m3-competition: results, conclusions and implications. International journal of forecasting, 16(4):451-476.
- Mamula, M. (2015). Modelling and forecasting international tourism demand-evaluation of forecasting performance. International Journal of Business Administration, 6(3):102-112.
- Moller-Levet, C. S., Klawonn, F., Cho, K.-H., and Wolkenhauer, O. (2003). Fuzzy clustering of short time-series and unevenly distributed sampling points. In International Symposium on Intelligent Data Analysis, pages 330-340. Springer.
- Montgomery, D. C., Jennings, C. L., and Kulahci, M. (2015). Introduction to time series analysis and forecasting. John Wiley & Sons.
- Morandat, F., Hill, B., Osvald, L., and Vitek, J. (2012). Evaluating the design of the r language. In European Conference on Object-Oriented Programming, pages 104-131. Springer.
- Morse, M. D. and Patel, J. M. (2007). An effcient and accurate method for evaluating time series similarity. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data, pages 569-580. ACM.
- Ngueyep, R. and Serban, N. (2015). Large-vector autoregression for multilayer spatially correlated time series. Technometrics, 57(2):207-216.
- Nie, D., Fu, Y., Zhou, J., Fang, Y., and Xia, H. (2010). Time series analysis based on enhanced nlcs. In Information Sciences and Interaction Sciences (ICIS), 2010 3rd International Conference on, pages 292-295. IEEE.
- Papacharalampous, G. A., Tyralis, H., and Koutsoyiannis, D. (2017). Comparison of stochastic and machine learning methods for multi-step ahead forecasting of hydrological processes. Journal of Hydrology, 10.
- Paterson, M. and Dancik, V. (1994). Longest common subsequences. Mathematical Foundations of Computer Science 1994, pages 127-142.
- Pennings, C. L. and van Dalen, J. (2017). Integrated hierarchical forecasting. European Journal of Operational Research, 263(2):412-418.
- Rani, S. and Sikka, G. (2012). Recent techniques of clustering of time series data: a survey. International Journal of Computer Applications, 52(15).
- Rousseeuw, P. J. (1987). Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal of computational and applied mathematics, 20:53-65.
- Salinas, D., Flunkert, V., and Gasthaus, J. (2017). Deepar: Probabilistic forecasting with autoregressive recurrent networks. arXiv preprint arXiv:1704.04110.
- Schwarz, G. et al. (1978). Estimating the dimension of a model. The annals of statistics, 6(2):461-464.
- Shaw, C. and King, G. (1992). Using cluster analysis to classify time series. Physica D: Nonlinear Phenomena, 58(1-4):288-298.
- Shmueli, G. and Lichtendahl, K. C. (2016). Practical Time Series Forecasting with R: A Hands-On Guide. Axelrod Schnall Publishers.
- Shumway, R. H. (2003). Time-frequency clustering and discriminant analysis. Statistics & probability letters, 63(3):307-314.
- Sigmund, M. and Ferstl, R. (2019). Panel vector autoregression in r with the package panelvar. The Quarterly Review of Economics and Finance.
- Sims, C. A. (1980). Macroeconomics and reality. Econometrica: Journal of the Econometric Society, pages 1-48.
- Sutskever, I., Vinyals, O., and Le, Q. V. (2014). Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pages 3104-3112.
- Vlachos, M., Kollios, G., and Gunopulos, D. (2002). Discovering similar multidimensional trajectories. In Data Engineering, 2002. Proceedings. 18th International Conference on, pages 673-684. IEEE.
- Wagner, N., Michalewicz, Z., Schellenberg, S., Chiriac, C., and Mohais, A. (2011). Intelligent techniques for forecasting multiple time series in real-world systems. International Journal of Intelligent Computing and Cybernetics, 4(3):284-310.
- Weatherford, L. R. and Kimes, S. E. (2003). A comparison of forecasting methods for hotel revenue management. International Journal of Forecasting, 19(3):401-415.
- Wickramasuriya, S. L., Athanasopoulos, G., and Hyndman, R. J. (2018a). Optimal forecast reconciliation for hierarchical and grouped time series through trace minimization. Journal of the American Statistical Association, (just-accepted):1-45.
- Wickramasuriya, S. L., Athanasopoulos, G., and Hyndman, R. J. (2018b). Optimal forecast reconciliation for hierarchical and grouped time series through trace minimization. Journal of the American Statistical Association, (just-accepted):1-45.
- Witt, S. and Witt, C. (2000). Forecasting tourism demand: A review of empirical research. International Library of Critical Writings in Economics, 121(3):141-169.
- Xiong, Y. and Yeung, D.-Y. (2002). Mixtures of arma models for model-based time series clustering. In Data Mining, 2002. ICDM 2003. Proceedings. 2002 IEEE International Conference on, pages 717-720. IEEE.
- Yuksel, S. (2007). An integrated forecasting approach to hotel demand. Mathematical and Computer Modelling, 46(7):1063-1070.
- Zakhary, A., El Gayar, N., and Atiya, A. F. (2008). A comparative study of the pickup method and its variations using a simulated hotel reservation data. ICGST International Journal on Arti_cial Intelligence and Machine Learning, 8:15-21.
- Zeileis, A., Hothorn, T., and Hornik, K. (2008). Model-based recursive partitioning. Journal of Computational and Graphical Statistics, 17(2):492-514.
- Zeileis, A., Leisch, F., Hornik, K., and Kleiber, C. (2001). strucchange. an r package for testing for structural change in linear regression models.
- Zhang, L. and Zhang, B. (1997). A forward propagation learning algorithm of multilayered neural networks with feed-back connections. Journal of Software, 8(4):252-258.
- Zhou, P.-Y. and Chan, K. C. (2014). A model-based multivariate time series clustering algorithm. In Pacifc-Asia Conference on Knowledge Discovery and Data Mining, pages 805-817. Springer.
 
 
 
 
第一頁 上一頁 下一頁 最後一頁 top