在多重支持度下有效率的挖掘與維護關聯規則; An Efficient Algorithm for Discovery and Maintenance of Frequent Patterns with Multiple Minimum Supports

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

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

Title:	在多重支持度下有效率的挖掘與維護關聯規則;An Efficient Algorithm for Discovery and Maintenance of Frequent Patterns with Multiple Minimum Supports
Authors:	胡雅涵;Ya-Han Hu
Contributors:	資訊管理研究所
Keywords:	頻繁物件集;關聯規則維護;多重門檻值;多重支持度;FP-tree;Incremental mechanism;FP-tree;Multiple Minimum Supports;Association Rules;Data Mining
Date:	2003-06-02
Issue Date:	2009-09-22 15:20:30 (UTC+8)
Publisher:	國立中央大學圖書館
Abstract:	利用多重門檻值來進行關聯規則挖掘是一項相當重要且符合現實生活的資料採礦方法，相對於傳統單一門檻值的關聯規則挖掘，它允許使用者可以針對每個不同商品設定不同的門檻值，以反映真實世界中購買各種商品頻率不一的問題。以往Liu曾提出MSapriori演算法來挖掘多重門檻值下的頻繁項目集，然而由於其所採取的是Apriori-based的方法而導致效率不佳。在本篇論文中，我們提出了一種與FP-tree相似的結構與方法（稱為MIS-tree）來進行多重門檻值下的頻繁項目集挖掘，實驗結果顯示其效率較傳統MSapriori演算法好上許多。另外，有鑑於實務上應用多重門檻值的資料挖掘方法時，使用者必須多次調整每個商品的門檻值才能找到滿足起所需的頻繁項目集，我們在此也提出了一個維護MIS-tree的方法，讓使用者在調整完各個商品的門檻值後不需要再重新掃瞄資料庫而直接去調整已存在的MIS-tree，如此可以省下許多的執行時間。 Mining association rules with multiple minimum supports is an important generalization of the association rule mining problem, which was recently proposed by Liu et al. Instead of setting a single minimum support threshold for all items, they allow users to specify multiple minimum supports to reflect the natures of the items and their varied frequencies in the database. In Liu’s paper, an Apriori-based algorithm, named MSapriori, is developed to mine all frequent item sets. In this paper, we study the same problem but with two additional improvements. First, we propose a FP-tree-like structure, MIS-tree, to store the crucial information about frequent patterns. Accordingly, an efficient MIS-tree-based algorithm, called the CFP-growth algorithm, is developed for mining all frequent item sets. We evaluate the performance of the algorithm using both synthetic datasets and real datasets, and the results show that the CFP-growth algorithm is much more efficient and scalable than the MSapriori algorithm. Second, since each item can have its own minimum support, it is very difficult for users to set the appropriate thresholds for all items at a time. In practice, users need to tune items’ supports and run the mining algorithm repeatedly until a satisfactory end is reached. To speed up this time-consuming tuning process, an efficient algorithm which can maintain the MIS-tree structure without rescanning database is proposed. Experiments on both synthetic and real-life datasets show that our MIS-tree maintenance algorithm achieves dramatic saving in computation when tuning supports.
Appears in Collections:	[Graduate Institute of Information Management] Electronic Thesis & Dissertation

Files in This Item:

File	Size	Format

社群 sharing

Loading...