臺灣博碩士論文加值系統

時間序列分割是目前資料挖掘問題的研究之一，近期研究上常關注於股票分析與巨量資料上，找出序列上的特徵或轉折點，使資料集可以更容易的分析和預測。其中PLR(Piecewise Linear Representation)被認為近期最經典的時間序列分割方法，其精準度極高，但也因此耗費了不少運算時間，尤其在巨量資料上分割的耗費時間會有著特別的顯著。為了應對這種狀況，本文提出了一個改善PLR的方法，不僅在執行時間上變快，也不讓其誤差比起PLR來的大。

在本研究中，我們引用了Feasible Space Window的概念，先在時間序列上找到一個可行性空間(feasible space)，在這可行性空間中使用PLR，最終輸出分割點集合，其特點是(1)加快執行時間，且誤差在可接受範圍上，(2)不需要等待完整資料即再進行分割，可直接在線上等待找到feasible space後進行分割。由實驗數據得到，其執行時間可比原方法PLR演算法來得快12倍，且其找出的分割點集合仍保有原始資料的趨勢。

Time series segmentation is one of the current research topics on data mining. As recent studies often apply time series segmentation in stocks analysis and big data processing, identifying the characteristics or turning points on the time series can effectively facilitate the analysis and forecast with the data set. Among a number of approaches to time series segmentation, PLR (Piecewise Linear Representation) has been regarded as the most classic one. It shows high accuracy, yet it takes considerable amount of time to conduct the algorithm, especially for big data segmentation. In view of such issue, this research proposes a solution which can not only improve the analysis efficiency with PLR, but also ensure that the result is within the error bound generated by PLR.

In this thesis, we propose a time series segmentation method called Piecewise Linear Representation based on Feasible Space (PLRFS). In this method, we find segmentation points based on feasible space as the time series data streaming in. The proposed method has two features. One is that it facilitates processing time with errors within an acceptable range, and the second is that the segmentation can be conducted as soon as a feasible space is located without collection of complete data. According to the experimental results, the proposed method only takes 1/12 of the processing time required by the original PLR algorithm. Moreover, the trend of original data can still be observed with the set of segment points generated by the proposed method.

第一章 緒論..............................................1
1.1 研究背景與動機...................................1
1.2 研究問題與目的...................................2
1.3 研究貢獻.........................................3
第二章 相關研究..........................................5
2.1 Piecewise Linear Representation演算法...........5
2.2 Maximum Vertical Distance and Segmentation
Criterion演算法.................................8
2.3 Feasible Space Window演算法....................10
2.4 Piecewise Linear Representation演算法後續研究...13
2.4.1 Change Point based Piecewise Linear
Representation演算法.....................13
2.4.2 Trend-Based Segmentation Method演算法....16
2.4.3 Piecewise Linear Representation based on
angle between lines演算法................18
第三章 Piecewise Linear Representation based on Feasible
Space...........................................21
3.1 問題定義與問題描述...............................21
3.2 Piecewise Linear Representation based on Feasible
Space演算法....................................21
3.2.1找尋可行性空間.............................22
3.2.2找尋分割點.................................26
3.2.3 PLRFS演算法介紹與描述......................27
第四章 系統實作與實驗....................................33
4.1 系統實作環境....................................33
4.2 實驗設計與目的..................................33
4.3 實驗結果分析與討論...............................35
第五章 結論與未來研究方向................................44
5.1 結論...........................................44
5.2 未來研究方向....................................44
參考文獻 ..............................................46

一、英文部分
[1] Danyang CAO,Yuan TIAN,Donghui BAI,“Representation
of Time Series Based on Angle Between Lines,
”Journal of Computational information Systems,
pp.8191–8200,2014.
[2] Jingyi Du,Lu Wang,“Sensor Fault Diagnosis Based
on a New Method of Feature Extraction in Time-
series,”2010 2nd International Conference on
Information Science and Engineering (ICISE),
pp.1-3,Dec.4-6,2010.
[3] Tak-chung Fu,“A review on time series data
mining,”Engineering Applications of Artificial
Intelligence 24,pp.164-181,2011.
[4] Xian-ping Ge,“Pattern Matching in Financial Time
Series Data,” final project report for ICS,1998.
[5] Pengtao Jia,Huacan He1,Tao Sun,“Error Restricted
Piecewise Linear Representation of Time Series
Based on Special Points,”Intelligent Control and
Automation, 2008. WCICA 2008. 7th World Congress
on,Chongqing,China,pp.2059-2064,June.25-27,2008.
[6] E. J. Keogh,et al,“An Online Algorithm for
Segmenting Time Series,”In proceeding of IEEE
International Conference on Data Mining,pp.289-
296,Nov.29-Dec.2,2001.
[7] E. J. Keogh,K. Chakrabarti,M. J. Pazzani,S.
Mehrotra,“Dimensionality reduction for fast
similarity search in large time series databases
,”Knowledge and Information Systems,2001,pp.263-
286.
[8] E. Keogh et al.,“Segmenting Time Series: A Survey
and Novel Approach,”Data mining in time series
databases ,2004,pp.1-22.
[9] Xiaoyan Liu,Member,Zhenjiang Lin,and Huaiqing
Wang,“Novel Online Methods for Time Series
Segmentation,”IEEE Transactions on Knowledge and
Data Engineering ,(Volume:20,Issue:12),pp.1616-
1626,Feb.2,2008.
[10] Sharpe, W. F.“A Linear Programming Approximation
for the General Analysis Problem,?The Journal of
Financial and Quantitative Analysis Vol.6 No.5
,pp.1263-1275,1971.
[11] Huanmei Wu,Betty Salzberg,Donghui Zhang,“Online
Event-driven Subsequence Matching over Financial
Data Streams,” SIGMOD ''04 Proceedings of the
2004 ACM SIGMOD international conference on
Management of data,2004.
[12] Jheng-Long Wu,Pei-Chann Chang,“A Trend-Based
Segmentation Method and the Support Vector
Regression for Financial Time Series
Forecasting,” Mathematical Problems in
Engineering Volume 2012,20pages,2012.
[13] Changfeng Yan,Jianfang Fang,Lixiao Wu,Shimin
Ma,“An Approach of Time Series Piecewise Linear
Representation Based on Local Maximum Minimum
and Extremum,”Journal of Information &
Computational Science 10:9,pp.2747-2756,2013.

二、中文部分
[14] 弓晉麗,彭賢武,城市道路交通流时间序列模式相似性分析,公
路交通 科技Vol.30 No.11,2013,pp.119-123.
[15] 方如果,基於相似性分析的時間序列數據挖掘算法,浙江大學碩
士論文,pp.19-24,2011.
[16] 林俊宇,建構動態時間校正結合線段切割法於股價買賣點之預
測,元智大學碩士論文,2008.
[17] 張曉青,建構智慧型線段切割法於股價買賣點之預測,元智大學
碩士論文,2007.
[18] 許徽,張劍英,陳娟,趙志凱,基於分段線性方法的瓦斯濃度时
间序列模式表示,工礦自動化第八期,2010,pp.41-44.
[19] 黃俞翔,結合交易點預測之動態投資組合管理系統,中央大學碩
士論文,2013.

三、Electronic Resources
[20] ACADIS Gateway: An Arctic Data Repository
https://www.aoncadis.org/home.htm
[21] Data - EnerNOC Open :: We <3 Energy
http://open.enernoc.com/data/
[22] Western Regional Climate Center Current WRCC
Weather Data Plots,
http://www.wrcc.dri.edu/weather/
[23] Data Mining Large Medical Time Series Databases
http://www.cs.ucr.edu/~eamonn/discords/