基于信息熵的異常檢測(cè)算法

張安勤, 吳 蕊, 張 挺

(上海電力大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 上海 200090)

隨著電力系統(tǒng)的信息化程度不斷提高,電網(wǎng)的數(shù)據(jù)規(guī)模飛速增長(zhǎng)[1]。如何對(duì)海量的電網(wǎng)數(shù)據(jù)進(jìn)行高效分析,快速準(zhǔn)確地檢測(cè)出異常的電力數(shù)據(jù),是電網(wǎng)安全有效運(yùn)行的重要保證。

異常檢測(cè)可以發(fā)現(xiàn)數(shù)據(jù)集中與一般數(shù)據(jù)有差異的數(shù)據(jù)對(duì)象,即一些與眾不同的數(shù)據(jù)[2]。在電力領(lǐng)域中,異常檢測(cè)可以作為數(shù)據(jù)研究的基礎(chǔ),如檢測(cè)出異常的電力負(fù)荷數(shù)據(jù)能有效提高負(fù)荷數(shù)據(jù)的質(zhì)量,對(duì)后續(xù)進(jìn)行負(fù)荷預(yù)測(cè)及合理規(guī)劃電網(wǎng)有著重要的作用[3-4]。異常檢測(cè)也可以直接用于數(shù)據(jù)分析,如異常用電檢測(cè)和設(shè)備故障檢測(cè)等。

異常檢測(cè)技術(shù)主要可以分為基于監(jiān)督、半監(jiān)督和無(wú)監(jiān)督3種類型?；诒O(jiān)督的異常檢測(cè)方法的訓(xùn)練集由帶標(biāo)簽的正常和異常數(shù)據(jù)構(gòu)成,主要有概率統(tǒng)計(jì)方法[5]、神經(jīng)網(wǎng)絡(luò)方法[6]等;基于半監(jiān)督的異常檢測(cè)方法[7]能夠從大量無(wú)標(biāo)簽的數(shù)據(jù)及部分有標(biāo)簽的數(shù)據(jù)中挖掘出異常數(shù)據(jù)的信息;基于無(wú)監(jiān)督的異常檢測(cè)方法可以直接從無(wú)標(biāo)簽的數(shù)據(jù)集中檢測(cè)出異常數(shù)據(jù),主要有基于K-means算法的異常檢測(cè)[8]、基于AP聚類的異常檢測(cè)[9]和基于局部離群因子的異常檢測(cè)[10]等。基于監(jiān)督的異常檢測(cè)方法需要提前得到訓(xùn)練樣本的標(biāo)簽信息,一般可通過(guò)人工標(biāo)記來(lái)獲得足夠的訓(xùn)練樣本,成本及代價(jià)較高;而電力負(fù)荷數(shù)據(jù)集中大多數(shù)為無(wú)標(biāo)簽的數(shù)據(jù),采用無(wú)監(jiān)督的異常檢測(cè)方法具有代價(jià)小、簡(jiǎn)單、高效等優(yōu)點(diǎn)。

近年來(lái),研究者們提出了很多針對(duì)異常檢測(cè)的相關(guān)方法。文獻(xiàn)[11]通過(guò)劃定時(shí)間窗口來(lái)提取相關(guān)特征,并運(yùn)用核密度估計(jì)算法建模,實(shí)現(xiàn)了在無(wú)標(biāo)簽的海量數(shù)據(jù)中識(shí)別異常數(shù)據(jù)。文獻(xiàn)[12]基于最小生成樹提出了一種新的距離度量方法,能夠比歐氏距離更好地進(jìn)行樣本間相似性度量,并通過(guò)捕獲數(shù)據(jù)點(diǎn)或簇之間的相對(duì)連通性來(lái)進(jìn)行異常數(shù)據(jù)的檢測(cè)。文獻(xiàn)[13]提出了一種異常檢測(cè)模型,包含了特征提取、主成分分析、網(wǎng)格處理、局部離群因子計(jì)算等方法,可用于檢測(cè)電力用戶異常的用電模式。

K-means算法作為一種無(wú)監(jiān)督聚類算法,方法簡(jiǎn)單且易于實(shí)現(xiàn),可以廣泛應(yīng)用于異常檢測(cè)且檢測(cè)效果良好[14]。但是存在以下兩個(gè)問題:一是算法隨機(jī)選擇初始中心,易使結(jié)果陷入局部最優(yōu)且初始中心可能包含異常數(shù)據(jù)點(diǎn),導(dǎo)致聚類效果差且影響最終的異常檢測(cè)率;二是在計(jì)算樣本間的相似性時(shí)采用各屬性無(wú)差別的歐氏距離來(lái)進(jìn)行度量,沒有考慮數(shù)據(jù)的屬性權(quán)重,使得計(jì)算的樣本間相似性不準(zhǔn)確[15]。

針對(duì)上述問題,本文結(jié)合信息熵與改進(jìn)的K-means算法,提出了一種用于電力負(fù)荷數(shù)據(jù)的異常檢測(cè)算法。首先,通過(guò)信息熵確定屬性權(quán)重,在計(jì)算歐氏距離時(shí)引入屬性權(quán)重來(lái)度量樣本間的相似性;其次,計(jì)算每個(gè)樣本的密度及數(shù)據(jù)集的平均密度,在樣本密度大于平均密度的數(shù)據(jù)對(duì)象中根據(jù)密度及距離依次選出K個(gè)初始中心;最后,在K-means算法的迭代過(guò)程中,對(duì)比簇中數(shù)據(jù)對(duì)象到簇中心的加權(quán)歐氏距離與該簇平均加權(quán)歐氏距離,以檢測(cè)數(shù)據(jù)是否異常。實(shí)驗(yàn)表明,改進(jìn)的異常檢測(cè)算法在檢測(cè)率和誤檢率方面結(jié)果更優(yōu)。對(duì)電力負(fù)荷數(shù)據(jù)進(jìn)行異常檢測(cè)時(shí),相較于對(duì)比算法,改進(jìn)算法的檢測(cè)率提高了10.3%,誤檢率降低了1.7%,適合應(yīng)用于電力領(lǐng)域。

1 Kmeans算法及屬性權(quán)重的計(jì)算

1.1 Kmeans算法

K-means算法的主要思想是基于歐氏距離來(lái)計(jì)算樣本間相似性,并根據(jù)樣本間的相似程度將其劃入所屬的簇。傳統(tǒng)K-means算法流程如下。

輸入:樣本集X={x1,x2,x3,…,xn},聚類中心數(shù)K。

輸出:簇P={P1,P2,P3,…,PK}。

步驟1 從X中隨機(jī)選擇K個(gè)樣本作為初始中心{c1,c2,c3,…,cK}。

步驟2 計(jì)算X中的樣本與各簇中心ci(1≤i≤K)的距離,并將樣本劃入與其最近的聚類中心所屬的簇。

步驟3 根據(jù)簇中包含的樣本,重新形成每個(gè)簇的中心點(diǎn)。

步驟4 重復(fù)步驟2和步驟3直到聚類中心不變,算法結(jié)束。

1.2 屬性權(quán)重的計(jì)算

K-means算法在計(jì)算時(shí)并未考慮數(shù)據(jù)的屬性權(quán)重對(duì)聚類的影響,將會(huì)導(dǎo)致算法的聚類結(jié)果不準(zhǔn)確。信息熵是一種計(jì)算屬性權(quán)重的經(jīng)典算法,可以用來(lái)計(jì)算屬性的離散程度。對(duì)于某項(xiàng)指標(biāo),其熵值越小,則該指標(biāo)的離散程度越大且具有更大的信息量。因此,對(duì)屬性而言,熵值越小時(shí)該屬性對(duì)聚類的影響越大。將信息熵應(yīng)用于K-means算法時(shí),可根據(jù)各屬性的離散程度計(jì)算其權(quán)重,并通過(guò)計(jì)算加權(quán)歐氏距離來(lái)提高聚類效果和異常檢測(cè)率。

信息熵計(jì)算屬性權(quán)重的算法流程如下。

步驟1 假設(shè)數(shù)據(jù)集X由n個(gè)m維樣本構(gòu)成,則X可以表示為一個(gè)n×m的矩陣,即

步驟2 為了消除量綱對(duì)聚類結(jié)果的影響,對(duì)數(shù)據(jù)進(jìn)行歸一化處理,公式為

(1)

式中:xij——第i個(gè)樣本的第j列屬性值;

max(xj),min(xj)——數(shù)據(jù)集中第j列屬性的最大值和最小值。

步驟3 計(jì)算第i個(gè)樣本的第j列屬性所占的比重,公式為

(2)

步驟4 計(jì)算第j列屬性的信息熵,公式為

(3)

步驟5 計(jì)算第j列屬性的差異系數(shù),公式為

qj=1-Ej

(4)

步驟6 計(jì)算第j列屬性的權(quán)重,公式為

(5)

其中,0≤wj≤1。

計(jì)算得到各屬性的權(quán)重后,給出數(shù)據(jù)對(duì)象a和b的加權(quán)歐氏距離[16],公式為

(6)

式中:xaj,xbj——數(shù)據(jù)對(duì)象a和b的第j列屬性取值。

2 異常檢測(cè)算法

2.1 Kmeans算法初始中心的選擇

需要進(jìn)行異常檢測(cè)的數(shù)據(jù)集一般包含正常和異常兩種數(shù)據(jù)。由于傳統(tǒng)K-means算法的初始聚類中心是隨機(jī)選出的,算法有可能將異常點(diǎn)選作初始中心,從而影響聚類結(jié)果。異常數(shù)據(jù)一般具有以下特征:與正常數(shù)據(jù)相比,異常數(shù)據(jù)所占比例較小,數(shù)據(jù)集中的大多數(shù)數(shù)據(jù)都為正常數(shù)據(jù);異常數(shù)據(jù)的密度較小,分布在稀疏的區(qū)域,比如在進(jìn)行異常用電檢測(cè)或計(jì)算機(jī)監(jiān)控時(shí),數(shù)據(jù)集中的大多數(shù)數(shù)據(jù)為正常數(shù)據(jù),而異常數(shù)據(jù)大多處于正常數(shù)據(jù)所聚集的簇的邊緣或者簇與簇之間的區(qū)域。根據(jù)異常數(shù)據(jù)的特點(diǎn),可以選擇密度大于數(shù)據(jù)集平均密度的數(shù)據(jù)點(diǎn)作為初始中心,使得初始中心不含異常點(diǎn)。

K-means算法的聚類結(jié)果和聚類效率與初始中心有直接的關(guān)聯(lián)。算法的初始中心越接近實(shí)際簇中心則聚類效率越高,而隨機(jī)的選擇初始中心則導(dǎo)致了聚類結(jié)果不夠可靠。

初始聚類中心的選擇算法如下。

輸入:樣本集X={x1,x2,x3,…,xn},最近鄰數(shù)據(jù)點(diǎn)個(gè)數(shù)t,聚類中心數(shù)K。

輸出:初始中心C={c1,c2,c3,…,cK}。

步驟1 計(jì)算X中數(shù)據(jù)點(diǎn)xj(1≤j≤n)的密度為

(7)

式中:Gt(xj)——xj的t個(gè)最近鄰數(shù)據(jù)點(diǎn)集合。

步驟2 計(jì)算所有數(shù)據(jù)對(duì)象的平均密度D,由D(xj)>D的數(shù)據(jù)點(diǎn)形成新的數(shù)據(jù)集X′。其平均密度的公式為

(8)

步驟3 在X′中,取D(xj)最大的數(shù)據(jù)點(diǎn)作為第1個(gè)初始中心c1,取距離c1最遠(yuǎn)的數(shù)據(jù)點(diǎn)作為第2個(gè)初始中心c2。對(duì)于X′中的樣本xj(j=1,2,3,…,n),計(jì)算其與前i-1(3≤i≤K)個(gè)初始中心的加權(quán)歐氏距離dist(xj,c1),dist(xj,c2),…,dist(xj,ci-1),選出其中的最小值min(dist(xj,c1),dist(xj,c2),…,dist(xj,ci-1))。按照上述方式依次計(jì)算X′中的每個(gè)樣本與前i-1個(gè)初始中心加權(quán)歐氏距離的最小值,并放入集合中,集合中最大值對(duì)應(yīng)的數(shù)據(jù)對(duì)象為第i個(gè)初始中心ci,直到選出K個(gè)初始中心,算法結(jié)束。即滿足

max{min(dist(xj,c1),dist(xj,c2),…,

dist(xj,ci-1))}

(9)

由上述算法過(guò)程可知,實(shí)際的簇中心一般處于密度較大的區(qū)域且相互間具有一定的距離,改進(jìn)算法在密度大于平均密度的數(shù)據(jù)點(diǎn)中均勻地選擇初始聚類中心,滿足了密度較大和保持距離的要求。另外,改進(jìn)算法有效避免了將異常點(diǎn)作為初始中心的情況,使算法不會(huì)從開始就陷入誤差,提高了聚類效率。

2.2 基于信息熵與改進(jìn)Kmeans算法的異常檢測(cè)算法

本文根據(jù)異常數(shù)據(jù)的特征和分布模式提出了一種異常檢測(cè)算法。該算法在聚類迭代時(shí)通過(guò)對(duì)比數(shù)據(jù)點(diǎn)到所屬簇中心的加權(quán)歐氏距離與該簇中所有數(shù)據(jù)點(diǎn)到簇中心的平均加權(quán)歐氏距離來(lái)檢測(cè)異常。在異常檢測(cè)過(guò)程中采用加權(quán)歐氏距離,考慮了屬性權(quán)重對(duì)異常檢測(cè)計(jì)算的影響,使異常檢測(cè)結(jié)果更加準(zhǔn)確。

基于信息熵與改進(jìn)K-means算法的異常檢測(cè)算法如下。

輸入:樣本集X={x1,x2,x3,…,xn},最近鄰數(shù)據(jù)點(diǎn)個(gè)數(shù)t,聚類中心數(shù)K,異常度閾值η(X不同時(shí),η的取值也不相同)。

輸出:簇P={P1,P2,P3,…,PK},異常點(diǎn)集合U。

步驟1 設(shè)數(shù)據(jù)集中每個(gè)數(shù)據(jù)對(duì)象的初始異常度為Fj=0(j=1,2,3,…,n),并根據(jù)信息熵計(jì)算屬性權(quán)重的算法來(lái)計(jì)算數(shù)據(jù)集X中各屬性權(quán)重。

步驟2 根據(jù)初始聚類中心的選擇算法選擇K個(gè)初始中心{c1,c2,c3,…,cK}。

步驟3 計(jì)算數(shù)據(jù)對(duì)象xj與各簇中心ci(i=1,2,3,…,K)的加權(quán)歐氏距離,并將xj劃入距其最近的聚類中心所在的簇。

步驟4 在K個(gè)簇中,若xj(j=1,2,3,…,n)與所屬簇中心的加權(quán)歐氏距離大于該簇中所有數(shù)據(jù)對(duì)象到簇中心的平均加權(quán)歐氏距離,則Fj++。上述判斷公式為

(10)

式中:|Pi|——簇Pi中的數(shù)據(jù)對(duì)象個(gè)數(shù)。

步驟5 重新生成每個(gè)簇的中心點(diǎn)

(11)

步驟6 若c′i≠ci,則將ci更新為c′i,并返回執(zhí)行步驟3。

步驟7 若數(shù)據(jù)對(duì)象xj的異常度Fj≥η,則判斷xj為異常點(diǎn),將xj并入U(xiǎn)中。

步驟8 聚類算法結(jié)束,輸出P和U。

由于數(shù)據(jù)對(duì)象的異常度是通過(guò)計(jì)算每次迭代時(shí)該數(shù)據(jù)對(duì)象與所屬簇中心的加權(quán)歐氏距離來(lái)確定的,因此算法選擇的初始中心越接近實(shí)際的簇類中心,異常檢測(cè)的性能越好。當(dāng)初始中心含異常點(diǎn)時(shí)會(huì)嚴(yán)重影響異常檢測(cè)的準(zhǔn)確率,而改進(jìn)算法選擇的初始中心不含異常點(diǎn),有效避免了上述問題。最后,在異常計(jì)算中引入屬性權(quán)重,考慮了各個(gè)屬性對(duì)異常檢測(cè)的作用。

3 實(shí)驗(yàn)分析

實(shí)驗(yàn)數(shù)據(jù)采用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)的Parkinson Disease Spiral Drawings Using Digitized Graphics Tablet數(shù)據(jù)集[17-18](以下簡(jiǎn)稱為“帕金森數(shù)據(jù)集”),以及某電廠一個(gè)月的電力負(fù)荷數(shù)據(jù)。將檢測(cè)率和誤檢率作為異常檢測(cè)性能的評(píng)價(jià)指標(biāo)。

檢測(cè)率(Detection Rate,DR)和誤檢率(False Alarm,FA)的定義如下[19]

(12)

(13)

其中:TP——被正確檢測(cè)為異常的異常樣本數(shù);

FN——被錯(cuò)誤檢測(cè)為正常的異常樣本數(shù);

TN——被正確檢測(cè)為正常的正常樣本數(shù);

FP——被錯(cuò)誤檢測(cè)為異常的正常樣本數(shù)。

帕金森數(shù)據(jù)集包含靜態(tài)螺旋、動(dòng)態(tài)螺旋和定點(diǎn)穩(wěn)定性3種測(cè)試。算法在每種測(cè)試中隨機(jī)選擇1 000條健康樣本與100條患者樣本作為數(shù)據(jù)集,分別對(duì)3種測(cè)試類型進(jìn)行計(jì)算,并將患者樣本當(dāng)做異常數(shù)據(jù)來(lái)驗(yàn)證異常檢測(cè)的效果。實(shí)驗(yàn)對(duì)比了改進(jìn)算法與傳統(tǒng)K-means算法、MinMax K-means算法的異常檢測(cè)性能[20-21],結(jié)果如表1所示。其中,對(duì)比算法的數(shù)據(jù)結(jié)果為兩種算法分別計(jì)算100次后的平均值[22]。

表1 3種算法在帕金森數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果對(duì)比 單位:%

對(duì)于電力負(fù)荷數(shù)據(jù)集,通過(guò)在其中隨機(jī)添加一定比例的異常數(shù)據(jù)來(lái)對(duì)比3種算法的異常檢測(cè)性能,結(jié)果如表2所示。

表2 3種算法在電力負(fù)荷數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果對(duì)比 單位:%

實(shí)驗(yàn)結(jié)果表明,與K-means算法和MinMax K-means算法相比,改進(jìn)算法的檢測(cè)率更高且誤檢率更低。究其原因如下:首先,改進(jìn)算法選擇了更優(yōu)的初始中心,不同的初始中心會(huì)導(dǎo)致在每次迭代時(shí)生成不同的簇類中心,而在迭代過(guò)程中數(shù)據(jù)對(duì)象的異常度計(jì)算與其所屬的簇中心相關(guān);其次,初始中心含有異常點(diǎn),會(huì)使算法從一開始就陷入偏差,影響數(shù)據(jù)對(duì)象異常度的計(jì)算,進(jìn)而影響最終的檢測(cè)率和誤檢率,而改進(jìn)算法有效避免了這種情況;最后,改進(jìn)算法引入了屬性權(quán)重的概念,根據(jù)各屬性影響程度的不同,其在計(jì)算時(shí)的占比也不同,使得異常計(jì)算的結(jié)果更加準(zhǔn)確,從而提高了異常檢測(cè)的性能。

4 結(jié) 語(yǔ)

本文根據(jù)異常數(shù)據(jù)的特征和分布情況,結(jié)合信息熵與改進(jìn)的K-means算法,提出了一種適用于電力負(fù)荷數(shù)據(jù)的異常檢測(cè)算法。算法在選擇初始聚類中心時(shí)有效避免了異常點(diǎn)并使得初始聚類中心均勻分布,聚類的效果更優(yōu)。在此基礎(chǔ)上,算法引入了屬性權(quán)重和加權(quán)歐氏距離來(lái)計(jì)算數(shù)據(jù)點(diǎn)的異常度。實(shí)驗(yàn)證明,相較于其他對(duì)比算法,本文提出的改進(jìn)算法有著更優(yōu)的異常檢測(cè)性能,能夠有效檢測(cè)出異常的電力負(fù)荷數(shù)據(jù),為實(shí)現(xiàn)高精度的負(fù)荷預(yù)測(cè)提供了重要保障。