DISCRETE CONCEPT FORMATION

Abstract

This thesis discusses a Discrete Concept Formation (DCF) theory. The theory is concerned with revealing an implicit discrete conceptual structure of a finite set of objects. The conceptual structure that we study is called Concept Lattice. Besides introducing the theory, this thesis also discusses a comprehensive set of Concept Lattice generation algorithms and several significant applications of the theory. The discussion on each Concept Lattice generation algorithm includes verification, time complexity analysis, implementation details, and examples of the algorithm. The actual implementations of these algorithms in the Lisp language arc included in the appendix. In particular, the Concept Lattice generation algorithm, Batch Algorithm, is shown to be superior in time complexity than most (if not all) existing Concept Lattice generation algorithms. In one of the applications of the DCF theory, a new search method on Concept Lattice has been invented to solve a class of problems called Subset Pattern Matching. This leads to an actual application in the area of Chinese computing that has resulted in two orders of magnitude improvement in search speed for a Chinese text input system. Several other diverse applications of the theory are also mentioned.