請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/22794
標題: | 點集合資料庫之時空樣式探勘 Mining Spatial and Temporal Patterns in Pointset Databases |
作者: | Wen-Kwang Tsao 曹文光 |
指導教授: | 李瑞庭(Jui-Ting Lee) |
關鍵字: | 資料探勘,點集合資料庫,時空資料樣式, data mining,pointset databases,spatial-temporal patterns, |
出版年 : | 2010 |
學位: | 博士 |
摘要: | 本論文提出一個新的資料表示方式與三種探勘頻繁樣式的演算法: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 |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/22794 |
全文授權: | 未授權 |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 1.32 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。