GSPT：使用前序表的高效關聯規則演算法

GSPT: An Efficient Mining Frequent Itemsets Algorithm Using Prefix Table

黃仁鵬(Jen-Peng Huang)

《Electronic Commerce Studies》 14卷2期 (2016/06) Pp. 257-277

摘要

隨著資訊科技的快速進步，交易、文件、日常處理的資料被電子化大量的累積，資料探勘的技術變得日益重要。其中，又以關聯規則在資料探勘領域中扮演著相當重要的角色，因此，許多探勘關聯規則演算法被不斷提出及改進，其主要目的在於增加執行效能或提升記憶體使用率。本研究提出GSPT 演算法 (Gradation Scanning using Prefix Table)。GSPT 演算法主要的特色就是前序表的排序概念與階段縮減過濾機制。建立前序表可將候選項目集加以集中，可減少計算支持度時掃瞄資料庫需花費的時間，進而改善傳統關聯規則演算法資料庫的掃瞄方式，加上配合前序表所提出的排序機制可有效的提升探勘效能；而階段縮減過濾機制可大量減少非頻繁項目集的數量，將可更適用於探勘交易長度較長的資料庫並且有效提昇記憶體的使用率。本研究實驗顯示本演算法在效能上優於Apriori 與 FP-growth 演算法。

關鍵字

資料探勘 ； 關聯規則 ； 前序表 ； 排序 ； 階段搜尋

並列摘要

Due to the science and technology make a great progress, transactions, documents and data are transformed into electronic types, the large number of data has been accumulated. Therefore, data mining technology becomes more important than before in recent years. In data mining territory, mining association rules plays a quite important position. Many of association rules mining algorithms were proposed to improve the efficiency of data mining or save the utility rate of memory. In this paper we propose a new algorithm － GSPT (Gradation Scanning using Prefix Table). The characters of the GSPT algorithm uses prefix table and gradation reduction mechanisms. GSPT uses prefix table to reduce the time of scanning database and gradation reduction mechanisms to reduce infrequent itemsets. Comprehensive experiments have been conducted to assess the performance of the proposed algorithm. The experimental results show that the GSPT algorithm outperforms Apriori and FP-growth.

並列關鍵字

data mining ； association rules ； prefix table ； sorting ； gradation scanning

參考文獻

黃仁鵬、柯柏瑄(2009)。GSSA：以階段分組排序搜尋機制探勘關聯規則之演算法。電子商務學報。11(3)，551-568。

Huang, J.-P.,Tsai, C.-L.(2007).GSA : A gradational scanning algorithm for mining association rules.Journal of e-Business.9(4),823-846.

Huang, J.-P.,Lan, G.-C.(2006).An efficient algorithm for mining association rules -GRA.Journal of e-Business.8(4),469-498.

Huang, J.-P.,Chien, I.-P.,Kuo, H.-C.(2006).An efficient incremental mining algorithm-ICI.Journal of e-Business.8(3),393-413.

Agrawal, R.,Srikant, R.(1994).Fast algorithms for mining association rules.Proceedings of 1994 International Conference on Very Large Data Bases.(Proceedings of 1994 International Conference on Very Large Data Bases).