并行關(guān)聯(lián)規(guī)則挖掘算法研究及其應(yīng)用.pdf

1、數(shù)據(jù)挖掘(DM)和知識發(fā)現(xiàn)(KDD)是從數(shù)據(jù)庫中抽取、識別出有效的、新穎的、有潛在作用的、可信的、并能最終被人理解的模式的非平凡處理過程.它適用于所有存在數(shù)據(jù)積累的領(lǐng)域.關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的主要模式之一,但是由于當(dāng)今的數(shù)據(jù)庫的量非常之大,在單機(jī)上進(jìn)行關(guān)聯(lián)規(guī)則挖掘顯得力不從心,隨著機(jī)群計(jì)算機(jī)的出現(xiàn),為進(jìn)行并行關(guān)聯(lián)規(guī)則挖掘提供了可能.本文將研究并行關(guān)聯(lián)規(guī)則挖掘算法,并提出一種無候選集生成的并行關(guān)聯(lián)規(guī)則挖掘算法,并將該并行關(guān)聯(lián)規(guī)則挖掘算法

2、應(yīng)用于電梯歷史數(shù)據(jù)領(lǐng)域.并行關(guān)聯(lián)規(guī)則的挖掘分為二步:首先挖掘出所有全局頻繁項(xiàng)集(根據(jù)給定最小支持度);然后生成所有強(qiáng)關(guān)聯(lián)規(guī)則(根據(jù)給定最小置信度).已有的并行挖掘算法都集中在對第一步問題的解決上,這些并行算法所采用的都是基于Apriori思想,即各個(gè)處理機(jī)各自對本地的數(shù)據(jù)庫進(jìn)行掃描,并利用全局頻繁項(xiàng)集Lk-1產(chǎn)生候選項(xiàng)集Ck,接著計(jì)算各候選項(xiàng)的局部支持?jǐn)?shù),在各處理機(jī)之間交換支持?jǐn)?shù)得到各候選項(xiàng)的全局支持?jǐn)?shù),最終生成全局頻繁K項(xiàng)集Lk.這些

3、算法存在的缺點(diǎn)是有大量的候選項(xiàng)生成,增加了通訊量,同時(shí)也需要多次掃描數(shù)據(jù)庫,增加了I/O消耗.本文提出了一種基于頻繁模式樹的并行挖掘算法,它的思想是:首先每個(gè)處理機(jī)掃描本地?cái)?shù)據(jù)庫并相互交換所有1-項(xiàng)集的支持?jǐn)?shù)得到全局頻繁1-項(xiàng)集Flist,再根據(jù)Flist將本地的數(shù)據(jù)庫壓縮成一棵頻繁模式樹;各處理機(jī)從各自的FPT中得到每個(gè)頻繁1-項(xiàng)的局部條件模式基,并通過交換在指定處理機(jī)上得到該1-項(xiàng)的全局條件模式基;各處理機(jī)對其上的全局條件模式基構(gòu)造

4、條件頻繁模式樹并挖掘出以該1-項(xiàng)為尾的所有頻繁項(xiàng)集.該算法的優(yōu)點(diǎn)是無需生成候選項(xiàng)集,這就避免了多次掃描數(shù)據(jù)庫各候選項(xiàng)進(jìn)行計(jì)數(shù),減少了I/O消耗;同時(shí)只通過交換各1-項(xiàng)的條件模式基,相應(yīng)地通訊量也大減少了.實(shí)驗(yàn)也證明了該算法的高效性.此外,將該算法注冊到基于機(jī)群計(jì)算機(jī)的并行數(shù)據(jù)挖掘平臺的算法庫中,并應(yīng)用到電梯數(shù)據(jù)集,挖掘出了電梯維護(hù)數(shù)據(jù)之間的有價(jià)值的規(guī)則,對經(jīng)營者的分析和決策提供有益的幫助和指導(dǎo).本研究得到到國家自然科學(xué)基金項(xiàng)目(6027