挖掘關聯規則之階段搜尋演算法－GSA

GRA: A Gradational Scanning Algorithm for Mining Association Rules

10.6188/JEB.2007.9(4).08

黃仁鵬(Jen-Peng Huang)；蔡季嵐(Chi-Lan Tsai)

階段搜尋 ； 資料探勘 ； 關聯規則 ； Gradational Scanning ； Data timing ； Association Rule

電子商務學報

9卷4期（2007 / 12 / 01）

823 - 845

繁體中文

隨著交易、文件、日常處理資料的電子化、各種型式的資料被大量的累積下來，也隨著資訊科技的進步，資料探勘的技術變得日益重要。而關聯規則探勘在資料探勘的領域中也扮演相當重要的地位。許多的資料探勘演算法不斷被提出來，並針對舊的演算法加以改進，以增進其效能或更節省其所使用的記憶體，本論文主要是針對關聯規則的領域提出效能及記憶體方面改進的演算法。本論文提出一個新的關聯規則演算法GSA (Gradational scanning Algorithm), GSA演算法主要是利用C(下標 K)=C(下標 K-1)*C(下標 K-1)、的概念產候選項目集，且加入階段搜尋的概念，並配合過濾機制，使得候選項目集之數量逼近高頻項目集之數量，有效增進探勘的效能，而且GSA演算法最少只需掃描4次資料庫，最多掃描6次資料庫便可完成所有探勘。

Due to transactions, documents and data were transformed into electronic types. The huge mass of data has been accumulated. Today, the science and technology make a great progress. Therefore, data mining technology becomes more important than before in recent years. ft is generally applied to forecast in commerce and supports the decisions. In data mining territory, mining association rules plays a quite important position. Many of data mining algorithms were proposed continuously to improve performance of the old algorithms. They try to improve efficiency of the algorithms or to save the memory. In this paper, our study focuses on association rules and proposes a new algorithm-GSA (Gradational Scanning Algorithm) which improve performance and memory utility rate of mining association rules. GSA basically uses a method which is similar to scan reduction method of SWF algorithm. Besides, it also uses the concept of gradational scanning and the filtration mechanisms to reduce the number of candidates. The GSA needs to scan the Database four times at least and at most six times to finish the mining process.

1. 黃仁鵬、錢依佩、郭煌政(2006)。高效率之遞增式資料探勘演算法－ICI。電子商務學報，8(3)，381-398。
   連結：
2. Agrawal, R.,R. Srikant(1994).Fast algorithms for mining association rules.Proceedings of 1994 International conference on Very Large Data Bases
3. Brin, S.,R. Motwani,J. D. Ullman,S. Tsur(1997).Dynamic Itemset Counting and Implication Rules for Market Basket Data.ACM SIGMOD Conf. Management of Data
4. Han, J.,J. Pei,Y. Yin(2000).Mining Frequent Patterns without Candidate Generation.Proc. ACM SIGMOD Int. Conf. on Management of Data
5. Lee, C. H.,C. R. Lin,M, S. Chen(2001).Sliding-Window Filtering: An Efficient Algorithm for Incremental Mining.Proc. of the ACM 10th Intern`l Conf. on Information and Knowledge Management (CIKM-01)
6. Lin, D.,Z. M. Kedem(1998).Pincer Search: A New Algorithm for Discovering the Maximum Frequent Set.Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology
7. Liu, J.,Y. Pan,K. Wang,J. Han(2002).Mining Frequent Item Sets by Opportunistic Projection.Proc. 2002 Int. Conf. on Knowledge Discovery in Databases (KDD`02)
8. Park, J. S.,M. S. Chen,P. S. Yu(1995).An Effective hash-based Algorithm for Mining Association Rules.Proceddings of the ACM SIGMOD Conference on Management of Data-SIGMOD`95
9. Tseng, F. C.,C. C. Hsu(2001).Creating frequent patterns with the frequent pattern list.Proc. Of the Asia Pacific Conference of Data Mining and Knowledge Discovery,Hong Kong:
10. 黃南傑(2004)。碩士論文(碩士論文)。南台科技大學資訊管理所。
11. 熊浩志(2005)。碩士論文(碩士論文)。南台科技大學資訊管理所。

1. 黃仁鵬(2016)。GSPT：使用前序表的高效關聯規則演算法。Electronic Commerce Studies，14(2)，257-277。
2. 黃仁鵬、柯柏瑄(2009)。GSSA：以階段分組排序搜尋機制探勘關聯規則之演算法。電子商務學報，11(3)，551-568。