Second Attribute Algorithm Based on Tree Expression

One view of finding a personalized solution of reduct in an information system is grounded on the viewpoint that attribute order can serve as a kind of semantic representation of user requirements. Thus the problem of finding personalized solutions can be transformed into computing the reduct on an attribute order. The second attribute theorem describes the relationship between the set of attribute orders and the set of reducts, and can be used to transform the problem of searching solutions to meet user requirements into the problem of modifying reduct based on a given attribute order. An algorithm is implied based on the second attribute theorem, with computation on the discernibility matrix. Its time complexity is O(n ²× m) (n is the number of the objects and m the number of the attributes of an information system). This paper presents another effective second attribute algorithm for facilitating the use of the second attribute theorem, with computation on the tree expression of an information system. The time complexity of the new algorithm is linear in n. This algorithm is proved to be equivalent to the algorithm on the discernibility matrix. Supported by the National Natural Science Foundation of China under Grant No. 60175023 and the National Basic Research 973 Program of China under Grant No. 2004CB318103. Su-Qing Han received the M.S. degree from Shanxi University, China, in 2000 and Ph.D. degree from Institute of Automation, the Chinese Academy of Sciences in 2005. She is currently an associate professor in the Department of Mathematics, Taiyuan Normal University, China. Her current research interests include rough sets, machine learning and data mining. Jue Wang is a professor of computer science and artificial intelligence at Institute of Automation, Chinese Academy of Sciences. He graduated on computer science and artificial intelligence from Graduate School, Univ. of Science and Technology of China in 1981. His research interests include knowledge representation, expert system, artificial neural network, genetic algorithm, knowledge discovery in databases and methodology in AI.