數據挖掘取樣方法研究

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

數據挖掘取樣方法研究

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

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

數據挖掘；取樣方法；均勻取樣；偏倚取樣

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

1.數據挖掘的取樣方法

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

■1.1 取樣方法的類別

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

■1.2 取樣方法的分析研究

1.2.1 最具代表性的取樣法

（1）A/R Sampling

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

（2）精確取樣

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

（3）計數取樣

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

（4）國會取樣

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

（5） Stratif i ed Sampling

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

（6）加權取樣

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

（7）Distinct Sampling

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

1.2.2 均勻取樣與偏倚取樣

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

2.數據挖掘取樣技術的發展

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

■2.1 傳統取樣技術在數據挖掘領域的拓展

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

■2.2 數據流中管理和挖掘中的取樣技術

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

■2.3 取樣技術發展前景

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

3.結束語

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

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

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