結合大數據流特征和改進SOM聚類的資源動態分配算法

項麗萍 楊紅菊

1(晉城職業技術學院信息工程系 山西 晉城 048000)2(山西大學計算機與信息技術學院 山西 太原 030006)

0 引 言

現階段，物聯網和人們的生活越來越密切，物聯網設備可以隨機生成數據，這種隨機性會導致具有未知特性的大數據流的產生[1]。這些大數據通常由多樣性的圖像、視頻、音頻和文本等數據組成。大數據流的數據特性包括4V：體積(Volume)、速度(Velocity)、類型(Variety)和可變性(Variability)。

隨著大數據流的增加，如何實時分析大數據是一個難題。使用最多的是基于云計算的大數據分析法，通過選擇合適的云資源來分析數據特性已成為熱門研究問題[2-3]。文獻[4]強調了動態資源配置是大數據應用程序調度中的一個具有挑戰性的問題。文獻[5]提出了一個基于QoS的框架實現大數據中的最優資源分配。該框架的功能和QoS要求由用戶提供。功能要求包括處理能力、GPU功率、RAM和輸入數據的大小等；QoS要求包括響應時間、輸出數據質量和結果可視化。根據功能和QoS要求，使用樸素貝葉斯算法確定所需云群。文獻[6]提出一種基于圖的大數據資源處理方法，可以在不影響響應時間的情況下提高數據處理效率。文獻[7]提出了一種基于優先級的多媒體數據處理方法，該方法是靜態混合算法。文獻[8]使用馬爾可夫鏈和分配的節點有效地預測了大數據的大小以進行數據處理。但是該模型沒有考慮大數據資源分配的高速性、多樣性和可變性。文獻[9]強調云數據中心的可變性會影響云資源的分配。文獻[10]表明了預測大數據請求的速度對有效配置云資源至關重要。以上研究表明，流式大數據的4V特性是云資源分配的重要參數。

因此，本文提出了一種大數據環境下結合數據特征預測和智能聚類的資源管理算法。其主要創新點在于：(1) 根據現有數據的體積、速度的變化情況，對下一時刻數據的特征進行估計。(2) 利用自組織映射SOM和粒子群優化PSO相結合，構建一種先進的聚類算法，根據估計的數據特征對數據進行聚類，用來分配合理資源。

1 算法流程

本文提出的算法旨在基于數據特性(4V)為大數據流分配適當的資源。為了實現該目標，算法分為兩步，如圖1所示。

圖1 本文算法框架

1) 首先從輸入流中提取小塊數據，塊大小是底層存儲系統(例如HDFS的默認塊大小為64 MB)的一個整數倍，這樣可減少讀取和分析數據的開銷。分析所選數據塊，根據現有數據特征來估計下一時刻數據流的體積和速度。在估計這些值時，會考慮數據的可變性。估計值用數據特征(CoD)向量表示。

2) 利用PSO優化SOM算法的權值分布，構建一種改進型SOM算法，用于對CoD向量進行聚類，動態創建和分配空閑的云資源集群。

在r個時間單位之后，使用自適應采樣技術[11]選擇另一個塊，其中，r取決于采樣率。這種機制允許算法在早期捕獲新到達數據流的變化性，從而分配適當的集群。接著，算法自動調整采樣率大小，這個過程中涉及到遷移開銷[12]。如果遷移開銷很高，r的值會增加，如果執行時間很長，則r的值會降低。對采樣的數據塊再次進行分析，并使用上述步驟分配資源。

2 數據特性的估計

為了估計數據特征，通過四個階段進行操作：第一階段，確定數據類型；第二階段，使用數據可變性估計數據的體積和速度；第三階段，計算相對體積和速度，即將這些估計值與其他到達云端的數據請求進行比較，并計算相對的體積和速度；第四階段，相對值的有效表示。下面給出詳細的步驟。

2.1 數據類型確定

目前，數據分析主要有四種類型[13]，分別是文本分析、圖像分析、音頻分析和視頻分析。本文使用Bloom過濾器[14]來確定數據的類型。Bloom過濾器的組成包括：(1) 一個n位的序列，初始值均為0；(2)k個哈希函數的集合h1,h2,…,hk；(3)m個鍵值組成的集合S。每個哈希函數將鍵值映射到n個塊中，對應于n個數組。Bloom過濾器的目的是允許S中的流元素通過，拒絕其他元素。

令p表示可接受的假陽性率，則n和k的值可由式(1)和式(2)計算得到：

(1)

(2)

Bloom過濾器的工作流程如算法1所示。

算法1Bloom過濾器的工作流程

輸入： 數組BF[n]，集合S，哈希函數h1,h2,…,hk

輸出： 特定類型的數據e

1. 初始化BF[1],…,BF[n]=0；2. 對于每個鍵值yi∈S

計算h1(yi),…,hk(yi)；

設置BF[hj(yi)]=1,1≤j≤k；

3. 對每個經過過濾器的流元素e

計算h1(e),…,hk(e)；

對于所有j，如果BF[hj(e)]=1

允許e通過濾波器并輸出；

4. 退出

在本文所提出的算法中，使用四個Bloom過濾器。第一個過濾器僅允許圖像類數據通過，并阻擋其他類型的數據。類似地，第二、第三和第四過濾器分別允許音頻、視頻和文本數據通過。

這里，一個特定Bloom過濾器的集合S由所有可能的數據格式組成。例如，在第一個過濾器中設置S包含所有圖像格式，如jpeg、png等。第二個過濾器中的集合S由所有音頻格式組成，如mp3、wav、aiff等。用同樣的方式構造另外兩個過濾器的S集合。因此，m的值等于S中n和k的總和。

在數據加入塊中時，計算塊中的數據的體積和速度的絕對值。設ρt(I)和ut(I)為t時刻圖像數據的絕對體積和速度，這些值開始時均為零。每次將圖像數據添加到其相應的存儲塊中時，都會使用式(3)和式(4)更新數據體積和速度值。其中，δ表示在一個時間點通過過濾器的數據的體積量。

ρt(I)=ρt(I)+δ

(3)

ut(I)=ut(I)+1

(4)

類似地，音頻數據的體積為ρt(A)，音頻數據的速度為ut(A)，視頻數據的體積為ρt(V)，視頻數據的速度為ut(V)，文本數據的體積為ρt(T)，文本數據的速度為ut(T) 。這些值根據它們各自的塊進行計算。在第二階段中，將使用這些值來估計第(t+1)時刻數據的體積和速度。

2.2 利用自回歸模型預測體積和速度

數據流可能不具有周期性峰值。比如，當社交媒體上發生某些事情時，可能會導致在特定時間段內大量高速生成數據。因此，在估計下一個時間間隔內到達的數據體積和速度的過程中，可變性有著重要的影響。為了減小可變性的影響，本文采用自回歸模型[15]。自回歸模型使用預測變量的線性組合來預測變量的值。

(5)

(6)

其中：

(7)

(8)

式中:cov()和var()分別代表協方差和方差。同樣，使用自回歸模型計算音頻、視頻和文本數據的預測體積和速度。

2.3 計算相對體積和速度

本文并沒有對大數據作一個具體的定義，因此，第二階段的體積和速度的預測值需要與其他到達云數據中心的數據請求進行比較。比較后得到的值稱為相對體積和速度。以下討論圖像數據的相對體積和速度的計算。音頻、視頻和文本數據的計算與圖像類型的計算方式類似。

(9)

(10)

式中：函數round(num，num_digit) 表示將數字num 四舍五入到具有num_digit位小數的數。本文中，將體積等于max(ρt(I))的大數據流的相對體積設置為1。這意味著相對體積的最大值是1。與之對應的，相對體積的最小值是零。因此，式(9)的取值范圍為[0,1] 。此外，由于式(9)的結果四舍五入到小數點后一位，所以{0,0.1,0.2,…,0.9,1}是相對體積的可能值的集合。相對速度的計算與相對體積類似。

2.4 預測值的CoD表示

在云資源的分配中，有必要以一種特殊的形式表示預測的4V值。本文中將數據的相對體積和速度預測值進行整合，形成數據強度度量。例如，圖像數據的強度φ(I)可以使用式(11)計算得到。

φ(I)=ρ″t+1(I)·u″t+1(I)

(11)

音頻、視頻和文本數據的強度也根據該等式進行計算。由于ρ″t+1()和u″t+1()的范圍都在[0,1]之間，所以強度的取值范圍也是[0,1]。

在獲得圖像、音頻、視頻和文本數據的強度之后，用數據特征(CoD)矢量的形式來表示它們。CoD的定義為：CoD=(φ(I),φ(A),φ(V),φ(T))。

3 基于改進SOM聚類的資源管理

3.1 PSO改進SOM聚類

傳統的聚類算法如K_meas等，往往需要事先定義聚類數目。通常基于經驗知識來確定類別個數，而且一般需要多次嘗試，這種方法具有很大的盲目性。

在本文資源聚類應用中，需要根據數據流特征來分配合適類型的資源，如果事先定義資源類型數量則不能適應數據流的變化。為此，本文采用了SOM聚類算法，利用SOM的可視化功能來動態確定聚類數目，避免傳統聚類算法確定聚類數目的盲目性。SOM是用于聚類分析的無監督神經網絡學習技術之一[16]。初始時將每個資源都作為一個聚類，通過計算資源與數據流的距離來動態聚類，以此為每個數據流分配最佳資源。SOM由輸入層和輸出層組成，其結構如圖2所示。

圖2 SOM映射網絡

利用SOM進行聚類分析可分為以下幾步：

初始化參數：輸入、輸出神經元個數n、m，當前迭代次數t，最大迭代次數T，初始權值Wij(1)，學習速率因子ψ(1)，鄰域半徑N(1)。

(1) 對SOM中神經元的初始權值Wij(1)進行歸一化，使權值的范圍處在(0,1)之間。

(2) 計算訓練樣本和輸出層神經元間的距離值，計算公式如下：

(12)

(3) 找出距離最小值對應的輸出層神經元，將它定義為獲勝神經元j：

(13)

(4) 調整獲勝神經元的權值：

Wij(t+1)=Wij(t)+ψ(t)(xi-Wij(t))

(14)

(5) 按照式(15)更新獲勝神經元的鄰域以及SOM的學習速率。

(15)

(6) 如果滿足以下所列條件中的任意一個，則SOM算法結束，輸出聚類結果。①ψ(t)的值下降為0；②t=T。否則，t=t+1，返回到步驟(2)重復執行。

雖然SOM算法的樣本學習更加精確，并且收斂速度能夠滿足多數情況下的要求，但SOM算法的收斂效果與權值的初始分布有著密切的關系。本文利用PSO算法優化SOM算法的權值，以增強收斂效果。

在PSO算法中，候選解通常用粒子來表示。在一個D維空間中，令粒子的位置P、速度V表示如下：

(16)

在PSO算法的迭代過程中，粒子根據個體最優值和全局最優值更新自身的位置xi(t+1)和速度vi(t+1)：

(17)

式中：w表示慣性權重；c1和c2表示學習因子，它們的取值范圍是(1,2)；λ1和λ2是兩個在(0,1)之間的常數；pbsti和gbsti分別表示個體最優粒子和全局最優粒子。

基于PSO優化SOM的具體步驟如下：

(1) 粒子位置編碼表示為：

P={w11,w12,…,w1m…wn1,…,wnm}

(18)

式中:m表示資源聚類數目，對應于SOM算法中的輸出神經元個數；n表示資源屬性數目，對應于SOM算法中的輸入神經元個數。

(2) 根據式(17)更新粒子的位置xi(t+1)和速度vi(t+1)。

(3) 計算粒子的適應度值，找出個體最優粒子pbsti和全局最優粒子gbsti。適應度值的計算式為：

(19)

式中：i表示樣本，j表示i相對應的獲勝神經元，Dij(t)表示i和j之間的距離。

(4) 當得到的全局最優粒子gbsti變化時，返回步驟(2)中重復執行操作，直到gbsti不再發生變化。

3.2 動態集群生成及資源分配

在本文提出的算法中，將特征預測步驟中得到的CoD向量作為輸入向量，輸入到改進SOM中進行聚類，如算法2所示。聚類過程從權重W和學習速率因子ψ的初始化開始，利用PSO初始化SOM的權值初始分布。SOM隨機選擇一個資源向量(Si)，并從每個CoD向量中計算與它的距離。具有最小距離的CoD向量(CJ)稱為獲勝向量，并將資源Si分配到CoD向量CJ對應的數據流。每個資源都會重復該過程，所有獲勝向量為CJ的資源稱為一個集群。

算法2利用改進SOM生成動態集群

1. 利用PSO初始化SOM的權值初始分布；

2. 將學習速率因子ψ定義為略小于1的值；

3. 重復3-9，直至計算邊界不滿足條件；

4. 對于每個輸入資源向量Si，重復步驟6-8；5. 對于每個輸出神經元j，根據下式計算S的歐氏距離的平方：

6. 選擇D(j)最小的j；

7. 設置聚類特征CoC(Si)=CoD(Cj) ；

8. 根據下式更新j的所有拓撲鄰居的權值：

Wjk(t+1)=(1-ψ)Wjk(t)+ψ(t)Sk；

9.ψ單調遞減；

10. 基于各自的CoC輸出虛擬聚類；

集群形成后，使用具有CoC=CoD屬性的集群來為數據流分配資源。如果選擇的集群有足夠的資源來處理數據流，則分配該集群。否則，搜索并分配具有足夠資源，且最近的拓撲有序集群，這么做可以減小數據流的等待時間。

4 實驗分析

實驗中分為兩個步驟，即數據流的特征估計和資源分配。其中，在PC機上通過Java編程實現自回歸模型，對下一時間間隔到達的數據的特征進行估計。在第二個步驟中，使用AWS SDK for Java工具，在Amazon Web Services云平臺上開發和部署Java應用程序，連接Amazon彈性計算云 EC2中的計算資源，實現資源分配。實驗分為兩個部分，即預測分析和算法對比分析。

4.1 實驗數據集

生成四個容量較大的數據集。第一個數據集是由86 280個圖像組成的圖像數據集，第二個數據集是一個音頻集合，包含1 568首音樂曲目，第三個數據集是一個包含32小時視頻的監控視頻數據集。第四個數據集是一個由1 000萬個單詞組成的文本數據集。使用這四個數據集創建一個數據庫，該數據庫滿足以下特征：

(1) 它由12%的圖像數據，21%的音頻數據，24%的視頻數據和43%的文本數據組成。

(2) 圖像數據在數據集前部時的體積較小，當它越靠近數據集尾部時，體積逐漸增大。

(3) 音頻數據在數據集前部中的體積很大，而在數據集的末端有所下降。

(4) 視頻數據的體積先下降然后增加。

(5) 文本數據的體積在整個數據集中保持均勻，幾乎不變。

將數據庫中的數據以流的形式輸入到算法中，時間為1小時。其中圖像、音頻、視頻和文本數據的速度遵循以下模式：

(1) 圖像數據的速度先下降然后隨時間增加，使其形成流的整體速度的19%。

(2) 音頻數據的速度隨時間減小，使其形成流的整體速度的23%。

(3) 視頻數據的速度隨時間增加，使其形成流的整體速度的22%。

(4) 文本數據的速度幾乎保持不變，使其形成流的整體速度的36%。

4.2 數據流體積和速度的預測

將數據流的實際值與本文算法的預測值進行比較，結果如表1和表2所示。本次實驗中，以0.5個樣本/min的恒定采樣頻率進行采樣。

表1 數據流體積的實際值與本文算法的預測值比較 GB

表2 數據流速度的實際值與本文算法的預測值比較 數據流量數量/min

從表1和表2可以看出，四種數據集的實際值與預測值之間的差異很小。圖3為四種數據類型的數據流體積和速度預測的平均絕對預測誤差(MAPE)。

圖3 平均絕對預測誤差

從圖3可以看出，MAPE隨著數據占比的增加而減少。如上文所述，數據流由12%的圖像數據，21%的音頻數據，24%的視頻數據和43%的文本數據組成，而預測圖像、音頻、視頻和文本數據體積的MAPE分別為0.247、0.216、0.172和0.123。圖像數據占比是最小的，但它的MAPE是最高的；文本數據的占比是最大的，而它的MAPE是最低的。因此，對于占比更高的數據類型，其MAPE會更低，并且這一數值隨著數據占比的減少而增加。從數據速度的角度上可以觀察到類似的現象，這符合大數定律，也就是說，誤差隨著數據大小的增加而減小。

從以上結果可知，本文算法能有效地預測圖像、音頻、視頻和文本數據的體積和速度。

4.3 算法對比

將本文提出的算法與文獻[5]提出的基于QoS的資源管理算法、文獻[8]提出的基于馬爾可夫鏈的資源分配算法進行實驗比較。本次實驗中生成具有不同體積和速度占比的5個大數據流集，流生成的過程與第4.1節相同。表3為5個數據流集中各種數據的體積和速度的占比，每隔十分鐘將一個流送入算法中。

表3 生成的流中不同數據的體積和速度的百分比

分別使用上述三種算法，從Amazon彈性計算云 Elastic Compute Cloud(EC2)中選擇虛擬機(VM)作為資源，分配給適當的數據流。本文中選擇10個VM實例來進行資源管理，每個實例都來自于EC2中針對計算密集型工作負載優化的c4.large實例，配備2.9 GHz Intel Xeon E5-2666 v3 處理器。虛擬機處理生成的流，并在每個流上運行Alon-Matias-Szegedy(AMS)算法。AMS用于確定流中不同元素的頻率。整個實驗的執行時間為一個小時。

圖4為三種算法的資源利用率的變化。在文獻[5]提出的基于QoS的算法中，算法的處理能力、GPU功率、RAM和輸入數據的大小由用戶提供。這些用戶需求用于為輸入請求分配資源。用戶需求取決于數據特征，在大數據流的情況下，用戶通常不知道數據特征。因此，在基于QoS的方法中，用戶可能無法為大數據流確定合適的資源，并且數據流在整個時間段內運行在相同的資源上。文獻[8]提出的算法能有效地預測數據流的大小，以選擇合適資源來處理數據，但是算法沒有考慮大數據資源分配的高速性、多樣性和可變性等因素。本文提出的算法能夠預測流的4V，并且能夠隨流中數據的特征變化恰當的分配資源。因此，在圖4中，與文獻[5]、文獻[8]提出的算法相比，本文提出的算法資源利用率更高。

圖4 資源利用率

圖5為三種算法的整體執行延遲的比較。在文獻[5]算法中，整個執行期間執行延遲幾乎相同，只是在實驗結束時執行延遲略有增加。這是因為隨著更多流添加到算法中，算法所需集群的不可用的概率逐漸增加(所請求的資源可能已被其他流所占用)，因此，算法需要更多的時間尋找可用且最近的拓撲有序集群。在文獻[8]算法中，執行延遲隨著執行時間的增加慢慢增大。在本文提出的算法中，實驗開始時，執行延遲較高，這是因為本文算法在分配適當集群之前就預測了流的CoD，這就減少了執行延遲，并且使合適資源可以更快地處理數據流。此外，從圖5可以看出，自從10 min后在系統中添加新流時，每隔10 min執行延遲會出現周期性峰值。這是因為，新流添加后需要重新計算所有流的CoD，這就導致執行延遲的周期性增加。盡管如此，本文提出算法的整體執行延遲小于其余兩種算法。

圖5 執行延遲

圖6為三種算法的的響應時間比較。本文提出的算法的響應時間在整個實驗中幾乎保持相同。這是因為無論數據流中的數據特征發生何種變化，在本文提出的算法中始終能找到更合適的資源集群來處理該數據流，這帶來了穩定的響應時間。對于文獻[5]算法，在整個執行時間段內，無論數據特性如何變化，流始終在相同的資源上運行，響應時間就會隨著執行時間而增加。文獻[8]算法僅僅根據數據流的大小來調整資源，沒有考慮資源速度的可變性，所分配的資源不一定最合適。

圖6 響應時間

5 結 語

本文提出了一種高效的大數據流資源管理算法。所提出的算法基于數據特性的預測來分配合適資源，從而高效的處理數據流。這種分配方式可以隨著數據特性改變做出調整，使對數據流的響應時間保持穩定。此外，由改進型SOM形成的簇的拓撲排序可以減少了流的等待時間。實驗結果表明，和常用的分配算法相比，本文提出的算法能有效提高云資源的利用率。