作者/邢馨心，河北衡水中學

數(shù)據(jù)挖掘取樣方法研究

作者/邢馨心，河北衡水中學

取樣方法這種有效的近似技術在現(xiàn)在的數(shù)據(jù)挖掘研究中能夠最大限度的減小數(shù)據(jù)集的處理規(guī)模，將大規(guī)模數(shù)據(jù)集及數(shù)據(jù)流數(shù)據(jù)上以數(shù)據(jù)挖掘算法進行處理。取樣法具有通用有效的特點。本文化通過對數(shù)據(jù)挖掘領域的取樣方法分類以及影響取樣方法選擇的因素等問題進行分析研究，著重探討了數(shù)據(jù)挖掘領域的代表性取樣方選用以及應用發(fā)展。

數(shù)據(jù)挖掘；取樣方法；均勻取樣；偏倚取樣

如今數(shù)據(jù)庫技術發(fā)展迅速、應用廣泛，數(shù)據(jù)庫中存儲的數(shù)據(jù)量也在急劇增長。數(shù)據(jù)挖掘就是把信息模式或未知和潛在有用的數(shù)據(jù)從海量數(shù)據(jù)存儲的數(shù)據(jù)庫中提取出來的一種方法。在數(shù)據(jù)挖掘領域中,采用一些有效的技術方法來處理數(shù)據(jù)，來減少和降低數(shù)據(jù)規(guī)模是有效準確提取數(shù)據(jù)的一種重要手段。取樣這種近似技術在處理數(shù)據(jù)集的規(guī)模上應用廣泛，它可以在的數(shù)據(jù)挖掘研究中能夠最大限度的減小數(shù)據(jù)集的處理規(guī)模，將大規(guī)模數(shù)據(jù)集及數(shù)據(jù)流數(shù)據(jù)上以數(shù)據(jù)挖掘算法進行處理。因此，這種通用的技術被廣泛應用到數(shù)據(jù)挖掘、統(tǒng)計評估、查詢優(yōu)化、數(shù)據(jù)流處理和機器處理學習中。

1.數(shù)據(jù)挖掘的取樣方法

作為一種經典的統(tǒng)計技術，抽樣長時間被廣泛應用于多個領域，當然也包括現(xiàn)在的數(shù)據(jù)管理領域。在數(shù)據(jù)管理中，通常我們會在大數(shù)據(jù)集中抽取具有數(shù)據(jù)基本特征的小部分數(shù)據(jù)子集來作為代表性樣本, 再根據(jù)該樣本進行數(shù)據(jù)挖掘來獲得近似的查詢結果。目前取樣技術中的諸多方法在數(shù)據(jù)管理中被廣泛運用。

■1.1 取樣方法的類別

取樣方法根據(jù)各數(shù)據(jù)項被選中概率的相同與否，主要可以分為均勻取樣和偏倚取樣兩大類，均勻取樣是指數(shù)據(jù)項被選中的概率相同，偏倚取樣是指數(shù)據(jù)項被選中的概率不同。在取樣過程中，均勻取樣設計這種所有以相同的取樣概率產生的相同尺寸且相互雷同的取樣，一般主要分為伯努利取樣和水庫取樣兩種經典的取樣設計，這兩種取樣設計是其他各類取樣方法的基礎。伯努利取樣具有取樣過程簡單、時間成本低和取樣均勻的特點。水庫取樣是一種隨機均勻取樣法，它通過單遍掃描數(shù)據(jù)集的方法生成均勻取樣集，它有效降低了時間復雜度，而且由于空間大小比較固定,所以很適合在數(shù)據(jù)庫領域應用。取樣技術的關鍵環(huán)節(jié)是如何確保取樣質量，傳統(tǒng)的取樣策略通常為三大類，分別是通過逐漸加大取樣尺寸或取樣率來使模型的正確性達到不再隨取樣進行改善的漸進取樣；以一個尺寸小的實驗樣本集進行數(shù)據(jù)集的預評估的如采用分層取樣、Two–Phase Sampling、luster Sampling等算法進行取樣的策略；第三類策略是以頻繁項誤差概要、近似查詢和查詢尺寸評估應用為方法來具體的應用抽取特定的數(shù)據(jù)特征的取樣策略。

■1.2 取樣方法的分析研究

1.2.1 最具代表性的取樣法

（1）A/R Sampling

A/R Sampling是一種應用于關系數(shù)據(jù)庫B+ 樹或空間數(shù)據(jù)庫的隨機取樣算法。它的主要流程是首先先選取某一種算法，隨機在數(shù)據(jù)集中均勻抽取一個候選元素與選擇條件進行對比，將經篩選后的所有與條件相符的元素放入樣本集中，拒絕條件不相符的元素，然后繼續(xù)第一步循環(huán)。

（2）精確取樣

精確取樣方法對于樣本集中只出現(xiàn)一次的元素依然采用水庫取樣的方式，以元素代碼表示，而對于于多次出現(xiàn)的元素則進行了一定的改進采用value, count結構來表示，value即意味著元素代碼，count表示樣本集中的元素數(shù)量。這種將各元素以初始值為1的概率參數(shù)T加入到樣本集合，當元素在樣本集中時則在計數(shù)器加1，如果樣本集溢出，就需要更改參數(shù)T，將樣本集中各個元素按照原參數(shù)與新參數(shù)之比進行刪除，以獲得存放新數(shù)據(jù)的空間的方法就是我們所說的精確取樣算法。它有效實現(xiàn)數(shù)據(jù)流上的均勻取樣，節(jié)約了內存。

（3）計數(shù)取樣

作為精確取樣方法變種的計數(shù)取樣是一種在處理樣本集溢出時所采取的一種變化性的方法。當樣本集溢出時,改變參數(shù)T，用原數(shù)據(jù)參數(shù)與新數(shù)據(jù)參數(shù)的比值來判斷是否進行減去，當計數(shù)器值下降為0時就停止對該元素數(shù)據(jù)進行操作。

（4）國會取樣

這種取樣方法一般主要應用于分組近似查詢，在每個分組內通過進行取樣率不同的獨立的水庫取樣，對分組屬性集中子集可能的組合情況進行綜合考慮。這種方法是一種對各分組屬性采用不同取樣概率來達到最佳查詢質量的取樣方法，是均勻取樣和偏倚取樣的綜合，它有效突破了均勻取樣的局限性，將不同分組大小數(shù)據(jù)的影響力和利益都考慮到取樣過程中。

（5） Stratif i ed Sampling

Stratif i ed Sampling是一種分層的取樣，它主要通過數(shù)據(jù)分布的歷史經驗來實現(xiàn)對數(shù)據(jù)進行取樣，在取樣過程中，對重要層分配的取樣點相對較多，然后采用隨機均勻取樣法對每一層進行取樣。這樣有效提高了評估的正確性，在取樣過程中要合理的對層數(shù)進行選擇并將數(shù)據(jù)分配到各個層中，從而使查詢處理結果達到偏差最小的狀態(tài)。

（6）加權取樣

在近似聚集查詢處理中，加權取樣有效的克服了均勻取樣的局限性，并且將更大的權重賦予使用率高的小數(shù)據(jù)集中的元組，借助工作負載信息獲得權值，是一種帶權值的偏倚取樣方法。

（7）Distinct Sampling

Distinct Sampling是一種對流查詢中的唯一值進行聚集的取樣技術的統(tǒng)稱。這種取樣方法使關系表更為精確，不至于遺漏關系表中稀少出現(xiàn)的屬性值，能夠通過對數(shù)據(jù)中的唯一值進行單遍掃描取樣，正確的評估唯一值的數(shù)目并對數(shù)據(jù)的插入和刪除進行增量維護。

1.2.2 均勻取樣與偏倚取樣

由于均勻取樣具有一定的局限性，所以在數(shù)據(jù)挖掘中出現(xiàn)了偏倚取樣法，它成功彌補了均勻取樣的弱點，使數(shù)據(jù)挖掘算法更為精確。均勻隨機取樣主要應用于數(shù)據(jù)分布概率比較均勻時，而當數(shù)據(jù)的尺寸決定樣本準確性時，應用均勻取樣就使查詢的精準度降低了。有時候占小比例的數(shù)據(jù)對用戶來說要比占大比例的數(shù)據(jù)重要的多。當數(shù)據(jù)的代表性都相同時，不同邏輯部分的數(shù)據(jù)就對用戶產生了偏斜的作用。當數(shù)據(jù)分布存在較大偏斜時，為了加速多維大數(shù)據(jù)集中聚類和離群檢測等挖掘任務的執(zhí)行，主要應用數(shù)據(jù)約減技術的密度偏倚取樣法，因為它能有效解決取樣過程中的偏斜、噪聲和高維問題能。

2.數(shù)據(jù)挖掘取樣技術的發(fā)展

取樣方法主要包括生成概要數(shù)據(jù)結構、數(shù)據(jù)預處理 、數(shù)據(jù)流近似聚集查詢、流數(shù)據(jù)分析與挖掘等，它目前廣泛應用于數(shù)據(jù)領域中。

■2.1 傳統(tǒng)取樣技術在數(shù)據(jù)挖掘領域的拓展

Adaptive Sampling, Stratif i ed Sampling等統(tǒng)計學領域中的傳統(tǒng)取樣技術目前正廣泛應用于數(shù)據(jù)挖掘和數(shù)據(jù)流領域。Adaptive Sampling 能夠有效評估有窮非負整數(shù)數(shù)列的通用方法，在數(shù)據(jù)挖掘領域中有著廣泛的應用。它是一種能夠有效調節(jié)取樣大小，以最小取樣尺寸解決誤差的一種自適應取樣方法。

■2.2 數(shù)據(jù)流中管理和挖掘中的取樣技術

數(shù)據(jù)流管理和數(shù)據(jù)流挖掘是數(shù)據(jù)流取樣技術的兩種基本表現(xiàn)方法。計數(shù)取樣、鏈式取樣、水庫取樣、精確取樣等算法主要是用于數(shù)據(jù)流處理模型中生成概要數(shù)據(jù)結構時。而在數(shù)據(jù)流近似聚集查詢時主要應用國會取樣和DV Sampling 類算法。對于數(shù)據(jù)流的查詢、分類、評估以及在線相關性分析我們一般主要采用偏倚取樣技術。

■2.3 取樣技術發(fā)展前景

傳統(tǒng)的取樣技術在數(shù)據(jù)挖掘領域中取得了重大的發(fā)展在數(shù)據(jù)庫的查詢優(yōu)化、數(shù)據(jù)挖掘算法的數(shù)據(jù)預處理等方面，對取樣技術的研究相對較多，而且成果顯著，但由于取樣算法中對于任意順序的差異與刪除和滑動窗口模型中應用的取樣技術、如何以最小化的樣本集中取得結果精確的最大化、如何設計偏倚取樣的算法等研究還比較較少，所以傳統(tǒng)取樣技術在數(shù)據(jù)挖掘領域的應用依舊面臨著很大的研究挑戰(zhàn)。以數(shù)據(jù)流管理領域最為突出。

3.結束語

通過研究發(fā)現(xiàn)，傳統(tǒng)取樣技術在數(shù)據(jù)挖掘領域得到了深遠的發(fā)展，有了新的生命力和內涵。但取樣技術的研究空間和研究挑戰(zhàn)性依然很大，人們期待更多新的取樣技術能做出更多的突破性發(fā)展。

＊ [1]胡臻龍.基于數(shù)據(jù)挖掘的高效取樣方法對手機用戶的周期運動模式的研究[J].科技通報,2013,(11):134-139+156.

＊ [2]胡文瑜,劉建華,張柏禮.近似聚集查詢中Congress onal Samples 算法的優(yōu)化研究[J].數(shù)學的實踐與認識，2013,(08):160-169.