基于改进差别信息树的粗糙集属性约简算法
|
摘要
差别矩阵为属性约简提供了很好的思路,差别信息树能有效消除差别矩阵中的冗余元素,并实现对差别矩阵的压缩存储.然而,差别信息树既没有考虑"核"属性在消除差别矩阵中冗余元素的作用,也没有考虑属性序在压缩存储差别矩阵中非空元素的作用.对此,基于"核"属性和属性序关系,提出改进差别信息树,该树能进一步实现对差别矩阵中非空元素的压缩存储.最后,给出基于UCI数据库的仿真结果,并通过仿真结果验证该树的有效性.
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.
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.
引文
[1]Pawlak Z.Rough sets[J].Int J of Computer and Information Science,1982,11(5):341-356.
[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.
[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.)
[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.)
[13]Jing S Y.A hybrid genetic algorithm for feature subset selection in rough set theory[J].Soft Computing,2014,18(7):1373-1382.
[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.
[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.)
[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.
[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.
[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.)
[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.)
[13]Jing S Y.A hybrid genetic algorithm for feature subset selection in rough set theory[J].Soft Computing,2014,18(7):1373-1382.
[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.
[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.)
[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.