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

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

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

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

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

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

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

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

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