裝備模擬訓練系統數據離散化

鄧 青， 薛 青， 杜 楠， 付朝博

(1.陸軍裝甲兵學院演訓中心， 北京 100072； 2.68303部隊， 格爾木 816099)

裝備模擬訓練系統數據預處理主要是用于挖掘前對數據展開治理，包含必要的數據融合、數據清洗、數據離散化、數據變換等步驟，從而使數據符合挖掘方法和挖掘模型的輸入標準[1]。數據離散化是其中的一項重要工作，在裝備模擬訓練系統的實際使用中，按照不同的應用場景以時間、空間順序采集了大量數據，涉及地理位置、機動路線、毀傷概率等連續型數據[2]。這些數據表達過于細化，不利于數據挖掘發現簡潔的模式和知識，另外對噪聲也非常敏感，一旦出現細小的誤差可能會造成兩個數據的比較值不相等。而數據離散化是在最小化信息損失的前提下，根據設定的離散化準則選擇連續型數據的若干個最優劃分，將連續型數據轉化成少量的有限區間，同時采用整型或字符型數據量化離散化區間的值。因此，通過對裝備模擬訓練系統數據進行離散化處理，能夠有效簡化數據，滿足挖掘算法的適用需求，提高挖掘算法的學習能力，從而提取有價值的規則。

數據離散化方法主要分為無監督和有監督兩類。無監督離散化不使用類標簽，通過數據的分布特征對單個屬性進行劃分，實現方式簡單，但最終離散的精度難以保證，尤其當數據分布極度不平衡時會產生較差的結果。等寬算法[3](equal width, Equal-W)是應用廣泛的無監督離散化算法，根據預先設定的參數，將連續數據劃分為若干個等寬區間，由于未考慮數據分布特點，算法易受噪聲影響。文獻[4]運用頻率模式增長(frequent pattern growth, FP-Growth)算法挖掘火炮模擬訓練系統數據，采用連續型數據結構，存儲代價大且隨著數據增長搜索效率下降。文獻[5]對坦克駕駛模擬訓練操作數據首先進行規范化、離散化等預處理，然后采用支持向量機進行分類挖掘，實驗證明在數據離散化處理后，能更好地提取泛化知識。文獻[6]基于定制的專門離散化算法研究了坦克駕駛模擬訓練數據，用于輔助裝備使用決策，同時能減少昂貴的裝備測試費用。文獻[7]提出Chimerge離散化算法將連續型數據的每個不同取值作為一個單獨的區間，采用χ2統計量對相鄰區間測試，并優先合并χ2最小的區間，直到所有區間的χ2都小于指定的閾值。文獻[8]提出自上而下的MDLP(minimum description length principle)離散化算法，選擇信息熵最小的點作為分割點，遞歸操作直到滿足最小描述長度準則。

從上述的數據離散化方法可以得出，多數是采用單屬性離散化，即在每次離散化的過程中，只考慮一個屬性，然后按照設定的離散化準則循環迭代，直至每個屬性處理完畢[9-11]。這些方法具有簡單易理解、執行速度快的特點，但往往忽視了屬性之間的相關性、互補性，割裂了屬性之間的聯系。而對于裝備模擬訓練系統實際運行產生的數據，往往幾個數據屬性之間是相互作用、共同影響的[12-13]，比如，在運用坦克駕駛模擬訓練系統進行駕駛操作技能訓練時，對油門、離合器、制動器的操作并不是孤立的，應該相互配合才能更好掌握操作要領，提高訓練成績，因此，在對油門、離合器、制動器的操作數據進行離散化時，必須要考慮它們之間的相互作用，否則在后續進行數據挖掘時會產生錯誤的知識。針對裝備模擬訓練系統數據離散化存在的問題，提出一種基于層次聚類和相容度的數據離散化方法(discretization algorithm by hierarchical cluster and compatibility，DHCC)。該方法屬于有監督、自下而上的處理過程，首先通過動態確定簇數對數據的所有屬性進行層次聚類，實現對各屬性的初始整體劃分，然后運用相容度差值指導相鄰區間的合并，有效去除冗余區間，從而獲得全局最優屬性區間集合。實驗階段對DHCC離散化算法進行了比較，并在實際數據集上進行了驗證。

1 裝備模擬訓練系統數據離散化過程建模

根據裝備模擬訓練系統產生的數據特點，通常包含條件屬性和類別屬性，一組條件屬性通過相互作用共同決定了類別屬性。因此，采用決策表將這些屬性表示成數據集合的形式，從而便于直觀地對裝備模擬訓練系統數據離散化過程進行建模分析。首先給出裝備模擬訓練系統數據決策表有關定義。

定義1從裝備模擬訓練系統關系數據庫中抽取數據挖掘所需要的數據集B，將其轉化為四元組的數學表達形式S=〈U,A=C∪D,V,F〉，其中，U為數據對象集，A為屬性集，包含條件屬性集C和決策屬性集D，V為值域集，F表示數據屬性到值域的映射，則稱S為決策表。

對裝備模擬訓練數據離散化需要結合實際的挖掘任務，將連續屬性轉變成離散屬性、定量數據變換為定性數據。根據以上分析，對裝備模擬訓練系統數據離散化過程模型描述如下。

假設裝備模擬訓練系統數據采用決策表S=〈U,A=C∪D,V,F〉表示，數據對象u∈U，屬性c∈C，c的值域為Vc=[lc,hc]，則存在F(u,c)∈Vc。設值域Vc上存在一分割點集合T={(c,a0), (c,a1),…, (c,an)}則T將Vc劃分形成區間集合Pc={[a0,a1), [a1,a2),…, [an-1,an]}，其中lc=a0

?c(u)∈[ai-1,ai)，i∈{ 1, 2, …,n}，根據屬性到值域的映射FP(u,c)可計算連續屬性c的所屬區間i，因此通過P={Pc|c∈C}將原決策表S=〈U,A=C∪D,V,F〉轉化成離散型決策表SP=〈U,A=C∪D,VP,FP〉。與原決策表相比，離散化后的決策表SP改變了屬性A的值域，對原有的取值范圍采用了有限個區間進行劃分，并用離散的數值標記每個區間，區間范圍內的數據都會被離散值所取代。

對于裝備模擬訓練數據決策表既包含連續型，又含有離散型數據，屬于混合型決策表，比如運用步戰車模擬訓練系統產生的數據既有電路總開關、音響按鈕等狀態數據，還包括油門裝置、發動機轉速等連續數據，有時不僅需要對連續型數據離散，為了挖掘出更加簡潔的作戰規則，在必要的時候對離散型數據也需更進一步的泛化處理，由此建立裝備模擬訓練系統數據離散化總體框架如圖1所示。其關鍵在于研究提出適當的數據離散化算法，同時滿足混合型決策表離散化的需求。

圖1 裝備模擬訓練系統數據離散化的總體框架Fig.1 Framework of equipment simulation training system data discretization

2 基于層次聚類和相容度的數據離散化方法

基于層次聚類和相容度的裝備訓練系統數據離散化方法，首先通過層次聚類，并結合屬性間的關聯，計算簇的正域調整確定聚類數目，實現對屬性的初始劃分。然后結合類別屬性信息，運用簡化的相容度對初始離散化結果的相鄰區間進行合并，減少斷點數和去除冗余區間，從而生成最終的離散化方案。

2.1 基于層次聚類的初始整體劃分

層次聚類是對整個決策表的所有條件屬性同時進行，可以更好地保持屬性間的關聯(和分類精度下降問題)。在聚類前，為便于比較數據對象間的相似性，對?c∈C的屬性值進行標準化處理，處理依據為

(1)

式(1)中：max[c(U)]、min[c(U)]分別表示整個決策表中屬性c的最大值和最小值。初始時將整個U中的每個對象都看作一個簇，選擇歐氏距離建立簇之間的相似度矩陣(simulation matrix, SIM)，矩陣元素SIMij表示ui和uj之間的距離，即

(2)

選擇矩陣SIM中最小元素所對應的兩個數據對象進行聚類，對新形成的簇與其他數據對象的相似性按照平均距離計算，爾后更新相似度矩陣，刪除原來的兩個數據對象。依此循環迭代進行聚類，直到滿足事先指定的聚類個數，但裝備模擬訓練系統數據所形成的決策表無法預知簇的個數。針對這一問題，利用數據自身的固有特征，在每次聚類過程中，計算正域的變化，當值減少表明聚類后出現了不一致性的數據，對該簇的聚類過程應當終止。反之表明聚類后沒有降低正域，可以繼續進行聚類，依次迭代直到處理完所有的數據對象。

假定最終生成的聚類數為L，將形成的每個簇向條件屬性空間進行投影，可得到每個屬性的一系列取值區間。以屬性c為例，對于第k個(1≤k≤L)簇所包含的數據對象集合為Uk，則屬性c在該簇中的取值集合為

(3)

進一步可得出屬性c在該簇的區間為

(4)

則屬性c在各個簇的左、右區間集合表示為

(5)

(6)

對上述兩個區間集合的元素按從小到大進行排序，得到屬性c的初始劃分區間為

(7)

2.2 基于相容度的區間合并

第一步的層次聚類用于初始劃分屬于無監督離散化，運算效率高，但容易導致相似的區間被分離，且隨著屬性數量的增多，產生的區間也會增加，因此，通過引入類別屬性信息，同時結合相容度指導區間合并，以此最小化屬性的區間數，提高離散化效果。

區間合并前，首先需要確定合并的優先級。根據信息論，熵值反映了數據的類分布特征。進一步，如果屬性區間的信息熵越小，則相應的類分布一致性越高，屬性區間的重要程度就越低，特別是當區間的信息熵為0時，相應的類屬性完全一致，該區間的重要程度最低，不會對其他屬性造成影響，應作為區間合并的首要選擇。因此，重要程度低的屬性區間優先合并。

(8)

(9)

(10)

為了體現不同屬性區間相對于類屬性的聯系，將所有屬性區間的信息熵進行排序，選擇信息熵最小的相鄰區間作為候選合并對象，確保每個屬性區間均有被選取的機會。

在執行合并的過程中，需要保持整個決策表的一致性不變，以此作為區間合并的判斷條件。為實現這一目的，通過采用計算合并后的相容度φ′，并將其與原始的相容度φ0進行比較，可以避免傳統采用人工設定閾值作為合并判斷條件帶來的誤差。即

Δ=φ′-φ0

(11)

當Δ<0，表明相容度減少，合并后引起了決策表的不一致性，對這個區間的合并應當終止，并將這一相鄰區間標記為不可合并狀態，后續也不會成為候選的合并對象。反之當Δ≥0，表明合并后決策表的一致性仍然滿足數據集的精度要求，可以執行區間合并。依次選擇需要合并的下一個相鄰區間，直到所有相鄰區間處理完畢或剩下的相鄰區間已被標記為不可合并狀態，從而得到最終的離散化區間集合。

求解合并前后決策表的相容度是一個計算密集型過程，尤其是迭代操作將會耗費大量時間。針對這一問題，在計算過程中進行了簡化，即當每次相鄰區間合并，決策表相容度的變化主要是由相鄰區間合并所引起的，對于未參與合并的其他區間對相容度的變化不會帶來影響，這些屬性區間的一致性不變。因此，在計算相容度變化時只考慮待合并的相鄰區間，具體推導為

Δ=φ′-φ0=

(12)

式(12)中：POS表示粗糙集中的正域關系;IND表示等價關系。

2.3 算法描述

根據前兩節的分析，基于層次聚類和相容度的數據離散化算法具體流程如圖2所示。

圖2 算法流程圖Fig.2 Algorithm flow chart

輸入：原始決策表S=〈U,A=C∪D,V,F〉，C={c1,c2,…,ck}為所有條件屬性的集合，即待離散化的屬性。

輸出：最終的離散化決策表。

Step 1標準化處理，為比較數據對象間的相似性，對?c∈C的屬性值按式(1)進行處理。

Step 2

Step 2.1：將整個U中的每個數據對象視為一個單獨的簇，構建初始相似度矩陣SIM。

Step 2.2：選擇SIM中最小值所對應的兩個元素作為聚類的候選對象，按式(2)計算新形成的簇的正域。

Step 2.3：根據正域的變化情況，若出現了不一致性的數據，則放棄該簇的聚類，轉到步驟Step 2.2。否則轉到Step 2.4。

Step 2.4：對候選的數據對象執行聚類，并更新聚類后的相似度矩陣。

Step 2.5：判斷U中的數據對象是否處理完畢，若沒有則轉到Step 2.2。否則轉到Step 2.6。

Step 2.6：由式(7)計算得到每個屬性的初始劃分區間。

Step 3

Step 3.2：優先合并信息熵為0的相鄰區間，然后選擇重要程度最低的區間進行合并。

Step 3.3：計算合并后相容度的變化Δ=φ′-φ0，當Δ≥0，轉到Step 3.4。否則終止區間的合并，轉到Step 3.2。

Step 3.4：判斷是否還有相鄰區間需要處理，若沒有則轉到Step 4。否則轉到Step 3.2。

Step 4對最終形成的區間用整數或字符進行編碼，完成最終的離散化。

對基于層次聚類和相容度的數據離散化算法的四點說明：

(1)Step 2.3結合正域的計算判斷數據的一致性，考慮了條件屬性與類別屬性之間的關聯，使聚類更加合理。

(2)Step 3.2計算區間信息熵并按從小到大進行排序，以此度量區間的重要程度，這一步驟是對條件屬性集合同時進行比較，確保每個屬性得到一致處理，避免了對單個屬性過度離散化。

(3)為提高算法效率，Step 3.3采用了簡化的相容度差值計算。

(4)當區間的信息熵為0時，相應的類屬性完全一致，合并后不會影響數據的一致性。當出現多個區間信息熵一致的情形時，優先選擇類屬性一致性較高的區間。

3 實驗與對比分析

3.1 實驗設計

為驗證DHCC離散化方法的性能，選擇UCI機器學習數據庫中6個標準數據集進行實驗(裝備模擬訓練系統數據屬于涉密范圍)，分別為Heart disease、Movement、Vehicle、Artificial、Iris plant、Glass，包含不同的數據樣本、條件屬性和類別屬性數目，已被廣泛應用于數據挖掘領域。表1對這些數據集進行了簡要描述。選擇等寬(Equal-W)、等頻(Equal-F)、Chimerge、MDLP、CAIM離散化方法進行對比分析。

表1 實驗數據集描述

實驗所用計算機處理器為Core i7、內存8 G，操作系統Windows7，編程環境為Matlab2010、Python3.7。

離散化后的數據集簡化了信息的表示，減少了所需的存儲空間，符合知識水平的表示，使得學習的過程更加準確和快速。因此，主要使用以下三個指標來綜合衡量離散化方法的優劣。

(1)離散化后的區間總數。對于實際的離散化，最終形成的區間總數越小，離散化結果越簡潔、效果越好。

(2)離散化后的精度。指離散化后數據相比原始數據的一致性程度，離散后的信息損失越少，離散化方法的精度越高。這一指標通過對離散化后的數據運行分類方法，計算分類的準確率來具體體現。

(3)方法運行時間。方法耗時體現了方法運行效率，對于動態離散化過程而言尤為重要。

實驗中，首先對數據集分別運用6種離散化方法進行處理，記錄離散化后的區間總數和方法運行時間，然后對離散化后的數據集運用5折交叉驗證的方法，隨機選取80%的數據作為訓練集，20%的數據作為測試集，采用C4.5分類方法進行測試，得到分類的準確率，為消除誤差實驗重復5次，計算各指標的平均值作為最終評價標準。

3.2 實驗結果分析

3.2.1 離散化后的區間總數分析

由表2可知，DHCC方法離散后的平均區間總數最少，因為該方法的層次聚類部分能一次對所有屬性進行聚類處理，屬于全局離散化，同時結合正域的變化作為終止判斷條件，可以避免分別對單個屬性離散化所產生的不合理區間，平均排名得分1.4。Chimerge、MDLP離散化方法采用χ2統計量和信息熵作為區間劃分的依據，對單個屬性依次處理，屬于局部離散化，最終所得區間總數有所增加，且隨著設定的顯著性水平增加，會對屬性進行過度的離散化操作，產生大量的冗余區間。Equal-W、Equal-F方法通過經驗公式設定初始的離散區間數，隨著數據集的規模變大、屬性增多，離散區間數也顯著增加，平均排名得分為4.8、5.3。

表2 區間總數

3.2.2 離散精度分析

由表3可知，在測試的數據集中，DHCC方法的精度具有一定優勢，測試精度的平均排名1.5分，表明DHCC方法在層次聚類和區間合并過程中，考慮所有條件屬性、類別屬性之間的相關性，有效減少信息損失，同時運用類別屬性信息對相鄰區間的合并進行有監督指導，最大限度地保留原始數據的一致性。Equal-W、Equal-F離散化方法的精度相比較低，主要是因為這兩種方法都屬于無監督，不使用類別屬性信息，當數據分布不平衡時容易產生較差的區間，比如在Movement數據集中的測試精度只有47.5%和43.3%。Chimerge、MDLP方法屬于有監督離散化，精度相比有所較高，但在離散化的過程中每次只考慮一個屬性，忽視了屬性之間的相互影響，平均精度比DHCC方法低。CAIM方法僅考慮最大類屬性的樣本，忽視了其他類屬性的作用，使得在選擇分割點時易出現誤差，將具有不同分布的類別屬性樣本劃分至同一個區間，降低分類的測試精度。

表3 離散精度Table 3 Discretization accuracy

3.2.3 運行時間分析

由表4可知，在測試的6個數據集中，Equal-W、Equal-F方法的運行時間最少，因為這兩種方法在離散化時都不考慮類別屬性信息，依據數據分布和經驗公式進行區間劃分，沒有復雜的迭代計算過程。DHCC方法因為涉及層次聚類和相容度的計算、迭代合并操作，所需時間相對較長。Chimerge、MDLP、CAIM方法通過計算設定的離散化度量值，然后迭代進行合并、分割操作，在Artificial、Movement兩個數據集的運行時間增加明顯。

表4 運行時間

從實驗對比分析可以得出，DHCC離散化算法在離散化后的區間總數、精度方面相比其他5種離散化算法具有一定優勢，確保了離散化后的數據質量。

3.3 實例驗證

為驗證所提離散化方法的有效性，以一個實際例子進行說明。表5為利用某型裝備模擬訓練系統進行射擊訓練時所涉及的部分數據決策表，具體屬性包括軍銜、裝備操作等級、裝備訓練科目、裝備訓練次數、裝備訓練成績等。

表5的數據表既包含連續型數據，又包含離散型數據。為從中挖掘裝備訓練規則，根據文中所提出的數據離散化處理框架和DHCC算法，對表5的數據進行離散化處理，生成離散化編碼如表6所示。

表5 某型裝備模擬訓練系統數據決策表

表6 離散化編碼表

根據離散化編碼表對表5的數據進行離散化處理可得表7。

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

得到離散化后的數據后，采用經典的Apriori算法進行關聯規則挖掘，設定支持度最小值為15%，置信度最小值為70%，以裝備訓練成績作為關聯規則后件，最終得到如下規則(“∧”表示屬性取值條件同時滿足，“?”表示由前項可推出后項)。

(1)X13∧X14∧X24∧X25∧X36?Y15，獲得裝備操作等級三級以上的下士、中士在“穩像模式下原地對不動目標射擊”中獲評成績[90, 98]。通過了解該分隊擔負射擊教學保障任務，對士官的等級評定要求嚴、抓得緊，保證了三級以上射手的裝備訓練水平達到規定的標準，也有利于形成射手的梯次配備，促進整體戰斗力提升。

(2)X32∧X41?Y14∧Y15，表明“火控系統模式轉換”科目通過較少次數訓練后，評定分數位于[82, 89][90, 98]兩個區間。這與實際情況相符，“火控系統模式轉換”動作相對簡單，訓練對象能較快掌握要領，可適當減少訓練次數。

通過某型裝備模擬訓練系統數據實現DHCC算法在實際裝備訓練中的應用，挖掘了裝備訓練科目、裝備訓練成績等屬性之間的關聯，有助于提高裝備訓練效果。

4 結論

構建了裝備模擬訓練系統數據離散化總體框架，提出了一種基于層次聚類和相容度的數據離散化方法，并應用于某型裝備模擬訓練系統數據分析，得出如下主要結論。

(1)離散化總體框架滿足了裝備模擬系統數據混合型決策表的處理需求，規范了系統數據預處理流程。

(2)動態確定簇數的層次聚類考慮屬性相關性，實現了對各屬性的初始劃分，避免了人工指定閾值帶來的誤差。

(3)簡化相容度差值合并相鄰區間，能有效去除冗余劃分，獲得全局最優屬性區間集合。