On the efficient stability computation for the selection of interesting formal concepts

Non-redundant implicational base of formal context with constraints using SAT

An implicational base is knowledge extracted from a formal context. The implicational base of a formal context consists of attribute implications which are sound, complete, and non-redundant regarding to the formal context. Non-redundant means that each attribute implication in the implication base cannot be inferred from the others. However, sometimes some attribute implications in the implication base can be inferred from the others together with a prior knowledge. Regarding knowledge discovery, such attribute implications should be not considered as new knowledge and ignored from the implicational base. In other words, such attribute implications are redundant based on prior knowledge. One sort of prior knowledge is a set of constraints that restricts some attributes in data. In formal context, constraints restrict some attributes of objects in the formal context. This article proposes a method to generate non-redundant implication base of a formal context with some constraints which restricting the formal context. In this case, non-redundant implicational base means that the implicational base does not contain all attribute implications which can be inferred from the others together with information of the constraints. This article also proposes a formulation to check the redundant attribute implications and encoding the problem into satisfiability (SAT) problem such that the problem can be solved by SAT Solver, a software which can solve a SAT problem. After implementation, an experiment shows that the proposed method is able to check the redundant attribute implication and generates a non-redundant implicational base of formal context with constraints.

Efficient Mining Support-Confidence Based Framework Generalized Association Rules

Mining association rules are one of the most critical data mining problems, intensively studied since their inception. Several approaches have been proposed in the literature to extend the basic association rule framework to extract more general rules, including the negation operator. Thereby, this extension is expected to bring valuable knowledge about an examined dataset to the user. However, the efficient extraction of such rules is challenging, especially for sparse datasets. This paper focuses on the extraction of literalsets, i.e., a set of present and absent items. By consequence, generalized association rules can be straightforwardly derived from these literalsets. To this end, we introduce and prove the soundness of a theorem that paves the way to speed up the costly computation of the support of a literalist. Furthermore, we introduce FasterIE, an efficient algorithm that puts the proved theorem at work to efficiently extract the whole set of frequent literalets. Thus, the FasterIE algorithm is shown to devise very efficient strategies, which minimize as far as possible the number of node visits in the explored search space. Finally, we have carried out experiments on benchmark datasets to back the effectiveness claim of the proposed algorithm versus its competitors.

On the Computation of Concept Stability Based on Maximal Non-Generator for Social Networking Services

The concept stability measure under the Formal Concept Analysis (FCA) theory is useful for improving the accuracy of structure identification of social networks. Nevertheless, the stability calculation is an NP-complete task which is the primary challenges in practical. Most existing studies have focused on the approximate estimate to calculate the stability. Therefore, we focus on introducing the Maximal Non-Generator-based Stability Calculation (MNG-SC) algorithm that directly deals with accurate stability calculation to pave the way for FCA’s application in structures identification of social networks. Specifically, a novel perspective of stability calculation by linking it to Maximal Non-Generator (MNG) is first provided. Then, the equivalence between maximal non-generator and lower neighbor concept is first proved, which greatly improves scalability and reduces computational complexity. The performed experiments show that the MNG-SC outperforms the pioneering approaches of the literature. Furthermore, a case study of identifying abnormal users in social networks is presented, which demonstrates the effectiveness and potential application of our algorithm.