于 楊，許少華，陳秀紅 (大慶石油學(xué)院計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318)

相似粗糙集理論在CBR系統(tǒng)中的應(yīng)用研究

于 楊，許少華，陳秀紅 (大慶石油學(xué)院計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318)

針對(duì)連續(xù)型屬性離散化對(duì)相似度計(jì)算造成的影響，給出了一種基于相似粗糙集的屬性權(quán)值計(jì)算方法，并提出基于相似粗糙集的CBR系統(tǒng)案例推理模型。經(jīng)實(shí)例驗(yàn)證，該方法在先驗(yàn)知識(shí)不足且連續(xù)型屬性眾多的案例推理應(yīng)用中具有很好的適用性。

相似粗糙集；CBR；決策表；相似關(guān)系；屬性權(quán)值

在基于案例推理CBR(Case Base Reasoning)系統(tǒng)中，從案例庫中自動(dòng)提取出有用而具有代表性的案例是案例推理的一個(gè)重要步驟。為了更準(zhǔn)確的獲取案例，近年來，人們提出了多種案例獲取的方法。如基于AHP的CBR系統(tǒng)案例檢索模型[1]，應(yīng)用本體的分布式案例推理方法[2]等。但這些方法在案例提取過程中，針對(duì)屬性權(quán)值的選定，都要求有很準(zhǔn)確的領(lǐng)域先驗(yàn)知識(shí)，并加入了很多主觀因素。為了解決這一問題，文獻(xiàn)[3～5]提出了應(yīng)用粗糙集理論進(jìn)行案例推理的方法，取得了很好的效果。但該方法要求對(duì)案例中定量的連續(xù)屬性值進(jìn)行屬性離散化，而大多數(shù)的屬性離散化方法都會(huì)產(chǎn)生案例相似度測(cè)量誤差, 造成案例推理的不準(zhǔn)確性。為此，筆者基于相似粗糙集理論，提出了一種基于相似粗糙集的案例推理模型及案例篩選原則，建立了在先驗(yàn)知識(shí)不足的情況下利用粗糙集理論計(jì)算特征權(quán)值的模型，給出了案例相似性評(píng)估方法，提高了相關(guān)案例提取的準(zhǔn)確性。

1 基本理論與方法

在相似粗糙集(Similarity Rough Set,SRS)理論中，知識(shí)被認(rèn)為是一種對(duì)客觀事物進(jìn)行分類的能力，為規(guī)范化起見，往往將考察的客觀事物稱為對(duì)象。通常，在SRS中，知識(shí)系統(tǒng)可以定義為S=(U,A,V,f)，其中,U為論域，表示一組有限非空的對(duì)象集；A=C∪D表示屬性的集合，其中,C={c1,c2,…,cp}是條件屬性集合；D={d1,d2,…,dp}為決策屬性集合；V=∪Va是所有屬性值域的集合，其中a∈A，Va為屬性a的值域；f=U×A→V是一個(gè)信息函數(shù)，表示U中每個(gè)對(duì)象的屬性取值[3,4]。

1.1決策表

通過以上方式定義的知識(shí)系統(tǒng)可以方便地用表格來實(shí)現(xiàn)其中列表示屬性，一個(gè)屬性對(duì)應(yīng)一個(gè)等價(jià)關(guān)系，一行表示一個(gè)對(duì)象，一個(gè)表可以看作是被定義的一族等價(jià)關(guān)系的集合。知識(shí)表達(dá)系統(tǒng)的數(shù)據(jù)表可分為決策表與非決策表。其中，決策表是一種特殊而重要的知識(shí)表達(dá)系統(tǒng)，在決策應(yīng)用中起著至關(guān)重要的作用。當(dāng)數(shù)據(jù)表中的決策屬性集不為空時(shí)，該數(shù)據(jù)表便可稱為決策表，一般的決策表都是單決策屬性表，即p=1。

1.2屬性相似度計(jì)算

對(duì)象的屬性可以根據(jù)取值范圍的不同分為連續(xù)型屬性與枚舉型屬性。對(duì)于不同類型的屬性，其相似度的計(jì)算方法如下：

定義1(屬性相似度[7]) 設(shè)i與j為決策表中的2個(gè)不同對(duì)象，Vi與Vj分別表示i和j在屬性a上的取值，Va min與Va max表示屬性a的最小與最大取值， 表示對(duì)象i和j在屬性a上的相似程度，則對(duì)于連續(xù)型屬性有：

(1)

對(duì)于枚舉型屬性有：

(2)

從以上定義可以看出，屬性相似度的取值Sa(i,j)∈[0,1]，故可以為屬性選定一個(gè)相似閾值ta∈[0,1]，當(dāng)且僅當(dāng)Sa(i,j)≥ta時(shí)，對(duì)象i與j在屬性a上相似。

1.3屬性權(quán)值確定

屬性權(quán)值的大小反映了在案例相似性評(píng)估中各特征屬性的相對(duì)重要程度，取值的不同將直接影響到評(píng)估結(jié)果。目前，常用的定權(quán)方法主要有專家咨詢法、成對(duì)比較法、調(diào)查統(tǒng)計(jì)法、 無差異折衷法以及相關(guān)分析法等。在上述方法中，前4種方法一般是在領(lǐng)域?qū)＜蚁闰?yàn)知識(shí)的基礎(chǔ)上通過事先假設(shè)或采用平權(quán)的辦法來確定特征屬性的權(quán)重值，無疑會(huì)給最相似實(shí)例檢索的準(zhǔn)確性造成影響；后一種方法基于一種統(tǒng)計(jì)的方法，相對(duì)于前者有一定的進(jìn)步，但從總體看，傳統(tǒng)的案例特征屬性定權(quán)方法過分依賴于主觀判斷和經(jīng)驗(yàn)[5]。

在CBR系統(tǒng)中應(yīng)用粗糙集理論，其本質(zhì)是在無先驗(yàn)知識(shí)或先驗(yàn)知識(shí)不足以及特征屬性確定的情況下，根據(jù)實(shí)際數(shù)據(jù)來確定各特征屬性在最終案例推理中所起的作用大小，即屬性權(quán)值。為了達(dá)到這一目的，引入以下定義[6～11]：

定義2(相似關(guān)系) 設(shè)一個(gè)屬性子集B?A，定義B上的相似關(guān)系為SIMB(i,j)，對(duì)象相似閾值為t∈[0,1]，集合的基為card(*)，則當(dāng)且僅當(dāng)

(3)

時(shí)稱對(duì)象i與j在屬性集B上相似，記為SIMB(i,j)。即只要i與j在屬性集B中的一部分屬性相似，就可以認(rèn)為對(duì)象i與j在屬性集B上相似，這個(gè)“一部分”占屬性集B的比例由對(duì)象相似閾值t確定。把所有在屬性集B上與對(duì)象i相似的集合(也叫對(duì)象i在相似關(guān)系SIMB上的相似類)記做：

SIMB(i)={j∈U:SIM(i,j)}

(4)

SIMB-(X)={x∈X:SIMB(x)?X}

(5)

其中，X的下近似表示對(duì)應(yīng)相似類SIMB(x)一定能歸入X的所有元素x的集合，而X的上近似則表示所有可能歸入X的元素的集合。

定義4(相似粗糙集的正域) 設(shè)U/d表示對(duì)象集U依據(jù)決策屬性d進(jìn)行的劃分，屬性集B?A，決策屬性d依據(jù)相似關(guān)系，相對(duì)于B的正域記為POSB(d)，則有：

(6)

正域表示根據(jù)相似關(guān)系SIMB，能夠確定劃入U(xiǎn)/d類的對(duì)象集合。

定義5(屬性集的分類能力) 不同屬性集對(duì)對(duì)象的分類能力不同，用rB(d)表示根據(jù)相似關(guān)系SIMB，屬性集B?A在決策屬性d上的分類能力，則有：

(7)

定義6(屬性權(quán)值) 對(duì)于同樣的決策屬性d，每個(gè)條件屬性的重要程度不同，這種重要程度經(jīng)過權(quán)值化之后便成為了屬性權(quán)值，設(shè)KB(a)與WB(a)分別表示在相似關(guān)系SIMB下，條件屬性a的重要度及權(quán)值，則有：

KB(a)=rB(d)-rB-{a}(d)

(8)

(9)

顯然有：

0≤KB(a)lt;rB(d)≤1 0≤WB(a)≤1

1.4屬性約簡

定義7(屬性約簡) 對(duì)屬性集B?A，依據(jù)相似關(guān)系，如果有POSB(d)=POSA(d)且不存在B1?B令POSB1(d)=POSB(d)，則稱屬性集B為A的一個(gè)約簡。

2 基于SRS的案例推理模型

圖1 基于SRS的案例推理模型

如圖1所示，基于SRS的案例推理的過程可以分為權(quán)值定期維護(hù)、案例推理與案例重用3個(gè)階段。其中權(quán)值定期維護(hù)是筆者討論的重點(diǎn)，它包括以下5個(gè)重要步驟：

1)根據(jù)式(3)計(jì)算相對(duì)于所有條件屬性集及決策屬性集的相似關(guān)系；

2)計(jì)算相對(duì)所有缺少一個(gè)條件屬性的屬性集的相似關(guān)系；

3)根據(jù)式(5)、(6)、(7)和式(8)計(jì)算出屬性的重要度；

4)根據(jù)重要度對(duì)屬性集進(jìn)行約簡；

5)根據(jù)式(9)對(duì)屬性重要度進(jìn)行權(quán)值化處理。

3 實(shí) 例

表1為一個(gè)簡化的壓裂酸化效果案例庫，下面以其為例進(jìn)行權(quán)值的計(jì)算。

表1 壓裂酸化效果案例

設(shè)c1表示產(chǎn)層有效厚度，c2表示含油飽和度，c3表示滲透率，c4表示有效孔隙度，c5表示油層壓力，c6表示泥質(zhì)含量，d表示壓裂效果。

首先，選取閾值ta與t分別為0.75與0.8，經(jīng)Step1與Step2可以得出：

U/C={{1，2，5}，{3}，{4}，{6}，{7}}}U/d={{1，2，5，6}，{3，4，7}}

U/C-c1={{1，2，5，6}，{3}，{4}，{7}}}U/C-c2={{1，2，5，7}，{3}，{4}，{6}}}

U/C-c3={{1，2，5}，{3}，{4}，{6}，{7}}}U/C-c4={{1，2，5}，{3}，{4}，{6}，{7}}}

U/C-c5={{1，2，5，6}，{3}，{4}，{7}}}U/C-c6={{1，2，5，7}，{3}，{4}，{6}}}

之后，根據(jù)式(5)、(6)、(7)計(jì)算出：

根據(jù)式(8)可以得出各屬性的重要度為：

由于屬性c3與c4的重要度為0，故在計(jì)算權(quán)值與推理的過程中可以將去掉，這樣就得到了一個(gè)條件屬性集的約簡 。根據(jù)式(9)它們的權(quán)值分別為：

4 結(jié) 語

筆者介紹了SRS的基本概念與理論，并說明它在CBR中應(yīng)用的特點(diǎn)和優(yōu)勢(shì)。在提出基于SRS案例推理模型的同時(shí)，給出應(yīng)用相似粗糙集計(jì)算屬性權(quán)值的方法，并給出了計(jì)算實(shí)例。當(dāng)然，在應(yīng)用SRS進(jìn)行權(quán)值計(jì)算時(shí)，閾值的選取會(huì)產(chǎn)生很大影響。因此，研究如何對(duì)閾值選取進(jìn)行優(yōu)化將十分有意義，有待于進(jìn)一步深入研究。

[1]屈喜龍, 杜娟, 孫林夫. 一個(gè)基于AHP的CBR系統(tǒng)實(shí)例檢索模型[J]. 計(jì)算機(jī)應(yīng)用研究, 2005,22(4)：33～35.

[2]丁劍飛，何玉林，李成武.基于本體的分布式CBR設(shè)計(jì)系統(tǒng)[J].計(jì)算機(jī)工程, 2007,33(21)：183～185.

[3]Salarno M，Golobardes E.Rough sets reduction techniques for Case-based reasoning[J].Pro-ceedings of ICCBR，2001：466-482.

[4]季賽，沈星，沈超.基于粗糙集和相似度量的CBR檢索方法[J].計(jì)算機(jī)工程與應(yīng)用, 2006,42(13):172～174.

[5]孫翎，張金隆，遲嘉昱.基于粗糙集的CBR系統(tǒng)案例特征項(xiàng)權(quán)值確定[J].計(jì)算機(jī)工程與應(yīng)用, 2003,39(30):44～46.

[6]Lu Yi-juan，Ni Zhi-wei，Hu Cai-ping.Technique used in CBR based on similarity rough set[J].Computer Engineering，2003，29(19)：50～51.

[7]季賽，袁慎芳，成亞萍.基于相似粗糙集的CBR范例提取算法[J].小型微型計(jì)算機(jī)系統(tǒng), 2007,(6):1072～0175.

[8]盧亦娟，倪志偉，胡彩平.基于相似粗糙集的范例推理技術(shù)[J].計(jì)算機(jī)工程，2003,(19):50～51.

[9]Kryszkiewicz M. Rough set approach to incomplete information systems[J].Information Sciences, 1998.39～49.

[10]胡可云，陸玉昌，石純一.粗糙集理論及其應(yīng)用進(jìn)展[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版)，2001，(1):64～68.

[11]吳今培，孫德山.現(xiàn)代數(shù)據(jù)分析[M].北京：機(jī)械工業(yè)出版社，2006.102～104.

[編輯] 易國華

TP18；TP31

A

1673-1409(2009)01-N065-04

2008-12-24

于楊(1984-)，男，2006年大學(xué)畢業(yè)，碩士生，現(xiàn)主要從事圖像處理及模式識(shí)別方面的研究工作。