臺灣博碩士論文加值系統

隨著越來越多資料以時間序列的型態被紀錄，針對時間序列資料尋找其中可用資訊的需求也越來越高。時間序列資料分析擁有許多現實世界中的應用：例如顧客購物順序的習慣分析，以利行銷策略的有效規劃；還有瀏覽網頁路徑的順序分析，以便能夠更有效的規劃網站中的網頁連結設計與利用等。
舉個台灣股市的例子。股票的價格與成交量間經常會有相互影響的關係存在。當股價攀升，成交量可能會在後來的日子裡也隨之提升。再者，同產業中龍頭個股的漲跌也可能帶動其他個股的變化。要找出股票價量之間的相互關係以及個股間的相互影響是個十分有趣的課題。如果我們能針對股市的變化從中找出某些特定的關聯性規則，則我們就能夠更準確的預測股市的走勢。
在這篇論文中，我們提出一個演算法來尋找時間序列資料中的關聯性規則。我們把每個描述不同主題的資料集如價格、成交量視為一條條的線，在線與線當中尋找其關聯。我們設計了一個資料結構來有效率的尋找關聯性規則，這個方法能夠有效的減少掃瞄整個資料庫所需耗用的時間。由實驗結果得知，我們所提出的方法比Apriori-like方法快上好幾倍。

While more and more data generated in the form of time-series, there are much more needs to find frequent patterns in time-series data. Time-series data mining becomes more and more popular in recent research areas and has broad applications like analysis of customer purchase patterns, web traversal patterns, etc.
Let’s consider the example of stock price fluctuation and trading volume fluctuation patterns of TWSE. There may be some implications that when the stock price went upwards two days before, the stock trading volume may go upwards in following days. The price and trading volume of some leading companies may also affect those changes of other companies in the same industry. It’s interesting for us to find the relationships between stock fluctuation patterns. If we could find out some association rules between stock fluctuation patterns, we can predicate more precisely the trends of stock markets.
In this thesis, we propose an algorithm to mine the association rules among time-series data. We view the transaction data describing different attributes or subjects as lines, and then we find association rules among those lines. We’ll introduce a method to find the frequent lines efficiently by constructing the bitmaps of frequent patterns, the method is helpful to reduce the number of database scans. The experimental results show that our proposed algorithm outperforms the Apriori-like approach by several orders of magnitude.

Table of Contents i
List of Figures ii
List of Tables iii
Chapter 1 Introduction 1
Chapter 2 Background and Literature Survey 3
2.1 Mining Association Rules 3
2.2 The Milestone─the Apriori Algorithm and the Improvements 4
2.2.1 The Apriori Algorithm 4
2.2.2 Improvement of Apiori─the Partition Algorithm 7
2.3 FP-tree: Mining without Candidate Generation 8
2.4 Mining Sequential Association Rules 11
2.5 Mining Inter-transaction Association Rules 12
2.6 Discussion 17
Chapter 3 Mining Association Rules Among Time-series Databases 18
3.1 Problem Definition 18
3.2 Algorithm 22
3.2.1 Data Preparation 23
3.2.2 Mining Association Rules among Time-series Databases 23
3.2.2.1 Frequent Line Segment Discovery 24
3.2.2.2 BitmapFilter 26
3.2.2.3 Association Rule Mining 28
3.2.2.4 LineSegmentIndex 31
3.3 Discussion 36
Chapter 4 Experiment Results and Performance Evaluation 37
4.1 Parameters and Setting 37
4.2 Experiments on Synthetic Data 38
4.3 Experiments on Real Data 42
4.4 Summary 47
Chapter 5 Conclusions and Future Work 48
References 49

[1] R. Agrawal, T. Imielinski, and A. Swami, “Mining Association Rules between Sets of Items in Large Databases,” Proc. ACM Special Interest Group on Management Of Data, pp. 207-216, May 1993.
[2] R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules in Large Databases,” Proc. 20th Int’l Conf. on Very Large Databases, Santiago, Chile, pp. 478-499, September 1994.
[3] R. Agrawal and R. Srikant “Mining Sequential Patterns,” Proc. 11th Int’l Conference on Data Engineering, Taiwan, March 1995.
[4] J. Han, J. Pei, and Y.Yin, “Mining Frequent Patterns without Candidate Generation,” Proc. ACM Special Interest Group on Management Of Data, pp. 1-12, May 2000.
[5] J. Han, H. Lu, L. Feng, “Beyond Intra-transactional Association Analysis: Mining Multi-dimensional Inter-transaction Association Rule,” ACM Transactions on Information Systems, Vol. 18, No. 4, pp. 423-454, October 2000.
[6] J. Han and M. Kamber, Data Mining: Concepts and Techniques, Morgan Kaufmann, San Francisco, 2000.
[7] Polly Wan Po Man, Man Hon Wong, “Efficient and Robust Feature Extraction and Pattern Matching of Time-series by a Lattice Structure,” Proc. 10th Int’l Conference on Information and Knowledge Management, Atlanta, Georgia, USA, pp. 271-278, October 2001.
[8] A. Savasere, E. Omiecinski, and S. Navathe, “An Efficient Algorithm for Mining Association in Large Databases,” Proc. 21st Int’l Conf. on Very Large Databases, Zurich, Swizerland, 1995.
[9] R. Srikant and R. Agrawal, “Mining Sequential Patterns: Generations and Performance Improvements,” Proc. Extending Database Technology, France, March 1996.
[10] R. Srikant and R. Agrawal, “Mining Quantitative Association Rules in Large Relational Tables,” Proc. ACM Special Interest Group on Management Of Data, Vol. 25, No. 2, pp. 1-12, June 1996.
[11] Pseudo Periodic Synthetic Time Series Database from the UCI KDD Archive, Information and Computer Science, University of California, Irvine,
http://kdd.ics.uci.edu/databases/synthetic/synthetic.html, September 1999.
[12] Taiwan Stock Exchange Corporation, http://www.tse.com.tw, May 2003.