數(shù)據(jù)挖掘取樣方法與數(shù)據(jù)結(jié)構(gòu)研究

張本文

摘要：取樣是一種非常通用的近似技術(shù)。取樣方法在數(shù)據(jù)挖掘研究中能顯著減小數(shù)據(jù)處理規(guī)模，使數(shù)據(jù)挖掘算法更加大規(guī)模的作用到數(shù)據(jù)流中。對數(shù)據(jù)結(jié)構(gòu)的研究也成為了數(shù)據(jù)挖掘取樣方法的中心。本文主要闡述了數(shù)據(jù)挖掘領(lǐng)域中取樣方法的靈活性，并且對數(shù)據(jù)挖掘取樣方法的發(fā)展和面臨的挑戰(zhàn)做出了展望。

關(guān)鍵詞：數(shù)據(jù)挖掘 取樣方法 數(shù)據(jù)結(jié)構(gòu)

中圖分類號(hào)：TP311.13 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）12-0106-01

正是由于數(shù)據(jù)庫技術(shù)的廣泛應(yīng)用和快速的發(fā)展，數(shù)據(jù)庫所能儲(chǔ)存的數(shù)據(jù)也順應(yīng)時(shí)代潮流越來越大。如何采用適當(dāng)?shù)募夹g(shù)來降低數(shù)據(jù)流的規(guī)模成為一個(gè)重要的問題，特別是最近的某些領(lǐng)域廣泛應(yīng)用數(shù)據(jù)流信息，比如通信管理和網(wǎng)絡(luò)監(jiān)測，為了維護(hù)數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)穩(wěn)定性，取樣成為了最通用的近似技術(shù)。取樣在保證一定的精確度下，使得數(shù)據(jù)挖掘算法廣泛應(yīng)用到數(shù)據(jù)流中去。目前常用的概要結(jié)構(gòu)設(shè)計(jì)方法有小波方法、直方圖方法、Hash等。

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

1.1 A/R Sampling

A/R Sampling算法主要是通過挖掘算法從數(shù)據(jù)流中不定向抽選一個(gè)候選元素，然后通過把此元素與所要求的條件作出對比，只有符合條件的元素才會(huì)接受，作為樣本集，不符合的拒絕，重復(fù)此循環(huán)。

1.2 精確取樣方法

精確取樣用元素代碼表示在樣本集中僅僅出現(xiàn)一次的元素，而用value，count來表示重復(fù)出現(xiàn)的元素，當(dāng)中的value是表示元素所對應(yīng)的代碼，count則表示元素出現(xiàn)的次數(shù)數(shù)量。一般情況，元素是否放入樣本集是有條件的，假如元素沒有在樣本集里出現(xiàn)過則就可以直接放入樣本集，但是如果元素已經(jīng)存在于樣本集中了，那么就在數(shù)量count上加1。這樣，當(dāng)樣本集容量已滿時(shí)，樣本集中的每個(gè)元素?cái)?shù)據(jù)都會(huì)按照原始對應(yīng)參數(shù)來進(jìn)行對比然后刪除，保持?jǐn)?shù)據(jù)的存放性。

1.3 計(jì)數(shù)取樣方法

計(jì)數(shù)取樣是在精確取樣方法基礎(chǔ)上轉(zhuǎn)變過來的，在處理樣本集溢出情況時(shí)，在刪除數(shù)據(jù)之前要和原數(shù)據(jù)進(jìn)行比較，然后通過新參數(shù)分之一來判斷數(shù)據(jù)時(shí)候要減1。當(dāng)數(shù)據(jù)的數(shù)量值為0時(shí)，就不再對該數(shù)據(jù)進(jìn)行操作。

1.4 分出取樣方法

分層取樣實(shí)際上是將數(shù)據(jù)信息曾經(jīng)分布的情況用作參考來對目前的數(shù)據(jù)進(jìn)行分層的，這樣，對于那些分布多的層就會(huì)采取更多的取樣點(diǎn)，大大提高了數(shù)據(jù)挖掘算法的準(zhǔn)確性。同時(shí)對于每一層的數(shù)據(jù)而言，則采用均勻的取樣技術(shù)進(jìn)行隨機(jī)的采取點(diǎn)。

1.5 國會(huì)取樣方法

國會(huì)取樣可以說是是均勻隨機(jī)取樣方法的基礎(chǔ)上結(jié)合了偏倚取樣技術(shù)，因?yàn)閷τ诿總€(gè)分組都會(huì)獨(dú)立取樣，不同的是取樣的概率是不同的。比如，對于某些較大的分組，就會(huì)對元素的取樣率大大增加，反過來說，對于某些較小的分組，對元素的取樣率就大大減少，這種兼顧性就突破了均勻取樣的局限性。

1.6 Distinct Sampling

Distinct Sampling相當(dāng)于取樣方法的綜合說法，從按類型方面來看，屬于聚集流的搜索處理查詢中的唯一值取樣方法。通過對數(shù)據(jù)中的唯一的元素進(jìn)行逐一的掃描再逐一的加入的樣本集的方法進(jìn)行取樣，這樣就大大提高了對于唯一的個(gè)體數(shù)目的評估正確性。

2 數(shù)據(jù)挖掘在取樣方法中的發(fā)展

取樣方法在統(tǒng)計(jì)計(jì)算、數(shù)據(jù)處理和挖缺信息中普遍存在，在某些知識(shí)發(fā)展的方面扮演著無法替換的功能角色。在數(shù)據(jù)挖掘取樣方法中的應(yīng)用案例非常之多，比如房地產(chǎn)的數(shù)據(jù)分析和用戶需求統(tǒng)計(jì)中一般采用均勻隨機(jī)的抽樣方法來搜集大數(shù)據(jù)。在對數(shù)據(jù)結(jié)構(gòu)的構(gòu)建中采用的數(shù)據(jù)挖掘算法也很多。例如CURE和CLARANS，通過算法再加上取樣方法的預(yù)處理能力，在專業(yè)人士的分析統(tǒng)計(jì)下，算法和取樣方法都得到了最大化的發(fā)揮。

自適應(yīng)取樣是針對有窮非負(fù)數(shù)數(shù)據(jù)的一種評估方法，我們可以任意調(diào)節(jié)取樣樣本的大小，通過數(shù)據(jù)挖掘方面的整理，可以實(shí)現(xiàn)用最小的樣本解決更小的誤差遺留問題。為了順應(yīng)需求節(jié)約取樣的成本，二階段取樣的評估方法出現(xiàn)了。大概含義如下：在挖掘樣本對象時(shí)，有時(shí)候會(huì)出現(xiàn)一些大成本的取樣對象，為了解決這種煩惱，可以尋找一種輔助的取樣對象來減少成本的代價(jià)。通過這個(gè)輔助對象的比例來推斷出原來那個(gè)大成本的取樣對象。這樣不但解決了成本問題，而且目標(biāo)精確度也會(huì)提高。

取樣技術(shù)在數(shù)據(jù)集中的主要方面就是管理和挖掘：（1）針對數(shù)據(jù)集的處理模型中數(shù)據(jù)結(jié)構(gòu)的需要里需要均勻取樣方法和計(jì)數(shù)取樣方法。（2）針對數(shù)據(jù)流在某些近似的查詢過程中需要國會(huì)取樣方法和Distinct Sampling等。（3）針對數(shù)據(jù)集運(yùn)用的偏倚取樣技術(shù)，這樣能夠解決一些應(yīng)用過程中的數(shù)據(jù)管理、分配、評判問題的分析。

3 數(shù)據(jù)挖掘取樣方法面對的挑戰(zhàn)

通過研究發(fā)現(xiàn)，傳統(tǒng)的取樣方法在數(shù)據(jù)挖掘領(lǐng)域中得到了深遠(yuǎn)的發(fā)展，取樣技術(shù)在數(shù)據(jù)庫的搜查處理、關(guān)于頻繁元素的挖掘和數(shù)據(jù)挖掘算法的提前處理等方面有比較成熟的研究，不過在取樣技術(shù)的某些方面挑戰(zhàn)性還有很大的存在，比如數(shù)據(jù)集管理方面上，具體包括：

（1）怎樣在小的樣本集上獲取盡可能的精確結(jié)果，克服空間局限，滿足相應(yīng)的要求下解決取樣復(fù)雜情況。（2）關(guān)于滑動(dòng)窗口的一些模型取樣技術(shù)方法還是不夠成熟，很多限制的存在造成了制約，比如說內(nèi)存界限的不確定性、滑動(dòng)窗口較小、成本高等問題。（3）當(dāng)前的算法大多數(shù)對于插入刪除情況有局限，對于用戶性的插入和頻繁刪除數(shù)據(jù)情況問題是數(shù)據(jù)流動(dòng)態(tài)維護(hù)所必要解決的問題。（4）如何設(shè)計(jì)出好的偏倚取樣算法是未來發(fā)展研究的方法之一。

4 結(jié)語

數(shù)據(jù)挖掘在社會(huì)經(jīng)濟(jì)的發(fā)展中展現(xiàn)了獨(dú)特的魅力，然后，取樣方法則是制約數(shù)據(jù)挖掘發(fā)展精確性的重要因素。在未來的發(fā)展空間中，只要運(yùn)用合適的取樣方法就可以大大提高數(shù)據(jù)挖掘的效率。企業(yè)在大量的數(shù)據(jù)中能夠迅速發(fā)現(xiàn)對自己有價(jià)值的信息，這樣就促進(jìn)了企業(yè)的競爭發(fā)展，在促進(jìn)企業(yè)健康發(fā)展的同時(shí)，正確的取樣方法也完善了數(shù)據(jù)挖掘的算法。隨著研究的深入，一定會(huì)在原有的基礎(chǔ)上取得更高的成就。

參考文獻(xiàn)

[1]張成叔關(guān)于數(shù)據(jù)挖掘取樣方式的若干分析[J].赤峰學(xué)院學(xué)報(bào)（自然科學(xué)版），2014（9）.

[2]胡文瑜.數(shù)據(jù)挖掘取樣技術(shù)與算法研究[D].東南大學(xué)，2011.

[3]胡文瑜，蔡文培.數(shù)據(jù)挖掘取樣方法的衡量與選用研究[J].福建工程學(xué)院學(xué)報(bào)，2011（4）.