李 慶，劉涵閱，張春生

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

0 引 言

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

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

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

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

1 基于隨機序列的洗牌算法

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

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

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

算法如下：

Hashtable hashtable=new Hashtable();

Rand() rm=new Rand() ;

int RmNum=N;//N為隨機數(shù)個數(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)識符[15]，在理想情況下，任何計算機和計算機集群都不會生成兩個相同的Guid值，一般表示成32個16進制數(shù)字(0-9，A-F)組成的字符串，它實質(zhì)上是一個128位長的二進制整數(shù)。

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

算法如下：

private void btn_jdsjxp_Click(object sender, EventArgs e)

{

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

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

int k; //隨機下標(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

//開始對所有樣本循環(huán)

{

k=GetRandNumber(0, i_ybzs-1);

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

yb_d[i]=yb_s[k];

}

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

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

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

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

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

例如n+1段k長樣本段的頭頭連接方法如下：

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長的p長子段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ù)算法，時間效率高于隨機數(shù)算法。

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

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

(1)

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

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

O(n)=n+mn

(2)

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

O(n)=n

(3)

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

3 洗牌算法評價因子

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

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

3.1 均勻度

設(shè)：

3.2 離散度

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

4 仿真實驗

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

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

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

4.2 實驗過程與結(jié)果

(1)算法時間效率對比分析。

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

圖1 算法時間效率分析

表1 算法時間效率分析

(2)離散度對比分析。

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

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

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

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

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

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

(3)均勻度對比分析

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

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

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

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

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

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

4.3 結(jié)果分析

(1)算法時間效率對比分析。

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

(2)離散度分析。

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

(3)均勻度分析。

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

(4)綜合評價。

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

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

5 結(jié)束語

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