葉青青，楊隆浩，傅仰耿+，陳曉聰

?

基于改進置信規(guī)則庫推理的分類方法*

葉青青1，楊隆浩2，傅仰耿1+，陳曉聰1

1.福州大學數(shù)學與計算機科學學院，福州350116 2.福州大學經(jīng)濟與管理學院，福州350116

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(05)-0709-13

http://www.ceaj.org Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant Nos. 61300026, 71371053, 71501047 (國家自然科學基金); the Natural Sci-ence Foundation of Fujian Province under Grant No. 2015J01248 (福建省自然科學基金); the National Collegiate Innovation and Entrepreneurship Training Program of China under Grant No. 201410386009 (國家級大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目); the Social Science Research Supported Foundation of Fuzhou University under Grant No. 14SKF16 (福州大學社科科研扶持基金).

Received 2015-06,Accepted 2015-08.

CNKI網(wǎng)絡優(yōu)先出版: 2015-08-12, http://www.cnki.net/kcms/detail/11.5602.TP.20150812.1630.004.htm l

摘要：通過引入置信規(guī)則庫的線性組合方式，設定規(guī)則數(shù)等于分類數(shù)及改進個體匹配度的計算方法，提出了基于置信規(guī)則庫推理的分類方法。比較傳統(tǒng)的置信規(guī)則庫推理方法，新方法中規(guī)則數(shù)的設置不依賴于問題的前件屬性數(shù)量或候選值數(shù)量，僅與問題的分類數(shù)有關，保證了方法對于復雜問題的適用性。實驗中，通過差分進化算法對置信規(guī)則庫的規(guī)則權重、前件屬性權重、屬性候選值和評價等級的置信度進行參數(shù)學習，得到最優(yōu)的參數(shù)組合。對3個常用的公共分類數(shù)據(jù)集進行測試，均獲得理想的分類準確率，表明新分類方法合理有效。

關鍵詞：置信規(guī)則庫；基于證據(jù)推理的置信規(guī)則庫推理方法（RIMER）；參數(shù)學習；分類方法

1 引言

隨著信息時代的到來，互聯(lián)網(wǎng)、醫(yī)學、金融等領域源源不斷地產(chǎn)生大量的數(shù)據(jù)，數(shù)據(jù)的豐富帶來了對強有力的數(shù)據(jù)分析工具的需求，其中數(shù)據(jù)分類技術就是典型的一種，因為很多工程實際問題都可以轉(zhuǎn)化為分類問題。目前，數(shù)據(jù)分類技術主要建立在傳統(tǒng)的數(shù)據(jù)挖掘算法上，包括決策樹算法、貝葉斯（Bayes）算法、神經(jīng)網(wǎng)絡算法、粗糙集算法、支持向量機以及模糊系統(tǒng)等。上述方法由于涉及的參數(shù)較多，且較難以通過解釋性的定義描述各類參數(shù)的含義，因此被稱為“黑箱”式的方法。

基于證據(jù)推理的置信規(guī)則庫推理方法（belief rulebase inference methodology using evidence reasoning，RIMER）由Yang等人[1]首次提出，其涵蓋了Dempster-Shafer證據(jù)理論[2-3]、決策理論[4]、模糊理論[5]和傳統(tǒng)IFTHEN規(guī)則庫[6]等基礎知識。目前，RIMER方法得到廣泛應用，主要包括輸油管道檢漏[7]、石墨成分檢測[8]和軍事能力評估[9]等工程領域。相比上述“黑箱”式的方法，RIMER方法則是一個“白箱”模型，其整個推理過程和涉及的參數(shù)學習過程是可見、可控的。同時，RIMER方法中的置信規(guī)則庫（belief rule base, BRB）具有置信結(jié)構(gòu)，增加了RIMER方法的可理解性。

對于RIMER方法的具體應用，其一般不適用于前件屬性數(shù)量過多的決策問題，否則將由于前件屬性及候選值的數(shù)量過多而導致規(guī)則數(shù)的“組合爆炸”問題。該問題產(chǎn)生的根源在于BRB的構(gòu)建需要覆蓋所有的前件屬性和各個候選值，因此當實際問題過于復雜時，BRB中的置信規(guī)則數(shù)勢必呈指數(shù)級增長趨勢。鑒此，本文基于RIMER方法提出了改進置信規(guī)則庫推理的分類方法。新方法改進了傳統(tǒng)構(gòu)建BRB的方式，對前件屬性候選值進行線性組合生成規(guī)則，由于設定規(guī)則數(shù)等于分類數(shù)，使得新分類方法能夠很好地適應不同規(guī)模的決策問題，不再受限于前件屬性或候選值的數(shù)量。在推理過程中，充分考慮距離與個體匹配度之間負相關關系，以輸入值到候選值之間的距離倒數(shù)的歸一化值作為個體匹配度，并用于計算規(guī)則的激活權重。在這種改進方式下，對于一組給定的測試數(shù)據(jù)，將激活所有的規(guī)則，這意味著本文方法考慮了BRB中每一條規(guī)則對于分類結(jié)果的貢獻度，同時以距離作為衡量該貢獻度大小的標準。新分類方法不僅延續(xù)了RIMER方法能夠有效利用不完整或不精確信息對復雜問題進行建模的能力，而且有效地解決了RIMER方法不適用于多屬性數(shù)據(jù)的分類問題。為驗證本文方法的有效性，在實驗部分對University of California at Irvine（UCI）分校的網(wǎng)站上3個常用的公共測試數(shù)據(jù)集進行了實驗，通過對比前人方法可知，本文方法具有更理想的分類準確性。

2 RIMER方法

RIMER方法是一種能夠利用不完整或不精確信息對復雜問題進行建模的方法，包括已知信息的規(guī)則化表示和決策過程的規(guī)則推導兩個部分。目前，該方法在解決回歸問題和分類問題時已卓有成效。

2.1已知信息的規(guī)則化表示

人工智能領域，以規(guī)則的形式表示已知信息是一種常見的方式，而在RIMER方法中，信息的規(guī)則化表示則體現(xiàn)在BRB中，其中BRB的四元組形式表示如下：

其中，U={Ui;i=1,2,…,T}是規(guī)則的前件屬性集合，T表示BRB中前件屬性的總數(shù)；A={Ai={Ai,j};i=1, 2,…,T;j=1,2,…,Ji}表示前件屬性的候選值集合，Ai表示第i個前件屬性的候選值集合，Ai,j表示第i個前件屬性的第j個候選值，Ji表示第i個前件屬性的候選值總數(shù)；D={Dn;n=1,2,…,N}表示后件屬性的評價等級集合，Dn表示第n個評價等級，N表示評價等級的總數(shù)；F表示前件屬性與后件屬性之間的函數(shù)關系。依據(jù)BRB的四元組，當前件屬性間以邏輯關系“與”相連時，則BRB中第k條規(guī)則表示如下：

其中，Rk(k=1,2,…,L)表示第k條規(guī)則，L表示BRB中規(guī)則的總數(shù)；Aki表示第k條規(guī)則中第i個前件屬性的候選值，因此有Aki∈Ai；βn,k表示第k條規(guī)則中后件屬性的第n個評價等級上的置信度，若βn,k<1,稱第k條規(guī)則包含完整的信息，否則稱第k條規(guī)則包含不完整的信息。此外，稱θk為第k條規(guī)則的規(guī)則權重，表示規(guī)則間的重要程度；稱δi(i=1,2,…,T)為第i個前件屬性的屬性權重，表示屬性間的重要程度。

2.2回歸問題中的規(guī)則推導

回歸問題是RIMER方法最早解決的問題，諸如輸油管道檢漏[10]、裝備故障檢測[11]和消費者偏好預測[12]等問題。在問題求解過程中，RIMER方法共包含兩個步驟，分別為激活權重的計算和激活規(guī)則的合成。為提升RIMER方法的決策準確性，BRB的參數(shù)學習已成為RIMER方法中不可或缺的一部分。

2.2.1激活權重的計算

激活權重的計算是指利用給定的輸入值及BRB中的權重參數(shù)計算各條規(guī)則的權重，并以此為度量標準決定BRB中用于合成輸出值的規(guī)則。在激活權重計算中，首先需要計算前件屬性各個候選值上的個體匹配度，給定輸入值向量為：

x={x1,x2,…,xT}（3）

以第i個前件屬性為例，由其輸入值xi及候選值集合Ai={Aki;k=1,2,…,L}，并根據(jù)基于效用的信息轉(zhuǎn)化技術[13]可算得個體匹配度為：

當以分布式框架表示第i個前件屬性的個體匹配度時，可表示如下：

S(xi)={(Ai,j,αi,j); i=1,2,…,T; j=1,2,…,Ji}（5）

其中，αi,j是第i個前件屬性中第j個候選值Aji的個體匹配度。依據(jù)式（5）可同樣算得其他前件屬性各個候選值上的個體匹配度。然后根據(jù)BRB中每條規(guī)則所包含候選值的個體匹配度及權重參數(shù)計算規(guī)則的激活權重，其中第k條規(guī)則的激活權重計算公式為：

2.2.2激活規(guī)則的合成

由2.2.1節(jié)中計算的激活權重可知，當激活權重大于0時，當前規(guī)則處于激活狀態(tài)需用于合成最終的決策結(jié)果，而激活規(guī)則的合成步驟如下所示。

首先，由激活規(guī)則后件屬性的置信度和激活權重計算基本可信值[14-15]：

式中n=1,2,…,N，i=1,2,…,L。

然后，利用證據(jù)推理（evidential reasoning，ER）算法的解析公式[16]將所有的激活規(guī)則一次合成，合成公式為：

接著，計算合成結(jié)果中各個評價等級上的置信度：

最后，依據(jù)后件屬性中各個評價等級的等級效用值μ={μ(D1),μ(D2),…,μ(DN)}計算給定輸入值的期望型輸出：

2.2.3 BRB的參數(shù)學習

RIMER方法的決策準確性與BRB中參數(shù)取值相關，在簡單決策問題中，可由專家根據(jù)歷史信息和先驗知識給定。但該方式具有主觀局限性，無法保證在復雜決策問題中RIMER方法的決策準確性，因此BRB的參數(shù)學習為研究者所關注。

BRB的參數(shù)學習是指利用歷史數(shù)據(jù)分析RIMER方法與實際系統(tǒng)的輸出誤差，通過誤差反復地調(diào)整BRB內(nèi)部的參數(shù)取值，進而提高RIMER方法的決策準確性，如圖1所示。由此可見BRB的參數(shù)學習實質(zhì)上是一個帶約束條件的優(yōu)化問題，詳見文獻[17]。

目前，可用于BRB參數(shù)學習的方法主要包括FM INCON函數(shù)[17]和群智能算法[18]等。FM INCON函數(shù)是Matlab優(yōu)化工具箱中用于求解非線性優(yōu)化問題的函數(shù)，依此對BRB參數(shù)學習進行研究的成果有：Yang等人[17]提出的局部參數(shù)學習方法和Chen等人[19]提出的全局參數(shù)學習方法等，但上述方法均存在收斂速度慢，收斂精度不高的問題。相比于FM INCON函數(shù)，利用群智能算法對BRB進行參數(shù)學習具備對參數(shù)初值不敏感，收斂速度快和收斂精度高的優(yōu)點，已有的研究成果有：Chang等人[20]提出的基于差分進化算法的參數(shù)學習方法和Zhou等人[21]提出的基于克隆選擇算法的參數(shù)學習方法和蘇群等人[22]提出的基于粒子群算法的參數(shù)學習方法。

2.3分類問題中的規(guī)則推導

分類問題是回歸問題的特殊情形，前者屬于離散型輸出，而后者屬于連續(xù)性輸出，因此相比于回歸問題中的規(guī)則推導，在分類問題的最終輸出中還需進行分類映射。目前，RIMER方法在分類問題[21]中的應用主要包括：淋巴結(jié)疾病診斷和UCI分類數(shù)據(jù)集測試[23]。

2.3.1 BRB分類方法與分類映射

目前，RIMER方法在求解分類問題時共分成了兩種BRB分類方法：

第一種BRB分類方法改進于回歸問題中的RIMER方法。首先，在構(gòu)建BRB時并非使用傳統(tǒng)的遍歷每個前件屬性所有候選值的方式，而是通過線性組合的方式構(gòu)建BRB中各條規(guī)則，如圖2所示。

Fig.1 Parameter training model of BRB圖1 BRB的參數(shù)訓練模型

Fig.2 Different ways of combining rules圖2 規(guī)則的不同組合方式

最后，利用激活規(guī)則合成中式（7）～（16）可推得各個評價等級上的置信度，并由分類映射確定最終分類結(jié)果。假設后件屬性中評價等級與分類等級一一對應，則相應的最終分類結(jié)果為：

第二種BRB分類方法擴展于回歸問題中的RIMER方法。BRB的構(gòu)建采用遍歷組合的方式，而算法流程包括BRB的參數(shù)學習，激活權重計算，激活規(guī)則合成和分類映射4個部分，鑒于與2.2節(jié)中介紹內(nèi)容相同，此處不再贅述。

2.3.2現(xiàn)有BRB分類方法的不足

現(xiàn)有BRB分類方法在一定程度上已能有效地解決分類問題，但其在具體應用時仍存在一些不足之處。

對于第二種BRB分類方法，在構(gòu)建BRB時采用遍歷組合的方法，因此其繼承了傳統(tǒng)RIMER方法中固有的“組合爆炸”問題。以分類問題中常用的數(shù)據(jù)集Cancer為例，數(shù)據(jù)集Cancer中共有前件屬性30個，假設每個前件屬性的候選值個數(shù)為2，則由此構(gòu)建的BRB中共有規(guī)則數(shù)230=1 073 741 824條，若再增加BRB中前件屬性數(shù)量或候選值數(shù)量，則BRB中的規(guī)則數(shù)呈指數(shù)遞增的趨勢；同時，通過對UCI上231組分類數(shù)據(jù)集分析可知，前件屬性數(shù)量少于10的分類數(shù)據(jù)集個數(shù)為54組，前件屬性數(shù)量為10至100的分類數(shù)據(jù)集個數(shù)為114組，前件屬性數(shù)量大于100的分類數(shù)據(jù)集個數(shù)為42組，由此可見現(xiàn)有的分類問題中多為多屬性的情形，因此第二種BRB分類方法并不適用于處理現(xiàn)有分類問題。

對于第一種BRB分類方法[24]，其中BRB的構(gòu)建是以線性組合的方式，有效地避免了規(guī)則數(shù)的“組合爆炸”問題，但在構(gòu)建BRB時未有合理的確定規(guī)則數(shù)的方式，進而易出現(xiàn)因BRB中規(guī)則數(shù)過少降低RIMER方法的分類準確性或因BRB中規(guī)則數(shù)過多增加參數(shù)學習的時空復雜度的問題。為避免BRB中規(guī)則的“零激活”問題，第一種BRB分類方法將各條規(guī)則上候選值對應的個體匹配度以累加求和的方式計算激活權重，其物理意義用規(guī)則表示是各個候選值間以“或”的邏輯關系相互關聯(lián)，有悖于式（2）中規(guī)則的候選值間以“和”的邏輯關系進行關聯(lián)的表示形式。

此外，在兩種BRB分類方法中均只度量與輸入值相鄰候選值上的個體匹配度，而在基于效用的信息轉(zhuǎn)化技術中距離是度量個體匹配度的依據(jù)，因此未考慮非相鄰候選值的個體匹配度度量方式的合理性有待進一步分析。

3 改進置信規(guī)則庫推理的分類方法

針對現(xiàn)有BRB分類方法存在的不足，及避免RIMER方法可能出現(xiàn)的規(guī)則數(shù)“組合爆炸”問題和規(guī)則“零激活”問題，本文提出了一種基于改進置信規(guī)則庫推理的分類方法。以下將在3.1節(jié)中具體介紹新方法的算法步驟，并在3.2節(jié)中分析其在推理方面的合理性。

3.1算法步驟

改進置信規(guī)則庫推理的分類方法的流程如圖3所示。

Fig.3 Process of classification for BRB圖3 置信規(guī)則庫分類方法的流程

由圖3可知，新分類方法的具體步驟為：

步驟1依據(jù)分類問題中分類數(shù)據(jù)集構(gòu)建初始BRB。

假設分類問題中屬性數(shù)量為T，訓練數(shù)據(jù)的組數(shù)為H，已知分類數(shù)為C，分類數(shù)據(jù)集的矩陣形式為：

其中，Pi表示矩陣的第i行，即第i組輸入數(shù)據(jù)構(gòu)成的行向量；Uj表示矩陣的第j列，即所有輸入數(shù)據(jù)的第j個屬性構(gòu)成的列向量；xi,j為矩陣的一個元素，表示第i組分類數(shù)據(jù)的第j個屬性取值。

由此可確定BRB中有T個前件屬性，每個前件屬性設置C個候選值，效用等級個數(shù)設置為C，依據(jù)線性組合方式可知，BRB中規(guī)則數(shù)為C。

步驟2依據(jù)分類數(shù)據(jù)集設置初始BRB的參數(shù)取值。

針對BRB中各類的參數(shù)，由分類數(shù)據(jù)集可確定其參數(shù)取值。

（1）對于BRB中第k條規(guī)則，其規(guī)則權重初值可設置為：

θk=1

（2）對于第i個前件屬性，其屬性權重初值可設置為：

δi=1

（3）對于第k條規(guī)則中的第i個前件屬性，其各個候選值的初值可設置為：

（4）每一個評價等級都對應一個分類，評價等級Dn設置為：

（5）第k條規(guī)則中第n個評價等級對應的置信度設置為：

其中，randi( )表示0到1之間的長度為C的隨機數(shù)序列中的第i個取值。

步驟3對初始BRB的參數(shù)進行訓練，得到最優(yōu)參數(shù)取值。

初始BRB中待優(yōu)化的參數(shù)包括前件屬性權重δi、屬性候選值Aki、規(guī)則權重θk和評價等級的置信度βn,k。本文使用全局參數(shù)優(yōu)化模型，可以表示如下：

P=P(θk,δi,βn,k, Aki)（23）

對于優(yōu)化模型中的等式和不等式約束條件，給出如下定義。

（1）標準化規(guī)則權重θi，其不小于0且不大于1，即：

0≤θk≤1, k=1,2,…,L（24）

其中，L表示BRB中的規(guī)則數(shù)。

（2）標準化前件屬性權重δi，其同樣不小于0且不大于1，即：

0≤δi≤1, i=1,2,…,T（25）

其中，T表示BRB中前件屬性的數(shù)量。

（3）任意一條置信規(guī)則的結(jié)果置信度均不小于0且不大于1，其中第k條規(guī)則的第j個評價等級上的置信度需滿足：

0≤βn,k≤1, n=1,2,…,N, k=1,2,…,L（26）

其中，N表示BRB中效用等級的個數(shù)。

（4）假設第k條規(guī)則是完整的，即輸入不包含不確定、模糊信息，則該條規(guī)則的結(jié)果置信度之和等于1：

（5）標準化屬性候選值，使其不大于訓練數(shù)據(jù)屬性取值的上限，不小于其下限，且同一屬性需滿足相鄰規(guī)則的候選值相差一個無窮小量Vi，即：

其中, H表示訓練數(shù)據(jù)的組數(shù)。

步驟4給定分類問題的前件屬性，通過RIMER方法及分類映射得到分類結(jié)果。

當制定規(guī)則的形式為前件屬性的線性組合時，由于規(guī)則的刪減，使得規(guī)則的組合并不能覆蓋所有的屬性候選值，無法保證對于一組給定的數(shù)據(jù)能夠激活某些規(guī)則，傳統(tǒng)的推理方式將無法進行。

鑒此，本文對傳統(tǒng)BRB中計算個體匹配度的函數(shù)進行改進，將輸入值到指定規(guī)則中對應屬性的候選值的距離倒數(shù)的歸一化值作為個體匹配度，則其個體匹配度的計算如下所示：

其中，xi表示式（3）中測試數(shù)據(jù)x的第i個屬性輸入值；Aki表示第i個屬性在第k條規(guī)則中的候選值；L為規(guī)則數(shù)；αi,k表示輸入數(shù)據(jù)對于第k條規(guī)則中的第i個屬性的個體匹配度。

在得到個體匹配度后，接著可以按照式（6）計算規(guī)則的激活權重，按照式（7）～（16）合成激活規(guī)則，最后由式（19）得到最終的分類結(jié)果。

3.2合理性分析

3.2.1個體匹配度計算的合理性

傳統(tǒng)的RIMER方法中，計算規(guī)則的激活權重時，其個體匹配度的計算公式如式（4）所示。以下對其過程進行簡要描述：首先對于一組輸入數(shù)據(jù)中的第i個前件屬性xi，找到其在BRB中對應屬性的候選值區(qū)間，如圖4所示，xi處在規(guī)則b和規(guī)則c對應的區(qū)間中，即候選值區(qū)間為[Abi, Aic]，其個體匹配度為：

Fig.4 Different ways of calculating indivial matching圖4 計算個體匹配度的不同方式

由于xi處于規(guī)則b和規(guī)則c的第i個屬性候選值之間，xi對于其他規(guī)則的個體匹配度均為0。得到個體匹配度后，便可用于計算規(guī)則的激活權重。

將上述計算過程運用于解決多屬性的分類問題時，因受限于規(guī)則的數(shù)量，以上方法并不適用，導致無法保證一定有規(guī)則被激活，由此可見現(xiàn)有方法存在一定局限性。此外，由圖4可知，當以線性組合的方式構(gòu)建規(guī)則時，輸入值xi到每條規(guī)則的第i個屬性的候選值的距離并不相同，例如xi到候選值Adi和Aai的距離并不相等，因此規(guī)則a和規(guī)則d在使用xi計算規(guī)則匹配度時其影響程度并不相同，但傳統(tǒng)的RIMER方法認為輸入值xi對規(guī)則a和規(guī)則d無影響。

鑒此，本文依據(jù)個體匹配度與輸入值到規(guī)則中對應候選值的距離負相關關系，提出如式（29）所示的個體匹配度計算的改進方法。以下通過一個簡單的曲線擬合實例驗證該個體匹配度計算方法的合理性。

假設二元復合冪函數(shù)為：

其中分別令τ=-3, -1, 1, 3，自變量x的取值范圍為[6,21]，自變量y的取值范圍為[4,10]，由定義域內(nèi)均勻選取的3 000組數(shù)據(jù)作為BRB參數(shù)學習的訓練數(shù)據(jù)。基于個體匹配度計算改進方法的曲線擬合結(jié)果如圖5。

Fig.5　Fitting of function圖5 函數(shù)的擬合情況

由圖5可知，上述4個二元函數(shù)的擬合效果理想，進而說明了本文提出的個體匹配度計算改進方法的合理性。

3.2.2規(guī)則數(shù)設置的合理性

對于BRB中規(guī)則數(shù)量的設定，假若規(guī)則數(shù)量太少，則分類準確性可能難以讓人滿意；假若規(guī)則數(shù)量太多，則可能導致運行效率低下且分類準確性不理想。因而這就要求針對特定的研究問題設置合理的規(guī)則數(shù)量。為此，本文提出通過分類問題中分類數(shù)量來確定BRB中的規(guī)則數(shù)量，即規(guī)則數(shù)等于分類數(shù)。其合理性分析如下：

當規(guī)則數(shù)少于分類數(shù)時，如圖6所示，個體匹配度計算公式改進后，同類別分類數(shù)據(jù)的輸入值易激活同一規(guī)則，且該條規(guī)則在激活規(guī)則合成時占主導作用。因此針對規(guī)則數(shù)少于分類數(shù)的情形，勢必造成最終分類出現(xiàn)無規(guī)則相對應的問題，最終降低方法的分類準確性。

Fig.6 Mapping of rule and class圖6 規(guī)則與分類的對應

當規(guī)則數(shù)多于分類數(shù)時，假設分類問題共有C個分類、T個前件屬性、N個后件屬性評價等級時，則BRB中需要參數(shù)學習的參數(shù)數(shù)量共為C+T+C× T+C×N。假定參數(shù)學習時劃分到每個參數(shù)的平均時間復雜度為O(K)，則參數(shù)學習的時間復雜度為：

O(K×(C+T+C×T+C×N))≈O(C×K×(T+N))（31）

由上述公式可見，每增加一條規(guī)則所需提高的時間復雜度為O(K×(T+N))。因此，從算法時間復雜度的角度分析，BRB中不宜設定過多的規(guī)則。

當規(guī)則數(shù)等于分類數(shù)時，如圖6所示，由于每一條規(guī)則根據(jù)其參數(shù)特征與特定分類建立一一對應關系，例如圖6中共有n條規(guī)則和n個分類，對于第k個分類，n條規(guī)則對其都存在一定的決定因素，但就決定能力而言，第i條規(guī)則對其有最大的決定能力，如80%，其余規(guī)則對其決定能力相對較小，如8%、5%等。因此使用規(guī)則數(shù)等于分類數(shù)的規(guī)則制定策略，可提高方法的分類準確性，并且使分類方法具有最低的時間復雜度。

4 實例分析

4.1實驗環(huán)境及實例背景

在使用本文方法進行數(shù)據(jù)分類時，以差分進化算法[25]作為BRB參數(shù)學習的優(yōu)化算法，其中種群規(guī)模NP=200，進化代數(shù)genSize=1 000，縮放因子F=0.5，交叉概率CR=0.9。此外，實驗環(huán)境為：Intel?Core i5-4570@3.20 GHz；4 GB內(nèi)存；W indows 7操作系統(tǒng)；算法由Visual C++ 6.0編寫。

對于實驗中所用的測試數(shù)據(jù)集，本文選自UCI公共測試數(shù)據(jù)集中乳腺癌數(shù)據(jù)Breast Cancer[26]、鳶尾花特征數(shù)據(jù)Iris[27]和玻璃類型數(shù)據(jù)Glass[28]。表1列舉了上述3個測試數(shù)據(jù)集中前件屬性數(shù)量、分類類別數(shù)量和測試集大小等信息。

Tabel 1 Basic information of test data sets表1 測試數(shù)據(jù)集的基本信息

4.2實驗過程

實驗中，對于以上3個數(shù)據(jù)集，分別測試當規(guī)則數(shù)為分類數(shù)上下范圍時的分類準確性。Breast Cancer 和Iris數(shù)據(jù)集分別測試當規(guī)則數(shù)為2到5條時的分類準確率，Glass數(shù)據(jù)集分別測試當規(guī)則數(shù)為5到9條時的分類準確率，同時統(tǒng)計其分類準確率的標準差。為說明本文方法的具體應用，以Iris數(shù)據(jù)集為例，具體介紹本文的算法步驟。

Table 2 Initial belief rule base表2 初始置信規(guī)則庫

Table 3 Trained belief rule base表3 參數(shù)訓練后的置信規(guī)則庫

首先，取規(guī)則數(shù)L=3構(gòu)建初始的置信規(guī)則庫。根據(jù)3.1節(jié)步驟1和步驟2可構(gòu)出如表2所示的Iris數(shù)據(jù)集的初始BRB。

然后通過差分進化算法，按照3.1節(jié)步驟3所述，訓練BRB中各個參數(shù)，得到如表3所示的參數(shù)訓練后的BRB。

在得到表3的BRB表示后，對于給定的輸入數(shù)據(jù)，可按照3.1節(jié)中步驟4推理相應的分類結(jié)果。

對于實驗結(jié)果有效性驗證，本文采用十折交叉驗證法，即每次取90%的數(shù)據(jù)作為訓練數(shù)據(jù)，剩下10%的數(shù)據(jù)作為測試數(shù)據(jù)。而在算法的效率分析中，同樣以Iris數(shù)據(jù)集為例，針對不同的規(guī)則數(shù)，算法所需時間如表4所示。

Table 4 Time for training parameters表4 BRB參數(shù)訓練時間

由表4中數(shù)據(jù)可繪制如圖7所示的折線圖。

根據(jù)圖7可知，對于以上的Iris數(shù)據(jù)集，隨著規(guī)則數(shù)的增加，其訓練時間也隨之增加，并且大致呈線性關系，與3.2.2小節(jié)中所述合理性相符。綜上所述，構(gòu)建BRB時的規(guī)則數(shù)不應設置過多。

4.3結(jié)果分析

Fig.7 Time of training parameters圖7 參數(shù)訓練時間

為進一步驗證本文方法的有效性，用表1所示的3個數(shù)據(jù)集進行測試，其中圖8、圖9和圖10分別為3個數(shù)據(jù)集在設定不同規(guī)則數(shù)時，10次十折交叉驗證的分類準確率。對應給定的規(guī)則數(shù)，都有10個點表示相應的準確率，由于某些點的重疊，圖上對應規(guī)則數(shù)的可見點可能小于10個。

同時，表5統(tǒng)計了3個數(shù)據(jù)集在給定規(guī)則數(shù)時10次驗證結(jié)果的標準差信息以及算法中訓練優(yōu)化模型所用的時間。在訓練和驗證每個數(shù)據(jù)集時，規(guī)則數(shù)N均取在以其分類數(shù)為中心的指定區(qū)間內(nèi)，由于當N小于2時，RIMER方法無法進行規(guī)則推導，規(guī)定N的下限為2。在表5中，加粗的數(shù)據(jù)表示當前數(shù)據(jù)集的分類數(shù)等于規(guī)則數(shù)的情況。

為了使以上的數(shù)據(jù)更加直觀，繪制如圖11、圖12和圖13所示的折線圖。圖11為Breast Cancer數(shù)據(jù)集的分類準確率及其標準差變化的折線圖；圖12為Iris數(shù)據(jù)集的分類準確率及其標準差變化的折線圖；圖13為Glass數(shù)據(jù)集的分類準確率及其標準差變化的折線圖。

Fig.8 Classification accuracy of Breast Cacncer圖8 Breast Cancer數(shù)據(jù)集分類準確性統(tǒng)計

Fig.9 Classification accuracy of Iris圖9 Iris數(shù)據(jù)集分類準確性統(tǒng)計

Fig.10 Classification accuracy of Glass圖10 Glass數(shù)據(jù)集分類準確性統(tǒng)計

Table 5 Classification accuracy of 3 datasets表5 3個數(shù)據(jù)集的分類準確率

Fig.11 Classification accuracy and standard deviation of Breast Cancer圖11 Breast Cancer分類準確率及其標準差

Fig.12 Classification accuracy and standarddeviation of Iris圖12 Iris分類準確率及其標準差

Fig.13 Classification accuracy and standard deviation of Glass圖13 Glass分類準確率及其標準差

根據(jù)圖11、圖12和圖13可知，分類準確率的變化趨勢與其標準差的變化趨勢基本上呈現(xiàn)負相關的關系。例如Breast Cancer數(shù)據(jù)集在規(guī)則數(shù)為2條時，分類準確率最高，標準差最?。籌ris數(shù)據(jù)集在規(guī)則數(shù)為3條時，分類準確率最高，標準差最小；Glass數(shù)據(jù)集在規(guī)則數(shù)為7條時，分類準確率最高，標準差最小。因此由以上3個數(shù)據(jù)集的測試結(jié)果表明，當BRB中的規(guī)則數(shù)剛好等于分類數(shù)時，其分類準確率最高，標準差最小。

為了驗證本文方法的有效性，表6列出了與Fallahnezhad等人[29]總結(jié)的部分前人成果的對比。

Table 6 Comparison of classification accuracy w ithdifferent methods表6 不同方法的平均分類準確率對比

根據(jù)表6可知，對于3個測試數(shù)據(jù)集，用本文分類方法的分類準確性均較理想，其中在Breast Cancer 和Iris數(shù)據(jù)集中都取得了僅次于最優(yōu)準確性的結(jié)果。

5 結(jié)束語

目前，面對海量數(shù)據(jù)處理時，分類問題是研究的熱點。本文提出了基于改進置信規(guī)則庫推理的分類方法，首先將分類問題的分類數(shù)與置信規(guī)則庫的規(guī)則數(shù)相關聯(lián)，設置規(guī)則數(shù)等于分類數(shù)，同時改進了傳統(tǒng)置信規(guī)則庫中個體匹配度的計算方法，然后將置信等級映射為分類結(jié)果。相比現(xiàn)有基于置信規(guī)則庫的分類方法，本文方法有效地克服了規(guī)則數(shù)的“組合爆炸”問題和規(guī)則的“零激活”問題。在實例分析部分，通過對3個公共測試數(shù)據(jù)集的多次實驗，驗證了當規(guī)則數(shù)等于分類數(shù)時，其分類準確性較高的結(jié)論，同時其分類準確性較當前文獻的研究方法具有較大的優(yōu)勢。

References:

[1] 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: Part A Systems and Humans, 2006, 36(2): 266-285.

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

[3] Shafer G. A mathematical theory of evidence[M]. Princeton, USA: Princeton University Press, 1976.

[4] Hwang C L, Yoon K. Methods for multiple attribute decision making[M]//Multiple Attribute Decision Making. Berlin, Heidelberg: Springer, 1981: 58-191.

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

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

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

[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 Systemsand Humans, 2007, 37(4): 569-585.

[9] Jiang Jiang, Li Xuan, Zhou Zhijie, et al. Weapon system capability assessment under uncertainty based on the evidential reasoning approach[J]. Expert Systems w ith Applications, 2011, 38(11): 13773-13784.

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

[11] Zhou Zhijie, Hu Changhua, Xu Dongling, et al. A model for real-time failure prognosis based on hidden Markov model and belief rule base[J]. European Journal of Operational Research, 2010, 207(1): 269-283.

[12] Wang Yingm ing, Yang Jianbo, Xu Dongling, et al. Consumer preference prediction by using a hybrid evidential reasoning and belief rule-based methodology[J]. Expert System w ith Application, 2009, 36(4): 8421-8430.

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

[14] Wang Yingm ing, Yang Jianbo, Xu Dongling. Environmental impact assessment using the evidential reasoning approach[J]. European Journal of Operational Research, 2006, 174(3): 1885-1913.

[15] Duan Xinsheng. Evidence theory, decision & artificial intelligence[M]. Beijing: Renmin University of China Press, 1993. [16] Wang Yingm ing, Yang Jianbo, Xu Dongling, et al. The evidential reasoning approach for multiple attribute decision analysis using interval belief degrees[J]. European Journal of Operational Research, 2006, 175(1): 35-66.

[17] Yang Jianbo, Liu Jun, Xu Dongling, et al. Optim ization 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.

[18] Wang Zhengzhi, Bo Tao. Evolutionary computation[M]. Changsha: National University of Defence Technology Press, 2000.

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

[20] 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]. Know ledge-Based System, 2015, 73: 69-80.

[21] Zhou Zhiguo, Liu Fang, Jiao Licheng, et al. A bi-level belief rule based decision support system for diagnosis of lymph node metastasis in gastric cancer[J]. Know ledge-Based System, 2013, 54: 128-136.

[22] 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.

[23] Jiao Lianmeng, Pan Quan, Denoeux T, et al. Belief rulebased classification system: extension of FRBCS in belief functions framework[J]. Information Sciences, 2015, 309: 26-49.

[24] Chang Leilei, Zhou Zhijie, You Yuan, et al. Belief rule based expert system for classification problems w ith new rule activation and weight calculation procedures[J]. Information Sciences, 2016, 336: 75-91.

[25] Storn R, Price K. Differential evolution—a simple and efficient heuristic for global optim ization over continuous spaces [J]. Journal of Global Optim ization, 1997, 11(4): 341-359.

[26] Aci M, Avc M. K nearest neighbor reinforced expectation maxim ization method[J]. Expert Systems w ith Applications, 2011, 38(10): 12585-12591.

[27] Fisher R A. The use of multiple measurements in taxonom ic problems[J].Annual Eugenics, 1936, 7(2): 179-188.

[28] Athitsos V, Sclaroff S. Boosting nearest neighbor classifiers for multiclass recognition, 2004-006[R]. Boston University, 2004.

[29] Fallahnezhad M, Moradi M H, Zaferanlouei S. A hybrid higher order neural classifier for handling classification problems[J]. Expert Systems w ith Applications, 2011, 38 (1): 386-393.

附中文參考文獻：

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

[15]段新生.證據(jù)理論與決策、人工智能[M].北京:中國人民大學出版社, 1993.

[18]王正志,薄濤.進化計算[M].長沙:囯防科技大學出版社, 2000.

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

YE Qingqing was born in 1992. She is a student at College of Mathematics and Computer Science, Fuzhou University. Her research interests include intelligent decision making technology and data mining, etc.

葉青青（1992—），女，福建寧德人，福州大學數(shù)學與計算機科學學院學生，主要研究領域為智能決策技術，數(shù)據(jù)挖掘等。

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

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

FU Yanggeng was born in 1981. He received 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.

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

CHEN Xiaocong was born in 1994. He is a student at College of Mathematics and Computer Science, Fuzhou University. His research interests include intelligent decision making technology and data mining, etc.

陳曉聰（1994—），男，福建龍巖人，福州大學數(shù)學與計算機科學學院學生，主要研究領域為智能決策技術，數(shù)據(jù)挖掘等。

Classification Approach Based on Im proved Belief Rule-Base Reasoning?

YE Qingqing1, YANG Longhao2, FU Yanggeng1+, CHEN Xiaocong1
1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China 2. School of Econom ics and Management, Fuzhou University, Fuzhou 350116, China
+ Corresponding author: E-mail: ygfu@qq.com

YE Qingqing, YANG Longhao, FU Yanggeng, et al. Classification approach based on im proved belief rulebase reasoning. Journal of Frontiersof Computer Science and Technology, 2016, 10(5)：709-721.

Abstract:This paper proposes a new classification approach based on improved belief rule-base reasoning by introducing linear combinational mode, setting the number of rules based on the classifications and improving the method of calculating individual matching degree. Compared w ith the traditional belief rule-base inference methodology, the number of rules in the proposed method does not depend on the number of antecedent attributes or its referential values, and it is only related to classification number. In this way, the new method can ensure the applicability for complex problems. In the experiments, the differential evolution algorithm is applied to train parameters, including rule weights, attribute weights, referential values of antecedent attributes and belief degrees. Three commonly public datasets have been employed to validate the proposed method. And the classification results are proved to be ideal, which shows that the proposed method is reasonable and effective.Key words: belief rule-base; belief rule-base inference methodology using evidence reasoning (RIMER）; parameter learning; classification method

doi:10.3778/j.issn.1673-9418.1507068 E-mail: fcst@vip.163.com

文獻標志碼：A

中圖分類號：TP18