基于Hypergraph的突發(fā)事件情景案例表示與檢索方法研究*

王興鵬 桂 莉 王 燦

(1.石家莊鐵道大學(xué)管理學(xué)院 石家莊 050043;2.河北經(jīng)貿(mào)大學(xué)公共管理學(xué)院 石家莊 050061)

突發(fā)事件是一個(gè)復(fù)雜、動(dòng)態(tài)演化的系統(tǒng),隨著事件的發(fā)展,其特征、形式及后果不斷發(fā)生變化?！扒榫?應(yīng)對(duì)”模式將突發(fā)事件發(fā)展演化過(guò)程看作是由若干動(dòng)態(tài)情景構(gòu)成的不斷演化的情景網(wǎng)絡(luò),根據(jù)不斷發(fā)展變化的情景,動(dòng)態(tài)生成處置方案予以應(yīng)對(duì),是目前突發(fā)事件應(yīng)急決策的基本范式[1]。

在突發(fā)事件應(yīng)對(duì)中,決策者面臨時(shí)間緊、信息少、經(jīng)驗(yàn)不足等困境,基于案例推理(Case-Based Reasoning,CBR)是有效提高決策效率和質(zhì)量的技術(shù)方法,“情景-應(yīng)對(duì)”模式下基于案例推理的關(guān)鍵問(wèn)題是情景案例的知識(shí)表示和檢索問(wèn)題。突發(fā)事件情景具有跨領(lǐng)域、結(jié)構(gòu)復(fù)雜、動(dòng)態(tài)關(guān)聯(lián)等特點(diǎn),這給情景案例的知識(shí)表示和檢索方法帶來(lái)了挑戰(zhàn)。很多學(xué)者在這方面進(jìn)行了有益探索和研究:王寧等提出了基于知識(shí)元的案例表示和檢索算法[2];錢(qián)靜等基于多維情景分析思想,提出了案例表示和推理方法[3];王琳等基于本體構(gòu)建了糧食應(yīng)急案例表示模型[4];樊舒基于復(fù)雜網(wǎng)絡(luò)研究了應(yīng)急案例庫(kù)結(jié)構(gòu)和案例的表示[5]。

現(xiàn)有案例表示和檢索方法大都將每個(gè)案例描述為結(jié)構(gòu)固定、孤立無(wú)關(guān)的個(gè)體,并沒(méi)有很好體現(xiàn)情景的動(dòng)態(tài)變化特征,基于語(yǔ)義網(wǎng)等普通圖模型也只能表達(dá)對(duì)象之間的二元關(guān)系,對(duì)于情景要素之間的多元復(fù)雜關(guān)系缺乏描述能力。而超圖在拓?fù)浣Y(jié)構(gòu)上對(duì)普通圖的進(jìn)行了拓展,具有比普通圖更強(qiáng)的描述能力,能夠更好體現(xiàn)對(duì)象間的多元關(guān)系。鑒于此,本文將超圖理論引入情景案例表示和檢索中,在對(duì)突發(fā)事件情景案例結(jié)構(gòu)特征進(jìn)行分析基礎(chǔ)上,構(gòu)建了基于超圖的突發(fā)事件情景案例表示模型,并在此基礎(chǔ)上結(jié)合超圖結(jié)構(gòu)特征提出了兩階段案例檢索策略和相似度計(jì)算方法,希望本文的探索能夠推動(dòng)突發(fā)事件案例推理的研究和應(yīng)用進(jìn)一步深入。

1 突發(fā)事件情景案例特征分析

情景是對(duì)突發(fā)事件現(xiàn)狀和可能演變態(tài)勢(shì)的描述[6],是突發(fā)事件靜態(tài)結(jié)構(gòu)特征與動(dòng)態(tài)演化特征的集成。根據(jù)突發(fā)事件演化過(guò)程,情景可分為:發(fā)生情景、發(fā)展情景、演化情景和結(jié)束情景[7]。作為突發(fā)事件情景應(yīng)對(duì)經(jīng)驗(yàn)的總結(jié),情景案例是對(duì)事件所經(jīng)歷的重要情景及其處置過(guò)程的描述,如圖1所示。

圖1 情景案例的組成

從圖1可以看出,一個(gè)完整的事件會(huì)包含若干相關(guān)聯(lián)的情景,情景案例不僅要描述具體情景節(jié)點(diǎn)的結(jié)構(gòu)特征(靜態(tài)特征),還應(yīng)描述情景之間的演化關(guān)聯(lián)特征(動(dòng)態(tài)特征),即情景鏈。在情景案例中情景是案例問(wèn)題特征描述和表示的基本單元,是案例檢索的依據(jù),而應(yīng)對(duì)方案則是案例檢索的目標(biāo)和結(jié)果,因此,本文重點(diǎn)討論情景要素的表示和檢索問(wèn)題。

2 情景案例知識(shí)表示需求與超圖理論

2.1 情景案例知識(shí)表示需求

通過(guò)對(duì)大量突發(fā)事件情景案例分析,可以總結(jié)出突發(fā)事件情景具有如下復(fù)雜性特征:

a.情景構(gòu)成要素復(fù)雜:情景由致災(zāi)事件、承災(zāi)體等多要素構(gòu)成,而且這些要素是相互影響、相互作用的。

b.情景之間關(guān)系復(fù)雜:情景不是孤立的,情景之間相互連接、交叉或耦合,表現(xiàn)為復(fù)雜的情景鏈。

突發(fā)事件情景的復(fù)雜性對(duì)情景案例的知識(shí)表示提出了更高的要求。常用的框架、本體、語(yǔ)義網(wǎng)等表示方法各有優(yōu)點(diǎn),但均不能很好描述突發(fā)事件情景間復(fù)雜演化關(guān)系,在描述對(duì)象間關(guān)聯(lián)關(guān)系方面,圖論是一種直觀、有效的建模工具,近年來(lái),認(rèn)知圖[8]、主題圖[9]、概率圖[10]等基于圖論的建模方法在應(yīng)急管理中有很多應(yīng)用,但這些模型都屬于普通圖范疇,只能描述對(duì)象間簡(jiǎn)單的二元關(guān)系,對(duì)于突發(fā)事件情景間多元、多層次關(guān)系描述能力有限,而超圖作為普通圖的拓展,具有更強(qiáng)的描述分析和建模能力,可以描述對(duì)象之間的多元關(guān)系。

2.2 超圖理論

1973年,Berge首次提出了超圖(Hypergraph)理論[11],經(jīng)過(guò)多年發(fā)展?jié)u成體系,被廣泛應(yīng)用于科研合作關(guān)系[12]、社交網(wǎng)絡(luò)[13]、交通網(wǎng)絡(luò)[14]等復(fù)雜網(wǎng)絡(luò)的研究中,近年來(lái),有學(xué)者開(kāi)始嘗試將超圖理論應(yīng)用于突發(fā)事件應(yīng)急管理領(lǐng)域,李勇建等利用超圖模型描述了地震災(zāi)害鏈中事件之間屬性的關(guān)聯(lián)關(guān)系,并提出了邊和節(jié)點(diǎn)重要性和網(wǎng)絡(luò)關(guān)聯(lián)度的評(píng)估方法[15]李鋒等基于超圖構(gòu)建了洪水災(zāi)害事件關(guān)聯(lián)度評(píng)價(jià)模型[16],這些成果為本文研究提供了很好借鑒和啟發(fā)。

2.2.1超圖的定義及其表示

超圖表示方式有多種,除了定義中的集合式外,還有閉合曲線、關(guān)聯(lián)矩陣表示等。圖2描述的是一個(gè)7個(gè)節(jié)點(diǎn),5條超邊的超圖。

圖2 超圖的表示(曲線表示、矩陣表示)

2.2.2超圖的結(jié)構(gòu)特性

在結(jié)構(gòu)上,超圖擁有很多拓?fù)涮匦?節(jié)點(diǎn)度、節(jié)點(diǎn)超度、超邊度、超邊超度、節(jié)點(diǎn)相鄰度等,其中節(jié)點(diǎn)相鄰度包含了較多與超圖結(jié)構(gòu)有關(guān)的信息[17],節(jié)點(diǎn)相鄰度定義如下:在超圖H中,V中任意一個(gè)節(jié)點(diǎn)對(duì)同時(shí)屬于超ei(?ei),則稱節(jié)點(diǎn)對(duì)在H相鄰;對(duì)于節(jié)點(diǎn)對(duì) ,存在超邊集的子集E′,滿足?et∈E′有?et且?e′t∈(E-E′)有?e′t,記δ=|E′|則節(jié)點(diǎn)的相鄰度為δ,記為DA(vj,vk)=δ。如:在圖2的超圖中,DA(v1,v2)=1,DA(v5,v6)=2。

3 基于超圖的情景案例表示

3.1 情景特征要素分析

突發(fā)事件情景涉及領(lǐng)域眾多,而不同領(lǐng)域的知識(shí)結(jié)構(gòu)差異很大,因而很難充分完整地描述出突發(fā)事件情景的所有特征。近年來(lái),很多國(guó)內(nèi)外學(xué)者從不同視角對(duì)突發(fā)事件情景要素信息構(gòu)成進(jìn)行了研究,提出了很多通用描述框架[18-20],它們雖然在情景要素信息在數(shù)量、粒度等方面存在差異,但總體上包括:情景概況信息和構(gòu)成要素信息(包括:致災(zāi)要素、承災(zāi)要素、環(huán)境要素等),其中構(gòu)成要素信息是情景劃分的關(guān)鍵,本文綜合上述觀點(diǎn),基于知識(shí)表示的簡(jiǎn)潔有效原則,將情景構(gòu)成要素劃分為情景事件、承災(zāi)體兩部分(環(huán)境作為背景要素放入情景概況中),情景事件、承災(zāi)體要素間的相互作用是推動(dòng)事件發(fā)展演化的關(guān)鍵[19]。

3.1.1情景事件

情景事件是指某一突發(fā)事件發(fā)生后作用在承災(zāi)體上表現(xiàn)出來(lái)的基本事件,基本事件是情景要素的主體,基本事件是推動(dòng)事件情景演化的基礎(chǔ),突發(fā)事件類別眾多,根據(jù)《突發(fā)事件應(yīng)對(duì)法》中對(duì)突發(fā)公共事件的分類,將事件分為四大類,即自然災(zāi)害類、事故災(zāi)害類、公共衛(wèi)生類、社會(huì)安全類,每個(gè)類型又可繼續(xù)細(xì)分,呈現(xiàn)多層次樹(shù)狀結(jié)構(gòu)。

3.1.2承災(zāi)體要素

承災(zāi)體是直接受到事件影響而造成損害的對(duì)象[18],也是應(yīng)急響應(yīng)行動(dòng)作用的對(duì)象,承災(zāi)體破壞導(dǎo)致其蘊(yùn)含的災(zāi)害要素釋放,是產(chǎn)生次生、衍生事件的必要條件,是事件發(fā)生連鎖反應(yīng)形成事件鏈的關(guān)鍵要素[7]。根據(jù)承災(zāi)體類屬的劃分,承災(zāi)體也呈現(xiàn)多層次樹(shù)狀結(jié)構(gòu)。

根據(jù)上述分析,情景的結(jié)構(gòu)可以從情景概況、情景事件、承災(zāi)體三方面對(duì)其進(jìn)行描述,可將其形式化表示為公式(1)。

Si={Ei,Vi}

(1)

其中Si為某個(gè)情景,Ei表示該情景所屬的基本事件,一般一個(gè)具體情景只有一個(gè)基本事件類型,即Ei={ei};Vi表示該情景中承災(zāi)體要素集合,由一個(gè)或多個(gè)承災(zāi)體要素構(gòu)成,即Vi={vi1,vi2,…}。

3.2 基于超圖的情景的表示

突發(fā)事件發(fā)展演化是情景事件與承災(zāi)體相互作用的結(jié)果,其過(guò)程為:初始事件發(fā)生,并使其影響范圍內(nèi)的承災(zāi)體受損,其中有些承災(zāi)體受損程度突破閾值發(fā)生災(zāi)變引發(fā)新的事件,從而導(dǎo)致事件發(fā)展演化形成情景鏈。突發(fā)事件情景演化具有如下特征:一個(gè)事件會(huì)同時(shí)作用于多個(gè)承災(zāi)體;同一承災(zāi)體可以被多個(gè)事件影響;受損承災(zāi)體是事件之間次生、衍生關(guān)系的依托。

超圖模型不僅能很好地描述情景鏈的上述特征,而且還可以實(shí)現(xiàn)情景鏈的可視化,本文構(gòu)建的情景鏈超圖模型中,以情景事件作為超邊,以承災(zāi)體為節(jié)點(diǎn),每條超邊中都包含多個(gè)不同的節(jié)點(diǎn),該模型反映了情景之間演化關(guān)系以及演化過(guò)程中情景事件與承災(zāi)體之間的相互作用關(guān)系。

依據(jù)超圖定義,結(jié)合公式(1),情景鏈超圖可表示為:

SH={E,V}

(2)

其中SH是超圖表示的情景鏈,由多個(gè)情景構(gòu)成,即SH={S1,S2,…},E是超圖的邊,在這里表示情景鏈中所有的基本事件的集合,即E=E1∪E2∪…={e1,e2,…};V是超圖的節(jié)點(diǎn),在這里表示情景鏈中所有承災(zāi)體要素集合,即V=V1∩V2∩…={v1,v2,…}(為表述方便,對(duì)承災(zāi)體按順序重新編號(hào))。

圖3描述了基于超圖的情景演化過(guò)程,即情景鏈的形成過(guò)程。

圖3 情景鏈超圖模型

4 基于超圖的突發(fā)事件情景案例檢索

案例檢索是實(shí)現(xiàn)案例推理的關(guān)鍵環(huán)節(jié),本文根據(jù)突發(fā)事件情景案例庫(kù)結(jié)構(gòu)特點(diǎn)設(shè)計(jì)了檢索流程,提出了基于超圖的情景鏈相似度、情景特征相似度的計(jì)算方法。

4.1 案例檢索策略

隨著案例庫(kù)中的案例數(shù)量越來(lái)越多,案例的檢索效率和準(zhǔn)確率將是一個(gè)突出問(wèn)題。目前廣泛采用的案例檢索策略有:最近相鄰法、歸納索引法、知識(shí)引導(dǎo)法、模板檢索法等,檢索策略的選擇問(wèn)題和案例組織方式和結(jié)構(gòu)特征有關(guān),本文為了提高檢索效率,情景案例庫(kù)按突發(fā)事件類型和承災(zāi)體類型(根據(jù)類屬關(guān)系從粗到細(xì)形成層次樹(shù))進(jìn)行組織并建立了索引,這樣通過(guò)事件和承災(zāi)體的不同組合將情景案例庫(kù)劃分為若干情景案例類(具有相同事件類型和包含相同承災(zāi)體),在此基礎(chǔ)上,提出兩階段檢索策略:第一階段為情景鏈檢索,篩選出相似度高的情景鏈;第二階段為情景檢索,在上一階段基礎(chǔ)上,篩選出最相近的情景案例實(shí)例,提取備選方案,具體檢索過(guò)程如圖4所示。

第一階段按當(dāng)前情景概況特征檢索到相應(yīng)情景類(具有相同事件類型和承災(zāi)體類型),提取該類中所有情景所在的情景鏈,生成情景鏈超圖模型,基于情景鏈超圖模型進(jìn)行情景鏈匹配,選擇滿足閾值的相似情景鏈。第二階段按情景特征檢索,依據(jù)情景屬性特征值,從備選情景鏈中進(jìn)行匹配,選擇與目標(biāo)情景匹配度較高的情景所在情景鏈。

通過(guò)兩階段檢索,可以找到與當(dāng)前情景相似度更高的案例,不僅是當(dāng)前情景特征相似,而且發(fā)展演化過(guò)程(情景鏈)也相似,從而保證了檢索出的備選案例比以往單個(gè)案例檢索出的案例更為有效,另外,整個(gè)檢索過(guò)程也體現(xiàn)了檢索范圍粒度逐級(jí)縮小,逐步求精,在保證檢索與匹配質(zhì)量條件下提高了檢索效率。

4.2 相似度計(jì)算

案例檢索是在案例間相似度匹配比較的基礎(chǔ)上進(jìn)行的,其關(guān)鍵是科學(xué)的相似度匹配計(jì)算方法。本文兩階段案例檢索中分別應(yīng)用了基于超圖的情景鏈相似度和情景特征相似度計(jì)算。

4.2.1情景鏈相似度計(jì)算

第一階段情景鏈檢索,要對(duì)目標(biāo)情景的情景鏈和源情景(選定的情景類中的所有情景)的情景鏈進(jìn)行比較,因?yàn)槟繕?biāo)情景仍在發(fā)展變化中,當(dāng)前目標(biāo)情景是該情景鏈的最后一個(gè)情景,所以源情景鏈也應(yīng)該截取由初始情景到當(dāng)前源情景這部分子鏈進(jìn)行比較,由于情景鏈基于超圖表示,所以情景鏈相似度的比較實(shí)際上是超圖相似度的比較,根據(jù)情景鏈超圖的特點(diǎn),超圖相似度應(yīng)該包括兩部分:要素相似度和結(jié)構(gòu)相似度。

①超圖相似度計(jì)算公式

SimL(SH,SH*)=α·Simb(SH,SH*)+(1-α)·Simc(SH,SH*)

(3)

其中,SimL(SH,SH*)表示超圖相似度,Simb(SH,SH*)表示超圖要素(即超邊和節(jié)點(diǎn))的相似度,Simc(SH,SH*)表示超圖結(jié)構(gòu)相似度,α、1-α為對(duì)應(yīng)權(quán)重。

②超圖要素相似度計(jì)算公式

(4)

其中,SH.E表示源情景鏈超圖的超邊集合,SH*.E表示目標(biāo)情景鏈超圖的超邊集合,SH.V表示源情景鏈超圖的節(jié)點(diǎn)集合,SH*.V表示目標(biāo)情景鏈超圖的節(jié)點(diǎn)集合,β、1-β為權(quán)重。

③超圖結(jié)構(gòu)相似度計(jì)算公式

超圖結(jié)構(gòu)的相似度是超圖超邊和節(jié)點(diǎn)關(guān)系的相似度。在兩個(gè)不同超圖中,它們對(duì)應(yīng)的超邊集合和節(jié)點(diǎn)集合可能都相同,即超圖要素相同,但是超邊和節(jié)點(diǎn)之間的關(guān)系可能不同,即兩者的結(jié)構(gòu)不同,比如:在兩個(gè)不同的“火災(zāi)→有毒氣體泄漏”情景鏈中,其事件超邊相似(都是“火災(zāi)”和“有毒氣體泄漏”),其承災(zāi)體也相似(都有“人”“建筑物”和“管道”),但是“人”是處在火災(zāi)情景中還是處于有毒氣體泄漏中,其應(yīng)急處置策略是完全不同的,可見(jiàn)對(duì)于情景鏈,僅僅判斷要素相似度是不夠的,其結(jié)構(gòu)相似度的匹配更加重要。

根據(jù)前面的超圖定義,節(jié)點(diǎn)相鄰度體現(xiàn)了超圖重要的結(jié)構(gòu)信息,它不但體現(xiàn)了節(jié)點(diǎn)之間的關(guān)系,而且體現(xiàn)了超邊和節(jié)點(diǎn)的關(guān)系,可以利用其來(lái)判定兩個(gè)超圖是否同構(gòu),因此,本文基于節(jié)點(diǎn)相鄰度建立超圖結(jié)構(gòu)相似度計(jì)算方法如公式(5)所示。

(5)

4.2.2情景特征相似度計(jì)算

第二階段情景檢索,主要是上面一個(gè)階段檢索結(jié)果基礎(chǔ)上進(jìn)一步篩選滿足條件的情景,本階段情景檢索是基于情景要素特征屬性來(lái)計(jì)算情景的相似度。

a.情景特征相似度計(jì)算公式

情景特征相似度等于情景要素(情景事件、承災(zāi)體)的特征屬性相似度的加權(quán)和。計(jì)算公式如下:

SimT(Si,S*)=ωESimd(Ei,E*)+ωVSimd(Vi,V*)

(6)

其中Simd()為要素特征屬性相似度計(jì)算公式,具體公式見(jiàn)式(7)。

b.要素特征相似度

要素特征相似度是指目標(biāo)情景和源情景中情景要素共有屬性相似度之和,計(jì)算公式如式(7)。

(7)

其中WX∩Y表示集合X和Y交集的權(quán)重之和,λi表示集合X和Y交集中的第i個(gè)屬性的權(quán)重,l表示集合X和Y交集中屬性的個(gè)數(shù)。sim(X.ai,Y.ai)表示要素屬性相似度,具體計(jì)算公式如下:

c.屬性相似度計(jì)算公式

情景要素特征屬性多種多樣,數(shù)據(jù)類型不盡相同,不同的數(shù)據(jù)類型相似度的計(jì)算方法也有差異。情景要素征屬性特征值涉及的數(shù)據(jù)類型主要包括:數(shù)值型、符號(hào)型、集合型、模糊型等四種,下面給出這四種類型的特征屬性相似度計(jì)算方法:

①當(dāng)特征屬性的值為數(shù)值型時(shí),屬性的相似度可以通過(guò)計(jì)算兩者的距離來(lái)衡量,本文采用最常用的歐氏距離算法,其計(jì)算公式如下:

(8)

其中β和α分別表示第i個(gè)確定數(shù)屬性的最大值和最小值。

②當(dāng)特征屬性的值為符號(hào)型時(shí),符號(hào)屬性值給出了該屬性所有可能的取值,不同取值間一般是互斥的,例如:火災(zāi)事件中,檢索承災(zāi)體“建筑物”的特征屬性“是否高層建筑”屬于符號(hào)型,其取值:“是”或“否”。符號(hào)型屬性相似度計(jì)算公式如式下:

(9)

③當(dāng)特征屬性是集合類型時(shí),

(10)

④當(dāng)特征屬性值是模糊型時(shí),模糊型又可分為模糊區(qū)間型和模糊概念型,模糊區(qū)間型采用模糊數(shù)學(xué)中隸屬度函數(shù)來(lái)計(jì)算相似度,計(jì)算方法如下:模糊概念型先進(jìn)行模糊處理,轉(zhuǎn)化為模糊區(qū)間型,再進(jìn)行計(jì)算。

(11)

其中

(12)

5 結(jié) 語(yǔ)

突發(fā)事件是一個(gè)動(dòng)態(tài)演化的系統(tǒng),對(duì)其發(fā)展、演化情景特征的準(zhǔn)確把握是實(shí)現(xiàn)有效應(yīng)對(duì)的關(guān)鍵,以往突發(fā)事件案例表示和檢索方法大都將情景案例看成一個(gè)孤立的個(gè)體,對(duì)情景演化特征描述不足。本文基于超圖理論構(gòu)建了情景案例表示模型,并在此基礎(chǔ)上提出案例檢索的策略和方法,具有一定創(chuàng)新性體現(xiàn)在:

a.提出以基本事件為超邊,承災(zāi)體為節(jié)點(diǎn)的情景鏈超圖模型,該模型不但描述了突發(fā)事件情景演化過(guò)程,而且也體現(xiàn)了突發(fā)事件情景關(guān)鍵要素間相互作用關(guān)系。

b.基于情景鏈超圖模型提出兩級(jí)檢索策略:情景鏈檢索和情景特征檢索,根據(jù)兩級(jí)級(jí)檢索策略,提出情景鏈相似度和情景相似度計(jì)算方法,該檢索過(guò)程體現(xiàn)了粒度從粗到細(xì)的變化,可以保證檢索的質(zhì)量和效率。

本文研究在一定程度上豐富了突發(fā)事件情景案例表示與推理的理論與方法,也拓展了超圖理論的應(yīng)用領(lǐng)域和場(chǎng)景。