帶權(quán)重條件熵的屬性約簡(jiǎ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

?

帶權(quán)重條件熵的屬性約簡(jiǎ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 (國(guó)家自然科學(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)新團(tuán)隊(duì)領(lǐng)軍人才培育計(jì)劃項(xià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)容之一就是屬性約簡(jiǎn)問(wèn)題，現(xiàn)有的許多屬性約簡(jiǎn)算法往往是基于屬性對(duì)分類的重要性，如果屬性約簡(jiǎn)的結(jié)果能滿足用戶實(shí)際需要的信息，如成本、用戶的偏好等，那么約簡(jiǎn)理論將會(huì)有更高的實(shí)用價(jià)值?；诖?，從信息熵的角度定義了帶權(quán)重的屬性重要性，然后重新定義了基于帶權(quán)重的屬性book=1,ebook=150重要性的熵約簡(jiǎn)算法。最后通過(guò)實(shí)際例子說(shuō)明，與基于屬性重要性的熵約簡(jiǎn)算法相比，考慮權(quán)重的算法更加符合用戶的實(shí)際需求。

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

1　引言

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

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

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

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

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

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

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

定義4[15]（條件熵）屬性集A(U/A={Y1,Y2,?,Ym})相對(duì)于屬性集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時(shí)，定義lb p(Yj|Xi)=0；當(dāng)屬性集B為空集時(shí)，H(A|?)=1。

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

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

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

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

定義6（屬性權(quán)重）對(duì)于目標(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。

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

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

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

當(dāng)屬性子集是空集時(shí)，根據(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}時(shí)，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ù)上述計(jì)算結(jié)果可以知道，由于屬性子集的改變，屬性的重要性也隨之改變，從而屬性的重要性是動(dòng)態(tài)變化的。在下面定義的算法中，在每一次的循環(huán)過(guò)程中屬性的子集都發(fā)生了改變，因此要注意每一次循環(huán)都需要重新計(jì)算屬性的重要性度量。

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

算法1基于屬性重要性的熵約簡(jiǎn)算法

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

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

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

（2）初始化B=C , A=?，計(jì)算每個(gè)條件屬性的重要性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）計(jì)算條件熵H(D|B-{ai})，如果H(D|C)= H(D|B-{ai})，則停止循環(huán)，否則跳到步驟（2）；

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

3.2基于帶權(quán)重的屬性重要性的熵約簡(jiǎ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ù)用戶的需求來(lái)設(shè)定。當(dāng)k=0時(shí)，加權(quán)屬性重要性就成了屬性的重要性，相應(yīng)的約簡(jiǎn)算法就是算法1給出的基于屬性重要性的熵約簡(jiǎn)算法，并且最終得到的約簡(jiǎn)是具有最少屬性的約簡(jiǎn)。當(dāng)k=1時(shí)，加權(quán)屬性重要性變成了屬性的權(quán)重，相應(yīng)的約簡(jiǎn)算法是基于權(quán)重的屬性約簡(jiǎn)算法，即將算法1中的屬性重要性換成屬性的權(quán)重，這樣最終獲得的約簡(jiǎn)更符合用戶的需求，即用戶支付最少的成本。當(dāng)0

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

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

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

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

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

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

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

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

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

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

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

3.3算法的完備性分析

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

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

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

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

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

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

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

分別根據(jù)算法1和算法2計(jì)算各自的熵約簡(jiǎn)，這里取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ù)屬性重要性算法計(jì)算信息系統(tǒng)的屬性約簡(jiǎn)，這里定義初始集為空集，根據(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}。容易驗(yàn)證此時(shí)H(D|B)= H(D|C)，則循環(huán)停止，進(jìn)行步驟（5）時(shí)可以計(jì)算出屬性b的重要性為0，其余屬性都不為0，因此只刪除b，最終約簡(jiǎn)為B={c,d}。

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

通過(guò)分析可以看出，約簡(jiǎn)算法2計(jì)算所得的總成本是5，約簡(jiǎn)算法1中所得的總成本是11。算法2的總成本比算法1的總成本要少，說(shuō)明算法2更符合用戶的需求。

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

本文提到的算法1將原始的屬性重要性定義為基于條件熵的屬性重要性，算法2將基于熵的屬性重要性和量化后的用戶需求相結(jié)合，也就是先驗(yàn)知識(shí)和客觀要求的結(jié)合，提出了更符合用戶需求的新算法。容易看出當(dāng)算法2中的權(quán)重系數(shù)k為0時(shí)，該算法就是算法1。算法2改進(jìn)了原始的約簡(jiǎn)算法，使其更接近現(xiàn)實(shí)生活，尤其是對(duì)專家系統(tǒng)和醫(yī)療診斷系統(tǒng)等現(xiàn)實(shí)問(wèn)題的發(fā)展更具有指導(dǎo)性的意義，這也將促進(jìn)粗糙集理論在現(xiàn)實(shí)生活中的應(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]王國(guó)胤,于洪,楊大春.基于條件信息熵的決策表約簡(jiǎn)[J].計(jì)算機(jī)學(xué)報(bào), 2002, 25(7): 759-762.

[13]張文修,梁怡,吳偉志.信息系統(tǒng)與知識(shí)發(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)域?yàn)榇植诩?，近似推理等?/p>

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)域?yàn)榇植诩?，概念格，近似推理等?/p>

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

中圖分類號(hào)：O236