請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9593
標題: | 點集合影片資料庫中封閉性樣式之資料探勘 Mining Closed Patterns in Pointset Video Databases |
作者: | Yi-Yu Lai 賴奕伃 |
指導教授: | 李瑞庭 |
關鍵字: | 資料探勘,點集合影片資料庫,封閉性樣式,頻繁樣式, data mining,pointset video database,closed pattern,frequent pattern, |
出版年 : | 2008 |
學位: | 碩士 |
摘要: | 隨著多媒體影像技術的蓬勃發展,多媒體資料量快速地遽增,如何從龐大的多媒體資料中找到有意義的資訊和特性已成為熱門的研究議題。我們可以將影片中發生的一個事件視為一個連續的點集合,而找到影片資料庫中由點集合所構成的封閉性樣式,則可以表達出影片中發生該事件的特性。因此,在本論文中,我們提出一個有效率的探勘演算法「CVP」來探勘出影片資料庫中的封閉性樣式。我們所提出的演算法主要先利用兩種資料結構儲存頻繁樣式的資訊,以深度優先搜尋的方式先對空間維度、再對時間維度產生出可能的頻繁樣式,最後再利用我們所提出的方法來修剪不符合或不必要的樣式以及判斷其封閉性。我們的演算法利用投影資料庫去產生可能的樣式和進行修剪,並不需要重複地搜尋整個影片資料庫,因此效率能夠得到明顯的改善。在人造及真實資料庫的實驗結果中顯示我們所提出的方法較改良式Apriori的方法來得更有效率。 Nowadays, the number of multimedia datasets is increasing rapidly. Thus, mining implicit and meaningful patterns from multimedia databases has attracted more and more attention in recent years. The event object can be viewed as a sequence of pointsets in a video. Mining closed patterns in pointset video databases can help us understand the pattern of an event in video databases. In this thesis, we first devise two data structures, called rplist and CV-tree, to store the information of frequent video patterns. Next, we propose a novel algorithm, called CVP, to mine frequent closed patterns from a video database in a depth-first search (DFS) manner. Our proposed algorithm consists of two phases. We first grow frequent video patterns in the spatial dimension and then grow them in the temporal dimension. To efficiently mine frequent closed patterns, we develop several pruning strategies to prune non-closed patterns. The CVP algorithm can localize the candidate generation, pattern join, and support counting in a small amount of rplists. Therefore, it can efficiently mine frequent closed patterns in a video database. The experiment results show that our proposed method outperforms modified Apriori algorithm in synthetic data and real data. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9593 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf | 492.52 kB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。