基于知识粒度的增量约简算法  

An incremental approach for reduction based on knowledge granularity

作　　者：景运革[1,2] 李天瑞[1] 

机构地区：[1]西南交通大学信息科学与技术学院,四川成都611756 [2]运城学院公共计算机教学部,山西运城044000

出　　处：《山东大学学报（工学版）》2016年第1期1-9,共9页Journal of Shandong University（Engineering Science）

基　　金：国家自然科学基金资助项目(61175047);国家自然科学基金委员会-中国工程物理研究院NSAF联合基金资助项目(U1230117)

摘　　要：在现实中,许多数据库都是动态变化的,非增量约简方法处理这些数据需要花费大量的时间和空间。增量技术是处理动态数据的有效方法。首先介绍了计算知识粒度的增量机制,然后提出了基于知识粒度的增量约简算法,当一些对象增加到决策表时,能够利用原有决策表的知识粒度和约简,快速计算出增加对象后的知识粒度和约简,并通过理论分析验证了增量方法可以减少计算属性约简的时间复杂度,最后用增量方法和非增量方法对UCI数据集进行一系列试验。试验结果表明,所提增量算法在处理动态数据时能够节省大量的计算时间。The object set in a decision table varied dynamically nowadays. It cost a lot of time for non-incremental algorithms solving reduction of dynamical data set. Incremental technique supplied an efficient and effective soluation to such dynamic data. An incremental mechanism for updating knowledge granularity was introduced and then an incremental approach for attribute reduction based on knowledge granularity was developed. With the existing knowledge granularity and reduction,the new reduction could be obtained by the proposed method when multiple objects were added to the decision table. Theoretical analysis validated that incremental approach could reduce complexity of time for computing attribute reduction. Experiments conducted on different data sets from UCI showed that the proposed incremental algorithm could achieve better performance than the non-incremental approach.

关 键 词：知识粒度 属性约简 增量学习 粗糙集理论 决策表 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]