一種混合型的增量數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘算法

鄧廣彪

摘要：在數(shù)據(jù)庫(kù)中增加數(shù)據(jù)且調(diào)整最小支持度時(shí)，數(shù)據(jù)庫(kù)中關(guān)聯(lián)規(guī)則會(huì)發(fā)生變化，為從數(shù)據(jù)量和最小支持度同時(shí)發(fā)生變化的數(shù)據(jù)庫(kù)中快速獲取頻繁項(xiàng)集，發(fā)現(xiàn)變化后的關(guān)聯(lián)規(guī)則，通過(guò)對(duì)FIM和AIUA算法進(jìn)行分析，提出一種結(jié)合兩種算法優(yōu)點(diǎn)的增量數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘My_FIM_AIUA算法，該算法能減少數(shù)據(jù)庫(kù)掃描次數(shù)，減少候選項(xiàng)集數(shù)量。通過(guò)實(shí)驗(yàn)表明My_FIM_AIUA算法能在數(shù)據(jù)量和最小支持度同時(shí)變化時(shí)快速找到頻繁項(xiàng)集，提高挖掘增量數(shù)據(jù)關(guān)聯(lián)規(guī)則的速度。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則；增量數(shù)據(jù)；支持度變化

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 概述

關(guān)聯(lián)規(guī)則挖掘是指從海量數(shù)據(jù)中尋找頻繁在一起出現(xiàn)的事務(wù)及規(guī)律，經(jīng)典的算法有Apriori算法和FP增長(zhǎng)算法，但這兩種算法都是面向數(shù)據(jù)量不變且最小支持度不變[1]。關(guān)聯(lián)規(guī)則挖掘經(jīng)常會(huì)出現(xiàn)數(shù)據(jù)量、最小支持度變化的情況，那么關(guān)聯(lián)規(guī)則增量更新主要分為數(shù)據(jù)量不變最小支持度變大/變小、最小支持度不變而數(shù)據(jù)量增加/減少、最小支持度和數(shù)據(jù)量?jī)烧咄瑫r(shí)發(fā)生變化三種[2]。為能快速發(fā)現(xiàn)數(shù)據(jù)量變化但最小支持度不變的關(guān)聯(lián)規(guī)則，D.W.Cheung等人提出FUP算法[3]以及T.F.Gharib等人提出FIM算法[4]，且FIM比FUP執(zhí)行效率高；為能發(fā)現(xiàn)數(shù)據(jù)量不變但最小支持度變化的關(guān)聯(lián)規(guī)則，馮玉才等人提出了IUA算法[5]及楊學(xué)兵等人提出了AIUA算法[6]，AIUA從IUA改進(jìn)而得，所以AIUA比IUA執(zhí)行效率更高?？稍诂F(xiàn)實(shí)工作中，數(shù)據(jù)量和最小支持度可能同時(shí)變化，為能快速發(fā)現(xiàn)兩者同時(shí)變化后的關(guān)聯(lián)規(guī)則，皋軍等人提出My_IUA算法[7]以及唐璐等人提出IFU算法[8]，但My_IUA算法在數(shù)據(jù)量增加且支持度變大時(shí)存在頻繁項(xiàng)集遺漏以及數(shù)據(jù)量增加且支持度變小的時(shí)候存在頻繁項(xiàng)集發(fā)現(xiàn)錯(cuò)誤的情況；IFU算法是在FUP和IUA算法的基礎(chǔ)上提出并改進(jìn)。為此，在總結(jié)FIM和AIUA算法優(yōu)點(diǎn)的基礎(chǔ)上，提出My_FIM_AIUA算法，在數(shù)據(jù)量增加和最小支持度變大時(shí)改進(jìn)FIM算法快速找到頻繁項(xiàng)集，相對(duì)FIM算法減少掃描新增數(shù)據(jù)的次數(shù)；在數(shù)據(jù)量增加和最小支持度變小時(shí)拓展AIUA算法找到相關(guān)頻繁項(xiàng)集，修正My_IUA算法的錯(cuò)誤，減少候選項(xiàng)集的數(shù)量。My_FIM_AIUA算法在FIM和AIUA基礎(chǔ)上提出，執(zhí)行速度相比IFU算法要更快。

2 FIM和AIUA算法

2.1 FIM算法基本思想

FIM算法是最小支持度不變、數(shù)據(jù)量變化時(shí)的一種關(guān)聯(lián)規(guī)則挖掘算法，它的基本思想是如果一個(gè)項(xiàng)集要是最終的頻繁項(xiàng)集，要么是原數(shù)據(jù)庫(kù)DB中的頻繁項(xiàng)集，要么是新增數(shù)據(jù)庫(kù)db中的頻繁項(xiàng)集。該算法假設(shè)DB中的現(xiàn)有頻繁項(xiàng)集[LDBk]都已保存，首先掃描新增數(shù)據(jù)得到db的頻繁項(xiàng)集[Ldbk]，將[LDBk]和[Ldbk]中相同的頻繁項(xiàng)集加入到最終頻繁項(xiàng)集[L'k]并將其從[LDBk]和[Ldbk]中刪除；接著掃描db對(duì)[LDBk]剩余的頻繁項(xiàng)集更新支持度計(jì)數(shù)并將滿足最小支持度計(jì)數(shù)的加入[L'k]；最后掃描DB對(duì)[Ldbk]中剩余的頻繁項(xiàng)集更新支持度計(jì)數(shù)并將滿足最小支持度的加入[L'k]。

2.2 AIUA算法基本思想

從實(shí)驗(yàn)結(jié)果可知，My_FIM_AIUA算法的運(yùn)行時(shí)間均比Apriori和IFU算法要少，說(shuō)明My_FIM_AIUA算法執(zhí)行速度快。雖然3個(gè)算法掃描數(shù)據(jù)庫(kù)的次數(shù)一致，但My_FIM_AIUA算法大大減少了候選項(xiàng)集的數(shù)量，所以在掃描數(shù)據(jù)庫(kù)時(shí)對(duì)候選項(xiàng)集支持度計(jì)數(shù)所花時(shí)間變少。從挖掘得到的頻繁項(xiàng)集個(gè)數(shù)看，My_FIM_AIUA算法與Apriori算法挖掘結(jié)果基本一致，說(shuō)明My_FIM_AIUA算法的正確性。

My_FIM_AIUA算法的缺點(diǎn)是需要保存[Lk]中頻繁項(xiàng)集的支持度計(jì)數(shù)，若[Lk]非常大超過(guò)運(yùn)行時(shí)內(nèi)存的可使用空間將成為本算法的瓶頸，而且該算法在支持度變小時(shí)與其他算法類似，依然需要多次掃描DB來(lái)獲得頻繁項(xiàng)集。

5 結(jié)束語(yǔ)

在信息量暴增和急需數(shù)據(jù)背后知識(shí)指導(dǎo)工作的信息時(shí)代，如何快速發(fā)現(xiàn)增量數(shù)據(jù)和最小支持度變化的關(guān)聯(lián)規(guī)則是企事業(yè)單位信息管理系統(tǒng)必須要解決的問(wèn)題。該文提出的My_FIM_AIUA算法在一定程度上提高了數(shù)據(jù)量和最小支持度同時(shí)變化時(shí)頻繁項(xiàng)集的挖掘效率，但該算法需要較大的內(nèi)存空間以及多次掃描數(shù)據(jù)庫(kù)，如何能減少掃描數(shù)據(jù)庫(kù)的次數(shù)或減少候選項(xiàng)集的數(shù)量將能進(jìn)一步提高算法的執(zhí)行效率，這是以后進(jìn)一步研究待解決的問(wèn)題。

參考文獻(xiàn)：

[1] 劉凱.彭國(guó)志.關(guān)聯(lián)規(guī)則挖掘方法研究[J].電腦知識(shí)與技術(shù)，2010，6（5）：1029-1031.

[2] 涂明，張公讓，程業(yè)媛.一種高效的關(guān)聯(lián)規(guī)則增量式更新算法[J].微電子學(xué)與計(jì)算機(jī)，2010，27（9）：56-60.

[3] D.W.Cheung， J.Han， V.T.Ng. Maintenance of Discovered Association Rules in Large Databases： An Incremental Updating Technique[C].Proceedings of the 12th international conference on Data Engineering， 1996：212-223.

[4] T.F.Gharib， M.Taha， and H.Nassar， "An efficient technique for incremental updating of association rules. " International Journal of Hybrid Intelligent Systems，pages 45-53，May 2008.

[5] 馮玉才，馮劍琳.關(guān)聯(lián)規(guī)則的增量式更新算法[J].軟件學(xué)報(bào)，1998，9（4）：301-306.

[6] 楊學(xué)兵，安紅梅.一種高效的關(guān)聯(lián)規(guī)則增量式更新算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2007，17（1）：108-110+113.

[7] 皋軍，王建東.關(guān)聯(lián)規(guī)則挖掘算法更新與拓展[J].計(jì)算機(jī)工程與應(yīng)用，2003，35：178-179+202.

[8] 唐璐，江紅，上官秋子. 一種改進(jìn)的關(guān)聯(lián)規(guī)則的增量式更新算法[J].計(jì)算機(jī)應(yīng)用與軟件，2012，29（4）：246-248.

My_FIM_AIUA算法的缺點(diǎn)是需要保存[Lk]中頻繁項(xiàng)集的支持度計(jì)數(shù)，若[Lk]非常大超過(guò)運(yùn)行時(shí)內(nèi)存的可使用空間將成為本算法的瓶頸，而且該算法在支持度變小時(shí)與其他算法類似，依然需要多次掃描DB來(lái)獲得頻繁項(xiàng)集。

5 結(jié)束語(yǔ)

在信息量暴增和急需數(shù)據(jù)背后知識(shí)指導(dǎo)工作的信息時(shí)代，如何快速發(fā)現(xiàn)增量數(shù)據(jù)和最小支持度變化的關(guān)聯(lián)規(guī)則是企事業(yè)單位信息管理系統(tǒng)必須要解決的問(wèn)題。該文提出的My_FIM_AIUA算法在一定程度上提高了數(shù)據(jù)量和最小支持度同時(shí)變化時(shí)頻繁項(xiàng)集的挖掘效率，但該算法需要較大的內(nèi)存空間以及多次掃描數(shù)據(jù)庫(kù)，如何能減少掃描數(shù)據(jù)庫(kù)的次數(shù)或減少候選項(xiàng)集的數(shù)量將能進(jìn)一步提高算法的執(zhí)行效率，這是以后進(jìn)一步研究待解決的問(wèn)題。

參考文獻(xiàn)：

[1] 劉凱.彭國(guó)志.關(guān)聯(lián)規(guī)則挖掘方法研究[J].電腦知識(shí)與技術(shù)，2010，6（5）：1029-1031.

[2] 涂明，張公讓，程業(yè)媛.一種高效的關(guān)聯(lián)規(guī)則增量式更新算法[J].微電子學(xué)與計(jì)算機(jī)，2010，27（9）：56-60.

[3] D.W.Cheung， J.Han， V.T.Ng. Maintenance of Discovered Association Rules in Large Databases： An Incremental Updating Technique[C].Proceedings of the 12th international conference on Data Engineering， 1996：212-223.

[4] T.F.Gharib， M.Taha， and H.Nassar， "An efficient technique for incremental updating of association rules. " International Journal of Hybrid Intelligent Systems，pages 45-53，May 2008.

[5] 馮玉才，馮劍琳.關(guān)聯(lián)規(guī)則的增量式更新算法[J].軟件學(xué)報(bào)，1998，9（4）：301-306.

[6] 楊學(xué)兵，安紅梅.一種高效的關(guān)聯(lián)規(guī)則增量式更新算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2007，17（1）：108-110+113.

[7] 皋軍，王建東.關(guān)聯(lián)規(guī)則挖掘算法更新與拓展[J].計(jì)算機(jī)工程與應(yīng)用，2003，35：178-179+202.

[8] 唐璐，江紅，上官秋子. 一種改進(jìn)的關(guān)聯(lián)規(guī)則的增量式更新算法[J].計(jì)算機(jī)應(yīng)用與軟件，2012，29（4）：246-248.

My_FIM_AIUA算法的缺點(diǎn)是需要保存[Lk]中頻繁項(xiàng)集的支持度計(jì)數(shù)，若[Lk]非常大超過(guò)運(yùn)行時(shí)內(nèi)存的可使用空間將成為本算法的瓶頸，而且該算法在支持度變小時(shí)與其他算法類似，依然需要多次掃描DB來(lái)獲得頻繁項(xiàng)集。

5 結(jié)束語(yǔ)

在信息量暴增和急需數(shù)據(jù)背后知識(shí)指導(dǎo)工作的信息時(shí)代，如何快速發(fā)現(xiàn)增量數(shù)據(jù)和最小支持度變化的關(guān)聯(lián)規(guī)則是企事業(yè)單位信息管理系統(tǒng)必須要解決的問(wèn)題。該文提出的My_FIM_AIUA算法在一定程度上提高了數(shù)據(jù)量和最小支持度同時(shí)變化時(shí)頻繁項(xiàng)集的挖掘效率，但該算法需要較大的內(nèi)存空間以及多次掃描數(shù)據(jù)庫(kù)，如何能減少掃描數(shù)據(jù)庫(kù)的次數(shù)或減少候選項(xiàng)集的數(shù)量將能進(jìn)一步提高算法的執(zhí)行效率，這是以后進(jìn)一步研究待解決的問(wèn)題。

參考文獻(xiàn)：

[1] 劉凱.彭國(guó)志.關(guān)聯(lián)規(guī)則挖掘方法研究[J].電腦知識(shí)與技術(shù)，2010，6（5）：1029-1031.

[2] 涂明，張公讓，程業(yè)媛.一種高效的關(guān)聯(lián)規(guī)則增量式更新算法[J].微電子學(xué)與計(jì)算機(jī)，2010，27（9）：56-60.

[3] D.W.Cheung， J.Han， V.T.Ng. Maintenance of Discovered Association Rules in Large Databases： An Incremental Updating Technique[C].Proceedings of the 12th international conference on Data Engineering， 1996：212-223.

[4] T.F.Gharib， M.Taha， and H.Nassar， "An efficient technique for incremental updating of association rules. " International Journal of Hybrid Intelligent Systems，pages 45-53，May 2008.

[5] 馮玉才，馮劍琳.關(guān)聯(lián)規(guī)則的增量式更新算法[J].軟件學(xué)報(bào)，1998，9（4）：301-306.

[6] 楊學(xué)兵，安紅梅.一種高效的關(guān)聯(lián)規(guī)則增量式更新算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2007，17（1）：108-110+113.

[7] 皋軍，王建東.關(guān)聯(lián)規(guī)則挖掘算法更新與拓展[J].計(jì)算機(jī)工程與應(yīng)用，2003，35：178-179+202.

[8] 唐璐，江紅，上官秋子. 一種改進(jìn)的關(guān)聯(lián)規(guī)則的增量式更新算法[J].計(jì)算機(jī)應(yīng)用與軟件，2012，29（4）：246-248.