模糊階層關聯規則及其支持度門檻值調整機制

Fuzzy Data Mining with Multi-Level Association Rules and Support Tuning Mechanism

康聖祥(Sheng-Hsiang Kang)

國立虎尾科技大學/管理學院/資訊管理研究所/碩士(2008年)

摘要

在資料探勘的領域中，關聯規則的其中一個應用是用來分析交易紀錄中顧客購買產品的關聯性。隨著大量資料不停地被收集和儲存，透過關聯規則探勘，找出具有價值的規則，便可以幫助許多商業決策的制定。本論文將透過結合模糊集合概念與階層關聯規則，使探勘時的效率提升。apriori-like approach方式是最常見且普遍的的關聯式法則演算法，此方法是以循序漸進的方式，採用多次掃描資料庫的方式來進行探勘產品間的關聯性，但其仍耗費許多的探勘時間與資料儲存的空間；在實務上，也常需要多次調整門檻值來產生滿足需求的頻繁項目集合，在使用apriori-like approach 時，當最小支持度門檻值改變時，必須重新掃描資料庫才可探勘出新的關聯規則，如此將耗費更多的時間。 本論文提出應用FP-tree 相似結構(FMFP-tree)的觀念及提出一個新的FMQFP-Growth 演算法，在模糊集合概念與階層關聯規則探勘結合的前提下，改善apriori-like approach 的缺點，並且提出門檻值調整機制，一旦最小支持度門檻值改變時，僅在P-tree 或FMFP-tree 進行刪除動作，而不需重新掃描資料庫，便可再次探勘關聯規則，所以，可以減少儲存空間與耗費時間。

並列摘要

In the field of data mining, one application of the association rules is to analyze the relationship of the transaction data. We can find the valuable rules by using data mining. In addition, it can help a business to make decisions. Combining with Fuzzy sets and multi-level association rules, data mining will be more efficient. The apriori-like approach is a universal algorithm to find association rules. This algorithm scans database several times to mine the relations of products. However, it still takes much time and many storage spaces in the mining process. In practice, we often adjust support threshold several times to find the satisfied frequent pattern sets. When the minimum support threshold values are changed by using the apriori-like approach, we must rescan the database to mine new association rules. In such a way, it will take more time and storage spaces.
In this paper we propose a FMFP-tree (Fuzzy Mining Frequent Pattern tree) concept like FP-tree structure and a new algorithm FMQFP-Growth (Fuzzy Mining QFP-Growth). It improves the efficiency of the apriori-like approach when combining with Fuzzy sets and multi-level association rules. We also propose a Support Tuning Mechanism. When the minimum support threshold is changed, this algorithm just prunes in the P-tree or FMFP-tree and mines the association rules without rescanning database. Therefore, it can reduce mining time and storage spaces.

參考文獻

[2] T. P. Hong, K. Y. Lin, and S. L. Wang, “Fuzzy data mining for interesting generalized association rules”, Fuzzy Sets and Systems, Vol. 138, No. 2, pp. 255-269, 2003.

[5] J. S. Park, M. S. Chen, and P. S. Yu, “An Effective Hash-Based Algorithm for Mining Association Rules”, Proceedings ACM-SIGMOD International Conference on Management of Data, pp.175-186, 1995.

[7] S. Brin, R. Motwani, J. Ullman, and S. Tsur, “Dynamic Itemset Counting and Implication Rules for Market Basket Data”, Proceedings of the 1997 ACM-SIGMOD Conference on Management of Data, pp. 255-264, 1997.

[8] J. Han, J. Pei, Y. Yin, and R. Mao, “Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach”, Data Mining and Knowledge Discovery, Vol. 1, No. 8, pp. 53-87, 2004.

[11] R. Agrawal, and R. Srikant, “Mining Quantitative Association Rules in Large Relational Tables”, Proceedings of the 1996 ACM-SIGMOD Conference on Management of Data, pp. 1-12, 1996.