基于粗糙集的CBR系統(tǒng)案例檢索策略

孫巖清1,2，尹樹(shù)華，林初善

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

1 引 言

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

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

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

2.1 屬性重要度定義

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

(1)

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

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

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

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

(2)

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

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

(3)

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

2.2 知識(shí)約簡(jiǎn)定義

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

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

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

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

3 相似案例檢索思想

3.1 案例相似度定義及分析

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

定義5：以dist(A,B)、sim(A,B)分別表示案例A、B之間的距離和相似度，則在最近鄰實(shí)例檢索中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)，即對(duì)稱性；

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

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

(4)

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

3.2 案例檢索過(guò)程

圖1為案例檢索流程圖。

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

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

4 實(shí)驗(yàn)結(jié)果和分析

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

4.1 案例檢索時(shí)間復(fù)雜度驗(yàn)證

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

圖2 3種檢索方法的時(shí)間對(duì)比Fig.2 The time comparison of three retrieval methods

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

4.2 案例檢索精度驗(yàn)證

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

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

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

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

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

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

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

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

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

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

表4 測(cè)試案例表Table 4 The testing case table

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

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

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

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

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

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

5 結(jié) 論

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

參考文獻(xiàn)：

[1] 王波，宋東，姜華男．基于粗糙集的CBR故障診斷案例的檢索方法研究[J]．計(jì)算機(jī)測(cè)量與控制，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] 蔣占四，陳立平，羅年猛．最近鄰實(shí)例檢索相似度分析[J]．計(jì)算機(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ī)的快速高光譜分類(lèi)研究[J]．陜西師范大學(xué)學(xué)報(bào)(自然科學(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)