属性最小约简的增量式算法

An Incremental Arithmetic for the Smallest Reduction of Attributes

知识约简是KDD(数据库中的知识发现)中的重要步骤,在粗糙集合理论中,对属性约简原理和方法有专门的论述,许多学者对约简算法进行研究.但是,这些研究几乎都是针对静态数据的,而数据库是动态的.本文提出了当增加数据库记录后,如何在已有最小属性约简簇集的基础上求解新的最小属性约简簇集的算法ASRAI,证明了该算法的正确和分析了它的时间复杂性.然后又提出了对这个算法的改进算法IASRAI.

Reducing for knowledge is an important step in KDD.In theory of rough sets,the principle and methods of the reducing for attribute are specially discussed.Many scholars work over arithmetic of the reduction,but the researches are almost for static data.However databases are dynamic.The paper provides the arithmetic,ASRAI,to get the sets of the new smallest attribute reductions from to the old sets ofter a record is added to the database.The arithmetic is proved to be right and the time complexity of the arithmetic is analyzed.Then the improved arithmetic,IASRAI,is provided.