9DLT影像資料庫中封閉性樣式之資料探勘

Abstract

由於資訊的進步，在影像資料庫中累積了大量的影像。如何從這些影像中探勘出有價值的資訊，也越來越受到重視。因此，在本篇論文中我們提出一個有效率的探勘演算法——「CP9」，以找尋9DLT影像資料庫中封閉性樣式。在這個資料庫中每一張影像，皆以9DLT字串方式來表示。我們的方法可分為兩階段：第一階段，掃描整個資料庫找出長度為二的頻繁樣式。第二階段，我們利用長度為k的頻繁樣式，以及與它可結合的頻繁樣式產生出長度為k+1的頻繁樣式，然後重複執行第二階段的步驟直到不能找到任何的封閉性樣式為止。因為我們提出的可結合頻繁樣式與修剪策略可以刪去許多不必要的樣式與路徑，實驗結果顯示所提出的方法具有效率與擴充性，且它優於9DLT-Miner演算法。

With advances of information technology, enormous numbers of images have been accumulated in image databases. As a result, how to mine useful patterns from image databases has attracted more and more attention in recent years. Hence, in this thesis, we proposed an efficient and scalable algorithm, CP9, to mine the frequent closed pattern in a 9DLT database, where every image is represented by a 9DLT string. Our proposed algorithm consists of two phases. First, we scan the database to find all frequent 2-patterns, and build an imageset for each frequent 2-pattern. Then, we use a frequent k-pattern to find its super (k+1)–patterns by joining the patterns in its joinable class in a depth-first search (DFS) manner where k>=2. The second phase is recursively repeated until no more frequent closed patterns can be found. Since our proposed algorithm uses the joinable class to localize the pattern generations and pruning properties to remove many frequent but non-closed patterns, it can efficiently mine frequent closed patterns in 9DLT image databases. The experimental results show that our proposed algorithm is efficient and scalable, and it outperforms the 9DLT-Miner algorithm.