﻿ 基于改进差别信息树的粗糙集属性约简算法
 控制与决策  2019, Vol. 34 Issue (6): 1253-1258 0

### 引用本文 [复制中英文]

[复制中文]
JIANG Yu. Attribute reduction with rough set based on improved discernibility information tree[J]. Control and Decision, 2019, 34(6): 1253-1258. DOI: 10.13195/j.kzyjc.2017.1523.
[复制英文]

### 文章历史

Attribute reduction with rough set based on improved discernibility information tree
JIANG Yu
College of Software Engineering, Chengdu University of Information Technology, Chengdu 610225, China
Abstract: A discernibility matrix is a good idea for attribute reduction. Discernibility information tree can effectively eliminate redundancy elements in discernibility matrix, and it realizes the compactness storage of discernibility matrix. However, discernibility information tree neither considers the role of core attribute in eliminating redundancy elements nor considers the effect of attribute order in the compactness storage elements in the discernibility matrix. Therefore, an improved discernibility information tree is proposed, which can further compress the storage space of non-empty elements in the discernibility matrix. In order to verify the effectiveness of the improved discernibility information tree, some simulation experiments for UCI datasets are displayed.
Keywords: rough set    discernibility matrix    attribute reduction    improved discernibility information tree    attribute significance
0 引言

1 差别信息树

 图 1 基于表 1构建的差别信息树

2 改进差别信息树的设计与实现

2.1 核属性剪枝策略

get IDI-tree(decision table T)

{

1) 令CoreC(D)=∅;

2) 创建改进差别信息树根节点TN, 并令TN为null;

3) 对于决策表T中每个对象对〈xi, xj〉, 计算其差别信息DI;

if(DI∩CoreC(D)==∅){

if(|DI|==1)CoreC(D)=CoreC(D) ∪ DI且根据属性指针头表删除含有该核属性的所有路径;

while(DI≠∅){

ⅰ)令属性b是排列在DI中最左边的元素;

ⅱ) if(TN有一子节点N, 且N的属性名为b)

{

如果N是一叶子节点, 返回; 否则TN=N

}

else{

a)创建一新节点N', 节点N'作为TN一子节点, 同时初始N'的属性名为b, 并通过该节点的同名指针连接到具有与该节点有相同属性名的节点上, 从而构成一个同名属性节点链;

b)令TN=N'.

}

ⅲ) DI= DI-{b}.

}

}

}

 图 2 基于表 1和算法1构建的IDI-tree

2.2 属性重要度策略

 图 3 IDI-tree:order(DI)=〈d, e, a, b, c〉

2.3 改进差别信息树的复杂度分析

3 基于改进差别信息树的属性约简算法

1) 创建一空集R.

2) 获取改进差别信息树的头表HT, 并令CList为头表中属性至上而下的有序序列集合.

3) 集合Core'C(D)是由改进差别信息树中只含有一个节点的路径所对应的属性所构成的集合.

4) 若Core'C(D)非空, 则对所有a∈Core'C(D), 在改进差别信息树中删除包含a属性的所有路径.

5) 令R←Core'C(D)且CList←CList-Core'C(D).

6) while CList≠∅∧IDI-tree≠∅ do{

ⅰ)选取CList中最右边的一属性Ci, 令CList←CList-{Ci};

ⅱ)如果HT[Ci]≠∅并且CiR, 则根据头表HT[Ci]所对应的同名指针, 搜索同名指针构成的指针链, 在搜索过程中, 若链中节点为叶子节点, 则在改进差别信息树中删除该叶子节点;

ⅲ) 把改进差别信息树中的只有一个节点的路径所对应的属性加入集合R中, 并在改进差别信息树中删除包含这些属性的路径, 同时在CList中删除这些属性.

}

7) 输出R, 算法结束.

 图 4 基于算法2的改进差别信息树:〈a, c, d, b〉

1) 初始时R为空, 而CList为{a, c, d, b};

2) 属性b加入约简R中, 并从CList中删除属性b, 同时从改进差别信息树中删除含属性b的路径;

3) 选取CList中最右边属性d, 通过同名指针链删除包含属性d的叶子节点;

4) 选取CList中最右边属性c, 通过同名指针链删除包含属性c的叶子节点;

5) 将属性a加入约简R中, 并从CList删除属性a, 同时删除含属性a的路径;

6) 将此时差别信息树改进为只含根节点的空树, 算法结束, 输出约简R={a, b}.

4 实验结果及分析

5 结论

 [1] Pawlak Z. Rough sets[J]. Int J of Computer and Information Science, 1982, 11(5): 341-356. DOI:10.1007/BF01001956 [2] Slowinski R. Intelligent decision support-handbook of applications and advances of the rough sets theory[M]. London: Kluwer Academic Publishers, 1992: 176-177. [3] 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/10): 597-618. [4] 蒋瑜, 刘胤田, 李超. 基于Bucket Sort的快速属性约简算法[J]. 控制与决策, 2011, 26(2): 207-212. (Jiang Y, Liu Y T, Li C. Fast algorithm for computing attribute reduction based on Bucket Sort[J]. Control & Decision, 2011, 26(2): 207-212.) [5] Wen S D, Bao Q H. A fast heuristic attribute reduction approach to ordered decision systems[J]. European J of Operational Research, 2018, 264(2): 440-452. DOI:10.1016/j.ejor.2017.03.029 [6] Liu G L, Hua Z, Chen Z H. A general reduction algorithm for relation decision systems and its applications[J]. Knowledge-Based Systems, 2017, 119(5): 87-93. [7] 王熙照, 王婷婷, 翟俊海. 基于样例选择的属性约简算法[J]. 计算机研究与发展, 2012, 49(11): 2305-2310. (Wang X Z, Wang T T, Zhai J H. An attribute reduction algorithm based on instance selection[J]. J of Computer Research and Development, 2012, 49(11): 2305-2310.) [8] 周建华, 徐章艳, 章晨光. 改进的差别矩阵的快速属性约简算法[J]. 小型微型计算机系统, 2014, 35(4): 831-834. (Zhou J H, Xu Z Y, Zhang C G. Quick attribute reduction algorithm based on the improved disernibility matrix[J]. J of Chinese Computer Systems, 2014, 35(4): 831-834. DOI:10.3969/j.issn.1000-1220.2014.04.030) [9] 冯少荣, 张东站. 基于改进差别矩阵的增量式属性约简算法[J]. 深圳大学学报理工版, 2012, 29(5): 405-411. (Feng S R, Zhang D Z. Increment algorithm for attribute reduction based on the improvement of disernibility matrix[J]. J of Shengzhen University Science and Engineering, 2012, 29(5): 405-411.) [10] Wu Z J, Zhang J M, Gao Y. An attribute reduction algorithm based on genetic algorithm and discernibility matrix[J]. J of Software, 2012, 7(11): 2040-2048. [11] Zheng J G, Yan R X. Attribute reduction based on cross entropy in rough set theory[J]. J of Information & Computational Science, 2012, 9(3): 745-750. [12] 马胜蓝, 叶东毅. 信息熵最小约简问题的若干随机优化算法[J]. 模式识别与人工智能, 2012, 25(1): 96-104. (Ma S L, Ye D Y. Research on computing minimum entropy based attribute reduction via stochastic optimization algorithms[J]. Pattern Recognition and Artificial Intelligence, 2012, 25(1): 96-104. DOI:10.3969/j.issn.1003-6059.2012.01.013) [13] Jing S Y. A hybrid genetic algorithm for feature subset selection in rough set theory[J]. Soft Computing, 2014, 18(7): 1373-1382. DOI:10.1007/s00500-013-1150-3 [14] Pradipta Maji, Sushmita Paul. Rough set based maximum relevance-maximum significance criterion and gene selection from microarray data[J]. Int J of Approximate Reasoning, 2011, 52(3): 408-426. DOI:10.1016/j.ijar.2010.09.006 [15] Majdi Mafarja, Derar Eleyan. Ant colony optimization based feature selection in rough set theory[J]. Int J of Computer Science and Electronics Engineering, 2013, 1(2): 244-247. [16] 于洪, 杨大春. 基于蚁群优化的多个属性约简的求解方法[J]. 模式识别与人工智能, 2011, 24(2): 176-184. (Yu H, Yang D C. Approach to solving attribute reductions with ant colony optimization[J]. Pattern Recognition and Artificial Intelligence, 2011, 24(2): 176-184. DOI:10.3969/j.issn.1003-6059.2011.02.004) [17] 蒋瑜, 王燮, 叶振. 基于差别矩阵的Rough集属性约简算法[J]. 系统仿真学报, 2008, 20(14): 3717-3720. (Jiang Y, Wang X, Ye Z. Attribute reduction algorithm of rough sets based on discernibility matrix[J]. J of System Simulation, 2008, 20(14): 3717-3720.) [18] Yao Y Y, Zhao Y. Discernibility matrix simplification for constructing attribute reducts[J]. Information Sciences, 2009, 179(5): 867-882. [19] 蒋瑜. 基于差别信息树的Rough Set属性约简算法[J]. 控制与决策, 2015, 30(8): 1531-1536. (Jiang Y. Attribute reduction with rough set based on discernibility information tree[J]. Control & Decision, 2015, 30(8): 1531-1536.) [20] Jiang Y, Yu Y. Minimal attribute reduction with rough set based on compactness discernibility information tree[J]. Soft Computing, 2016, 20(6): 2233-2243. DOI:10.1007/s00500-015-1638-0