資源描述:
《基于閉項目集的Apriori算法改進》由會員上傳分享,免費在線閱讀,更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、首都師范大學信息工程學院2013-2014學年第二學期2013碩士研究生計算機應用技術(shù)專業(yè)期末考試試卷課程名稱數(shù)據(jù)挖掘考試形式撰寫學術(shù)論文考試時間2014.4.21考試對象2013級研究生姓名李燕學號2131002053任課教師利民成績基于閉項目集的Apriori算法李燕(首都師范大學信息工程學院,北京100089)摘要:本文針對Apriori算法中需要不斷掃描原始事務項集問題,介紹了在某些情況下,可以大大減少掃描次數(shù)的close算法,同時對此算法給出了改進的想法和簡單實現(xiàn)。關鍵字:關聯(lián)規(guī)則Apriori算法頻繁閉項集、close算法AnimprovedApriorialgorithmA
2、bstract:ThisarticleinviewoftheApriorialgorithmneedtoconstantlyscantheoriginaltransactionitemsets,Introducedinsomecases,cangreatlyreducethenumberofscanningthecloseofthealgorithm,atthesametime,thisalgorithmgivestheimprovementideasandsimpleimplementation.Keywords:AssociationRules?AprioriAlgorithm?Fr
3、equentClosedItemSetcloseAlgorithm0前言 信息技術(shù)的不斷推廣應用,將企業(yè)帶入了一個信息爆炸的時代。如何充分利用這些數(shù)據(jù)信息為企業(yè)決策者提供決策支持成為一個十分迫切的又棘手的問題,人們除了利用現(xiàn)有的關系數(shù)據(jù)庫標準查詢語句得到一般的直觀的信息以外,必須挖掘其內(nèi)含的、未知的卻又實際存在的數(shù)據(jù)關系。著名的Apriori算法是一種挖掘關聯(lián)規(guī)則的算法。本文利用事務集閉項集來在一定程度上減少數(shù)據(jù)事務集的掃描次數(shù)來減少Apriori算法的瓶頸。這有利于提高挖掘的速度和減少數(shù)據(jù)庫的I/O操作時間的開銷。1關聯(lián)規(guī)則挖掘理論和基本概念 數(shù)據(jù)挖掘(DataMining)利用統(tǒng)計與
4、人工智能的算法,從龐大的企業(yè)歷史資料中,找出隱藏的規(guī)律并建立準確的模型,用以預測未來。其中關聯(lián)規(guī)則(AssociationRules)的挖掘是數(shù)據(jù)挖掘中的一個重要問題。關聯(lián)規(guī)則(AssocationRule)最由Agarwal等提出,用于交易數(shù)據(jù)庫。關聯(lián)規(guī)則是數(shù)據(jù)挖掘領域的一個熱點,它發(fā)現(xiàn)交易數(shù)據(jù)庫中不同商品(項)之間的聯(lián)系,即關聯(lián)規(guī)則。關聯(lián)規(guī)則一般用以發(fā)現(xiàn)交易數(shù)據(jù)庫中不同商品(項)之間的聯(lián)系,用這些規(guī)則找出顧客的購買行為模式,比如購買了某一種商品對購買其他商品的影響,這種規(guī)則可以應用于超市商品貨架設計、貨物擺放以及根據(jù)購買模式對用戶進行分類等。進而引伸至尋找一個變量間不同選擇之間的關系
5、,或?qū)ふ也煌兞块g的關系。關聯(lián)規(guī)則中的基本概念主要包括:定義1.1:k-項集一個商品或者一個屬性稱為一個項目。多個項目的集合稱為項集。設i為數(shù)據(jù)庫D中全體項目的集合,集合x={il,i2,?,ik}(x∈i且IXI=k),稱為k-項集。定義1.2:事務一條事務,或者說一條記錄,是形如{tid,X)的二元組,其中tid稱為事務標識符,它唯一標識該條記錄,X為項目集。要挖掘的數(shù)據(jù)集或者數(shù)據(jù)庫D是N條事務的集合,一條事務也稱為一條記錄,N為數(shù)據(jù)集D的記錄總數(shù)。若事務t包含項目集X中的所有項目,則稱事務t支持或包含項目集X。定義1.3:支持度計數(shù)和支持度數(shù)據(jù)庫TDB中包含(支持)項集X的事務的數(shù)
6、目稱為項集X的支持度計數(shù),記為count(X),support(X)=count(X)/N稱為項集X的支持度,其中N為數(shù)據(jù)庫中記錄總數(shù)。定義1.3:支持度計數(shù)和支持度數(shù)據(jù)庫TDB中包含(支持)項集X的事務的數(shù)目稱為項集X的支持度計數(shù),記為count(X),support(X)=count(X)/N稱為項集X的支持度,其中N為數(shù)據(jù)庫中記錄總數(shù)。定義1.4:頻繁項目集.支持度不小于用戶給定的最小支持度閾值(minsup)的項集稱為頻繁項目集,或者大項目集。所有的頻繁1-項集記為Ll定義1.5:關聯(lián)規(guī)則關聯(lián)規(guī)則是形如X=>Y的蘊涵式,X稱為關聯(lián)規(guī)則的前件或前提,Y稱為關聯(lián)規(guī)則的后件或結(jié)論。項集
7、XUY的支持度稱為關聯(lián)規(guī)則的支持度。定義1.6:置信度關聯(lián)規(guī)則X=>Y的置信度。確定Y在包含X的事務中出現(xiàn)的頻繁程度。confidence(X=>Y)=support(X∪Y)support(X)×100%支持度和置信度是描述關聯(lián)規(guī)則的兩個重要概念,前者用于衡量關聯(lián)規(guī)則在整個數(shù)據(jù)集中的統(tǒng)計重要性,后者用于衡量關聯(lián)規(guī)則的可信程度。一般來說,只有支持度和置信度均較高的關聯(lián)規(guī)則才可能是用戶感興趣、有用的關聯(lián)規(guī)則。Agrawal等人建立了用