基于閉項(xiàng)目集的Apriori算法改進(jìn)

《基于閉項(xiàng)目集的Apriori算法改進(jìn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、首都師范大學(xué)信息工程學(xué)院2013-2014學(xué)年第二學(xué)期2013碩士研究生計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)期末考試試卷課程名稱數(shù)據(jù)挖掘考試形式撰寫(xiě)學(xué)術(shù)論文考試時(shí)間2014.4.21考試對(duì)象2013級(jí)研究生姓名李燕學(xué)號(hào)2131002053任課教師利民成績(jī)基于閉項(xiàng)目集的Apriori算法李燕（首都師范大學(xué)信息工程學(xué)院，北京100089）摘要：本文針對(duì)Apriori算法中需要不斷掃描原始事務(wù)項(xiàng)集問(wèn)題，介紹了在某些情況下，可以大大減少掃描次數(shù)的close算法，同時(shí)對(duì)此算法給出了改進(jìn)的想法和簡(jiǎn)單實(shí)現(xiàn)。關(guān)鍵字：關(guān)聯(lián)規(guī)則Apriori算法頻繁閉項(xiàng)集、close算法AnimprovedApriorialgorithmA

2、bstract:ThisarticleinviewoftheApriorialgorithmneedtoconstantlyscantheoriginaltransactionitemsets，Introducedinsomecases,cangreatlyreducethenumberofscanningthecloseofthealgorithm,atthesametime,thisalgorithmgivestheimprovementideasandsimpleimplementation.Keywords:AssociationRules?AprioriAlgorithm?Fr

3、equentClosedItemSetcloseAlgorithm0前言　信息技術(shù)的不斷推廣應(yīng)用，將企業(yè)帶入了一個(gè)信息爆炸的時(shí)代。如何充分利用這些數(shù)據(jù)信息為企業(yè)決策者提供決策支持成為一個(gè)十分迫切的又棘手的問(wèn)題，人們除了利用現(xiàn)有的關(guān)系數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)查詢語(yǔ)句得到一般的直觀的信息以外，必須挖掘其內(nèi)含的、未知的卻又實(shí)際存在的數(shù)據(jù)關(guān)系。著名的Apriori算法是一種挖掘關(guān)聯(lián)規(guī)則的算法。本文利用事務(wù)集閉項(xiàng)集來(lái)在一定程度上減少數(shù)據(jù)事務(wù)集的掃描次數(shù)來(lái)減少Apriori算法的瓶頸。這有利于提高挖掘的速度和減少數(shù)據(jù)庫(kù)的I/O操作時(shí)間的開(kāi)銷。1關(guān)聯(lián)規(guī)則挖掘理論和基本概念　數(shù)據(jù)挖掘(DataMining)利用統(tǒng)計(jì)與

4、人工智能的算法,從龐大的企業(yè)歷史資料中,找出隱藏的規(guī)律并建立準(zhǔn)確的模型,用以預(yù)測(cè)未來(lái)。其中關(guān)聯(lián)規(guī)則(AssociationRules)的挖掘是數(shù)據(jù)挖掘中的一個(gè)重要問(wèn)題。關(guān)聯(lián)規(guī)則(AssocationRule)最由Agarwal等提出，用于交易數(shù)據(jù)庫(kù)。關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)熱點(diǎn)，它發(fā)現(xiàn)交易數(shù)據(jù)庫(kù)中不同商品(項(xiàng))之間的聯(lián)系，即關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則一般用以發(fā)現(xiàn)交易數(shù)據(jù)庫(kù)中不同商品(項(xiàng))之間的聯(lián)系,用這些規(guī)則找出顧客的購(gòu)買行為模式,比如購(gòu)買了某一種商品對(duì)購(gòu)買其他商品的影響,這種規(guī)則可以應(yīng)用于超市商品貨架設(shè)計(jì)、貨物擺放以及根據(jù)購(gòu)買模式對(duì)用戶進(jìn)行分類等。進(jìn)而引伸至尋找一個(gè)變量間不同選擇之間的關(guān)系

5、,或?qū)ふ也煌兞块g的關(guān)系。關(guān)聯(lián)規(guī)則中的基本概念主要包括：定義1.1：k-項(xiàng)集一個(gè)商品或者一個(gè)屬性稱為一個(gè)項(xiàng)目。多個(gè)項(xiàng)目的集合稱為項(xiàng)集。設(shè)i為數(shù)據(jù)庫(kù)D中全體項(xiàng)目的集合，集合x(chóng)={il，i2，?，ik}(x∈i且IXI=k)，稱為k-項(xiàng)集。定義1.2：事務(wù)一條事務(wù)，或者說(shuō)一條記錄，是形如{tid，X)的二元組，其中tid稱為事務(wù)標(biāo)識(shí)符，它唯一標(biāo)識(shí)該條記錄，X為項(xiàng)目集。要挖掘的數(shù)據(jù)集或者數(shù)據(jù)庫(kù)D是N條事務(wù)的集合，一條事務(wù)也稱為一條記錄，N為數(shù)據(jù)集D的記錄總數(shù)。若事務(wù)t包含項(xiàng)目集X中的所有項(xiàng)目，則稱事務(wù)t支持或包含項(xiàng)目集X。定義1.3：支持度計(jì)數(shù)和支持度數(shù)據(jù)庫(kù)TDB中包含(支持)項(xiàng)集X的事務(wù)的數(shù)

6、目稱為項(xiàng)集X的支持度計(jì)數(shù)，記為count(X)，support(X)=count(X)／N稱為項(xiàng)集X的支持度，其中N為數(shù)據(jù)庫(kù)中記錄總數(shù)。定義1.3：支持度計(jì)數(shù)和支持度數(shù)據(jù)庫(kù)TDB中包含(支持)項(xiàng)集X的事務(wù)的數(shù)目稱為項(xiàng)集X的支持度計(jì)數(shù)，記為count(X)，support(X)=count(X)／N稱為項(xiàng)集X的支持度，其中N為數(shù)據(jù)庫(kù)中記錄總數(shù)。定義1.4：頻繁項(xiàng)目集．支持度不小于用戶給定的最小支持度閾值(minsup)的項(xiàng)集稱為頻繁項(xiàng)目集，或者大項(xiàng)目集。所有的頻繁1-項(xiàng)集記為L(zhǎng)l定義1.5：關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則是形如X=>Y的蘊(yùn)涵式，X稱為關(guān)聯(lián)規(guī)則的前件或前提，Y稱為關(guān)聯(lián)規(guī)則的后件或結(jié)論。項(xiàng)集

7、XUY的支持度稱為關(guān)聯(lián)規(guī)則的支持度。定義1.6:置信度關(guān)聯(lián)規(guī)則X=>Y的置信度。確定Y在包含X的事務(wù)中出現(xiàn)的頻繁程度。confidence(X=>Y)=support(X∪Y)support(X)×100%支持度和置信度是描述關(guān)聯(lián)規(guī)則的兩個(gè)重要概念，前者用于衡量關(guān)聯(lián)規(guī)則在整個(gè)數(shù)據(jù)集中的統(tǒng)計(jì)重要性，后者用于衡量關(guān)聯(lián)規(guī)則的可信程度。一般來(lái)說(shuō)，只有支持度和置信度均較高的關(guān)聯(lián)規(guī)則才可能是用戶感興趣、有用的關(guān)聯(lián)規(guī)則。Agrawal等人建立了用