關(guān)聯(lián)規(guī)則的增量更新算法研究

《關(guān)聯(lián)規(guī)則的增量更新算法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、關(guān)聯(lián)規(guī)則的增量更新算法研究(1)摘?要?隨著數(shù)據(jù)庫的不斷變化，關(guān)聯(lián)規(guī)則的增量更新變得尤為重要。為了漣更好的對關(guān)聯(lián)規(guī)則進(jìn)行有效的更新，本文輻對已經(jīng)提出的經(jīng)典的關(guān)聯(lián)規(guī)則更新算法FィUP和IUA算法進(jìn)行分析，指出其優(yōu)缺瀹點(diǎn)；最后對另外的改進(jìn)算法，做一個(gè)簡單迫的敘述。關(guān)鍵詞?數(shù)據(jù)庫；關(guān)聯(lián)規(guī)則；增ヰ量更新?關(guān)聯(lián)規(guī)則反映了數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)遣目之間有趣的關(guān)聯(lián)關(guān)系，而其中發(fā)現(xiàn)頻繁ね項(xiàng)目集是關(guān)聯(lián)規(guī)則挖掘應(yīng)用中的關(guān)鍵技術(shù)谫和步驟。關(guān)于頻繁項(xiàng)目集的挖掘算法研究腱，人們對此進(jìn)行了大量的工作，其中以R.Agrawal等人提出的Apr

2、iori、AprioriTid等算法最具靖有影響力和代表性。而這些算法的提出都驕?zhǔn)窃谕诰驍?shù)據(jù)庫和最小支持度不變的條件下進(jìn)行的。但實(shí)際中，遇到的情況可能是毹：隨著時(shí)間的推移，挖掘數(shù)據(jù)庫的規(guī)?？蓮[能不斷膨脹或需要?jiǎng)h除一部分記錄，或者舞需要對最小支持度進(jìn)行調(diào)整從而逐步聚集填到我們感興趣的頻繁項(xiàng)目集上。因而如何若從數(shù)據(jù)發(fā)生變動(dòng)后的數(shù)據(jù)庫中高效地對已木經(jīng)推導(dǎo)出的關(guān)聯(lián)規(guī)則進(jìn)行更新，具有非常亠重要的應(yīng)用價(jià)值，這就是所謂的增量式挖纓掘關(guān)聯(lián)規(guī)則的問題。1?關(guān)聯(lián)規(guī)則問題描嶼述：設(shè)I={i1，i2，...，im苧}是m個(gè)不同

3、項(xiàng)目的集合，給定一個(gè)事務(wù)︼數(shù)據(jù)庫D，其中D每一個(gè)事務(wù)T是I中一︱組項(xiàng)目的集合，即TI，T有一個(gè)惟一的統(tǒng)標(biāo)志符TID。如果對于I中的一個(gè)子集欷X，有XT，我們就說一個(gè)事務(wù)T包含Xサ。一條關(guān)聯(lián)規(guī)則(associatio13/13捫nrule)就是一個(gè)形如X=>Y的蘊(yùn)涵式，其中X，YT，而X∩Y=Φ。關(guān)鐙聯(lián)規(guī)則成立的條件是：①它具有最小支持鬣度s，即事務(wù)數(shù)據(jù)庫D中至少有s%的事彤務(wù)包含X∪Y；②它具有最小可信度c，齡即在事務(wù)數(shù)據(jù)庫D中包含X的事務(wù)中至少有c%同時(shí)也包含Y。給定一個(gè)事務(wù)集DЪ，挖掘關(guān)聯(lián)規(guī)則問題就

4、是產(chǎn)生支持度和可皋信度分別大于用戶給定的最小支持度和最小可信度的關(guān)聯(lián)規(guī)則，也就是產(chǎn)生強(qiáng)規(guī)則菜的問題。關(guān)聯(lián)規(guī)則的挖掘問題可以分解為搬以下兩個(gè)問題：(1)找出事務(wù)數(shù)據(jù)庫中妝所有具有用戶最小支持度的項(xiàng)目集。具有婦用戶指定最小支持度的項(xiàng)目集稱為頻繁項(xiàng)鄒目集，反之稱為非頻繁項(xiàng)目集。一個(gè)項(xiàng)目中所含項(xiàng)目的個(gè)數(shù)稱為該項(xiàng)目的長度。(蠢2)利用頻繁項(xiàng)目集生成關(guān)聯(lián)規(guī)則。對于睇每一個(gè)頻繁項(xiàng)目集A，若BA，B≠Φ，恚且support(A)/suppor入t(B)>minconf，則有關(guān)聯(lián)規(guī)郫則B=>(A-B)。目前大多數(shù)的研究

5、主要集中在第一個(gè)問題上面。2?Apr澍iori核心算法[1]Agrawal唼等人于1994年提出了一個(gè)挖掘顧客交炫易數(shù)據(jù)庫中項(xiàng)集間的關(guān)聯(lián)規(guī)則的重要方法熠Apriori算法，其核心是基于兩個(gè)庖階段頻繁項(xiàng)集思想的遞推算法。算法的基命本思想是首先找出所有的頻集，這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度魂一樣。然后由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，嫌這些規(guī)則必須滿足最小支持度和最小可信年度。Apriori核心算法思想簡要描Ё述如下：該算法中有兩個(gè)關(guān)鍵步驟連接步噔和剪枝步。(1)連接步：為找出Lk(竦13/13頻繁k一

6、項(xiàng)集)，通過Lk-1與自身連郡接，產(chǎn)生候選k-項(xiàng)集，該候選項(xiàng)集記作圊Ck；其中Lk-1的元素是可連接的。氌(2)剪枝步：Ck是Lk的超集，即它佃的成員可以是也可以不是頻繁的，但所有析的頻繁一項(xiàng)集都包含在Ck中。掃描數(shù)據(jù)綣庫，確定Ck中每一個(gè)候選的計(jì)數(shù)，從而﹂確定Lk(計(jì)數(shù)值不小于最小支持度計(jì)數(shù)遁的所有候選是頻繁的，從而屬于Lk)。芒然而，Ck可能很大，這樣所涉及的計(jì)算狼量就很大。為壓縮Ck，使用Aprio弧ri性質(zhì)：任何非頻繁的(k-1)-項(xiàng)顆集都不可能是頻繁k-項(xiàng)集的子集。因此棘，如果一個(gè)候選k-項(xiàng)集的(

7、k-1)項(xiàng)孤集不在Lk中，則該候選項(xiàng)也不可能是頻ɑ繁的，從而可以由Ck中刪除。這種子集瞳測試可以使用所有頻繁項(xiàng)集的散列樹快速搞完成。這個(gè)方法要求多次掃描可能很大的縈交易數(shù)據(jù)庫，即如果頻集最多包含10個(gè)眥項(xiàng)，那么就需要掃描交易數(shù)據(jù)庫10遍，黍這需要很大的I/O負(fù)載?？赡墚a(chǎn)生大量錒的候選集，以及可能需要重復(fù)掃描數(shù)據(jù)庫輞，是Apriori算法的兩大缺點(diǎn)。3釓?關(guān)聯(lián)規(guī)則增量更新關(guān)聯(lián)規(guī)則反映了數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)目之間有趣的關(guān)聯(lián)關(guān)系，而其顴中發(fā)現(xiàn)頻繁項(xiàng)目集是關(guān)聯(lián)規(guī)則挖掘應(yīng)用中嘉的關(guān)鍵技術(shù)和步驟。關(guān)于頻繁項(xiàng)目集的挖х掘算法

8、研究，人們對此進(jìn)行了大量的工作次，其中以R.Agrawal等人提出的蘑Apriori、AprioriTid等算法最具有影響力和代表性。而這些算法的提出都是在挖掘數(shù)據(jù)庫和最小支持度兕不變的條件下進(jìn)行的。實(shí)際中，數(shù)據(jù)庫的獅規(guī)模隨著時(shí)間，可能不斷膨脹或需要?jiǎng)h除循13/13一部分記錄，或者需要對最小支持度進(jìn)行お調(diào)整從而逐步聚集到我們感興趣的頻繁項(xiàng)氐目集上。因而如何高效地從更新后的數(shù)據(jù)鰣庫中對已經(jīng)推導(dǎo)出的關(guān)聯(lián)規(guī)則進(jìn)行更