一种基于C-Tree的属性约简增量式更新算法  

An incremental updating algorithm for attribute reduction based on C-Tree

作　　者：杨明[1] 吕静[1] 

机构地区：[1]南京师范大学计算机科学与技术学院,南京210046

出　　处：《控制与决策》2012年第12期1769-1775,共7页Control and Decision

基　　金：国家自然科学基金项目(60873176;61003116;61272222);江苏省自然科学基金重点重大专项项目(BK2011005);江苏省自然科学基金项目(BK2011782;BK2010263)

摘　　要：针对以往文献为克服基于差别矩阵的属性约简算法存储代价高的不足而提出的基于浓缩树(C-Tree)的高效属性约简算法仅考虑决策表不变的情况,提出了一种基于C-Tree的属性约简增量式更新算法,主要考虑对象动态增加情况下属性约简的更新问题.该算法可通过快速更新C-Tree,在动态求解核的基础上,利用原有的属性约简有效地进行属性约简的增量式更新.理论分析和实验结果表明,所提出的算法是有效可行的.To overcome the disadvantage of those attribute reduction algorithms based on the discernibility matrix with high space complexity,a compact storage structure called condensing tree（C-Tree） and corresponding efficient algorithms for attribute reduction are introduced in the existing reference,respectively.However,the mentioned algorithms in the reference only consider the case of the static decision table.Therefore,an incremental updating algorithm is proposed for attribute reduction based on C-Tree in the case of inserting,which only needs to modify the related nodes in the corresponding paths when updating the C-Tree.After dynamically computing a core,attribute reduction can be effectively updated by utilizing the old attribute reduction.Theoretical analysis and experiments show that the proposed algorithm is effective and feasible.

关 键 词：粗糙集 差别矩阵 浓缩树 核 属性约简 增量式更新 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]