祖鴻嬌，米據(jù)生

河北師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，石家莊050024

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(03)-0445-06

?

帶權(quán)重條件熵的屬性約簡算法*

祖鴻嬌+，米據(jù)生

河北師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，石家莊050024

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(03)-0445-06

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant Nos. 61170107, 61300153, 61300121 (國家自然科學(xué)基金); the Natural Science Foundation of Hebei Province of China under Grant Nos. A2013208175, A2014205157 (河北省自然科學(xué)基金); the Talent Programme of Innovation Team in Colleges and Universities of Hebei Province under Grant No. LJRC022 (河北省高校創(chuàng)新團隊領(lǐng)軍人才培育計劃項目).

Received 2015-05,Accepted 2015-07.

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2015-07-03, http://www.cnki.net/kcms/detail/11.5602.TP.20150703.1101.001.html

摘要：粗糙集理論中最重要的內(nèi)容之一就是屬性約簡問題，現(xiàn)有的許多屬性約簡算法往往是基于屬性對分類的重要性，如果屬性約簡的結(jié)果能滿足用戶實際需要的信息，如成本、用戶的偏好等，那么約簡理論將會有更高的實用價值?；诖?，從信息熵的角度定義了帶權(quán)重的屬性重要性，然后重新定義了基于帶權(quán)重的屬性book=1,ebook=150重要性的熵約簡算法。最后通過實際例子說明，與基于屬性重要性的熵約簡算法相比，考慮權(quán)重的算法更加符合用戶的實際需求。

關(guān)鍵詞：粗糙集；條件熵；加權(quán)屬性重要性；熵約簡

1　引言

粗糙集是由Pawlak教授在1982年提出的，用以處理不確定、不精確知識的一種數(shù)學(xué)理論方法。粗糙集理論[1]在很多領(lǐng)域有廣泛的應(yīng)用，如數(shù)據(jù)挖掘、機器學(xué)習(xí)、故障診斷、模式識別[2-5]等。該理論最重要的特點就是它不需要任何先驗信息就可以直接從信息系統(tǒng)中提取知識。屬性約簡是從數(shù)據(jù)表中獲取規(guī)則的重要過程，是為了簡化原始的信息系統(tǒng)但不影響信息系統(tǒng)的分類能力，從而刪除冗余屬性的過程，是粗糙集理論中最重要的研究內(nèi)容之一[6-10]。本文以條件熵為啟發(fā)知識，對決策表采用啟發(fā)式知識約簡算法，算法的起點是初始條件屬性集，采用逐步刪除條件屬性的方法來得到約簡結(jié)果。

基于條件熵的屬性重要性[11]的屬性約簡算法是以最少條件屬性為出發(fā)目標(biāo)，同樣采用啟發(fā)式原則，令初始的約簡屬性集為給定的條件屬性集，將屬性按照其重要性從小到大逐個刪除，直到屬性集滿足約簡條件為止。從該約簡算法的處理過程可以看出，通過這種算法確實可以得到最小的屬性集，然而其得到的約簡結(jié)果卻忽視了如成本、用戶的偏好等實際需要，缺乏實際應(yīng)用價值。2014年重慶大學(xué)的張清華和沈文在文獻(xiàn)[12]中研究了這類問題，提出了考慮用戶需求的加權(quán)屬性重要性，并給出了一種新的屬性約簡算法，與本文不同的是，其算法采用的是正域約簡。

在現(xiàn)實生活中，人們往往是為了滿足自身需求而進(jìn)行某些社會活動。在粗糙集的熵約簡中，用戶已經(jīng)有了每個屬性的先驗知識，如用戶的偏好，而這些先驗信息并不能反映其對屬性集合的分類能力，而屬性的重要性也只反映了其對屬性集合的分類能力，并不能反映用戶的偏好需求。因此需要通過添加一個權(quán)重系數(shù)將這兩個要求結(jié)合起來，并通過調(diào)整系數(shù)的大小來反映用戶對這兩個要求的傾向程度。這樣，根據(jù)重新定義的加權(quán)屬性重要性設(shè)計出一個新的熵約簡算法，通過該算法來得到更滿足用戶需求的屬性約簡。

2　預(yù)備知識

定義1[13]（目標(biāo)信息系統(tǒng)）目標(biāo)信息系統(tǒng)被定義為一個四元組S=(U,C?D,V,f)，其中U是研究對象的非空有限集合，也稱為論域，U={x1,x2,?,xn}; C?D稱為屬性集, C是條件屬性集，D是決策屬性集；V是屬性值的集合；f:U×C?D→V稱為信息函數(shù)，它指定U中每一個對象的屬性值。

定義213]（不可辨識關(guān)系）對于條件屬性集C或決策屬性集D的一個子集B，有一個U上的不可辨識關(guān)系,如果(x,y)屬于RB，就說x和y是B不可辨識的。以這種方法定義的不可辨識關(guān)系是等價關(guān)系。不可辨識關(guān)系RB的所有等價類的集合記作，包含元素x的等價類記作。

定義3[14]（信息熵）設(shè)U是一個論域，屬性集合B 在U上的劃分為X={X1,X2,?,Xn}，屬性集合B的熵H(B)定義為H(B)=

定義4[15]（條件熵）屬性集A(U/A={Y1,Y2,?,Ym})相對于屬性集B(U/B={X1,X2,?,Xn})的條件熵H(A|B)定義為H(A|B)=，其中i=1,2,?,n，j=1,2,?,m。特別地,當(dāng)Yj?Xi=?, 即p(Yj|Xi)=0時，定義lb p(Yj|Xi)=0；當(dāng)屬性集B為空集時，H(A|?)=1。

定義5[15]（熵約簡）對于目標(biāo)信息系統(tǒng)S=(U, C?D,V,f)，其中U是論域，C是條件屬性集，D是決策屬性集。對于B?C，如果有H(D|B)=H(D|C)，則稱B為一個熵協(xié)調(diào)集，若對于B的任何真子集B′，都有H(D|B′)≠H(D|C)，則稱B為C的一個熵約簡。

3　帶權(quán)重的熵約簡算法

3.1帶權(quán)重的熵約簡標(biāo)準(zhǔn)

對于已有的約簡算法來說，大多數(shù)的約簡標(biāo)準(zhǔn)都是為了得到最小的屬性集合，而本文則是通過添加一個權(quán)重系數(shù)，將最少的屬性和更滿足用戶需求的結(jié)果作為約簡的標(biāo)準(zhǔn)，這樣便能得到更具有實際應(yīng)用價值的研究結(jié)果。然而對于不同的用戶，其對上述兩個標(biāo)準(zhǔn)的傾向程度也存在著差異，可以通過設(shè)置不同的權(quán)重系數(shù)來達(dá)到相應(yīng)的目的。下面就給出屬性權(quán)重的定義。

定義6（屬性權(quán)重）對于目標(biāo)信息系統(tǒng)S=(U, C?D,V,f)，其中U是論域，C是條件屬性集，D是決策屬性集。令ti是屬性ai的成本值，其中i=1, 2,?,n。?ai∈C，它的屬性權(quán)重定義為qi=1-ti/j。

屬性重要性是研究約簡問題時一個關(guān)鍵的概念，文獻(xiàn)[7]所用到的屬性重要性的概念是一個基于正域的度量，本文定義的屬性重要性是基于條件熵的度量。下面給出基于條件熵的屬性重要性的概念。

定義7（基于條件熵的屬性重要性）對于目標(biāo)信息系統(tǒng)S=(U,C?D,V,f)，其中U是論域，C是條件屬性集，D是決策屬性集，且A?C，則對于任意屬性a∈C-A的重要性SGF(a,A,D)定義為SGF(a,A,D)= H(D|A)-H(D|A-{a})。

當(dāng)A為空集時，SGF(a,?,D ) =1-H(D|a ) , SGF(a,A,D )的值越大，說明在已知屬性子集A的情況下屬性a對于決策D越重要。根據(jù)上述定義還可以看出，當(dāng)屬性子集A發(fā)生改變時，所有屬性的重要性也發(fā)生相應(yīng)的變化，也就是說屬性的重要性和屬性子集是密切相關(guān)的。下面利用表1進(jìn)行說明，表中第一行表示用戶所支付的成本。

當(dāng)屬性子集是空集時，根據(jù)定義4和定義7, U/{a}={{x1,x7},{x2,x3,x4,x5,x6,x8}}，則屬性a的重要性為：

Table 1　 Decision information system表1　目標(biāo)信息系統(tǒng)

當(dāng)屬性子集為{b,c}時，U/{b,c}={{x1,x3,x7,x8},{x2}, {x4,x5,x6}},U/{a,b,c}={{x1,x7},{x2},{x3,x8}{x4,x5,x6}},則屬性a的重要性為：

SGF(a,{b,c},D)=H(D|{b,c})-H(D|{a,b,c})=

根據(jù)上述計算結(jié)果可以知道，由于屬性子集的改變，屬性的重要性也隨之改變，從而屬性的重要性是動態(tài)變化的。在下面定義的算法中，在每一次的循環(huán)過程中屬性的子集都發(fā)生了改變，因此要注意每一次循環(huán)都需要重新計算屬性的重要性度量。

上面已經(jīng)有了基于條件熵的屬性重要性以及熵約簡的概念，下面給出基于屬性重要性的熵約簡的具體算法。

算法1基于屬性重要性的熵約簡算法

輸入：一個目標(biāo)信息系統(tǒng)S=(U,C?D,V,f)，C和D分別為條件屬性集和決策屬性集。

輸出：該目標(biāo)信息系統(tǒng)的一個熵約簡B。

（1）計算目標(biāo)信息系統(tǒng)S中決策屬性D相對條件屬性C的條件熵H(D|C)；

（2）初始化B=C , A=?，計算每個條件屬性的重要性SGF(ai,A,D)，其中, ai∈C，將ai按SGF(ai,A, D)升序排列；

（3）按SGF(ai,A,D)升序依次選出ai，令B= B-ai，A=A?ai，如果B=?，則終止循環(huán)；

（4）計算條件熵H(D|B-{ai})，如果H(D|C)= H(D|B-{ai})，則停止循環(huán)，否則跳到步驟（2）；

（5）對于B中每個屬性，如果它的屬性重要性SGF(ai,B-{ai},D)=H(D|B-{ai})-H(D|B)=0，則刪除這個屬性，否則就保留，那么此時的B就是約簡結(jié)果。

3.2基于帶權(quán)重的屬性重要性的熵約簡算法

定義8（帶權(quán)重的屬性重要性）考慮目標(biāo)信息系統(tǒng)S=(U,C?D,V,f)，其中U是論域，C是條件屬性集，D是決策屬性集。?ai∈C，它的加權(quán)屬性重要性定義為Si=kqi+(1-k)SGF(ai,A,D)，其中，qi是屬性權(quán)重, SGF(ai,A,D)是屬性重要性，k為屬性權(quán)重和屬性重要性的權(quán)重系數(shù)，系數(shù)k可以根據(jù)用戶的需求來設(shè)定。當(dāng)k=0時，加權(quán)屬性重要性就成了屬性的重要性，相應(yīng)的約簡算法就是算法1給出的基于屬性重要性的熵約簡算法，并且最終得到的約簡是具有最少屬性的約簡。當(dāng)k=1時，加權(quán)屬性重要性變成了屬性的權(quán)重，相應(yīng)的約簡算法是基于權(quán)重的屬性約簡算法，即將算法1中的屬性重要性換成屬性的權(quán)重，這樣最終獲得的約簡更符合用戶的需求，即用戶支付最少的成本。當(dāng)0

下面給出綜合考慮約簡屬性的數(shù)量以及用戶需求的帶權(quán)重的屬性重要性的熵約簡算法。

算法2基于帶權(quán)重的屬性重要性的熵約簡算法

輸入：一個信息系統(tǒng)S=(U,C?D,V,f)，C和D分別為條件屬性集和決策屬性集。

輸出：該目標(biāo)信息系統(tǒng)的一個熵約簡B。

（1）B初始化，B=C , A=?，根據(jù)用戶的需求調(diào)整權(quán)重系數(shù)k的取值；

（2）計算目標(biāo)信息系統(tǒng)S中決策屬性D相對條件屬性C的條件熵H(D|C)；

（3）計算A中每個屬性的加權(quán)屬性的重要性Si=kqi+(1-k)SGF(ai,A,D)，初始化SGF(ai,A,D)=1-H(0qqoa2g|{ai})；

（4）選擇最小加權(quán)屬性重要性的屬性ai, B= B-ai，A=A?ai，如果B=?，則跳到（6）；

（5）如果H(D|C)=H(D|B-{ai})，則循環(huán)停止, B是初始的約簡，否則跳到步驟（3）；

（6）對于B中每個屬性，如果它的屬性重要性SGF(ai,B-{ai},D)=H(D|B-{ai})-H(D|B)=0，則刪除這個屬性，否則就保留，那么此時的B就是最終的約簡。

該算法輸出的約簡結(jié)果B在滿足約簡條件的同時又能減少用戶的支付成本，這是和用戶需求一致的。需要注意的是每一次循環(huán)步驟（3）時，每個屬性的加權(quán)屬性重要性都應(yīng)該重新計算。

3.3算法的完備性分析

根據(jù)熵約簡的定義，如果B?C是一個給定的目標(biāo)信息系統(tǒng)的條件屬性的約簡，應(yīng)滿足下列條件：

（1）H(D|B)=H(D|C)；

（2）對于B的任何真子集B′, H(D|B′)≠H(D|C)。

如果約簡算法同時滿足條件（1）和（2），那么這個屬性約簡算法就是完備的。條件（1）表明屬性子集B是一個協(xié)調(diào)集，這也是屬性約簡的最基本的要求。條件（2）表明通過該算法得到的約簡沒有多余的屬性，去掉協(xié)調(diào)集B中的任一屬性后都會導(dǎo)致約簡的可辨識關(guān)系的改變。

定理1基于加權(quán)屬性重要性的屬性算法是完備的。

證明先看條件（1），因為算法2的結(jié)束條件是（1），所以由算法2得到的約簡一定滿足條件（1）。步驟（6）中屬性的重要性度量等于0的屬性是刪除的，根據(jù)定義7，在步驟（6）中并不存在冗余的屬性，因此條件（2）是滿足的。從上面的分析可以得出這樣的結(jié)論：基于加權(quán)屬性的重要性的熵約簡算法是完備的。□

例1以表1為例，表中數(shù)據(jù)量化用戶的需求為成本屬性，這個成本屬性與用戶的需求逆相關(guān)，即成本值越大，用戶對其需求性就越小。

分別根據(jù)算法1和算法2計算各自的熵約簡，這里取k=0.6，其中C={a,b,c,d}為條件屬性，D={e}為決策屬性。根據(jù)表1 U/C={{x1,x7},{x2},{x3,x8}, {x4,x5,x6}}，U/D={{x1,x3,x8},x2,x4,x5,x6,x7}。

首先根據(jù)屬性重要性算法計算信息系統(tǒng)的屬性約簡，這里定義初始集為空集，根據(jù)定義7，SGF(a, ?,D)=0.061 3，SGF(b,?,D)=0.137 9 , SGF(c,?,D)= 0.594 4，SGF(d,?,D)=0.512 5，因此選取屬性a，則B={b,c,d}。容易驗證此時H(D|B)= H(D|C)，則循環(huán)停止，進(jìn)行步驟（5）時可以計算出屬性b的重要性為0，其余屬性都不為0，因此只刪除b，最終約簡為B={c,d}。

基于算法2，根據(jù)定義6，每個條件屬性的權(quán)重分別為a=0.777 8，b=0.833 3，c=0.944 4, d=0.444 4。在第一輪循環(huán)中，每個加權(quán)屬性重要性分別為a=0.491 2，b=0.555 1，c=0.804 4，d=0.471 6，因此挑出屬性d，即B=B-uoocmuy={a,b,c}。容易驗證此時H(D|B)=H(D|C)，循環(huán)停止，并且在進(jìn)行步驟（6）時可以得到屬性b的屬性重要性為0，其余均不為0，故刪掉b，因此最終約簡為B={a,c}。

通過分析可以看出，約簡算法2計算所得的總成本是5，約簡算法1中所得的總成本是11。算法2的總成本比算法1的總成本要少，說明算法2更符合用戶的需求。

4　結(jié)束語

本文提到的算法1將原始的屬性重要性定義為基于條件熵的屬性重要性，算法2將基于熵的屬性重要性和量化后的用戶需求相結(jié)合，也就是先驗知識和客觀要求的結(jié)合，提出了更符合用戶需求的新算法。容易看出當(dāng)算法2中的權(quán)重系數(shù)k為0時，該算法就是算法1。算法2改進(jìn)了原始的約簡算法，使其更接近現(xiàn)實生活，尤其是對專家系統(tǒng)和醫(yī)療診斷系統(tǒng)等現(xiàn)實問題的發(fā)展更具有指導(dǎo)性的意義，這也將促進(jìn)粗糙集理論在現(xiàn)實生活中的應(yīng)用。

References:

[1] Pawlak Z. Rough sets[J]. International Journal of Computer and Information Sciences, 1982, 1115: 341-356.

[2] Pawlak Z, Grzymala-Busse J, Slowinski R, et al. Rough sets[J]. Communications of the ACM, l995, 38(11): 89- 95.

[3] Lingras P J, Yao Yiyu. Data mining using extensions of the rough set model[J]. Journal of the American Society for Information Science, 1998, 49(5): 415-422.

[4] Tsumoto S. Automated discovery of positive and negative knowledge in clinical databases based on rough set model[J]. IEEE EMB Magazine, 2000, 19(4): 56-62.

[5] Ziako W C. Rough sets: trends, challenges, and prospects: rough sets and current trends in computing[M]. Berlin: Springer-Verlag, 2001.

[6] Duentsch I, Gediga G. Uncertainty measures of rough set prediction[J].Artificial Intelligence, 1998, 106(1): 109-137.

[7] Dai Jianhua, Li Yuanxiang, Liu Qun. A hybrid genetic algorithm for reduct of attributes in decision system based on rough set theory[J]. Wuhan University Journal of Natural Sciences, 2002, 7(3): 285-289.

[8] Du Yong, Hu Qinghua, Zhu Pengfei, et al. Rule learning for classification based on neighborhood covering reduction[J]. Information Sciences, 2011, 181(24): 5457- 5467.

[9] Dai Jianhua, Xu Qing. Attribute selection based on information gain ratio in fuzzy rough set theory with application to tumor classification[J]. Applied Soft Computing, 2013, 13 (1): 211-221.

[10] Xu Weihua, Li Yuan, Liao Xiuwu. Approaches to attribute reductions based on rough set and matrix computation in inconsistent ordered information systems[J]. Knowledge Based Systems, 2012, 27: 78-91.

[11] Wang Guoyin, Yu Hong, Yang Dachun. Decision table reduction based on conditional information entropy[J]. Chinese Journal of Computers, 2002, 25(7): 759-762.

[12] Zhang Qinghua, Shen Wen. Research on attribute reduction algorithm with weight[J]. Journal of Intelligent & Fuzzy Systems, 2014, 27(2): 1011-1019.

[13] Zhang Wenxiu, Liang Yi, Wu Weizhi. Information system and knowledge discovery[M]. Beijing: Science Press, 2003: 42-48.

[14] Zhang Wenxiu, Liang Yi, Xu Ping. Uncertainty reasoning based on inclusion degree[M]. Beijing: Tsinghua University Press, 2007: 43-49.

[15] Dai Jianhua, Wang Wentao, Tian Haowei, et al. Attribute selection based on a new conditional entropy for incompletedecision systems[J]. Knowledge Based System, 2013, 39: 207-213.

附中文參考文獻(xiàn)：

[11]王國胤,于洪,楊大春.基于條件信息熵的決策表約簡[J].計算機學(xué)報, 2002, 25(7): 759-762.

[13]張文修,梁怡,吳偉志.信息系統(tǒng)與知識發(fā)現(xiàn)[M].北京:科學(xué)出版社, 2003: 42-48.

[14]張文修,梁怡,徐萍.基于包含度的不確定推理[M].北京:清華大學(xué)出版社, 2007: 43-49.

ZU Hongjiao was born in 1990. She is an M.S. candidate in mathematics at Hebei Normal University. Her research interests include rough set and approximate reasoning, etc.祖鴻嬌（1990—），女，河北秦皇島人，河北師范大學(xué)數(shù)學(xué)專業(yè)碩士研究生，主要研究領(lǐng)域為粗糙集，近似推理等。

MI Jusheng was born in 1966. He received the Ph.D. degree in applied mathematics from Xi’an Jiaotong University in 2003. Then he was a post-doctoral fellow at the Chinese University of Hong Kong. Now he is a professor and Ph.D. supervisor at Hebei Normal University. His research interests include rough sets, concept lattices and approximate reasoning, etc.米據(jù)生（1966—），男，河北寧晉人，2003年于西安交通大學(xué)應(yīng)用數(shù)學(xué)專業(yè)獲得博士學(xué)位，隨后在香港中文大學(xué)從事博士后研究，現(xiàn)為河北師范大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域為粗糙集，概念格，近似推理等。

Attribute Reduction Algorithm Based on Conditional Entropy with Weights?

ZU Hongjiao+, MI Jusheng
College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang 050024, China
+ Corresponding author: E-mail: zuhongjiao5@163.com

ZU Hongjiao, MI Jusheng. Attribute reduction algorithm based on conditional entropy with weights. Journal of Frontiers of Computer Science and Technology, 2016, 10(3): 445-450.

Abstract:Attribute reduction is one of the most important contents of rough set theory, and many of the existing reduction algorithms are often based on attribute importance. If the result of attribute reduction can meet the information of actual need, such as the costs and users’preference, etc, the theory of reduction will have higher practical value. So, this paper defines the attribute importance with weights based on information entropy, then defines attribute entropy reduction algorithm which is based on the attribute importance with weights. Finally, the experimental results show that, compared with the entropy reduction algorithm based on the attribute importance, the algorithm with weights is more coincident with the actual requirements of users.

Key words:rough set; condition entropy; weighted attribute importance; entropy reduction

doi:10.3778/j.issn.1673-9418.1506013

文獻(xiàn)標(biāo)志碼：A

中圖分類號：O236