Existential generalization on attributes in formal concept analysis

Abstract

In almost every domain of life, there are situations where big databases are used. In these situations, extracting and exploiting information from such databases become extremely difficult. In Formal Concept Analysis, such information is called "patterns". When these data are transformed into formal contexts, patterns can be extracted, mainly in two forms: i) formal concepts describing object sets together with their common attributes, and ii) association rules including implications between attributes or objects. More often, the number of these patterns appears very large in a context, making them difficult to be studied. Many authors have proposed several methods of reducing the number of these patterns, notably in [7, 26, 27, 39, ?, 43, 44, 45]. Generalization of attributes is one of these methods. Generalization on attributes in a formal context is a method of aggregation of attributes in order to form new attributes called generalized attributes. It was first mentioned in [34] where the authors consider a taxonomy on items to extract relevant information in the formal context of a transactions database in the form of association rules. However, in this study, the authors considered both the items of the leaves of the taxonomy and that of the others nodes, called generalized items. With the type of generalization described in [27], the attributes which are put together do not appear in the generalized context, and then the generalized context has a size less than the initial one. Depending of the way attributes are grouped in a formal context, there are three types of generalization (see [27]): the universal generalization denoted by (8-generalization), the alpha-generalization denoted by (_-generalization) and the existential generalization denoted by (9-generalization). By reducing the size of the context trough a generalization, one expects to also reduce the size of the concept lattice. But that is not always the case, especially with the 9-generalization. In this work, we have brought our contribution to the resolution of the following problems: i) The study of the size of concept lattices: by studying a special case, we have shown that in the 9-generalization, the size of concept lattices can increase exponentially. Then, we have studied the worst case of increase one can get after an 9-generalization on a pair of attributes in a given formal context; and to round up, we have presented some conditions for which the 9-generalization stabilizes the size of concept lattices. ii) The search of a method of grouping attributes: here, we have proposed a way of grouping attributes such that the size of the concept lattice does not increase after an 9-generalization. By observing some existing similarity measures, we have found that they do not enhance a decision on wether the size of the concept lattice increases or no. This gave us enough reason to construct a new similarity measure compatible with the 9-generalization, and such that putting together similar attributes do not leads to more new concepts than putting together non similar ones. iii) The study of the relation between implications of the initial formal context and that of the generalized formal context: here, we have mainly studied the variation of the size of the set of all informative implications between the initial formal context and the generalized formal context.