Finding Top-N Pseudo Formal Concepts with Core Intents

摘要

We discuss in this paper a method for finding Top-N Pseudo Formal Concepts. A pseudo formal concept (pseudo FC in short) can be viewed as a natural approximation of formal concepts. It covers several formal concepts as its majorities and can work as a representative of them. In a word, such a pseudo FC is defined as a triple (X, Y, S), where X is a closed set of objects, Y a set of primary features, S a set of secondary features. Then, the concept tells us that 1) all of the objects in X are associated with the primary features Y and 2) for each secondary feature y ∈ S, a majority of X is also associated with y. Therefore, X can be characterized not only exactly by Y but also naturally and flexibly by Y ∪ {y} for each secondary feature y. Our task is formalized as a problem of finding Top-N δ-Valid (τ,ρ)-Pseudo Formal Concepts. The targets can be extracted based on clique search. We show several pruning and elimination rules are available in our search. A depth-first branch-and-bound algorithm with the rules is designed. Our experimental result shows that a pseudo FC with a natural conceptual meaning can be efficiently extracted.