基于粗糙集的CBR系統案例檢索策略

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

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

1 引 言

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

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

2 粗糙集相關概念

2.1 屬性重要度定義

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

(1)

定義2：設S=(U,A,V,f)為一個信息系統，A=C∪D，?R?C，且R在對象集合U上產生的劃分為: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系統，約簡應既能很好地反映專家經驗知識，又能生成正確的決策規則，因此，應該綜合考慮屬性決策分類和本身重要度兩方面的因素。

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

(3)

式中，0≤w≤1。當w=1時，同等考慮屬性對決策分類的影響度和屬性本身的重要度，最大化地反映領域專家的經驗知識；當w=0時，僅考慮屬性對決策分類的影響，而一般情況下，對于CBR系統采取前者的定義。

2.2 知識約簡定義

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

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

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

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

3 相似案例檢索思想

3.1 案例相似度定義及分析

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

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

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

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

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

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

(4)

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

3.2 案例檢索過程

圖1為案例檢索流程圖。

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

利用粗糙集理論首先對案例庫進行屬性約簡，并計算約簡后的屬性重要度權值，而后在小案例庫時采取相似度計算方法檢索案例，在大案例庫時采用概率神經網絡實現，從而充分利用相似度計算和神經網絡的優點，取長補短，達到CBR系統案例檢索的最優效果。

4 實驗結果和分析

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

4.1 案例檢索時間復雜度驗證

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

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

由圖2可以看出，在小數據集時，3種檢索算法耗時均很小，且相似度計算方法性能更優；而隨著案例的增多，基于相似度計算和KNN算法的檢索時間會線性增長，神經網絡算法則在一定的時間點或范圍內保持穩態。

4.2 案例檢索精度驗證

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

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

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

4.3 基于粗糙集的案例檢索驗證及應用

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

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

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

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

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

表3 訓練案例表Table 3 The training case table

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

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

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

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

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

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

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

5 結 論

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

參考文獻：

[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]．計算機集成制造系統，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]．陜西師范大學學報(自然科學版)，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)