روش کاهش برای شبکه های مفهومی بر اساس نظریه مجموعه راف و کاربرد آن

Rough set theory and formal concept analysis are two complementary mathematical tools for data analysis. In this paper, we study the reduction of the concept lattices based on rough set theory and propose two kinds of reduction methods for the above concept lattices. First, we present the sufficient and necessary conditions for justifying whether an attribute and an object are dispensable or indispensable in the above concept lattices. Based on the above justifying conditions, we propose a kind of multi-step attribute reduction method and object reduction method for the concept lattices, respectively. Then, on the basis of the defined discernibility functions of the concept lattices, we propose a kind of single-step reduction method for the concept lattices. Additionally, the relations between the attribute reduction of the concept lattices in FCA and the attribute reduction of the information system in rough set theory are discussed in detail. At last, we apply the above multi-step attribute reduction method for the concept lattices based on rough set theory to the reduction of the redundant premises of the multiple rules used in the job shop scheduling problem. The numerical computational results show that the reduction method for the concept lattices is effective in the reduction of the multiple rules.

Formal concept analysis (FCA) [1] and [2] is a kind of important mathematical tool for conceptual data analysis and knowledge processing. In FCA, the data for analysis are described by formal context (U,A,R)(U,A,R), which consists of universe UU, attributes set AA and relation R∈U×AR∈U×A. Based on the formal context, we can construct some formal concepts and the set of all the above formal concepts forms a concept lattice. In FCA, the formal concept and the concept lattice are two central issues. Up to now, FCA has been applied to information retrieval, database management systems, software engineering and other aspects [3], [4], [5], [6] and [7]. In FCA, Wille first defined the formal concept as an ordered pair (X,Y)(X,Y) [1] and [2], where XX and YY are the sets of objects and attributes, respectively, and they uniquely determine each other. Then, several generalizations of the above formal concept can be found in the existing literature. For example, triadic concepts, each of which consists of three sets of objects, attributes and conditions under which objects may possess certain attributes, were introduced in [8]. Ferre etc. [9] replaced the attributes set of the above formal concept by logic expressions. Also, monotone concepts were introduced in [10]. As a tool for processing uncertain and incomplete information, rough set theory, in which the lower and upper approximations of an arbitrary subset of universe UU are the basic operators, was originally proposed by Pawlak [11] and [12]. In rough set theory, the data for analysis are described by information system (U,A,F)(U,A,F), which corresponds to the formal context in FCA and consists of universe UU, attributes set AA and relation FF between UU and AA. At present, rough set theory has been used for data analysis and data processing, such as data mining, knowledge discovery and so on [12], [13] and [14]. FCA and rough set theory are two kinds of complementary mathematical tools for data analysis and data processing [15] and [16]. Up to now, many efforts have been made to combine these two theories [16], [17], [18], [19], [20], [21], [22], [23], [24] and [25], in which the concept lattices based on rough set theory, including the attribute oriented concept lattice [17] and the object oriented concept lattice [15] and [16], are perspective concept lattices for knowledge representation and knowledge discovery. However, the concept lattices usually contain redundant attributes and objects. In this paper, in order to obtain the concept lattices with relatively less attributes and objects, we study the reduction of the concept lattices based on rough set theory, including the attribute oriented concept lattice and the object oriented concept lattice, and propose two kinds of attribute reduction methods and object reduction methods for the concept lattices, respectively. First, we present the sufficient and necessary conditions for justifying whether an attribute and an object are dispensable or indispensable in the above concept lattices. Based on the above justifying conditions, we propose a kind of multi-step attribute reduction method and object reduction method for the concept lattices, respectively. Furthermore, we define a suitable and simple discernibility function, and propose a kind of single-step reduction method for the concept lattices based on the above discernibility function. By means of the above two proposed reduction methods, we can remove the attributes and the objects, which are not essential for the structures and the hierarchical orders of the concept lattices, thus obtaining the reduct of the concept lattices. Additionally, we study the relations between the attribute reductions of the concept lattices in FCA and the attribute reductions of the information system in rough set theory in detail. Finally, by means of constructing a suitable formal context dynamically, we apply the above multi-step attribute reduction method for the concept lattices to the reduction of the redundant premises of the multiple rules used for solving the job shop scheduling problem (JSSP) [26] and [27]. The numerical computational results show that the reduction method for the concept lattices is effective in the reduction of the multiple rules. This paper is organized as follows. In Section 2, the concept lattices based on rough set theory, including the attribute oriented concept lattice and the object oriented concept lattice, are briefly reviewed. In Section 3, we give the sufficient and necessary conditions for justifying whether an attribute and an object are dispensable or indispensable in the above concept lattices, and propose a kind of multi-step attribute reduction method and object reduction method for the concept lattices, respectively. Also, we propose a kind of single-step reduction method for the concept lattices based on the defined discernibility functions in Section 4. In Section 5, the relations between the attribute reduction of the concept lattices in FCA and the attribute reduction of the information system in rough set theory are discussed. In Section 6, we apply the above multi-step attribute reduction method for the concept lattices to the reduction of the redundant premises of the multiple rules used for solving JSSP, and make numerical computations. Finally, some conclusions are given in Section 7.

In this paper, we study the reduction of the concept lattices based on rough set theory, and propose two kinds of attribute reduction methods and object reduction methods for the concept lattices, respectively. Additionally, we study the relations between the attribute reduction of the concept lattices in FCA and the attribute reduction of the information system in rough set theory in detail. At last, we apply the multi-step attribute reduction method for the concept lattices based on rough set theory to the reduction of the redundant premises of the multiple rules used for solving JSSP. The numerical computational results show that the reduction method for the concept lattices is effective in the reduction of the above multiple rules.