基于聚類思想的加權(quán)條件熵及屬性約簡(jiǎn)

范會(huì)濤， 馮 濤

(河北科技大學(xué) 理學(xué)院 河北 石家莊 050018)

0 引言

粗糙集理論是20世紀(jì)80年代提出的一種研究不完整、不確定知識(shí)和數(shù)據(jù)的表達(dá)、學(xué)習(xí)、歸納的理論方法[1].由于粗糙集理論無(wú)需提供問(wèn)題所需處理的數(shù)據(jù)集合以外的任何先驗(yàn)信息，可充分體現(xiàn)數(shù)據(jù)的客觀性.因此，粗糙集理論被廣泛應(yīng)用于數(shù)據(jù)挖掘、模式識(shí)別、人工智能等領(lǐng)域[2-3].隨著現(xiàn)實(shí)世界中大量應(yīng)用數(shù)據(jù)在結(jié)構(gòu)和形式上日益復(fù)雜化和多樣化，基于劃分和等價(jià)關(guān)系的經(jīng)典粗糙集模型已經(jīng)很難滿足大量現(xiàn)實(shí)問(wèn)題的實(shí)際需要，于是有些學(xué)者將論域的劃分?jǐn)U展為覆蓋，將等價(jià)關(guān)系擴(kuò)展為非等價(jià)關(guān)系，提出了一些新的粗糙集模型.

粗糙集利用信息粒對(duì)數(shù)據(jù)集合的近似，描述對(duì)象之間的不確定關(guān)系.而信息?；^(guò)程在很大程度上取決于對(duì)象之間的關(guān)系，既可以采用基于等價(jià)關(guān)系、相似關(guān)系、鄰域關(guān)系的方法對(duì)信息進(jìn)行?；部梢岳镁垲惙治龅姆椒▽?duì)信息進(jìn)行?；?，由聚類分析得到的相似類可視為信息粒.在聚類分析的粒化方面，文獻(xiàn)[4]提出了一種基于數(shù)據(jù)聚類的信息粒化方法，文獻(xiàn)[5]提出了基于聚類的數(shù)值數(shù)據(jù)信息粒化方法.因此，可以利用聚類分析的?；Y(jié)果與粗糙集理論相結(jié)合進(jìn)行知識(shí)約簡(jiǎn).

屬性約簡(jiǎn)是一種刪除不相關(guān)和冗余屬性的降維方法.基于信息熵、正域、可辨識(shí)矩陣、決策成本和知識(shí)粒度等已提出了許多啟發(fā)式屬性約簡(jiǎn)算法[6]，文獻(xiàn)[7-8]分別提出了基于近似決策熵、強(qiáng)化正域的屬性約簡(jiǎn)方法，文獻(xiàn)[9]提出了一種最小測(cè)試代價(jià)約簡(jiǎn)的改進(jìn)算法，文獻(xiàn)[10]提出了基于貼近度的協(xié)調(diào)序決策系統(tǒng)屬性約簡(jiǎn)算法，文獻(xiàn)[11]提出了基于α信息熵的模糊粗糙屬性約簡(jiǎn)方法.然而這些方法都把對(duì)象平等對(duì)待，但是現(xiàn)實(shí)生活中對(duì)象的權(quán)重往往都不相同.文獻(xiàn)[12]提出了基于代價(jià)敏感的對(duì)象權(quán)重確定方法，并將該權(quán)重用于粗糙集的約簡(jiǎn)之中，但是該權(quán)重確定方法過(guò)分依賴專家，使得權(quán)重的確定受到較大的主觀因素的影響.本文結(jié)合粗糙集理論與聚類分析的方法，給出了一種新的對(duì)象權(quán)重確定方法與加權(quán)熵的定義方式，并提出一種相容關(guān)系下的屬性約簡(jiǎn)算法.

1 預(yù)備知識(shí)

首先，在給出新的約簡(jiǎn)算法之前先回顧一下關(guān)于粗糙集和熵的相關(guān)知識(shí)和已有結(jié)論.

信息熵是粗糙集的一種不確定性度量，度量了信息系統(tǒng)提供的平均信息量的大小.經(jīng)典粗糙集中信息熵和條件信息熵的定義如下.

條件信息熵度量了兩個(gè)屬性集之間的依賴程度，即表示知識(shí)Φ從知識(shí)Ψ中所獲得的信息量.

若將余弦相似度應(yīng)用于信息系統(tǒng)的對(duì)象中，由于信息系統(tǒng)中的屬性值往往都是正數(shù)，若信息系統(tǒng)出現(xiàn)負(fù)值時(shí)，利用文獻(xiàn)[15]中的公式a′=(a-amin)/(amax-amin)對(duì)數(shù)據(jù)進(jìn)行模糊化處理，將屬性值歸一化為[0,1]區(qū)間上的值后再對(duì)對(duì)象求余弦相似度.因此，余弦相似度在信息系統(tǒng)中有如下性質(zhì).

性質(zhì)1設(shè)S=(U,C∪D,V,f)是一個(gè)信息系統(tǒng)，M和N分別表示對(duì)象xi和xj在屬性集C∪D上的屬性值構(gòu)成的向量，0表示零向量，則對(duì)象xi和xj的余弦相似度cos′()滿足以下性質(zhì)：

(1) 0≤cos′(M,N)≤1; (2) cos′(M,M)=1;

(3) cos′(0,N)=0，其中N≠0; (4) cos′(M,N)=cos′(N,M).

定義5[2]設(shè)S=(U,C∪D,V,f)是一個(gè)決策信息系統(tǒng)，U為非空有限論域，C為條件屬性集，D為決策屬性集.記RC={(xi,xj):fl(xi)=fl(xj)(al∈C)}，RD={(xi,xj):fd(xi)=fd(xj)(ad∈D)}，若RC?RD，則稱(U,C∪D,V,f)為協(xié)調(diào)決策信息系統(tǒng)，否則稱(U,C∪D,V,f)為不協(xié)調(diào)決策信息系統(tǒng).

2 一種基于聚類思想的相容關(guān)系

經(jīng)典粗糙集中的關(guān)系都是等價(jià)關(guān)系，但是現(xiàn)實(shí)生活中的關(guān)系往往都是非等價(jià)關(guān)系.因此，結(jié)合聚類思想給出一種新的相容關(guān)系，并利用這種相容關(guān)系構(gòu)造信息粒.在聚類分析中，余弦相似度常常用于衡量?jī)蓚€(gè)個(gè)體間差異的大小.余弦相似度利用余弦值表示向量的相似程度，兩個(gè)向量的余弦值越接近1，則兩個(gè)向量越相似.余弦值等于1，則兩個(gè)向量相等，可以用聚類分析中的這種想法去構(gòu)造信息系統(tǒng)中的相似類.但是在粗糙集中不僅要度量?jī)蓚€(gè)對(duì)象屬性值構(gòu)成的向量的夾角，還要度量它們的模.顯然，余弦相似度無(wú)法滿足度量向量模的要求.例如設(shè)對(duì)象x1和x2的屬性值構(gòu)成的向量分別為M=(2，4)和N=(3，6)，可得M和N的余弦相似度為1，即x1和x2歸為一類，但是在粗糙集中，這樣的結(jié)果顯然不符合實(shí)際，因此對(duì)此相似性度量進(jìn)行了改進(jìn).給出如下新的相似性度量的定義.

定義7設(shè)S=(U,A=C∪D,V,f)為一個(gè)信息系統(tǒng)，U為非空有限論域，C為條件屬性集，D為決策屬性集，xi,xj∈U，M和N分別表示對(duì)象xi和xj在屬性集A下的屬性值構(gòu)成的向量，則對(duì)象xi和xj的sim相似度simA(xi,xj)=cos′(M,N)×(1-‖M‖-‖N‖/max{‖M‖,‖N‖})，其中|·|表示絕對(duì)值，規(guī)定當(dāng)M=N=0時(shí)，‖M‖-‖N‖/max{‖M‖,‖N‖}=0.

性質(zhì)2在信息系統(tǒng)S=(U,A=C∪D,V,f)中，?xi,xj,xk∈U，M、N和Q分別表示對(duì)象xi、xj和xk在屬性集A下的屬性值構(gòu)成的向量，0表示零向量，則sim相似度滿足以下性質(zhì)：

(1) 0≤simA(xi,xj)≤1; (2)simA(xi,xi)=1;

(3)simA(xk,xj)=0，其中Q=0，N≠0； (4)simA(xi,xj)=simA(xj,xi);

(5) 若simA(xi,xj)=1，則必有M=N.

定義8設(shè)S=(U,A=C∪D,V,f)為一個(gè)信息系統(tǒng)，U為非空有限論域，C為條件屬性集，D為決策屬性集，A=C∪D的值集是全序集.根據(jù)sim相似度定義如下一種新的關(guān)系：

?xi,xj∈U}，

性質(zhì)4對(duì)于任意的X,Y?U，sim上、下近似滿足以下性質(zhì)：

3 基于聚類思想的對(duì)象權(quán)重確定方法

現(xiàn)有的權(quán)重確定方法主要集中在屬性權(quán)重上，雖然屬性權(quán)重會(huì)對(duì)決策和約簡(jiǎn)產(chǎn)生較大的影響，但在現(xiàn)實(shí)生活中對(duì)象權(quán)重也會(huì)對(duì)約簡(jiǎn)結(jié)果產(chǎn)生影響.一些學(xué)者利用代價(jià)敏感和AHP方法在對(duì)象權(quán)重的確定方法上做出了一些成果，但是這些方法都受到較大的主觀因素的影響.因此，利用聚類分析的思想構(gòu)造二元關(guān)系的方法來(lái)給出對(duì)象權(quán)重，從而降低主觀因素的影響.

易證m(Xi)滿足mass函數(shù)的基本性質(zhì)，因此是一個(gè)mass函數(shù).mass函數(shù)是2U上的概率分布函數(shù)，可以構(gòu)造出2U上的每個(gè)信息粒的一個(gè)不確定性度量——粒的權(quán)重.

性質(zhì)5設(shè)S=(U,A=C∪D,V,f)是一個(gè)信息系統(tǒng)，ω(xi)是對(duì)象xi∈U的權(quán)重，則ω(xi)滿足以下性質(zhì)：

4 基于加權(quán)條件信息熵的屬性重要度確定方法與約簡(jiǎn)算法

信息熵是信息論的主要內(nèi)容之一，它可以對(duì)信息量進(jìn)行量化度量.知識(shí)從信息中獲得，所以知識(shí)也是一種特殊的信息[13].因此，熵理論也可用于粗糙集的研究中.下面給出一種基于對(duì)象權(quán)重的加權(quán)條件熵的定義方式，并提出了基于加權(quán)條件熵的屬性重要度確定方法和屬性約簡(jiǎn)算法.

性質(zhì)6由X得到的加權(quán)信息熵滿足以下性質(zhì):

(3)若所有的相容類權(quán)重都相同，即ω(X1)=ω(X2)=…=ω(Xn)=ω時(shí)，則當(dāng)Xi/U=1/2時(shí)，Hω(X)取得最大值，并且Hω(X)=ω.

令～Xi表示Xi的補(bǔ)集，由于ω(～Xi)與ω(Xi)不一定相等，因此，Hω(～X)和Hω(X)不一定相等，即加權(quán)信息熵不滿足對(duì)稱性.新定義的加權(quán)信息熵滿足上面幾條性質(zhì)，符合加權(quán)信息熵的條件.下面給出相應(yīng)的加權(quán)條件熵的定義.

性質(zhì)7X相對(duì)于D的加權(quán)條件熵滿足以下性質(zhì)：

現(xiàn)有的屬性約簡(jiǎn)算法主要是在對(duì)象重要度相同的基礎(chǔ)上給出的，但是在現(xiàn)實(shí)生活中，對(duì)象的重要性往往都是不相同的.雖然文獻(xiàn)[12]考慮了對(duì)象權(quán)重對(duì)約簡(jiǎn)的影響，但是其考慮的對(duì)象權(quán)重需要依賴專家的先驗(yàn)知識(shí)得到，增加了主觀因素對(duì)約簡(jiǎn)算法的影響.為了降低這種影響，根據(jù)聚類分析與粗糙集相結(jié)合所得的屬性重要度與熵理論給出新的基于加權(quán)條件熵的屬性約簡(jiǎn)算法，該算法是一種基于熵不變的約簡(jiǎn)算法.

定義15設(shè)S=(U,C∪D,V,f)是一個(gè)信息系統(tǒng)，U為有限非空論域，C為條件屬性集，D為決策屬性集.若對(duì)于B?C，有Hω(DB)=Hω(DC)，且對(duì)于B的任何真子集B′都有Hω(DB′)≠Hω(DC)，則稱B為C的一個(gè)熵約簡(jiǎn).

定理1設(shè)S=(U,C∪D,V,f)是一個(gè)信息系統(tǒng)，U為有限非空論域，C為條件屬性集，D為決策屬性集，則有

(1) 若S為協(xié)調(diào)信息系統(tǒng)，則Hω(DC)=0；

(2) 若S為不協(xié)調(diào)信息系統(tǒng)，則Hω(DC)>0；

(3) 若S是一個(gè)協(xié)調(diào)信息系統(tǒng)，a是決策核心，則有H(DC)=0，Hω(DC-{a})>0;

(4) 若S是一個(gè)不協(xié)調(diào)信息系統(tǒng)，a是核心屬性，則有Hω(DC-{a})≠Hω(DC).

定義16對(duì)于加權(quán)目標(biāo)信息系統(tǒng)Sω=〈U,W,C·D,V,f〉，U為有限非空論域，C為條件屬性集，D為決策屬性集，W為權(quán)重集合.設(shè)B?C，則對(duì)于任意屬性a∈C-B，屬性a對(duì)屬性集B的內(nèi)部屬性重要度為SGF(a,B,D)in=|Hω(DB)-Hω(DB-a)|；屬性a對(duì)屬性集B的外部屬性重要度為SGF(a,B,D)out=|Hω(DB)-Hω(DB∪a)|.

基于給出的內(nèi)部屬性重要度和外部屬性重要度，提出了兩種啟發(fā)式約簡(jiǎn)算法，見(jiàn)表1.算法首先選取信息系統(tǒng)的核心屬性，然后添加外部屬性重要度大的屬性，最后再刪除多余屬性即可得到最終約簡(jiǎn).算法1和算法2分別介紹了協(xié)調(diào)信息系統(tǒng)和不協(xié)調(diào)信息系統(tǒng)的屬性約簡(jiǎn)算法.

表1 信息系統(tǒng)的屬性約簡(jiǎn)算法Tab.1 Attribute reduction algorithm for information system

例1為了說(shuō)明算法的合理性，以表2的信息表為例進(jìn)行仿真計(jì)算.

由重要度定義求得a1的內(nèi)部重要度SGF(a1,B,D)in=|Hω(DB)-Hω(DB-a1)|=0，同理可得a2,a3,a4的內(nèi)部重要度SGF(a2,B,D)in=0.013 3，SGF(a3,B,D)in=0.124 ，SGF(a4,B,D)in=0，又由于原信息系統(tǒng)是不協(xié)調(diào)的信息系統(tǒng)，所以根據(jù)SGF(ai,B,D)>0.002得RED={a2,a3}.又由于此時(shí)滿足|Hω(DC)-Hω(DB∪{amax})|<θ，再逐個(gè)刪除多余屬性即得最后約簡(jiǎn)RED={a2,a3}.

為了驗(yàn)證所提出的算法在大數(shù)據(jù)中的有效性，從UCI數(shù)據(jù)庫(kù)找出幾組數(shù)據(jù)分別與文獻(xiàn)[11，17]中的α-FRS算法和FNRS算法進(jìn)行了對(duì)比實(shí)驗(yàn)，進(jìn)行約簡(jiǎn)之前按照文獻(xiàn)[11，17]的方法對(duì)有數(shù)據(jù)缺失的對(duì)象進(jìn)行了刪除，并將處理后的數(shù)據(jù)集描述列于表3中.對(duì)幾組數(shù)據(jù)集選取合適的ε與θ值，本文算法與α-FRS算法和FNRS算法的約簡(jiǎn)結(jié)果對(duì)比分別列于表4和表5中.數(shù)據(jù)集Ecoli在不同參數(shù)下的約簡(jiǎn)結(jié)果列于表6中.

表2 信息表

表3 數(shù)據(jù)集描述Tab.3 Description of data sets

表4 α-FRS算法與本文算法約簡(jiǎn)結(jié)果的比較Tab.4 The reduction comparison of α-FRS and the proposed algorithm

表5 FNRS算法與本文算法約簡(jiǎn)結(jié)果的比較Tab.5 The reduction comparison of FNRS and the proposed algorithm

表6 數(shù)據(jù)集Ecoli在不同參數(shù)下的約簡(jiǎn)結(jié)果Tab.6 The reduction with different thresholds on the data of Ecoli

根據(jù)表6參數(shù)的變化可以看出，隨著ε的減小，信息系統(tǒng)會(huì)變得不協(xié)調(diào)，而參數(shù)θ的變大會(huì)使得約簡(jiǎn)越來(lái)越小.根據(jù)專家的經(jīng)驗(yàn)對(duì)數(shù)據(jù)集設(shè)置合適的ε與θ值，就能得到一個(gè)合適的約簡(jiǎn)結(jié)果.

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

將粗糙集理論與聚類分析的方法相結(jié)合提出了一種新的對(duì)象權(quán)重的確定方法，并且將對(duì)象權(quán)重與熵理論相結(jié)合給出了一個(gè)新的加權(quán)條件熵的定義，同時(shí)給出了基于加權(quán)條件熵屬性重要度的新定義.最后基于此屬性重要度給出了屬性約簡(jiǎn)算法，并且用UCI中選取的幾組數(shù)據(jù)集驗(yàn)證了該算法的合理性和有效性.

[1] PAWLAK Z．Rough sets[J]．International journal of computer and information sciences，1982，11(5)：341-356．

[2] 張文修，仇國(guó)芳．基于粗糙集的不確定決策[M]．北京：清華大學(xué)出版社，2005．

[3] 湯建國(guó)，佘堃，祝峰．覆蓋粗糙集的技術(shù)與方法[M]．成都：電子科技大學(xué)出版社，2013．

[4] 雷聰聰．一種基于數(shù)據(jù)聚類的信息?；椒╗D]．鄭州：鄭州大學(xué)，2010．

[5] 錢(qián)宇華．復(fù)雜數(shù)據(jù)的粒化機(jī)理與數(shù)據(jù)建模[D]．太原：山西大學(xué)，2011．

[6] JING Y G，LI T R，HUANG J F，et al．An incremental attribute reduction approach based on knowledge granularity under the attribute generalization[J]．International journal of approximate reasoning，2016，76: 80-95．

[7] 江峰，王莎莎，杜軍威，等．基于近似決策熵的屬性約簡(jiǎn)[J]．控制與決策，2015，30(1)：65-70．

[8] 史博文，李國(guó)和，吳衛(wèi)江，等．基于強(qiáng)化正域的屬性約簡(jiǎn)方法[J]．計(jì)算機(jī)應(yīng)用研究，2017，34(1)：107-109．

[9] 何華平，陳光建．一種最小測(cè)試代價(jià)約簡(jiǎn)的改進(jìn)算法[J]．鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2015, 47(1)：74-77．

[10] 孟慧麗，張倩倩，徐久成．基于貼近度的協(xié)調(diào)序決策系統(tǒng)屬性約簡(jiǎn)算法[J]．鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2016, 48(3)：90-93．

[11] 潘瑞林，李園沁，張洪亮，等．基于α信息熵的模糊粗糙屬性約簡(jiǎn)方法[J]．控制與決策，2017，32(2)：340-348．

[12] 劉金福，于達(dá)仁，胡清華，等．基于加權(quán)粗糙集的代價(jià)敏感故障診斷方法[J]．中國(guó)電機(jī)工程學(xué)報(bào)，2007，27(23)：93-99．

[13] 于迎春．覆蓋粗糙集中基于信息熵的幾個(gè)定義[J]．商業(yè)文化，2012(2)：344．

[14] 陳大力，沈巖濤，謝檳竹，等．基于余弦相似度模型的最佳教練遴選算法[J]．東北大學(xué)學(xué)報(bào)(自然科學(xué)版)，2014，35(12): 1697-1700．

[15] QIAN Y H，WANG Q，CHENG H H，et al．Fuzzy-rough feature selection accelerator[J]．Fuzzy sets and systems，2015，258：61-78．

[16] 張文修，梁怡，徐萍．基于包含度的不確定推理[M]．北京：清華大學(xué)出版社，2005．

[17] WANG C Z，SHAO M W，HE Q，et al．Feature subset selection based on fuzzy neighborhood rough sets[J]．Knowledge-based systems，2016，111：173-179．