一種用于軍事情報分析系統的數據分類算法

王卓君

（解放軍國際關系學院，江蘇 南京 210039）

自動化情報分析系統就是在情報分析的若干環節應用計算機軟件，幫助情報分析人員做出情報研判的自動化系統。其中，分類分析法是計算機輔助情報分析的方法之一。常用的分類分析算法有決策樹算法、最近鄰算法、Bayes算法和神經網絡算法等。決策樹算法[1]是一種從訓練樣本集中推理出判定樹表示形式的分類規則的方法。其優點在于直觀性和易理解性。該算法不僅能做出分類和預測，而且它的生成過程、分類、預測以及從中所提取的分類規則都具有很強的可理解性。但決策樹算法同時也存在著不足。在計算樹節點熵屬性時，計算量大、復雜度高、訓練集過大，從而可能造成計算機內存無法運行。神經網絡算法可用于數據挖掘的分類、聚類、特征挖掘、預測和模式識別等方面。其優點包括對噪音數據的高承受能力，以及它對未訓練數據的分類能力。神經網絡最大的不足是需要較長的訓練時間并且可解釋性較差。最近鄰算法也稱KNN(K Nearest Neighbors)算法[2]。該算法的不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。Bayes算法是一類利用概率統計知識進行分類的算法，如NB （Naive Bayes）算法[3]。樸素貝葉斯分類算法是基于一個簡單的假定：在給定分類特征條件下，屬性值之間是相互條件獨立的[4]。其薄弱環節在于實際情況下，類別總體的概率分布和各類樣本的概率分布函數常常是未知的。為了獲得它們，就要求樣本足夠大。

其中，決策樹算法和神經網絡算法以其直觀性、易理解性、對噪音數據的高承受能力和對未訓練數據的分類能力顯著優勢被廣為應用。本文嘗試應用決策樹算法中ID3算法[5]和神經網絡算法中的Boltzmann機[6]對軍事情報系統進行組合建模，并針對Boltzmann機和ID3算法存在的不足，分別對Boltzmann機的Sigmoid函數和ID3算法中的信息熵進行改進，從而改善Boltzmann機在訓練過程中易出現網絡麻痹與溫度訓練過擬合等問題，同時降低ID3的計算復雜度，加快了建模的速度。

1 軍事情報分析系統的組成和業務處理流程

1.1 系統的組成

軍事情報分析系統以情報數據分類算法（IDC Information Data Classifying Agorithm）為核心，主要包括情報數據預處理模塊、IDC數據分類模塊、規則庫模塊。其中，IDC情報數據分類模塊是其核心模塊。

1.2 系統的業務處理流程

軍事情報分析系統采用雙層分類算法對情報數據進行分析處理。系統的業務處理流程簡述如下。流程圖如圖1所示。

2 算法原理與改進

2.1 Boltzmann機算法原理與改進

作為第一層數據快速計算層中的核心算法，依據情報數據自身的特點，這里選擇Boltzmann機是較為合適的，Boltzmann行動選擇策略適于求解非精確狀態信息下的順序決策過程問題的行動選擇策略。具體算法原理如圖2所示：

圖1 情報處理系統基本業務流程圖

圖2 Boltzmann機算法原理圖

雖然 Boltzmann機能夠用來求解組合優化等問題，但仍存在訓練時間長和對統計錯誤敏感的問題。在實際應用中，收斂速度和推廣能力會受到影響。對網絡模型改進的主要目標有兩個：一是防止網絡訓練過程中麻痹現象的出現，提高網絡的訓練速度；二是提高網絡的泛化能力，避免過擬合現象。

由于 Boltzmann機是基于梯度下降法進行訓練的，所以網絡的激活函數要求連續可微。參數導數的存在性對學習至關重要，因此Boltzmann機網絡一般不采用閾值函數和符號函數作為 sigmoid激活函數。Boltzmann機的激活函數一般要求非線性，否則多層網絡將不提供高于兩層網絡之上的任何計算能力。有界性也是激活函數的一個條件，這可以限定權值和單元輸出的上下邊界，使訓練次數也有限。如果輸出是代表一個概率時，有界性尤其重要。單調性也是激活函數的一個期望的性質，因為如果激活函數在定義域中不是單調的，存在一個或多個極值，則會延長訓練時間并對錯誤敏感。

當 sigmoid函數的輸出接近飽和值時，其梯度很小，相應的權值調節量也很小，學習速度很慢，這就是麻痹現象產生的原因。一旦產生網絡麻痹，則會不斷地對采集過程中產生的演習過程數據中的某些屬性值進行退火降溫，從而拉長數據學習時間，降低整個數據分類效率。為了防止產生這種現象，本文提出了對 sigmoid函數的輸出進行限制的方法，限制其最大輸出值小于飽和值，改進sigmoid函數為

2.2 ID3算法原理與改進

ID3基本原理是基于二叉分類問題，但很容易將其擴展到多叉分類上。假設訓練集中有m個樣本，樣本分別屬于c個不同的類，每個類的預設訓練實例集為X，學習的目的是將訓練實例分為n類，記為C={X1，X2…Xn}。設第i類的訓練實例個數是|Xi|=Ci，X中總的訓練實例個數為|X|，記一個實例屬于第i類的概率為P(Xi)，則有

此時決策樹對劃分C的不確定程度為I(X,C)，簡記為I(X)：

對熵壓縮的度量過程就是縮小對數據劃分不確定程度的過程。若選擇屬性A進行測試，設屬性A具有性質a1,a2,a3,…at，在A=aj的情況下屬于第i類的實例個數為，即為測試屬性。A的取值為aj時，它屬于第i類的概率。記為A= aj時的實例集。此時決策樹對分類的不確定程度就是訓練實例集對屬性A的條件熵：

葉結點Xj對于分類信息的信息熵為

即屬性A的熵壓縮為

其中，I( X|A)越小， G ain( A)的值越大。說明選擇測試屬性A對于分類提供的信息越大，選擇A之后對分類的不確定程度越小。該算法是把信息熵作為選擇測試屬性的標準，即樹結點的選擇策略。但在計算基于屬性的信息熵時，公式比較復雜，計算量較大，相應的復雜度也高，當數據量很大時很耗費硬件資源，計算花費的時間也長。

改進后的ID3算法結合洛倫茨曲線思想，設屬性劃分絕對平等曲線和實際屬性劃分曲線之間的面積為A，實際屬性劃分曲線右下方的面積為B，并以A除以A+B的商表示不平等程度。如果A為零，系數為零，表示屬性劃分完全平等；如果B為零，則系數為1，屬性劃分絕對不平等。曲線的弧度越大，那么系數也越大。具體曲線關系如圖3所示。

圖3 絕對平等曲線與實際屬性劃分曲線圖

此算法區別于傳統決策樹計算期望信息的方法，以往在計算不同類的信息概率后，首先將計算后的所有值進行相減，得出分類期望信息隨后，再分別計算對類中不同的屬性的熵，對這些熵進行相加，得出子集的熵最后，在將期望信息與子集的熵相減得出這個分支上的編碼信息：

這樣的計算步驟繁雜，在計算機語言中難以表達，因此，本文提出了一種反向熵壓縮度量法。該算法對的定義進行了改進，縮小了分析的粒度，立足點設立在每個集合中的屬性分布情況，從而降低了測試復雜度，減少了計算時間。下面對反向熵度量做出介紹。

在反向熵度量法中，I ( s1+ s2+ . ..+ sm)是一個計算根節點分裂的關鍵要素，是類中每個屬性的信息值。當對根節點進行分裂時，直接計算數據集合中每個類中不同屬性的熵值，根據每個類中屬性值總和的大小對整個數據集進行分裂。熵值越小，子集劃分純度越高。

其中，Pi是屬性i在屬性集中出現的相對頻率。

如果類I按照某個劃分點分成I1和I2，則劃分后的屬性信息和為

2.3 情報數據分類算法

情報數據分類算法（IDC Information Data Classifying Agorithm）由兩層組合而成：第一層是基于改進后的Boltzmann機的快速計算層；第二層是基于改進后的ID3算法的精確分析層。當經過預處理的情報數據進入IDC計算第一層后，對實戰過程情報數據、參戰單位編成情報數據、裝備相關情報數據、地理位置情報數據進行加權計算，權值是由輸入和輸出的相關性決定。相關性越大，則它們的相關權越大。然后采用Boltzmann機算法進行粗粒度地快速分類處理，得出分類結果。當數據粗分類結果進入第二層時，數據開始重新根據屬性集中各個屬性出現的相對頻率進行決策樹節點分裂計算，選擇屬性出現頻率最大的作為決策樹節點分裂值。對進入第二層的情報數據屬性集進行反復計算，形成決策樹，得出當前作戰的決策和規則。IDC算法流程如圖4所示。

圖4 IDC算法原理示意圖

3 實例分析與驗證

3.1 系統實例分析

3.1.1數據預處理

在數據挖掘的前期數據準備階段，需要對等待挖掘的原始數據進行數據清洗、數據變換、數據維歸約等操作，將之轉化為高質量的訓練樣本數據。以作戰過程中的陸戰編成數據中的部分屬性為例：

采集數據以數組的形式接收進來，其中D1為編成序號，D2為單位序號，D3為X軸坐標值上的參戰部隊坐標值，D4為Y軸上的參戰部隊坐標值。

為了使網絡達到較好的訓練效果，需要對數據進行規范化處理，將屬性數據按比例縮放，使之落入一個小的特定區間，如[0，1]或[-1,1]之間。

本文采用最小-最大規范化對原始數據進行線性轉換。假定minA和maxA分別為屬性A的最小和最大值。最小-最大規范化通過計算：

將A的值v映射到區間[n ew _ minA,n ew _ maxA]中的 v'。例如屬性編制人數的最小與最大值分別是0和8006，如果想映射編制人數到區間[0, 1]，根據最小-最大規范化，編制人數1280將轉變為

當數據預處理結束后，將所有規格化數據根據不同的屬性劃入不同的計算節點。節點劃分策略是根據數據屬性來確定節點的數量，數據屬性，節點= { n1, n2,...,nn}。隨后采用情報數據分類算法進行下一步的分類工作。

3.1.2數據快速分類層

當情報數據進入數據快速計算層時，采用抽取主表進行分析的策略。這里選擇陸戰編成情報數據和陸戰當前狀態情報數據這兩類情報數據作為數據快速計算層分析的主要內容，對其進行布爾量化，量化結果如表1所示。

表1 布爾量化結果表

首先設定網絡權值、初始溫度。預置權值不能為0，否則學習過程將不可能開始，一般權值選定在[0，-1]或[-1，1]之間。任取初始權值w1＝ 0 .5,w2＝0.4,w3＝0.2,w4＝0.3。訓練集由狀態｛0000,0100,0101,0110,1000,1100,1101｝ 組成，它們的閾值分別為-0.9，-0.2，-0.3，0.7，初始溫度為0.25，0.5，1。

隨后根據各個節點單元激活函數值計算出各個狀態的轉移概率。當屬性狀態從0轉移至1時，

在初始設定溫度為 0.25時，當 φ ( s )＜ 3 .992，取；當 φ ( s )＞ 3 .992，取ρ值。ρ取{0，3.992}之間的一個值，這里定為3.9；當初始設定溫度為0.5時，ρ取{0，3.994}之間的一個值，這里也定為3.9；當在初始設定溫度為1時，則ρ取{0，3.968}之間的一個值，這里同樣定為3.9。

對陸戰情報數據中的火力打擊能力進行情報分析需要根據P(1)的綜合指標指數來判定火力打擊的水平 PSD。P(1)綜合值越高，打擊水平越強。根據 P(0)的綜合指標指數初步判定危險級別DL。P(0)綜合值越小，危險級別越高，結果見表3。

3.1.3數據精確分類層

當數據從上一層分析完畢后，進入精確分類層的數據已經形成初步的分類數據模型，隨后展開進一步的精確數據分類處理。這里需要確定能夠生成一棵簡單決策樹的分裂屬性。

已分析過的數據中包含{zbx，zby，xtk，xhp，xdd，pbwql，bcxh，f}屬性。其中，xtk表示坦克，xhp表示火炮，xdd表示地點，pbwql表示武器，bcxh表示消耗量，f表示類型。下面展開對這些屬性反向熵值的計算。類標號 f有兩個不同的值（即{1，2}，1代表我軍，2代表敵軍），因此有兩個不同類 C=2。設C1對應1，C2對應2。類1中有12個樣本，類2中有8個樣本，隨后基于C中不同的類別開始計算屬性的反向熵值。首先從陸戰編成情報數據和陸戰當前狀態情報數據中的屬性開始，如表4。

表2 第一層Boltzmann機網絡訓練結果表

表3 評估結果表

根據式（8）、式（9）對每一個屬性的反向熵值進行計算：

目前最小的反向熵值屬性是 xhp，所以在決策樹的根節點處選擇xhp作為其分裂節點。隨后對我軍編成情報數據、敵軍編成情報數據中的數據進行屬性熵值分析。這時需要重新劃分類C。我軍編成情報數據、敵軍編成情報數據中的類標號屬性 bcxh有兩類不同的值，分別是{001001001000001,…, 001001001001000}和{001001001001001,…, 001001001002000}，這時也存在兩個不同的類 C=2。設 C1對應{001001001000001,…, 001001001001000}，C2 對應{001001001001001,…, 001001001002000}。計算我軍編成情報數據中的屬性熵值，如表5。

表4 陸戰屬性計算表

表5 我軍編成屬性計算表

計算敵軍編成情報數據中的屬性熵值，如表6。

表6 敵軍編成屬性計算表

故此部隊編號屬性為決策樹的子節點的屬性。

隨后計算我軍部隊編成準備情報數據、敵軍部隊編成準備情報數據的屬性熵值，這時劃分類C不用發生改變。下面計算我軍部隊編成準備情報數據中的屬性熵值，如表7。

表7 我軍部隊編成準備屬性計算表

故此裝備編碼屬性為決策樹子節點的屬性。所有采集的數據都依次推算，最終得到一顆完整的決策樹。

3.1.4生成規則

部分得到的規則如表8所示，表中的DL分別取值“High”、“Normal”和“Low”，代表指定單位實時威脅評估的風險等級。

表8 第二層得到的規則表

3.2 系統驗證

首先采用改進sigmoid函數的Boltzmann機對問題進行訓練，sigmoid函數采用公式（1）中的函數，ρ取1.5。訓練目標采用區間[-1.7,-1.0]或[1.0,1.7]，訓練方法采用隨機訓練法。隨后采用改進熵函數的ID3算法對經過改進后的Boltzmann機訓練后的問題進行分類。同時，也采用沒有改進的Boltzmann機和ID3算法對問題進行訓練和分類。為了直觀的比較兩種情況的效果，我們分別做出了它們的訓練曲線，實驗結果如下。

實驗分別采用了83-53-13結構的Boltzmann機網絡進行訓練，然后利用ID3算法對訓練結果進行分類，例如圖 5是利用改進后的 Boltzmann機與未改進Boltzmann機進行問題訓練曲線圖。

圖5 改進后的Boltzmann機與未改進Boltzmann機問題訓練曲線圖

圖6是利用改進后的ID3算法和未改進的ID3算法進行問題分類的曲線圖。

圖6 改進后的ID3算法與未改進ID3算法問題分類曲線圖

圖7是采用改進后的 Boltzmann機和改進后的ID3算法-未做改進的Boltzmann機和ID3算法進行問題訓練分類曲線圖。如圖所示，在三種情況下，用改進后的 Boltzmann機和 ID3算法明顯比未做改進的Boltzmann機和ID3算法訓練分類速度快。

圖7 改進后的Boltzmann機和ID3算法和未做改進的Boltzmann機和ID3算法問題訓練分類曲線圖

4 結束語

本文利用兩種情報數據分類算法構建出一種新的情報數據分類算法用于軍事情報分析系統的設計開發之中，針對原有算法的不足做出改進，并借助情報數據對整個系統進行了實例分析與驗證。從分析結果中發現，新的情報數據分類算法在數據訓練、分類的速度上要優于未做改進的算法。

[1]王旅,彭宏,胡勤松.基于判定樹歸納分類的土質分類定名方法[J].計算機工程與設計,2006,27(11)：1929-1931.

[2]王燕,李睿,李明.數據挖掘技術應用研究[J].甘肅科技,2001,17(1)：49-50.

[3]Witten I H,Frank E.Data Mining：Practical Machine Learning Tools and Techniques with Java Implementations[M]. Seattle: Morgan Kaufmann Publishers,2000:265-314.

[4]張璠.多策略改進樸素貝葉斯分類器[J].微機發展,2004(4):35-36.

[5]賈世樓.信息理論基礎[M].哈爾濱：哈爾濱工業大學出版社,1986.

[6]D.E.Culler, R.Karp, D.Patterson, A.Sahay, K.E.Schauser,E.Santos,R.Subramonian,T.Voneicken[A].LogP: Towards a Realistic Model of Parallel Computation. Proc.ACM Symp.on Principles and Practice of Parallel Programming,1993:1-12.