1、關(guān)聯(lián)規(guī)則基礎(chǔ)上數(shù)據(jù)挖掘最新算法 課程設(shè)計(jì)報(bào)告 1 名 稱(chēng)： 數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘 題 目： 院 系： 經(jīng)濟(jì)管理系 班 級(jí)： 學(xué) 號(hào)：學(xué)生姓名： 韓智強(qiáng) 指導(dǎo)教師： 溫磊 成 績(jī)： 日期：2015年5月 目錄 一、引 言 3 二、基于復(fù)雜數(shù)據(jù)組織形式的關(guān)聯(lián)規(guī)則算法3 (一)并行數(shù)據(jù)庫(kù) 3 (二)數(shù)據(jù)倉(cāng)庫(kù) 3 (三)時(shí)間連續(xù)數(shù)據(jù)庫(kù) 4 (四)增量式更新數(shù)據(jù)庫(kù)4 三、新研究方法的引入 5 (一)模糊集 5 (二)概念格 5 (三)其他研究方法 5 四、前沿研究 5 (一)時(shí)間-空間數(shù)據(jù)庫(kù) 5 (二)Web挖掘 6 (三)多媒體數(shù)據(jù)庫(kù)6 (四)可視化挖掘 6 五、總結(jié)與展望 7 2 數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則的

2、發(fā)展趨勢(shì) 一、引 言 目前,越來(lái)越多的行業(yè)都存在巨量數(shù)據(jù)處理的問(wèn)題,結(jié)構(gòu)簡(jiǎn)明的關(guān)聯(lián)規(guī)則憑借簡(jiǎn)單易懂的規(guī)則表達(dá)形式較其他數(shù)據(jù)挖掘方法更容易被接受,其廣泛的應(yīng)用前景也被學(xué)術(shù)界所認(rèn)同。理論體系的逐漸完善和實(shí)際應(yīng)用的巨大成功使關(guān)聯(lián)規(guī)則一度成為數(shù)據(jù)挖掘的重要研究方向。但隨著現(xiàn)代數(shù)據(jù)庫(kù)技術(shù)的發(fā)展和應(yīng)用領(lǐng)域的拓寬,數(shù)據(jù)存儲(chǔ)形式甚至數(shù)據(jù)格式都發(fā)生了巨大變化,關(guān)聯(lián)規(guī)則研究也面臨著前所未有的挑戰(zhàn)。 為了明確關(guān)聯(lián)規(guī)則研究的現(xiàn)實(shí)意義和未來(lái)發(fā)展趨勢(shì),筆者考察了近幾年國(guó)內(nèi)外相關(guān)的研究成果和最新動(dòng)態(tài)。在對(duì)復(fù)雜數(shù)據(jù)組織形式的關(guān)聯(lián)規(guī)則挖掘詳細(xì)描述的基礎(chǔ)上,探討了其他學(xué)科領(lǐng)域?qū)﹃P(guān)聯(lián)規(guī)則的理解及相應(yīng)的研究方法,最后提出了關(guān)聯(lián)規(guī)則的

3、前沿研究問(wèn)題和未來(lái)的發(fā)展趨勢(shì)。 二、基于復(fù)雜數(shù)據(jù)組織形式的關(guān)聯(lián)規(guī)則算法 隨著并行和分布式數(shù)據(jù)庫(kù)系統(tǒng)、數(shù)據(jù)倉(cāng)庫(kù)、聯(lián)機(jī)分析處理(OLAP)和數(shù)據(jù)立方體等數(shù)據(jù)組織、存儲(chǔ)、分析和處理技術(shù)的出現(xiàn)和成熟,使關(guān)聯(lián)規(guī)則挖掘在并行數(shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)、時(shí)間連續(xù)數(shù)據(jù)庫(kù)和增量更新數(shù)據(jù)庫(kù)等復(fù)雜數(shù)據(jù)組織形式中的應(yīng)用成為可能,相應(yīng)地產(chǎn)生了一系列新的關(guān)聯(lián)規(guī)則算法。 (一)并行數(shù)據(jù)庫(kù) 對(duì)于并行數(shù)據(jù)庫(kù)而言,一般具有多個(gè)可以同時(shí)獨(dú)立運(yùn)行的處理器(結(jié)點(diǎn)),并通過(guò)網(wǎng)絡(luò)交換信息。由于并行體系結(jié)構(gòu)計(jì)算能力強(qiáng),數(shù)據(jù)處理量大,因而基于并行體系結(jié)構(gòu)的關(guān)聯(lián)規(guī)則算法明顯優(yōu)于基于單處理器的順序算法。并行數(shù)據(jù)庫(kù)可以分為無(wú)共享體系(share-nothin

4、g)結(jié)構(gòu)和內(nèi)存共享體系(shared-memory)結(jié)構(gòu)。關(guān)聯(lián)規(guī)則并行算法的設(shè)計(jì)主要從數(shù) 據(jù)合理分配、減少I(mǎi)/O操作、負(fù)載平衡、減少結(jié)點(diǎn)間的通信和同步以及減少計(jì)算冗余等方面權(quán)衡考慮。 無(wú)共享體系結(jié)構(gòu)中,數(shù)據(jù)庫(kù)分布在各個(gè)結(jié)點(diǎn)(即分布式數(shù)據(jù)庫(kù)),各結(jié)點(diǎn)間有網(wǎng)絡(luò)連接,每個(gè)結(jié)點(diǎn)可獨(dú)立處理子數(shù)據(jù)庫(kù)。主要算法都是將原有的順序算法并行化,如Agrawal,R.等(1996)的Countdistribu2tion,DataDistribution和CandidateDistribution1;Park,J.S.等(1995)的PDM2;Cheung,D.W.等(1996)的FDM3和Cheung,D.W.等(

5、1996)的DMA4,以及Za2ki,M.J.等(1997)的ParEclat5等算法。在內(nèi)存共享體系結(jié)構(gòu)中多個(gè)結(jié)點(diǎn)共用內(nèi)存和數(shù)據(jù)庫(kù),各結(jié)點(diǎn)通過(guò)共享變量通信。這類(lèi)算法采用了異步候選集生成,比寬度優(yōu)先算法的掃描次數(shù)少。但各結(jié)點(diǎn)可獨(dú)立訪(fǎng)問(wèn)數(shù)據(jù)庫(kù),因此需要解決I/O通道共享和并發(fā)訪(fǎng)問(wèn)數(shù)據(jù)庫(kù)時(shí)I/O占用問(wèn)題。由于這類(lèi)并行數(shù)據(jù)庫(kù)較少使用,相關(guān)的研究也不多,有代表性的算法是APM6。 (二)數(shù)據(jù)倉(cāng)庫(kù) 目前,數(shù)據(jù)倉(cāng)庫(kù)已經(jīng)成為標(biāo)準(zhǔn)的數(shù)據(jù)存儲(chǔ)和組織形式。在數(shù)據(jù)倉(cāng)庫(kù)中各種數(shù)據(jù)3 以多維形式組織,即數(shù)據(jù)立方體。而采用OLAP技術(shù)驅(qū)動(dòng)的數(shù)據(jù)倉(cāng)庫(kù)具有數(shù)據(jù)質(zhì)量高、相關(guān)數(shù)據(jù)環(huán)境好和實(shí)時(shí)分析等優(yōu)點(diǎn)。因此相應(yīng)的算法就直接針對(duì)數(shù)

6、據(jù)立方體設(shè)計(jì),并由OLAP技術(shù)實(shí)現(xiàn)。這類(lèi)算法多是已有的多維關(guān)聯(lián)規(guī)則算法的推廣和優(yōu)化。 較為簡(jiǎn)單的算法是建立在頻繁謂詞集上的,把謂詞作為項(xiàng),謂詞的出現(xiàn)次數(shù)作為支持度,不考慮謂詞出現(xiàn)的強(qiáng)度。如Apriori-Cube算法7(高學(xué)東等(2003)直接在數(shù)據(jù)立方體上搜索頻繁謂詞集。而考慮概念層次的算法較復(fù)雜,如Adaptive-FP算法8和FP-Growth9類(lèi)似,但是先對(duì)項(xiàng)加入概念層次編碼后再建立FP-tree,采用同一支持度挖掘同一概念層次的維間和維內(nèi)頻繁集,采用可變支持度挖掘不同維或者同維不同概念層次的頻繁集,賀瓊等(2004)在Adaptive-FP的基礎(chǔ)上進(jìn)一步利用概念層次信息優(yōu)化了FP-t

7、ree的建立過(guò)程10。 (三)時(shí)間連續(xù)數(shù)據(jù)庫(kù) 時(shí)間連續(xù)數(shù)據(jù)庫(kù)包含了隨時(shí)間延續(xù)而變化的事務(wù)數(shù)據(jù)或事件記錄。這類(lèi)數(shù)據(jù)的特點(diǎn)是具有明顯的時(shí)間順序,且呈現(xiàn)一定的規(guī)律性或者周期性。這方面的研究主要集中在連續(xù)時(shí)間的事務(wù)數(shù)據(jù)集和多個(gè)時(shí)間序列中的關(guān)聯(lián)規(guī)則挖掘。連續(xù)時(shí)間的事務(wù)數(shù)據(jù)集中的關(guān)聯(lián)規(guī)則挖掘類(lèi)似具有時(shí)間維度的多維關(guān)聯(lián)規(guī)則挖掘,但直接將時(shí)間效應(yīng)引入算法,增加算法的適應(yīng)性和可擴(kuò)展性。施平安等(2001)認(rèn)為事務(wù)的出現(xiàn)頻率和時(shí)間段有關(guān)。因此先定義頻繁集的高頻適用期和低頻適用期,然后分別挖掘高頻適用期和低頻適用期中的頻繁集;喻偉等(2002)建立了延遲關(guān)聯(lián)規(guī)則模型:X?TY,當(dāng)T>0時(shí),稱(chēng)為延遲規(guī)則;當(dāng)T=

8、0時(shí)為一般規(guī)則,并提出了DirectDelay算法挖掘延遲規(guī)則。在時(shí)間序列中,每個(gè)序列都表示一個(gè)數(shù)值屬性的取值曲線(xiàn)或者事件的持續(xù)時(shí)間和間隔。而數(shù)值屬性的時(shí)間序列可映射為多個(gè)取值區(qū)間的事件序列，因此時(shí)間序列都可轉(zhuǎn)化為事件序列。事件序列的關(guān)聯(lián)規(guī)則更強(qiáng)調(diào)規(guī)律性和周期性,常被稱(chēng)為頻繁序列模式(frequentsequentialpattern)或者頻繁片斷模式(frequentepisodepattern)。Villafane,R.等(2000)分析多個(gè)時(shí)序的事件在時(shí)間段上的包含關(guān)系13,由此建立可傳遞的閉合包含圖(transitivelyclosedcontain2mentgraph),再通過(guò)點(diǎn)和邊

9、的計(jì)數(shù)得到頻繁包含關(guān)系的支持度和可信度。Harms,S.K.等(2004)提出了挖掘片斷關(guān)聯(lián)規(guī)則的MOWCATL算法14,可在關(guān)聯(lián)規(guī)則的前件和后件中分別引入用戶(hù)指定的內(nèi)包約束(inclusionconstraint),還可指定固定的或者最大的時(shí)間滯后值。 (四)增量式更新數(shù)據(jù)庫(kù) 增量式更新數(shù)據(jù)庫(kù)中的關(guān)聯(lián)規(guī)則挖掘面臨的問(wèn)題主要有兩個(gè):第一,給定的支持度和置信度閾值,新的事務(wù)數(shù)據(jù)值d加入原數(shù)據(jù)集D時(shí),如何得到dD的關(guān)聯(lián)規(guī)則;第二,給定事務(wù)數(shù)據(jù)庫(kù)D,支持度和置信度閾值發(fā)生變化時(shí),如何得到新的關(guān)聯(lián)規(guī)則。 Cheung,D.W.等(1996)首先考慮了第一個(gè)問(wèn)題,并提出了增量式更新數(shù)據(jù)庫(kù)中關(guān)聯(lián)規(guī)則挖掘的

10、FUP算法15。FUP基于Apriori16并假設(shè)已有頻繁集和支持度已經(jīng)保存。該算法沒(méi)有充分利用已有的頻繁集信息,需要對(duì)dD進(jìn)行n次掃描(n為D中最大頻繁項(xiàng)集的大小),掃描次數(shù)過(guò)多;而李寶東等(2002)的EFUP算法17,只要先逐層掃描d,再掃描D一次,就能得到dD的頻繁集。對(duì)于第二個(gè)問(wèn)題,有兩種情況:第一,支持度閾值變大導(dǎo)致頻繁集減少;第二,支持度閾值變小導(dǎo)致頻繁4 集增加。第一種情況只需掃描一次數(shù)據(jù)庫(kù)并保留滿(mǎn)足新的支持度的頻繁集即可。第二種情況較為復(fù)雜,需要重新設(shè)計(jì)算法。代表算法有IUA18。IUA算法使用了一種新的候選集生成方法,充分利用了已有的頻繁集信息。但I(xiàn)UA中的iua-gen(

11、)函數(shù)的連接操作所得候選集數(shù)目過(guò)大,而修剪操作還會(huì)誤刪頻繁集。陳麗等(2001)的EIUA算法19和石冰等(2000)的LAA算法20分別改進(jìn)了iua-gen()函數(shù),避免誤刪頻繁集的同時(shí)又提高了算法的效率。 三、新研究方法的引入 (一)模糊集 模糊集由Zadeh,A.于1965年創(chuàng)立。其主要?jiǎng)?chuàng)新是把經(jīng)典集合里特征函數(shù)的取值函數(shù)由二值域0,1擴(kuò)展到閉區(qū)間0,1,并給出了模糊集的定義:一個(gè)定義在論域U上的模糊集合F由隸屬函數(shù)F:U?0,1表征,其中F表示在模糊集合F上的隸屬度。模糊集主要用于提高關(guān)聯(lián)規(guī)則的有趣度和可理解性。Hong,T.等(1999)提出一種典型的定量關(guān)聯(lián)規(guī)則挖掘算法21。先使用

12、隸屬函數(shù)將每個(gè)定量數(shù)據(jù)轉(zhuǎn)化為帶有語(yǔ)言值的標(biāo)量基數(shù),再在該模糊集中挖掘關(guān)聯(lián)規(guī)則。Wang,S.等(2002)考慮了時(shí)間連續(xù)的事務(wù)數(shù)據(jù)庫(kù)中挖掘模糊相似的序列模式的問(wèn)題22。Hong,T.等(2003)提出了模糊多層關(guān)聯(lián)規(guī)則的挖掘方法23。 (二)概念格 在形式概念分析中24,概念的外延表示這個(gè)概念的所有對(duì)象的集合,而內(nèi)涵表示所有對(duì)象共有的屬性集合。以此將概念的哲學(xué)理解形式化。概念格(conceptlattice)是形式概念分析中的核心數(shù)據(jù)結(jié)構(gòu),概念格的結(jié)點(diǎn)關(guān)系體現(xiàn)了概念之間的泛化和實(shí)例化關(guān)系,因此非常適合用來(lái)挖掘規(guī)則型知識(shí)。 Missaoui,R.等(1994)首次從概念格中提取近似規(guī)則25,實(shí)現(xiàn)

13、了基于概念格的關(guān)聯(lián)規(guī)則挖掘;Pasquier,N.等(1999)利用了概念格中概念連接的閉合性,創(chuàng)新地定義了閉合項(xiàng)集格26,并通過(guò)A-close算法挖掘頻繁閉合項(xiàng)集(frequentcloseditemset);Pei,J.等(2000)的CLOSET算法以FP-tree為基礎(chǔ),使用深度優(yōu)先策略搜索頻繁閉合集27;Wang,J.等(2003)在FP-tree結(jié)構(gòu)、修剪策略和驗(yàn)證閉合性等方面對(duì)CLOSET做出改進(jìn)得到CLOSET+算法28;而Zaki,M.J.等(2002)建立的CHARM算法采用了tid2set和diffsets結(jié)構(gòu)表示事務(wù)標(biāo)簽集29,并同時(shí)搜索項(xiàng)集和事務(wù)標(biāo)簽集,可高效修剪并得

14、到頻繁閉合集。 (三)其他的研究方法 粗糙集由波蘭數(shù)學(xué)家Pawlak,Z.于1982年創(chuàng)新。粗糙集強(qiáng)調(diào)數(shù)據(jù)的不可辨(indiscernibility)與模棱兩可(ambiguity),研究不同類(lèi)中的對(duì)象組成的集合間的關(guān)系。因此粗糙集在關(guān)聯(lián)規(guī)則中的應(yīng)用主要是規(guī)則挖掘前的數(shù)據(jù)約簡(jiǎn)和降維等預(yù)處理;朱建平等(2004)給出了事務(wù)數(shù)據(jù)庫(kù)的粗糙集表示30,并詳細(xì)討論了事務(wù)性數(shù)據(jù)庫(kù)的粗糙集壓縮的信息損失問(wèn)題,大大減少了后續(xù)的關(guān)聯(lián)規(guī)則挖掘的搜索空間;劉發(fā)升等(1999)利用粗糙集泛化概念層次樹(shù),以約簡(jiǎn)所得的關(guān)聯(lián)規(guī)則 31;Guan,J.W.等(2003)使用粗糙集方法挖掘文本數(shù)據(jù)庫(kù)系統(tǒng)的關(guān)聯(lián)規(guī)則32。 5 基

15、于生物遺傳算法的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)方法,利用遺傳算法的自適應(yīng)尋優(yōu)及智能搜索技術(shù)獲取與客觀事實(shí)相容的關(guān)聯(lián)規(guī)則。生物遺傳算法需要首先確定染色體編碼方案,然后確定適應(yīng)度函數(shù),最后確定遺傳操作。通過(guò)遺傳算子(如選擇,交叉(重組)和變異等)來(lái)產(chǎn)生一群新的更適應(yīng)環(huán)境的染色體,形成新的種群。許國(guó)艷等(2002)對(duì)圖書(shū)館借閱數(shù)據(jù)采用生物遺傳算法挖掘關(guān)聯(lián)規(guī)則33。 四、前沿研究 作為最成功的一種數(shù)據(jù)挖掘工具,關(guān)聯(lián)規(guī)則挖掘得到了全面而深入的研究。目前,前沿研究主要有以下幾個(gè)方面。 (一) 時(shí)間空間數(shù)據(jù)庫(kù) 時(shí)間空間關(guān)聯(lián)規(guī)則(spatio-temporalassocia2tionrule),就是在關(guān)聯(lián)規(guī)則的謂詞集中加入空間

16、謂詞和時(shí)間謂詞。這方面的研究主要集中在地理信息系統(tǒng)和地球科學(xué)等自然科學(xué)領(lǐng)域,由于時(shí)間空間數(shù)據(jù)庫(kù)的規(guī)模異常龐大,主要使用空間換時(shí)間的算法策略,在較短的時(shí)間內(nèi)盡快挖掘出有效規(guī)則。 Tan,P.等(2001)采用時(shí)間序列的關(guān)聯(lián)規(guī)則算法挖掘地球生態(tài)變化模式34;Su,F.等(2004)采用空間分布式數(shù)據(jù)的關(guān)聯(lián)規(guī)則算法挖掘生態(tài)關(guān)聯(lián)規(guī)則,并對(duì)中國(guó)黃海區(qū)域的魚(yú)群分布進(jìn)行了實(shí)例分析35。 (二)Web挖掘 通常互聯(lián)網(wǎng)站無(wú)法獲取用戶(hù)訪(fǎng)問(wèn)網(wǎng)頁(yè)的完整行為,只能得到大量訪(fǎng)問(wèn)日志文件和網(wǎng)頁(yè)鏈接的點(diǎn)擊記錄。因此,Web挖掘理所當(dāng)然地成為數(shù)據(jù)挖掘的一個(gè)主要研究領(lǐng)域。現(xiàn)階段的研究集中在Web內(nèi)容挖掘和Web使用挖掘。關(guān)聯(lián)規(guī)則

17、作為Web挖掘的重要工具,既可通過(guò)分析Web日志文件和Web鏈接數(shù)據(jù)挖掘出用戶(hù)的訪(fǎng)問(wèn)規(guī)律,也可作為Web內(nèi)容聚類(lèi)和檢索的預(yù)處理步驟。有關(guān)的研究有李穎基等(2003)提出的基于Web拓樸概率模型和有趣關(guān)聯(lián)規(guī)則的IAR算法36,可對(duì)Web日志進(jìn)行關(guān)聯(lián)規(guī)則挖掘;宋擒豹等(2003)提出一種Web文檔聚類(lèi)算法37,先采用向量空間模型表示主題,根據(jù)主題表示文檔;再把文檔作為事務(wù),主題作為項(xiàng),采用關(guān)聯(lián)規(guī)則算法得到主題頻繁集,以供后續(xù)的聚類(lèi)操作;Xing,D.等(2004)將用戶(hù)訪(fǎng)問(wèn)頁(yè)面的停留時(shí)間和點(diǎn)擊鏈接的順序作為偏好程度,并以此提出UAM和PNT算法挖掘頻繁瀏覽模式38。 (三)多媒體數(shù)據(jù)庫(kù) 現(xiàn)在多媒體

18、數(shù)據(jù)庫(kù)的容量和規(guī)模快速增長(zhǎng),迫切地需要一個(gè)有效的查詢(xún)技術(shù)以提高多媒體數(shù)據(jù)庫(kù)的使用效率。可是,現(xiàn)代計(jì)算機(jī)圖形技術(shù)提供的基于圖形描述符的圖形檢索與用戶(hù)輸入的查詢(xún)的概念描述仍然存在差距。這是因?yàn)?第一,低層次的圖形特征關(guān)系無(wú)法準(zhǔn)確反映用戶(hù)查詢(xún)的概念描述;第二,用戶(hù)主觀性也會(huì)導(dǎo)致概念描述的差異。此外,多媒體數(shù)據(jù)庫(kù)本身也在不斷完善之中,相應(yīng)的數(shù)據(jù)庫(kù)操作仍在研究之中,因此關(guān)聯(lián)規(guī)則挖掘還局限在靜態(tài)圖像的范圍內(nèi)。 Zaane,O.R.等(1998)在基于OLAP技術(shù)的數(shù)據(jù)挖掘系統(tǒng)DBMiner和基于數(shù)字圖書(shū)館的圖形檢索系統(tǒng)C-BIRD基礎(chǔ)上,建立了可挖掘高層次信息的多媒體數(shù)挖掘系統(tǒng)MultiMediaMine

19、r39,該系統(tǒng)采用數(shù)據(jù)立方體的數(shù)據(jù)組織形式并實(shí)現(xiàn)了6 關(guān)聯(lián)規(guī)則挖掘在內(nèi)的多種數(shù)據(jù)挖掘方法;Snchez,D.等(2003)提出圖像語(yǔ)言值學(xué)習(xí)模型40,把圖像的語(yǔ)言值作為圖像的概念描述進(jìn)行檢索,使用圖像的視覺(jué)屬性來(lái)表征圖像。通過(guò)模糊關(guān)聯(lián)規(guī)則來(lái)描述特征與概念之間的關(guān)系,在圖像語(yǔ)言值的層次上進(jìn)行圖像檢索,用模糊關(guān)聯(lián)規(guī)則的不確定性表示用戶(hù)主觀性。 (四)可視化挖掘 人類(lèi)視覺(jué)系統(tǒng)是一個(gè)非常寬域的信息通道。可視化方法就是利用人類(lèi)這一能力來(lái)發(fā)現(xiàn)并解釋基于圖形表示的數(shù)據(jù)模式和結(jié)構(gòu)。因此關(guān)聯(lián)規(guī)則發(fā)現(xiàn)過(guò)程的可視化就成為最具潛力的研究方向之一。 Kopanakis,I.等(2003)提出了并行的柱狀圖系統(tǒng)41,利用柱狀圖各種特征(長(zhǎng)度,顏色和背景等)實(shí)現(xiàn)數(shù)據(jù)降維和關(guān)聯(lián)規(guī)則發(fā)現(xiàn);Kimani,S.等(2004