點集合資料庫之時空樣式探勘

Mining Spatial and Temporal Patterns in Pointset Databases

曹文光(Wen-Kwang Tsao)

指導教授 ： 李瑞庭

國立臺灣大學/管理學院/資訊管理學研究所/博士(2010年)

https://doi.org/10.6342/NTU.2010.10731

摘要

本論文提出一個新的資料表示方式與三種探勘頻繁樣式的演算法：MaxFSP、PCP 及CVP。MaxFSP演算法從二維點集合資料庫中探勘最大頻繁空間樣式；PCP演算法從二維點集合資料庫中探勘封閉性頻繁空間樣式；CVP演算法則從視訊點集合資料庫中探勘封閉性頻繁時空樣式。在MaxFSP 及PCP 演算法中，我們除了運用Apriori 演算法所提出之反單調修剪原則，修剪不可能的候選樣式外，我們還針對空間關係的特性，提出快速修剪方法。並參考MAFIA與CHARM演算法，各別加入最大頻繁樣式與封閉性頻繁樣式所需的修剪方法。透過這些方法，我們可以在探勘過程中有效刪除不可能的候選樣式。CVP演算法更進一步考慮了時間軸上的關係，探勘視訊資料庫中封閉性頻繁時空樣式。CVP 演算法除了應用了空間中修剪方法之外，並提出「快速成長」(fast-grow)的策略，可有效地在樣式索引樹中標示不須延展的節點，進而避免重複檢查的運算，減少耗時的候選樣式產生時間。實驗結果顯示，MaxFSP 演算法的執行效率優於改良式的MAFIA演算法；PCP演算法的執行效率優於改良式的Apriori演算法、SASMiner演算法與MaxGeo演算法；CVP演算法的執行效率優於改良式的Apriori演算法。

關鍵字

資料探勘 ； 點集合資料庫 ； 時空資料樣式

並列摘要

In this dissertation, we propose a novel data representation and three algorithms, MaxFSP, PCP, and CVP algorithms. The MaxFSP algorithm is proposed to find the maximal frequent spatial patterns in image databases. The PCP algorithm is designed to find the frequent closed spatial patterns in image databases. The CVP algorithm is developed to find the frequent closed spatial-temporal patterns in video databases. In the MaxFSP and PCP algorithms, in addition to using the anti-monotone pruning strategy to prune unnecessary candidate patterns, we utilize the characteristics of the spatial relationships to design the pruning strategies. Specifically, we design pruning strategies based on the MAFIA and CHARM algorithms respectively to prune non-maximal and non-closed candidates. By using these strategies, we can prune a large number of unnecessary candidate patterns. The CVP algorithm is further considering temporal information to mine all frequent closed spatial-temporal patterns in video databases. In the CVP algorithm, we not only use the spatial relationship to prune unnecessary candidate patterns, we also propose a fast-grow pruning strategy, which can speed up the mining process in the temporal dimension. Therefore, the CVP algorithm can effectively prune the unnecessary branches in the frequent pattern tree and avoid the costly candidates’ generation. The experimental results show that the MaxFSP algorithm outperforms the modified MAFIA algorithm; the PCP algorithm outperform the modified Apriori, SASMiner, and MaxGeo algorithms; and the CVP algorithm outperform the modified Apriori algorithm

並列關鍵字

data mining ； pointset databases ； spatial-temporal patterns

參考文獻

[2] R. Agarwal, C. Aggarwal, V. Prasad, A tree projection algorithm for generation of frequent itemsets, Parallel and Distributed Computing, 2001.

[5] H. Arimura, Takeaki Uno, Shinichi Shimozono, Time and space efficient discovery of maximal geometric graphs, LNCS (LNAI), Vol. 4755, Springer, Heidelberg, 2007, pp. 42-55.

[8] D. Burdick, M. Calimlim, J. Gehrke, MAFIA: A maximal frequent itemset algorithm for transactional databases, Proceedings of the 17th International Conference on Data Engineering, 2001, pp. 443-452.

[9] J. Cheng, Y. Ke, W. Ng, δ-tolerance closed frequent itemsets, Proceedings of the IEEE International Conference on Data Mining, Hong Kong, China, 2006, pp. 139-148.

[11] G.L. Foresti, L. Marcenaro, C.S. Regazzoni, Automatic detection and indexing of video-event shots for surveillance application, IEEE Transactions on Multimedia, Vol. 4, No. 4, 2002, pp. 459-471.