分布式關(guān)聯(lián)規(guī)則挖掘若干算法研究與實(shí)現(xiàn).pdf

1、隨著信息時(shí)代的到來和計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，分布式環(huán)境日益普遍，而傳統(tǒng)的集中式數(shù)據(jù)挖掘技術(shù)無法解決分布式下的挖掘問題，故在分布式下如何進(jìn)行有效的數(shù)據(jù)挖掘成為當(dāng)今人工智能研究領(lǐng)域一個(gè)熱門課題。關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘研究領(lǐng)域的一個(gè)重要問題，目前所面臨的最大挑戰(zhàn)是計(jì)算效率，內(nèi)存和結(jié)果冗余問題。解決的途徑之一是開發(fā)高效的分布式算法。因此本文從分布式的角度出發(fā)，針對關(guān)聯(lián)規(guī)則挖掘理論和方法進(jìn)行了深入研究，提出了若干高效的分布式關(guān)聯(lián)規(guī)則挖掘算法。具體研

2、究內(nèi)容如下： 第一，針對關(guān)聯(lián)規(guī)則的問題及現(xiàn)有分布式系統(tǒng)體系結(jié)構(gòu)的特點(diǎn)，根據(jù)數(shù)據(jù)分布和通信模型的不同，提出了兩種分布式挖掘關(guān)聯(lián)規(guī)則的框架：同步挖掘和異步挖掘。 第二，分析當(dāng)前分布式拓?fù)浣Y(jié)構(gòu)的特點(diǎn)，提出了網(wǎng)狀分布式拓?fù)浣Y(jié)構(gòu)下關(guān)聯(lián)規(guī)則同步挖掘算法NDMA和星型分布式拓?fù)浣Y(jié)構(gòu)下關(guān)聯(lián)規(guī)則異步挖掘算法SDMA算法。算法中用到的優(yōu)化技術(shù)包括：基于哈希方法的候選集的劃分和通信技術(shù)，候選集局部前綴樹的構(gòu)建和全局修剪技術(shù)，局部數(shù)據(jù)抽樣技術(shù)及

3、集成時(shí)的歸納學(xué)習(xí)和推導(dǎo)技術(shù)等，這些技術(shù)能產(chǎn)生較小的候選集，使候選集計(jì)數(shù)通信次數(shù)減為o(n)，從而提高了算法效率，改善了內(nèi)存使用情況。實(shí)驗(yàn)結(jié)果表明：NDMA算法在支持度較低時(shí)執(zhí)行效率比同類算法FDM高60％以上。算法中用到的提高挖掘精度的技術(shù)包括：提出候選頻繁模式集降低分布式挖掘漏計(jì)概率；提出負(fù)邊界和動(dòng)態(tài)縮減的支持度解決抽樣導(dǎo)致挖掘精度不高的問題，定義了棄真和存?zhèn)蝺深愬e(cuò)誤來評(píng)估挖掘結(jié)果。實(shí)驗(yàn)結(jié)果表明：SDMA算法抽樣率在25％就達(dá)到了棄真

4、錯(cuò)誤為1.6％，存?zhèn)五e(cuò)誤為4.6％較高的挖掘精度。 第三，針對現(xiàn)有分布式關(guān)聯(lián)規(guī)則挖掘結(jié)果冗余的問題，設(shè)計(jì)了一個(gè)全新的分布式無冗余關(guān)聯(lián)規(guī)則異步算法DGNRR。該算法摒棄了現(xiàn)存相關(guān)算法在分站點(diǎn)采用完全模式挖掘的方法，改用閉合模式挖掘。算法核心技術(shù)主要有定義了閉合模式傳輸格式和集成后的閉合模式格式，設(shè)計(jì)了根據(jù)源站點(diǎn)的不同的兩套閉合模式集成規(guī)則，分析了無冗余關(guān)聯(lián)規(guī)則的特點(diǎn)，在此基礎(chǔ)上給出了從閉合模式產(chǎn)生無冗余關(guān)聯(lián)規(guī)則的方法。最后在稀疏型