再生分辨矩陣與決策熵的不完備決策系統(tǒng)屬性約簡(jiǎn)

閻桂林，徐廷學(xué)，袁有宏，張眾

（1.海軍航空工程學(xué)院，山東煙臺(tái)264001；2.解放軍92514部隊(duì)，山東煙臺(tái)264001；3.海軍駐蘭州地區(qū)軍代室，蘭州730070）

再生分辨矩陣與決策熵的不完備決策系統(tǒng)屬性約簡(jiǎn)

閻桂林1，2，徐廷學(xué)1，袁有宏3，張眾1

（1.海軍航空工程學(xué)院，山東煙臺(tái)264001；2.解放軍92514部隊(duì)，山東煙臺(tái)264001；3.海軍駐蘭州地區(qū)軍代室，蘭州730070）

為了有效地解決不完備決策系統(tǒng)的屬性約簡(jiǎn)問題，提高屬性約簡(jiǎn)的效率，提出了基于再生分辨矩陣與決策熵的不完備屬性約簡(jiǎn)算法。該算法利用基于容差關(guān)系的分辨矩陣來計(jì)算相對(duì)核，通過再生分辨矩陣計(jì)算再生集和再生集屬性來縮小加入約簡(jiǎn)集的條件屬性選擇范圍，以再生集屬性的分辨度和決策熵為依據(jù)，選擇加入約簡(jiǎn)集的條件屬性，并通過實(shí)例進(jìn)行驗(yàn)證分析。結(jié)果表明，該算法適用于協(xié)調(diào)不完備決策系統(tǒng)與不協(xié)調(diào)不完備決策系統(tǒng)，能夠有效地降低時(shí)間復(fù)雜度，并得到最優(yōu)屬性約簡(jiǎn)。

再生分辨矩陣，決策熵，不完備決策系統(tǒng)，屬性約簡(jiǎn)

0　引言

屬性約簡(jiǎn)一直以來就是粗糙集理論研究的核心內(nèi)容之一［1］。關(guān)于完備決策系統(tǒng)屬性約簡(jiǎn)方法的研究已經(jīng)取得了許多成果，然而由于各種原因，人們獲得的信息往往是不完備的，因此，不完備決策系統(tǒng)屬性約簡(jiǎn)方法的研究更加具有實(shí)際意義，也受到了越來越多的關(guān)注。文獻(xiàn)［2］提出了基于屬性重要度的不完備信息系統(tǒng)屬性約簡(jiǎn)算法；文獻(xiàn)［3］利用容差關(guān)系給出相似矩陣，通過相似矩陣定義屬性重要度來進(jìn)行屬性約簡(jiǎn)；文獻(xiàn)［4］提出了通過容差關(guān)系下的可辨識(shí)矩陣的核屬性來簡(jiǎn)化可分辨矩陣，然后再采用可辨識(shí)函數(shù)求屬性約簡(jiǎn)；文獻(xiàn)［5-7］研究了基于信息熵和條件熵的屬性約簡(jiǎn)方法；文獻(xiàn)［8］提出了一種考慮完備決策表協(xié)調(diào)性的基于決策熵的屬性約簡(jiǎn)算法；文獻(xiàn)［9］研究了容差關(guān)系的決策熵，提出了基于決策熵的不完備信息系統(tǒng)屬性約簡(jiǎn)方法。

本文在上述算法的基礎(chǔ)上，提出了基于再生分辨矩陣與決策熵的不完備屬性約簡(jiǎn)算法。該算法通過再生分辨矩陣和再生集來降低時(shí)間復(fù)雜度，以決策熵來更好地反映決策表的決策能力。實(shí)例表明，該算法是可行的，并且能更加快速地得到最優(yōu)屬性約簡(jiǎn)。

1　相關(guān)概念

定義1不完備決策系統(tǒng)

定義2容差關(guān)系與不完備決策系統(tǒng)的協(xié)調(diào)性

對(duì)于不完備決策系統(tǒng)S=（U，C∪D，V，f），對(duì)于具有缺失屬性值的屬性集，容差關(guān)系T（B）定義如下［4］：

定義3容差關(guān)系分辨矩陣［4］

其中，i，j=1，2，…，n，k=1，2，…，m。容差關(guān)系分辨矩陣是關(guān)于對(duì)角線對(duì)稱的矩陣，因此，當(dāng)定義i＞j，則只需計(jì)算上三角或下三角矩陣。

定義4相對(duì)核

給定容差關(guān)系分辨矩陣DM，?Cij∈DM，ck∈Cij，若card（Cij）=1，則該元素項(xiàng)對(duì)應(yīng)的兩對(duì)象只能通過屬性ck來分辨，屬性ck相對(duì)于決策屬性是必要的，因此，Cij中所包含的屬性ck就稱為核屬性。那么由這些核屬性組成的集合稱為不完備決策系統(tǒng)的相對(duì)核COREC（D），記為

定義5再生分辨矩陣［11］

設(shè)不完備決策系統(tǒng)的條件屬性C=｛c1，c2，…，ck｝，R表示不完備決策系統(tǒng)的約簡(jiǎn)集，對(duì)于任意ck∈R，有

則稱RDM（R）為再生分辨矩陣，將限制容差關(guān)系分辨矩陣DM中含有約簡(jiǎn)集內(nèi)條件屬性的元素項(xiàng)置空的過程稱為分辨矩陣的再生。

定義6再生集與再生集屬性分辨度

若再生分辨矩陣存在其他非空元素項(xiàng)，顯然這些元素項(xiàng)不包含約簡(jiǎn)集R內(nèi)的任意條件屬性，同時(shí)它們對(duì)于區(qū)別相應(yīng)的兩對(duì)象所必需的，這些項(xiàng)中屬性數(shù)量最少的元素稱為再生集RS，再生集定義如下

性質(zhì)1：再生集必須包含兩個(gè)或兩個(gè)以上屬性，若僅包含單一屬性，則只能是核屬性。

性質(zhì)2：若再生分辨矩陣仍存在再生集，那么該再生分辨矩陣至少能再生一次。

若存在條件屬性ck∈RS，則條件屬性ck稱為再生集屬性，則其分辨度為

定義7基于容差關(guān)系的決策熵及其屬性重要度

由于文獻(xiàn)［9］提出的決策熵不具單調(diào)性，結(jié)合文獻(xiàn)［10］對(duì)決策熵單調(diào)性的研究，本文給出一種改進(jìn)的決策熵定義。對(duì)于不完備決策系統(tǒng)S=（U，C∪ D，V，f），，條件屬性集合B在U上基于容差關(guān)系導(dǎo)出的覆蓋為：TB（x）=｛X1，X2，…，Xn｝，決策屬性D在U上基于容差關(guān)系導(dǎo)出的覆蓋為：TD（x）=｛Y1，Y2，…，Ym｝，則改進(jìn)的決策熵定義為：

（1）E（B→D）≤E（C→D）；

（2）對(duì)于?ck∈B，有E（B-｛ck｝→D）＞E（B→D）。

2　基于再生分辨矩陣與決策熵的屬性約簡(jiǎn)

2.1算法描述

輸入：不完備決策系統(tǒng)S=（U，C∪D，V，f）；

輸出：S的屬性約簡(jiǎn)集R。

步驟1計(jì)算容差關(guān)系分辨矩陣DM和相對(duì)核CoreC（D），令屬性約簡(jiǎn)集R=CoreC（D）；

步驟2若容差關(guān)系分辨矩陣DM中的元素項(xiàng)Cij滿足條件R∩Cij≠?，則將這些元素項(xiàng)置空，得到再生分辨矩陣RDM（R），若RDM（R）的元素項(xiàng)都為空，則算法結(jié)束，否則轉(zhuǎn)到步驟3；

步驟3計(jì)算再生分辨矩陣RDM（R）的再生集RS及再生集屬性ck的分辨度，若僅存在某個(gè)再生集屬性ck的分辨度λ=1，則R=R∪ck，算法結(jié)束；若存在多個(gè)再生集屬性ck的分辨度λ=1時(shí)，選擇滿足約簡(jiǎn)集條件E（R∪ck→D）≤E（C→D）的再生集屬性ck加入約簡(jiǎn)集，令R=R∪ck，算法結(jié)束，否則對(duì)每個(gè)再生集屬性ck∈RS，計(jì)算決策熵E（R∪ck→D）；

步驟4選擇使E（R∪ck→D）最小的再生集屬性ck，若同時(shí)有多個(gè)屬性達(dá)到最小值，則選取再生集所含屬性中分辨度最大的屬性ck，令R=R∪ck，轉(zhuǎn)到步驟2。

2.2復(fù)雜度分析

3　實(shí)例分析

實(shí)例1利用文獻(xiàn)數(shù)據(jù)表，選取航空發(fā)動(dòng)機(jī)穩(wěn)態(tài)工作過程9個(gè)參數(shù)表征發(fā)動(dòng)機(jī)性能狀況，分別為進(jìn)口溫度T1，渦輪后燃?xì)饪倻豑4，低壓轉(zhuǎn)子轉(zhuǎn)速N1，高壓轉(zhuǎn)子轉(zhuǎn)速N2，風(fēng)扇進(jìn)口導(dǎo)向器葉片轉(zhuǎn)角α1，高壓氣機(jī)靜子葉片轉(zhuǎn)角α2，尾噴口指示值φPC，滑油壓力PM，發(fā)動(dòng)機(jī)機(jī)匣振動(dòng)值r和發(fā)動(dòng)機(jī)狀態(tài)d。航空發(fā)動(dòng)機(jī)在定檢Б加力狀態(tài)下決策系統(tǒng)如表1所示，表中“1”、“2”和“3”表示是連續(xù)值歸一化后不同的取值區(qū)間，決策屬性d取值“0”和“1”，分別表示發(fā)動(dòng)機(jī)故障和正常狀態(tài)。，故定檢Б加力狀態(tài)下的不完備決策系統(tǒng)是協(xié)調(diào)的。利用容差關(guān)系分辨矩陣求出核屬性T4，令R=CoreC（D）=T4。計(jì)算再生分辨矩陣RDM（R），該矩陣中包含非空元素項(xiàng)，故計(jì)算得再生集RS=｛α1，φPC｝，由于α1和φPC的分辨度都不為1，故計(jì)算E（R∪α1→D）=0.793 8，E（R∪φPC→D）=0.75，故R=R∪φPC=｛T4，φPC｝，刪除包含屬性φPC的矩陣元素后仍包含非空元素項(xiàng)，計(jì)算再生集RS=｛T1，N1，r｝，

表1　定檢Б加力狀態(tài)下的不完備決策表

文獻(xiàn)［7］的算法在選擇加入屬性約簡(jiǎn)集的條件屬性時(shí)，需要計(jì)算除現(xiàn)有約簡(jiǎn)集屬性外所有的條件屬性的粗糙信息熵，而本文算法在每次選擇加入約簡(jiǎn)集的條件屬性時(shí)，首先通過計(jì)算再生集和再生集屬性來縮小條件屬性的選擇范圍，使得每次加入約簡(jiǎn)集的條件屬性都來自再生集，由于再生集屬性的個(gè)數(shù)一般小于除約簡(jiǎn)集外剩余條件屬性的個(gè)數(shù)，因此，本文算法比文獻(xiàn)［7］的算法能更加快速地找到最優(yōu)屬性約簡(jiǎn)，且能得到正確的最優(yōu)屬性約簡(jiǎn)和診斷規(guī)則。

實(shí)例2為驗(yàn)證本文算法也適用于不協(xié)調(diào)的不完備決策系統(tǒng)，以文獻(xiàn)［12］的不完備決策表（如表2所示）進(jìn)行分析說明。

表2　不完備決策表

4　結(jié)論

屬性約簡(jiǎn)是在盡量保留決策表信息的前提下，刪除冗余條件屬性，選擇較少的條件屬性來表示條件屬性與決策屬性的關(guān)系的過程。本文在考慮了不完備決策系統(tǒng)的協(xié)調(diào)性的前提下，研究了不完備決策系統(tǒng)的屬性約簡(jiǎn)算法。該算法通過基于容差關(guān)系下的分辨矩陣得到相對(duì)核，并引入了再生分辨矩陣與再生集，通過再生集屬性的分辨度和決策熵來選擇條件屬性，有效地降低算法的時(shí)間復(fù)雜度。最后通過實(shí)例驗(yàn)證了算法的可行性和有效性。

［1］鄂旭，邵良杉，周津，等.一種新的不完備信息系統(tǒng)屬性約簡(jiǎn)算法［J］.重慶郵電大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，22（5）：648-651.

［2］ZHONG N，DONG J Z，OHSUGA S.Using rough sets with heuristics for feature selection［J］.Journalof intelligentinformation systems，2001，16（2）：199-214.

［3］陳貞.不完備信息系統(tǒng)中基于屬性重要度的約簡(jiǎn)算法［J］.長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，33（4）：456-459.

［4］顏家凱，范敏，劉文奇，等.基于容差關(guān)系的不完備信息系統(tǒng)的屬性約簡(jiǎn)［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2014，24（1）：102-104.

［5］GEDIGAG D I.Uncertaintymeasures of rough setprediction［J］.Artificial Intelligence，1998，106（1）：109-137.

［6］騰書華，周石琳，孫即祥，等.基于條件熵的不完備信息系統(tǒng)屬性約簡(jiǎn)算法［J］.國(guó)防科技大學(xué)學(xué)報(bào)，2010，32（1）：90-94.

［7］陳利安，肖明清，趙鑫.基于粗糙集與信息熵的不完備測(cè)試信息條件下故障診斷［J］.振動(dòng)與沖擊，2012，31（22）：24-28.

［8］徐久林，孫林.一種新的基于決策熵的決策表約簡(jiǎn)方法［J］.重慶郵電大學(xué)學(xué)報(bào)，2009，21（4）：479-483.

［9］胡峰，陳曦，王小燕.基于決策熵的不完備信息系統(tǒng)的知識(shí)約簡(jiǎn)方法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（1）：289-292.

［10］徐章艷，宋威，楊炳儒，等.關(guān)于“兩種新的決策表屬性約簡(jiǎn)概念”的注記［J］.小型微型計(jì)算機(jī)系統(tǒng)，2007，28（9）：1686-1689.

［11］張錚.不完備不協(xié)調(diào)條件下的設(shè)備智能故障診斷［D］.武漢：華中科技大學(xué)，2006.

［12］王婷，徐章艷，陳宇文，等.基于不完備決策表的正區(qū)域?qū)傩约s簡(jiǎn)的壓縮差別矩陣方法［J］.計(jì)算機(jī)科學(xué)，2014，41（6）：377-382.

AttributesReduction Based on RegenerativeDiscernibility M atrix and Decision Entropy in Incom p leteDecision System

YANGui-lin1，2，XU Ting-xue1，YUAN You-hong3，ZHANG Zhong1
（1.Naval Aeronautical and Astronautical University，Yantai264001，China；2.Unit92514 of PLA，Yantai264001，China；3.PLA Presentation Office in Lanzhou District，Lanzhou 730070，China）

In order to effectively solve the problem of attributes reduction in incomplete decision system and improve the efficiency of attribute reduction，attribute reduction algorithm based on regenerative discernibility matrix and decision entropy is proposed in incomplete decision system.The algorithm calculates relative core with the dicernibility matrix based on tolerance relation，narrowes the range of condition attribute which join reduction sets by using regenerative discernibilty matrix to calculate regenerative set and its attributes，selectes condition attribute to join reduction sets on the basis of the resolution of regenerative set attributes and decision entropy，and verifies and analysises by an example.Results show that the algorithm is suitable for the coordination and uncoordinated incomplete decision system，can effectively reduce the time complexity and get the optimal attribute reduction.

regenerative discernibilitymatrix；decision entropy；incomplete decision system；attribute reduction

TP391

A

1002-0640（2016）09-0173-04

2015-07-05

2015-08-07

閻桂林（1986-），男，廣西桂林人，碩士研究生。研究方向：武器裝備綜合保障理論與技術(shù)。