January 28, 2000
3:30pm

Rokia Missaoui
Université du Québec à Montréal

Mining from Data Fragments

In order to reduce the complexity of the knowledge discovery process, one can perceive the mining of a very large data set as the mining of a set of data fragments obtained from a decomposition of the original input.

In this talk, we first give some background about formal concept analysis (Ganter and Wille 1999), which is a conceptual clustering approach. From the context (O, P, R) describing a set O of objects, a set P of descriptors and a binary relation R between O and P, a unique ordered set can be derived, which describes the inherent lattice structure defining natural groupings and relationships among the objects and their descriptors. This structure is known as a concept lattice and allows the identification of concepts and rules.

We then present an approach to mining a set of data fragments resulting from a vertical decomposition of a relational table (or context). The approach makes use of formal concept analysis and explores the power of nested line diagrams, which express the nesting of concept lattices corresponding to individual fragments.

The approach is useful for many reasons:

• It enhances the readability and interpretation of the discovered knowledge by offering a good visualization tool.
• It offers a progressive and exploratory way to perform data mining.
• The discovery of concepts and rules from a given input can be handled by exploring independently and separately each fragment resulting from a vertical decomposition of that input.

Our contribution lies in the development of procedures for the following tasks:

1. building lattices at two and even higher levels of nesting,
2. creating mappings between nested and unnested lattices, and
3. generating concepts and rules from the nested structure without considering the input as a whole.

This work can be useful for distributed and parallel mining.

References

Ganter, B. & Wille, R . Formal Concept Analysis. Mathematical Foundations, Springer-Verlag, 1999.