基于抽樣的分布式關(guān)聯(lián)規(guī)則挖掘算法.pdf

1、數(shù)據(jù)挖掘是指從巨量數(shù)據(jù)中獲取有效的、新穎的、潛在有用的、最終可理解的模式的非平凡過程，其目的就是要從大量數(shù)據(jù)中找出有意義的模式，因此具有廣泛的應(yīng)用價(jià)值。在數(shù)據(jù)挖掘的研究中，如何高效的發(fā)現(xiàn)滿足用戶要求的關(guān)聯(lián)規(guī)則已經(jīng)成為一個(gè)核心問題。 抽樣是指選取給定數(shù)據(jù)庫D的隨機(jī)樣本S，在S中而不是在D中進(jìn)行數(shù)據(jù)挖掘。抽樣方法比較適合于對(duì)大型數(shù)據(jù)庫的挖掘。分布式情況下，各站點(diǎn)擁有的數(shù)據(jù)量較大時(shí)，可以采用抽樣方法在各站點(diǎn)隨機(jī)抽樣獲得樣本集，將這些隨

2、機(jī)樣本的挖掘結(jié)果作為對(duì)整個(gè)分布式數(shù)據(jù)庫挖掘的結(jié)果，提高挖掘的效率。 動(dòng)態(tài)項(xiàng)集計(jì)數(shù)技術(shù)將數(shù)據(jù)庫劃分為標(biāo)記開始點(diǎn)的塊，不像Apriori僅在每次掃描之前確定新的候選，在這種變形中，可以在任何開始點(diǎn)添加新的候選集。該技術(shù)動(dòng)態(tài)地評(píng)估已被計(jì)數(shù)的所有項(xiàng)集的支持度，如果一個(gè)項(xiàng)集的所有子集已被確定為頻繁的，則添加它作為新的候選，結(jié)果算法需要的數(shù)據(jù)庫掃描比Apriori少，減輕了I/O負(fù)載，提高了挖掘的效率。 影響分布式數(shù)據(jù)挖掘效率的主要

3、因素是分布式數(shù)據(jù)庫中各節(jié)點(diǎn)間的通信量。元學(xué)習(xí)的概念是由Prodromidis等人于2000年首先提出的，該方法采用集成學(xué)習(xí)(ensemblelearning)的方式來生成最終的全局預(yù)測(cè)模型。其優(yōu)點(diǎn)在于：在基學(xué)習(xí)階段，各個(gè)結(jié)點(diǎn)可以自主地選擇合適的學(xué)習(xí)算法來生成局部的基分類器(baseclassifiers)，與此同時(shí)各結(jié)點(diǎn)間不存在任何通訊與同步開銷，因此系統(tǒng)中各結(jié)點(diǎn)間的通信量較少，效率較高。 由二元關(guān)系導(dǎo)出的概念格作為一種非常有用

4、的形式化工具，體現(xiàn)了概念內(nèi)涵和外延的統(tǒng)一，反映了對(duì)象和特征間的聯(lián)系以及概念的泛化與例化關(guān)系。在挖掘規(guī)則知識(shí)過程中，規(guī)則本身是用內(nèi)涵集之間的關(guān)系來描述，而體現(xiàn)于相應(yīng)外延集之間的包含關(guān)系。而由于概念格節(jié)點(diǎn)之間的關(guān)系體現(xiàn)了概念之間泛化和例化關(guān)系，因此非常適合作為規(guī)則發(fā)現(xiàn)的基礎(chǔ)性數(shù)據(jù)結(jié)構(gòu)。 本文詳細(xì)介紹了關(guān)聯(lián)規(guī)則挖掘的基本概念和相關(guān)技術(shù)，結(jié)合動(dòng)態(tài)項(xiàng)集計(jì)數(shù)和抽樣的思想，利用元學(xué)習(xí)策略來產(chǎn)生頻繁項(xiàng)集，提出了一個(gè)分布式關(guān)聯(lián)規(guī)則挖掘算法DASM

5、；引進(jìn)了相似度的概念，并用之提高了挖掘結(jié)果的精確度。理論分析以及實(shí)驗(yàn)均表明，DASM算法具有較高的挖掘效率和較低的通信量，適用于對(duì)效率要求較高的應(yīng)用領(lǐng)域。此外，介紹了概念格和關(guān)聯(lián)規(guī)則發(fā)現(xiàn)之間的關(guān)系，描述了對(duì)于分布式環(huán)境下利用概念格理論、抽樣方法進(jìn)行關(guān)聯(lián)規(guī)則提取的解決方法，并給出了一個(gè)利用概念格提取無冗余關(guān)聯(lián)規(guī)則的分布式算法DSCL算法。 我們的創(chuàng)新點(diǎn)在于：1.將動(dòng)態(tài)項(xiàng)集計(jì)數(shù)方法和抽樣方法相結(jié)合，解決了關(guān)聯(lián)規(guī)則挖掘算法I/O負(fù)載過

6、重的問題，可以很好地滿足對(duì)效率比完備性要求更高的應(yīng)用領(lǐng)域的需要。 2.在分布式算法中，使用元學(xué)習(xí)分布式策略，使分布式挖掘規(guī)則的過程中的通信量?jī)H和產(chǎn)生的頻繁項(xiàng)集個(gè)數(shù)相關(guān)，減少了分布式系統(tǒng)中各站點(diǎn)間的通信量，解決了目前分布式算法通信量較大的問題。 3.將概念格和抽樣方法相結(jié)合，利用概念格的特性避免了在發(fā)現(xiàn)規(guī)則的過程中需要多次掃描數(shù)據(jù)庫的問題，并使用抽樣方法減少了數(shù)據(jù)量，進(jìn)一步減少了I/O負(fù)載，提高了算法的挖掘效率。另外，應(yīng)用