改良式週期性轉換發掘部份週期性特徵樣式

Using Modified Periodicity Transform for Partially Periodic Pattern Mining

蔡孟書(Tsai Meng-Shu)

指導教授 ： 蕭翰文

亞洲大學/資訊學院/資訊工程學系碩士班/碩士(2004年)

摘要

週期性特徵樣式探勘（periodic pattern mining），在先前已有許多研究者投入其中。而其中大部份研究則是專注於探討，全週期性特徵樣式探勘。而部份週期性特徵樣式（partially periodic pattern mining）也有討論，但事實上，先前的演算法執行效率，尚有改進的空間，記憶體消耗也還是很嚴重，加之繁雜的運算過程使得運算成本大幅增加。而在某些研究中，週期性或部份週性特徵樣式探勘的作法，依然是仰賴使用者輸入假設的候選特徵樣式，進而檢驗該候選特徵樣式的存在可能性。
在本研究以週期性轉換（periodicity transform）演算法為基礎，提出MPT與MPT_NNC演算法。在依據使用者給定的候選特徵樣式與其它門檻值;max_dist，min_rept，MPT可以有效地完成探勘，特別是在超長序列下，也有不錯地表現。而在沒有預設的候選特徵樣式的條件下，MPT_NNC則能有效地列舉，可能的候選特徵樣式集合以進行探勘，證明其存在性。由於EMS Projection的效果，使得判斷合法子 序列的程序大為簡化，大幅地縮短運算時間，而不受max_dist 與min_rept等門檻值影響。而針對非同部(asynchronous)的部份週期性特徵樣式的探勘，本研究也提出skip element方法，在不需修改演算法本身的前提下偵測出特徵樣式。

關鍵字

時間序列分析 ； 部份週期性特樣式探勘 ； 週期性特樣式探勘 ； 資料探勘

並列摘要

Numerous efforts had been made on periodic pattern mining in the past years. The problem of partially periodic pattern mining is similar to that of periodic pattern mining; however, the occurrences of patterns in sequences are different. Unlike periodic patterns, partially periodic patterns usually yield a result of period missing and/or shifting. Many approaches to partially periodic pattern mining had been proposed in the literature, but did not reach a satisfactory result in terms of computation time and memory accessibility. Besides, most approaches require given patterns for the mining tasks. On the basis of periodicity transforms, the modified periodicity transforms (MPT) and modified periodicity transforms without candidate pattern (MPT_NNC) are proposed in the study for discovering partially periodic patterns in sequences. Moreover, an efficient method for automatic generation of candidate patterns without giving domain knowledge is proposed as well. It is based on the location and possibility of the basis elements in a sequence and can be regarded as an auxiliary approach to the MPT and MPT_NNC algorithms.

並列關鍵字

time series analysis ； partially periodic pattern mining ； periodic pattern mining ； data mining

參考文獻

[6] J. Yang, W. Wang, and P. Yu, STAMP: On Discovery of statistically important pattern repeats in long sequential data, Proceedings of the 3rd SIAM International Conference on Data Mining, San Francisco, USA, 2003, pp. 224-238.

[8] Ozden, B., S. Ramaswamy, and A. Silberschatz, Cyclic association rules, Proceedings of the 14th International Conference on Data Engineering, Orlando, USA, 1998, pp. 412-421. 50

[11] W. A. Sethares, T. W. Staley, Periodicity transforms, IEEE Transactions on Signal Processing, Vol. 47, No.11, 1999, pp. 2953-2964.

[14] R. Rastogi, and K. shim, Mining Optimized association rules with categorical and numerical attributes, IEEE Transaction on Knowledge and Data Engineering, Vol.14, No.1, January/February, 2002, pp. 29-50.

[15] G. Chen, Q. Wei, and H. Zhang, Discovering similar time-series patterns with fuzzy clustering and DTW methods, Proceedings of the Joint 9th IFSA World Congress and 20th NAFIPS International Conference, Vancouver, Canada, Vol. 4, 2001, pp. 2160-2164.