數(shù)據(jù)挖掘取樣技術(shù)與算法研究.pdf

1、數(shù)據(jù)挖掘是在海量數(shù)據(jù)中提取隱含的、未知的、潛在有用的知識(shí)或信息模式的決策支持方法,其在功能上的健壯性和應(yīng)用領(lǐng)域的廣泛性已被研究者一致認(rèn)同.而取樣是最通用有效的近似技術(shù),在保證一定精確度的前提下,取樣方法顯著減小了所處理數(shù)據(jù)集的規(guī)模,使得眾多數(shù)據(jù)挖掘算法得以應(yīng)用到大規(guī)模數(shù)據(jù)集以及數(shù)據(jù)流數(shù)據(jù)上.由此,取樣這種近似技術(shù)在數(shù)據(jù)挖掘,查詢優(yōu)化,統(tǒng)計(jì)評(píng)估,決策支持,數(shù)據(jù)流處理和機(jī)器學(xué)習(xí)中被普遍使用,另外,由于取樣方法良好的伸縮性和靈活性,也使其成為

2、構(gòu)建數(shù)據(jù)流概要的一個(gè)非常重要的方法.
　　 本文圍繞著數(shù)據(jù)挖掘的取樣技術(shù)進(jìn)行研究,研究的過程中采用了比較研究的技術(shù)和方法,其主要內(nèi)容包括:
　　 (1)代表性取樣方法之間的特性、應(yīng)用與性能比較;
　　 (2)偏倚取樣與均勻取樣方法之間的利弊與選用比較;
　　 (3)取樣方法與其他概要數(shù)據(jù)結(jié)構(gòu)方法的比較;
　　 (4)基本的最優(yōu)K相異性取樣算法(OptiSim)與擴(kuò)展的OptiSim方法的比較;

3、r>　　 (5)近似查詢處理中在線處理方法與預(yù)計(jì)算處理方法的比較;
　　 此外,本文提出了可應(yīng)用于數(shù)據(jù)挖掘領(lǐng)域的一系列有效取樣算法,并進(jìn)行了理論分析和實(shí)驗(yàn)驗(yàn)證.具體而言。本論文研究的主要內(nèi)容及創(chuàng)新點(diǎn)可以歸納為以下六個(gè)方面:
　　 (1)綜述了數(shù)據(jù)挖掘領(lǐng)域取樣技術(shù)和方法的研究成果,在對(duì)代表性取樣方法進(jìn)行比較研究和分析總結(jié)的基礎(chǔ)上,提出了一個(gè)能將現(xiàn)有的代表性取樣方法納入的一個(gè)通用取樣算法分類框架.論述了均勻取樣存在的應(yīng)用局

4、限與偏倚取樣的必要性問題.闡述了數(shù)據(jù)挖掘取樣技術(shù)的應(yīng)用與發(fā)展,特別是傳統(tǒng)取樣技術(shù)在數(shù)據(jù)挖掘領(lǐng)域中的新拓展與新應(yīng)用,指出了取樣技術(shù)和方法面臨的挑戰(zhàn)和研究展望.
　　 (2)在綜述了數(shù)據(jù)挖掘領(lǐng)域中與取樣技術(shù)相關(guān)的構(gòu)造概要數(shù)據(jù)結(jié)構(gòu)方法的基礎(chǔ)上,進(jìn)行取樣方法與其他概要數(shù)據(jù)結(jié)構(gòu)方法(如:哈希、小波、直方圖和基本窗口)之間的多方位討論與比較.著重研究了取樣復(fù)雜性理論,取樣尺寸對(duì)取樣偏差的影響、適用的取樣方法衡量標(biāo)準(zhǔn)以及影響取樣方法選擇的因素

5、等問題.提出了能更好地評(píng)估取樣質(zhì)量,尤其是偏倚取樣方法取樣質(zhì)量的”取樣方法代表性”和”取樣偏差(Sampie Deviation)”等概念,并在此基礎(chǔ)上得出了若干能避免過取樣問題的研究結(jié)論,最后通過實(shí)驗(yàn)驗(yàn)證了這些結(jié)論的可靠性.
　　 (3)最優(yōu)K相異性選擇算法OptiSim是一些基于相異性選擇算法的一個(gè)更加一般的、統(tǒng)一的方法,是一種能選擇既有代表性又兼顧多樣化的快速和通用的數(shù)據(jù)子集選擇技術(shù),而DBSCAN是一種優(yōu)秀的密度聚類算法

6、.本文提出了一個(gè)基于OptiSim的的密度聚類算法:OR-DBSCAN,它在DBSCAN處理之前應(yīng)用代表性子集取樣算法OptiSim作為數(shù)據(jù)預(yù)處理,由此來提高原DBSCAN算法的聚類效率.在研究了OptiSim存在的應(yīng)用局限的基礎(chǔ)上,提出了擴(kuò)展的OptiSim(EOptiSim)方法,EOptiSim方法對(duì)OptiSim有三處關(guān)鍵的改進(jìn):偏好選擇改進(jìn)、旋轉(zhuǎn)選擇改進(jìn)和不對(duì)稱旋轉(zhuǎn)選擇改進(jìn),從而彌補(bǔ)了原OptiSim算法在處理組合數(shù)據(jù)庫(kù)和分布

7、式數(shù)據(jù)庫(kù)方面的不足.最后,提出了一個(gè)基于相異性選擇的數(shù)據(jù)流偏倚取樣方法與有效性可行性分析.
　　 (4)將EOptiSim技術(shù)和移動(dòng)Agent技術(shù)結(jié)合起來,推廣應(yīng)用于分布式數(shù)據(jù)挖掘中,提出了一種適用于分布式數(shù)據(jù)挖掘環(huán)境的偏倚取樣技術(shù).該方法尤其適合于各場(chǎng)地?cái)?shù)據(jù)是互相關(guān)聯(lián)和互相依賴的分布式數(shù)據(jù)挖掘任務(wù).在同樣條件下,所提方法的CPU需求、I/O成本和網(wǎng)絡(luò)通訊代價(jià)比集中式處理模型(Client-Server模型)的小,并且具有良好的

8、實(shí)時(shí)性能.
　　 (5)在對(duì)應(yīng)用于近似聚集查詢的取樣技術(shù)和離群點(diǎn)檢測(cè)技術(shù)深入研究的基礎(chǔ)上,提出了一個(gè)能克服均勻取樣局限的離群分治取樣算法:Outlier-DivideConquer,其中的離群分離算法Outlier-Divide,只需單遍掃描數(shù)據(jù)集,無需對(duì)整個(gè)聚集屬性集進(jìn)行排序,與同類算法相比,運(yùn)行效率有優(yōu)勢(shì).Outlier-DivideConquer方法在數(shù)據(jù)集存在少量離群數(shù)據(jù)的情況下,能有效提高近似聚集查詢的質(zhì)量,實(shí)驗(yàn)結(jié)果驗(yàn)