Covering Concept Lattices with Concept Chains

摘要

The total number of concepts in a concept lattice tends to grow exponentially with the size of a context. There are numerous methods for selecting a subset of concepts based on some interestingness measure. We propose a method for finding interesting concept chains instead of interesting concepts. Concept chains also correspond to a certain visual rearrangement of a binary data table called a seriation. In a case study on the performance data of 852 students 80% of the corresponding formal context was covered by a single concept chain. We present three heuristic algorithms (MS-Chain, FL-Sort, KM-chain) for finding the concept chain cover in an efficient manner.