基于折疊技術的大數據樣本洗牌算法研究

李 慶，劉涵閱，張春生

(內蒙古民族大學 計算機科學與技術學院，內蒙古 通遼 028043)

0 引 言

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

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

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

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

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

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

1.1 基于哈希技術的洗牌算法

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

算法如下：

Hashtable hashtable=new Hashtable();

Rand() rm=new Rand() ;

int RmNum=N;//N為隨機數個數

for (int i=0;hashtable.Count

{

int nValue=rm.Next(100);

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

{

hashtable.Add(nValue, nValue);

}

}

1.2 基于Guid技術的洗牌算法

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

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

算法如下：

private void btn_jdsjxp_Click(object sender, EventArgs e)

{

int i_ybzs; //樣本總數

int i; //設置樣本循環變量

int k; //隨機下標

i_ybzs=int.Parse(tb_ybs.Text);

//樣本總數轉換為整

int[] yb_s=new int[i_ybzs];

//定義原始樣本序列

int[] yb_d=new int[i_ybzs];

//定義目標樣本序列

for(i=0;i

//初始化樣本序列

{

yb_s[i]=i+1;

yb_d[i]=0;

}

for(i=0;i

//開始對所有樣本循環

{

k=GetRandNumber(0, i_ybzs-1);

//隨機選擇不重復樣本下標

yb_d[i]=yb_s[k];

}

2 基于折疊技術的洗牌算法

2.1 基于折疊技術的洗牌算法的優勢

鑒于隨機抽樣算法受到時間種子的影響，采樣分布不夠均勻，而折疊洗牌算法模仿撲克牌的洗牌原理，進行多次分段均勻組合，算法的分布不受隨機數限制，全程均勻分布，同時由于不進行重復數判斷，所以，無論從數據分布還是時間效率上都應比隨機抽樣算法優越。

2.2 折疊技術的洗牌算法描述

基于折疊洗牌技術的采樣算法基本原理是，折疊洗牌算法模擬撲克的洗牌過程，設樣本總數為n*k+p，其中p和k代表段長，p≤k。當p=k時，n*k+p=(n+1)*k，數據分n+1段；當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

該文認為折疊洗牌算法不受時間種子的影響，均勻度和離散度高于隨機數算法，時間效率高于隨機數算法。

2.3 經典洗牌算法與折疊技術的洗牌算法時間效率分析

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

(1)

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

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

O(n)=n+mn

(2)

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

O(n)=n

(3)

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

3 洗牌算法評價因子

均勻度和離散度是衡量抽樣算法數據分布的2個指標。

設樣本分成n段，每段長度為k。

3.1 均勻度

設：

3.2 離散度

設有n個樣本：I1,I2,…,In

4 仿真實驗

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

4.1 數據準備

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

4.2 實驗過程與結果

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

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

圖1 算法時間效率分析

表1 算法時間效率分析

(2)離散度對比分析。

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

表2 基于循環次數變化的離散度對比

圖2 基于循環次數變化的離散度對比

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

表3 基于分段數變化的離散度對比

圖3 基于分段數變化的離散度對比

(3)均勻度對比分析

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

表4 基于循環次數變化的均勻度對比

圖4 基于循環次數變化的均勻度對比

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

表5 基于分段數變化的均勻度對比

圖5 基于分段數變化的均勻度對比

4.3 結果分析

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

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

(2)離散度分析。

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

(3)均勻度分析。

從均勻度因子定義來看，均勻度越小，說明數據離散的好，實驗結果表明，當分段數小于等于50，循環次數小于等于40時，折疊洗牌算法具有明顯的優勢。

(4)綜合評價。

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

通過實驗表明，當樣本數為1 000，分段數為50，循環次數為20時，效果最佳，也就是當分段數為樣本總數的5%，循環次數為樣本總數的2%時，達到最佳效果。

5 結束語

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