基于LCS的應(yīng)急決策文本相似性比對(duì)分析模型*

徐 可，蓋文妹，鄧云峰

(1.中國(guó)地質(zhì)大學(xué)(北京) 工程技術(shù)學(xué)院，北京 100083；2. 中共中央黨校(國(guó)家行政學(xué)院)，北京 100089)

0 引言

近年來，各種突發(fā)事件頻繁發(fā)生，給人類社會(huì)造成了嚴(yán)重的傷亡、損失和惡劣的影響[1]。作為應(yīng)急管理的“大腦”，應(yīng)急決策是應(yīng)急管理過程至關(guān)重要的一環(huán)。同時(shí)，這種決策大多發(fā)生在各級(jí)指揮部的小范圍內(nèi)，在極少數(shù)情況下就由指揮部的核心成員甚至就是最高首長(zhǎng)臨機(jī)決斷決策[2]，這些決策往往通過決策文本的各種形式下發(fā)，通過對(duì)決策主體所制定決策文本的研究分析，就能較好地把握決策主體對(duì)相關(guān)形勢(shì)的判斷、態(tài)度以及接下來工作方向的指導(dǎo)和偏好。

對(duì)于危機(jī)情境下的高層決策文本分析，國(guó)內(nèi)外對(duì)此的研究不多。國(guó)內(nèi)外的研究主要集中在制度文本分析的方法與理論框架，如Yamashiro, Daniel K.M.分析了在國(guó)家危機(jī)時(shí)期宗教對(duì)美國(guó)總統(tǒng)外交政策決策的影響[3]；美國(guó)國(guó)家總評(píng)估辦公室 (The U.S.A General Accountability Office,GAO) 提出的內(nèi)容分析法這種定性分析方法[4]，以及國(guó)內(nèi)很多學(xué)者提出的制度文本分析框架[5-6]。總體來講，有關(guān)制度文本分析的研究已有大量文獻(xiàn)，但針對(duì)危機(jī)情境下高層決策文本分析的研究文獻(xiàn)相對(duì)較少，已有的文獻(xiàn)大部分是關(guān)于重大事件決策的影響因素的研究[7-8]，也有文獻(xiàn)對(duì)突發(fā)事件中的相似度計(jì)算進(jìn)行了相關(guān)論述，但主要是集中在突發(fā)事件的匹配度，通過將突發(fā)事件的文本視為各種屬性的集合，并通過基于語(yǔ)義詞典以及句子依存結(jié)構(gòu)計(jì)算突發(fā)事件框架的相似度[1]。這種框架更適合于標(biāo)準(zhǔn)化的表述文本形式，對(duì)于高層應(yīng)急決策文本中簡(jiǎn)略的口語(yǔ)化表達(dá)過于復(fù)雜，同時(shí)框架中的“事件基本屬性”、“承災(zāi)載體”、“應(yīng)急管理”、“次生衍生災(zāi)害”4個(gè)子集合也不太適用于高層應(yīng)急決策文本。關(guān)于文本相似度方面的研究，主要是將非結(jié)構(gòu)化的文本形式轉(zhuǎn)化為結(jié)構(gòu)化形式。如Salton等提出的基于統(tǒng)計(jì)學(xué)方法的向量空間模型(VSM)[9]，雖然VSM結(jié)構(gòu)簡(jiǎn)單，但它是基于文本中的特征詞頻數(shù)統(tǒng)計(jì)計(jì)算的相似度[10]，并沒有考慮特征詞的位置關(guān)系，對(duì)于高層應(yīng)急決策文本的相似度分析來說過于片面。同時(shí)，也有學(xué)者基于自然語(yǔ)言處理進(jìn)行了相似度方面的研究，如Hofmann,Thomas引入潛在類變量來提高相似度計(jì)算的精度[11]；Emesto等通過對(duì)指定本體概念派生出的類使用聚類的方法進(jìn)行語(yǔ)義消歧[12]。

本文針對(duì)危機(jī)情景下高層決策文本特征分析中的相似度計(jì)算問題，通過歧義消除、同近義合并、編碼的方法將非結(jié)構(gòu)化的決策文本轉(zhuǎn)化為結(jié)構(gòu)化的字符串形式，同時(shí)根據(jù)決策文本的特點(diǎn)細(xì)化其主題詞分級(jí)，并運(yùn)用序列比對(duì)中最長(zhǎng)公共子序列模型(LCS)的理論及方法，綜合考慮字符匹配度以及字符順序來計(jì)算決策序列對(duì)的相似度，將決策樣本的聚類分析轉(zhuǎn)化為求解決策序列之間的相似性問題，建立了高層應(yīng)急決策文本相似性比對(duì)分析模型，定量化序列之間的差異性；用Needleman-Wunsch算法求解該模型，并通過實(shí)例檢驗(yàn)了模型的有效性和可行性，研究結(jié)果可為高層應(yīng)急決策文本分析研究提供參考和借鑒。

1 問題描訴與模型建立

1.1 問題提出

應(yīng)急決策文本，不同于一般的政策工具，其可能是1項(xiàng)通知、1則公告或者幾行命令。它是承載了決策主體在不確定條件下對(duì)各種意外事態(tài)進(jìn)行研判并采取應(yīng)急處置措施的文本。為了應(yīng)對(duì)突發(fā)事件，決策主體根據(jù)經(jīng)驗(yàn)、知識(shí)、能力等提出自己認(rèn)為正確的“任務(wù)”或“行動(dòng)”，由于突發(fā)事件的復(fù)雜性，這些應(yīng)對(duì)措施往往不是唯一的，所以這些決策文本的內(nèi)容往往是多主題的。當(dāng)我們對(duì)這些決策文本進(jìn)行主題詞提取、整合，就會(huì)得到該決策文本所特有的決策序列，如圖1。當(dāng)處于同一危機(jī)情境下，如何對(duì)這些序列進(jìn)行聚類分析進(jìn)而得到?jīng)Q策主體的決策行為特征就是本文研究的問題。

圖1 決策序列示意Fig.1 Schematic diagram of decision-making sequence

1.2 變量及名詞定義

最長(zhǎng)公共子序列模型(LCS)是由Wagner和Fisher在20世紀(jì)70年代提出的一種較為基礎(chǔ)的算法，其主要用途是查找2個(gè)序列之間的最長(zhǎng)公共子序列[1]。這種算法一經(jīng)提出就廣泛應(yīng)用于生物信息學(xué)，對(duì)于發(fā)現(xiàn)核酸和蛋白質(zhì)序列上的功能、結(jié)構(gòu)和進(jìn)化的信息具有非常重要的意義[13]。對(duì)于高層應(yīng)急決策序列對(duì)，可以通過得到序列對(duì)之間的相似性分值來對(duì)樣本進(jìn)行聚類分析，進(jìn)而研究各類之間的區(qū)別及聯(lián)系，由此，序列比對(duì)時(shí)應(yīng)該考慮的內(nèi)容就在于決策內(nèi)容和決策順序。決策內(nèi)容本質(zhì)上是決策主體從應(yīng)對(duì)特定突發(fā)事件的各種措施的大集合中挑選出滿足自身要求、各種任務(wù)部署的小集合，而決策順序則代表了決策主體對(duì)這些任務(wù)部署的優(yōu)先級(jí)的確定。各變量及名詞定義如下。

1)主題詞：用以表達(dá)決策文本主題的詞匯，具有概念化和規(guī)范化的特征。主題詞來源于樣本數(shù)據(jù)，1個(gè)主題詞的來源可能是多個(gè)樣本，比如：“全力加強(qiáng)人員搜救，這是第一位的工作”與“全力以赴開展人員搜救”這2句的主題詞都可以為“人員搜救”。同時(shí)，根據(jù)決策文本的特點(diǎn)，從執(zhí)行層面上大致分為2級(jí)：目標(biāo)和行動(dòng)，并且后者屬于前者，1個(gè)目標(biāo)可以有很多活動(dòng)或者沒有活動(dòng)。

2)編碼號(hào)：連接序列和決策文本的中間元素。既是決策序列的組成部分，又一一對(duì)應(yīng)決策文本中的主題詞。

3)設(shè)序列S記為S=s1s2s3…sx，序列T記為T=t1t2t3…ty。用Si和Tj分別表示序列S的第i個(gè)編碼號(hào)和序列T的第j個(gè)編碼號(hào)。

4)在整個(gè)樣本數(shù)據(jù)中，m是目標(biāo)級(jí)別編碼的數(shù)量，n是各目標(biāo)級(jí)別所含行動(dòng)級(jí)別編碼的數(shù)量。

5)置換得分ωij：Si與Tj的相似性分值。

6)相似性計(jì)分矩陣：基于置換得分得到的打分矩陣。

7)空位罰分Q：序列比對(duì)時(shí)，加入空位時(shí)的相似性罰分。在這里，Q=G×num。G表示1個(gè)空位設(shè)置的罰分；num表示序列比對(duì)中所設(shè)置的空位數(shù)目。

8)相似性分值F：2序列比對(duì)得到的相似性得分。目標(biāo)函數(shù)為：

(1)

1.3 模型建立

基于以上變量及名詞定義，以2序列比對(duì)的相似性分值最大為優(yōu)化目標(biāo)，建立高層應(yīng)急決策文本相似性比對(duì)分析模型，如式(2)～(4)所示，其中，式(3)代表了相似性計(jì)分矩陣的取值，表示不同的替換情況的替換得分。

(2)

(3)

Q=G×num

(4)

2 模型的求解算法

Needleman-Wunsch算法是基于動(dòng)態(tài)規(guī)劃的全局比對(duì)算法[14]。算法的基本思想為：使用迭代的方法逐步計(jì)算出2條序列的相似分值，并將其保存在1個(gè)得分矩陣中，然后根據(jù)這個(gè)得分矩陣，通過動(dòng)態(tài)規(guī)劃的方法回溯尋找最優(yōu)的比對(duì)序列[15]。該算法使用二維表格，表格里的每1個(gè)分值分別有3個(gè)來源：

1)來自上方的單元格，代表將對(duì)應(yīng)行的編碼與空格比對(duì)。

2)來自左側(cè)的單元格，代表將對(duì)應(yīng)列的編碼與空格比對(duì)。

3)來自左上側(cè)的單元格，代表將對(duì)應(yīng)行與列的編碼比對(duì)。

根據(jù)相似性計(jì)分矩陣和空位罰分值，該單元格的值取這3個(gè)來源的最大值。此算法的計(jì)算步驟如下：

1)初始化表格。在進(jìn)行比對(duì)的2條序列前面都加上空格，然后填充第2行和第2列的值。比如：填充第2行意味著使用位于頂部的序列的編碼與空格進(jìn)行比對(duì)，而不是與最左側(cè)序列的編碼，用相似的方法得到第2列的值。同時(shí)將位于左上角的第1個(gè)分值設(shè)為0。

2)填充剩下的表格，根據(jù)相似性積分矩陣和設(shè)置的空位罰分值，取上述3個(gè)來源的最大值。

3)回溯?？梢约僭O(shè)2個(gè)新字符串U和V，將上側(cè)的字符串加入到U中，將左側(cè)的字符串加入到V中。從右下角開始回溯，根據(jù)表格的構(gòu)建過程可知，有3個(gè)方向回溯：“從右到左”、“從下到上”和“從右下到左上”。選取3個(gè)方向中的最大值(當(dāng)最大值不止1個(gè)時(shí)，可以從中任選1個(gè))，同時(shí)遵循以下原則：“從右到左”意味著將左側(cè)字符加入到V中，將空格加入到U中；“從下到上”意味著將上側(cè)字符加入到U中，將空格加入到V中；“從右下到左上”意味著分別將2側(cè)字符加入到U和V中，如圖2所示。

圖2 回溯示意Fig.2 Schematic diagram of backtracking

3 實(shí)例分析

3.1 數(shù)據(jù)來源和初始化

數(shù)據(jù)來源是45位政府高層管理人員參加的1次地震演練情景，共得到45份應(yīng)急決策文本。通過對(duì)這些文本進(jìn)行主題詞提取、整理和編譯，得到全樣本決策編碼，如表1所示。根據(jù)表1，任取2份樣本得到2條決策序列對(duì)S和T，如圖3所示。

3.2 相對(duì)相似性得分

從表1中可知，此實(shí)例共得到了目標(biāo)決策12個(gè)，相應(yīng)的行動(dòng)決策31個(gè)。同時(shí)根據(jù)模型中的公式(3)，當(dāng)總樣本確定后，根據(jù)樣本得到目標(biāo)決策以及相對(duì)應(yīng)的行動(dòng)決策，其對(duì)比序列的替換矩陣也就確定，即序列比對(duì)時(shí)編碼匹配度的影響因素就已確定，影響最終相似性得分的因素只有G(單個(gè)的空位罰分值)和num(插入空位的數(shù)量)。G的設(shè)置是避免為了得到最大相似性得分而插入過多空位。當(dāng)G設(shè)置為0時(shí)，2條序列比對(duì)的相似性得分等價(jià)于擁有長(zhǎng)度相同的“最長(zhǎng)公共子序列”的2序列比對(duì)相似性得分(這里的“最長(zhǎng)公共子序列”不止包括相等，還包括從屬關(guān)系、并列關(guān)系)；當(dāng)G<-m時(shí)，序列比對(duì)時(shí)，當(dāng)2個(gè)編碼不同而位置相同時(shí)，不管其他編碼情況如何，都會(huì)選擇插入2個(gè)空位，進(jìn)而造成序列比對(duì)插入過多的空位；當(dāng)0>G>-m時(shí)，相同序列進(jìn)行對(duì)比的相似性得分隨著單個(gè)空位罰分值的增大而增大，但不同序列相似性得分的大小比較結(jié)果并不會(huì)有所改變。為了降低空位罰分在整個(gè)目標(biāo)函數(shù)中的權(quán)重，可以設(shè)置此次序列比對(duì)的單個(gè)空位罰分值G為-5。經(jīng)計(jì)算得到S和T2條序列比對(duì)的打分矩陣，如表2所示。

表1 地震演練情景下的高層應(yīng)急決策編碼Table 1 Emergency decision-making codes of senior people under earthquake drill scenario

圖3 決策序列Fig. 3 Sequence of decision-making

根據(jù)打分矩陣表可以得出決策序列對(duì)S和T的全局相似性得分為80，同時(shí)其最優(yōu)比對(duì)結(jié)果之一為表3，其中“-”表示插入的空位。

從模型以及算法的計(jì)算過程可以得到，當(dāng)多條序列進(jìn)行比對(duì)時(shí)，假設(shè)其中2條序列很短，僅有幾個(gè)編碼，即使他們的相似性很高，得分也不會(huì)太高，反之，當(dāng)2條序列很長(zhǎng)時(shí)，即使相似性不那么高，他們的得分也可能會(huì)超過前2條序列的得分，如何處理這些情況，或者說如何根據(jù)相似性得分來判定所有序列的聚類情況。在這里，本文引入相對(duì)相似性得分的概念，其計(jì)算公式如下：

(5)

式中：a和b分別為序列S和T的編碼數(shù)量。

根據(jù)式(5)可得S和T的相對(duì)相似性得分為0.476，從數(shù)學(xué)意義上來說，約等于大約有一半的相同編碼相同位置的序列比對(duì)結(jié)果，同時(shí)可以從表3中得到，序列對(duì)相同的編碼為rs,sj,CF,bj,DJ,xf,yj2,sz,ld,zl，大于一半的數(shù)目，如前文所述，序列之間的相似性取決于序列編碼號(hào)以及編碼順序，這一結(jié)果也很好地說明了這一點(diǎn)。

表2 打分矩陣Table 2 Scoring matrix

表3 序列最優(yōu)比對(duì)結(jié)果Table 3 Optimal comparative results of sequences

3.3 與VSM算法的比較

本文選取另1個(gè)樣本與前2個(gè)樣本進(jìn)行兩兩之間的相似度計(jì)算，并與VSM算法計(jì)算得到的結(jié)果進(jìn)行比較，計(jì)算結(jié)果如表4所示。

表4 相似度計(jì)算結(jié)果Table 4 Calculation results of similarity

從表4中結(jié)果可以看到，由于算法中設(shè)置了空位罰分值，2序列之間的相似性比較更為嚴(yán)格，所以本文算法得到的相似性得分普遍低于VSM算法得到的分值，而且由于VSM只是考慮了主題詞匹配度的問題，并沒有考慮主題詞之間的位置差異，所以在序號(hào)2和3中，本文算法得到相比于樣本1，樣本2和樣本3更相似的結(jié)果，而這更能體現(xiàn)決策文本區(qū)別于普通文本的序列性的特點(diǎn)。同時(shí)，由于決策文本中的主題詞都有著相對(duì)獨(dú)立性，VSM模型中各主題詞的權(quán)重設(shè)置就體現(xiàn)不出差異性，而本文算法根據(jù)決策文本特點(diǎn)，將其分為目標(biāo)和行動(dòng)2級(jí)，并根據(jù)兩者之間的關(guān)系設(shè)置不同的比對(duì)得分，提高了精確性。

3.4 樣本數(shù)量敏感性分析

為了研究樣本數(shù)量對(duì)模型結(jié)果的影響，取上述2條序列對(duì)，并依次增加樣本數(shù)量，同時(shí)將G設(shè)置為-2，得到不同樣本數(shù)量情況下同一序列對(duì)的相對(duì)相似性得分，如圖4所示。

圖4 同一序列對(duì)在不同樣本數(shù)量下的相對(duì)相似性得分Fig.4 Relative similarity scores of same sequence pair under different sample amounts

從圖4中可以看出，隨著樣本數(shù)量的增加，序列對(duì)的相對(duì)相似性得分是逐漸增加的，這是由于樣本數(shù)量的增多導(dǎo)致目標(biāo)級(jí)別主題詞的完善，將本沒有關(guān)系的行動(dòng)級(jí)別的主題詞聯(lián)系起來，進(jìn)而增加了相似性得分。同時(shí)也可以看到，在曲線的某些階段以及最后一段，曲線趨于平滑。這是由于樣本數(shù)量的增加并沒有對(duì)同一序列對(duì)的相對(duì)相似性得分造成影響，間接說明了此實(shí)例中的主題詞并不是無限擴(kuò)展的，同時(shí)此實(shí)例中的45份樣本也已經(jīng)滿足實(shí)驗(yàn)要求。

4 結(jié)論

1)為了計(jì)算高層應(yīng)急決策文本的相似度，在對(duì)文本進(jìn)行主題詞提取得到?jīng)Q策序列對(duì)的基礎(chǔ)上，提出高層應(yīng)急決策文本分析模型，并用Needleman-Wunsch算法求解該模型。模型中將主題詞分為“目標(biāo)”和“行動(dòng)”2級(jí)，對(duì)比時(shí)基于樣本數(shù)據(jù)得到替換矩陣，并通過設(shè)置空位罰分來避免過多插入空位，進(jìn)而計(jì)算決策序列對(duì)的相似性得分。

2)對(duì)基于地震情景下得到的45份高層應(yīng)急決策文本的分析證明了模型的可行性，并由此確定了相對(duì)相似性得分的概念，來更好地分析相似性得分在決策序列中的數(shù)學(xué)意義。同時(shí)，通過與文本相似度經(jīng)典的VSM算法的對(duì)比結(jié)果，體現(xiàn)了本文模型在進(jìn)行決策文本相似度計(jì)算中有著更嚴(yán)格、更精確的特點(diǎn)。

3)本文提出模型可為其他情景下的應(yīng)急決策文本的相似度計(jì)算和模型構(gòu)建提供思路和借鑒。同時(shí)，應(yīng)急決策文本的相似度分析是決策行為分析的一個(gè)重要方面，在接下來的研究中，作者將會(huì)考慮決策主體經(jīng)驗(yàn)、學(xué)識(shí)及地理文化差異等更多與決策行為相關(guān)的實(shí)際影響因素，對(duì)決策行為分析進(jìn)行更深入的研究。