基于BK樹的擴展置信規(guī)則庫結(jié)構(gòu)優(yōu)化框架*

蘇　群，楊隆浩，傅仰耿+，余瑞銀

1.福州大學 數(shù)學與計算機科學學院，福州 350116

2.福州大學 經(jīng)濟與管理學院，福州 350116

基于BK樹的擴展置信規(guī)則庫結(jié)構(gòu)優(yōu)化框架*

蘇群1，楊隆浩2，傅仰耿1+，余瑞銀1

1.福州大學 數(shù)學與計算機科學學院，福州 350116

2.福州大學 經(jīng)濟與管理學院，福州 350116

SU Qun,YANG Longhao,FU Yanggeng,et al.Structure optimization framework of extended belief rule base based on BK-tree.Journal of Frontiers of Computer Science and Technology,2016,10(2)：257-267.

針對擴展置信規(guī)則庫（extended belief rule base,EBRB）系統(tǒng)在規(guī)則數(shù)較多時推理效率不理想的問題，引入BK樹數(shù)據(jù)結(jié)構(gòu)，提出了一種基于BK樹的結(jié)構(gòu)優(yōu)化框架。首先根據(jù)置信規(guī)則在度量空間中彼此的距離建立EBRB的樹形索引結(jié)構(gòu)，然后通過設(shè)置閾值減少EBRB系統(tǒng)推理時搜索規(guī)則的數(shù)量，并激活關(guān)鍵規(guī)則，最終達到提高EBRB系統(tǒng)推理效率的目的。以非線性函數(shù)擬合、輸油管道泄露仿真實驗及分類數(shù)據(jù)集的對比實驗，驗證結(jié)構(gòu)優(yōu)化框架在EBRB系統(tǒng)中的有效性，實驗結(jié)果表明，所提框架能夠優(yōu)化EBRB系統(tǒng)推理效率并提高決策準確性。

擴展置信規(guī)則庫（EBRB）；證據(jù)推理（ER）；BK樹；優(yōu)化框架

1　引言

專家系統(tǒng)是人工智能領(lǐng)域最活躍和最廣泛的應(yīng)用領(lǐng)域之一，為了綜合使用定量信息及由專家提供的不完整或不精確的主觀信息，Yang等人在D-S證據(jù)理論[1-2]、決策理論[3]、模糊理論[4]和傳統(tǒng)IF-THEN規(guī)則庫[5]的基礎(chǔ)上提出了基于證據(jù)推理算法的置信規(guī)則庫推理方法[6]（belief rule base inference methodology using the evidential reasoning approach，RIMER）。相比于神經(jīng)網(wǎng)絡(luò)算法和支持向量機等“黑箱”方法，RIMER方法的推理過程具有更好的解釋性和透明性[7]。

置信規(guī)則庫（belief rule base,BRB）是RIMER方法中重要的組成部分，因此RIMER方法也稱為BRB系統(tǒng)。為了提高BRB系統(tǒng)的推理能力，Yang等人[8]首次提出了BRB系統(tǒng)的參數(shù)優(yōu)化模型，并通過Matlab優(yōu)化工具箱中的FMINCON函數(shù)進行參數(shù)學習。隨后，Chen等人[9]增加前提屬性的參考值進行參數(shù)學習，提出了全局優(yōu)化模型。Liu等人[10]提出BRB規(guī)則間的一致性問題，將BRB的一致性加入適應(yīng)度函數(shù)，改進了目標函數(shù)。但上述方法均屬于基于FMINCON函數(shù)的不斷迭代的參數(shù)學習方法，導致算法效率不理想。針對該問題，基于群智能算法[11-12]的參數(shù)學習方法相繼被提出，雖然算法效率有所提高，但是BRB的參數(shù)學習同樣屬于反復迭代的搜索過程。隨后，Liu等人[13]將分布式置信框架引入置信規(guī)則的前件部分，并提出相應(yīng)的擴展置信規(guī)則庫（extended belief rule base,EBRB）系統(tǒng)表示、產(chǎn)生和推理的方法，該方法簡單高效，且在EBRB系統(tǒng)無需進行參數(shù)學習的情況下，也具有良好的推理準確性。針對Liu等人的方法，其在推理效率方面仍存在瑕疵，主要體現(xiàn)在EBRB系統(tǒng)中規(guī)則均為無序存儲狀態(tài)，導致在對規(guī)則進行組合推理時需要遍歷EBRB系統(tǒng)中所有規(guī)則以計算激活權(quán)重，當EBRB系統(tǒng)具有較多規(guī)則時，反復地遍歷EBRB系統(tǒng)內(nèi)規(guī)則將會導致推理效率低下，再加之當進行參數(shù)學習時需反復迭代，勢必增加算法的時間開銷，而這些都將制約EBRB系統(tǒng)的實現(xiàn)與應(yīng)用。

BK樹（Burkhard-Keller tree,BK-tree）通過對數(shù)據(jù)構(gòu)建樹形索引結(jié)構(gòu)，進而可以對查詢高效地搜索近鄰數(shù)據(jù)[14]，BK樹已經(jīng)被廣泛應(yīng)用于模式識別、文本和多媒體信息檢索中[15]。為了提高EBRB系統(tǒng)的推理效率以及組合更具代表性的規(guī)則進行推理決策，本文提出了一種基于BK樹的結(jié)構(gòu)優(yōu)化框架。通過該結(jié)構(gòu)優(yōu)化框架可簡單、高效地構(gòu)建基于BK樹的樹形索引的EBRB系統(tǒng)，高效地搜索近鄰規(guī)則以響應(yīng)查詢，進而克服傳統(tǒng)EBRB系統(tǒng)在計算激活權(quán)重時需遍歷整個EBRB的問題。結(jié)構(gòu)優(yōu)化框架的具體實現(xiàn)過程可概述為將EBRB內(nèi)規(guī)則根據(jù)度量空間中彼此間的度量距離建立索引，在計算激活權(quán)重時利用索引對規(guī)則進行高效的搜索，再通過閾值設(shè)置的方式組合EBRB內(nèi)關(guān)鍵規(guī)則，最終提升EBRB系統(tǒng)的推理效率和決策性能。此外，本文提出的基于BK樹的結(jié)構(gòu)優(yōu)化框架有別于現(xiàn)有的參數(shù)學習方法，其并未改變EBRB系統(tǒng)的參數(shù)取值，因而可靈活地與任意EBRB系統(tǒng)或其他具備置信框架的系統(tǒng)及方法相結(jié)合，達到提升系統(tǒng)或方法效率的目的。最后引入函數(shù)擬合問題、輸油管道泄漏問題和多個分類數(shù)據(jù)集，通過與傳統(tǒng)BRB系統(tǒng)及傳統(tǒng)EBRB系統(tǒng)在推理效率和決策準確性方面進行比較，說明本文所提結(jié)構(gòu)優(yōu)化框架是切實可行的。

2　擴展置信規(guī)則庫系統(tǒng)

2.1擴展置信規(guī)則庫的表示

為了表示數(shù)據(jù)或知識中存在的不確定性及不完整性，Yang等人基于傳統(tǒng)IF-THEN規(guī)則，在規(guī)則的THEN部分引入分布式置信框架，并考慮前提屬性權(quán)重和規(guī)則權(quán)重對推理結(jié)果的影響，提出了置信規(guī)則（belief rule）[6]。為了使規(guī)則表示信息時更加準確和全面，Liu等人在規(guī)則的IF部分也引入了分布式置信度框架，并提出了相適應(yīng)的規(guī)則產(chǎn)生和推理方法[13]。表1對Yang和Liu提出的BRB系統(tǒng)進行了簡單比較。

其中，(A,αk)是分布式置信度的形式，也可表示為，Ai,j表示第i個前提屬性的第j個參考值，且參考值數(shù)量為Ji；T表示規(guī)則中前提屬性的數(shù)量；L表示EBRB內(nèi)規(guī)則的數(shù)量；N表示評價結(jié)果的數(shù)量；θk表示第k條規(guī)則的規(guī)則權(quán)重，反映第k條規(guī)則在EBRB中的重要度；δi表示規(guī)則中第i個前提屬性的權(quán)重，反映規(guī)則中第i個前提屬性相對于其他前提屬性的重要度；βj,k(j=1,2,…,N,k=1,2,…,L)表示第k條規(guī)則中第 j個評價結(jié)果的置信度，如果，則稱第k條規(guī)則是完整的，否則稱第k條規(guī)則是不完整的。

2.2擴展置信規(guī)則庫的構(gòu)建

Liu等人提出了一種數(shù)據(jù)驅(qū)動的構(gòu)建EBRB的方法。假設(shè)EBRB系統(tǒng)第i個輸入數(shù)據(jù)xi為定量數(shù)據(jù)，且xi為數(shù)值形式。首先由專家或決策者建立參考值A(chǔ)i,j(j=1,2,…,Ji)與數(shù)值量γi,j，并建立起對應(yīng)關(guān)系，假設(shè)專家對參考值的偏好程度滿足γi,j+1＞γi,j，那么輸入xi可以等價地轉(zhuǎn)換為分布式置信分布的期望形式：

其中αi,j的計算方法如下：

通過式（2）～（5）產(chǎn)生擴展置信規(guī)則的前件部分，與輸入xi相對應(yīng)的輸出yi可采用同樣的方法產(chǎn)生評價結(jié)果的分布式置信分布形式，從而由數(shù)據(jù)集構(gòu)建完整的EBRB。

Table 1　Comparison between Yang-BRB system and Liu-EBRB system表1　Yang-BRB系統(tǒng)與Liu-EBRB系統(tǒng)的比較

2.3擴展置信規(guī)則庫的推理

EBRB系統(tǒng)通過ER算法對規(guī)則進行組合，從而獲得EBRB系統(tǒng)的推理結(jié)果。對于輸入信息X，首先計算每條置信規(guī)則的激活權(quán)重，其中第k條置信規(guī)則的激活權(quán)重計算公式如下：

利用ER解析公式[16-17]，可求解激活規(guī)則組合后的對應(yīng)評價結(jié)果Dj(j=1,2,…,N)的基本可信值，然后再轉(zhuǎn)化為置信度的形式，具體公式如下：

其中，βj表示評價結(jié)果Dj的置信度；βH表示未分配給任意評價結(jié)果的置信度。假設(shè)已知一組對應(yīng)的輸入輸出(xm,ym)且m=1,2,…,T，根據(jù)評價結(jié)果分布式的置信度可以得到EBRB系統(tǒng)輸出的期望效用值，方法如下：

3　EBRB的結(jié)構(gòu)優(yōu)化框架

EBRB方法能夠簡單高效地產(chǎn)生擴展置信規(guī)則，并避免了BRB系統(tǒng)存在的維數(shù)災難問題[18]。但在EBRB根據(jù)輸入進行推理時，擴展置信規(guī)則以無序的方式存儲，因此需要依次遍歷EBRB中的所有規(guī)則以計算規(guī)則的激活權(quán)重，當規(guī)則數(shù)量較大時會導致EBRB系統(tǒng)的推理效率不理想。為了解決這一問題，本文提出一個基于BK樹數(shù)據(jù)結(jié)構(gòu)的EBRB結(jié)構(gòu)優(yōu)化框架，并與數(shù)據(jù)驅(qū)動的EBRB方法[13]相結(jié)合，說明該框架的原理與作用。該結(jié)構(gòu)優(yōu)化框架首先計算置信規(guī)則間的度量距離，然后根據(jù)度量距離基于BK樹將原先無序存儲的規(guī)則建成樹形結(jié)構(gòu)的索引，在搜索激活規(guī)則時通過設(shè)置的閾值減少搜索規(guī)則的數(shù)量并得到關(guān)鍵規(guī)則，最后使EBRB系統(tǒng)在決策時具有良好的效率和準確性。

3.1Burkhard-Keller樹

Burkhard-Keller樹簡稱BK樹，是由Burkhard和Keller提出的一種能高效地解決最優(yōu)匹配問題的方法[14]。該方法對數(shù)據(jù)在一個度量空間中建立樹形數(shù)據(jù)結(jié)構(gòu)的索引，設(shè)X為所有可能取值的集合，d表示集合X的度量，?x,y,z∈X，對于一個度量空間(X,d)，應(yīng)具有以下3個性質(zhì)。

（1）非負性：d(x,y)≥0，且d(x,y)=0當且僅當x=y。

（2）對稱性：d(x,y)=d(y,x)。

（3）三角不等式：d(x,z)≤d(x,y)+d(y,z)。

BK樹具有一個特點，即一棵子樹中的所有節(jié)點與父節(jié)點具有相同的度量距離。圖1展示了一個三層BK樹的結(jié)構(gòu)圖，其中第一層節(jié)點為根節(jié)點；第二層有m+1個節(jié)點，表示可以將除根節(jié)點外的其他節(jié)點劃分為m+1棵子樹，第i(i=0,1,…,m)棵子樹中的節(jié)點與根節(jié)點的度量距離都相同。要注意的是i并非一定等于度量距離，它可以是度量距離進行離散處理后對應(yīng)的值。同樣第三層子樹中的節(jié)點與第二層的父節(jié)點也具有相同的度量距離。

基于度量空間的性質(zhì)以及BK樹的特點，文獻[14]提出了一種有效的剪枝策略，可高效地實現(xiàn)多維空間中關(guān)鍵數(shù)據(jù)的搜索。需要注意的是，在常見的索引結(jié)構(gòu)中，相似性查詢有兩種常用的方式，分別為K近鄰查詢和范圍查詢。對于一個詢問q,q∈X，搜索BK樹的索引得到的結(jié)果數(shù)據(jù)集Y應(yīng)滿足d(q,x)≤θd,?x∈Y。這表明結(jié)果數(shù)據(jù)集元素與詢問的度量距離滿足閾值θd范圍的數(shù)據(jù)，可認為是一種范圍查詢方式。

Fig.1　Three layer structure of BK-tree圖1　三層BK樹結(jié)構(gòu)圖

3.2基于BK樹的擴展置信規(guī)則庫構(gòu)建

基于BK樹構(gòu)建EBRB是指基于BK樹對擴展置信規(guī)則建立樹形結(jié)構(gòu)的索引。首先需要選擇一個合適的度量空間對擴展置信規(guī)則進行度量。本文選擇常見的歐氏距離作為度量距離并進行標準化，度量Rp和Rq兩條規(guī)則的具體方法如下：

其中，擴展置信規(guī)則的前提屬性均為分布式置信度的形式，第k條規(guī)則的第i個前提屬性表示為。在對規(guī)則進行度量后即可建立基于BK樹的擴展置信規(guī)則間的索引，具體步驟如下：

步驟2計算Rn和集合中剩余規(guī)則的度量距離，將剩余規(guī)則劃分為m+1個子集合R0,R1,…,Rm，其中d(Rn,r)=i,?r∈Ri，依次對每個子集合執(zhí)行步驟3。

步驟3從集合Ri(i=0,1,…,m)中隨意選擇一條規(guī)則，建立其與Rn的索引并將其作為新的Rn。若子集合Ri的元素個數(shù)大于1，即，則執(zhí)行步驟2，否則不做處理。

通過上述遞歸的算法步驟可以完成BK樹的構(gòu)建，從而將原本無序存儲的擴展置信規(guī)則在一個度量空間中建立起樹形結(jié)構(gòu)的索引。假設(shè)現(xiàn)在有5條規(guī)則，規(guī)則只有1個前提屬性，前提屬性有兩個參考值，度量距離為歐氏距離，5條規(guī)則在規(guī)則前件部分分別為：（0.4，0.6）、（0.5，0.5）、（0.3，0.7）、（0.2，0.8）和（0.6，0.4）。圖2給出了對這5條規(guī)則建立BK樹形索引的一種可能結(jié)構(gòu)。

Fig.2　Index structure of 5 rules圖2　5條規(guī)則索引結(jié)構(gòu)圖

3.3基于BK樹的擴展置信規(guī)則庫搜索

構(gòu)建完基于BK樹的EBRB后，接著介紹基于BK樹的EBRB搜索策略。假設(shè)輸入數(shù)據(jù)為X，則在基于BK樹的EBRB中搜索滿足d(Rn,X)≤θd的規(guī)則，并將其作為激活規(guī)則用于推理最終的決策結(jié)果，其中具體搜索步驟如下：

步驟1設(shè)置閾值θd，計算當前規(guī)則Rn和X的度量距離，令d=d(Rn,X)。若d≤θd則說明Rn可能被激活。

步驟2進行m+1次判斷，m+1表示以當前節(jié)點為根的子樹個數(shù)，若滿足剪枝策略, k=0,1,…,m，則將第k棵子樹的根節(jié)點規(guī)則作為新的Rn執(zhí)行步驟3，否則不做處理。其中，dk表示Rn和第k棵子樹中規(guī)則的度量距離。

步驟3計算當前規(guī)則Rn和X的度量距離更新d，若d≤θd，則說明Rn可能被激活，然后執(zhí)行步驟2。

在對基于BK樹的EBRB進行激活規(guī)則搜索時，利用“三角形不等式性質(zhì)”可以得到步驟2中的剪枝策略。根據(jù)剪枝策略只搜索可能滿足d≤θd條件的規(guī)則，減少了搜索規(guī)則的數(shù)量，從而提高EBRB系統(tǒng)推理的效率。以3.2節(jié)中的5條規(guī)則為例，現(xiàn)假設(shè)閾值θd=0.2，輸入X為(0.45,0.55)。根據(jù)式（19）計算根節(jié)點規(guī)則和X的度量距離可得d=0.07，因此該規(guī)則可能被激活。然后根據(jù)剪枝策略可得左子樹的結(jié)果為，而右子樹的結(jié)果為，因此只對滿足剪枝策略的左子樹搜索而不對右子樹搜索。隨后計算節(jié)點(0.5,0.5)和X的度量距離可得d=0.07，因此該規(guī)則可能被激活，然后根據(jù)剪枝策略可得子樹的結(jié)果為，從而不繼續(xù)對子樹中的規(guī)則進行搜索。

3.4結(jié)構(gòu)優(yōu)化框架下的規(guī)則推理

通過搜索得到可能被激活的規(guī)則集合后，需計算規(guī)則的激活權(quán)重。根據(jù)式（6）～（7）易知個體匹配度計算結(jié)果可能為負值，因此，本文提出改進的個體匹配度計算公式，改進后公式如下所示：

由式（2）～（5）可將定量輸入值X轉(zhuǎn)換為分布式形式，經(jīng)式（20）可得輸入值X與第k條規(guī)則的距離。此外，規(guī)則的不一致性極易影響EBRB系統(tǒng)的推理性能，由于在知識表示或獲取時可能導致置信規(guī)則間存在不一致性，與此同時，當用歷史數(shù)據(jù)產(chǎn)生置信規(guī)則時規(guī)則的不一致性還與噪聲數(shù)據(jù)相關(guān)，因此規(guī)則推理時需采取適當?shù)姆椒ㄏ?guī)則間的不一致性。本文采用文獻[13]中的方法對規(guī)則的一致性問題進行處理。

由式（20）、（7）和（8）確定完激活規(guī)則后，根據(jù)ER方法對規(guī)則進行組合，得到評價結(jié)果的置信度分布情況，再計算效用值得到最后EBRB系統(tǒng)的推理結(jié)果。為方便敘述，下文將基于BK樹的結(jié)構(gòu)優(yōu)化框架和EBRB系統(tǒng)相結(jié)合的系統(tǒng)稱為BK-EBRB系統(tǒng)，其中BK-EBRB系統(tǒng)的流程如圖3所示。

由圖3可知結(jié)構(gòu)優(yōu)化框架是獨立于EBRB系統(tǒng)的優(yōu)化框架，其沒有改變EBRB系統(tǒng)的參數(shù)值，可見基于BK樹的結(jié)構(gòu)優(yōu)化框架易與其他具備信度框架的決策模型相結(jié)合。

表2對Liu-EBRB系統(tǒng)與BK-EBRB系統(tǒng)的復雜度進行比較。從表2中可以發(fā)現(xiàn)，BK-EBRB系統(tǒng)相比Liu-EBRB系統(tǒng)在構(gòu)建系統(tǒng)時因為需要構(gòu)建樹形索引結(jié)構(gòu)，所以復雜度更高，而當查詢激活規(guī)則時BK-EBRB系統(tǒng)無需對規(guī)則遍歷，可以高效地搜索近鄰規(guī)則，相比Liu-EBRB系統(tǒng)具有更低的復雜度，當詢問個數(shù)越多時，BK-EBRB系統(tǒng)的表現(xiàn)越好。

Fig.3　Flow chart of BK-EBRB system圖3　BK-EBRB系統(tǒng)流程圖

Table 2　Complexity comparison between Liu-EBRB system and BK-EBRB system表2　Liu-EBRB系統(tǒng)與BK-EBRB系統(tǒng)的復雜度比較

4　示例分析

為驗證本文方法，引入非線性函數(shù)、輸油管道泄漏兩個實例以及多個分類數(shù)據(jù)集。實驗環(huán)境為：Intel?CoreTMi5-4570 CPU@3.20 GHz；4 GB內(nèi)存；Windows 8操作系統(tǒng)；算法實現(xiàn)平臺Matlab R2012b與Visual Studio 2013。

4.1函數(shù)擬合問題

文獻[13]證明了EBRB系統(tǒng)是通用逼近器，可以逼近任意非線性映射。本節(jié)將通過一個非線性數(shù)學函數(shù)來檢驗BK-EBRB系統(tǒng)的推理性能和效率，并與Yang的涉及局部參數(shù)學習的BRB系統(tǒng)[8]和Chen的涉及全局參數(shù)學習的BRB系統(tǒng)[9]進行比較。為方便敘述，以下分別簡稱為Yang-BRB系統(tǒng)和Chen-BRB系統(tǒng)。

非線性數(shù)學函數(shù)如下所示：

構(gòu)建EBRB時，x為前提屬性，并且具有7個參考值{0,0.5,1.0,1.5,2.0,2.5,3.0}，結(jié)果等級數(shù)目為5，相對應(yīng)的等級效用值依次為{-2.5,-1.0,2.0,3.0}。在x的取值范圍內(nèi)均勻地選擇500個數(shù)值，并根據(jù)式（21）得到對應(yīng)函數(shù)的真實值，再根據(jù)前文所提方法構(gòu)建BK-EBRB。其中閾值θd根據(jù)經(jīng)驗設(shè)定為0.01，測試數(shù)據(jù)為在x的取值范圍內(nèi)均勻選擇的1 000組數(shù)據(jù)。

從圖4中可以發(fā)現(xiàn)，Yang-BRB系統(tǒng)的模擬輸出與數(shù)學函數(shù)的真實輸出存在明顯的差距，擬合效果并不理想；圖5中Chen-BRB系統(tǒng)的模擬輸出與數(shù)學函數(shù)的真實輸出差距不大，僅在極大極小值處存在明顯欠擬合問題，整體上具有較好的擬合效果；圖6中BK-EBRB系統(tǒng)的模擬輸出與數(shù)學函數(shù)的真實輸出差距不大，能夠很好地擬合該數(shù)學函數(shù)。

表3對3種方法測試結(jié)果及運行時間進行了比較。其中，Yang-BRB系統(tǒng)和Chen-BRB系統(tǒng)均運用Matlab工具箱中的FMINCON函數(shù)對BRB系統(tǒng)的參數(shù)進行學習，而BK-EBRB系統(tǒng)是將本文提出的BK樹結(jié)構(gòu)優(yōu)化框架與數(shù)據(jù)驅(qū)動的EBRB方法相結(jié)合，并未進行參數(shù)學習。從表3中可以發(fā)現(xiàn)，BK-EBRB系統(tǒng)的模擬輸出與真實值間的MSE為3種方法中最小的，在未進行參數(shù)學習情況下BK-EBRB系統(tǒng)也具有良好的推理能力。而參數(shù)學習是一個反復迭代的過程，需要大量的時間。因此，BK-EBRB系統(tǒng)的運行時間最短，與其他兩種方法相比極大地提高了系統(tǒng)的效率。

Fig.4　Function fitting chart of Yang-BRB system圖4　Yang-BRB系統(tǒng)函數(shù)擬合圖

Fig.5　Function fitting chart of Chen-BRB system圖5　Chen-BRB系統(tǒng)函數(shù)擬合圖

Fig.6　Function fitting chart of BK-EBRB system圖6　BK-EBRB系統(tǒng)函數(shù)擬合圖

Table 3　Performance comparison of BRB system in function fitting表3　函數(shù)擬合BRB系統(tǒng)推理性能比較

4.2輸油管道泄漏問題

以一個具體的實際問題——輸油管道泄漏作為研究對象[9,19-21]，通過使用輸油管道泄漏的真實泄漏數(shù)據(jù)對本文提出的BK-EBRB系統(tǒng)性能進行驗證。在該實際問題中，當輸油管道發(fā)生泄漏時，輸油管道中油液的流量和壓力會發(fā)生變化。因此，選擇輸油管道輸入和輸出的流量差（flow difference,FD）以及油液對管道產(chǎn)生的平均壓力差（pressure difference,PD）對泄漏大?。╨eak size,LS）進行估計。

在構(gòu)造EBRB時，選取了2 008組從無泄漏到發(fā)生25%泄漏狀況的數(shù)據(jù)作為實驗數(shù)據(jù)。因為FD和PD可以反映輸油管道泄漏情況，所以系統(tǒng)的輸入為FD和PD，而LZ則為輸出。其中，根據(jù)專家經(jīng)驗得到前提屬性FD有8個參考值，分別為{-10,-5,-3,-1, 0,1,2,3}；PD有7個參考值，分別為{-0.042,-0.025, -0.010,0,0.010,0.025,0.042}；輸出LZ則有5個評價等級，分別為{0,2,4,6,8}。

在2 008組數(shù)據(jù)中，根據(jù)文獻[9]的方法按照一定比例從3個時間段隨機選擇總共1 500條數(shù)據(jù)作為訓練數(shù)據(jù)，產(chǎn)生置信規(guī)則，然后按照Liu的方法[13]和本文方法分別構(gòu)造Liu-EBRB系統(tǒng)和BK-EBRB系統(tǒng)進行比較，并以平均絕對誤差（mean absolute difference, MAE）作為評價指標。

圖7和圖8分別將Liu-EBRB系統(tǒng)和BK-EBRB系統(tǒng)（theta=0.4，theta即θd）產(chǎn)生的模擬輸出與真實數(shù)據(jù)進行比較。兩種方法均根據(jù)訓練數(shù)據(jù)產(chǎn)生EBRB，后者引入基于BK樹的優(yōu)化框架。從圖中可以發(fā)現(xiàn)BK-EBRB系統(tǒng)能較好地對輸油管道泄漏情況進行檢測，得到與真實值接近的結(jié)果。而當PD∈[-0.02,0]且FD∈[-10,-5]時，Liu-EBRB系統(tǒng)產(chǎn)生的模擬輸出與真實值存在較大差距，BK-EBRB系統(tǒng)的模擬輸出則更接近真實的情況。其主要是因為BKEBRB系統(tǒng)對置信規(guī)則建立基于BK樹的索引，同時設(shè)置了閾值，進而減少了激活規(guī)則的數(shù)量。另一方面，由于僅對關(guān)鍵規(guī)則進行組合，減少了不一致規(guī)則對最終結(jié)果的影響，提高了系統(tǒng)的推理能力。

Fig.7　Liu-EBRB system output and test data圖7　Liu-EBRB系統(tǒng)輸出和測試數(shù)據(jù)

Fig.8　BK-EBRB system output and test data圖8　BK-EBRB系統(tǒng)輸出和測試數(shù)據(jù)

表4列出了Liu-EBRB系統(tǒng)和3個設(shè)置不同閾值的BK-EBRB系統(tǒng)產(chǎn)生的模擬輸出與真實值間的MAE以及各自進行推理時搜索規(guī)則的次數(shù)。圖9以柱狀圖的形式更形象地對4個EBRB系統(tǒng)在規(guī)則推理時的搜索規(guī)則次數(shù)進行比較?？梢园l(fā)現(xiàn)當BKEBRB系統(tǒng)的閾值設(shè)置為1.0時，BK-EBRB系統(tǒng)和Liu-EBRB系統(tǒng)具有相同的MAE并且搜索規(guī)則的次數(shù)一致。這是因為Liu-EBRB系統(tǒng)需要對置信規(guī)則進行完整的遍歷，而當閾值為1.0時，剪枝策略沒有發(fā)揮作用，BK-EBRB系統(tǒng)仍需遍歷所有的規(guī)則。當BK-EBRB系統(tǒng)的閾值小于1.0時，搜索規(guī)則次數(shù)減少。因為當閾值小于1.0時，剪枝策略將發(fā)揮作用，可以縮小搜索規(guī)則的范圍，減少搜索規(guī)則的數(shù)量，從而提高EBRB系統(tǒng)的推理效率。由表4還可以發(fā)現(xiàn)，相較于Liu-EBRB系統(tǒng)，BK-EBRB系統(tǒng)獲得了更小的MAE，具有更好的推理能力。這是因為BK-EBRB系統(tǒng)通過閾值的設(shè)置，激活更為關(guān)鍵的規(guī)則進行組合，從而提升了EBRB系統(tǒng)的推理能力。

Table 4　Performance comparison of EBRB system in oil pipeline leak detection表4　輸油管道泄漏檢測EBRB系統(tǒng)推理性能比較

Fig.9　Search rules times in EBRB systems inference圖9　EBRB系統(tǒng)進行推理搜索規(guī)則次數(shù)

通過輸油管道泄漏實例對Liu-EBRB系統(tǒng)和BKEBRB系統(tǒng)進行比較，表明基于BK樹的結(jié)構(gòu)優(yōu)化框架在提高EBRB系統(tǒng)推理效率的同時也可使EBRB系統(tǒng)能夠更準確地反映系統(tǒng)的行為。

4.3分類數(shù)據(jù)集測試

為了驗證本文方法的有效性，從UCI上選擇了9個著名的分類數(shù)據(jù)集進行測試。通過5折交叉驗證的方法，構(gòu)造訓練數(shù)據(jù)和測試數(shù)據(jù)。每個前提屬性都根據(jù)數(shù)據(jù)范圍設(shè)置6個均勻分布的參考值，評價結(jié)果數(shù)與分類數(shù)一致，以此根據(jù)數(shù)據(jù)產(chǎn)生擴展置信規(guī)則。然后根據(jù)本文方法構(gòu)造4個BK-EBRB系統(tǒng)，并分別設(shè)置閾值theta為1.0，0.8，0.6和0.4，度量距離為歐氏距離，實驗結(jié)果如表5所示。從表中可以發(fā)現(xiàn)，在大部分數(shù)據(jù)集上隨著閾值的減小，BK-EBRB系統(tǒng)的推理準確性獲得了提高，具有更好的分類準確度，這表明通過閾值設(shè)置激活關(guān)鍵規(guī)則可以提高系統(tǒng)的推理能力。BK-EBRB系統(tǒng)在Ecoli、Knowledge和Yeast這3個數(shù)據(jù)集上性能提升效果最為明顯，而在Breast和Glass這兩個數(shù)據(jù)集上，BK-EBRB系統(tǒng)的推理準確性呈現(xiàn)出先升高后降低的情況。閾值的設(shè)置會影響B(tài)K-EBRB系統(tǒng)的推理性能，合理的閾值將會使系統(tǒng)具有更好的推理性能，反之將會降低系統(tǒng)的推理性能。從表中可以發(fā)現(xiàn)，不同數(shù)據(jù)集相同閾值的推理能力不一致，應(yīng)根據(jù)數(shù)據(jù)集的自身結(jié)構(gòu)特點設(shè)置不同的閾值。閾值的設(shè)置可以通過枚舉的方法對不同系統(tǒng)的推理性能進行比較，選擇具有最優(yōu)推理準確性系統(tǒng)對應(yīng)的閾值，也可以將該問題視為一個最優(yōu)化問題，并通過相關(guān)方法進行求解得到最優(yōu)閾值。

Table 5　Performance comparison of BK-EBRB systems on benchmarks表5　分類數(shù)據(jù)集上BK-EBRB系統(tǒng)推理性能比較

5　結(jié)束語

針對現(xiàn)有EBRB系統(tǒng)中因規(guī)則以無序的方式存儲，導致在推理時需采用遍歷EBRB內(nèi)所有規(guī)則的方式計算激活權(quán)重，從而產(chǎn)生系統(tǒng)推理效率不理想的問題，本文提出了一種基于BK樹的EBRB系統(tǒng)結(jié)構(gòu)優(yōu)化框架。

本文的優(yōu)化框架通過對規(guī)則建立基于BK樹的索引結(jié)構(gòu)減少搜索EBRB中規(guī)則的數(shù)量；另一方面，通過設(shè)定合適的閾值篩選出更具有代表性的規(guī)則用于規(guī)則組合，提高EBRB系統(tǒng)的推理效率。此外，該結(jié)構(gòu)優(yōu)化框架還易與其他具有信度框架的決策模型相結(jié)合，具有良好的擴展性。示例分析中，通過在函數(shù)擬合問題和輸油管道泄漏問題中與各類BRB/ EBRB系統(tǒng)進行對比，驗證了本文方法能夠提升EBRB系統(tǒng)的效率和決策性能；通過對多個分類數(shù)據(jù)集進行測試，進一步驗證了方法有效性，并簡單分析了閾值設(shè)置方法。在今后的研究工作中，將對合理設(shè)置閾值、激活置信規(guī)則及置信規(guī)則間一致性問題做進一步的研究，以期提出推理性能良好且更合理的BRB構(gòu)建和推理方法。

References:

[1]Dempster A P.A generalization of Bayesian inference[J]. Journal of the Royal Statistical Society:Series B Methodological,1968,30(2):205-247.

[2]Shafer G.A mathematical theory of evidence[M].Princeton,USA:Princeton university press,1976.

[3]Wang C L,Yoon K S.Multiple attribute decision making[J].Berlin:Springer-Verlag,1981.

[4]Zadeh L A.Fuzzy sets[J].Information and Control,1965,8 (3):338-353.

[5]Sun R.Robust reasoning:integrating rule-based and similaritybased reasoning[J].Artificial Intelligence,1995,75(2):241-295.

[6]Yang Jianbo,Liu Jun,Wang Jin,et al.Belief rule-base inference methodology using the evidential reasoning approach-RIMER[J].IEEE Transactions on Systems,Man and Cybernetics:PartASystems and Humans,2006,36(2):266-285.

[7]Huysmans J,Dejaeger K,Mues C,et al.An empirical evaluation of the comprehensibility of decision table,tree and rule based predictive models[J].Decision Support Systems, 2011,51(1):141-154.

[8]Yang Jianbo,Liu Jun,Xu Dongling,et al.Optimization models for training belief-rule-based systems[J].IEEE Transactions on Systems,Man and Cybernetics:Part A Systems and Humans,2007,37(4):569-585.

[9]Chen Yuwang,Yang Jianbo,Xu Dongling,et al.Inference analysis and adaptive training for belief rule based systems[J]. Expert Systems with Applications,2011,38(10):12845-12860.

[10]Liu Jun,Martinez L,Ruan Da,et al.Optimization algorithm for learning consistent belief rule-base from examples[J]. Journal of Global Optimization,2011,51(2):255-270.

[11]Chang Leilei,Sun Jianbin,Jiang Jiang,et al.Parameter learning for the belief rule base system in the residual life probability prediction of metalized film capacitor[J].Knowledge-Based Systems,2015,73:69-80.

[12]Su Qun,Yang Longhao,Fu Yanggeng,et al.Parameter training approach based on variable particle swarm optimization for belief rule base[J].Journal of Computer Applications,2014, 34(8):2161-2165.

[13]Liu Jun,Martinez L,Calzada A,et al.A novel belief rule base representation,generation and its inference methodology[J].Knowledge-Based Systems,2013,53:129-141.

[14]Burkhard W A,Keller R M.Some approaches to best-match file searching[J].Communications of the ACM,1973,16(4): 230-236.

[15]Chávez E,Navarro G,Baeza-Yates R,et al.Searching in metric spaces[J].ACM Computing Surveys,2001,33(3):273-321.

[16]Yang Jianbo.Rule and utility based evidential reasoning approach for multiattribute decision analysis under uncertainties[J].European Journal of Operational Research, 2001,131(1):31-61.

[17]Yang Jianbo,Xu Dongling.On the evidential reasoning algorithm for multiple attribute decision analysis under uncertainty[J].IEEE Transactions on Systems,Man and Cybernetics:PartASystems and Humans,2002,32(3):289-304.

[18]Chen Yuwang,Yang Jianbo,Xu Dongling,et al.On the inference and approximation properties of belief rule based systems[J].Information Sciences,2013,234:121-135.

[19]Xu Dongling,Liu Jun,Yang Jianbo,et al.Inference and learning methodology of belief-rule-based expert system for pipeline leak detection[J].Expert Systems with Applications,2007,32(1):103-113.

[20]Zhou Zhijie,Hu Changhua,Yang Jianbo,et al.Online updating belief rule based system for pipeline leak detection under expert intervention[J].Expert Systems with Applications,2009,36(4):7700-7709.

[21]Zhou Zhijie,Yang Jianbo,Hu Changhua.Confidence expert system rule base and complex system modeling[M].Beijing:Science Press,2011.

附中文參考文獻：

[12]蘇群,楊隆浩,傅仰耿,等.基于變速粒子群優(yōu)化的置信規(guī)則庫參數(shù)訓練方法[J].計算機應(yīng)用,2014,34(8):2161-2165.

[21]周志杰,楊劍波,胡昌華.置信規(guī)則庫專家系統(tǒng)與復雜系統(tǒng)建模[M].北京:科學出版社,2011.

SU Qun was born in 1991.He is an M.S.candidate at College of Mathematics and Computer Science,Fuzhou University.His research interests include intelligent decision-making technology and belief rule base inference,etc.

蘇群（1991—），男，福建寧德人，福州大學數(shù)學與計算機科學學院碩士研究生，主要研究領(lǐng)域為智能決策技術(shù)，置信規(guī)則庫推理等。

YANG Longhao was born in 1990.He is a Ph.D.candidate at College of Economics and Management,Fuzhou University.His research interests include intelligent decision-making technology and belief rule base inference,etc.

楊隆浩（1990—），男，福建南平人，福州大學經(jīng)濟與管理學院博士研究生，主要研究領(lǐng)域為智能決策技術(shù)，置信規(guī)則庫推理等。

傅仰耿（1981—），男，福建泉州人，2013年于福州大學獲得博士學位，現(xiàn)為福州大學數(shù)學與計算機科學學院講師，CCF會員，主要研究領(lǐng)域為不確定多準則決策，置信規(guī)則庫推理，移動互聯(lián)網(wǎng)應(yīng)用等。

YU Ruiyin was born in 1990.He is an M.S.candidate at College of Mathematics and Computer Science,Fuzhou University.His research interests include intelligent decision-making technology and belief rule base inference,etc.

余瑞銀（1990—），男，福建福州人，福州大學數(shù)學與計算機科學學院碩士研究生，主要研究領(lǐng)域為智能決策技術(shù)，置信規(guī)則庫推理等。

Structure Optimization Framework of Extended Belief Rule Base Based on BK-Tree*

SU Qun1,YANG Longhao2,FU Yanggeng1+,YU Ruiyin1
1.College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350116,China
2.College of Economics and Management,Fuzhou University,Fuzhou 350116,China
+Corresponding author:E-mail:ygfu@qq.com

To the problem of undesirable inference efficiency in extended belief rule base(EBRB)with large number of rules,this paper introduces BK-tree data structure and proposes a structure optimization framework based on BK-tree.Firstly,the index with tree structure of EBRB is made by the metric distance between the belief rules in the metric space.By setting the threshold,reducing the number of search rules and activating the key rules,the reasoning efficiency of the EBRB system is improved.Finally,simulation experiments on a nonlinear function,a practical pipeline leak detection problem and multiple classification data sets are conducted to validate the performance of the optimization framework combined with EBRB system.The experimental results show the proposed method can be used to optimize the reasoning efficiency and decision accuracy of the EBRB system.

extended belief rule base(EBRB);evidential reasoning(ER);BK-tree;optimization framework

2015-05,Accepted 2015-09.

FU Yanggeng was born in 1981.He the Ph.D.degree from Fuzhou University in 2013.Now he is a lecturer at College of Mathematics and Computer Science,Fuzhou University,and the member of CCF.His research interests include multi-criteria decision making under uncertainty,belief rule base inference and mobile Internet applications,etc.

10.3778/j.issn.1673-9418.1505065

*The National Natural Science Foundation of China under Grant Nos.61300026,71371053,71501047(國家自然科學基金);the Natural Science Foundation of Fujian Province under Grant No.2015J01248(福建省自然科學基金);the Science and Technology Project of Fujian Education Department under Grant No.JA13036(福建省教育廳科技項目);the Science and Technology Development Foundation of Fuzhou University under Grant No.2014-XQ-26(福州大學科技發(fā)展基金項目).

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-09-15,http://www.cnki.net/kcms/detail/11.5602.TP.20150915.1347.004.html

A

TP18；TP273.5