FP-tree(Frequent Pattern Tree)的調整維護技術研究

NCUIR > School of Management at National Central University > Graduate Institute of Information Management > Electronic Thesis & Dissertation > Item 987654321/12894

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

Title:	FP-tree(Frequent Pattern Tree)的調整維護技術研究
Authors:	張元哲;Yuan-Che Chang
Contributors:	資訊管理研究所
Keywords:	資料挖掘;Data Mining;association rules;FP-tree
Date:	2001-07-04
Issue Date:	2009-09-22 15:17:42 (UTC+8)
Publisher:	國立中央大學圖書館
Abstract:	在資料庫中挖掘association rules是相當普遍的資料挖掘課題，而這類的研究主要可以分成兩大類：(1)利用Apriori-like的方法產生candidate set，並找出符合minimum support的large itemsets，再依據large itemsets產生association rules；(2)使用Non Apriori-like的方法，找出large itemsets。這兩類的方法中，第(2)類的方法在效率上明顯優於第(1)類，而在第(2)類方法中，又以FP-tree（Frequent Pattern Tree）的結構結合FP-growth algorithm的方法最新、最有效率也最為著名，如今它已經實際運用於DBMiner中，而且有很好的效率表現。然而上述的兩類方法都需要掃描資料庫兩次以上，在超大型的交易資料庫上進行這樣的動作將相當費時，因此如果能夠依照交易資料庫的異動情況，以incremental的方式修改large itemsets來維護association rules的正確性，又不需要重新掃描資料庫，便相當有價值。過去所提出的incremental維護方法，均是針對第(1)類方法所進行的研究，而第(2)類方法目前都還沒有人提出相關的incremental維護方法，本研究便是針對第(2)類方法中的FP-tree結構，提出incremental維護演算法FPI（FP-tree Incremental），可以在資料庫發生insert、delete或update時，不需要重新掃描整個資料庫即可很有效率地動態調整FP-tree，使它維持正確的結構。另外一種常見的情況是產生association rule的minimum support變小時，由於FP-tree並未包含原先minimum support下屬於infrequent item的node，故需要重新掃描資料庫來建構新的FP-tree，FPI在這種情況下也可以達到動態調整的目的，而不用浪費掃描整個資料庫的I/O時間來重新建構FP-tree。由於FP-tree通常遠小於交易資料庫本身而可以放在主記憶體中，所以一旦完成FP-tree的建構，以FP-growth來產生frequent patterns就非常的迅速，因此它所花費的主要時間便在掃描資料庫的I/O和建構FP-tree之上，本研究所提供的FPI演算法可以即時地維護FP-tree正確結構，使association rules可以快速產生。
Appears in Collections:	[Graduate Institute of Information Management] Electronic Thesis & Dissertation

Files in This Item:

File	Size	Format

社群 sharing

Loading...