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

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

1.福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福州 350116

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

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

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

1.福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福州 350116

2.福州大學(xué) 經(jīng)濟(jì)與管理學(xué)院，福州 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.

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

擴(kuò)展置信規(guī)則庫(kù)（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ī)則庫(kù)[5]的基礎(chǔ)上提出了基于證據(jù)推理算法的置信規(guī)則庫(kù)推理方法[6]（belief rule base inference methodology using the evidential reasoning approach，RIMER）。相比于神經(jīng)網(wǎng)絡(luò)算法和支持向量機(jī)等“黑箱”方法，RIMER方法的推理過(guò)程具有更好的解釋性和透明性[7]。

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

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

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

2.1擴(kuò)展置信規(guī)則庫(kù)的表示

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

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

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

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

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

通過(guò)式（2）～（5）產(chǎn)生擴(kuò)展置信規(guī)則的前件部分，與輸入xi相對(duì)應(yīng)的輸出yi可采用同樣的方法產(chǎn)生評(píng)價(jià)結(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擴(kuò)展置信規(guī)則庫(kù)的推理

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

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

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

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

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

3.1Burkhard-Keller樹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在對(duì)基于BK樹的EBRB進(jìn)行激活規(guī)則搜索時(shí)，利用“三角形不等式性質(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）計(jì)算根節(jié)點(diǎn)規(guī)則和X的度量距離可得d=0.07，因此該規(guī)則可能被激活。然后根據(jù)剪枝策略可得左子樹的結(jié)果為，而右子樹的結(jié)果為，因此只對(duì)滿足剪枝策略的左子樹搜索而不對(duì)右子樹搜索。隨后計(jì)算節(jié)點(diǎn)(0.5,0.5)和X的度量距離可得d=0.07，因此該規(guī)則可能被激活，然后根據(jù)剪枝策略可得子樹的結(jié)果為，從而不繼續(xù)對(duì)子樹中的規(guī)則進(jìn)行搜索。

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

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

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

由式（20）、（7）和（8）確定完激活規(guī)則后，根據(jù)ER方法對(duì)規(guī)則進(jìn)行組合，得到評(píng)價(jià)結(jié)果的置信度分布情況，再計(jì)算效用值得到最后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)化框架是獨(dú)立于EBRB系統(tǒng)的優(yōu)化框架，其沒(méi)有改變EBRB系統(tǒng)的參數(shù)值，可見基于BK樹的結(jié)構(gòu)優(yōu)化框架易與其他具備信度框架的決策模型相結(jié)合。

表2對(duì)Liu-EBRB系統(tǒng)與BK-EBRB系統(tǒng)的復(fù)雜度進(jìn)行比較。從表2中可以發(fā)現(xiàn)，BK-EBRB系統(tǒng)相比Liu-EBRB系統(tǒng)在構(gòu)建系統(tǒng)時(shí)因?yàn)樾枰獦?gòu)建樹形索引結(jié)構(gòu)，所以復(fù)雜度更高，而當(dāng)查詢激活規(guī)則時(shí)BK-EBRB系統(tǒng)無(wú)需對(duì)規(guī)則遍歷，可以高效地搜索近鄰規(guī)則，相比Liu-EBRB系統(tǒng)具有更低的復(fù)雜度，當(dāng)詢問(wèn)個(gè)數(shù)越多時(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)的復(fù)雜度比較

4　示例分析

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

4.1函數(shù)擬合問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5　結(jié)束語(yǔ)

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

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

附中文參考文獻(xiàn)：

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

[21]周志杰,楊劍波,胡昌華.置信規(guī)則庫(kù)專家系統(tǒng)與復(fù)雜系統(tǒng)建模[M].北京:科學(xué)出版社,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—），男，福建寧德人，福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)橹悄軟Q策技術(shù)，置信規(guī)則庫(kù)推理等。

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—），男，福建南平人，福州大學(xué)經(jīng)濟(jì)與管理學(xué)院博士研究生，主要研究領(lǐng)域?yàn)橹悄軟Q策技術(shù)，置信規(guī)則庫(kù)推理等。

傅仰耿（1981—），男，福建泉州人，2013年于福州大學(xué)獲得博士學(xué)位，現(xiàn)為福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院講師，CCF會(huì)員，主要研究領(lǐng)域?yàn)椴淮_定多準(zhǔn)則決策，置信規(guī)則庫(kù)推理，移動(dòng)互聯(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—），男，福建福州人，福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)橹悄軟Q策技術(shù)，置信規(guī)則庫(kù)推理等。

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(國(guó)家自然科學(xué)基金);the Natural Science Foundation of Fujian Province under Grant No.2015J01248(福建省自然科學(xué)基金);the Science and Technology Project of Fujian Education Department under Grant No.JA13036(福建省教育廳科技項(xiàng)目);the Science and Technology Development Foundation of Fuzhou University under Grant No.2014-XQ-26(福州大學(xué)科技發(fā)展基金項(xiàng)目).

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