魯文霞，馬盈倉

(西安工程大學(xué)理學(xué)院，陜西西安710048)

實值信息系統(tǒng)上基于熵的屬性約簡

魯文霞，馬盈倉

(西安工程大學(xué)理學(xué)院，陜西西安710048)

研究實值系統(tǒng)中的知識獲取是粒計算研究的主要方向之一.為給出一種高效的知識獲取方法，文中基于鄰域粗糙集的原理，針對實值特點，在實值信息系統(tǒng)上給出熵和基于熵的屬性重要度的定義和約簡定理.同時研究其性質(zhì)，并給出了實值信息系統(tǒng)上基于熵的屬性重要度的約簡算法，對算法的性質(zhì)進(jìn)行了分析，通過實例驗證了該算法的有效性.

粗糙集理論;實值系統(tǒng);屬性約簡;熵

0 引言

粗糙集作為一種處理不協(xié)調(diào)、不確定與不完備數(shù)據(jù)的新的數(shù)學(xué)理論［1-2］，最初是由波蘭科學(xué)家Pawlak于1982年提出的.近幾年來，它已經(jīng)成功地應(yīng)用于機(jī)器學(xué)習(xí)、模式識別、決策支持、數(shù)據(jù)挖掘、過程控制等領(lǐng)域［3-5］.

然而經(jīng)典粗糙集理論是基于等價關(guān)系的，分類過于苛刻，它適用于處理離散型變量，對于現(xiàn)實中廣泛存在的數(shù)值型數(shù)據(jù)卻不能直接處理.在金融、醫(yī)療、科研和工程領(lǐng)域，實值型變量無處不在，如：配電系統(tǒng)診斷的電流信號［6］等.為了解決這種問題，人們在經(jīng)典粗糙集的基礎(chǔ)上進(jìn)行了許多有意義的推廣，引入了很多新的模型，如模糊粗糙集模型［7-10］、鄰域系統(tǒng)粗糙集模型［11］和鄰域關(guān)系模型［12］.其中，在鄰域模型方面，Hu提出基于鄰域?；痛植诒平臄?shù)值屬性約簡［12］，Yao［13］提出1-step鄰域，Wu［14］提出并研究了k-step鄰域信息系統(tǒng)的性質(zhì)，以及帶有誤差范圍和測試代價的數(shù)據(jù)屬性約簡［15］等.可以看出，不同的模型是基于不同的粒化和逼近機(jī)制來處理現(xiàn)實中實值型數(shù)據(jù).

粗糙集理論中的約簡一直是核心問題.合理的屬性約簡可以起到非常有效的作用，對于知識獲取、決策分析等起到指導(dǎo)作用.一般地講，一個決策系統(tǒng)的屬性約簡往往不是惟一的，理想中人們期望找到?jīng)Q策系統(tǒng)中的最小約簡，但是找到最小約簡是一個NP-hard的問題，所以在現(xiàn)實生活中人們解決這一類問題一般采取啟發(fā)式算法來求出最優(yōu)或次最優(yōu)約簡.在經(jīng)典粗糙集模型上，借助熵及條件熵作為度量可以對屬性進(jìn)行約簡［16］.在實值系統(tǒng)上也有人在這方面作了文章，如：協(xié)調(diào)覆蓋決策系統(tǒng)下基于條件信息熵的屬性約簡［17］，覆蓋決策信息系統(tǒng)的約簡［18］，模糊概率近似空間及其信息度量［19］等.本文在經(jīng)典粗糙集熵的定義和鄰域粗糙集模型研究的基礎(chǔ)上，提出了實值信息系統(tǒng)上的熵和基于熵的屬性重要度的定義，它是等價關(guān)系上一個推廣，并研究了其性質(zhì).在實值信息系統(tǒng)上，給出了在熵定義下的約簡定理，提出了基于熵的屬性重要度約簡算法，同時對算法的性質(zhì)進(jìn)行了理論分析，揭示了屬性重要度作為啟發(fā)式算法的合理性;最后通過實例，表明該算法是有效的.

1 鄰域覆蓋粗糙集

定義1［11］給定一個n維的實數(shù)空間Ω，ΔRN×RN→R，稱Δ是RN上的一個度量，如果Δ滿足：

則稱〈Ω，Δ〉為度量空間.歐式距離是實數(shù)空間上常用的度量.

定義2實值信息系統(tǒng)S=(U，A)，xi∈U，a∈A，xi的關(guān)于屬性a的e-鄰域為

注e(a)為誤差范圍.

根據(jù)度量的性質(zhì)，有如下結(jié)論：

不難看出，鄰域粒子族{ea(xi)|i=1，2，…，n}構(gòu)成了U的一個覆蓋.

進(jìn)一步的，由鄰域的定義，可以得到

性質(zhì)1(1)eB1∪B2=eB1∩eB2，(2)?xi∈U，e1≤e2，則e1(xi)?e2(xi).

2 實值信息系統(tǒng)中基于熵的約簡

2.1 鄰域下的熵

定義3實值信息系統(tǒng)S=(U，A)，xi∈U，B?A，則屬性集B具有的信息熵定義為

其中|U|表示論域中元素的個數(shù)，|eB(xi)|/|U|表示xi的B鄰域在U中的概率.

注此定義是經(jīng)典粗糙集中熵的一種推廣，可以退化為等價關(guān)系中定義的熵.

定理1實值信息系統(tǒng)S=(U，A)，xi∈U，B?A，則H(B)≤H(A).

證明由于

由鄰域的定義B?A，則

2.2 鄰域下的屬性重要性的度量

定義4實值信息系統(tǒng)S=(U，A)，xi∈U，a∈A，屬性a在A中的重要性定義為

特別當(dāng)A={a}時，用sig(a)表示sig?(a)：

定義5實值信息系統(tǒng)S=(U，A)，a∈A，若H(A)≠H(A-{a})，則稱屬性a在A中是必要的，否則就是不必要的.

性質(zhì)2(1)0≤sigA-{a}(a)≤1;(2)屬性a∈A在A中是必要的充要條件是sigA-{a}(a)＞0;(3) CORE(A)={a∈A|sigA-{a}(a)＞0}.

證明(1)由定理1的結(jié)論可知，0≤sigA-{a}(a)≤1.

(2)充分性：若a∈A在A中是必要的，則H(A)≠H(A-{a}).而H(A)≥H(A-{a})，故sigA-{a}(a)＞0.

必要性：若sigA-{a}(a)＞0，即H(A)≠H(A-{a})，故a∈A在A中是必要的.

(3)由性質(zhì)(2)可知.

定義6實值信息系統(tǒng)S=(U，A)，xi∈U，B?A，任意屬性a∈A-B關(guān)于屬性集B中的重要性定義為

通過信息系統(tǒng)屬性約簡的概念和以上結(jié)論，可以容易地得到如下定理，它通過熵來刻畫信息系統(tǒng)約簡.

定理2實值信息系統(tǒng)S=(U，A)，B?A，如果：(1)H(A)=H(B)，(2)?a∈B，有sigB-{a}(a)＞0，則B為A的一個約簡.

證明在實值信息系統(tǒng)中B?A為A的一個約簡的充分必要條件為eA(xi)=eB(xi)且B是獨(dú)立的.

由定理1知，當(dāng)B?A時，eA(xi)=eB(xi)成立的充分必要條件是H(A)=H(B).B是獨(dú)立的成立的充分必要條件是?a∈B是必要的，則H(B)≠H(B-{a})，即sigB-{a}(a)＞0.故定理成立.

2.3 屬性重要性的約簡算法

由于核屬性是所有約簡的交集，因此，在求最小約簡時可以把核作為起點，在性質(zhì)2中可以很容易地求出屬性集的核.再根據(jù)定義4中定義的屬性重要度作為啟發(fā)式函數(shù)，選擇重要度最大的屬性添加到核中去，直到熵等于整個條件屬性的熵為止.

實值信息系統(tǒng)的核與約簡算法：

輸入：實值信息系統(tǒng)S=(U，A)，其中U為論域，A為條件屬性.

輸出：該信息系統(tǒng)的核和約簡.

步驟1求CORE(A)，計算每個屬性a∈A在A中是否必要，且令CORE(A)=?.若sigA-{a}(a)＞0，則CORE(A)：=CORE(A)∪{a}，最后得到的CORE(A)為屬性集A的核;若H(A)=H(CORE(A))則終止(此時CORE(A)為A的最小約簡);否則，執(zhí)行步驟2.

步驟2令C=CORE(A)，對屬性集A-C重復(fù)執(zhí)行：當(dāng)C=?時，計算每一個屬性a∈A的熵H({a})，若H({a})=H(A)，則終止(此時{a}為A的最小約簡);當(dāng)C≠?時，轉(zhuǎn)以下步驟：

(1)對每個屬性a∈A-C，計算sigC(a).

(3)若H(C)=H(A)，則終止(此時C為A的最小約簡);否則，轉(zhuǎn)(1).

以上是依據(jù)熵的屬性重要度求屬性約簡的算法步驟，該算法是有效的，下面通過例子進(jìn)行分析.

例1實值信息系統(tǒng)S=(U，A)，如表1，其中U={x1，x2，x3，x4，x5}，A={a1，a2，a3}，求其信息表的核與約簡.其中，Δ(x1，x2)=|a(xi)-a(xj)|.

步驟1由于

表1 信息表

故A中必要元素為a1，即CORE(A)={a1}.

步驟2令C={a}，對屬性a2，a3∈A-C，計算sigC(a2)，sigC(a3).

若選擇屬性a2，C：=C∪{a2}，則H(C)=H(A)，終止.

若選擇屬性a3，C：=C∪{a3}，則H(C)=H(A)，終止.

所給算法求出信息系統(tǒng)的核CORE(A)={a1};約簡為{a1，a2}或{a1，a3}.

3 結(jié)束語

本文在鄰域覆蓋粗糙集的定義下，將經(jīng)典粗糙集中的熵和屬性重要度推廣到實值信息系統(tǒng)中，給出了其在實值系統(tǒng)上的定義，并給出了實值信息系統(tǒng)在熵下的約簡定理.在此基礎(chǔ)上，提出了一種基于熵的屬性重要度的實值信息系統(tǒng)上的屬性約簡算法，并通過例子驗證了該算法的有效性.今后將對實值決策系統(tǒng)在條件熵上的屬性約簡進(jìn)行研究，并將其應(yīng)用到UCI數(shù)據(jù)中，與其他算法進(jìn)行比較.

［1］PAWLAK Zdzislaw.Rough sets［J］.International Journal of Computer and Information Sciences，1982，11(5)：341-356.

［2］張文修，吳偉志，梁吉業(yè)，等.粗糙集理論與方法［M］.北京：科學(xué)出版社，2005：1-15.

［3］朱永利，吳立增，李雪玉.貝葉斯分類器與粗糙集相結(jié)合的變壓器綜合故障［J］.中國電機(jī)工程學(xué)報，2005，25(10)：159-165.

［4］孫秋野，張化光.基于粗糙集的配電系統(tǒng)連續(xù)信號故障診斷方法［J］.中國電機(jī)工程學(xué)報，2006，26(11)：156-161.

［5］劉清，劉少輝，鄭非.Rough邏輯及其在數(shù)據(jù)約簡中的應(yīng)用［J］.軟件學(xué)報，2001，12(3)：415-419.

［6］SNN Q Y，ZHANG H G.Fault diagnose algorithm of distribution system by continuous signals based on rough sets［J］.The Chinese Society for Electrical Engineering，2006，26(11)：156-161.

［7］羅承忠.模糊集引論［M］.北京：北京師范大學(xué)出版社，2007：45-48.

［8］高新波.模糊聚類分析及其應(yīng)用［M］.西安：西安電子科技大學(xué)出版社，2004：44-45.

［9］SLAVKA B.Approximation of fuzzy concepts in decision making［J］.Fuzzy Sets and Systems，1997，85(2)：23-29.

［10］RADZIKOWSKA M，KERRE E E.Comparative study of fuzzy rough sets［J］.Fuzzy Sets and System，2002，126(2)：29-34.

［11］HU Qinghua，ZHANG Lei，CHEN Degang.Gaussian kernel based fuzzy rough sets：Model，measures and applications［J］.International Journal of Approximate Reasoning，2010，51(1)：453-471.

［12］胡清華，于達(dá)仁，謝宗霞.基于鄰域?；痛植诒平臄?shù)值屬性約簡［J］.軟件學(xué)報，2008，19(3)：640-649.

［13］YAO Y.Y.Relational interpretation of neighborhood operators and rough set approximation operators［J］.Information Science，1998，111(1)：239-259.

［14］WU Weizhi，ZHANG Wenxiu.Neighborhood operator systems and approximations［J］.Information Science，2002，144(1-4)： 201-217.

［15］MIN Fan，ZHU William.Attribute reduction of data with error ranges and test costs［J］.Information Science，2012，18(4)：3-14.

［16］張海軍，梁吉業(yè)，梁春華.一種基于知識量的約簡算法［J］.小型微型計算機(jī)系統(tǒng)，2007，28(11)：1968-1971.

［17］夏秀云，秦克云，田浩.協(xié)調(diào)覆蓋決策系統(tǒng)下基于條件信息熵的屬性約簡［J］.河南大學(xué)學(xué)報：自然科學(xué)版，2010，40 (4)：406-410.

［18］許晴媛，李進(jìn)金，張燕蘭.覆蓋決策信息系統(tǒng)的約簡［J］.山東大學(xué)學(xué)報：理學(xué)版，2010，45(1)：89-93.

［19］HU Qinghua，YU Daren，XIE Zongxia，et al.Fuzzy probabilistic approximation spaces and their information measures［J］.IEEE Transactions on Fuzzy Systems，2006，14(2)：191-201.

Attribute reduction of the real value information system based on entropy

LU Wen-xia，MA Ying-cang

(School of Science，Xi'an Polytechnic University，Xi'an 710048，China)

Research knowledge acquisition of the real value system is one of the main directions of the granular computing research.For giving an efficient knowledge acquisition method，based on the neighborhood of rough set theory and according to the characteristics of the real value，the definition of the entropy and attribute importance based on the entropy and reduction theorem in the real value information system are given，and its properties are studied.Moreover，the algorithm of attribute reduction based on attribute importance in the real value information system is proposed.Lastly，the properties of algorithm are discussed and the effectiveness of the algorithm are showed by an example.

rough set theory;real system;attribute reduction;entropy

TP 18;B 815

A

1674-649X(2014)01-0128-05

編輯、校對：武暉

2013-07-04

國家自然科學(xué)基金資助項目(61170128);陜西省教育廳專項科研計劃項目(12JK0878);西安工程大學(xué)研究生創(chuàng)新基金資助(chx131114)

馬盈倉(1972-)，男，陜西省合陽縣人，西安工程大學(xué)教授，博士，主要研究領(lǐng)域為粗糙集理論及應(yīng)用、非經(jīng)典數(shù)理邏輯.E-mail：mayingcang@126.com