從交易資料庫中以自我推導方式探勘具有多層次FP-tree ;Mining Self-derivable Multilevel FP-tree From a Transactional Database

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/9300

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/9300

Title:	從交易資料庫中以自我推導方式探勘具有多層次FP-tree;Mining Self-derivable Multilevel FP-tree From a Transactional Database
Authors:	李翊銘;Yi-Ming Lee
Contributors:	資訊工程研究所
Keywords:	multilevel association rule;FP-growth;FP-tree;Apriori;association rule mining
Date:	2006-08-17
Issue Date:	2009-09-22 11:44:58 (UTC+8)
Publisher:	國立中央大學圖書館
Abstract:	在探勘關聯式規則的領域裡，一些近期的研究中顯示出一些比Apriori-like演算法還要好的方法。探勘頻繁模式在發掘關聯式規則的領域裡占有很重要的角色。在過去，Apriori-like的方法被用在探勘頻繁模式中，但是這些方法對於探勘的工作過程中過於沒效率，這是因為在探勘過程中有著多次重複掃描資料庫和不斷遞迴式地靠著模式比對來產生大量候選者的集合。一個被叫作FP-tree精簡結構被發展出用來改善之前Apriori-like方法的缺點。靠著由J. Han所提出的FP-growth方法，我們可以更便利地去探勘多頻繁模式，雖然FP-growth在探勘多頻繁模式領域中，相較一些作法是一個比較有效率的方法，但是探勘的結果對管理者和決策者來說可能太過詳細。我們提出一個探勘具有較高階層次的頻繁模式的想法，也就是說那些較低階的頻繁模式和精簡的結構可以更加地被歸納和簡化。我們基本的概念是利用FP-tree的特性和結構並且根據一個現存自定的階層關係進行探勘工作。有鑒於此，我們提供有效率提升方法使得原本的FP-tree可以進而成為一個較高階層次的FP-tree。在我們的方法中，被轉換的高層次FP-tree仍保有原本FP-tree的特性。藉由這些提升方法，我們可以達到低階FP-tree到高階FP-tree轉換的目的，並提供管理者具歸納性質的資訊，在實驗結果中也顯示出我們所提出方法的效果性。 Some recent works have showed the improved approaches which are certainly better than original Apriori-like algorithms for mining association rules. Mining frequent patterns (itemsets) plays an important role of discovering association rules. In the past, Apriori-like methods were adopted to mine frequent itemsets. But these approaches are inefficient to perform a mining task. This is a result from its repeatedly scans of database and iteratively checking a large set of candidates by pattern matching. A compact structure, called FP-tree, was developed to improve the disadvantages of Apriori-like algorithms. By FP-growth approach, proposed by J. Han, we can facilitate mining frequent itemsets. Although FP-growth is a relatively more efficient approach for mining frequent itemsets, the results deduced by FP-growth may be too detailed to satisfy managers or policymakers. We proposed that lower level frequent itemsets and those compressed data within a FP-tree can be generalized furthermore for mining higher level frequent itemsets. Our basic idea is employing the properties and structure of FP-tree according to an existed conceptual hierarchy on mined items. We then provide efficient evolution algorithms to modify the original FP-tree to a higher level FP-tree. In our approaches, the transformed FP-tree still retains the properties of primitive FP-tree. By these novel approaches, we can effectively achieve the goals of transforming from a lower level FP-tree to a higher one, providing more generalized information to managers. Our experimental results also show the effectiveness of the proposed methods.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Size	Format

社群 sharing

Loading...