劉蕓菲，陸 奎

(安徽理工大學(xué) 計算機科學(xué)與工程院，安徽 淮南 232001)

0 引 言

目前，社會經(jīng)濟正處在高速發(fā)展的時期，電網(wǎng)規(guī)模持續(xù)擴大。電力的穩(wěn)定供應(yīng)不僅關(guān)系著企業(yè)的生存、效益和發(fā)展，更影響著人民生活、國家經(jīng)濟發(fā)展和社會穩(wěn)定的大局[1]。然而，近年來電力生產(chǎn)與作業(yè)過程中的安全問題頻頻發(fā)生，給人民生活帶來不便，嚴(yán)重阻礙了電力行業(yè)的進一步發(fā)展。因此，為了降低電力行業(yè)事故的發(fā)生率，需要對可能發(fā)生危險的生產(chǎn)或檢查工作進行預(yù)警，這樣，才能更好地應(yīng)對異常情況的發(fā)生[2-3]。

貝葉斯網(wǎng)絡(luò)是應(yīng)用廣泛的預(yù)測模型之一，其使用非循環(huán)有向圖編碼隨機變量之間的條件獨立關(guān)系。非循環(huán)有向圖可用于“讀取”條件獨立關(guān)系，從而提供對由貝葉斯網(wǎng)絡(luò)表示的聯(lián)合概率分布的結(jié)構(gòu)的洞察[4]。

貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的一種標(biāo)準(zhǔn)方法是“搜索和得分”[5]。選擇得分以表示觀察數(shù)據(jù)(和任何先前知識)支持任何候選BN的程度，然后進行搜索以找到具有最大得分的貝葉斯網(wǎng)絡(luò)。因此，貝葉斯網(wǎng)絡(luò)學(xué)習(xí)是一個優(yōu)化問題[6-7]。不幸的是，即使非循環(huán)有向圖中任何頂點的父親數(shù)限制為2，這個優(yōu)化問題對于任何合理的分數(shù)都是NP難的[8]。

鑒于這種結(jié)果，大多數(shù)貝葉斯網(wǎng)絡(luò)學(xué)習(xí)工作集中在啟發(fā)式搜索上，其中不能保證找到最優(yōu)貝葉斯網(wǎng)絡(luò)。然而，關(guān)于精確貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的研究越來越多。一種方法是使用動態(tài)編程[9-10]，它已經(jīng)成功地用于精確學(xué)習(xí)多達30個頂點。所以，文中集中于兩個關(guān)鍵：首先，尋求一種新穎的貪婪算法，以互信息為衡量標(biāo)準(zhǔn)，旨在解決網(wǎng)絡(luò)學(xué)習(xí)中的NP難問題；其次，將貝葉斯網(wǎng)絡(luò)應(yīng)用于電力事故的預(yù)警，根據(jù)典型事故中的致因因素來預(yù)測可能發(fā)生的事故等級。并根據(jù)等級的不同警示電網(wǎng)領(lǐng)域，做好事故的應(yīng)對方案。

具體貢獻在于：構(gòu)造貝葉斯網(wǎng)絡(luò)，根據(jù)互信息，為屬性間的依賴關(guān)系提供了一種衡量方法；再者，通過互信息和貪婪算法的結(jié)合，優(yōu)化了整個網(wǎng)絡(luò)的構(gòu)造過程。電網(wǎng)事故預(yù)警，在完成網(wǎng)絡(luò)構(gòu)建的同時，成功做到電網(wǎng)預(yù)警的目的。

1 相關(guān)知識

電網(wǎng)的事故產(chǎn)生包含多種因素，如高空墜落、接地線不良和觸電等。設(shè)A為電網(wǎng)事故的致因數(shù)據(jù)集屬性，d為A的大小，Ad為最后電網(wǎng)事故的預(yù)測等級，分別為等級1、等級2、等級3、等級4和等級5。則A上的貝葉斯網(wǎng)絡(luò)[11]定義為一組屬性對(AP)，即(A1,P1),…,(Ad,Pd)，則有：

(1)每個Ai都是A中的唯一屬性；

(2)每個Pi是A中屬性的子集。Pi是貝葉斯網(wǎng)絡(luò)中Ai的父集合；

(3)對于任何1≤i

圖1顯示了基于六個事故致因?qū)傩缘呢惾~斯網(wǎng)絡(luò)。

圖1 六個電網(wǎng)致因?qū)傩缘呢惾~斯網(wǎng)絡(luò)

2 貝葉斯網(wǎng)絡(luò)的電網(wǎng)事故預(yù)警模型

2.1 私有方法

(1)

定義：最大AP對聯(lián)合分布。給定AP對(A,P)，最大AP對聯(lián)合分布M*(A,P)是最大化A和P之間的互信息的分布。

引理：假設(shè)|dom(A)|≤|dom(P)|，M*(A,P)是最大AP對聯(lián)合分布，如果：

(1)對于?a∈dom(A)，M*(A=a)=1/|dom(A)|;

(2)對于?p∈dom(P)，最多有一個a∈dom(A)，其中M*(A=a,P=p)>0。

證明：假設(shè)|dom(A)|≤|dom(P)|，log|dom(A)|是互信息，則屬性A和P之間的最大互信息是：

maxI(A,P)=min{maxH(A),maxH(P)}=min{log|dom(A)|,log |dom(P)|} = log |dom(A)|

(2)

假設(shè)M*(A,P)是滿足引理中兩個屬性的聯(lián)合分布。那么，給定信息論的基本結(jié)果，這兩個屬性相當(dāng)于：

(1)H(A)=log|dom(A)|；

(2)H(A|P)=0。

因此，M*(A,P)的互信息是：

I(A,P)=H(A)-H(A|P)=log|dom(A)|

(3)

根據(jù)定義，M*(A,P)是最大AP對聯(lián)合分布。

另一方面，假設(shè)M*(A,P)是具有l(wèi)og|dom(Ai)|的最大聯(lián)合分布，則互信息可表示為：

I(A,P)=log|dom(A)|=H(A)-H(A|P)

(4)

其中H(A)≤log|dom(A)|并且H(A|P)≥0始終保持。因此，可以得出結(jié)論，I(A,P)在如下情況下能實現(xiàn)最大化：

(1)H(A)=log|dom(A)|，僅通過dom(A)上的均勻分布實現(xiàn)；

(2)H(A|P)=0，這意味著對于每個父集p存在屬性a，使得Pr[A=a，P=p]。

2.2 私有貝葉斯網(wǎng)絡(luò)

為了構(gòu)建k度貝葉斯網(wǎng)絡(luò)，對于k=1的情況，Chow等[12]提出，根據(jù)最大互信息貪婪地選擇下一個邊緣是最佳的。Van等[13]指出，當(dāng)k>1時，這個優(yōu)化問題是NP難的。因此，啟發(fā)式算法[14]經(jīng)常在實踐中使用。為了克服這個問題，尋求一種新穎的貪婪算法。

算法：貝葉斯網(wǎng)絡(luò)構(gòu)造。

輸入：數(shù)據(jù)集DS，限制參數(shù)k；

輸出：貝葉斯網(wǎng)絡(luò)BN。

(1)數(shù)據(jù)集DS清洗

(2)初始化BN=? andV=?

(3)從A中隨機選擇一個屬性A1;添加(A1,0)到BN;添加A1到V

(4)Fori=2 toddo

(5)初始化Ω=?；

(6)for eachAi∈AVdo

(7)找到A中所有最大父集

(8)for eachPi∈Vkdo

(9)添加(Ai，Pi)到Ω

(10)從Ω中選擇包含最大互信息I(Ai,Pi)的一對(Ai,Pi)

(11)Add(Ai,Pi) to BN；addAitoV

(12)結(jié)束

(13)返回BN

在算法(第1～2行)的開頭，對原始數(shù)據(jù)集DS進行清理操作(刪除空值)，并將貝葉斯網(wǎng)絡(luò)BN初始化為空的AP對列表。假設(shè)V是一個包含其父集已在BN的部分構(gòu)造中被修復(fù)的所有屬性的集合。作為下一步，算法從A中隨機選擇一個屬性(表示為A1)并將其父集P1設(shè)置為0(第3行)。算法的其余部分由d-1次迭代(第4～11行)組成，每次迭代都貪婪地添加到具有大互信息的AP對中。具體而言，在候選集中選擇包含迭代期間所需的兩個AP對：

(1)|P|≤k，通過僅從Vk選擇P來確保BN是k度貝葉斯網(wǎng)絡(luò)，其中Vk表示V的所有子集的集合，并且其大小是min(k,|V|)(第4～10行)。

(2)對于任何j

一旦確定了每個屬性的父集合，該算法就終止并返回貝葉斯網(wǎng)絡(luò)BN(第12～13行)。

2.3 時間復(fù)雜度分析

由于難以從具有低信噪比的小樣本空間獲得可靠的估計，因此用戶記錄的數(shù)量需要足夠大。

定理：假設(shè)數(shù)據(jù)集DS的平均大小為m，貝葉斯網(wǎng)絡(luò)節(jié)點屬性集大小為v，則算法的時間復(fù)雜度是：O(Nmkv+tNv2d)。

證明：算法將逐個掃描所有貝葉斯網(wǎng)絡(luò)BN用戶的記錄，其長度為k*m，因此時間復(fù)雜度估計為O(N(km)v)。此外，在t次迭代中，在觀察每個比特串時計算每個組合的后驗概率將產(chǎn)生O(tNv2d)的時間復(fù)雜度。因此，總時間復(fù)雜度為O[N(km)v+tNv2d]。

3 實 驗

3.1 實驗設(shè)置

為了模擬電網(wǎng)事故等級的預(yù)測問題，采取美國1994年人口普查數(shù)據(jù)庫抽取而來的成年人(Adult[15-16])數(shù)據(jù)集進行實驗。成年人數(shù)據(jù)集包含了32 561條成人數(shù)據(jù)，并同時具有連續(xù)屬性和分類屬性。為了更好地衡量實驗的效果，選取種族，國家，教育，階級，工作和收入六個屬性。將文中的私有貝葉斯網(wǎng)絡(luò)與K-近鄰算法和決策樹算法進行對比，并同時驗證在收入是否超過50K情況下的分類效果。對于每個分類任務(wù)，使用數(shù)據(jù)中70%的元組作為訓(xùn)練集，另外30%作為測試集。

3.2 實驗分析

為了構(gòu)造貝葉斯網(wǎng)絡(luò)BN，計算每個屬性之間的互信息，并且每次將具有最大互信息值的AP對添加到貝葉斯網(wǎng)絡(luò)BN。構(gòu)造的貝葉斯網(wǎng)絡(luò)如圖2所示。

圖2 DS中六個屬性的貝葉斯網(wǎng)絡(luò)

對于貝葉斯網(wǎng)絡(luò)BN的訓(xùn)練集設(shè)置為7 722條記錄。為更好地衡量BN的分類能力，現(xiàn)將BN劃分為六個數(shù)量級進行分類預(yù)測，數(shù)據(jù)集劃分為L=(1K,2K,4K，8K，16K，30K)(1K=1 000)。在圖3中觀察到的總體趨勢是，隨著實驗數(shù)據(jù)集的增加，分類錯誤率呈現(xiàn)不同程度的波動。不同數(shù)據(jù)集的確切行為有所不同，在某些情況下，其數(shù)據(jù)集漸近趨近，而在另一些情況下，具有更多的S形。可以看出，這種行為主要是由于貝葉斯網(wǎng)絡(luò)具有不同元數(shù)據(jù)捕捉數(shù)據(jù)分布的先天能力。在多組數(shù)據(jù)劃分的數(shù)據(jù)集里，文中的私有貝葉斯網(wǎng)絡(luò)的分類錯誤率普遍低于K-近鄰和決策樹分類的效果。這是因為，文中的私有貝葉斯網(wǎng)絡(luò)不僅成功實現(xiàn)了分類的目的，而且考慮了屬性間的關(guān)系。

圖3 分類誤差率對比

4 結(jié)束語

電網(wǎng)安全問題事關(guān)民生之本，迫切需要一種能夠早發(fā)現(xiàn)、早預(yù)警的事故模型?；谝陨锨榫埃岢隽艘环N基于貪婪算法和互信息的事故預(yù)警模型，可以高效、直觀地對事故等級進行劃分，這有利于電網(wǎng)日常的風(fēng)險防范。特別地，文中提出了貪婪構(gòu)造貝葉斯網(wǎng)絡(luò)的方法。

貝葉斯網(wǎng)絡(luò)模型已被證明是近似表示相關(guān)數(shù)據(jù)的有效方法，以這種模型發(fā)布的數(shù)據(jù)不僅高效而且準(zhǔn)確，并比分類機制能提供更高的準(zhǔn)確性。文中提出的私有貝葉斯網(wǎng)絡(luò)的構(gòu)造關(guān)鍵部分是利用互信息來構(gòu)造相關(guān)性模型，這不僅提供了屬性間的關(guān)聯(lián)情況，更提高了發(fā)布數(shù)據(jù)的質(zhì)量。實驗結(jié)果表明，構(gòu)建的私有貝葉斯網(wǎng)絡(luò)具有較好的分類效果。