Decision Logic In Formal Concept Analysis

Formal Concept Analysis (FCA), pioneered by R.Wille in mid 80’s, is an order-theoretic method for the mathematical analysis of scientific data. FCA is capable of describing the relationship of intent and extent and visualizing the generalization and instantiation of concepts by means of concept lattice, the core structure of FCA. Due to the advantages, FCA has been become a powerful tool for machine learning, information retrieval, software engineering and social network analysis.In FCA, performing knowledge achievement amounts to extracting at-tribute implications. Presently, much attention has been paid to the study of attribute implications and fuzzy attribute implications, and the results showed that FCA-based classifiers can achieve the competitive performance than other classifiers, but are less practicable due to the large number of extracted attribute implications. Thus, how to obtain an effective set of attribute implications is still a hot area of FCA. One of solutions is to develop and logically study de-cision implications, thus reduce redundant decision implications that do not matter the decision process, and obtain complete and non-redundant set of de-cision implications. Little work, however, has been done on this area. In this thesis, we make a systematic and in-depth investigation of decision implica-tions and fuzzy decision implications based on FCA. The results obtained not only enrich FCA theory, but also have potential applications in various fields that require decision-making. The main results and originalities are summa-rized as follows:(1) We describe the semantical and syntactical characteristics of decision implications. In the semantical aspect, we introduce the notions of "closure" and "unite closure", and present several theorems for determining complete-ness; in the syntactical aspect, we propose two inference rules, namely (Aug-mentation) and (Combination), and show that the two rules are complete with respect to the semantical aspect. As a special case, we derive the semantical and syntactical characteristics of decision context based decision implications. We also describe an approach to obtain a decision context from a given set of decision implications, and show that the given set is complete with respect to the decision context obtained;(2) By virtue of logical treatment of decision implications, we put for-ward to the so-called decision implication canonical basis. This basis takes decision premises as its premises and the closures of decision premises as its consequences. We prove that the basis is complete, non-redundant and of min-imal cardinality among all complete sets of decision implications. From the results, decision implication canonical basis with respect to decision context follows naturally as a special case of decision implication canonical basis. We also describe an algorithm to generate decision implication canonical basis and verify its effectiveness by experiments;(3) We describe the semantical and syntactical characteristics of fuzzy decision implications. By extending the results on decision implications, in the semantical aspect, we introduce the notion of completeness, and present several theorems for determining completeness; in the syntactical aspect, we derive three deduction rules, namely (F-Transformation), (F-Add) and (F-Sht), and prove that the three deduction rules are sound, complete and optimal with respect to the semantical aspect. We also derive the semantical and syntactical characteristics of fuzzy decision context based fuzzy decision implications. In addition, we describe an approach to obtain a fuzzy decision context from a given set of fuzzy decision implications, and show that the given set is complete with respect to the fuzzy decision context obtained;(4) Based on the results on fuzzy decision implications, we introduce the notion of FD-premise and put forward to the so-called fuzzy decision impli-cation canonical basis. We prove that the basis is complete, non-redundant and optimal. As a special case, we derive fuzzy decision context based fuzzy decision implication canonical basis, and show that it is also complete, non-redundant and optimal with respect to fuzzy decision context.