基于最優(yōu)K 均值聚類算法的負(fù)荷大數(shù)據(jù)任務(wù)均衡調(diào)度研究

白雨佳，李靖，高升

（1.國(guó)網(wǎng)內(nèi)蒙古東部電力有限公司信息通信分公司，呼和浩特 010020；2.中國(guó)科學(xué)院沈陽(yáng)計(jì)算技術(shù)研究所有限公司，沈陽(yáng) 110000）

0 引言

由于因特網(wǎng)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)中共享的資源越來(lái)越多，資源的種類越來(lái)越多，各種資源被廣泛引用，如何有效地傳輸多源數(shù)據(jù)成為相關(guān)學(xué)者亟待解決的重要問題，傳統(tǒng)的多源大數(shù)據(jù)在進(jìn)行預(yù)取時(shí)，往往會(huì)出現(xiàn)多個(gè)節(jié)點(diǎn)輸出相同結(jié)果的情況，從而導(dǎo)致資源競(jìng)爭(zhēng)現(xiàn)象的發(fā)生[1]。為避免出現(xiàn)上述問題，迫切需要研究多源大數(shù)據(jù)均衡調(diào)度的新方法?？缭促Y源調(diào)度方法是一種有效的調(diào)度方法[2-3]得到了人們的廣泛關(guān)注。

為此，王慧等人[4]提出了基于小波分析的大數(shù)據(jù)調(diào)度方法，該方法通過(guò)小波分析對(duì)電力大數(shù)據(jù)去噪后，以去噪數(shù)據(jù)完成優(yōu)先級(jí)列表控制模型構(gòu)建，并完成負(fù)載均衡傳輸信道模型的建立，通過(guò)自適應(yīng)加權(quán)控制方法和時(shí)隙分配獲取最佳目標(biāo)函數(shù)，完成數(shù)據(jù)調(diào)度，但是該方法的時(shí)間開銷較大；周生奇等人[5]研究了基于灰色模糊預(yù)測(cè)的大數(shù)據(jù)調(diào)度方法。該方法采用灰色模糊預(yù)測(cè)方法完成多服務(wù)器中的流動(dòng)數(shù)據(jù)的調(diào)度，但是該方法在調(diào)度過(guò)程中，負(fù)荷大數(shù)據(jù)的均衡度不夠理想。

為確保電力負(fù)荷大數(shù)據(jù)的準(zhǔn)確調(diào)用，需進(jìn)一步明確數(shù)據(jù)的類別和數(shù)據(jù)信息，因此需劃分電力負(fù)荷數(shù)據(jù)。K 均值聚類算法為迭代求解聚類分析算法的一種，并且是應(yīng)用廣泛的劃分聚類算法，其應(yīng)用過(guò)程簡(jiǎn)潔且效率較高。因此本文選擇K 均值聚類算法對(duì)電力負(fù)荷大數(shù)據(jù)實(shí)行分類。基于此，本文研究基于最優(yōu)K 均值聚類的電力負(fù)荷大數(shù)據(jù)跨源調(diào)度方法，以期實(shí)現(xiàn)較小開銷下的電力負(fù)荷大數(shù)據(jù)調(diào)度。

1 電力負(fù)荷大數(shù)據(jù)跨源調(diào)度

1.1 基于最優(yōu)K均值聚類的電力負(fù)荷大數(shù)據(jù)分類

1.1.1 K 均值聚類算法

K 均值聚類算法的核心為：設(shè)數(shù)據(jù)對(duì)象數(shù)量為n，對(duì)其實(shí)行劃分處理，共分為k個(gè)類，使全部數(shù)據(jù)對(duì)象距離該類的聚類中心點(diǎn)平方和為最小。

設(shè)算法的輸入數(shù)據(jù)集為F={x1,x2,...,xn}，算法的輸出為k個(gè)類，即{F1,F2,...,Fk}，且保證最小平方誤差準(zhǔn)則。算法步驟如下所述：

1）設(shè)數(shù)據(jù)樣本為X，初始聚類中心cj為隨機(jī)選取的數(shù)據(jù)對(duì)象，其中j=1,2,...,k。

2）為獲取X中的各個(gè)對(duì)象xi至k個(gè)聚類中心cj的距離，計(jì)算歐式距離公式為

3）獲取cj(n+1)的值，并將其作為新聚類中心點(diǎn)[6]：計(jì)算公式為

式中，Nj為第j個(gè)類中心數(shù)據(jù)對(duì)象的數(shù)量。

4）判斷準(zhǔn)則是否滿足，若滿足，則轉(zhuǎn)至步驟2），反之轉(zhuǎn)至步驟5）。根據(jù)判斷準(zhǔn)則可知，兩次迭代獲取的聚類中心點(diǎn)相同，且聚類離散度不會(huì)再發(fā)生變化。由此可建立聚類離散度函數(shù)為

5）輸出聚類結(jié)果。

1.1.2 聚類中心優(yōu)化

上節(jié)中的K 均值聚類算法雖然可快速完成聚類，但是其聚類不是最優(yōu)結(jié)果。由于其初始聚類中心點(diǎn)是通過(guò)隨機(jī)選取K 個(gè)數(shù)據(jù)對(duì)象完成，通過(guò)迭代計(jì)算尋優(yōu)，直至符合收斂條件[7]。因此，初始中心點(diǎn)的差別會(huì)導(dǎo)致聚類結(jié)果出現(xiàn)差異性，導(dǎo)致聚類效果不穩(wěn)定、結(jié)果不是全局最優(yōu)解，甚至還會(huì)降低算法的效率。

基于上述分析，K 均值聚類算法初始中心點(diǎn)的優(yōu)化尤為重要，實(shí)現(xiàn)依據(jù)聚類對(duì)象自動(dòng)完成k值估計(jì)。K 均值聚類算法利用優(yōu)化后的最優(yōu)聚類中心完成電力負(fù)荷的分類[8]，獲取合理、準(zhǔn)確的分類結(jié)果。本文采用密度法優(yōu)化K 均值聚類算法初始中心點(diǎn)，其將初始聚類中心用k個(gè)位于高密度區(qū)域且相互距離最遠(yuǎn)的點(diǎn)表示。優(yōu)化的算法可有效抑制噪聲點(diǎn)對(duì)聚類算法的影響。

該算法在優(yōu)化過(guò)程中，需計(jì)算每一個(gè)數(shù)據(jù)對(duì)象的密度參數(shù)，并以其為標(biāo)準(zhǔn)，將選取k個(gè)值較高的對(duì)象作為初始聚類中心[9-11]。優(yōu)化后算法的計(jì)算步驟如下：

1）待處理樣本數(shù)據(jù)集合為F={x1,x2,...,xn}，k個(gè)初始聚類中心點(diǎn)為z1,z2,...,zk。

2）通式（1）對(duì)任意對(duì)象xi到聚類中心之間的歐式距離求解。

求解計(jì)算對(duì)象之間的平均距離，其計(jì)算公式為

式中，n和分別為數(shù)據(jù)對(duì)象的數(shù)量和任意兩個(gè)對(duì)象組合的總數(shù)量。

MeanDist 作為計(jì)算對(duì)象密度參數(shù)的一個(gè)關(guān)鍵量，以式（4）為依據(jù)，則任意兩個(gè)數(shù)據(jù)對(duì)象之間距離的平均值通常作為其值的選取，但在特殊條件下，可在一定范圍內(nèi)對(duì)其進(jìn)行調(diào)整[12-13]。

3）為獲取各個(gè)對(duì)象的密度參數(shù)density（p,）MeanDist 采用式（5）完成。

4）尋找密度參數(shù)最大值所對(duì)應(yīng)的數(shù)據(jù)對(duì)象，將其作為第1 個(gè)初始聚類中心，同時(shí)將該聚類中心之間距離小于MeanDist 的數(shù)據(jù)對(duì)象的密度參數(shù)從D中刪除[15]。

5）重復(fù)步驟3）和步驟4），停止條件為獲取到密度參數(shù)較大的k個(gè)數(shù)據(jù)對(duì)象為止，并將該對(duì)象作為初始聚類中心點(diǎn)[16-17]。基于密度方法優(yōu)化初始中心點(diǎn)的計(jì)算流程圖見圖1。

圖1 優(yōu)化聚類初始中心點(diǎn)流程Fig.1 Initial center point flow process of optimization clustering

1.2 電力負(fù)荷大數(shù)據(jù)跨源調(diào)度

1.2.1 關(guān)聯(lián)特征提取

基于電力負(fù)荷大數(shù)據(jù)聚類結(jié)果，結(jié)合基于權(quán)重的跨源調(diào)度方法，對(duì)聚類后的電力負(fù)荷大數(shù)據(jù)實(shí)行跨源調(diào)度[18]，獲取電力大數(shù)據(jù)跨域調(diào)度的輸出特征量為

資源調(diào)度負(fù)載均衡特征向量在支持向量機(jī)學(xué)習(xí)模式下可表示為

式中，Wu,i和Wu,j分別為分類得到的數(shù)據(jù)輸入集和數(shù)據(jù)聚類中心的電力負(fù)荷大數(shù)據(jù)評(píng)價(jià)矩陣[21]，則電力負(fù)荷大數(shù)據(jù)分布集的優(yōu)化關(guān)聯(lián)特征為

1.2.2 大數(shù)據(jù)跨源調(diào)度輸出

在支持向量機(jī)學(xué)習(xí)模式下，利用自適應(yīng)權(quán)重學(xué)習(xí)方法完成電力負(fù)荷大數(shù)據(jù)跨源調(diào)度的尋優(yōu)控制[22-23]。電力負(fù)荷大數(shù)據(jù)跨源調(diào)度的主特征決策樹用四元組(Ei,Ej,q,t)表示，其中，電力負(fù)荷大數(shù)據(jù)在有向圖中的分岔節(jié)點(diǎn)分別為Ei和Ej，獲取電力負(fù)荷大數(shù)據(jù)的差異化融合特征量，其公式為

式中：m為電力負(fù)荷大數(shù)據(jù)分布的有限數(shù)據(jù)集；(qik)為相似度分布映射[24]。電力負(fù)荷大數(shù)據(jù)的相似度分布映射計(jì)算公式為

對(duì)電力負(fù)荷大數(shù)據(jù)實(shí)行優(yōu)化調(diào)度和挖掘處理[25-32]，則獲取電力負(fù)荷大數(shù)據(jù)調(diào)度均衡的輸出模型，其公式為

根據(jù)上述步驟，完成電力負(fù)荷大數(shù)據(jù)的跨源調(diào)度處理模型構(gòu)建。

2 實(shí)例分析

為測(cè)試本文方法的應(yīng)用性能，選取某電網(wǎng)企業(yè)中1 000 個(gè)不同用戶，將這些用戶按照每天每時(shí)的用電負(fù)荷按照由低到高排列，具體數(shù)據(jù)見表1，數(shù)據(jù)單位為kW·h。

表1 用戶用電日負(fù)荷數(shù)據(jù)Table 1 Daily load data of power consumption of user kW·h

聚類的類別數(shù)k的取值對(duì)于負(fù)荷大數(shù)據(jù)分類的結(jié)果存在較大影響，因此需確定最佳k值，測(cè)試不同k值時(shí)，聚類結(jié)果見圖2。

圖2 測(cè)試結(jié)果Fig.2 Test result

根據(jù)圖2 的測(cè)試結(jié)果可知：當(dāng)k值達(dá)到4 以后，聚類離散度平穩(wěn)不再發(fā)生變化，因此，為保證電力負(fù)荷大數(shù)據(jù)分類結(jié)果準(zhǔn)確，k值取值為4，下述實(shí)驗(yàn)中，該值均為4。

采用本文方法對(duì)表1 數(shù)據(jù)進(jìn)行分類，分析本文方法的分類結(jié)果，見表2。

根據(jù)表2 的測(cè)試結(jié)果可知：第1 類用戶和第2 類用戶負(fù)荷波動(dòng)均較小，波動(dòng)范圍分別在0.14～0.25/kW·h和0.03～0.12/kW·h，其中負(fù)載較高的時(shí)間范圍在9～12 時(shí)和1～3 時(shí)；第3 類用戶負(fù)荷波動(dòng)較大，波動(dòng)范圍在1～10 時(shí)，說(shuō)明該用戶夜間用電較多；第4 類用戶負(fù)荷波動(dòng)也較小，并且相對(duì)平穩(wěn)。根據(jù)該結(jié)果可說(shuō)明：本文方法可根據(jù)不同的電力負(fù)荷大數(shù)據(jù)特點(diǎn)，有效完成用戶電力負(fù)荷大數(shù)據(jù)分類，具備較好的分類效果。

表2 電力大數(shù)據(jù)分類結(jié)果Table 2 Classification result of power big data kW·h

將文獻(xiàn)[4]和文獻(xiàn)[5]的基于小波分析的大數(shù)據(jù)自適應(yīng)延遲調(diào)度方法和基于灰色模糊預(yù)測(cè)的大數(shù)據(jù)調(diào)度方法作為本文方法的對(duì)比方法，統(tǒng)計(jì)3 種方法調(diào)度的負(fù)載均衡度，結(jié)果見圖3。

圖3 3種方法調(diào)度的負(fù)載均衡度對(duì)比結(jié)果Fig.3 Comparison of load balancing degree of three methods

根據(jù)圖3 測(cè)試結(jié)果可知：在相同迭代次數(shù)條件下，本文方法調(diào)度的負(fù)載均衡度優(yōu)于兩種對(duì)比方法；隨著迭代次數(shù)的增加，3 種方法調(diào)度的負(fù)載均衡度均呈現(xiàn)上升趨勢(shì)，但是，本文方法的調(diào)度后的負(fù)載均衡度結(jié)果依舊優(yōu)于兩種對(duì)比方法。說(shuō)明本文方法調(diào)度后的負(fù)載均衡度較好，具備良好的大數(shù)據(jù)跨源調(diào)度均衡性。

采用均衡負(fù)載離差進(jìn)一步衡量3 種方法的跨源調(diào)度性能，其計(jì)算公式為

式中：LBj和分別為處理器調(diào)度前負(fù)載和調(diào)度后負(fù)載；m為數(shù)據(jù)量。

利用式（15）獲取3 種方法在不同調(diào)度任務(wù)量條件下的負(fù)載均衡離差結(jié)果，見圖4。

圖4 3種方法的對(duì)比結(jié)果Fig.4 Comparison result of three methods

根據(jù)圖4 測(cè)試結(jié)果可知：在調(diào)度任務(wù)量相同的情況下，本文方法的電力負(fù)荷大數(shù)據(jù)跨源調(diào)度負(fù)載均衡離差均低于兩種對(duì)比方法；隨著調(diào)度任務(wù)量的增加，3 種方法的負(fù)載均衡離差均呈現(xiàn)上升趨勢(shì)，但是本文方法的上升趨勢(shì)相對(duì)平緩，并且依舊低于兩種對(duì)比方法，當(dāng)調(diào)度任務(wù)量達(dá)到1 000 個(gè)時(shí)，負(fù)載均衡離差也低于0.15，說(shuō)明本文方法的跨源調(diào)度負(fù)載均衡較好，調(diào)度性能較好。

調(diào)度開銷是衡量調(diào)度性能的主要指標(biāo)，統(tǒng)計(jì)3種方法在不同大小數(shù)據(jù)調(diào)度情況下所需的調(diào)度時(shí)間開銷，結(jié)果見圖5。

根據(jù)圖5 的測(cè)試結(jié)果可知：3 種方法在調(diào)度數(shù)據(jù)量相同時(shí)，調(diào)度開銷結(jié)果中，本文方法的開銷最低，均低于0.95 s；隨著調(diào)度數(shù)據(jù)量的增加，兩種對(duì)比方法的調(diào)度開銷呈現(xiàn)明顯上升趨勢(shì)，本文方法則相對(duì)平穩(wěn)，調(diào)度開銷沒有明顯增加。說(shuō)明本文方法可有效降低調(diào)度延遲和時(shí)間開銷，適用性較高。

圖5 3種方法的調(diào)度開銷對(duì)比結(jié)果Fig.5 Comparison result of scheduling cost of three methods

3 結(jié)語(yǔ)

隨著電力系統(tǒng)的發(fā)展，負(fù)荷數(shù)據(jù)日益復(fù)雜，且用戶類型多樣化，使得當(dāng)前電力用戶的負(fù)荷調(diào)度成為一大難題。本文研究基于最優(yōu)K 均值聚類的電力負(fù)荷大數(shù)據(jù)跨源調(diào)度方法，滿足電力企業(yè)用電需求的同時(shí)保障電力負(fù)荷均衡度。經(jīng)實(shí)驗(yàn)測(cè)試表明：本文方法在k值為4 時(shí)，可獲取最佳電力負(fù)荷大數(shù)據(jù)分類結(jié)果，并且調(diào)度均衡度較好，調(diào)度時(shí)的開銷較低，可有效完成電力負(fù)荷大數(shù)據(jù)的均衡調(diào)度。