以前序樹結構加速探勘意外週期樣式之研究

A Prefix Tree Base Approach for Mining Surprising Patterns Efficiently

林孝鴻(Hsiao-hung Lin)

指導教授 ： 柯佳伶

國立臺灣師範大學/教育學院/資訊教育學系/碩士(2002年)

摘要

以往探勘時序週期樣式過程中，判斷週期樣式是否重要主要是依據出現次數多寡，在時序性資料中出現次數少於最小出現次數門檻值的資料項出現之週期現象將無法被探勘出來。為解決此問題，意外週期樣式判斷的準則同時採用資料項出現機率值及樣式出現次數來計算，可找出資料項出現率低，卻具相對高支持度的週期樣式。
在此論文中，我們針對對於如何有效探勘意外週期樣式提出探討。本論文提出了PF_SP Miner演算法，使用前序樹為儲存的資料結構，將時序性資料項序列儲存在前序樹中。並將樹狀結構壓縮合併可以快速的找出時序資料項序列中所有的時序樣式，判斷其是否為意外週期樣式。另外我們設計出支持度過濾矩陣可以更快速過濾候選的意外週期樣式。實驗結果顯示我們所提出之演算法比相關文獻中所提出的方法，在執行時間上更有效率。

關鍵字

意外週期樣式 ； 時序資料項序列

並列摘要

In the past, the progress of mining temporal patterns, we used to base on the frequency of the temporal patterns occur to decide whether it’s important or not. If the patterns occurrences of the temporal data are smaller than the minimum support, then mining of this temporal phenomenon can not be done. In order to solve this problem, the rules of defining the surprising patterns adopt both the possibility of the occurrence of the data and the times of the pattern occur to calculate, this method can find out that the occurrence possibility of the data is low, but on the other hand it has relatively high confidence .
In this thesis, we focus on the discussion of the mining of surprising effectively. We use PF_SP Miner mathematical in this thesis, take prefix tree as the storage of data structure, and save temporal data string in the prefix tree. Moreover, we combine and condense the tree structure so that we can find out the temporal data string temporal data string in all the temporal patterns quickly. Besides, we also design minsupport matrix that can filter the surprising patterns much faster. The result of our research shows that our mathematical method is much more efficient on the time of execution than the methods which relate references used .

並列關鍵字

surprising pattern ； temporal data

參考文獻

[1] J. Yang, W. Wang, and P. Yu, “InfoMiner: mining surprising periodic patterns,” in Proc. ACM Int. Conf. on Knowledge Discovery and Data Mining, 2001.

[3] C. H. Lee, C. R. Lin and M. S. Chen , “On Mining General Temporal Association Rules in a Publication Database,” in Proc. IEEE Int. Conf. on Data Mining, 2001.

[5] J. Han, G. Dong, and Y. Yin, “Efficient mining partial periodic patterns in time series database,” in Proc. IEEE Int. Conf. on Data Engineering, 1999.

[6] J. Yang, W. Wang, and P. Yu, “Mining asynchronous periodic patterns in time series data,” in Proc. ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, 2000.

[7] B. Liu, W. Hsu, and Y. Ma, “Mining association Rules with multiple minimum supports,” in Proc. ACM SIGMOD Int. Conf. on Management of Data, 1999.