基于雙向概念格的坦克駕駛模擬訓(xùn)練關(guān)聯(lián)規(guī)則挖掘

鄧青， 薛青， 高恒, 翟凱

(陸軍裝甲兵學(xué)院 演訓(xùn)中心， 北京 100072)

0 引言

隨著仿真技術(shù)在軍事領(lǐng)域的應(yīng)用，模擬訓(xùn)練已成為世界軍事強(qiáng)國普遍采用的一種重要訓(xùn)練手段[1-2]。通過坦克駕駛模擬器開展模擬訓(xùn)練，可以在保證經(jīng)濟(jì)性的同時(shí)彌補(bǔ)實(shí)裝訓(xùn)練準(zhǔn)備周期長、訓(xùn)練代價(jià)高等缺陷[3-4]，大大提高訓(xùn)練效率。坦克駕駛模擬訓(xùn)練結(jié)束往往會(huì)產(chǎn)生大量數(shù)據(jù)，包括訓(xùn)練操作數(shù)據(jù)、受訓(xùn)人員數(shù)據(jù)、訓(xùn)練科目數(shù)據(jù)、訓(xùn)練結(jié)果數(shù)據(jù)等，這些數(shù)據(jù)具有規(guī)模大、維度高、非線性等特征，相互之間蘊(yùn)含著各種復(fù)雜的關(guān)系[5]。在傳統(tǒng)的坦克駕駛模擬訓(xùn)練結(jié)果分析中，主要是以人為主的統(tǒng)計(jì)分析，易受分析人員專業(yè)知識(shí)、個(gè)人偏好的主觀影響，對(duì)訓(xùn)練的影響因素考慮不全，無法精確指導(dǎo)受訓(xùn)人員進(jìn)行坦克駕駛操作技能訓(xùn)練，也難以從這些復(fù)雜數(shù)據(jù)中發(fā)現(xiàn)有價(jià)值的訓(xùn)練規(guī)則。為解決這一問題，關(guān)聯(lián)規(guī)則挖掘被引入坦克駕駛模擬訓(xùn)練數(shù)據(jù)的分析，以期從中獲取訓(xùn)練指導(dǎo)規(guī)律。

關(guān)于坦克模擬訓(xùn)練的關(guān)聯(lián)規(guī)則挖掘，國外公開的文獻(xiàn)資料不多，對(duì)具體的挖掘過程及算法也沒有涉及。美軍訓(xùn)練與條令司令部提出了戰(zhàn)斗增強(qiáng)分析法，采集模擬訓(xùn)練中的作戰(zhàn)部署、作戰(zhàn)半徑、車輛位置等數(shù)據(jù)，研究坦克分隊(duì)?wèi)?zhàn)場機(jī)動(dòng)的影響因素[6]。美國陸軍研究院開發(fā)了數(shù)據(jù)挖掘工具包，內(nèi)置關(guān)聯(lián)分析套件，成功應(yīng)用于裝甲裝備戰(zhàn)損分析，為裝備試驗(yàn)提供了依據(jù)[7]。美國蘭德公司基于聯(lián)合沖突戰(zhàn)術(shù)模擬訓(xùn)練系統(tǒng)，運(yùn)用定制的關(guān)聯(lián)規(guī)則挖掘算法研究了坦克模擬訓(xùn)練交戰(zhàn)數(shù)據(jù)，輔助裝備使用決策同時(shí)減少昂貴的裝備測試費(fèi)用[8]。國內(nèi)王澤璞等[9]運(yùn)用FP-Growth算法對(duì)火炮模擬訓(xùn)練數(shù)據(jù)進(jìn)行了關(guān)聯(lián)分析，但該算法采用頻繁模式樹的非線性結(jié)構(gòu)，存儲(chǔ)代價(jià)大且搜索效率隨著樹的增長明顯下降。鄧桂龍等[10]、馬建軍[11]、MOHAMMAD等[12]運(yùn)用Apriori算法分別研究了某型空地作戰(zhàn)模擬訓(xùn)練系統(tǒng)和炮兵專業(yè)技術(shù)訓(xùn)練產(chǎn)生的數(shù)據(jù)，得到了一些有趣的規(guī)則，但Apriori算法每次生成頻繁項(xiàng)集都需要掃描數(shù)據(jù)庫，導(dǎo)致計(jì)算開銷大，在大數(shù)據(jù)集上運(yùn)行效率不高。而針對(duì)坦克駕駛模擬訓(xùn)練數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘還很匱乏，以上傳統(tǒng)的方法由于存儲(chǔ)開銷、計(jì)算效率問題，無法直接用于坦克駕駛模擬訓(xùn)練數(shù)據(jù)。

概念格是一種新型知識(shí)表示模型，主要思想是根據(jù)二元關(guān)系提出概念結(jié)構(gòu)[13-14]，體現(xiàn)概念外延和內(nèi)涵的包含關(guān)系。通過搜索概念內(nèi)涵可以快速得到閉項(xiàng)集，且不會(huì)丟失任何信息，因此概念格非常適合產(chǎn)生蘊(yùn)含規(guī)則。運(yùn)用概念格的核心是要搜索構(gòu)造概念節(jié)點(diǎn)，概念格的經(jīng)典Bordat[14]算法通過拆分形式背景建立子概念格，再對(duì)子概念格進(jìn)行合并，整個(gè)拆分、合并操作比較繁瑣，且無法處理多值數(shù)據(jù)。

針對(duì)坦克駕駛模擬訓(xùn)練數(shù)據(jù)的特點(diǎn)[15]，本文提出一種基于雙向概念格的關(guān)聯(lián)規(guī)則(BCLAR)挖掘方法。該方法利用矩陣布爾化將多值數(shù)據(jù)轉(zhuǎn)化為單值背景，然后計(jì)算內(nèi)涵秩和外延秩，分別從格的頂層、底層構(gòu)建概念節(jié)點(diǎn)，最后增加規(guī)則后件固定作為約束條件，過濾不相關(guān)的概念節(jié)點(diǎn)，提取用戶所需的關(guān)聯(lián)規(guī)則。

1 基于BCLAR挖掘方法

定義1假設(shè)K=(O,A,R)，其中，O是對(duì)象集合，A是屬性集合，R是從對(duì)象集映射到屬性集的二元關(guān)系[16]，即R?O×A，則稱K是形式背景。

通過形式背景的定義可以將待挖掘的數(shù)據(jù)對(duì)象進(jìn)行有效表達(dá)，對(duì)于坦克駕駛模擬訓(xùn)練產(chǎn)生的數(shù)據(jù)決策表可視為一種特殊的形式背景。

定義2對(duì)于X?O，Y?A，記X*={y∈A|?x∈X,(x,y)∈R}，Y′={x∈O|?y∈Y,(x,y)∈R}，X*代表對(duì)象集X中所包含的相同屬性集合，Y′代表具有屬性集Y中全部元素的對(duì)象集合。若X*=Y，Y′=X同時(shí)成立，則稱C=(X,Y)是形式背景中的概念[12]。其中：X是概念外延，記X=Ext(C)；Y是概念內(nèi)涵，記Y=Int(C)；K=(O,A,R)中的所有概念集合記作B(K)。

定義3假設(shè)C1=(X1,Y1)、C2=(X2,Y2)是形式背景K=(O,A,R)的兩個(gè)概念，當(dāng)C1≤C2?X1?X2?Y2?Y1，則“≤”稱為概念之間的偏序關(guān)系，C2是C1的父概念，C1是C2的子概念。B(K)通過偏序關(guān)系所構(gòu)成的完備集L(K)=(B(K),≤)稱為概念格[13]。

對(duì)一個(gè)形式背景K=(O,A,R)而言，都存在與其對(duì)應(yīng)的唯一偏序關(guān)系集，不論形式背景中的數(shù)據(jù)對(duì)象、屬性關(guān)系如何排序，它們最終所生成的概念格都具有唯一性，這是概念格的一個(gè)重要性質(zhì)，也是構(gòu)建概念格過程中進(jìn)行雙向搜索的重要依據(jù)。

對(duì)概念格中的概念C1=(X1,Y1)、C2=(X2,Y2)進(jìn)行交、并操作，有

C1∩C2=(X1∩X2,((Y1∪Y2)′)*)，

(1)

C1∪C2=(((X1∪X2)*)′,Y1∩Y2).

(2)

根據(jù)定義2可知，按上述交、并操作后，C1∩C2、C1∪C2依然是概念，保證了概念格的完備性，其中求交運(yùn)算的實(shí)質(zhì)是尋找共同節(jié)點(diǎn)即子節(jié)點(diǎn)，求并運(yùn)算則是產(chǎn)生父節(jié)點(diǎn)。由此可以求出形式背景K=(O,A,R)所對(duì)應(yīng)概念格的上確界、下確界：

(3)

(4)

1.1 多值背景轉(zhuǎn)換

多值背景是指形式背景中對(duì)象集與屬性集之間的關(guān)系不能僅通過0或1表示，在屬性集中含有更多的數(shù)值型量化屬性。傳統(tǒng)的概念格用于對(duì)數(shù)據(jù)表進(jìn)行挖掘時(shí)，所要求的是對(duì)象集與屬性集之間存在二元關(guān)系，即單值背景。而坦克駕駛模擬訓(xùn)練產(chǎn)生的數(shù)據(jù)表屬于多值背景，例如，在運(yùn)用坦克駕駛模擬器進(jìn)行聯(lián)網(wǎng)戰(zhàn)術(shù)訓(xùn)練時(shí)，數(shù)據(jù)庫所保存的坦克機(jī)動(dòng)速度、坦克毀傷程度等數(shù)據(jù)均為多值背景范疇。因此，為了運(yùn)用概念格挖掘其蘊(yùn)含的關(guān)聯(lián)規(guī)則，需要先將原始多值背景轉(zhuǎn)化為單值背景。由于形式背景與矩陣之間可直接轉(zhuǎn)換，本節(jié)采用矩陣布爾化的方法以求取單值背景，具體步驟如下：

輸入：原始多值背景K=(O,A,R)。

輸出：單值背景矩陣P.

步驟1根據(jù)等價(jià)關(guān)系對(duì)K進(jìn)行劃分，使形式背景結(jié)構(gòu)簡化，避免后續(xù)對(duì)相同的對(duì)象重復(fù)搜索概念格節(jié)點(diǎn)。在此基礎(chǔ)上，將K中對(duì)象與屬性分別轉(zhuǎn)化為二維矩陣的行與列，并把二者的映射關(guān)系轉(zhuǎn)化為矩陣的元素值，從而得到K的矩陣形式MK.

步驟2利用文獻(xiàn)[17]中的離散化算法對(duì)MK中的數(shù)據(jù)進(jìn)行離散化處理，得到各屬性的劃分區(qū)間及編碼表示。

步驟3根據(jù)離散化后的各屬性編碼情況進(jìn)行布爾化處理。若編碼結(jié)果為1，則該屬性是冗余的，可不用考慮；若編碼結(jié)果為2，則直接轉(zhuǎn)化為布爾型0、1；若編碼結(jié)果大于2，則將該屬性進(jìn)行擴(kuò)展，新增加的屬性在原屬性命名基礎(chǔ)上增加一個(gè)二維下標(biāo)進(jìn)行標(biāo)識(shí)，屬性擴(kuò)展長度為該屬性離散化的編碼個(gè)數(shù)，相應(yīng)的屬性值根據(jù)擴(kuò)展前的數(shù)據(jù)取布爾值0、1.

步驟4判斷K中的屬性是否處理完畢，若已處理完則轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟3繼續(xù)進(jìn)行布爾化處理。

步驟5輸出最終轉(zhuǎn)化后的單值背景矩陣P.

下面通過一個(gè)例子簡要說明上述轉(zhuǎn)換方法。表1為利用坦克駕駛模擬器進(jìn)行對(duì)抗訓(xùn)練時(shí)所采集的部分?jǐn)?shù)據(jù)，并以多值形式背景表示。

表1 多值形式背景

通過對(duì)數(shù)據(jù)離散化得到編碼如表2所示。

表2 離散化編碼表

對(duì)表1中的數(shù)據(jù)進(jìn)行離散化編碼、矩陣轉(zhuǎn)化，得到M′K：

對(duì)M′K中編碼數(shù)大于2的屬性進(jìn)行布爾化處理，得到單值背景矩陣P：

1.2 雙向概念格構(gòu)建

在將多值背景轉(zhuǎn)化為單值背景并以矩陣表示之后，基于同一形式背景所產(chǎn)生的概念格是唯一的，其結(jié)構(gòu)具有不變性特點(diǎn)，本文采用矩陣秩的方法來定義內(nèi)涵秩和外延秩，然后通過計(jì)算這兩個(gè)秩的值從概念格頂層上確界和底層下確界同時(shí)搜索概念節(jié)點(diǎn)，并結(jié)合支持度閾值對(duì)概念格進(jìn)行約簡，最終實(shí)現(xiàn)概念格的雙向構(gòu)建，以此提高建格效率。

1.2.1 基于內(nèi)涵秩構(gòu)建概念格

定義4設(shè)L(K)=(B(K),≤)為形式背景K=(O,A,R)所對(duì)應(yīng)的概念格，C=(X,Y)是L(K)中的一個(gè)概念，則對(duì)C可分為以下兩類[18]：

1)?a∈Y使得(a′,a)∈R，其中a′為具有屬性a的對(duì)象集合，并且滿足|a′|=|X|，則稱C為第1類概念；

2)?C≤Cp1、C≤Cp2，其中Cp1、Cp2為C的父概念，使得Cp1∩Cp2=C，則稱C為第2類概念。

根據(jù)對(duì)偶原理和概念格的唯一性，由定義4可知，?Cs1≤C、Cs2≤C，其中Cs1、Cs2為C的子概念，使得Cs1∪Cs2=C，從而為雙向構(gòu)建概念格提供可行條件。另外在求概念節(jié)點(diǎn)時(shí)，關(guān)鍵是構(gòu)造第2類概念，傳統(tǒng)做法是通過對(duì)所有上層概念進(jìn)行求交運(yùn)算[19-20]，從而找到所需的概念節(jié)點(diǎn)，但運(yùn)算量較大且存在計(jì)算冗余。為此引入外延秩、內(nèi)涵秩協(xié)同搜尋概念節(jié)點(diǎn)，并對(duì)上述求交運(yùn)算進(jìn)行簡化。

定義5對(duì)K=(O,A,R)轉(zhuǎn)化為矩陣P后，?o∈O、?a∈A. 如果在P中o所對(duì)應(yīng)的行含有m個(gè)1，則稱外延秩為m，記作rE(o)=m；如果在P中a所對(duì)應(yīng)的列含有n個(gè)1，則稱內(nèi)涵秩為n，記作rI(a)=n.

性質(zhì)1設(shè)L(K)=(B(K),≤)為形式背景K=(O,A,R)所對(duì)應(yīng)的概念格，C1、C2、C3∈B(K)且均為第1類概念，C為第2類概念，C≤C3、C3≤C1、C3≤C2，C1∩C2為第2類概念并與C3具有相同的內(nèi)涵秩，則在構(gòu)造C時(shí)，只需計(jì)算上層的第1類概念與其他第1類概念的交集。

證明根據(jù)定義3、定義5，不失一般性，令rI(Int(C1))=rI(Int(C2))=d，rI(Int(C3))=rI(Int(C1∩C2))=d-1，C的上層第1類概念為C3，與其他第1類概念求交，有

rI(Int(C1∩C3))=rI(Int(C2∩C3))=d-2.

(5)

因?yàn)閞I(Int(C3))=d-1，C3與C1、C2的交集各有d-2個(gè)內(nèi)涵秩，由此可以得d-3≤rI(Int(C1∩C2∩C3))≤d-2. 先假設(shè)

rI(Int(C1∩C2∩C3))=d-3.

(6)

由(5)式、(6)式可得

rI(Int(C1∩C3))-rI(Int(C1∩C2∩C3))=
rI(Int(C2∩C3))-rI(Int(C1∩C2∩C3))=1.

結(jié)合rI(Int(C1))=rI(Int(C2))=d可推出rI(Int(C1∩C2))≤d-2，顯然這與rI(Int(C1∩C2))=d-1相矛盾，說明rI(Int(C1∩C2∩C3))=d-3的假設(shè)不成立，則有rI(Int(C1∩C2∩C3))=rI(Int((C1∩C2)∩C3))=d-2與(5)式的內(nèi)涵秩一致，表明第1類概念與第2類概念之間交集形成的概念可以由第1類概念求交得出，即在構(gòu)造C時(shí)，只需計(jì)算上層的第1類概念與其他第1類概念的交集。

由定義5可知：對(duì)于內(nèi)涵秩，從概念格的頂端至底端是逐步減小的，內(nèi)涵數(shù)量增加，概念逐步細(xì)化；對(duì)于外延秩，從概念格的底端至頂端是逐步減小的，外延數(shù)量增加，概念逐步泛化。因此通過迭代計(jì)算內(nèi)涵秩和外延秩，并利用概念的交、并操作對(duì)概念節(jié)點(diǎn)分層提取，從而實(shí)現(xiàn)概念格的雙向構(gòu)建。

步驟1根據(jù)(3)式計(jì)算概念格的上確界(Xsup,Ysup)=(((∪Xi)*)′,∩Yi)，其中Xi?O、Yi?A，Xsup、Ysup分別為上確界的概念外延和概念內(nèi)涵，將上確界作為概念格的頂層節(jié)點(diǎn)。

步驟2計(jì)算j=max {rI(a)|a∈A-∩Yi,Yi?A}，掃描形式背景矩陣找到內(nèi)涵秩為j所對(duì)應(yīng)的a，則頂層節(jié)點(diǎn)的子節(jié)點(diǎn)為(Xj,Yj)=((a∪Ysup)′,a∪Ysup)且全部屬于第1類概念。

步驟3令=j-1，由定義4可知，rI(a)=的概念節(jié)點(diǎn)包含兩部分。其中一部分由內(nèi)涵秩為j的第1類概念與上層所有的第1類概念按(1)式進(jìn)行求交操作，選擇相應(yīng)內(nèi)涵秩為的概念，對(duì)于其他秩小于的概念可作為下層的備選節(jié)點(diǎn)。另一部分通過掃描形式背景矩陣找到內(nèi)涵秩為所對(duì)應(yīng)的a，則可求得概念節(jié)點(diǎn)為(Xj-1,Yj-1)=((a∪Yj)′,a∪Yj). 為減少后續(xù)關(guān)聯(lián)規(guī)則提取過程中的候選項(xiàng)集數(shù)量，引入支持度約束作為判斷條件，即如果節(jié)點(diǎn)的外延個(gè)數(shù)小于最小支持度supmin，則其內(nèi)涵所對(duì)應(yīng)的項(xiàng)集一定是不頻繁的，因此可以去除該節(jié)點(diǎn)，不再參與求交運(yùn)算，否則保留該節(jié)點(diǎn)。

步驟4若j>0，則轉(zhuǎn)步驟3繼續(xù)搜索相應(yīng)的內(nèi)涵秩及其所包含的節(jié)點(diǎn)。否則輸出最終的概念。

1.2.2 基于外延秩構(gòu)建概念格

步驟1根據(jù)(4)式計(jì)算概念格的下確界(Xinf,Yinf)=(∩Xi,((∪Yi)′)*)，其中Xi?O、Yi?A，Xinf、Yinf分別為下確界的概念外延和概念內(nèi)涵，并將下確界作為概念格的底層節(jié)點(diǎn)。

步驟2計(jì)算l=max {rE(o)|o∈O-∩Xi,Xi?O}，掃描形式背景矩陣找到外延秩為l所對(duì)應(yīng)的o，則底層節(jié)點(diǎn)的父節(jié)點(diǎn)為(Xl,Yl)=(o∪Xinf,(o∪Xinf)*)且全部屬于第1類概念。

步驟3令=l-1，由定義4可知，rE(o)=的概念節(jié)點(diǎn)包含兩部分。其中一部分由外延秩為l的第1類概念與下層所有的第1類概念按(2)式進(jìn)行求并操作，選擇外延秩為的概念，對(duì)于其他秩小于的概念可作為上層的備選節(jié)點(diǎn)。另一部分通過掃描形式背景矩陣找到外延秩為所對(duì)應(yīng)的o，則相應(yīng)的概念節(jié)點(diǎn)為(Xl-1,Yl-1)=(o∪Xl,(o∪Xl)*)。

步驟4若l>0，則轉(zhuǎn)步驟3繼續(xù)搜索相應(yīng)的外延秩及其所包含的節(jié)點(diǎn)，否則輸出最終的概念。

1.3 后件約束關(guān)聯(lián)規(guī)則提取

在實(shí)際的關(guān)聯(lián)規(guī)則提取過程中，通常挖掘的目標(biāo)是明確的，例如要分析坦克駕駛模擬訓(xùn)練成績的影響關(guān)聯(lián)因素，因此可以提前確定產(chǎn)生規(guī)則的后件，啟發(fā)搜索內(nèi)涵間的相互關(guān)系，從而減少冗余計(jì)算、提高算法運(yùn)行效率。本節(jié)以生成的概念節(jié)點(diǎn)為基礎(chǔ)，通過分析外延數(shù)與支持度閾值的關(guān)系得到頻繁概念節(jié)點(diǎn)，然后以規(guī)則后件固定作為約束條件過濾不相關(guān)的節(jié)點(diǎn)，最后提取滿足置信度閾值的關(guān)聯(lián)規(guī)則。

對(duì)于概念節(jié)點(diǎn)C=(X,Y)，當(dāng)外延數(shù)大于最小支持度時(shí)，稱此節(jié)點(diǎn)為頻繁概念節(jié)點(diǎn)。由于外延是具有共同屬性的全部對(duì)象集合，內(nèi)涵Y所對(duì)應(yīng)的項(xiàng)集為頻繁閉項(xiàng)集。根據(jù)Apriori反單調(diào)性[11]類比可知，任何頻繁概念節(jié)點(diǎn)的父節(jié)點(diǎn)都是頻繁的，任何非頻繁概念節(jié)點(diǎn)的子節(jié)點(diǎn)都是不頻繁的。因此，通過計(jì)算頻繁閉項(xiàng)集可以避免產(chǎn)生所有候選項(xiàng)集，極大地提高規(guī)則產(chǎn)生效率。

設(shè)C=(X,Y)為L(K)=(B(K),≤)中的一個(gè)概念節(jié)點(diǎn)，約束條件為Res且Res(C)=True成立，則C為符合條件的約束概念節(jié)點(diǎn)。本文中采用的約束條件為確定的規(guī)則后件項(xiàng)集D?A，可通過析取范式記為D=a1∧a2∧…∧an,ai∈A.

在1.2節(jié)得到所有概念節(jié)點(diǎn)后，按以下步驟提取關(guān)聯(lián)規(guī)則，若對(duì)規(guī)則結(jié)果不滿意，則可以調(diào)整支持度閾值，快速生成頻繁概念節(jié)點(diǎn)，避免傳統(tǒng)關(guān)聯(lián)規(guī)則提取過程中因支持度變化需要重新掃描數(shù)據(jù)庫生成頻繁項(xiàng)集的問題：

步驟1遍歷概念格的所有節(jié)點(diǎn)，依據(jù)支持度閾值產(chǎn)生頻繁概念節(jié)點(diǎn)，并將具有相同內(nèi)涵數(shù)的概念節(jié)點(diǎn)作為一組。

步驟2采用D=a1∧a2∧…∧an作為約束條件，從分組的頻繁概念節(jié)點(diǎn)中生成符合條件的概念節(jié)點(diǎn)集S.

步驟3取出S中的一個(gè)概念節(jié)點(diǎn)C=(X,Y)，并令=S-C，產(chǎn)生形如Y-D?D的規(guī)則。

步驟4計(jì)算規(guī)則Y-D?D置信度，當(dāng)項(xiàng)集Y-D不屬于任何一個(gè)節(jié)點(diǎn)的內(nèi)涵時(shí)，由外延與內(nèi)涵的封閉性可知，Y-D與Y具有相同的對(duì)象數(shù)，所產(chǎn)生的規(guī)則置信度為1，將Y-D?D加入規(guī)則集。反之，當(dāng)Y-D屬于某一個(gè)節(jié)點(diǎn)的內(nèi)涵時(shí)，所產(chǎn)生的規(guī)則置信度為|X|/|(Y-D)′|，若滿足置信度閾值條件，則將該規(guī)則加入規(guī)則集，否則將其刪除。

步驟5判斷概念節(jié)點(diǎn)集，若為空集，則關(guān)聯(lián)規(guī)則提取結(jié)束，輸出最終產(chǎn)生的規(guī)則集，否則轉(zhuǎn)步驟3.

圖1 基于BCLAR挖掘方法流程Fig.1 Mining process of association rules based on bidirectional concept lattice

通過以上對(duì)關(guān)聯(lián)規(guī)則挖掘的3個(gè)階段具體描述，給出基于BCLAR挖掘方法流程如圖1所示。

1.4 對(duì)比分析

為檢驗(yàn)算法的可行性與有效性，選擇Apriori算法和Bordat算法進(jìn)行對(duì)比分析，實(shí)驗(yàn)所需數(shù)據(jù)來自兩類：一類是真實(shí)數(shù)據(jù)集，通常具有較大的數(shù)據(jù)密度，包括Connect、Mushroom數(shù)據(jù)集；另一類是合成數(shù)據(jù)集，通過IBM的實(shí)驗(yàn)數(shù)據(jù)生成器獲得，并記作Tμ.Iλ.D?，其中μ代表含有的項(xiàng)集總數(shù)，λ代表數(shù)據(jù)庫中頻繁項(xiàng)集的平均長度，?代表數(shù)據(jù)庫所包含的數(shù)據(jù)對(duì)象總數(shù)。實(shí)驗(yàn)中共生成兩個(gè)數(shù)據(jù)集，分別為T10.I5.D500(T10)、T15.I8.D800(T15)。表3對(duì)4個(gè)數(shù)據(jù)集的基本信息進(jìn)行了簡要描述。

表3 實(shí)驗(yàn)數(shù)據(jù)集描述

由于在實(shí)際的關(guān)聯(lián)規(guī)則挖掘過程中，對(duì)挖掘算法的復(fù)雜度和被要求資源的承載度有較高要求，選擇運(yùn)行時(shí)間以衡量關(guān)聯(lián)規(guī)則算法復(fù)雜度，生成的頻繁項(xiàng)集數(shù)量作為占用內(nèi)存的評(píng)價(jià)指標(biāo)，同時(shí)為消除誤差，每次實(shí)驗(yàn)重復(fù)進(jìn)行5次，選擇各指標(biāo)的平均值作為最終評(píng)價(jià)標(biāo)準(zhǔn)。

1.4.1 算法運(yùn)行時(shí)間分析

設(shè)定支持度閾值為10%，置信度閾值為60%，以上3種算法在4個(gè)測試數(shù)據(jù)集上的運(yùn)行時(shí)間如圖2所示。由圖2可以看出，對(duì)于小規(guī)模數(shù)據(jù)集T10、T15，BCLAR算法與Apriori算法、Bordat算法的運(yùn)行時(shí)間相差不大，說明在數(shù)據(jù)密度較小情況下減少了整個(gè)搜索空間，相應(yīng)產(chǎn)生的候選項(xiàng)集規(guī)模也隨之減小，3種算法都能快速提取相應(yīng)的規(guī)則集。隨著數(shù)據(jù)規(guī)模變大，Apriori算法的運(yùn)行時(shí)間急劇增長，該算法需要重復(fù)掃描數(shù)據(jù)庫且迭代驗(yàn)證候選項(xiàng)集，導(dǎo)致在大規(guī)模數(shù)據(jù)集上消耗時(shí)間顯著增加，而BCLAR算法、Bordat算法直接根據(jù)概念格節(jié)點(diǎn)生成頻繁項(xiàng)集，避免了候選和驗(yàn)證的重復(fù)操作，所需時(shí)間比Apriori算法少，且BCLAR算法在構(gòu)建概念格時(shí)從頂部和底端同時(shí)搜尋概念節(jié)點(diǎn)，在時(shí)間上具有一定優(yōu)勢(shì)。

圖2 3種算法在不同規(guī)模數(shù)據(jù)集的運(yùn)行時(shí)間Fig.2 Run times of three algorithms in different scale datasets

1.4.2 頻繁項(xiàng)集數(shù)量分析

以Mushroom數(shù)據(jù)集為例，通過設(shè)定不同的支持度閾值(分別為1%、5%、10%、15%、20%、25%)，比較3種算法所產(chǎn)生的頻繁項(xiàng)集數(shù)量，如圖3所示。從圖3的結(jié)果可以看出：隨著支持度閾值的增加，頻繁項(xiàng)集數(shù)量都呈逐漸減少的趨勢(shì)；Apriori算法在支持度閾值較低時(shí)，頻繁項(xiàng)集的個(gè)數(shù)明顯大于BCLAR算法和Bordat算法，主要是由于Apriori算法搜索大量候選項(xiàng)集，再進(jìn)行連接操作會(huì)產(chǎn)生數(shù)據(jù)集中不存在的無效項(xiàng)集，導(dǎo)致頻繁項(xiàng)集數(shù)量較多；后兩種算法根據(jù)支持度閾值從概念格節(jié)點(diǎn)上搜索到的是頻繁閉項(xiàng)集，可以有效減少頻繁項(xiàng)集數(shù)；BCLAR算法在從頂層向下構(gòu)建概念節(jié)點(diǎn)時(shí)，結(jié)合支持度閾值提前刪除了不頻繁的概念節(jié)點(diǎn)，相當(dāng)于進(jìn)行了剪枝處理，從而使頻繁項(xiàng)集的搜索空間大大壓縮，產(chǎn)生的頻繁項(xiàng)集數(shù)比Bordat算法少。

圖3 3種算法在不同支持度下的頻繁項(xiàng)集數(shù)量Fig.3 Number of frequent itemsets of three algorithms with different support degrees

從1.4.1節(jié)、1.4.2節(jié)對(duì)比分析可以看出，BCLAR算法在運(yùn)行時(shí)間和生成的頻繁項(xiàng)集數(shù)量方面比Apriori算法、Bordat算法具有一定優(yōu)勢(shì)，能適用不同規(guī)模和密度的數(shù)據(jù)集，為了說明這種優(yōu)勢(shì)的存在，下面從理論上進(jìn)一步分析。在時(shí)間復(fù)雜性方面，Apriori算法在每次產(chǎn)生頻繁項(xiàng)集時(shí)，都需要掃描一次數(shù)據(jù)庫以進(jìn)行候選和驗(yàn)證操作，時(shí)間復(fù)雜度為O(|?|η+1)，|?|為數(shù)據(jù)對(duì)象總數(shù)，η為最大頻繁項(xiàng)對(duì)應(yīng)的項(xiàng)集總數(shù)。Bordat算法通過掃描一次數(shù)據(jù)庫，自頂向下構(gòu)建概念格，時(shí)間復(fù)雜度為O(22η|?|)；BCLAR算法在產(chǎn)生形式背景后不再掃描數(shù)據(jù)庫，通過雙向構(gòu)建概念格，時(shí)間復(fù)雜度為O(22η-1|?|)，比其他兩種算法的時(shí)間復(fù)雜度要小，同時(shí)當(dāng)支持度閾值發(fā)生變化時(shí)，不用重新掃描數(shù)據(jù)庫，直接在原始概念格上搜索頻繁概念節(jié)點(diǎn)，提高了算法運(yùn)行效率。因此，BCLAR算法具有更好的時(shí)間特性。在空間復(fù)雜性方面，Apriori算法由于迭代執(zhí)行連接和剪枝操作，產(chǎn)生大量候選項(xiàng)集，最壞情況可能呈指數(shù)增加，占用較多內(nèi)存空間。BCLAR算法采用概念格的形式存儲(chǔ)數(shù)據(jù)，直接計(jì)算概念節(jié)點(diǎn)的外延數(shù)得到支持度，從而產(chǎn)生無冗余的閉頻繁項(xiàng)集，極大地減少了內(nèi)存空間的占用。

2 坦克駕駛模擬訓(xùn)練關(guān)聯(lián)規(guī)則挖掘

通過BCLAR算法對(duì)坦克駕駛模擬訓(xùn)練產(chǎn)生的數(shù)據(jù)進(jìn)行分析，進(jìn)而探索一些適用的關(guān)聯(lián)規(guī)則，用于發(fā)現(xiàn)訓(xùn)練問題，以更好指導(dǎo)坦克駕駛模擬訓(xùn)練的組織實(shí)施。

2.1 數(shù)據(jù)來源

某型坦克駕駛模擬器是與實(shí)裝物理外觀一致、操作規(guī)程一致、使用方法一致的模擬訓(xùn)練裝備，同時(shí)還研發(fā)了專用的數(shù)據(jù)采集工具，用于采集駕駛模擬器的整個(gè)訓(xùn)練過程數(shù)據(jù)，支持設(shè)置數(shù)據(jù)采集的時(shí)間段，支持TB級(jí)數(shù)據(jù)量的存儲(chǔ)，能滿足分布式、集中式存儲(chǔ)的不同需求。

從系統(tǒng)數(shù)據(jù)庫中選取坦克駕駛模擬訓(xùn)練涉及的訓(xùn)練對(duì)象數(shù)據(jù)、訓(xùn)練過程數(shù)據(jù)、訓(xùn)練結(jié)果數(shù)據(jù)，建立數(shù)據(jù)決策表如表4所示，其中論域U={u1,u2,…,un}，數(shù)據(jù)屬性集A={軍銜，年齡，服役年限，文化程度，體能，訓(xùn)練等級(jí)，訓(xùn)練科目，理論測試，訓(xùn)練次數(shù)，成績?cè)u(píng)定}={X1,X2,X3,X4,X5,X6,X7,X8,X9,Y1}。根據(jù)坦克駕駛教范相關(guān)規(guī)定，并結(jié)合訓(xùn)練人員實(shí)際情況，對(duì)屬性集A的取值說明如下：

1)軍銜。取值范圍：列兵、上等兵、下士、中士、上士。

2)年齡。取值范圍：18≤X2≤32,X2∈Z，Z為整數(shù)集。

3)服役年限。取值范圍：1≤X3≤12,X3∈Z.

4)文化程度。取值范圍：初中、高中、大專、本科。

5)體能。取值范圍：優(yōu)秀、良好、及格、不及格。

6)訓(xùn)練等級(jí)。取值范圍：無等級(jí)、初級(jí)、3級(jí)、2級(jí)、1級(jí)。

7)訓(xùn)練科目。取值范圍：基礎(chǔ)駕駛動(dòng)作、坡上駕駛、低速擋駕駛、分個(gè)通過限制路和障礙物、換擋駕駛、各種速度駕駛、連續(xù)通過限制路和障礙物、道路駕駛。

8)理論測試。取值范圍：1≤X8≤100.

9)訓(xùn)練次數(shù)。取值范圍：1≤X9≤8,X9∈Z.

10)成績?cè)u(píng)定。取值范圍：1≤X10≤100.

表4 坦克駕駛模擬訓(xùn)練數(shù)據(jù)決策表

2.2 數(shù)據(jù)預(yù)處理

由表4顯示的內(nèi)容可知其為混合型決策表，既包含連續(xù)型屬性又含有離散型屬性。為了更好地提取泛化知識(shí)，采用文獻(xiàn)[17]中的離散化算法對(duì)混合型決策表中的數(shù)據(jù)進(jìn)行處理，產(chǎn)生各屬性的離散化編碼如表5所示。從表5中可以看出，年齡屬性被離散化成一個(gè)區(qū)間，表明其對(duì)坦克駕駛模擬訓(xùn)練成績影響最小，在后續(xù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘時(shí)可以不予考慮。

根據(jù)離散化編碼依據(jù)對(duì)原決策表的數(shù)據(jù)進(jìn)行處理可得表6，其顯示的內(nèi)容為多值形式背景。為了運(yùn)用概念格進(jìn)行關(guān)聯(lián)規(guī)則的挖掘，需要首先采用BCLAR算法中的多值關(guān)系轉(zhuǎn)換模塊，將原始多值形式背景離散化后采用矩陣形式表達(dá)為M′K，然后利用布爾化操作將M′K轉(zhuǎn)換為單值背景矩陣P：

表5 決策表的屬性離散化編碼

表6 離散化處理后的決策表

2.3 關(guān)聯(lián)規(guī)則提取

得到單值背景矩陣P后，計(jì)算內(nèi)涵秩和外延秩，從而逐層產(chǎn)生概念節(jié)點(diǎn)，實(shí)驗(yàn)中設(shè)定支持度閾值為10%，置信度閾值為65%，根據(jù)實(shí)驗(yàn)結(jié)果也可以動(dòng)態(tài)調(diào)整參數(shù)設(shè)置。由于對(duì)坦克駕駛模擬訓(xùn)練數(shù)據(jù)實(shí)施關(guān)聯(lián)規(guī)則分析重點(diǎn)是研究對(duì)坦克駕駛技能成績的影響因素及內(nèi)在規(guī)律，選擇訓(xùn)練成績?cè)u(píng)定作為規(guī)則后件固定的約束條件，從而刪除一些與之不相關(guān)的頻繁概念節(jié)點(diǎn)，最終生成的約簡關(guān)聯(lián)規(guī)則如表7所示。

以表5為依據(jù)，對(duì)最終得到的關(guān)聯(lián)規(guī)則分析如下：

1)規(guī)則1：X11∧X43∧X44∧X71∧X91?Y14，即具有大專以上文化程度的列兵經(jīng)過1～2次訓(xùn)練，在“基礎(chǔ)駕駛動(dòng)作”訓(xùn)練科目中成績?cè)u(píng)定為[83,89]。表明高學(xué)歷入伍的士兵接受能力、動(dòng)手操作能力較強(qiáng)，在受過較短時(shí)間訓(xùn)練后，能在基礎(chǔ)訓(xùn)練科目上取得較好成績，體現(xiàn)了高學(xué)歷教育在增強(qiáng)士兵軍事本領(lǐng)上的重要作用。因此針對(duì)這類具有較高學(xué)歷士兵，可以有針對(duì)性地集中組訓(xùn)，適當(dāng)加快訓(xùn)練進(jìn)度，從而有效提高他們的駕駛專業(yè)技能水平。

表7 坦克駕駛模擬訓(xùn)練中的關(guān)聯(lián)規(guī)則

2)規(guī)則2：X14∧X15∧X64∧X65∧X77?Y15，即具有2級(jí)以上訓(xùn)練等級(jí)的中士、上士，在“連續(xù)通過限制路和障礙物”訓(xùn)練科目中成績?cè)u(píng)定為[91, 99]。表明作為坦克駕駛隊(duì)伍主體的2級(jí)、1級(jí)駕駛員具有較高的操作技能水平，在難度較大的科目“連續(xù)通過限制路和障礙物”中獲得了優(yōu)異成績。因此在平時(shí)訓(xùn)練中可以充分發(fā)揮這些專業(yè)人才的幫教作用，讓他們充當(dāng)小教員，縮短復(fù)雜訓(xùn)練科目時(shí)間，提高訓(xùn)練效率。

3)規(guī)則3：X72∧X91?Y14∧Y15，即在“低速擋駕駛”訓(xùn)練科目中，經(jīng)過1～2次訓(xùn)練可取得良好以上的訓(xùn)練成績，表明“低速擋駕駛”訓(xùn)練科目相對(duì)容易，受訓(xùn)人員在經(jīng)過較少的訓(xùn)練后即可以掌握此項(xiàng)技能。因此針對(duì)該科目可以適當(dāng)減少訓(xùn)練時(shí)間，提高坦克駕駛模擬器的利用率。

4)規(guī)則4：X11∧X12∧X13∧X79∧X94?Y11∧Y12，即列兵、上等兵、下士在“行軍駕駛”訓(xùn)練科目中經(jīng)過7～8次訓(xùn)練，成績總體仍然比較差，評(píng)定分?jǐn)?shù)位于[35, 58]、[60, 73]兩個(gè)區(qū)間，表明“行軍駕駛”科目的訓(xùn)練效果不夠理想，具有一定的普遍性，應(yīng)該考慮系統(tǒng)因素。通過分析某型坦克駕駛模擬器發(fā)現(xiàn)，對(duì)“行軍駕駛”科目功能的設(shè)計(jì)還不夠詳細(xì)，仿真模型與真實(shí)訓(xùn)練場景還有一定誤差，需要進(jìn)一步研究改進(jìn)，從而滿足坦克駕駛模擬訓(xùn)練的全覆蓋要求。

5)規(guī)則5：X11∧X42∧X75∧X81∧X82?Y12，即具有高中文化程度的列兵對(duì)駕駛理論掌握較差，在“分個(gè)通過限制路和障礙物”訓(xùn)練科目中，成績?cè)u(píng)定為[60, 73]，表明此類受訓(xùn)對(duì)象對(duì)駕駛理論不夠熟悉，而“分個(gè)通過限制路和障礙物”訓(xùn)練科目的動(dòng)作要領(lǐng)比較復(fù)雜，通過方法也不盡相同，涉及操作的扣分點(diǎn)多達(dá)17項(xiàng)。因此在操作駕駛模擬器前，需要對(duì)相關(guān)的理論進(jìn)行認(rèn)真學(xué)習(xí)，熟練掌握通過各種限制路和障礙物的方法步驟，為實(shí)際操作訓(xùn)練打下基礎(chǔ)。

3 結(jié)論

本文提出一種基于BCLAR挖掘方法，并將其用于坦克駕駛模擬訓(xùn)練結(jié)果分析。得出主要結(jié)論如下：

1)通過矩陣布爾化操作對(duì)坦克駕駛模擬訓(xùn)練數(shù)據(jù)進(jìn)行多值轉(zhuǎn)化處理，可有效拓展概念格的適用范圍。

2)BCLAR算法利用內(nèi)涵秩和外延秩同時(shí)構(gòu)建概念格，設(shè)計(jì)支持度閾值約簡概念節(jié)點(diǎn)，運(yùn)行時(shí)間和生成頻繁項(xiàng)集數(shù)量優(yōu)于Apriori算法和Bordat算法。

3)在解決某型坦克駕駛模擬器訓(xùn)練結(jié)果分析時(shí)，BCLAR算法可以提取用戶所注的關(guān)聯(lián)規(guī)則，對(duì)坦克駕駛模擬訓(xùn)練具有一定的指導(dǎo)作用。