基于折疊技術(shù)的大數(shù)據(jù)樣本洗牌算法研究

李 慶，劉涵閱，張春生

(內(nèi)蒙古民族大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，內(nèi)蒙古 通遼 028043)

0 引 言

大數(shù)據(jù)分析是目前研究和應(yīng)用的熱點(diǎn)，近幾年在大數(shù)據(jù)分析領(lǐng)域的研究取得了長(zhǎng)足的發(fā)展，但大數(shù)據(jù)分析的效率問(wèn)題仍然是發(fā)展的瓶頸。舍恩伯格和庫(kù)克耶指出:大數(shù)據(jù)不用隨機(jī)分析法這樣的捷徑，而采用所有數(shù)據(jù)的方法。所謂“所有數(shù)據(jù)”是一種相對(duì)的說(shuō)法，但在問(wèn)題思路上，似乎又回轉(zhuǎn)向了“全面調(diào)查”，數(shù)據(jù)科學(xué)家甚至提出了“樣本=總體”的準(zhǔn)則。

對(duì)“樣本=總體”的觀點(diǎn)存在爭(zhēng)議，事實(shí)上不可能完全利用存在無(wú)效信息的全部大數(shù)據(jù)進(jìn)行分析，因此采樣調(diào)查仍然具有可行性。采樣調(diào)查強(qiáng)調(diào)的是“窺一斑而知全豹”，從充分均勻的樣本中選取一部分，就能有效推斷總體的情況[1-6]。

但在大數(shù)據(jù)時(shí)代，面對(duì)大量的數(shù)據(jù)及源源不斷的數(shù)據(jù)流，如何科學(xué)地從中選取合適的樣本，從而達(dá)到保證采樣調(diào)查樣本的精度和統(tǒng)計(jì)分析的目的，這是大數(shù)據(jù)時(shí)代下采樣調(diào)查面臨的最大問(wèn)題。另外，采樣后的局部數(shù)據(jù)是否能真實(shí)反映全局?jǐn)?shù)據(jù)的規(guī)則也是探討和研究的一個(gè)重要課題。一個(gè)潛在的解決方案是給出近似結(jié)果，也就是由抽樣產(chǎn)生的局部數(shù)據(jù)生成的隱知識(shí)來(lái)近似表示全局的隱知識(shí)。

得到正確可用的局部數(shù)據(jù)的前提是要有一個(gè)好的大數(shù)據(jù)洗牌算法，鑒于隨機(jī)抽樣算法存在樣本分布不夠理想的現(xiàn)實(shí)[7-11]，該文首先提出一種基于折疊技術(shù)的洗牌算法。該算法來(lái)源于生活中的撲克洗牌原理，算法簡(jiǎn)單易行，不受時(shí)間種子的影響，具有較高的時(shí)間效率、離散度和均勻度?；谡郫B技術(shù)的大數(shù)據(jù)洗牌算法為大數(shù)據(jù)抽樣和提高局本樣本的可用性提供了一個(gè)新途徑。

1 基于隨機(jī)序列的洗牌算法

為了與該文提出的基于折疊洗牌技術(shù)的大數(shù)據(jù)抽樣算法進(jìn)行對(duì)比，采用目前比較流行的2種不重復(fù)隨機(jī)采樣算法，即基于哈希技術(shù)和基于Guid技術(shù)的不重復(fù)隨機(jī)采樣算法。

1.1 基于哈希技術(shù)的洗牌算法

利用哈希表來(lái)生成無(wú)沖突序列算法的基本原理是[12-14]，首先定義一個(gè)空哈希表，通過(guò)隨機(jī)函數(shù)Rand()生成一個(gè)隨機(jī)數(shù)，并判斷哈希表里是否有與之相同的隨機(jī)數(shù)，如果有則重新調(diào)用Rand()函數(shù)，如果沒(méi)有，則將該隨機(jī)數(shù)放入哈希表，并使其關(guān)鍵碼值也等于該隨機(jī)數(shù)。由于該序列的每一個(gè)關(guān)鍵碼值與其所對(duì)應(yīng)的數(shù)據(jù)值相等，所以可以直接通過(guò)關(guān)鍵碼的映射進(jìn)行按值查詢。

算法如下：

Hashtable hashtable=new Hashtable();

Rand() rm=new Rand() ;

int RmNum=N;//N為隨機(jī)數(shù)個(gè)數(shù)

for (int i=0;hashtable.Count

{

int nValue=rm.Next(100);

if(!hashtable.ContainsValue(nValue) && nValue!=0)

{

hashtable.Add(nValue, nValue);

}

}

1.2 基于Guid技術(shù)的洗牌算法

Guid又稱為全局唯一標(biāo)識(shí)符[15]，在理想情況下，任何計(jì)算機(jī)和計(jì)算機(jī)集群都不會(huì)生成兩個(gè)相同的Guid值，一般表示成32個(gè)16進(jìn)制數(shù)字(0-9，A-F)組成的字符串，它實(shí)質(zhì)上是一個(gè)128位長(zhǎng)的二進(jìn)制整數(shù)。

算法首先定義一個(gè)空序列，并調(diào)用Guid方法生成一個(gè)不唯一的數(shù)，然后將這個(gè)數(shù)作為隨機(jī)種子放入Rand()函數(shù)中得到一個(gè)隨機(jī)數(shù)，接著將這個(gè)隨機(jī)數(shù)放入剛才定義的空序列，重復(fù)以上操作，最終會(huì)得到一個(gè)隨機(jī)序列。

算法如下：

private void btn_jdsjxp_Click(object sender, EventArgs e)

{

int i_ybzs; //樣本總數(shù)

int i; //設(shè)置樣本循環(huán)變量

int k; //隨機(jī)下標(biāo)

i_ybzs=int.Parse(tb_ybs.Text);

//樣本總數(shù)轉(zhuǎn)換為整

int[] yb_s=new int[i_ybzs];

//定義原始樣本序列

int[] yb_d=new int[i_ybzs];

//定義目標(biāo)樣本序列

for(i=0;i

//初始化樣本序列

{

yb_s[i]=i+1;

yb_d[i]=0;

}

for(i=0;i

//開(kāi)始對(duì)所有樣本循環(huán)

{

k=GetRandNumber(0, i_ybzs-1);

//隨機(jī)選擇不重復(fù)樣本下標(biāo)

yb_d[i]=yb_s[k];

}

2 基于折疊技術(shù)的洗牌算法

2.1 基于折疊技術(shù)的洗牌算法的優(yōu)勢(shì)

鑒于隨機(jī)抽樣算法受到時(shí)間種子的影響，采樣分布不夠均勻，而折疊洗牌算法模仿?lián)淇伺频南磁圃恚M(jìn)行多次分段均勻組合，算法的分布不受隨機(jī)數(shù)限制，全程均勻分布，同時(shí)由于不進(jìn)行重復(fù)數(shù)判斷，所以，無(wú)論從數(shù)據(jù)分布還是時(shí)間效率上都應(yīng)比隨機(jī)抽樣算法優(yōu)越。

2.2 折疊技術(shù)的洗牌算法描述

基于折疊洗牌技術(shù)的采樣算法基本原理是，折疊洗牌算法模擬撲克的洗牌過(guò)程，設(shè)樣本總數(shù)為n*k+p，其中p和k代表段長(zhǎng)，p≤k。當(dāng)p=k時(shí)，n*k+p=(n+1)*k，數(shù)據(jù)分n+1段；當(dāng)p

例如n+1段k長(zhǎng)樣本段的頭頭連接方法如下：

I11,I12,…,I1k

I21,I22,…,I2k

…

In1,In2,…,Ink

I(n+1)1,I(n+1)2,…,I(n+1)k

頭頭連接為：

I11,I21,…,In1,I(n+1)1,I12,I22,…,In2,I(n+1)2,…,I1k,I2k,…,Ink,I(n+1)k

若存在不足k長(zhǎng)的p長(zhǎng)子段I(n+1)1,I(n+1)2,…,I(n+1)p，則直接加到序列尾部。

頭頭連接為：

I11,I21,…,In1,I12,I22,…,In2,…,I1k,I2k,…,Ink,I(n+1)1,I(n+1)2,…,I(n+1)p

該文認(rèn)為折疊洗牌算法不受時(shí)間種子的影響，均勻度和離散度高于隨機(jī)數(shù)算法，時(shí)間效率高于隨機(jī)數(shù)算法。

2.3 經(jīng)典洗牌算法與折疊技術(shù)的洗牌算法時(shí)間效率分析

哈希算法在生成隨機(jī)序列的時(shí)候，每生成一個(gè)隨機(jī)數(shù)之前，都會(huì)進(jìn)行一次沖突檢測(cè)，假設(shè)當(dāng)前檢測(cè)的序列長(zhǎng)度為n，那么每一次檢測(cè)所消耗的時(shí)間平均量為n/2。如果要保證每次添加的隨機(jī)數(shù)都不重復(fù)，則需要做n次檢測(cè)，其時(shí)間復(fù)雜度為：

(1)

用大O法表示即為O(n2)。

Guid算法的核心在于用微軟的Guid標(biāo)準(zhǔn)生成一個(gè)全球唯一的128位數(shù)字，并將其作為Rand()函數(shù)的種子，來(lái)生成一個(gè)不重復(fù)的數(shù)。由于Guid屬于微軟內(nèi)部實(shí)現(xiàn)的功能，這里無(wú)法對(duì)其時(shí)間復(fù)雜度進(jìn)行直接評(píng)價(jià)，于是將其所在函數(shù)GetRandNumber()的時(shí)間復(fù)雜度記為m。那么整體算法的時(shí)間復(fù)雜度可以視為：

O(n)=n+mn

(2)

而基于折疊技術(shù)的洗牌算法由于只是將原始數(shù)據(jù)序列分割成n段，有n段重新組合生成新的目標(biāo)序列，所以其總體時(shí)間復(fù)雜度為：

O(n)=n

(3)

顯然，相比前兩種經(jīng)典的算法，從理論上看，基于折疊技術(shù)的洗牌算法的時(shí)間復(fù)雜度更小，運(yùn)行速度相對(duì)更快，效率更高。

3 洗牌算法評(píng)價(jià)因子

均勻度和離散度是衡量抽樣算法數(shù)據(jù)分布的2個(gè)指標(biāo)。

設(shè)樣本分成n段，每段長(zhǎng)度為k。

3.1 均勻度

設(shè)：

3.2 離散度

設(shè)有n個(gè)樣本：I1,I2,…,In

4 仿真實(shí)驗(yàn)

該文對(duì)上面提到的3種洗牌算法從時(shí)間效率、均勻度、離散度進(jìn)行比較，從而證明基于折疊技術(shù)的洗牌算法的優(yōu)越性。

4.1 數(shù)據(jù)準(zhǔn)備

應(yīng)用C#語(yǔ)言開(kāi)發(fā)出實(shí)驗(yàn)程序，實(shí)驗(yàn)系統(tǒng)設(shè)置樣本總數(shù)、最大分割段數(shù)、循環(huán)次數(shù)和均勻度及離散度分析時(shí)的分段數(shù)。在折疊方式可采用單向折疊和隨機(jī)雙向折疊，根據(jù)系統(tǒng)產(chǎn)生的隨機(jī)數(shù)決定每個(gè)分段的折疊方向。同時(shí)在最大分段數(shù)的范圍內(nèi)，可采用固定分段和隨機(jī)分段的方式進(jìn)行，通過(guò)各項(xiàng)功能的設(shè)置，提高了實(shí)驗(yàn)程序的靈活性，滿足不同的實(shí)驗(yàn)需要。

4.2 實(shí)驗(yàn)過(guò)程與結(jié)果

(1)算法時(shí)間效率對(duì)比分析。

對(duì)Hash算法、Guid算法、折疊技術(shù)3種洗牌算法進(jìn)行時(shí)間效率對(duì)比分析，樣本數(shù)量從1 000到10 000，增量為1 000，對(duì)比結(jié)果如表1所示，對(duì)比圖如圖1所示。

圖1 算法時(shí)間效率分析

表1 算法時(shí)間效率分析

(2)離散度對(duì)比分析。

對(duì)Hash算法、Guid算法、折疊技術(shù)3種洗牌算法進(jìn)行離散度對(duì)比分析，樣本數(shù)量為1 000，分段數(shù)量為50段，循環(huán)次數(shù)從10到50，對(duì)比結(jié)果如表2所示，對(duì)比圖如圖2所示。

表2 基于循環(huán)次數(shù)變化的離散度對(duì)比

圖2 基于循環(huán)次數(shù)變化的離散度對(duì)比

對(duì)Hash算法、Guid算法、折疊技術(shù)3種洗牌算法進(jìn)行離散度對(duì)比分析，樣本數(shù)量為1 000，分段數(shù)量為10～50段，循環(huán)次數(shù)20，對(duì)比結(jié)果如表3所示，對(duì)比圖如圖3所示。

表3 基于分段數(shù)變化的離散度對(duì)比

圖3 基于分段數(shù)變化的離散度對(duì)比

(3)均勻度對(duì)比分析

對(duì)Hash算法、Guid算法、折疊技術(shù)3種洗牌算法進(jìn)行離散度對(duì)比分析，樣本數(shù)量為1 000，分段數(shù)量為50段，循環(huán)次數(shù)從10到50，對(duì)比結(jié)果如表4所示，對(duì)比圖如圖4所示。

表4 基于循環(huán)次數(shù)變化的均勻度對(duì)比

圖4 基于循環(huán)次數(shù)變化的均勻度對(duì)比

對(duì)Hash算法、Guid算法、折疊技術(shù)3種洗牌算法進(jìn)行離散度對(duì)比分析，樣本數(shù)量為1 000，分段數(shù)量為10～50段，循環(huán)次數(shù)20，對(duì)比結(jié)果如表5所示，對(duì)比圖如圖5所示。

表5 基于分段數(shù)變化的均勻度對(duì)比

圖5 基于分段數(shù)變化的均勻度對(duì)比

4.3 結(jié)果分析

(1)算法時(shí)間效率對(duì)比分析。

從實(shí)驗(yàn)結(jié)果來(lái)看，折疊洗牌算法從時(shí)間效率來(lái)看遠(yuǎn)遠(yuǎn)優(yōu)于Hash算法和Guid算法，這與理論分析一致，從而證明折疊洗牌算法具有時(shí)間效率優(yōu)越性。

(2)離散度分析。

從離散度因子定義來(lái)看，離散度越大，說(shuō)明數(shù)據(jù)離散的好，實(shí)驗(yàn)結(jié)果表明，當(dāng)分段數(shù)大于等于40，循環(huán)次數(shù)小于等于30時(shí)，折疊洗牌算法具有明顯的優(yōu)勢(shì)，同時(shí)也看到分段數(shù)與循環(huán)次數(shù)的變化對(duì)Hash算法和Guid算法的離散度改變不大，幾乎沒(méi)有影響。

(3)均勻度分析。

從均勻度因子定義來(lái)看，均勻度越小，說(shuō)明數(shù)據(jù)離散的好，實(shí)驗(yàn)結(jié)果表明，當(dāng)分段數(shù)小于等于50，循環(huán)次數(shù)小于等于40時(shí)，折疊洗牌算法具有明顯的優(yōu)勢(shì)。

(4)綜合評(píng)價(jià)。

從時(shí)間效率來(lái)看，折疊洗牌算法遠(yuǎn)遠(yuǎn)優(yōu)于Hash算法和Guid算法；綜合離散度和均勻度2因素，當(dāng)分段數(shù)在[40，50]區(qū)間，循環(huán)次數(shù)在[10，30]區(qū)間時(shí)，折疊洗牌算法具有非常好的效果。同時(shí)也要注意到：分段數(shù)與循環(huán)次數(shù)的變化對(duì)Hash算法和Guid算法的離散度幾乎沒(méi)有影響，這也是基于隨機(jī)技術(shù)的致命缺點(diǎn)。

通過(guò)實(shí)驗(yàn)表明，當(dāng)樣本數(shù)為1 000，分段數(shù)為50，循環(huán)次數(shù)為20時(shí)，效果最佳，也就是當(dāng)分段數(shù)為樣本總數(shù)的5%，循環(huán)次數(shù)為樣本總數(shù)的2%時(shí)，達(dá)到最佳效果。

5 結(jié)束語(yǔ)

提高大數(shù)據(jù)處理效率問(wèn)題是大數(shù)據(jù)研究的熱點(diǎn)，成熟的方案也很多，但基于抽樣技術(shù)的大數(shù)據(jù)處理方法不僅適合于靜態(tài)數(shù)據(jù)處理，也適合流式數(shù)據(jù)處理。一個(gè)好的大數(shù)據(jù)洗牌算法能保證抽樣樣本的可用性。該文從生活中的撲克洗牌算法得到啟示，提出一種大數(shù)據(jù)洗牌算法，算法原理簡(jiǎn)單，易于實(shí)現(xiàn)，從實(shí)驗(yàn)結(jié)果來(lái)看，當(dāng)樣本分段數(shù)為樣本總數(shù)的5%，循環(huán)次數(shù)為樣本總數(shù)的2%時(shí)，具有最佳效果，明顯優(yōu)于其他基于隨機(jī)技術(shù)的常規(guī)算法。