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

魯文霞，馬盈倉(cāng)

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

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

魯文霞，馬盈倉(cāng)

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

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

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

0 引言

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

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

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

1 鄰域覆蓋粗糙集

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

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

定義2實(shí)值信息系統(tǒng)S=(U，A)，xi∈U，a∈A，xi的關(guān)于屬性a的e-鄰域?yàn)?/p>

注e(a)為誤差范圍.

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

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

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

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

2 實(shí)值信息系統(tǒng)中基于熵的約簡(jiǎn)

2.1 鄰域下的熵

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

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

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

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

證明由于

由鄰域的定義B?A，則

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

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

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

定義5實(shí)值信息系統(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實(shí)值信息系統(tǒng)S=(U，A)，xi∈U，B?A，任意屬性a∈A-B關(guān)于屬性集B中的重要性定義為

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

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

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

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

2.3 屬性重要性的約簡(jiǎn)算法

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

實(shí)值信息系統(tǒng)的核與約簡(jiǎn)算法：

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

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

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

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

(1)對(duì)每個(gè)屬性a∈A-C，計(jì)算sigC(a).

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

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

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

步驟1由于

表1 信息表

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

步驟2令C={a}，對(duì)屬性a2，a3∈A-C，計(jì)算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};約簡(jiǎn)為{a1，a2}或{a1，a3}.

3 結(jié)束語(yǔ)

本文在鄰域覆蓋粗糙集的定義下，將經(jīng)典粗糙集中的熵和屬性重要度推廣到實(shí)值信息系統(tǒng)中，給出了其在實(shí)值系統(tǒng)上的定義，并給出了實(shí)值信息系統(tǒng)在熵下的約簡(jiǎn)定理.在此基礎(chǔ)上，提出了一種基于熵的屬性重要度的實(shí)值信息系統(tǒng)上的屬性約簡(jiǎn)算法，并通過(guò)例子驗(yàn)證了該算法的有效性.今后將對(duì)實(shí)值決策系統(tǒng)在條件熵上的屬性約簡(jiǎn)進(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］.中國(guó)電機(jī)工程學(xué)報(bào)，2005，25(10)：159-165.

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

［5］劉清，劉少輝，鄭非.Rough邏輯及其在數(shù)據(jù)約簡(jiǎn)中的應(yīng)用［J］.軟件學(xué)報(bào)，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ù)值屬性約簡(jiǎn)［J］.軟件學(xué)報(bào)，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è)，梁春華.一種基于知識(shí)量的約簡(jiǎn)算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2007，28(11)：1968-1971.

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

［18］許晴媛，李進(jìn)金，張燕蘭.覆蓋決策信息系統(tǒng)的約簡(jiǎn)［J］.山東大學(xué)學(xué)報(bào)：理學(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

編輯、校對(duì)：武暉

2013-07-04

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

馬盈倉(cāng)(1972-)，男，陜西省合陽(yáng)縣人，西安工程大學(xué)教授，博士，主要研究領(lǐng)域?yàn)榇植诩碚摷皯?yīng)用、非經(jīng)典數(shù)理邏輯.E-mail：mayingcang@126.com