Abstract: 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 research and achieved some progress in recent years. Though attribute reduction algorithm have 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 illustrated by 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.