臺灣博碩士論文加值系統

在資料庫的研究中，資料挖掘是一項相當熱門的議題，資料挖掘的興起主要是為了能夠在一個擁有龐大資料的資料庫中，找到一些隱含的知識（implicit knowledge），在業界及學術界上都已經有不錯的研究發表出來。但是觀察現今的研究趨勢，我們可以發現到資料挖掘的研究領域漸漸由分散點狀資料往時間性資料庫轉移，也就是時間序列的資料。對於時間序列資料庫的快速搜尋和比對顯得特別有興趣，因此在時間序列資料庫中特別有興趣的就是相似性查詢。為了解決多維度的問題，我們需要使用一些轉換的方法產生一組新的索引，如此可以改善比對的效率。目前有許多的方法可以儲存資料，例如：R-Tree、R*-Tree、SS-Tree和SR-Tree，但是這些方法會因為資料的維度增加而造成績效很差。在此我們選定了Haar小波轉換和傅利葉轉換。
本研究的目的，是要利用Haar小波轉換，將資料庫中的資料轉換成新的資料序列，利用新的索引做相似性查詢，包含下列二種模式：（1）區間查詢：對一個特定的股票價格資料，從資料庫中找出某個範圍的相似性；（2）最接近查詢：對一個特定的股票價格資料，找出與它最接近相似性的股價資料。同時我們利用傅利葉轉換做相同的工作，藉以比較出Harr小波轉換與傅利葉轉換之間的優劣。
根據研究結果，本論文所使用的Haar小波轉換的確可以利用轉換後的前幾項係數代表全部序列資料去查詢，有其相當的精確度，且可以有效的降低查詢所需的時間和儲存資料所需的資料庫空間。在主要的各種測試情況下，都有較傅利葉轉換為佳的查詢效率。

Time series data searching and mining has become a growing trend in temporal/time-series database management systems. How to store and retrieve a time-series data becomes an important research topic. To increase the performance, many approaches have been proposed to use Discrete Fourier Transform (DFT) to transform a time series data into a lower-dimensional feature vector.
In this thesis, we propose an approach to index time series data by Haar Wavelet Transform (HWT). In the proposed approach, a time series data is transformed to a feature vector by the HWT and the first 8~11 HWT coefficients are selected as an index. Then the indices are stored into an SR-Tree. To compare the performance of the proposed approach with that of the DFT approach, we use two types of queries, range query and nearest neighbor query, to conduct some experiments on a set of time series data.
According to the experimental results, it has been shown that the approach based on HWT outperforms the approach based on DFT in terms of the precision and number of disk accesses.

第一章 緒論.................................................1
第一節 研究動機...........................................1
第二節 研究目的...........................................3
第三節 研究架構...........................................4
第二章 文獻探討.............................................5
第一節 兩向量間距離的比較.................................5
第二節 多維度索引的處理...................................5
第三節 離散式傅利葉轉換..................................18
第四節 Haar小波轉換......................................20
第五節 綜合討論..........................................20
第三章 研究方法............................................22
第一節 時間序列資料的前置處理............................22
第二節 Haar小波轉換......................................24
第三節 相似性查詢的策略..................................37
第四章 研究結果............................................46
第一節 實驗程序簡介......................................46
第二節 HAAR小波轉換和DFT參數選取實驗.....................47
第三節 股票間的相似性查詢................................50
第四節 HAAR小波轉換與DFT之比較...........................57
第五節 其他的小波轉換....................................65
第六節 不同長度的查詢....................................67
第五章 結論................................................70
第一節 結論..............................................70
第二節 未來研究建議......................................71
參考文獻....................................................72

一、中文部分
[1]江玥慧，時間性資料庫中相似曲線的搜尋─以台灣股價資料庫為例，國立台灣大學資訊管理研究所碩士論文，1998。
二、英文部分
[1]Rakesh Agrawal, Christos Faloutsos, and Arun swami, Efficient similarity search in sequence database, In Proceedings of the Fourth International Conference on Foundations of Data Organization and Algorithms, 1993.
[2]Rakesh Agrawal and Ramakrishnan Srikant, Mining sequential patterns, In Proceedings 1995 International Conference Data Engineering, pages 3-14, 1995.
[3]Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. The R*-tree: An efficient and robust access method for points and rectangles. In Procs. of ACM SIGMOD Conference on Management of Data, pages 322-330, 1990.
[4]Donald J. Berndt and James Clifford, Advances in Knowledge Discovery and Data Mining, Menlo park, Calif.: AAAI/MIT Press, 1996.
[5]C. Sidney Burrus, R. A. Gopinath, and H. Guo, Introduction to Wavelets and Wavelets Transforms, A primer, Upper Saddle River, N.Y.: Prentice Hall, 1997.
[6]Tim Edwards, Discrete wavelet transforms: Theory and implementation. Technical report, Stanford university, 1991.
[7]Christos Faloutsos, M. Ranganathan, and Y. Manolopoulos, Fast subsequence matching in time-series databases, In Proc. of the ACM SIGMOD Conference on Management of Data, pages 419-429, 1994.
[8]Rafael C. Gonzalez and Richard E. Woods, Digital Image Processing, Readings, Mass.: Addison Wesley, 1992.
[9]Antonin Guttman, R-trees: A dynamic index structure for spatial searching, In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 47-57, 1984.
[10]Alfred Haar, Theorie der Orthogonalen funkionen-system, Berlin[etc.]:J. Springer[etc.]: Mathematische Annalen, 69:331-371, 1910.
[11]N. Katayama, S. Satoh, The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries, In Proceedings of the ACM SIGMOD Intl. Conf. on Mgmt. of Data(SIGMOD ’97), pages 369-380, AZ, USA, May 1997.
[12]A. V. Oppenheim and R. W. Schafer, Digital Signal Processing, Englewood Cliffs, N.Y.: Prentice Hall, 1975.
[13]D. Rafiei, Similarity-based queries for time series data, In Proceedings of the ACM SIGMOD Intl. Conf. on Mgmt. of Data(SIGMOD ’97), pages 13-24, Tucson, Arizona, May 1997.
[14]Davood Rafiei, On Similiarity-Based Queries for Time Series Data, In Proceedings of 15th International Conference on Data Engineering, 1999.
[15]Nick Roussopoulos, Stephen Kelly, and Frederic Vincent, Nearest neighbor queries, In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 71-79, 1995.
[16]D. Rsfiei and A. Mendelzon, Efficient retrieval of similar time sequence using DFT, In Proc. of the 5th Intl. Conf. On Found. Of Data Org. and Alg. (FODO ’98), Kobe, Japan, November 1998.
[17]Karl Weierstrass, Mathematische Werke, Volume Ⅱ, Berlin: Mayer & Muller, 1895.
[18]D. A. White and R. Jain, Similiarity Indexing with the SS-tree, In Proc. Of the 12th Int. Conf. on Data Engineering, New Orleans, USA, pages 516-523, May 1996.