Abstract: Association rule discovery, as a kernel task of data mining, has been studied widely. Concept lattice, induced from a binary relation between objects and features, is a very useful formal tool and has been used in many fields. It realizes the unification of concept intension and concept extension, represents the association between objects and features, and reflects the relationship of generalization and the specialization among concepts, so it is fit for discovering the potential concept below the data. In this paper, the relationship between concept lattice and association rule discovery is analyzed. Then, the structure of node in lattice is modified according to the requirement, while two algorithms are developed for constructing the corresponding lattice incrementally and for extracting association rules, where some theorems and properties are used to reduce the number of discovered rules. Finally, the complexity problem is discussed, and the corresponding experimental results are given.