一種改進(jìn)apriori算法研究

《一種改進(jìn)apriori算法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、一種改進(jìn)的算法研究摘要：算法是一種最有影響的挖掘關(guān)聯(lián)規(guī)則的算法。該算法的基本思想是，首先找出所有的頻集。通過(guò)頻集，得出關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。本論文提出改進(jìn)的算法，主要是通過(guò)引入興趣項(xiàng)、頻數(shù)閥值，來(lái)提高挖掘的效率；通過(guò)動(dòng)態(tài)挖掘數(shù)據(jù)關(guān)系來(lái)方便用戶(hù)的需求。通過(guò)多次實(shí)驗(yàn)證實(shí)，本算法較傳統(tǒng)算法在時(shí)空復(fù)雜度上有較大的提高。關(guān)鍵詞：算法；最小可信度；動(dòng)態(tài)挖掘；興趣項(xiàng)；頻數(shù)閥值A(chǔ)StudyofImprovingAlgorithmAbstract：Thealgorithmisoneofthemostinfluentialforminingassocia

2、tionrules.Thebasicideaofthealgorithmistofirstidentifyallthefrequentsets.Throughthefrequentsets,derivedassociationrules,theserulesmustsatisfyminimumsupportandminimumconfidence.Thispaperpresentsimprovedalgorithms,mainlythroughtheintroductionofinterestinitems,frequencythreshold,toimprov

3、etheminingefficiency;relationshipsthroughdynamicdataminingtofacilitatetheneedsofusers.Confirmedbymanyexperiments,thisalgorithmisbetterthantraditionalalgorithmsintimeandspacecomplexity.Keywords：algorithm;minimumconfidence;dynamicmining;interestitems;frequencythreshold1前言隨著人工智能、數(shù)據(jù)庫(kù)技術(shù)和數(shù)

4、理統(tǒng)計(jì)等技術(shù)的發(fā)展，數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)(KDD)和數(shù)據(jù)挖掘技術(shù)(DM)隨之而生。在事務(wù)數(shù)據(jù)庫(kù)中挖掘關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的重要研究方向，關(guān)聯(lián)規(guī)則是KDD研究中一個(gè)重要的研究課題，用于發(fā)現(xiàn)大量數(shù)據(jù)的項(xiàng)集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系[1]。數(shù)據(jù)挖掘的主要技術(shù)為關(guān)聯(lián)規(guī)則、聚類(lèi)、粗糙集、神經(jīng)網(wǎng)絡(luò)和遺傳算法等。關(guān)聯(lián)規(guī)則表示數(shù)據(jù)庫(kù)中一組對(duì)象之間某種關(guān)聯(lián)關(guān)系的規(guī)則，它在數(shù)據(jù)挖掘領(lǐng)域應(yīng)用很廣泛。它可以分成兩個(gè)子問(wèn)題[2]，尋找滿足最小支持度的頻繁項(xiàng)目集和用頻繁項(xiàng)目集，根據(jù)最小可信度來(lái)產(chǎn)生關(guān)聯(lián)規(guī)則。其中第一個(gè)問(wèn)題是開(kāi)銷(xiāo)最大的,因此目前大多數(shù)關(guān)聯(lián)規(guī)則挖掘算法都致力于提高尋找頻繁項(xiàng)目集的效率

5、。有一些方法擴(kuò)展了關(guān)聯(lián)規(guī)則，如數(shù)值型關(guān)聯(lián)規(guī)則[3]，多層關(guān)聯(lián)規(guī)則[4]。目前已提出了許多挖掘關(guān)聯(lián)規(guī)則的算法，其中最為經(jīng)典的是算法。本文是在算法的基礎(chǔ)之上，通過(guò)引入興趣項(xiàng)和頻數(shù)閥值來(lái)減少對(duì)數(shù)據(jù)庫(kù)的檢索。采用動(dòng)態(tài)挖掘來(lái)方便用戶(hù)需求，能很好的滿足客服的需求，提高算法的效率。2關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則挖掘起源于對(duì)超市購(gòu)物問(wèn)題的分析，用于發(fā)現(xiàn)交易數(shù)據(jù)庫(kù)中不同商品之間的聯(lián)系，這些聯(lián)系反映了顧客購(gòu)買(mǎi)行為模式。發(fā)現(xiàn)這樣的聯(lián)系可以應(yīng)用于顧客購(gòu)物分析、目錄設(shè)計(jì)、商品廣告郵寄分析等。在數(shù)據(jù)挖掘研究領(lǐng)域，對(duì)于關(guān)聯(lián)規(guī)則挖掘的研究開(kāi)展得比較深入，已提出了多種關(guān)聯(lián)規(guī)則挖掘算法。目前，關(guān)聯(lián)規(guī)則挖掘已成

6、功應(yīng)用于各個(gè)相關(guān)領(lǐng)域，成為數(shù)據(jù)挖掘中最成熟、最主要、最廣泛的研究?jī)?nèi)容之一[5]。2.1相關(guān)概念為了便于描述，在此約定：表示事務(wù)數(shù)據(jù)庫(kù)中的一個(gè)屬性，是事務(wù)數(shù)據(jù)庫(kù)中所有屬性的集合，表示事務(wù)數(shù)據(jù)庫(kù)中的一個(gè)事務(wù)，表示一個(gè)事務(wù)數(shù)據(jù)庫(kù)，表示事務(wù)數(shù)據(jù)庫(kù)的事務(wù)數(shù)。這里，集合中的元素可以重復(fù)。為避免重復(fù)的事務(wù)被遮蓋，本文給事務(wù)數(shù)據(jù)庫(kù)中的每一個(gè)事務(wù)指定一個(gè)唯一的標(biāo)識(shí)符。項(xiàng)集的支持度是數(shù)據(jù)庫(kù)中包含的事務(wù)在整個(gè)數(shù)據(jù)庫(kù)中所占的比率。關(guān)聯(lián)規(guī)則的置信度是數(shù)據(jù)庫(kù)中項(xiàng)集出現(xiàn)時(shí)項(xiàng)集出現(xiàn)的條件概率。支持度的閥值是關(guān)聯(lián)規(guī)則挖掘時(shí)項(xiàng)集必須滿足的最小支持度。置信度的閥值是關(guān)聯(lián)規(guī)則必須滿足的最小置信度。支持

7、度大于或等于支持度的閥值的項(xiàng)集稱(chēng)為頻繁項(xiàng)集。2.2傳統(tǒng)的算法介紹首先需要挖掘出頻繁1-項(xiàng)集；然后，繼續(xù)采用遞推的方式來(lái)挖掘頻繁k-項(xiàng)集（k>1），具體做法是：在挖掘出候選頻繁k-項(xiàng)集之后，根據(jù)最小置信度來(lái)篩選，得到頻繁k-項(xiàng)集。最后合并全部的頻繁k-項(xiàng)集（k>0）。置信度大于給定最小置信度的關(guān)聯(lián)規(guī)則稱(chēng)為頻繁關(guān)聯(lián)規(guī)則。在這一步，首先需要從頻繁項(xiàng)集入手，首先挖掘出全部的關(guān)聯(lián)規(guī)則，然后根據(jù)來(lái)得到頻繁關(guān)聯(lián)規(guī)則。2.3示例說(shuō)明算法設(shè)事務(wù)數(shù)據(jù)庫(kù)如表1所示，為50%，為70%，求事務(wù)數(shù)據(jù)庫(kù)D中的頻繁關(guān)聯(lián)規(guī)則。表1事務(wù)數(shù)據(jù)庫(kù)表項(xiàng)目集1ABCDE2ABC3CDEF4ABE執(zhí)行過(guò)程

8、如下：第一步：求頻繁項(xiàng)集