作者/邢馨心，河北衡水中學(xué)

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

作者/邢馨心，河北衡水中學(xué)

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

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

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

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

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

■1.1 取樣方法的類別

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

■1.2 取樣方法的分析研究

1.2.1 最具代表性的取樣法

（1）A/R Sampling

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

（2）精確取樣

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

（3）計(jì)數(shù)取樣

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

（4）國(guó)會(huì)取樣

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

（5） Stratif i ed Sampling

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

（6）加權(quán)取樣

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

（7）Distinct Sampling

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

1.2.2 均勻取樣與偏倚取樣

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

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

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

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

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

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

數(shù)據(jù)流管理和數(shù)據(jù)流挖掘是數(shù)據(jù)流取樣技術(shù)的兩種基本表現(xiàn)方法。計(jì)數(shù)取樣、鏈?zhǔn)饺印⑺畮?kù)取樣、精確取樣等算法主要是用于數(shù)據(jù)流處理模型中生成概要數(shù)據(jù)結(jié)構(gòu)時(shí)。而在數(shù)據(jù)流近似聚集查詢時(shí)主要應(yīng)用國(guó)會(huì)取樣和DV Sampling 類算法。對(duì)于數(shù)據(jù)流的查詢、分類、評(píng)估以及在線相關(guān)性分析我們一般主要采用偏倚取樣技術(shù)。

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

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

3.結(jié)束語(yǔ)

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

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

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