9DLT影片資料庫中頻繁樣式之資料探勘

隨著影音設備、數位相機、網路的盛行，多媒體資料系統也變得愈來愈受歡迎。因此，如何從一個影片資料庫中找出頻繁樣式越來越受到矚目。在本篇論文中，我們提出了一個有效率的探勘演算法「FVP-Miner」，用來找出影片資料庫中的頻繁樣式。演算法主要可分為兩個階段。第一階段，我們將每一段影片轉換成9DLT字串。第二階段，我們先找出所有長度為2的影像頻繁樣式，接著再對這些頻繁樣式作空間和時間上兩個維度的成長以找出所有的頻繁樣式。我們應用了三個修剪技巧和投影資料庫以去除不可能的候選樣式和加速演算法。因此，我們所提出的演算法可以有效率地在影片資料庫中找出頻繁樣式。實驗結果顯示，不管在合成資料或真實資料中，我們所提出的方法皆比改良式的Apriori演算法更有效率與擴充性。

關鍵字

資料探勘；頻繁影片樣式； 9DLT字串；影片資料庫

並列摘要

Multimedia database systems are becoming increasingly popular owing to the widespread use of audio-video equipment, digital cameras, CD-ROMs, and the Internet. Therefore, mining frequent patterns from video databases has attracted increasing attention in recent years. In this thesis, we proposed a novel algorithm, FVP-Miner (Frequent Video Pattern Miner), to mine frequent patterns in a video database. Our proposed algorithm consists of two phases. First, we transform every video into 9DLT strings. Second, we find all frequent image 2-patterns from the database and then recursively mine the frequent patterns in the spatial and temporal dimension. We employ three pruning strategies to prune many impossible candidates, and the concept of projected database to localize the support counting, pattern joining, and candidate pruning on the projected database. Therefore, our proposed algorithm can efficiently mine the frequent patterns in a video database. The experiment results show that our proposed method is efficient and scalable, and outperforms the modified Apriori algorithm in several orders of magnitude.

並列關鍵字

data mining ； frequent video pattern ； 9DLT string ； video database

參考文獻

[4] S.K. Chang, Q.Y. Shi, C.W. Yan, Iconic indexing by 2-D strings, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 9, No. 3, 1987, pp. 413–427.

[5] G. Grahne, J. Zhu, Fast algorithms for frequent itemset mining using FP-trees, IEEE Transactions on Knowledge and Data Engineering, Vol. 17, No. 10, 2005, pp. 1347-1362.

[8] Y.C. Huang, Mining frequent spatial co-relation patterns, Master Thesis, Department of Computer Science, National Chengchi University, Taiwan, 2004.

[10] R. Jin, C. Wang, D. Polshakov, S. Parthasarathy, G. Agarwal, Discovery frequent topological structures from graph datasets, Proceeding of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2005, pp. 606-611.

[11] A. J.T. Lee, and C.S. Wang, An efficient algorithm for mining frequent inter-transaction patterns, Information Sciences, Vol. 177, No. 17, 2007, pp. 3453-3476.

國際替代計量

9DLT影片資料庫中頻繁樣式之資料探勘

全文下載

主題瀏覽