李寅煦

(上海交通大學(xué)安泰經(jīng)濟與管理學(xué)院， 上海 200052)

0 引 言

粗糙集非常適合應(yīng)用于知識系統(tǒng)中以處理不完全信息、消除數(shù)據(jù)冗余、獲取邏輯規(guī)則并提高檢索的效率，因此已被廣泛應(yīng)用到CBR的理論和應(yīng)用研究中，其中最主要的就是范例屬性的約簡.利用粗糙集在范例推理系統(tǒng)中進行屬性約簡已經(jīng)在多個領(lǐng)域有了成功的應(yīng)用，比如分類選擇、疾病診斷、故障分析以及組合預(yù)測等等.突發(fā)危機事件，是指突然發(fā)生，造成或者可能造成嚴(yán)重社會危害，需要采取應(yīng)急處置措施予以應(yīng)對的自然災(zāi)害、事故災(zāi)難、公共衛(wèi)生事件和社會安全事件[1].在過去的十幾年中，突發(fā)危機事件已逐漸成為了一個全球關(guān)注的重大問題.本文介紹了粗糙集在突發(fā)危機事件范例推理中的應(yīng)用研究.

1 突發(fā)危機事件范例的表示和組織

范例的表示過程是將歷史事件信息與專家決策知識相結(jié)合，按照轉(zhuǎn)換規(guī)則轉(zhuǎn)化為計算機系統(tǒng)可識別、可處理信息的過程.根據(jù)知識表示的便捷性、有效性、可擴展性以及應(yīng)用領(lǐng)域的不同，可以借鑒人工智能領(lǐng)域的多種知識表示方法，如劇本、框架、謂詞邏輯、語義網(wǎng)絡(luò)和面向?qū)ο蟮谋硎痉椒ǖ萚2].盡管CBR中對范例概念的解釋目前還沒有統(tǒng)一的說法，但不論采用何種方法，范例的表達都要遵循一定的規(guī)則，形成規(guī)范的結(jié)構(gòu)，以便檢索和匹配.一般來說，最常用、也是最方便的方式是采用范例的特征向量.

對一個典型的范例，進行描述至少需要使用二元組：<問題描述，解描述>.在很多CBR系統(tǒng)中，也有采用三元組表示的：<問題描述，解描述，效果描述>.

考慮到面向?qū)ο蟊硎痉ㄋ哂械姆庋b性、模塊性、繼承性和易維護性等特征，本文在三元組的基礎(chǔ)上采用面向?qū)ο蟮膶哟谓Y(jié)構(gòu)表示法來實現(xiàn)突發(fā)危機范例的表示與存儲，以實現(xiàn)范例表示的靈活性與可擴充性.具體而言，對于范例C，用多元組的形式可以表示為C={T,P,S,R}，其中T表示范例類型描述，P表示范例問題描述，包括環(huán)境屬性，危機屬性等，S表示范例解決方案描述，R表示對問題采用S后產(chǎn)生的狀態(tài)或反饋信息，即范例決策結(jié)果的描述.

2 范例相似度算法

2.1 范例相似度基本函數(shù)

范例間相似性的度量在范例檢索中發(fā)揮著重要的作用，這也是為什么CBR系統(tǒng)有時也被稱為相似性檢索系統(tǒng)的原因.按照目前通常采用的范例庫組織形式，范例檢索一般用最近相鄰算法.由于通常用多維屬性向量表示范例，因此也稱為k-最近相鄰算法(K-Nearest Neighbour，KNN)[3].

KNN最近相鄰算法最初被用于分類，是一種無參數(shù)消極分類方法.對于給定的待檢索對象，KNN算法檢索得到與其最為相近的范例，并將該范例歸入最相近范例的類別中.顯然，KNN算法的精確率和可靠性在很大程度上依賴于范例間距離函數(shù)的定義，即范例相似度為范例屬性相似度的加權(quán)聚合.

2.2 基于粗糙集的范例相似度屬性加權(quán)算法和程序?qū)崿F(xiàn)

屬性加權(quán)算法直接關(guān)系著范例距離函數(shù)的有效性，它的確定對范例檢索的效果和效率有著決定性的影響.在文獻[3]中可以找到有關(guān)屬性加權(quán)算法的詳細(xì)介紹和綜述.

粗糙集算法可以進行屬性約簡，是一種屬性選擇操作[4, 5]，但從某種意義上來看，它仍然是一種確定屬性重要性，即屬性權(quán)重的方法.所有基于粗糙集的屬性加權(quán)算法都基于如下思想，即某屬性f將對象x∈U劃分到?jīng)Q策類Xi(i=1,…,r(d))這一過程及結(jié)果的貢獻程度[6].那些可以明確決定將某對象歸入某決策類的屬性權(quán)重為1，而那些與范例歸類無關(guān)的屬性權(quán)重為0，可以省去.

基于經(jīng)典粗糙集的屬性加權(quán)算法通過設(shè)計相關(guān)函數(shù)考察待加權(quán)屬性與對象分類之間的相關(guān)程度，因此這類加權(quán)算法通常從屬性的相對約簡集和決策類的相對正域著手進行分析，典型的如PRS(Proportional Rough Sets)算法和DRS(Dependence Rough Sets)算法[7].

PRS算法考察屬性f在約簡集中的出現(xiàn)頻率，以此為該屬性賦權(quán)，即

(1)

其中，R是關(guān)系的集合，card表示集合的勢.對于沒有在任何一個約簡集中出現(xiàn)的屬性f，其權(quán)重μ(f)為0，而在核中出現(xiàn)的屬性，其權(quán)重μ(f)為1.

DRS算法計算屬性的依賴系數(shù)，即屬性重要度，以此作為屬性的權(quán)重.

(2)

其中，R為條件屬性C對決策屬性D的相對約簡集，D=U/D，兩者皆可從原始數(shù)據(jù)中計算得到.POSR(D)是根據(jù)約簡集R所表示知識得到的關(guān)于決策屬性D的相對正域，POS(R-{f})(D)表示在約簡集R中除去屬性f后根據(jù)剩余屬性所表示知識得到的關(guān)于決策屬性D的相對正域.

計算相對正域及其變化非常復(fù)雜，計算代價很高，因此在實際應(yīng)用中并不常見.但經(jīng)過分析可以發(fā)現(xiàn)，基于粗糙集對范例屬性進行加權(quán)，主要考察的是屬性對信息系統(tǒng)的分類能力，即辨識不同范例的能力，而計算相對正域的變化只是度量分類能力的一種方法.

從屬性約簡的計算過程中可以看出，在相似辨識矩陣中，出現(xiàn)最小勢矩陣元素中的屬性一定是核屬性，而出現(xiàn)在勢較小的元素中的屬性則更可能出現(xiàn)在約簡集中.由此可見，可利用相似辨識矩陣及勢為屬性加權(quán).那些在低勢元素中出現(xiàn)頻率較高的元素對范例分類的貢獻較大，將被賦予較高的權(quán)[8].

首先，根據(jù)預(yù)先定義的各屬性相似度閾值，加權(quán)算法對范例進行兩兩比較，構(gòu)建相似辨識矩陣.然后，算法考察各條件屬性在相似辨識矩陣SDn×n中出現(xiàn)的位置和頻率，并以此為各屬性進行打分，在最低勢矩陣元素中出現(xiàn)頻率最高的屬性擁有最高的權(quán)重分?jǐn)?shù).最后對所有屬性的權(quán)重分?jǐn)?shù)進行規(guī)范化，使其和為1.打分時，考慮的因素包括出現(xiàn)位置(矩陣元素的勢，勢低則分?jǐn)?shù)高)和出現(xiàn)頻率(頻率高則分?jǐn)?shù)高).

在屬性約簡算法中，如果屬性被添加到約簡集RED(C)中，則該屬性將從相似辨識矩陣中刪去.類似地，基于相似辨識矩陣的屬性加權(quán)算法考察屬性在矩陣中出現(xiàn)的位置和頻率，如果對于某一勢水平中，屬性a的出現(xiàn)頻率比屬性b高，那么屬性a比屬性b更為重要，不必再在更高的勢中進行進一步的比較.因此，在具體操作過程中屬性權(quán)重的分配是基于相對關(guān)系確定的.在確定最高權(quán)重屬性后，其他屬性的分值以差值的方式表示.例如：如果包含屬性a的矩陣元素的最低的勢為3(假設(shè)相應(yīng)的分值權(quán)重為5)，則出現(xiàn)的頻率為5；若屬性b在同級別元素中出現(xiàn)頻率為2次，那么兩者間的分值差則為5×(5-2)=15；若屬性b在同級別元素中也出現(xiàn)了5次，那么將在高一級別矩陣元素中進行比較.

(1) 構(gòu)建一個n×(n+1)矩陣Fr用于存儲各屬性在相似辨識矩陣中出現(xiàn)的位置和頻率，其中n為條件屬性的個數(shù),參數(shù)的初始值均為0.

i=j=l=m=0; k=1;

for (i=1; i<=n; i++)

{ for (j=1; j<=n; j++) { l=card(i,j);

遍歷相似辨識矩陣所有元素 SD(i,j);

while (屬性 x 出現(xiàn))

{for (m=1; m<=k; m++)

{if (x==Fr(m,n+1)) break;

} /* 在Fr中尋找屬性x */

if (m==k)

{Fr(m,n+1)=x; k++;

} /* 屬性x不包含在Fr中，添加 */

Fr(m,l)++;

}

}

}

(2) 對矩陣Fr進行整理排序.

n--;

While (n>0)

{j=1;

for (i=1; i<=n; i++)

{比較行i和行(i+1);

{整行交換行i和行(i+1);

j=i;

}

n=j; /* 行j以后的行已整理完成 */

}

}

我們定義行i > 行(i+1)成立,當(dāng)：

for (j=1; j<=n; j++)

{ if (Fr(i,j)>Fr(i+1,j))

根據(jù)餌料魚不同的配套模式、設(shè)計單產(chǎn)量、上市季節(jié)等不同，翹嘴鱖“華康1號”養(yǎng)殖可分為餌料魚專池飼養(yǎng)和餌料魚、鱖魚混養(yǎng)兩種模式。它可以按照鱖魚共性的技術(shù)標(biāo)準(zhǔn)、操作規(guī)范和生產(chǎn)流程進行養(yǎng)殖，諸如清塘、苗種消毒，或單一品種精養(yǎng)，或多品種立體混養(yǎng)或者輪捕輪放，飼料投喂，開展病害防治以及防災(zāi)減災(zāi)，同時該魚養(yǎng)殖也有個性要求。

{ 命題成立;

break;

}

}

(3) 計算各屬性的權(quán)重分?jǐn)?shù).

for (j=1; j<=n; j++)

{if (Fr(n,j)==0)

{ score(n)=Fr(n,j+1)*(n-j);

break;

}

}

for (i=n-1; i>0; i--)

{for (j=n; j>0; j--)

{if (Fr(i,j)==0)

for (k=j+1; k<=n; k++)

{while (Fr(i,j+1)-Fr(i+1,j+1)<>0)

score(i)=score(i+1)+(Fr(i,j+1)-Fr(i+1,j+1))*(n-j);

}

break;

}

}

if (j==0) /*第i行中已沒有空元素*/

{for (k=j+1; k<=n; k++)

{while (Fr(i,j+1)-Fr(i+1,j+1)<>0)

score(i)=score(i+1)+(Fr(i,j+1)-Fr(i+1,j+1))*(n-j);

}

}

}

(4) 將各屬性分值規(guī)范化，使屬性權(quán)重和為1，即

(3)

表1 信息系統(tǒng)S的相似辨識矩陣

下面我們通過一個實例說明上述加權(quán)算法.假設(shè)信息系統(tǒng)S=U，其中共有范例12個，屬性集R的勢為5.經(jīng)計算，其相似辨識矩陣如表1所示[8].

由此，我們可統(tǒng)計各屬性在相似辨識矩陣中出現(xiàn)的位置和頻率，如表2所示.

此表閱讀方法如下：屬性a3在勢為3的矩陣元素中出現(xiàn)的次數(shù)為4，則表中對應(yīng)的位置數(shù)值為4.相似辨識矩陣中元素的勢最低為1，最高為5.勢為1的元素分值為5，勢升高時分值依次降低，勢為5時分值為1.計分過程從表中最后一行開始.屬性a4出現(xiàn)的元素勢最高為3，出現(xiàn)頻率為2，則其分值為3×2=6.由于屬性a2出現(xiàn)在勢為2中的元素中，而屬性a4沒有，因此其分值差為4×(2-0)=8，屬性a2分值為14.由于屬性a1和屬性a2在更高的勢中出現(xiàn)頻率相同，在勢為2的元素中出現(xiàn)頻率仍相同，在勢為3的元素中進行比較，因此分值差為3×(6-4)=6，屬性a1分值為20.依次類推，屬性a1和屬性a5的分值分別為25和33.將屬性分值規(guī)范化后，可得各屬性權(quán)重分別為0.204 1，0.142 9，0.255 1，0.061 2和0.336 7.

表2 基于相似辨識矩陣的屬性權(quán)重計分表

由相似辨識矩陣中，我們可以計算得出核屬性為{a3,a5}，約簡集為{a1,a3,a5}或{a2,a3,a5}.核屬性權(quán)重最高，約簡集中其余屬性權(quán)重次之，其它屬性權(quán)重最小.如有必要，被約簡屬性可以不做加權(quán).如上述示例中，屬性a4不在約簡集中，被刪去，這樣其它屬性的權(quán)重依次為0.217 4，0.152 2，0.271 7和0.358 7.

2 粗糙集在突發(fā)危機事件范例約簡中的應(yīng)用舉例

以水災(zāi)為例，結(jié)合范例庫示范粗糙集在突發(fā)危機事件范例約簡中的應(yīng)用.

本文基于自然基金項目，已構(gòu)建了一個突發(fā)危機事件案例庫，其中記錄了100多條各種類型的防汛應(yīng)急范例.由于本例重點研究粗糙集的范例檢索和匹配，因而并沒有將范例的決策屬性列出.我們?nèi)∑渲?0個范例構(gòu)建信息系統(tǒng)，并基于此表進行范例推理過程的演示.

根據(jù)本節(jié)中描述的算法，在進行范例檢索之前的準(zhǔn)備工作依次包括：范例屬性相似度度量、相似辨識矩陣構(gòu)建、范例屬性約簡以及范例屬性加權(quán).

以范例A0001和范例A0002為例，我們舉例說明范例屬性相似度度量方法.

“死亡人口”屬于精確數(shù)值屬性.考慮到范例A0007“印度洋海嘯”事件死亡人數(shù)近30萬，是一個例外事件，若將其考慮在內(nèi)將影響相似度的度量結(jié)果，因此本屬性值域定義為[0，1 126].范例A0001和A0002在屬性“死亡人口”上的相似度為SIMa7=1-(121-117)/1 126=0.996 4.

圖1 “降水量”屬性的梯形表示

“災(zāi)害類型”為精確符號屬性，范例A0001和A0002在此范例上相似度為1.

“降雨量”屬于模糊區(qū)間屬性.屬性值域為[0，650].范例A0001和A0002屬性取值分別為80～100和50～90，兩者用梯形表示如圖1所示.

由此，根據(jù)預(yù)先定義的范例屬性相似度閾值，可以確定范例A0001和A0002在屬性a8和a14上不相似，相似辨識矩陣對應(yīng)元素SD1,2={a8,a14}.

6 結(jié)束語

上述研究表明，基于粗糙集的算法有助于更高效地獲得高精確度的相似案例，可應(yīng)用于如下兩個方面：

(1) 范例庫維護. 當(dāng)信息系統(tǒng)中的信息容量(即對象數(shù))不同時，粗糙集將得到不同的約簡結(jié)果.為了保證不損失范例庫中的信息，范例以全量范例的形式保存(即保存范例的所有屬性信息)，而在每次進行范例庫維護之前需重新計算范例的屬性約簡，從而既提高了效率，又健全了系統(tǒng).

(2) 范例檢索. 由于突發(fā)危機事件應(yīng)急決策信息水平低、有限決策時限短等特殊情況，在進行危機范例檢索時，如果要求決策者輸入所有的范例屬性值才能進行范例檢索，則顯然是不實際的.粗糙集在保證檢索效果和效率的前提下減少檢索時必要的范例屬性數(shù)目，對于面向突發(fā)危機事件應(yīng)急決策支持的范例推理系統(tǒng)而言意義重大.

具體來說，當(dāng)決策者面對新的突發(fā)危機事件問題，需要決定是否采取某行動(即范例的某一決策屬性SK)以及如何采取該行動(即決策屬性的SK取值),那么通過構(gòu)建決策信息系統(tǒng)，并利用粗糙集對其進行處理，決策者就能夠相應(yīng)地了解到在過去的實踐中，在哪些情況下采取了該行動，具體都是如何操作的.這樣，如果新的突發(fā)危機事件問題與歷史范例相匹配，就能實施同樣的方案；即使沒有完全匹配的信息，通過分析相似范例，也能在該決策屬性與范例其他條件屬性之間建立邏輯關(guān)系，協(xié)助決策者對行動方案進行選擇.

因此，基于粗糙集的范例推理能有效地提高系統(tǒng)的效率，幫助更高效地獲得高精確度的相似案例，從而提高突發(fā)危機事件決策的效用.

參考文獻

[1] 國務(wù)院突發(fā)危機應(yīng)急管理所. 國家突發(fā)公共事件總體應(yīng)急預(yù)案[M]. 北京: 中國法制出版社, 2006:1-1.

[2] 史忠直. 知識發(fā)現(xiàn)[M]. 北京: 清華大學(xué)出版社, 2002: 3-4.

[3] Wettschereck, D., D. Aha, T. Mohri. A review and empirical evaluation of feature weighting methods for a class of lazy learning algorithms[J]. Artificial Intelligence Review, 1997, 11(1):273-314.

[4] Aamodt, A.. Knowledge-intensive case-based reasoning in creek[J]. Advances in Case-Based Reasoning, 2004,(5): 793-850.

[5] B rner, K.. Structural similarity as guidance in case-based design[J]. Topics in Case-Based Reasoning, 1994, (5):197-208.

[6] Brown, M.. An underlying memory model to support case retrieval[J]. Topics in Case-Based Reasoning, 1994,(1):132-143.

[7] Salam, M.， E. Golobardes. Analysing rough sets weighting methods for case-based reasoning systems[J]. Inteligencia artificial, 2002,(6): 15-16.

[8] Tao, J.,S. Huizhang. Feature Selection and Weighting Method Based on Similarity Rough Set for CBR[R]. Service Operations and Logistics, and Informatics, 2007:948-952.