一種混合型的增量數據關聯規則挖掘算法

鄧廣彪

摘要：在數據庫中增加數據且調整最小支持度時，數據庫中關聯規則會發生變化，為從數據量和最小支持度同時發生變化的數據庫中快速獲取頻繁項集，發現變化后的關聯規則，通過對FIM和AIUA算法進行分析，提出一種結合兩種算法優點的增量數據關聯規則挖掘My_FIM_AIUA算法，該算法能減少數據庫掃描次數，減少候選項集數量。通過實驗表明My_FIM_AIUA算法能在數據量和最小支持度同時變化時快速找到頻繁項集，提高挖掘增量數據關聯規則的速度。

關鍵詞：關聯規則；增量數據；支持度變化

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）31-7237-04

Abstract： There will be some changes of association rules when adding data and adjusting the minimum support in the database. In order to obtain the frequent item sets quickly from the database when changes of the data size and minimum support happened at the same time， and to find out the changed association rule， the My_FIM_AIUA mining algorithm for incremental data association rule that combined the advantages of FIM and AIUA will be proposed by means of the analysis of FIM and AIUA algorithm. This algorithm can reduce the times of database scanning and decrease the numbers of candidate items. Thus， an experiment will be taken to show that the My_FIM_AIUA algorithm can search the frequent item sets quickly when changes of data size and minimum support happened at the same time， and it can improve the speed of mining the incremental data association rule.

Key words： association rule； incremental data； support changes

1 概述

關聯規則挖掘是指從海量數據中尋找頻繁在一起出現的事務及規律，經典的算法有Apriori算法和FP增長算法，但這兩種算法都是面向數據量不變且最小支持度不變[1]。關聯規則挖掘經常會出現數據量、最小支持度變化的情況，那么關聯規則增量更新主要分為數據量不變最小支持度變大/變小、最小支持度不變而數據量增加/減少、最小支持度和數據量兩者同時發生變化三種[2]。為能快速發現數據量變化但最小支持度不變的關聯規則，D.W.Cheung等人提出FUP算法[3]以及T.F.Gharib等人提出FIM算法[4]，且FIM比FUP執行效率高；為能發現數據量不變但最小支持度變化的關聯規則，馮玉才等人提出了IUA算法[5]及楊學兵等人提出了AIUA算法[6]，AIUA從IUA改進而得，所以AIUA比IUA執行效率更高。可在現實工作中，數據量和最小支持度可能同時變化，為能快速發現兩者同時變化后的關聯規則，皋軍等人提出My_IUA算法[7]以及唐璐等人提出IFU算法[8]，但My_IUA算法在數據量增加且支持度變大時存在頻繁項集遺漏以及數據量增加且支持度變小的時候存在頻繁項集發現錯誤的情況；……