A fast algorithm for generating concepts

The concept lattice, the core data structure in the formal concept analysis, has been used widely in machine learning, data mining, etc. In the formal concept analysis, researching on constructing the concept lattice efficiently is one of the important contents. This paper presents a new algorithm called IETreeCS (Concept Sets based on Intension and Extension Tree) based on the IE-Tree (Intension and Extension Tree) and characteristic space partitions. The IETreeCS algorithm firstly defines an IE-Tree, and then it converts the formal context into the IE-Tree to reduce the storage of data sets. The paper also defines characteristic spaces and describes how to partition a characteristic space on the basis of the IE-Tree, and finally presents an integrated algorithm that generates all concepts efficiently from a binary relation. The experimental results show that the IETreeCS algorithm performs much better than the NextClosure and SSPCG algorithms in the large-scale sparse data sets or distributed data sets.