裝備維修流程設(shè)計(jì)需求聚類分析

岳強(qiáng)斌，歐 淵，石 倩

(1.軍械工程學(xué)院，石家莊 050003;2.中國(guó)國(guó)防科技信息中心，北京 100142)

裝備維修流程是裝備維修操作的具體實(shí)施程序，是裝備維修任務(wù)能否完成的關(guān)鍵。對(duì)裝備維修流程進(jìn)行重新設(shè)計(jì)，能更加快速和有效地提高裝備維修流程效率，快速完成裝備維修任務(wù)，恢復(fù)裝備戰(zhàn)斗力。

裝備維修流程設(shè)計(jì)需求是裝備維修流程設(shè)計(jì)的重要依據(jù)和根本基礎(chǔ)。由于獲取的裝備維修流程設(shè)計(jì)需求數(shù)量較大，因此需要將裝備維修流程設(shè)計(jì)需求進(jìn)行分類，將針對(duì)同一問題的裝備維修流程設(shè)計(jì)需求歸到一起，并且區(qū)分其層次關(guān)系，以便于后續(xù)的流程設(shè)計(jì)工作。

1 裝備維修流程設(shè)計(jì)需求聚類分析過程

裝備維修流程設(shè)計(jì)需求是針對(duì)不同的方面進(jìn)行闡述的，可能涉及到層次上的區(qū)別，所以，本文選擇采用凝聚層次聚類法(hierarchical agglomerative clustering，HAC)來進(jìn)行聚類分析。HAC又稱為合并型層次聚類，是一種自底向上的方法，將每一個(gè)對(duì)象看作一個(gè)聚類，把它們逐漸合并成越來越大的聚類［1］。在每一層中，根據(jù)一些規(guī)則將距離最近的2個(gè)聚類合并，直到滿足預(yù)先設(shè)定的終止條件。例如，所有的對(duì)象最終合為了1類，或者聚類的數(shù)目達(dá)到了預(yù)定值，或者最近的2個(gè)類之間的距離達(dá)到預(yù)定的閾值［2－3］。根據(jù)HAC的原理，基于HAC的裝備維修流程設(shè)計(jì)需求聚類分析過程如圖1所示，包括4個(gè)關(guān)鍵步驟:分詞、提取特征詞、相似度計(jì)算和聚類處理［4］。

圖1 基于HAC的裝備維修流程設(shè)計(jì)需求聚類分析過程

1.1 分詞

裝備維修流程設(shè)計(jì)需求是以短句的形式存在。裝備維修流程設(shè)計(jì)需求的基本要求是主題唯一，對(duì)象明確，語言簡(jiǎn)明、具體等。但是對(duì)于后續(xù)的相似度計(jì)算，需要計(jì)算裝備維修流程設(shè)計(jì)需求之間的相似度，而句子之間的相似度是以詞語之間的相似度為基礎(chǔ)的，所以，首先要將其切分為詞語，對(duì)裝備維修流程設(shè)計(jì)需求進(jìn)行分詞［5－6］。

由于裝備維修流程設(shè)計(jì)需求的結(jié)構(gòu)比較明了和清晰，分詞就變得相對(duì)比較容易，因此，本文采用基于規(guī)則分詞法中相對(duì)精確的逆向最大匹配法(reverse maximum matching method，RMM)來進(jìn)行分詞，提出了基于RMM裝備維修流程設(shè)計(jì)需求的分詞方法［7］。

首先，定義進(jìn)程P，其中x為待分詞的裝備維修流程設(shè)計(jì)需求所包含的漢字個(gè)數(shù)，如圖2所示。由于RMM法的核心思想是將待分詞的裝備維修流程設(shè)計(jì)需求與裝備維修流程設(shè)計(jì)需求詞典庫(kù)中的詞條進(jìn)行比對(duì)，因此，首先定義預(yù)處理分詞進(jìn)程，引入一個(gè)計(jì)數(shù)參數(shù)k，在將k置零后將待分的裝備維修流程設(shè)計(jì)需求與詞典庫(kù)進(jìn)行比對(duì)。若能匹配成功，則直接形成分詞結(jié)果;當(dāng)匹配不成功時(shí)去掉最左邊的一位，此時(shí)計(jì)數(shù)參數(shù)k=k+1，取后(x－k)位的裝備維修流程設(shè)計(jì)需求再進(jìn)行匹配處理。若能成功匹配，則判斷k是否為零。k為零，表示待分詞的裝備維修流程設(shè)計(jì)需求是一次匹配成功;若k不為零，則要將去掉的最左邊的k位重新與裝備維修流程設(shè)計(jì)需求詞典庫(kù)進(jìn)行比對(duì)，分詞成功以后，輸出分詞結(jié)果。

在定義了預(yù)定義的分詞進(jìn)程P以后，采用RMM算法進(jìn)行處理，算法流程如圖3所示。假設(shè)裝備維修流程設(shè)計(jì)需求詞典庫(kù)中最長(zhǎng)詞條所包含的漢字個(gè)數(shù)為a，待分詞的裝備維修流程設(shè)計(jì)需求包含的漢字個(gè)數(shù)為b。

若a≥b，則表示待分詞的裝備維修流程設(shè)計(jì)需求中的漢字個(gè)數(shù)小于詞典庫(kù)中的最長(zhǎng)詞條的漢字?jǐn)?shù)，此時(shí)應(yīng)將整個(gè)裝備維修流程設(shè)計(jì)需求與裝備維修流程設(shè)計(jì)需求詞典庫(kù)進(jìn)行匹配，利用預(yù)定義進(jìn)程P得到分詞的結(jié)果。

若a＜b，則表示待分詞的裝備維修流程設(shè)計(jì)需求中的漢字個(gè)數(shù)大于詞典庫(kù)中的最長(zhǎng)詞條的漢字?jǐn)?shù)，此時(shí)應(yīng)取裝備維修流程設(shè)計(jì)需求的后a個(gè)字進(jìn)行分詞，同樣利用預(yù)定義進(jìn)程P得到后a個(gè)字的分詞結(jié)果。再取裝備維修流程設(shè)計(jì)需求剩余的(ba)個(gè)字，此時(shí)，需要比對(duì)(b－a)與詞典庫(kù)中的最長(zhǎng)詞條的漢字?jǐn)?shù)a的大小關(guān)系。當(dāng)(b－a)≤a時(shí)，則可以直接將裝備維修流程設(shè)計(jì)需求剩余的(b－a)個(gè)字與詞典庫(kù)進(jìn)行匹配，進(jìn)行分詞處理。但是當(dāng)(b－a)＞a時(shí)，這樣就與前述的a＜b的情況一樣，因此，返回計(jì)算，重新取剩余裝備維修流程設(shè)計(jì)需求(b－a)個(gè)字的后a個(gè)字進(jìn)行分詞處理。需要注意的是，在a＜b的條件下，最終需要將所得的分詞結(jié)果進(jìn)行合并，得到一個(gè)完整的分詞結(jié)果。

圖2 預(yù)定義的分詞進(jìn)程P

圖3 RMM算法流程

1.2 提取特征詞

對(duì)裝備維修流程設(shè)計(jì)來說，裝備維修流程設(shè)計(jì)需求就是對(duì)流程要達(dá)到水平的一些具體要求。那么，從意義上理解，其語句形式就是要使什么方面達(dá)到什么樣的程度。例如，裝備維修流程設(shè)計(jì)需求“工藝設(shè)計(jì)合理”，經(jīng)過原始的需求轉(zhuǎn)換得到的裝備維修流程設(shè)計(jì)需求的表達(dá)形式本來就是比較簡(jiǎn)練，根據(jù)裝備維修流程設(shè)計(jì)需求的結(jié)構(gòu)特點(diǎn)，可以將裝備維修流程設(shè)計(jì)需求的結(jié)構(gòu)分為3部分:關(guān)鍵詞、屬性詞和程度詞。關(guān)鍵詞是裝備維修流程設(shè)計(jì)需求所描述的對(duì)象，是裝備維修流程設(shè)計(jì)需求的中心詞;屬性詞是裝備維修流程設(shè)計(jì)需求所描述對(duì)象的某一具體屬性;程度詞是所述裝備維修流程設(shè)計(jì)需求所要達(dá)到的目標(biāo)。

根據(jù)裝備維修流程設(shè)計(jì)需求的3部分結(jié)構(gòu)，裝備維修流程設(shè)計(jì)需求特征值提取就是區(qū)分關(guān)鍵詞、屬性詞和核心詞，它們是裝備維修流程設(shè)計(jì)需求的主要內(nèi)容，也是進(jìn)行相似度計(jì)算時(shí)的重要指標(biāo)。雖然裝備維修流程設(shè)計(jì)需求的表述已經(jīng)比較扼要，但分詞進(jìn)行完成后，還會(huì)存在一些與關(guān)鍵詞、屬性詞和核心詞無關(guān)的助詞和副詞等，因此在進(jìn)行特征值提取時(shí)，要將這些與裝備維修流程設(shè)計(jì)需求主要內(nèi)容意義表達(dá)無關(guān)的詞去掉。

1.3 相似度計(jì)算

裝備維修流程設(shè)計(jì)需求包括關(guān)鍵詞、屬性詞和程度詞3部分結(jié)構(gòu)，因此裝備維修流程設(shè)計(jì)需求的相似度計(jì)算核心就是這3個(gè)詞語之間的相似度計(jì)算。根據(jù)裝備維修流程設(shè)計(jì)需求詞語相似度計(jì)算的特點(diǎn)，本文提出了基于知網(wǎng)(Hownet)的裝備維修流程設(shè)計(jì)需求語義相似度計(jì)算方法［8］。

裝備維修流程設(shè)計(jì)需求包含3部分詞語，本文所計(jì)算的裝備維修流程設(shè)計(jì)需求詞語相似度是指同類的詞語的相似度，如關(guān)鍵詞與關(guān)鍵詞的相似度，屬性詞與屬性詞的相似度，而程度詞是一些指標(biāo)和目標(biāo)方面的描述，可能是一些具體的數(shù)字，也可能是一些程度上的定性描述，所以計(jì)算它的相似度對(duì)整個(gè)裝備維修流程設(shè)計(jì)需求的相似度意義不大。因此，基于知網(wǎng)的裝備維修流程設(shè)計(jì)需求語義相似度計(jì)算方法計(jì)算的是關(guān)鍵詞和關(guān)鍵詞、屬性詞和屬性詞的相似度。分別計(jì)算出其相似度后，再對(duì)二者進(jìn)行加權(quán)處理，得到整個(gè)裝備維修流程設(shè)計(jì)需求的相似度。

1.3.1 詞語相似度

假設(shè)有詞語 W1和W2。W1的義項(xiàng)有 n個(gè):F11，F(xiàn)12，…，F(xiàn)1n，用 F1i表示，i=1，2，…，n。W2的義項(xiàng)有 m 個(gè):F21，F(xiàn)22，…，F(xiàn)2m，用 F2j表示，j=1，2，…，m。

定義詞語W1和W2的相似度為

其含義是:2個(gè)詞語 W1和 W2的相似度SimW(W1，W2)等于二者各義項(xiàng)之間相似度SimF(F1i，F(xiàn)2j)的最大值。

由于義項(xiàng)是用多個(gè)義原來描述的，所以，義原的相似度計(jì)算是目前需要考慮的問題。定義2個(gè)義原 T1、T2，其相似度為

其中:d是T1、T2在義原層次體系中的路徑長(zhǎng)度，是一個(gè)正整數(shù);α是一個(gè)可調(diào)節(jié)的參數(shù)，其含義是相似度為0.5時(shí)的路徑長(zhǎng)度。

在知網(wǎng)中，將實(shí)詞的語義表達(dá)分為4個(gè)部分:

1)第1獨(dú)立義原描述式。將2個(gè)義項(xiàng)的這一部分的相似度記為SimT1(T1，T2)。

2)其他獨(dú)立義原描述式。語義表達(dá)式中除第1獨(dú)立義原以外的所有其他獨(dú)立義原(或具體詞)，將 2個(gè)義項(xiàng)的這一部分的相似度記為SimT2(T1，T2)。

3)關(guān)系義原描述式。語義表達(dá)式中所有的用關(guān)系義原描述式，將2個(gè)義項(xiàng)的這一部分的相似度記為 SimT3(T1，T2)。

4)符號(hào)義原描述式。語義表達(dá)式中所有的用符號(hào)義原描述式，將2個(gè)義項(xiàng)的這一部分的相似度記為 SimT4(T1，T2)。

在此定義的基礎(chǔ)上，義項(xiàng)F1和F2的語義相似度為

其中βi(1≤i≤4)是各義原的調(diào)節(jié)參數(shù)，且β1+β2+ β3+β4=1，β1≥β2≥β3≥β4，表示從第 1 獨(dú)立義原到符號(hào)義原的相似度對(duì)整個(gè)義項(xiàng)的相似度依次遞減。第1獨(dú)立義原對(duì)義項(xiàng)相似度影響最大，因此β1比較大，一般在0.5以上。

1.3.2 裝備維修流程設(shè)計(jì)需求相似度

對(duì)于裝備維修流程設(shè)計(jì)需求，分別計(jì)算出對(duì)應(yīng)的關(guān)鍵詞和關(guān)鍵詞、屬性詞和屬性詞之間的相似度后，就可以計(jì)算整個(gè)裝備維修流程設(shè)計(jì)需求的相似度。

假設(shè)2個(gè)裝備維修流程設(shè)計(jì)需求為V1和V2，V1的關(guān)鍵詞和屬性為W11、W12，V2的關(guān)鍵詞和屬性為W21、W22，那么裝備維修流程設(shè)計(jì)需求V1和V2的相似度為

其中γ是關(guān)鍵詞和屬性詞的在計(jì)算相似度時(shí)的權(quán)重，根據(jù)實(shí)際情況確定。

1.4 聚類處理

聚類處理［9］是將裝備維修流程設(shè)計(jì)需求歸類的一個(gè)過程。首先對(duì)裝備維修流程設(shè)計(jì)需求聚類處理做如下假設(shè):

1)裝備維修流程設(shè)計(jì)需求集V={V1，V2，…，Vi，…，Vn}。

2)將V中的每個(gè)裝備維修流程設(shè)計(jì)需求Vi都看作是一個(gè)包括單個(gè)裝備維修流程設(shè)計(jì)需求的類Ci={Vi}，因此，這些類構(gòu)成了V的一個(gè)聚類C={C1，C2，…，Ci，…，Cn}。

3)設(shè)t為相似度閾值，當(dāng)2個(gè)裝備維修流程設(shè)計(jì)需求相似度大于等于t時(shí)，才符合聚類基本條件，才可能歸為一類;當(dāng)2個(gè)裝備維修流程設(shè)計(jì)需求相似度小于t時(shí)，則認(rèn)為二者屬于同一類。

聚類處理算法處理過程:

1)首先，計(jì)算其他聚類Cj(j≠i)分別與Ci的相似度Sim(Vi，Vj)，計(jì)算出的相似度有(n－1)個(gè)。

2)判斷Sim(Ci，Cj)是否達(dá)到相似度閾值要求。若Sim(Ci，Cj)≥t，則將其列為可能相似的對(duì)象;若Sim(Ci，Cj)＜ t，則二者肯定不相似。

3)取滿足相似度閾值要求的Sim(Ci，Cj)，取它們中的最大值即Max Sim(Ci，Cj)，將二者聚為一類 CiCj。

4)將新的CiCj歸類繼續(xù)與其他類進(jìn)行聚類。有CiCj與 Ck(Ck為其他任一類)，則分別計(jì)算Sim(Ci，Ck)和 Sim(Cj，Ck)，取二者均值 Average=［Sim(Ci，Ck)+Sim(Cj，Ck)］/2。若 Average≥t，則認(rèn)為Ck與 CiCj相似，將其聚為新類 CiCjCk;若Average＜t，則認(rèn)為Ck與CiCj不相似，不進(jìn)行聚類。

5)重復(fù)上述步驟，直至C中所有對(duì)象均不符合以上聚類條件，則聚類完成。

2 結(jié)束語

本文提出裝備維修流程設(shè)計(jì)需求聚類分析方法，以HAC為基本原理，通過分詞、提取特征詞、相似度計(jì)算和聚類處理4個(gè)關(guān)鍵步驟，實(shí)現(xiàn)了裝備維修流程設(shè)計(jì)需求的聚類分析，進(jìn)行了層次關(guān)系區(qū)分，為后續(xù)裝備維修流程設(shè)計(jì)打下堅(jiān)實(shí)基礎(chǔ)。

［1］孫衛(wèi)，馬德云，歐陽為民，等.基于聚類的體制數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)［J］.計(jì)算機(jī)與現(xiàn)代化，2008(9):58－64.

［2］劉文軍，游興中.一種改進(jìn)的凝聚層次聚類法［J］.吉首大學(xué)學(xué)報(bào):自然科學(xué)版，2011，32(4):11－14.

［3］羅可，洪亮亮，童小嬌.一種有效的分類型數(shù)據(jù)聚類方法［J］.控制與決策，2011，26(10):1542 －1544.

［4］李玲玲.關(guān)于凝聚層次聚類時(shí)間復(fù)雜度的研究［J］.宿州學(xué)院學(xué)報(bào)，2011，26(2):21 －22.

［5］羅桂瓊，費(fèi)洪曉，戴弋.基于反序詞典的中文分詞技術(shù)研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2008，18(1):80 －83.

［6］胡錫衡.正向最大匹配法在中文分詞技術(shù)中的應(yīng)用［J］.鞍山師范學(xué)院學(xué)報(bào)，2008，10(2):42 －45.

［7］徐殿軍，崔寶華.PHP+MYSQL環(huán)境下的中文分詞技術(shù)研究［J］.遼寧師范大學(xué)學(xué)報(bào):自然科學(xué)版，2008，31(1):57－59.

［8］金博，史彥軍，滕弘飛.基于語義理解的文本相似度算法［J］.大連理工大學(xué)學(xué)報(bào):自然科學(xué)版，2005，45(2):291－297.

［9］潘有能.XML文檔自動(dòng)聚類研究［J］.情報(bào)學(xué)報(bào)，2006，25(2):215－220.

［10］王偉.文本自動(dòng)聚類技術(shù)研究［J］.情報(bào)雜志，2009(2):94－97.