增量式關(guān)聯(lián)規(guī)則挖掘算法的研究

亓文娟

（1.武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院；2.認(rèn)知計(jì)算與智能信息處理福建省高校重點(diǎn)實(shí)驗(yàn)室，福建 武夷山 354300）

0 引言

關(guān)聯(lián)規(guī)則挖掘（Association Rule Mining）是數(shù)據(jù)挖掘中的重要研究?jī)?nèi)容，用于發(fā)現(xiàn)數(shù)據(jù)庫(kù)中項(xiàng)集之間的關(guān)聯(lián)關(guān)系。關(guān)聯(lián)規(guī)則中的經(jīng)典算法Apriori算法以最小支持度、最小置信度和數(shù)據(jù)庫(kù)中元組數(shù)都不變?yōu)榍疤幔⒅赜陟o態(tài)數(shù)據(jù)的挖掘，但實(shí)際情況下，數(shù)據(jù)挖掘卻是一個(gè)動(dòng)態(tài)的交互過程，需要不斷調(diào)整最小支持度、置信度兩個(gè)閾值或者數(shù)據(jù)庫(kù)中的數(shù)據(jù)不斷地發(fā)生更新，這時(shí)候需要尋找真正感興趣的規(guī)則，就必須重新進(jìn)行挖掘，如果繼續(xù)采用Apriori算法，不僅效率非常低，還浪費(fèi)了以前挖掘出來(lái)的信息。因此為了能快速更新關(guān)聯(lián)規(guī)則，降低重新掃描數(shù)據(jù)庫(kù)的代價(jià)，在此實(shí)際需求的驅(qū)動(dòng)下，注重于動(dòng)態(tài)數(shù)據(jù)挖掘的增量式關(guān)聯(lián)規(guī)則挖掘成為關(guān)聯(lián)規(guī)則挖掘的一個(gè)重要研究方向。

1 增量式關(guān)聯(lián)規(guī)則

增量式關(guān)聯(lián)規(guī)則挖掘的主要思想是在更新的數(shù)據(jù)庫(kù)或參數(shù)上，充分利用原有挖掘規(guī)則，發(fā)現(xiàn)滿足條件的新規(guī)則，刪除失效的舊規(guī)則,目的是盡量減少計(jì)算量。增量式關(guān)聯(lián)規(guī)則挖掘算法主要解決以下三類問題：①即在原始數(shù)據(jù)庫(kù)D不變，最小支持度和置信度發(fā)生變化時(shí)，如何生成D中新的關(guān)聯(lián)規(guī)則；②在最小支持度和置信度不變，數(shù)據(jù)庫(kù)發(fā)生更新時(shí)，如何生成新數(shù)據(jù)庫(kù)D∪d或D-d的關(guān)聯(lián)規(guī)則；③在原始數(shù)據(jù)庫(kù)發(fā)生更新的同時(shí)，最小支持度和置信度同時(shí)發(fā)生變化時(shí)，如何生成新數(shù)據(jù)庫(kù)在新支持度下的關(guān)聯(lián)規(guī)則。馮玉才等人提出了IUA算法和PIUA算法[1]針對(duì)第一類問題進(jìn)行了研究，針對(duì)第二類問題，D.W.Cheung等人對(duì)新數(shù)據(jù)庫(kù)D∪d的情況提出FUP算法[2]和 FUP2算法[3]，其中FUP2算法同時(shí)考慮了新數(shù)據(jù)庫(kù)D∪d和D-d的情況。徐文拴等[4]針對(duì)第三類情況中數(shù)據(jù)集增加和最小支持度同時(shí)變化的關(guān)聯(lián)規(guī)則更新問題進(jìn)行了研究。本文重點(diǎn)研究關(guān)聯(lián)規(guī)則增量式更新算法FUP算法的思想，算法的優(yōu)缺點(diǎn)及改進(jìn)，為增量式關(guān)聯(lián)規(guī)則挖掘奠定理論基礎(chǔ)。

1.1 FUP算法的基本思想

當(dāng)數(shù)據(jù)庫(kù)中的數(shù)據(jù)發(fā)生變化時(shí)，為了獲取更新后的關(guān)聯(lián)規(guī)則，最簡(jiǎn)單的辦法是重新運(yùn)用Apriori算法對(duì)數(shù)據(jù)庫(kù)進(jìn)行挖掘，但是這樣做不僅效率較低，而且沒有充分利用以前挖掘的結(jié)果，在眾多的增量式關(guān)聯(lián)規(guī)則挖掘算法中，D.W.Cheung等提出的FUP算法最為典型，它是Apriori算法的改進(jìn)算法，與Apriori算法的框架一致[5]，主要解決在支持度和置信度不變，數(shù)據(jù)集增加的情況下，如何生成新的頻繁項(xiàng)集的算法。

設(shè)原始數(shù)據(jù)集為D，新增數(shù)據(jù)集為d，則變化后的數(shù)據(jù)集為（D+d），假設(shè)已經(jīng)采用Apriori算法獲得原始數(shù)據(jù)集D的頻繁項(xiàng)集L（D），則FUP算法的基本思想是：

1）利用Apriori算法生成新增數(shù)據(jù)集d的頻繁項(xiàng)集L（D），比較L（D）和L（D），根據(jù)某一項(xiàng)集t在D中為頻繁項(xiàng)集，在d中也為頻繁項(xiàng)集，那么該項(xiàng)目集在（D+d）中也為頻繁項(xiàng)集的理論，找出相同部分，將其放入（D+d）的頻繁項(xiàng)集L（D+d）中。

2）對(duì)于項(xiàng)集t∈L（d）且t?L（D）的情況，掃描D得到t在D中的支持度supportD，再根據(jù)d中以求出的支持度supportd，求出t在（D+d）中的支持度supportD+d，如果supportD+d≥minsup，則把t放入（D+d）的頻繁項(xiàng)集L（D+d）中，否則t不是頻繁項(xiàng)集。

3）對(duì)于項(xiàng)集t∈L（D）且t?L（d）的情況，掃描d得到t在d中的支持度supportd，再根據(jù)D中以求出的支持度supportD，求出t在（D+d）中的支持度supportD+d，如果supportD+d≥minsup，則把t放入（D+d）的頻繁項(xiàng)集L（D+d）中，否則t不是頻繁項(xiàng)集。

4）如果某一項(xiàng)集t在D中為非頻繁項(xiàng)集，在d中也為非頻繁項(xiàng)集，那么該項(xiàng)目集在（D+d）中也一定為非頻繁項(xiàng)集。

1.2 FUP算法的描述

FUP算法執(zhí)行如下：

1.3 FUP算法實(shí)例分析

已知原始數(shù)據(jù)集D，新增數(shù)據(jù)集d，設(shè)最小支持度為0.4，圖1是FUP算法尋找頻繁項(xiàng)集的過程。

圖1 FUP算法尋找頻繁項(xiàng)集過程

在圖1（1）中L（D）表示從原始數(shù)據(jù)集D中獲得的頻繁項(xiàng)集；（2）中利用Apriori算法生成新增數(shù)據(jù)集d的頻繁項(xiàng)集L（d）；（3）中比較L（D）和L（d），找出相同的頻繁項(xiàng)集{C、D}放入到事務(wù)數(shù)據(jù)庫(kù)（L+d）的頻繁項(xiàng)集L（D+d）中；（4）中對(duì)于屬于D中頻繁項(xiàng)集，但非d中頻繁項(xiàng)集{A、A,D}的情況，則掃描d得到項(xiàng)集在d中的支持度分別為supportd={2/6，2/6}，再根據(jù)項(xiàng)集在D中的支持度supportD={5/10，5/10}，求出它在（L+d）中的支持度supportD+d={7/16，7/16}，由于supportD+d大于最小支持度0.4，則把項(xiàng)集{A、A,D}也放入事務(wù)數(shù)據(jù)庫(kù)（L+d）的頻繁項(xiàng)集L（D+d）中；（5）中對(duì)于屬于d中頻繁項(xiàng)集，但非D中頻繁項(xiàng)集{E、D,E}的情況，與（4）類似，重新掃描D，確定是否是頻繁項(xiàng)集，由于項(xiàng)集{E、D,E}在（L+d）中的支持度supportD+d={4/16，3/16}均小于最小支持度，因此是非頻繁項(xiàng)集。（6）為新數(shù)據(jù)集的頻繁項(xiàng)集。

1.4 FUP算法的優(yōu)缺點(diǎn)

FUP算法在新增數(shù)據(jù)集d與原始數(shù)據(jù)集D相差不大的情況下，較Apriori算法在效率方面有了很多的提升，主要體現(xiàn)在Apriori算法需要多次掃描數(shù)據(jù)庫(kù)，而FUP算法只有在確定項(xiàng)集t∈L（d）且t?L（D）的情況下，才需要掃描原始數(shù)據(jù)集；通過對(duì)K項(xiàng)集在原始數(shù)據(jù)集和新增數(shù)據(jù)集中是否頻繁的分析，可以過濾掉許多候選項(xiàng)集。FUP算法雖然對(duì)原始數(shù)據(jù)集挖掘結(jié)果進(jìn)行了使用，但是對(duì)于一些大數(shù)據(jù)集而言，該算法也存在著不足：由于候選項(xiàng)集的生成由Apriori連接來(lái)獲得，即使用L'k-1生成Ck，產(chǎn)生新增數(shù)據(jù)集的候選項(xiàng)集規(guī)模是巨大的，在處理這些候選項(xiàng)集時(shí)耗費(fèi)大量時(shí)間，而且其中有很多是非頻繁項(xiàng)集，影響了算法的效率；對(duì)候選項(xiàng)集進(jìn)行模式匹配時(shí)需要對(duì)整個(gè)數(shù)據(jù)庫(kù)進(jìn)行多次重復(fù)掃描，代價(jià)很大；算法對(duì)新增項(xiàng)目不敏感。

2 算法的改進(jìn)

針對(duì)FUP算法只考慮了支持度和置信度不變，數(shù)據(jù)集增加的情況，以及該算法存在的不足，眾多學(xué)者對(duì)該算法進(jìn)行了改進(jìn)。文獻(xiàn)[4]針對(duì)數(shù)據(jù)庫(kù)和最小支持度同時(shí)發(fā)生變化的情況，提出了哈希增量更新算法HIUA，該算法結(jié)合hash定位以及鏈表插入、刪除的高效性，不生成候選項(xiàng)集，只掃描原始數(shù)據(jù)集一次，充分利用了原有的挖掘信息，算法效率較高。文獻(xiàn)[6]提出了基于臨時(shí)表的改進(jìn)算法MFUP，該算法適用于原始數(shù)據(jù)庫(kù)規(guī)模大，新增數(shù)據(jù)集相對(duì)小的情況，通過建立臨時(shí)表，來(lái)存放新增數(shù)據(jù)集的頻繁項(xiàng)集，充分利用原始數(shù)據(jù)集挖掘的結(jié)果，大大減少了對(duì)數(shù)據(jù)的重復(fù)掃描，提高了算法的效率。文獻(xiàn)[7]提出了IFU算法，用于解決數(shù)據(jù)庫(kù)和最小支持度都發(fā)生改變時(shí)關(guān)聯(lián)規(guī)則的增量式更新問題，該算法減少了對(duì)原始數(shù)據(jù)集和新增數(shù)據(jù)集的掃描次數(shù)，提高了算法的效率，但由于該算法使用了一次IUA算法，所以如何減少對(duì)原始數(shù)據(jù)集D的掃描次數(shù)有待進(jìn)一步研究。文獻(xiàn)[8]提出了一種基于矩陣的增量式關(guān)聯(lián)規(guī)則挖掘算法IUBM，充分利用原始數(shù)據(jù)集挖掘的結(jié)果，采用數(shù)組和位運(yùn)算，不管支持度如何變化，僅掃描一次新增數(shù)據(jù)集，不需要掃描原始數(shù)據(jù)集，同時(shí)在挖掘的過程中加入了剪枝算法，減少了大量不必要的比較和計(jì)算，該算法的時(shí)間復(fù)雜度和空間復(fù)雜度大大降低。

3 總結(jié)

增量式關(guān)聯(lián)規(guī)則挖掘算法大致分為基于Apriori算法的增量更新算法和基于FP-tree的增量更新算法兩類。本文對(duì)基于Apriori算法的增量式關(guān)聯(lián)規(guī)則算法FUP算法的基本思想，優(yōu)缺點(diǎn)進(jìn)行了探討，并通過具體實(shí)例說明發(fā)現(xiàn)頻繁項(xiàng)集的方法，最后針對(duì)算法不足指出了改進(jìn)算法，為增量式關(guān)聯(lián)規(guī)則挖掘奠定理論基礎(chǔ)。下一步工作的重點(diǎn)是根據(jù)數(shù)據(jù)庫(kù)中不同數(shù)據(jù)項(xiàng)的重要性不同問題，結(jié)合增量式關(guān)聯(lián)規(guī)則更新和多支持度的局限性，提出基于多支持度的增量式關(guān)聯(lián)規(guī)則挖掘算法。