粗糙集在突發(fā)危機(jī)事件范例推理中的應(yīng)用研究

李寅煦

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

0 引 言

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

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

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

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

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

2 范例相似度算法

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

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

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

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

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

(1) 構(gòu)建一個(gè)n×(n+1)矩陣Fr用于存儲(chǔ)各屬性在相似辨識(shí)矩陣中出現(xiàn)的位置和頻率，其中n為條件屬性的個(gè)數(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);

遍歷相似辨識(shí)矩陣所有元素 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) 對(duì)矩陣Fr進(jìn)行整理排序.

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

{ 命題成立;

break;

}

}

(3) 計(jì)算各屬性的權(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行中已沒(mé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的相似辨識(shí)矩陣

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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

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

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

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

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

參考文獻(xiàn)

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

[2] 史忠直. 知識(shí)發(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.