利用聚類(lèi)分析構(gòu)建基于析取范式的置信規(guī)則庫(kù)

張 婕，傅仰耿，鞏曉婷

(1. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 福建 福州 350108; 2. 福州大學(xué)決策科學(xué)研究所, 福建 福州 350108)

0 引言

2006年，文獻(xiàn)[1] 提出了基于證據(jù)推理的置信規(guī)則庫(kù)推理方法(belief rule base inference methodology using the evidence reasoning，RIMER). 該方法基于傳統(tǒng)的IF-THEN規(guī)則表達(dá)式，引入置信框架，涵蓋了證據(jù)理論[2]、 決策理論[3]、 模糊集理論[4]等，主要用來(lái)處理不確定、 不完備問(wèn)題. 經(jīng)過(guò)多年的研究發(fā)展，置信規(guī)則庫(kù)(belief rule base, BRB)已經(jīng)成功應(yīng)用在輸油管道檢漏[5]、 橋梁風(fēng)險(xiǎn)評(píng)估[6]、 石墨成分分析[7]、 臨床診斷等方面. 文獻(xiàn)[1]在構(gòu)建BRB時(shí)，提出基于合取范式的置信規(guī)則庫(kù)(conjunctive belief rule base, CBRB)和基于析取范式的置信規(guī)則庫(kù)(disjunctive belief rule base, DBRB). 為了更好地進(jìn)行多屬性決策，文獻(xiàn)[8]首次將DBRB應(yīng)用在分類(lèi)問(wèn)題中，不僅能保證信息的完整性, 同時(shí)能有效減少系統(tǒng)的規(guī)則數(shù)，避免“組合爆炸”的問(wèn)題.

目前，DBRB構(gòu)建方法的研究主要包括，文獻(xiàn)[9]提出的基于赤池信息量化標(biāo)準(zhǔn)的規(guī)則數(shù)和規(guī)則參數(shù)聯(lián)合優(yōu)化方法，但該方法衡量指標(biāo)單一，構(gòu)建的系統(tǒng)易出現(xiàn)過(guò)擬合現(xiàn)象； 文獻(xiàn)[10]利用霍夫丁不等式推導(dǎo)BRB系統(tǒng)的泛化誤差，用于CBRB和DBRB的構(gòu)建，但該方法存在依賴(lài)人為因素的問(wèn)題； 文獻(xiàn)[11]針對(duì)DBRB在分類(lèi)問(wèn)題上的應(yīng)用，提出將系統(tǒng)的規(guī)則數(shù)目設(shè)置為問(wèn)題的分類(lèi)數(shù)，進(jìn)行規(guī)則庫(kù)構(gòu)建，但該方法僅適用于結(jié)果數(shù)目確定的分類(lèi)問(wèn)題，且回歸問(wèn)題結(jié)果評(píng)價(jià)等級(jí)大多是人為確定的，問(wèn)題規(guī)模較大時(shí)專(zhuān)家無(wú)法提供準(zhǔn)確的評(píng)價(jià)等級(jí).

針對(duì)上述問(wèn)題，本研究提出利用聚類(lèi)分析構(gòu)建基于析取范式的置信規(guī)則庫(kù)的新方法. 通過(guò)聚類(lèi)DBRB相關(guān)參數(shù)，進(jìn)而確定系統(tǒng)規(guī)模，且無(wú)需依賴(lài)專(zhuān)家經(jīng)驗(yàn)，充分利用已知數(shù)據(jù)完成規(guī)則庫(kù)構(gòu)建. 為說(shuō)明所提方法的合理有效，以輸油管道檢漏和橋梁風(fēng)險(xiǎn)評(píng)估兩個(gè)實(shí)驗(yàn)為背景對(duì)方法進(jìn)行驗(yàn)證，同時(shí)與其他方法進(jìn)行對(duì)比，由實(shí)驗(yàn)結(jié)果可知，本研究方法在規(guī)則庫(kù)構(gòu)建方面相對(duì)于其他方法推理性能有所提高.

1 DBRB專(zhuān)家系統(tǒng)

1.1 DBRB表示

DBRB在傳統(tǒng)BRB的基礎(chǔ)上，通過(guò)‘∨’連接屬性，具體的規(guī)則表達(dá)形式如式(1)所示：

(1)

1.2 DBRB推理機(jī)制

DBRB系統(tǒng)的推理機(jī)制主要是采用RIMER方法，該方法對(duì)于每個(gè)輸入信息x激活的規(guī)則，采用證據(jù)理論(evidence reasoning，ER)方法進(jìn)行合成，從而獲得推理結(jié)果，主要包括兩個(gè)步驟： 激活權(quán)重計(jì)算和基于ER的激活規(guī)則合成.

1.2.1激活權(quán)重計(jì)算

首先計(jì)算輸入信息對(duì)前提屬性候選值的個(gè)體匹配度. 對(duì)于輸入x的第i個(gè)分量xi，可以轉(zhuǎn)化為如下期望形式：

S(xi)={(Ai, j,αi, j),i=1, 2, …,M;j=1, 2, …,Ji}

(2)

其中,αi, j表示輸入xi對(duì)屬性參考值A(chǔ)i, j的隸屬度，規(guī)則權(quán)重計(jì)算如下：

(3)

DBRB的屬性聯(lián)合影響因子計(jì)算如下：

(4)

(5)

1.2.2ER推理合成

采用證據(jù)理論對(duì)規(guī)則進(jìn)行合成，見(jiàn)式(6)，假設(shè)系統(tǒng)效用值為μ={μ(D1),μ(D2), …,μ(DN)}，繼而計(jì)算每個(gè)輸入值的期望輸出，見(jiàn)式(7).

(6)

(7)

2 聚類(lèi)分析

聚類(lèi)通過(guò)對(duì)未標(biāo)記樣本數(shù)據(jù)進(jìn)行訓(xùn)練學(xué)習(xí)，尋找數(shù)據(jù)間的內(nèi)在聯(lián)系，并通過(guò)某種指標(biāo)將關(guān)聯(lián)的數(shù)據(jù)歸為同一個(gè)“簇”[12]. 其中，K-means算法自1965年提出后常被用于解決各種聚類(lèi)問(wèn)題.

2.1 K-means聚類(lèi)方法

K-means是一個(gè)梯度下降尋優(yōu)的過(guò)程，一般取歐式距離作為相似性度量指標(biāo)，誤差平方和(sum of squares for error ，SSE)作為聚類(lèi)目標(biāo)，將樣本集D={x1,x2, …,xi, …,xn}中的數(shù)據(jù)不斷劃分到K個(gè)簇中C={C1,C2, …,Cj, …,Ck}，令簇中的每個(gè)數(shù)據(jù)與所在簇的質(zhì)心距離最?。?/p>

(8)

(9)

(10)

2.2 最優(yōu)K值確定

本研究從數(shù)據(jù)自身聯(lián)系，采用SSE和輪廓系數(shù)S這兩個(gè)指標(biāo)來(lái)確定真實(shí)K范圍[13].

2.2.1誤差平方和

SSE用于衡量樣本點(diǎn)與質(zhì)心間的誤差距離，表現(xiàn)為聚類(lèi)樣本的類(lèi)內(nèi)誤差. 當(dāng)K小于最優(yōu)K值，SSE下降幅度大，而當(dāng)K大于最優(yōu)K值時(shí)，SSE下降緩慢，則可以確定該樣本的最優(yōu)聚類(lèi)數(shù).

2.2.2輪廓系數(shù)法

輪廓系數(shù)法作為評(píng)判聚類(lèi)效果的另一種方法，結(jié)合類(lèi)內(nèi)距離和類(lèi)間距離，計(jì)算每個(gè)樣本與同簇樣本、 最近簇樣本的平均距離作為該樣本的輪廓系數(shù)，求出所有樣本的輪廓系數(shù)平均值即為該聚類(lèi)下的平均輪廓系數(shù)：

(11)

3 置信規(guī)則庫(kù)構(gòu)建

本研究提出基于聚類(lèi)分析的置信規(guī)則庫(kù)構(gòu)建新方法，通過(guò)對(duì)輸出結(jié)果進(jìn)行聚類(lèi)，發(fā)現(xiàn)結(jié)果的分布特征，并根據(jù)聚類(lèi)結(jié)果設(shè)置系統(tǒng)規(guī)則數(shù)等于輸出結(jié)果聚類(lèi)數(shù)目即L=K，結(jié)果評(píng)價(jià)等級(jí)個(gè)數(shù)等于聚類(lèi)數(shù)加2即N=K+2，同時(shí)，將聚類(lèi)質(zhì)心和評(píng)價(jià)等級(jí)上下界設(shè)置為結(jié)果評(píng)價(jià)等級(jí).

Di+1=mi(i=1, 2, …,K)，D1=Dmin，Dk+2=Dmax

(12)

其中:N表示結(jié)果評(píng)價(jià)等級(jí)個(gè)數(shù)，K表示聚類(lèi)數(shù).

采用的聚類(lèi)算法為K-means聚類(lèi)方法，規(guī)則庫(kù)構(gòu)建具體算法流程如下：

步驟1 根據(jù)數(shù)據(jù)規(guī)模，選擇K范圍，一般選取K∈[1, 10].

步驟2 采用K-means聚類(lèi)算法，根據(jù)式(9)～(11)計(jì)算在不同K取值下SSE、 聚類(lèi)中心以及S.

步驟3 根據(jù)計(jì)算結(jié)果，構(gòu)造K與SSE、K與S之間的關(guān)系圖，確定最優(yōu)K值范圍.

步驟4 對(duì)任意K，根據(jù)式(12)構(gòu)建規(guī)則庫(kù)，同時(shí)，在值域范圍內(nèi)設(shè)置各類(lèi)參數(shù)的初始值.

1) 在屬性參考值值域范圍內(nèi)，隨機(jī)生成屬性參考值，并動(dòng)態(tài)設(shè)置屬性參考值的上下界[14]：

(13)

其中, random()表示生成[0, 1]之間的隨機(jī)數(shù).

2) 隨機(jī)生成初始的屬性權(quán)重和規(guī)則權(quán)重.

3) 根據(jù)式(13)設(shè)置結(jié)果評(píng)價(jià)等級(jí)個(gè)數(shù)為K+2，同時(shí)令評(píng)價(jià)結(jié)果等于聚類(lèi)中心和輸出結(jié)果上下界.

4) 對(duì)于系統(tǒng)中第k條規(guī)則，第j個(gè)結(jié)果評(píng)價(jià)等級(jí)的置信度設(shè)置如下：

(14)

步驟5 對(duì)構(gòu)建的DBRB進(jìn)行參數(shù)訓(xùn)練，確定其他參數(shù)取值.

步驟6 分析不同K值DBRB的性能，確定性能最優(yōu)的DBRB 系統(tǒng).

4 實(shí)驗(yàn)驗(yàn)證與分析

為驗(yàn)證本研究方法的有效性，實(shí)驗(yàn)選取輸油管道檢漏和橋梁風(fēng)險(xiǎn)評(píng)估兩個(gè)BRB經(jīng)典案例作為實(shí)驗(yàn)對(duì)象，并與其他方法進(jìn)行對(duì)比. 采用該方法進(jìn)行規(guī)則庫(kù)的構(gòu)建，同時(shí)選取群智能方法作為DBRB參數(shù)學(xué)習(xí)方法，實(shí)驗(yàn)過(guò)程所需參數(shù)設(shè)置如下： 種群大小NP=100，迭代次數(shù)num=50 000. 每個(gè)實(shí)驗(yàn)運(yùn)行300次，取實(shí)驗(yàn)結(jié)果的平均值作為最終結(jié)果. 實(shí)驗(yàn)環(huán)境為： Intel(R) Core i5-4570@ 3.20 GHz； 4 GB 內(nèi)存； Windows 8 操作系統(tǒng)； 算法在 Visual C++ 6.0 編寫(xiě).

4.1 輸油管道檢漏實(shí)驗(yàn)

輸油管道檢漏實(shí)驗(yàn)對(duì)象為英國(guó)一條100多km長(zhǎng)的油氣運(yùn)輸管道，實(shí)驗(yàn)利用管道的流量差異(FD)和平均壓力差(PD)，檢測(cè)管道的泄漏大小(LS). 該實(shí)驗(yàn)共有測(cè)試數(shù)據(jù)2 008組，取其中500組作為訓(xùn)練數(shù)據(jù)，對(duì)輸出結(jié)果進(jìn)行K={1, 2，…，10}的聚類(lèi)，結(jié)果如圖1～2所示. 綜合推理精度、 時(shí)間和空間復(fù)雜度可知，當(dāng)K=4時(shí)，構(gòu)建的規(guī)則庫(kù)系統(tǒng)能夠獲得最佳的推理性能.

圖1 輸油管道中K與SSE關(guān)系圖 Fig.1 K-SSE for pipeline

圖2 輸油管道中K與S關(guān)系圖 Fig.2 K-S for pipeline

將本研究構(gòu)建的DBRB規(guī)則庫(kù)系統(tǒng)與其他方法進(jìn)行比較，該方法構(gòu)建的DBRB與現(xiàn)有的BRB、 EBRB方法相比，不僅能有效減少規(guī)則數(shù)目和參數(shù)個(gè)數(shù)，在節(jié)約時(shí)間和空間資源的同時(shí)，能獲取較高的推理精度； 與Chang-DBRB相比，該方法不僅規(guī)則數(shù)與參數(shù)個(gè)數(shù)均小于Chang-DBRB，且推理精度提升了13%； 與Yang-DBRB相比，當(dāng)K=4時(shí)，本研究雖然參數(shù)個(gè)數(shù)較多，但推理性能提高了3%； 當(dāng)K=3，規(guī)則數(shù)相同的情況下，本研究的推理準(zhǔn)確性高于Yang-DBRB. 從表1對(duì)比結(jié)果可知，該方法能快速確定系統(tǒng)規(guī)模并完成系統(tǒng)構(gòu)建，同時(shí)提高系統(tǒng)的推理準(zhǔn)確度，這說(shuō)明本研究所提方法合理、 有效.

表1 輸油管道: 不同方法BRB推理性能比較

4.2 橋梁風(fēng)險(xiǎn)評(píng)估

橋梁風(fēng)險(xiǎn)評(píng)估作為檢測(cè)BRB系統(tǒng)性能的另一實(shí)驗(yàn)，是以英國(guó)高速公路局的橋梁風(fēng)險(xiǎn)檢測(cè)為背景，通過(guò)分析橋梁的安全性(SA)、 功能性(FU)、 可持續(xù)發(fā)展性(SU)以及周邊環(huán)境(EN)推測(cè)該橋梁的危險(xiǎn)程度(RS). 該實(shí)驗(yàn)共有506組數(shù)據(jù)，其中66組作為訓(xùn)練數(shù)據(jù)，全部506組作為測(cè)試數(shù)據(jù)進(jìn)行實(shí)驗(yàn)比較[18].

根據(jù)文獻(xiàn)[18]，該實(shí)驗(yàn)可以構(gòu)建一個(gè)由5條規(guī)則組合的DBRB系統(tǒng). 考慮到人為因素帶來(lái)的不確定性，因此，選用本研究方法來(lái)確定結(jié)果評(píng)價(jià)等級(jí)和規(guī)則數(shù)以構(gòu)建DBRB系統(tǒng). 同樣，對(duì)66組訓(xùn)練數(shù)的評(píng)價(jià)結(jié)果進(jìn)行聚類(lèi)分析，f選取K={1, 2，…，10}進(jìn)行聚類(lèi)，結(jié)果如圖3～4所示.

圖3 橋梁風(fēng)險(xiǎn)評(píng)估中K與SSE關(guān)系圖Fig.3 Bridge risk assessment-relationship of K and SSE

圖4 橋梁風(fēng)險(xiǎn)評(píng)估中K與S關(guān)系圖Fig.4 Bridge risk assessment-relationship of K and S

從圖3～4可知，取K=5構(gòu)建的DBRB系統(tǒng)在較小的時(shí)間和空間花銷(xiāo)下能獲取較高的推理性能，性能最佳.

另外，由于現(xiàn)有方法構(gòu)建橋梁風(fēng)險(xiǎn)評(píng)估的DBRB系統(tǒng)規(guī)則數(shù)最少達(dá)到5條，因此，取K=5構(gòu)建的DBRB系統(tǒng)與其他方法相比，結(jié)果如表2所示. 其中，Yang-BRB、 Yang-DBRB的規(guī)則數(shù)量分別達(dá)到48條和5條，而采用本研究方法構(gòu)建的DBRB在構(gòu)造5條規(guī)則的情況下可獲得較上述兩種方法更高的推理準(zhǔn)確性，說(shuō)明利用該方法確定結(jié)果評(píng)價(jià)等級(jí)并構(gòu)建的規(guī)則庫(kù)系統(tǒng)是合理有效的.

表2 橋梁風(fēng)險(xiǎn)評(píng)估: 不同方法BRB性能比較

5 結(jié)語(yǔ)

針對(duì)現(xiàn)有DBRB系統(tǒng)構(gòu)建方法存在過(guò)擬合、 依賴(lài)主觀因素、 未合理利用數(shù)據(jù)信息等問(wèn)題，提出基于利用聚類(lèi)分析構(gòu)建基于析取方式的置信規(guī)則庫(kù)的新方法. 通過(guò)對(duì)樣本數(shù)據(jù)的聚類(lèi)分析，取結(jié)果評(píng)價(jià)等級(jí)等于樣本數(shù)據(jù)輸出結(jié)果的聚類(lèi)中心，設(shè)置系統(tǒng)的規(guī)則數(shù)等于聚類(lèi)數(shù)，結(jié)果評(píng)價(jià)等級(jí)個(gè)數(shù)等于聚類(lèi)數(shù)加二，以此確定系統(tǒng)規(guī)模，并充分利用已知信息，通過(guò)對(duì)樣本數(shù)據(jù)的訓(xùn)練學(xué)習(xí)確定系統(tǒng)參數(shù)取值，從而構(gòu)建完整的基于析取方式的置信規(guī)則庫(kù)系統(tǒng). 為驗(yàn)證該方法的合理性，通過(guò)對(duì)輸油管道檢漏和橋梁風(fēng)險(xiǎn)評(píng)估兩個(gè)實(shí)驗(yàn)進(jìn)行研究總結(jié)，充分說(shuō)明本研究所提方法合理有效，并相較現(xiàn)有DBRB構(gòu)建方法具有更高的推理準(zhǔn)確性.