基于數據立方體的評估特征項生成方法

劉海洋,唐宇波,胡曉峰,喬廣鵬

(1.國防大學聯合作戰學院,北京 100091;2.航天工程大學,北京 101416)

典型的戰區聯合作戰方案涉及要素眾多、作戰空間廣闊、作戰問題多樣且指標關聯復雜,針對相同的作戰方案評估問題,不同的專家往往會給出不同的指標選取建議,就是同一個專家在不同作戰階段所選取的指標也會有所側重。傳統的自上而下逐層分解的指標生成模式[1]:一方面囿于專家經驗的條條框框,在指標完備性上很難突破現有的認知;另一方面由于人工介入程度較高,在速度上很難實現快速提升,因此,傳統的指標生成模式在作戰態勢快速變化的情況下顯然無法滿足需求。為解決評估指標快速選取問題,首先需要構建開放的基礎評估指標庫,并在此基礎上針對特定的評估問題快速選取相關指標,類似于“搭積木”一樣快速實現評估指標的組合,同時結合專家經驗對指標進行適當的增減與微調,最終形成評估指標產品快速投入評估工作。

在基礎評估指標庫的構建過程中,評估指標需要相應的評估數據做支撐,而評估數據中蘊含了大量的數據特征,除了利用特征工程由人工構建有限的評估指標外,很多數據特征并未得到有效利用。多維數據模型是面向數據分析應用而提出來的一種直觀的概念模型[2]。該模型將數據看作數據立方體(Data Cube)[3]形式。傳統的數據立方體是以犧牲存儲空間為代價來換取查詢效率上的提升,其對所有可能的維度組合進行聚集計算,并將聚集結果進行實例化存儲,以縮短查詢響應時間[4-5]。為減小數據立方體的尺寸,很多壓縮算法被相繼提出,如Condensed Cube[6]、Quotient Cube[7]、Dwaf[8]等算法。文獻[9-12]等通過使用MapReduce并行架構,實現數據立方體的并行建立、查詢和更新等功能,提高了數據立方體的計算效率。文獻[13]針對數據流的特點,提出了一種流數據立方體分析挖掘框架,文獻[14]對維度屬性中的概念分層特性進行了研究,文獻[15]從復雜網絡的角度對數據立方體內部結構特性進行了研究,文獻[16]針對大數據背景下的數據立方體物化視圖選擇問題,提出了基于云計算環境的物化視圖選擇算法改進思路。國內外相關研究大多集中在數據立方體的壓縮算法與查詢效率上,對具有動態時序特性的數據研究相對較少。

依托國防大學兵棋團隊研制的大型戰役兵棋系統開展聯合作戰方案推演,能夠為聯合作戰方案評估提供涵蓋陸、海、空、天、網電等多維戰場空間全過程推演所產生的全時空樣本數據。本文按照從數據中獲取指標的思路,以兵棋推演數據為基礎,基于數據立方體框架構建評估特征項生成模型,利用不同維度組合生成評估特征項。圍繞數據立方體中存在的“維度爆炸”問題,利用維度組合裁剪模型來縮小維度組合搜索空間,通過特征項標識算法對生成的評估特征項進行唯一標識,并采用移動時間窗口提取評估特征數據。所提取出的評估特征數據在某種意義上可以看作是評估問題在特定時空條件下所表征出來的特征信息,通過分析挖掘評估特征數據與評估問題的關聯性,能夠幫助指揮員從不同的視角、不同的側面理解評估問題。

1 數據立方體框架

定義1:多維數據模型(Multi-attribute Data Model, MDM)

具有多個維度的數據記錄,可形式化表達為S=(F0,F1,…,Fi:M),Fi表示維度特征,M為維度度量。

以奪取制空權作戰為例,空中作戰任務多維數據模型可表示為:

MDM=(作戰時間,屬性,任務類型,機型,活動空域,狀態:數量)

其中,在多維數據模型S中的維度特征主要包括作戰時間、屬性、任務類型、機型、活動空域和狀態等6個維度,特征的度量為飛機的統計數量。數據記錄r=(XXXX,1,2,5,4,1:6)可解析為:“作戰時間=XXXX”表示紀錄作戰發生的時刻(可精確至秒級),“屬方=1”表示紅方,“任務類型=2”表示空中偵察任務,“機型=5”表示某型飛機,“活動空域=4”表示在第4號空域內活動,“狀態=1”表示飛機狀態良好,“數量=6”表示飛機數量有6架。

定義2:數據立方體(Data Cube, DC)

給定一個時間段內的MDM,按照不同維度組合構建的一個數據集合。對于數據立方體中的每條數據記錄r=(f1,f2,…,fn:m),其中r[Fi]=fi∈Fi,i=1,2,…,n,fi為特征Fi的值,m為度量值。

數據立方體可以理解為多維數據模型在某時間段內的集合,對于時間維度T,ti-1

定義3:父代單元和子代單元

對于數據立方體中的數據單元Cm和Cn,定義*表示該維度折疊且不考慮聚合計算,則Cm是Cn的父代(或者Cn是Cm的子代)可表示為:

(1)

記為Cn[t]?Cm[t],即兩個數據單元的時間相同,父代單元至少在一個維度上能夠包含子代單元,且在其他維度上和子代單元的取值相等。父代單元與子代單元之間的關系可用數據立方體晶格表示[16],父子兩代的數據單元具有連接關系,且由父代單元指向子代單元,在3個維度上的數據立方體晶格如圖1所示。

圖1 在3個維度上的數據立方體晶格

以空中作戰任務數據立方體中的數據單元C0=(SIDE-1, J10B, AIR-ATTACK) 為例,其父代單元有如下7個:

C1=(*, J10B, AIR-ATTACK)

C2=(SIDE-1, *, AIR-ATTACK)

C3=(SIDE-1, J10B, *)

C4=(*, *, AIR-ATTACK)

C5=(*, J10B, *)

C6=(SIDE-1, *, *)

C7=(*, *, *)

上述例子中沒有顯示數據單元的度量值M,父代單元的度量值可以由其子代單元的度量值通過聚合計算得出。

假設數據立方體的維度為N,則該數據立方體的維度組合規模為

MD=2N

(2)

若數據立方體在每個維度上的取值基數為li,記為li=|Fi|表示第i維候選值的數量,其中i=1,2,…,N。則該數據立方體能夠生成的特征項規模可達

(3)

在某時間段內考察數據立方體中的數據,時間間隔越小,時間分辨率越高,所產生的數據規模越大。若該時段T內有k個時間片段,則最終的數據規模為

(4)

舉例來說,空中作戰任務數據立方體在僅考慮屬方、機型與任務類型3個維度的情況下,其維度組合有23=8種。假設屬方維度包括紅、藍、綠3方,機型維度包括84種不同型號的飛機,任務類型維度包括14種不同類型的任務,則可生成的特征項數量為(3+1)×(84+1)×(14+1)=5 100。若考察時間段設為4個小時,時間窗口間隔為5分鐘,則該時段內共有48個時間片段,最終形成的數據規模為48×5 100=244 800。

基于數據立方體框架,采用工程化的維度組合方法生成評估特征項,同時根據時間窗口大小,將數據切分為不同粒度的數據塊,通過聚合計算獲得與評估特征相對應的評估數據。在兵棋推演數據的基礎上,數據立方體提供了有組織、時序化的匯總數據,因此能夠在不同粒度層次上對數據單元進行較為全面的挖掘與分析,從而大大增強了探索式數據挖掘的能力,為后續的問題評估提供全量、實時和多層次數據支撐。

2 評估特征項生成模型

在利用數據立方體生成評估特征項的過程中,首先為縮小計算時間與存儲空間上的成本,需要對維度組合空間進行適當的縮減;其次需要對大量的評估特征項進行唯一標識,以便于后續的計算與檢索;最后在獲取數據的時間窗口上應能夠動態調整,以滿足不同粒度上的評估需求。

2.1 維度組合裁剪模型

由數據立方體模型產生的維度組合數量是冪級增長的,如給定n維記錄r=(f1,f2,…,fn:m),則可以產生2n種維度組合。隨著維度數量的增加,將會出現海量的維度組合,從而造成數據立方體的“維度爆炸”問題。因此,一般在維度的選擇上,需要引入領域專家的先驗知識,對相關維度的選取層次與取值范圍進行適當的限定,同時考慮計算的時間效率和存儲的空間效率,綜合選取數據立方體的維度。

1)限定維度組合規則

從兵棋推演數據中抽取相關維度,需要領域專家的先驗知識,而將抽取出的維度進行組合則需要考慮數據的涵義與推演的常識,部分不合理的維度組合將被剔除。以空中作戰任務中的屬方、機型和任務類型3個維度為例,機型維度中的殲10、殲11和殲20等機型應與屬方維度中的紅方相組合,與藍方或綠方的維度組合均為不合理的維度組合,另這3種機型可派出執行空中巡邏、空中游獵等任務,而執行空中運輸、電子對抗等任務的情況則應被剔除。因此,在考慮數據涵義與推演常識的基礎上加入維度組合規則,能夠排除掉很多不合理的組合情況,從而縮小了搜索空間,省掉不少沒有意義的維度組合計算。

假設數據立方體有N個維度,第i個維度記為Di,i=1,2,…,N,維度Di的取值可用Dij表示,j=1,2,…,|Di|。維度Di與維度Di+1的組合記為(Di,Di+1),組合后生成的特征項集合可表示為S=(Di1,Di2,…,Dim)～(D(i+1)1,D(i+1)2,…,D(i+1)n)。在數據涵義已知的情況下,通過加入維度組合規則,將維度取值限定在有限個數量較小的集合中,避免出現不合理的維度組合情況。圖2所示為一個在3個維度上的組合規則集合特例,其中|D1|=m,|D2|=n,|D3|=k,該維度組合的限定規則集合為

S1=D11～(D21,D22,…,D2i)～(D31,D32,…)

S2=D12～(D2i,D2(i+1),…)～(D31,D33,…)

…

Sm=D1m～(D2(j+1),…,D2n)～(D31,…,D3k)

(5)

圖2 在3個維度上的組合限定規則集合

通常情況下,維度組合的限定規則可通過對兵棋推演數據的預統計獲得,對各維度取值之間的組合情況進行計數,將計數值不為零的組合情況添加到規則集合中。限定規則也可使用排除規則,將不可能出現的維度組合情況加入到規則集合中,其作用原理與組合規則相同。在實際應用過程中,具體使用哪種規則應根據數據預統計情況綜合判斷。

2)限定維度組合測量閾值

數據立方體的聚合操作一般可以分為分布型(distributive)、代數型(algebraic)和整體型(holistic)3類[3]。在兵棋推演數據聚合操作中,常見的如sum和count等都屬于分布型聚合操作。這類分布型聚合操作的父代單元聚合了其所有子代單元的值,由父代單元的取值可得到子代單元的上限和下限,而由子代單元也可以推理出父代單元取值的范圍,如式(6)所示。

count(X)=sum({count(Xi|i=1,2,…,n)})

(6)

其中,父代單元X可由子代單元Xi集合組成。對于父代單元X下的任意子空間g的取值上下限如式(7)所示:

count(g)=sum({count(Xi|i=1,2,…,n)})

count(g)=min({count(Xi|i=1,2,…,n)})

(7)

結合式(7)可知,父代單元與子代單元間的包含關系在分布型操作中體現出單調特性,即

Cac[count]>τ→Ca[count]>τ,Cc[count]>τ

(8)

由上述父代單元與子代單元的上下限原理,可得維度組合測量閾值限定規則如下:

對于分布型聚合操作,如父代單元的測量值小于閾值,則所有它的子代單元的測量值必定小于閾值,因此可以裁剪掉所有子代單元。

如給定記錄r=(a,b,c),若Ca[count]<τ,則Cab|ac|abc[count]<τ。對于n維度的數據,可先對每個維度進行單維度統計,假設經統計后有k個單維度數據單元的測量值小于限定閾值(一般設限定閾值為0),則可以裁剪的維度組合數量為2k,而對于數據庫中每條數據記錄可減少統計操作2k-n次。如果單維度閾值篩選效果不佳,也可嘗試進行二維或高維的閾值篩選,其原理與單維度閾值篩選相同。由于兵棋推演數據中維度的取值往往具有稀疏性,所以裁剪模型通過限定測量閾值的方法通常可以剔除掉大多數的維度組合。

2.2 特征項標識算法

數據立方體通過維度組合產生了大量的特征項,而這些特征項中不同維度的屬性值又包含多種類型,如離散型、連續型以及字符型等等。為便于后續計算,對于單個維度的不同屬性值,還需要對其進行字典化處理,即以序列量化的形式對其進行編碼。

特征項標識(Feature Identifier, FI)算法的功能就是把維度組合所產生的特征項映射成唯一整數,且算法支持維度或屬性的擴展,即對現有維度或屬性進行新增或修改都不會與原值產生沖突。在數據R=(F1,F2,…,Fn:M)中,|Fi|表示第i維的基數,使用下列步驟進行特征項標識。

1)由于維度屬性值具有多樣性,需要先把記錄R的維度Fi映射成連續的自然數,即Fmap(fi)→Ni,0≤Ni≤|Fi|;

2)在步驟1)中產生n個自然數Ni,i=1,2,…,n,形成集合S=(N1,N2,…,Nn),對S中的任意非空子集,使用配對函數產生唯一的自然數標識。

定義4:配對函數(Pairing Function, PF)

配對函數的定義是把二維元組映射為一維元組,可形式化表示為π:N×N→N。一般情況下,配對函數是一類雙射函數[17],在自然數域內具有單調遞增的特性。

在元組維度較高的情況下,可使用嵌套模式進行映射,本文選擇Cantor配對函數[18]進行配對映射。在對不同維度的屬性取值進行編碼的基礎上,按照維度順序對屬性取值進行嵌套配對,把中間配對結果當成下一步遞歸操作的輸入。Cantor配對函數的嵌套映射原理見式(9)。

(9)

當元組維度較高時,Cantor配對函數可采用嵌套模式生成映射值,而當某些維度基數較大時,映射結果往往會出現大數值的情況,給標識理解與后續計算帶來一定的不便。此時,可考慮對配對函數進行部分改進,其基本思路是在不改變計算模型的情況下,盡量產生較小的映射值。

改進配對函數的理論依據如下:

1)在數據立方體中,數據單元描述與維度的先后順序無關,即數據單元(F1,F2)=(F2,F1);

2)嵌套計算為倒序計算,數值排序越靠后則參與循環的次數就越多,其對映射結果的影響就越大。

定義5:改進配對函數(Improved Pairing Function, IPF)

改進配對函數的定義如式(10)和式(11)所示。

IPF(F1,F2,…,Fn)→|F1|>|F2|>…>|Fn|

(10)

對給定維度Fi:

freq(fi1)>freq(fi2)>…>freq(fin)→n1

(11)

式(10)表示對輸入維度的先后順序進行排序,即改進配對函數的輸入維度順序取決于維度基數大小,基數越大則維度越靠前。式(11)表示對維度取值的先后順序進行排序,在把維度取值編碼成連續自然數時,將小自然數賦給出現頻率高(freq值大)的維度取值。通過對兵棋推演數據進行預統計,可以得到不同維度基數的大小和維度值的出現頻率。使用改進配對函數能夠有效減少大數值在嵌套中的計算次數,從而達到控制輸出映射值的目的。

特征項標識算法先通過數據統計對維度順序進行排序,并把維度值出現頻率按照由高到低的順序編碼成由小到大的自然數,通過嵌套函數得到所有相關的維度組合,并使用Cantor配對函數獲得所有特征項的唯一標識。結合維度組合裁剪模型,對特征項標識算法進行改進,可得到基于裁剪模型的特征項標識算法,如算法1所示。

算法1:基于裁剪模型的特征項標識算法

輸入:數據記錄r=(f1,f2,…,fi:m),裁剪閾值τ;

輸出:數據r生成的所有特征項標識。

Step1: set←{};

Step2: ←Cak[count]>τ,1≤k≤i;

Step3: (f1,f2,…,fj)←(f1,f2,…,fi)|;

Step4: 根據IPF模型中式(11)和式(12)進行排序編碼操作,(f1,f2,…,fj)→(n1,n2,…,nj);

Step5: set=(n1,n2,…,nj)組合所產生的所有特征項集合;

Step6: set←{};

Step7: begin for x∈{};

Step8: ←pairing function(x);

Step9: end for;

Step10: return .

2.3 時間序列索引描述

在數據立方體框架下,經過維度組合裁剪模型處理后生成的特征項,可視為有效的評估特征項,與評估特征項對應的評估數據需從兵棋推演數據中經聚合計算得到。由于兵棋推演數據本身帶有時間標簽,其具有內在的時序性,在對兵棋推演數據進行分析時應采用定制時間窗口按需在不同時間粒度上進行分析。

兵棋推演數據中的時間主要包括作戰時間和物理時間,作戰時間是按照虛擬的作戰邏輯進行演化,而物理時間則是對發生具體操作的真實時間的記錄,在作戰方案評估過程中應以作戰時間為主線對兵棋推演數據進行分析。在作戰時間軸上對時間進行離散化處理,生成連續的時間片段,按照時間片段對評估特征項進行聚合操作,將得到的結果存入評估特征空間中。

圖3 數據立方體時間窗口的聚合操作

如圖3所示,數據立方體中的時間粒度選擇支持時間窗口間的聚合操作,即小時間單元的累加可得大時間單元上的度量值。假設生成的評估特征項數量為n,對于任意第j個特征項,j=1,2,…,n,其在時間上的度量值均滿足時間聚合計算條件,合并算式如式(12)所示:

?1≤j≤n:DC[j,hj(ita+tb)]←DC[j,hj(ita)]+DC[j,hj(itb)]

(12)

3 實驗結果與分析

以某次兵棋推演數據為基礎,討論聯合作戰方案中制空權爭奪問題。對制空權評估來講,應重點考慮空中作戰、地面防空、偵察預警、干擾壓制、后裝保障等方面的影響因素,以空中作戰因素為例選取兵棋推演數據如表1所示,在屬方、任務類型和機型3個維度上進行維度組合,度量指標為數量,時間為作戰時間。

經數據預統計可知,屬方維度的基數是3,任務類型維度的基數是14,機型維度的基數是84,不經裁剪生成特征項的規模為5100。根據維度組合裁剪模型,屬方1對應的空中作戰任務類型有12種,共有49種機型參與空中作戰任務,每種空中作戰任務類型對應的機型數量取值范圍在[1,18]中,屬方1可生成的特征項數量為99,屬方2和3依次可生成50和57,故經裁剪后生成特征項規模為206項,裁剪率接近96%。

抽取作戰時間為20XX年X月X日6:00-7:00,作戰空間為XX號作戰空域,統計在特定時間內能夠對XX號作戰空域產生影響的作戰飛機數量,其中限制條件為空中任務編隊距作戰空域的距離同時小于探測距離與打擊距離(或干擾距離)。設定時間窗口大小為5 min,時間間隔為1 min,共生成60組評估特征數據如表3所示。

考慮空中作戰、地面防空、偵察預警與干擾壓制4類影響因素,在實際實驗過程中對部分維度屬性取值在概念層次上進行了聚合,如雷達型號基數較大,則可按照雷達作用距離將其概括為遠程雷達、中程雷達與近程雷達3個維度。針對制空權評估問題綜合選取了107個特征項,抽取1個小時內100個作戰區域的近4 000組評估特征數據作為特征數據集,利用兵棋推演實驗來判定制空權標簽數據,基于WEKA平臺分別采用樸素貝葉斯(NB)、支持向量機(SVM)、多層感知機(MLP)和隨機森林(RF)4種機器學習方法進行有監督訓練,訓練結果如表4所示。

由表4可知,除NB算法外,其余3種算法的分類準確率均超過了92%,而RF算法的準確率略高于SVM和MLP算法。從機器學習算法的分類效果來看,依據本文提出的方法所生成的評估特征項涵蓋了制空權評估的部分關鍵特征,能夠為分析制空權評估問題提供有效支撐。由107個特征項與標簽組成的訓練樣本集在制空權分類中的部分數據分布情況如圖4所示。

表1 兵棋推演空中作戰任務數據示例

表2 經裁剪后生成的特征項規模統計

表3 空中作戰任務評估特征數據抽取示例

表4 評估特征數據在4種不同機器學習算法上的訓練結果對比

圖4 部分評估特征數據在結果分類上的分布情況

4 結束語

基于數據立方體的評估特征項生成,本質上來講就是提取在特定時空條件下對當前作戰態勢產生影響的外在表征,且盡可能涵蓋相關的關鍵特征。從部分專家經驗來看,大規模的評估特征項可能會有很多沒有軍事意義或毫無價值,但是從數據的角度來看,特征的意義與價值則取決于特征數據與最終評估問題的相關性。結合從兵棋推演數據中獲取的評估特征數據,構建評估特征空間,可為后續的基于機器學習的評估模型提供可靠的訓練樣本數據集。在評估特征空間構建過程中,主要考慮特征的完備性和數據的時效性兩個方面。在完備性方面,主要采用維度組合的方式生成大規模的特征項,再利用裁剪模型縮小評估特征空間;在時效性方面,主要采用移動時間窗口的方法提取特定時段內的特征數據,較好的體現了作戰態勢的動態演化以及作戰效果影響的時延特性。