关键词: 粗糙集理论, 信息系统, 属性约简, 时间复杂性

Abstract: This paper proposes a new attribute reduction algorithm for information systems.For that，the paper，firstly constructs the correlation between information systems and relation matrix，studies new and relatively reasonable formulas measuring attribute significance from the viewpoint of relation matrix，and uses the new formulas as heuristic information to design a new attribute reduction algorithm.Compared with the existed attribute reduction algorithm，the algorithm developed in this paper can avoid repeatedly calculating important value of unimportant attributes by gradually deleting unimportant attributes from searching space.Besides，its time complexity has been analyzed in detail，and a real example and experimental results demonstrate both its feasibility and effectiveness.

Key words: rough set theory, information systems, attribute reduction, time complexity