數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)

數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)

相關(guān)規(guī)則是r.agrawal等人首次提出的cdd的重要研究?jī)?nèi)容，近年來(lái)引起了數(shù)據(jù)庫(kù)界的關(guān)注。關(guān)聯(lián)規(guī)則是尋找在同一個(gè)事件中出現(xiàn)的不同項(xiàng)的相關(guān)性,即找出事件中頻繁發(fā)生的項(xiàng)或?qū)傩缘乃凶蛹?以及它們之間應(yīng)用相互關(guān)聯(lián)性。關(guān)聯(lián)規(guī)則最早用于發(fā)現(xiàn)顧客交易數(shù)據(jù)庫(kù)中不同商品間的聯(lián)系,后來(lái)諸多的研究人員對(duì)關(guān)聯(lián)規(guī)則的挖掘問(wèn)題進(jìn)行了大量的拓展和研究。他們的工作包括對(duì)原有算法的優(yōu)化,如引入并行的思想,以提高算法的效率,對(duì)關(guān)聯(lián)規(guī)則的應(yīng)用進(jìn)行擴(kuò)展。關(guān)聯(lián)規(guī)則挖掘具有計(jì)算量大,I/O負(fù)載集中的特點(diǎn)。而且許多關(guān)聯(lián)規(guī)則的實(shí)際應(yīng)用涉及到海量數(shù)據(jù)。在這種情況下,即使對(duì)算法進(jìn)行了優(yōu)化,在單處理機(jī)上使用串行算法進(jìn)行挖掘所需要的時(shí)間可能也是無(wú)法接受的。其主要原因在于單處理器本身受到內(nèi)存和I/O帶寬的限制。因此,必須依靠高性能并行計(jì)算來(lái)有效地完成挖掘任務(wù)。1關(guān)聯(lián)規(guī)則的挖掘關(guān)聯(lián)規(guī)則的形式化描述如下:一個(gè)關(guān)聯(lián)規(guī)則是形如X?Y的蘊(yùn)涵式,這里X?I,Y?I,并且X∩Y=ф。規(guī)則X?Y在交易數(shù)據(jù)庫(kù)D中的支持度(support)是交易數(shù)據(jù)庫(kù)中X和Y的交易數(shù)與所有交易數(shù)之比,記為support(X?Y),即規(guī)則X?Y在交易數(shù)據(jù)庫(kù)D中的可信度(confidence)指包含X和Y的交易數(shù)與包含X的交易數(shù)之比,記為給定一個(gè)交易集D,關(guān)聯(lián)規(guī)則的挖掘問(wèn)題就是產(chǎn)生支持度和可信度分別大于用戶給定的最小支持度(minsupp)和最小可信度(minconf)的關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則的發(fā)掘分為兩個(gè)步驟:(1)找出所有支持度大于最小支持度的頻集;(2)從頻集中產(chǎn)生期望的規(guī)則。2提取網(wǎng)絡(luò)關(guān)聯(lián)規(guī)則的算法目前所有并行關(guān)聯(lián)規(guī)則算法都是在相應(yīng)的串行算法的基礎(chǔ)上提出的。本文首先對(duì)這些串行算法進(jìn)行介紹和分析。2.1基于數(shù)據(jù)庫(kù)的限制競(jìng)爭(zhēng)函數(shù)在各種關(guān)聯(lián)規(guī)則挖掘算法中,最經(jīng)典、最廣泛使用的就是Agrawal等設(shè)計(jì)的Apriori算法,其核心思想是基于頻集理論的遞推方法。首先產(chǎn)生頻繁1-項(xiàng)集,然后是頻繁2-項(xiàng)集,直到有某個(gè)r值使頻繁r-項(xiàng)集為空,算法停止。這里在第k次循環(huán)中,過(guò)程先通過(guò)對(duì)兩個(gè)只有一個(gè)項(xiàng)不同的屬于k-1的頻集做(k-2)-連接產(chǎn)生候選k-項(xiàng)集的集合。然后驗(yàn)證候選k-項(xiàng)集中的每個(gè)元素來(lái)決定是否將其加入k-頻集,這里的驗(yàn)證過(guò)程是算法性能的一個(gè)瓶頸。這個(gè)方法要求多次掃描數(shù)據(jù)庫(kù),這就需要很大的I/O負(fù)載。Park等提出了一個(gè)高效地產(chǎn)生頻繁集的基于雜湊(hash)的算法:DynamicHashingandPruning(DHP)算法。通過(guò)實(shí)驗(yàn)可以發(fā)現(xiàn)尋找頻集的主要計(jì)算是在生成頻繁2-項(xiàng)集上。DHP利用一個(gè)雜湊表在計(jì)算頻繁1-項(xiàng)集時(shí)先大概計(jì)算出2-項(xiàng)集的支持度,從而減少了候選2-項(xiàng)集的數(shù)量。DHP還采用了數(shù)據(jù)庫(kù)修剪技術(shù),通過(guò)修剪掉那些不包含頻集的事物集以減小下一次循環(huán)中數(shù)據(jù)庫(kù)的大小。然而,這種修剪技術(shù)的優(yōu)化并不顯著。其主要原因在于只能通過(guò)過(guò)濾對(duì)數(shù)據(jù)庫(kù)執(zhí)行邏輯上的修剪,任何物理上的修剪意味著在每次循環(huán)中要改寫(xiě)數(shù)據(jù)庫(kù),這是不切實(shí)際的。Savasere等提出了一種基于劃分(partition)的算法。這種算法把數(shù)據(jù)庫(kù)從邏輯上分成幾個(gè)互不相交的塊,每次單獨(dú)考慮一個(gè)分塊并對(duì)它生成所有的頻集。然后把產(chǎn)生的頻集合并,用以生成所有可能的頻集,最后計(jì)算這些頻集的支持度。Partition算法很大程度上減小了I/O負(fù)載。然而在處理高項(xiàng)集時(shí)存在一些問(wèn)題,而且它還有頻集的錯(cuò)誤處理的缺陷。Brin等提出的DynamicItemsetCounting(DIC),也是基于劃分的一種算法。它通過(guò)在一個(gè)循環(huán)中生成不同長(zhǎng)度的候選集以減少數(shù)據(jù)庫(kù)掃描的次數(shù),有效地改進(jìn)了算法在低層的效率。然而該算法在同構(gòu)數(shù)據(jù)的情況下具有較好的性能。例如,多數(shù)分塊有相似的頻集分布。否則,DIC可能需要比Apriori更多的對(duì)數(shù)據(jù)庫(kù)的掃描。Muellel在他的碩士論文中提出了4種基于Apriori和Partition的算法:SEAR算法,基于TID劃分的SPTID算法,基于劃分的SPEAR算法和SPINC算法。SEAR算法與Apriori算法相似,只是該算法用一個(gè)前綴數(shù)(prefixtree)取代雜湊數(shù)(hashtree)來(lái)存儲(chǔ)候選項(xiàng)集,而且引入了一個(gè)循環(huán)綁定(passbunding)的優(yōu)化策略,即只要內(nèi)存允許在一個(gè)循環(huán)中可生成不同長(zhǎng)度的候選集,這樣在對(duì)數(shù)據(jù)庫(kù)的一次掃描中就可以計(jì)算所有當(dāng)前候選集的支持度。實(shí)驗(yàn)表明,SEAR算法優(yōu)于其他算法,具有較好的性能。Zaki等在論文中提出了基于數(shù)據(jù)的垂直分布的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法。其中最簡(jiǎn)單的是Eclat算法,性能最好的是MaxClique算法。當(dāng)前多數(shù)關(guān)聯(lián)規(guī)則挖掘算法采用的是水平數(shù)據(jù)分布方式,即數(shù)據(jù)由一系列事物構(gòu)成。使用這種格式,計(jì)算負(fù)載主要集中在支持計(jì)數(shù)上。而且,數(shù)據(jù)的水平分布迫使每次循環(huán)均需遍歷整個(gè)數(shù)據(jù)庫(kù)或每個(gè)局部劃分。數(shù)據(jù)的垂直分布是指數(shù)據(jù)集由一系列項(xiàng)目構(gòu)成。數(shù)據(jù)垂直分布的優(yōu)點(diǎn)在于可以通過(guò)簡(jiǎn)單地鏈接任意兩個(gè)(k-1)-子集生成候選k-項(xiàng)目集,不需要復(fù)雜的hash數(shù)據(jù)結(jié)構(gòu),無(wú)須對(duì)數(shù)據(jù)庫(kù)進(jìn)行遍歷。以上介紹的都是基于Apriori的關(guān)聯(lián)規(guī)則挖掘算法。即使已經(jīng)進(jìn)行了一定的優(yōu)化,但是Apriori方法仍存在一些固有的無(wú)法克服的缺陷:(1)可能產(chǎn)生大量的候選集;(2)對(duì)數(shù)據(jù)庫(kù)進(jìn)行多次掃描。2.2頻繁模式樹(shù)的fp-g水質(zhì)數(shù)據(jù)庫(kù)的構(gòu)建Han等提出了一種富有創(chuàng)新性的方法,即FP-growth方法。這種算法采用了分而治之的策略,經(jīng)過(guò)第1次掃描之后,把數(shù)據(jù)庫(kù)中的頻集壓縮到一棵頻繁模式樹(shù)(FP-tree)中,同時(shí)依然保留其中的關(guān)聯(lián)信息。隨后再將FP-tree劃分為一些條件庫(kù),每個(gè)庫(kù)和一個(gè)長(zhǎng)度為1的頻集相關(guān)。然后再對(duì)這些條件庫(kù)分別進(jìn)行挖掘。FP-growth只需對(duì)數(shù)據(jù)庫(kù)進(jìn)行二次掃描,而且避免了產(chǎn)生大量候選集的問(wèn)題。實(shí)驗(yàn)表明,FP-growth對(duì)不同長(zhǎng)度的規(guī)則具有很好的適應(yīng)性,同時(shí)在效率上較之Apriori算法有很大的提高。3多處理器關(guān)聯(lián)規(guī)則的研究盡管關(guān)聯(lián)規(guī)則的描述很簡(jiǎn)單,但是它卻是一個(gè)計(jì)算和I/O集中的任務(wù)。假設(shè)給定m個(gè)項(xiàng)目集,那么存在2m個(gè)子集可能是頻集。處理如此指數(shù)級(jí)的數(shù)據(jù)需要大量的磁盤(pán)I/O。實(shí)驗(yàn)證明,在限定交易長(zhǎng)度的情況下,關(guān)聯(lián)規(guī)則的挖掘和數(shù)據(jù)庫(kù)的大小呈線性遞增的關(guān)系。而且,隨著項(xiàng)目集的數(shù)量和維度的增加,以及交易數(shù)據(jù)庫(kù)大小的增加,串行算法顯然不具有良好的性能。因此必須依靠高性能并行計(jì)算來(lái)有效地完成挖掘任務(wù)。然而利用多處理器系統(tǒng)進(jìn)行關(guān)聯(lián)規(guī)則發(fā)現(xiàn),要想獲得好的性能并非易事。其中涉及到的問(wèn)題包括:減小同步和通信,負(fù)載平衡,數(shù)據(jù)放置和減小磁盤(pán)I/O。下面從并行度、負(fù)載平衡、以及實(shí)現(xiàn)平臺(tái)等方面對(duì)當(dāng)前主要的并行關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法進(jìn)行介紹和分析。3.1cd和pdm算法多處理器體系結(jié)構(gòu)有3種形式:共享內(nèi)存系統(tǒng)(sharememorysystem),共享磁盤(pán)系統(tǒng)(share-disksystem)和不共享系統(tǒng)(share-nothingsystem)。在共享內(nèi)存系統(tǒng)中,所有處理器共享一個(gè)通用的,非常大的內(nèi)存。這樣任何一個(gè)處理器都可以訪問(wèn)所有的數(shù)據(jù),具有動(dòng)態(tài)負(fù)載平衡。在這種系統(tǒng)中,想要獲得好的并行性能,關(guān)鍵在于處理好數(shù)據(jù)的同步問(wèn)題。在共享磁盤(pán)和不共享系統(tǒng)中,數(shù)據(jù)分布在各個(gè)處理器節(jié)點(diǎn)上,它們之間的通信和I/O是通過(guò)消息傳遞來(lái)實(shí)現(xiàn)的。因此獲得好的并行性能的關(guān)鍵就在于合理分布數(shù)據(jù),以取得好的負(fù)載平衡,減小通信代價(jià)。Agrawal等提出了3種基于Apriori的并行關(guān)聯(lián)規(guī)則挖掘算法:CountDistribution(CD),DateDistribution(DD)和CandidateDistribution算法。它們是在不共享的IBMPOWER并行SP2系統(tǒng)上實(shí)現(xiàn)的。Apriori算法的主要計(jì)算代價(jià)是候選集的生成及其支持度的計(jì)算。因此高度并行地完成此過(guò)程必然可以大大地降低算法執(zhí)行的時(shí)間,提高算法的性能。一種并行的方法是復(fù)制候選集(CD算法)(見(jiàn)圖1),另一種方法是劃分候選集(DD算法)(見(jiàn)圖2),再就是將兩種方法合成,即部分劃分候選集的方法(CandidateDistribution)。CD算法將生成候選集的過(guò)程復(fù)制到所有處理器上。每個(gè)處理器生成一個(gè)完整的候選雜湊樹(shù),根據(jù)本地?cái)?shù)據(jù)庫(kù)分塊獨(dú)立地計(jì)算出候選項(xiàng)的局部支持計(jì)數(shù),然后通過(guò)在所有處理器之間交換局部支持計(jì)數(shù)來(lái)得到全局支持計(jì)數(shù)。因?yàn)樵谔幚砥鏖g只需交換支持?jǐn)?shù)而不是合并不同的雜湊樹(shù),這種算法具有較小的通信負(fù)載。然而它并沒(méi)有實(shí)現(xiàn)雜湊樹(shù)構(gòu)成過(guò)程的并行化,在處理器數(shù)量增加的情況下,將成為算法執(zhí)行的瓶頸,而且它也沒(méi)有有效地利用內(nèi)存。DD算法用一種循環(huán)的方式將候選集劃分到每個(gè)處理器中,然后由每個(gè)處理器負(fù)責(zé)計(jì)算本地存儲(chǔ)的候選子項(xiàng)集的支持計(jì)數(shù)。這個(gè)過(guò)程需要每個(gè)處理器既要掃描分配給該處理器的數(shù)據(jù)庫(kù),還要掃描其他處理器上的數(shù)據(jù)庫(kù),從而導(dǎo)致了很高的通信負(fù)載,降低了該算法的性能。為了交換各自的支持計(jì)數(shù)或頻集,CD算法和DD算法都需要在每次循環(huán)結(jié)束時(shí)進(jìn)行處理器之間的同步。CandidateDistribution算法,在l循環(huán)中劃分候選集,同時(shí)選擇性地復(fù)制數(shù)據(jù)庫(kù)以便每個(gè)處理器可以獨(dú)立地生成候選集和全局支持計(jì)數(shù)。實(shí)驗(yàn)表明,較之其他兩種算法,CD算法的性能最好。PDM算法是Park等提出的并行DHP算法。該算法類似于CD算法,所有處理器含有相同的雜湊表和候選集。并行候選集生成的過(guò)程,是通過(guò)每個(gè)處理器生成一個(gè)候選子項(xiàng)集,然后交換所有處理器上的子項(xiàng)集生成全局候選集來(lái)實(shí)現(xiàn)的。每個(gè)處理器通過(guò)一個(gè)雜湊表(hashtable)生成k-項(xiàng)集的局部支持?jǐn)?shù)和k+1-項(xiàng)集的近似局部支持?jǐn)?shù),然后通過(guò)全局廣播的方式交換k-項(xiàng)集的局部支持?jǐn)?shù)而得到k-項(xiàng)集的全局支持?jǐn)?shù)。由于2-項(xiàng)集雜湊表很可能非常大,直接交換的代價(jià)將是非常高。該算法采用了一種優(yōu)化策略,即只交換那些支持?jǐn)?shù)大于最小支持?jǐn)?shù)的項(xiàng)集。PDM算法實(shí)現(xiàn)了雜湊表構(gòu)成的并行,性能優(yōu)于CD算法。Shintani等提出了3種類似文獻(xiàn)的算法:NonPartition,Simple-Partition和Hash-PartitionApriori算法,是在不共享的有64個(gè)節(jié)點(diǎn)的FujitsuAP1000DDV系統(tǒng)上實(shí)現(xiàn)的。Non-PartitionApriori算法本質(zhì)上和CD算法相同,不同之處在于它使用了一個(gè)控制處理器完成全局支持?jǐn)?shù)的累計(jì)過(guò)程。Simple-PartitionApriori算法和DD算法一樣。Hash-PartitionApriori算法類似于CandidateDistribution算法,采用雜湊函數(shù)將候選集分配給處理器,減小了處理器間發(fā)送局部數(shù)據(jù)庫(kù)分塊的通信負(fù)載。Zaki等提出的CommonCandidatePartitionDatabase(CCPD)算法,以及Cheung等提出的AsynchronousParallelMining(APM)算法是在共享內(nèi)存的系統(tǒng)上實(shí)現(xiàn)的。在CCPD算法中,所有處理器共享一個(gè)候選雜湊樹(shù),而數(shù)據(jù)庫(kù)被邏輯劃分為大小相等的分塊。該算法采用鎖機(jī)制來(lái)實(shí)現(xiàn)雜湊樹(shù)生成過(guò)程的并行。論文中指出,由于雜湊本身的特點(diǎn),雜湊樹(shù)具有很差的數(shù)據(jù)放置,加之共享雜湊樹(shù)可能會(huì)造成支持計(jì)數(shù)時(shí)產(chǎn)生錯(cuò)誤的結(jié)果。針對(duì)上述問(wèn)題,他們提出了一些優(yōu)化策略,如雜湊樹(shù)平衡(hashtreebalancing)、優(yōu)化內(nèi)存布置(memoryplacementoptimization)等。APM算法是基于DIC的并行算法,對(duì)數(shù)據(jù)扭曲非常敏感,并且認(rèn)為數(shù)據(jù)是同構(gòu)的。在APM算法中,采用全局修剪技術(shù)來(lái)減小候選2-項(xiàng)集的大小,這在存在大的數(shù)據(jù)扭曲的時(shí)候非常有效。在第一次循環(huán)中,數(shù)據(jù)庫(kù)被邏輯劃分為大小相等的塊,對(duì)每個(gè)分塊執(zhí)行局部支持計(jì)數(shù),然后對(duì)它們進(jìn)行群集,用以生成候選2-項(xiàng)集。接下來(lái),數(shù)據(jù)庫(kù)被劃分為同構(gòu)的分塊,每個(gè)處理器在局部分塊上獨(dú)立地執(zhí)行DIC算法。這些在共享內(nèi)存系統(tǒng)上實(shí)現(xiàn)的基于Apriori并行算法存在著一些嚴(yán)重的缺陷,如極高的I/O負(fù)載、磁盤(pán)競(jìng)爭(zhēng)和欠佳的數(shù)據(jù)放置。3.2數(shù)據(jù)庫(kù)mlfptZaiane等提出了基于FP-growth的MultipleLocalFrequentPatternTree(MLFPT)算法,它是在共享內(nèi)存的有64個(gè)處理器的SGI系統(tǒng)上實(shí)現(xiàn)的。MLFPT算法只需對(duì)數(shù)據(jù)庫(kù)進(jìn)行二次掃描,避免了生成大量候選集的問(wèn)題,而且通過(guò)在挖掘過(guò)程的不同階段采用不同的劃分策略實(shí)現(xiàn)最佳的負(fù)載平衡。在頻繁模式樹(shù)(FPtree)生成階段,數(shù)據(jù)庫(kù)被劃分為大小均等的分塊,每個(gè)處理器生成一個(gè)局部頻繁模式樹(shù)(localFPtree)(見(jiàn)圖3)。在挖掘階段,所有處理器共享這些局部頻繁模式樹(shù),并生成相應(yīng)的頻繁1-項(xiàng)集的條件庫(kù),很大程度上減少了資源競(jìng)爭(zhēng)的現(xiàn)象。4并行關(guān)聯(lián)規(guī)則挖掘算法本文討論了現(xiàn)有的關(guān)聯(lián)規(guī)則挖掘算法,并從實(shí)現(xiàn)平臺(tái)、并行度和負(fù)載平衡等方面對(duì)并行關(guān)聯(lián)規(guī)則算法進(jìn)行了分析。依靠高性能的并行計(jì)算挖掘海量數(shù)據(jù)庫(kù)是一種理想的方法,然而想要獲得良好的性能并非易事。關(guān)于這方面的研究已經(jīng)取得了很大的成績(jī),但仍存在許多問(wèn)題有待進(jìn)一步地深