基于相似度的集值信息系统属性约简算法

Attribute reduction in set-valued information system based on similarity

属性约简是粗糙集理论研究的重要内容之一.借助于属性集值的相似程度在集值信息系统上定义了一种新的相似度,用于度量知识的粗糙性,分析相关性质.在此基础上,提出一种基于相似度的启发式属性约简算法,以属性相似度为启发式信息,不需首先求核,尤其对核属性个数少甚至无核的集值信息系统计算约简更加有效.

As an important mathematic method to deal with knowledge fuzziness and knowledge uncertainty,rough sets theory has been paid more and more attention and widely used in various fields such as artificial intelligence,pattern recognition and classification,intelligent information processing.Attribute reduction is one of the important contents of the rough set theory.For set-valued information system attribute reduction,some scholars have conducted researches and achieved some progress in recent years.Though attribute reduction algorithm has obtained many essential achievements,there are still some important issues needed to be further resolved,especially fast and accurate algorithm of attribute reduction,which is still the hot spot of current research.However,most studies are aimed at core information system.For no core information system,there is not yet a relatively efficient algorithm.Based on the similar degree of attribute values,a new method to compute the similarity of attributes is defined in set-valued information system,and it is used to measure the roughness of knowledge and analyze some corresponding properties.A new improved algorithm of attribute reduction based on knowledge of the similarity is proposed and it is especially effective to set-valued information system without core.For core set-valued information system,the algorithm of this paper can seek an attribute reduction;for no core set-valued information system,the algorithm does not need to find out a core,reducing algorithm to calculate the time complexity and improving the efficiency of algorithm.At last,we use several classical databases from UCI repository to test the algorithm.The validity of the algorithm is illustratedby theoretical analysis and experimental results.Although the space complexity of the algorithm presented in this paper is as same as the existing heuristic attribute reduction algorithm,the latter wastes additional time on the calculation of core.