孫巖清1,2，尹樹華，林初善

(1.西安通信學(xué)院 研究生管理大隊，西安 710106；2.中國酒泉衛(wèi)星發(fā)射中心 指揮通信室，甘肅 酒泉 732750；3.西安通信學(xué)院 軍用光纖通信教研室，西安 710106)

1 引 言

基于案例推理(Case-Based Reasoning, CBR)是通過回憶一個或幾個過去發(fā)生的具體案例，進而采用類比的推理方法，提出解決新問題的方案，其一般過程為“檢索-重用-修正-存儲”，檢索是其中的關(guān)鍵，直接決定了案例推理系統(tǒng)的性能。目前，研究較多的檢索方法有決策樹[1]、KNN[2-3]、神經(jīng)網(wǎng)絡(luò)[4-5]、支持向量機[6]等，但其每一種具體算法都有一定的局限性，不能夠在CBR系統(tǒng)中得到很好的應(yīng)用。其中，決策樹法存在案例庫改變時需要重新建樹且存儲、開銷大的缺點；神經(jīng)網(wǎng)絡(luò)法存在案例屬性較多時訓(xùn)練耗時，只能給出單個相似案例的缺點；KNN算法存在計算量大、效率不高和在案例較多時檢索耗時的缺點；支持向量機則存在隨著案例或案例屬性增加而檢索耗時、計算復(fù)雜的缺點。

因此，已有檢索方法存在各自問題，不能很好地應(yīng)用于實際的CBR系統(tǒng)，故本文提出基于粗糙集理論進行屬性約簡，刪除案例冗余屬性，完成案例庫優(yōu)化，再結(jié)合相似度計算方法和概率神經(jīng)網(wǎng)絡(luò)算法進行不同情況下的案例檢索策略，做到既保證檢索的精度，盡可能地檢索出要求的所有相似案例，又避免檢索時間隨案例增加而線性增長。

2 粗糙集相關(guān)概念

2.1 屬性重要度定義

定義1：設(shè)S=(U,A,V,f)為一個信息系統(tǒng)，A=C∪D，?R?C,屬性依賴度表示為r(R,D)=|PosR(D)|/|PosC(D)|，則?c∈R的屬性重要度可表示為依賴度的差值：

(1)

定義2：設(shè)S=(U,A,V,f)為一個信息系統(tǒng)，A=C∪D，?R?C，且R在對象集合U上產(chǎn)生的劃分為:U/R={X1,X2,…,Xn},則知識P的熵為

式中，p(Xi)=|Xi|/|U|。

則決策表中任一條件屬性本身的重要度可以由它所引起的信息熵的變化來衡量，即已知屬性集R?C，?c∈C-R的重要度可定義為

SIG2(c,R,C)=H(R∪c)-H(R)

(2)

對于CBR系統(tǒng)，約簡應(yīng)既能很好地反映專家經(jīng)驗知識，又能生成正確的決策規(guī)則，因此，應(yīng)該綜合考慮屬性決策分類和本身重要度兩方面的因素。

定義3：對于決策信息系統(tǒng)S=(U,A,V,f)，A=C∪D，n=U，屬性c∈R?C在R中的重要度為

(3)

式中，0≤w≤1。當(dāng)w=1時，同等考慮屬性對決策分類的影響度和屬性本身的重要度，最大化地反映領(lǐng)域?qū)＜业慕?jīng)驗知識；當(dāng)w=0時，僅考慮屬性對決策分類的影響，而一般情況下，對于CBR系統(tǒng)采取前者的定義。

2.2 知識約簡定義

定義4：設(shè)S=(U,A,V,f)為一個信息系統(tǒng)，A=C∪D，?P?C，如果P滿足下面兩個條件，則P是一個Pawlak約簡：

(1)PosP(D)=PosC(D)；

(2)?a∈P,PosP-{a}(D)≠PosC(D)。

上面定義中，第一個條件保證了相同決策規(guī)則的生成，第二個條件保證了約簡的獨立性。

3 相似案例檢索思想

3.1 案例相似度定義及分析

設(shè)F為一案例庫，且其中案例的屬性均已進行歸一化處理。

定義5：以dist(A,B)、sim(A,B)分別表示案例A、B之間的距離和相似度，則在最近鄰實例檢索中sim(A,B)=1-dist(A,B)，那么，sim(A,B)應(yīng)滿足以下條件和性質(zhì)：

(1)sim(A,B)∈[0,1]，sim(A,B)=1，當(dāng)且僅當(dāng)A=B，即自反性；

(2)sim(A,B)=sim(B,A)，即對稱性；

(3)對任意的案例A,B,C?F，有sim(A,B)≥sim(A,C)+sim(B,C)-1，即滿足三角不等式關(guān)系。

由定義5可知，采用最近鄰進行檢索案例的核心工作就是計算目標案例與待檢案例之間的距離，而后選取距離最小者作為最相似案例。在實際應(yīng)用中多采用歐幾里得距離法，同時，為滿足條件(1)，對傳統(tǒng)距離公式進行改進，對距離進行歸一化處理，有：

(4)

式中，wi為案例的第i個屬性權(quán)值，可以在屬性約簡的過程中獲得，其值越大則表示該屬性越重要；n為屬性個數(shù)；A(i)、B(i)分別表示案例A、B的第i個屬性值。

3.2 案例檢索過程

圖1為案例檢索流程圖。

圖1 案例檢索流程圖Fig.1 Case retrieval flowchart

利用粗糙集理論首先對案例庫進行屬性約簡，并計算約簡后的屬性重要度權(quán)值，而后在小案例庫時采取相似度計算方法檢索案例，在大案例庫時采用概率神經(jīng)網(wǎng)絡(luò)實現(xiàn)，從而充分利用相似度計算和神經(jīng)網(wǎng)絡(luò)的優(yōu)點，取長補短，達到CBR系統(tǒng)案例檢索的最優(yōu)效果。

4 實驗結(jié)果和分析

為驗證文中檢索策略的正確性，采用UCI數(shù)據(jù)集和人工數(shù)據(jù)集相結(jié)合的方法進行，仿真環(huán)境為Matlab R2006a，計算機配置為AMD Athlon 64位處理器，1G內(nèi)存。其中，UCI數(shù)據(jù)集主要采用了Wine、Riply和Iris 3種，分別用于驗證時間復(fù)雜度和檢索精度，同時在小數(shù)據(jù)集下運用人工數(shù)據(jù)集對檢索精度進行了驗證。

4.1 案例檢索時間復(fù)雜度驗證

采用Wine數(shù)據(jù)集進行時間復(fù)雜度驗證，它包括178個樣本、13個條件屬性和3個決策屬性。實驗以成倍增加案例的方式進行，任選其中的一個案例作為待檢測樣本，同時，為避免檢索時間的隨機性，降低仿真誤差，采取每次檢索仿真10次，取平均值作為最終檢索時間的方法。仿真結(jié)果如圖2所示。

圖2 3種檢索方法的時間對比Fig.2 The time comparison of three retrieval methods

由圖2可以看出，在小數(shù)據(jù)集時，3種檢索算法耗時均很小，且相似度計算方法性能更優(yōu)；而隨著案例的增多，基于相似度計算和KNN算法的檢索時間會線性增長，神經(jīng)網(wǎng)絡(luò)算法則在一定的時間點或范圍內(nèi)保持穩(wěn)態(tài)。

4.2 案例檢索精度驗證

采用Riply數(shù)據(jù)集進行檢索精度的驗證，Riply數(shù)據(jù)集包括訓(xùn)練樣本250個、檢測樣本1 000個、條件屬性2個、決策屬性2個。檢索結(jié)果如表1所示，其中相似度檢索選擇了兩種模式，即取一個相似案例和兩個相似案例。

表1 3種算法檢索結(jié)果對比Table 1 The retrieval result comparison of three algorithms

由表1可知，在只追求單個最相似案例的情況下，概率神經(jīng)網(wǎng)絡(luò)檢索更加精確，K近鄰次之，相似度檢索算法較差。但前兩種算法卻不能夠給出多個相似案例，存在局限；而相似度檢索算法則能夠給出多個相似案例，一般選擇2個，在此情況下，相似度檢索算法具有相當(dāng)高的精度，優(yōu)勢比較突出。

4.3 基于粗糙集的案例檢索驗證及應(yīng)用

由以上實驗可以看出：在小數(shù)據(jù)集時，相似度計算檢索既能保證檢索精度，又能保證檢索的時間復(fù)雜度；在大數(shù)據(jù)集時，神經(jīng)網(wǎng)絡(luò)算法則可以保證檢索精度，且能夠避免檢索時間的線性增長。因此，文中提出的案例檢索策略能夠有效提高CBR系統(tǒng)的性能，適合于案例推理的實際應(yīng)用，結(jié)合粗糙集理論則能夠進一步優(yōu)化檢索的時間復(fù)雜度問題。

用Iris數(shù)據(jù)集進行實驗，它包括150個案例樣本、4個條件屬性和3個決策屬性，用其中90個樣本進行訓(xùn)練，其余60個樣本用于測試。運用Matlab對3種算法進行仿真，檢索時間采取10次仿真的加權(quán)平均值，約簡后訓(xùn)練數(shù)據(jù)集包含88個樣本、3個條件屬性，屬性重要度值分別為1.071 1、0.755 7和1.602 1。檢索結(jié)果如表2所示。

表2 約簡前后的檢索結(jié)果對比Table 2 The retrieval result comparison of before-and-after reduction

由表2可以看出，經(jīng)過粗糙集約簡后的案例檢索算法，在案例檢索效率和精度方面都有一定提高，尤其對于相似度檢索方法，效果更加明顯。由此可以看出，利用粗糙集方法對案例庫優(yōu)化能夠有效提高案例推理系統(tǒng)的檢索效率，從而能夠提高CBR系統(tǒng)的整體性能。

將基于粗糙集的案例檢索策略應(yīng)用于數(shù)字數(shù)據(jù)網(wǎng)故障診斷系統(tǒng)中，收集了網(wǎng)絡(luò)運行中出現(xiàn)的46個典型案例，包括9個條件屬性和9個決策屬性，限于篇幅，具體含義不作詳述。其中38個案例用于訓(xùn)練、8個用于測試，分別如表3和表4所示。

表3 訓(xùn)練案例表Table 3 The training case table

表4 測試案例表Table 4 The testing case table

顯然，表3中案例8和案例16為噪聲案例，案例36、37、38為冗余案例。運用粗糙集進行屬性約簡，得到約簡后的決策表，即刪除了相同冗余案例37、38，合并噪聲案例8和16成一個新案例，約去了冗余屬性c。

由于案例庫較小，采用相似度檢索算法實現(xiàn)。約簡后各屬性重要度如表5所示，可以看出屬性“a”和“g”的重要度明顯大于其它屬性的重要度，而它們分別代表終端數(shù)據(jù)收發(fā)情況和信道連接情況，對于信道類故障，它們也正是故障案例的重要特征，是專家判斷故障類型的主要依據(jù)。可見，基于粗糙集的屬性重要度值能真實反映屬性的重要程度及專家經(jīng)驗。

表5 基于粗糙集的屬性重要度表

檢索結(jié)果如表6所示，“/”兩端分別表示基于粗糙集的屬性重要度和默認屬性重要度檢索結(jié)果。當(dāng)取相似案例數(shù)為1時，能夠得到絕大部分待檢案例的正確故障類別；當(dāng)取相似案例數(shù)為2時，基于粗糙集重要度的相似度檢索得到了所有正確類別，而基于一般默認屬性重要度的相似度檢索則仍不能涵蓋所有的正確類別；當(dāng)取數(shù)為3時，兩種情況均涵蓋了所有的正確類別。

因此，在實際應(yīng)用中，相似度檢索方法在案例庫較小時能夠盡可能地檢索到所有相似案例，用于指導(dǎo)實際的故障診斷，而采用粗糙集重要度則能夠進一步提高案例檢索準確度，相對于一般默認屬性重要度都為1的情況，案例的檢索效率更高，也更有利于提高故障診斷的準確性。

表6 粗糙集與默認屬性重要度的相似度檢索結(jié)果Table 6 The similarity retrieval result of rough set and default attribute significance

5 結(jié) 論

根據(jù)案例推理系統(tǒng)的實際，分析了反映專家經(jīng)驗的屬性重要度，結(jié)合粗糙集理論，提出了不同案例庫下的案例檢索方法，十分適用于增長式的案例推理系統(tǒng)。與前人單純檢索策略相比，文中充分利用粗糙集理論、相似度計算和神經(jīng)網(wǎng)絡(luò)等方法的各自優(yōu)點，保證了CBR系統(tǒng)案例檢索的精度和時間效率。實驗結(jié)果表明，檢索策略能夠有效避免神經(jīng)網(wǎng)絡(luò)方法小案例庫的精度較低和大案例庫時相似度計算及KNN算法檢索時間線性增長的缺點，將其應(yīng)用于數(shù)字數(shù)據(jù)網(wǎng)故障診斷中，可以顯著提高案例檢索的精度，降低檢索時間。但此檢索策略不適用于動態(tài)案例庫的情況，這方面的工作需要進一步研究。

參考文獻：

[1] 王波，宋東，姜華男．基于粗糙集的CBR故障診斷案例的檢索方法研究[J]．計算機測量與控制，2007,15(11):1430-1433.

WANG Bo,SONG Dong,JIANG Hua-nan.Case Retrieve of Fault Diagnosis Expert System Based on CBR[J].Computer Measurement & Control，2007,15(11)：1430-1433.(in Chinese)

[2] LI Yan，Simon C K Shiu，Sankar K Pal．Combining Feature Reduction and Case Selection in Building CBR Classifiers[J]．IEEE Transactions on Knowledge and data Engineering，2006,18(3):415-429.

[3] 蔣占四，陳立平，羅年猛．最近鄰實例檢索相似度分析[J]．計算機集成制造系統(tǒng)，2007,13(6):1165-1168.

JIANG Zhan-si,CHEN Li-ping,LUO Nian-meng.Similarity analysis in nearest-neighbor case retrieval[J]．Computer Integrated Manufacturing Systms，2007,13(6)：1165-1168.(in Chinese)

[4] Piliouras N，Kalatzis I，Theocharakis P．Development of the probabilistic neural network-cubic least squares mapping classifier to assess carotid plaques risk[J]．Pattern Recognition Letters，2004,25(2):249-258.

[5] WU Jian-da，CHIANG Peng-hsin，CHANG Yo-wei．An expert system for fault diagnosis in internal combustion engines using probability neural network[J]．Expert Systems with Applications，2008,34(4):2704-2713.

[6] 劉江永，王大明．基于支持向量機的快速高光譜分類研究[J]．陜西師范大學(xué)學(xué)報(自然科學(xué)版)，2009,37(4):43-47.

LIU Jiang-yong, WANG Da-ming．Fast classification of hyperspectral data based on support vector machines[J]．Journal of Shaanxi Normal University(Natural Science Edition)，2009,37(4)：43-47.(in Chinese)