基于差别集的启发式属性约简算法

Heuristics Attribute Reduction Algorithm Based on Discernibility Set

属性约简是粗糙集理论重要研究内容之一,基于可分辨矩阵的属性约简方法需占用大量存储空间,不利于大数据集的处理.为此,引入差别集定义和基于差别集属性约简定义,并指出基于差别集属性约简本质上是在当前差别集中不断寻求关键属性的过程,并给出删除单个条件属性和删除条件属性集两种获取关键属性的属性约简方法,同时证明了这两种属性约简方法是正确的、完备的;进一步,为了获得最小属性约简,采用两个启发式信息来筛选关键属性;在上述基础上,设计基于差别集的启发式属性约简算法.最后,通过实例和实验验证了该算法的有效性和高效性.

Attribute reduction is one of important research concept in rough set theory. The method of attribute reduction based on dis- cernibility matrix need more high cost of storage space, and the method is not benefit for the huge data sets. To overcome this short- coming, firstly, the definitions of discernibility set and attribute reduction based on discernibility set are proposed. Secondly, it is pointed that the hypostasis of attribute reduction based on discernibility set is the process of searching the key attributes in the current discernibility set. And then, the two methods of obtaining the key attributes through deleting single condition attribute and condition attribute set are present, and it is proved that the acquired attribute reduction form above two methods are correct and complete. For obtaining minimal reduction, in addition, two heuristic information are used to search the key attributes. Based above, a heuristic at- tribute reduction algorithm based on discernibility set is proposed. Finally, both of theoretical analysis and experimental results show that the algorithm is effective and efficient.