Attribute reduction based on information entropy of approximation boundary accuracy
-
摘要: 针对信息观只考虑知识粒度的大小，不能客观、全面度量属性重要性的不足，首先从代数观出发，提出近似边界精度的定义；其次，根据相对模糊熵的定义，提出相对信息熵及增强信息熵概念，与相对模糊熵相比具有明显的放大作用；再次，将近似边界精度融合相对信息熵和增强信息熵，提出两种新的属性约简方法，在求U/（B∪b）时充分利用U/B的结果，可大大减少系统的时间开销；最后，通过实验分析和比较，本文算法在约简质量、分类精度上的可行性和有效性得到了验证.Abstract: From an information point of view, only the size of knowledge granularity is taken into account, while the importance of attributes cannot be objectively and comprehensively measured. First, starting from the perspective of algebra, the concept of approximate boundary accuracy is proposed. Afterwards, according to the definition of relative fuzzy entropy, this paper proposes two new concepts for relative information entropy and enhanced information entropy. Compared with relative fuzzy entropy, the proposed information entropy has an obvious magnification effect. Two new methods of attribute reduction are subsequently proposed by incorporating approximate boundary accuracy into relative information entropy and enhanced information entropy. Computing U/(B∪b) while making full use of U/B can greatly reduce the computational overhead on time. Finally, through the experimental analysis and comparison, it is validated that the proposed algorithm has feasibility and effectiveness in both reduction quality and classification accuracy.
-
算法1 近似边界精度增强信息熵及相对信息熵的计算 输入: 决策表${\rm DT}=(U,C,D,V,f)$, 划分
$U/B=\{X_1 ,X_2 ,\cdots ,X_n \}, U/D=\{Y_1 ,Y_2 ,\cdots ,Y_m \},$ 且$B\subseteq C$
输出: 近似边界精度增强信息熵${\rm ABAE}'(D\vert B)$, 相对信息熵为${\rm ABAE}(D\vert B)$int ${\rm ABAE}'={\rm ABAE}=0$;
int type;
for ($i$ from 1 to $m$) //$m$为$U/D$子划分的数目
{ int $t1$=$t2$=$t3$=$t4$=count=0;
input type;
for ($j$ from 1 to $n$) // $n$为$U/B$子划分的数目
{ count = count + $\left| {X_j } \right|$;
temp = intersect ($X_j, Y_i)$.length; //统计下近似元素的个数
if (temp = = $\left| {X_j } \right|)$ then
$t1=t1+\left| {X_j } \right|$;
else if (temp = = 0)
$t2=t2+\left| {X_j } \right|$;
else { switch(type) {
case 1: //计算增强信息熵
$t3=t3+\left| {X_j} \right|\cdot \dfrac{2\Big(1-\dfrac{{\rm temp}}{|X_j|}\Big)}{2-\dfrac{{\rm temp}}{|X_j|}}$; break;
case 2: //计算相对信息熵
if ($0\le \dfrac{\rm temp}{\left| {X_j } \right|}\prec \dfrac{1}{2}\Big)$ $t4=t4+\left| {X_j } \right|\cdot \Big[{1-{\dfrac{\rm temp}{\left| {X_j } \right|}} \Big/ {\Big(1-\dfrac{\rm temp}{\left| {X_j } \right|}\Big)}} \Big]$;
else $t4=t4+\left| {X_j } \right|\cdot \Big[{1-{\Big(1-\dfrac{\rm temp}{\left| {X_j } \right|}\Big)} \Big/{\dfrac{\rm temp}{\left| {X_j } \right|}}} \Big]$; }
break; } }
$t2$ = count - $t2$; //统计上近似元素个数
${\rm ABAE}=\; \; {\rm ABAE}+\bigg(1-\dfrac{\dfrac{t_1}{t_2}}{2-\dfrac{t_1}{t_2}}\bigg)\cdot t4; {\rm ABAE}'=\; \; {\rm ABAE}'+\bigg(1-\dfrac{\dfrac{t_1}{t_2}}{2-\dfrac{t_1}{t_2}}\bigg)\cdot t3;$ }
下载: 导出CSV
算法2 基于近似边界精度增强信息熵约简及相对信息熵约简 输入: ${\rm DT}=(U,C,D,V,f)$;
输出: R.step1 $R=\varnothing$, $C'=C$;
step2 计算$U/C$, $U/D$;
step3 计算条件属性$C$相对决策属性$D$的近似边界增强信息熵${\rm ABAE}'(D\vert C)$, 相对信息熵${\rm ABAE}(D\vert C)$;
step4 while ( 1 )
{ 计算Sig$'(b_k ,R,D)$＝$\mathop {\rm Max}\limits_{b_i \in C'}$Sig$'(b_i ,R,D)$或Sig$(b_k ,R,D)=\mathop {\rm Max}\limits_{b_i \in C'}$Sig$(b_i ,R,D)$, $1\le i\le \vert C'\vert $.
若有多个属性的重要性都达到最大值, 则从中任选一个$b_k $;
$R=R\cup b_k$; $C'=C'-b_k$;
if (${\rm ABAE}'(R\vert C)={\rm ABAE}'(D\vert C))$
输出增强信息熵的约简$R$;
if (${\rm ABAE}(R\vert C)={\rm ABAE}(D\vert C))$
输出相对信息熵的约简$R$; }
下载: 导出CSV
表 1 约简结果比较(剩余属性数)
Tab. 1 Comparison of reduction result(residue number)
DataSet RN CE FE CCE ADEAR ABAE ABAE’ Tic 8 8 8 8 8 8 8 Zoo 5 9 5 5 5 5 5 Ecoli 5 6 6 6 5 5 5 Lymph 6 8 6 7 6 6 6 Chess 29 30 30 29 29 29 29 Mush 4 5 5 5 5 5 4
下载: 导出CSV
表 2 运行时间比较
Tab. 2 Comparison of run time
DataSet CE/s FE/s CCE/s ADEAR/s ABAE/s ABAE'/s Tic 8.73 6.76 0.36 0.101 0.103 0.089 Lymph 3.124 1.36 0.126 0.053 0.054 0.048 Mush 300.22 166.92 24.88 1.80 1.88 1.67
下载: 导出CSV
-
[1] PAWLAK Z, SKOWRON A. Rough sets:Some extensions[J]. Information Sciences, 2007, 117(1):28-40. https://www.sciencedirect.com/science/article/pii/S0020025506001496 [2] PAWLAK Z. Rough sets[J]. Int J of Computer and Information Sciences, 1982, 11(5):341-356. doi: 10.1007/BF01001956 [3] 王熙照, 王婷婷, 翟俊海.基于样例选取的属性约简算法[J].计算机研究与发展, 2012, 49(11):2305-2310. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=jsjyjyfz201211005 [4] KIM K, CHU Y Y, WATADA J Z, et al. A DNA-based algorithm for minimizing decision rules:A rough sets approach[J]. IEEE Trans Nanobiosci, 2011, 10(3):139-151. doi: 10.1109/TNB.2011.2168535 [5] HUANG C C, TSENG T L, JIANG F H, et al. Rough set theory:A novel approach for extraction of robust decision rules based on incremental attributes[J]. Annals of Operations Research, 2014, 216(1):163-189. doi: 10.1007/s10479-013-1352-1 [6] 荆涛, 王家林, 石旭东, 等.基于粗糙集约简的飞机发电机故障诊断决策研究[J].计算机应用研究, 2017, 34(4):1101-1104. http://d.old.wanfangdata.com.cn/Periodical/jsjyyyj201704033 [7] 朱庆, 苗双喜, 丁雨淋, 等.知识引导的滑坡监测数据粗差定位与剔除方法[J].武汉大学学报(信息科学版), 2017, 42(4):496-502. http://d.old.wanfangdata.com.cn/Periodical/whchkjdxxb201704011 [8] 梁宝华, 汪世义.行式存储的快速属性约简算法[J].模式识别与人工智能, 2015, 8(9):795-801. http://d.old.wanfangdata.com.cn/Periodical/mssbyrgzn201509004 [9] 赵洁, 梁俊杰, 董振宁, 等.位运算和核属性快速识别下的粗糙集属性约简算法研究[J].小型微型计算机系统, 2015, 36(2):316-321. http://www.cnki.com.cn/Article/CJFDTotal-XXWX201502027.htm [10] 史博文, 李国和, 吴卫江, 等.基于强化正域的属性约简方法[J].计算机应用研究, 2017, 34(1):107-109. http://d.old.wanfangdata.com.cn/Periodical/jsjyyyj201701022 [11] 周建华, 徐章艳, 章晨光.改进的差别矩阵的快速属性约简算法[J].小型微型计算机系统, 2014, 35(4):831-834. http://industry.wanfangdata.com.cn/dl/Detail/Periodical?id=Periodical_xxwxjsjxt201404030 [12] 蒋瑜.基于差别信息树的rough set属性约简算法[J].控制与决策, 2015, 30(8):1531-1536. http://www.cnki.com.cn/Article/CJFDTotal-KZYC201508031.htm [13] 龙浩, 徐超.基于改进差别矩阵的属性约简增量式更新算法[J].计算机科学, 2015, 42(6):251-255. doi: 10.11896/j.issn.1002-137X.2015.06.053 [14] SHANNON C E. The mathematical theory of communication[J]. Bell System Technical J, 1948, 27(3/4):373-423. http://www.ncbi.nlm.nih.gov/pubmed/9230594 [15] 王国胤, 于洪, 杨大春.基于条件信息熵的决策表约简[J].计算机学报, 2002, 25(7):759-776. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=jsjxb200207013 [16] 杨明.决策表中基于条件信息熵的近似约简[J].电子学报, 2007, 35(11):2156-2160. doi: 10.3321/j.issn:0372-2112.2007.11.023 [17] 张清华, 肖雨.新的信息熵属性约简[J].计算机科学与探索, 2013, 7(4):359-367. http://www.cnki.com.cn/Article/CJFDTOTAL-KXTS201304009.htm [18] 潘瑞林, 李园沁, 张洪亮, 等.基于α信息熵的模糊粗糙集属性约简方法[J].控制与决策, 2017, 32(2):340-348. http://subject.wanfangdata.com.cn/xstjbg/2010/rgzn4.html [19] 江峰, 王莎莎, 杜军威, 等.基于近似决策熵的属性约简[J].控制与决策, 2015, 30(1):65-70. http://www.cnki.com.cn/Article/CJFDTotal-KZYC201501011.htm [20] QIAN Y H, LIANG J Y, PEDRYCZ W, et al. Positive approximation:An accelerator for attribute reduction in rough set theory[J]. Artificial Intelligence, 2010, 174(9):597-618. http://www.scirp.org/journal/PaperInformation.aspx?paperID=38982& [21] 蒋瑜, 刘胤田, 李超.基于Bucket Sort的快速属性约简算法[J].控制与决策, 2011, 26(2):207-212. http://d.old.wanfangdata.com.cn/Periodical/kzyjc201102009 -
点击查看大图
图(1) / 表(4)
计量
- 文章访问数: 131
- HTML全文浏览量: 53
- PDF下载量: 247
- 被引次数: 0