Eclat Grouping:基於分群策略之頻繁項目集探勘演算法加速

Abstract

頻繁項目集探勘是一資料探勘的分支，是一基礎且重要的技術，其目的在於找出物品之間的關聯性。頻繁項目集探勘的發展歷史悠久，直至今日依然有不少關於此技術的論文發表，試圖加速或優化其探勘的過程。根據資料的緊湊程度，可以分成密集、中等及稀疏，每種都有著不同的性質，而大多數的演算法都只對於特定的性質進行算法上的加速。然而，隨著數位化的普及，各式資料皆以數位的形式儲存，使得資料量迅速成長，許多演算法的短處也在資料量的成長下逐漸顯露出來。為了使演算法更具通用性，本篇論文提出基於分群策略之頻繁項目集探勘演算法加速(Eclat Grouping)，在二元陣列的表示法下，試圖利用分群的方式降低資料維度以加速頻繁項目集探勘的過程。Eclat Grouping利用二元陣列稀疏的特性，將資料分群合併，藉此減少空值的情形與降低運算量，同時利用二階段驗證來確保結果的正確性。此外，我們也藉由中央處理器的特定指令對陣列做平行化處理，進一步加速運算流程。實驗結果顯示Eclat Grouping在稀疏資料集下優越於以往的演算法，同時在密集資料集下保持著近似的運算速度。

Frequent itemset mining (F.I.M) is a branch of data mining. It is a fundamental andimportant technique, which aims to find out the relation between items. The concept ofF.I.M was proposed many years ago and there are still have many works that try to optimize and accelerate the mining process. According to the density of the database, it canbe divided into three types, including dense, mid-dense, and sparse database. Each typeof database has its characteristics and most of the algorithms are only specific to one typeof density. Due to the popularization of digitization, the size of databases grows rapidly.However, the growing data also enlarges the shortcomings in most algorithms. To makethe algorithm more general in different density of databases, we proposed an efficientfrequent itemset mining algorithm based on the grouping strategy calledEclat Grouping.We use the grouping method to reduce the data dimension based on binary array representation and accelerate the process of F.I.M. Moreover, we use two-stage accelerationto filter non-frequent itemsets in the first stage and ensure the correctness of the result in the second stage. In addition, we use certain instructions to parallelize and accelerate thecomputing process. The experiment shows that Eclat Grouping is faster than others insparse databases with negligible change for the running time in dense databases.