Abstract
We present a novel approach to the automatic acquisition of taxonomies or concept hierarchies from a text corpus. The approach is based on Formal Concept Analysis (FCA), a method mainly used for the analysis of data, i.e. for investigating and processing explicitly given information. We follow Harris distributional hypothesis and model the context of a certain term as a vector representing syntactic dependencies which are automatically acquired from the text corpus with a linguistic parser. On the basis of this context information, FCA produces a lattice that we convert into a special kind of partial order constituting a concept hierarchy. The approach is evaluated by comparing the resulting concept hierarchies with hand-crafted taxonomies for two domains: tourism and finance. We also directly compare our approach with hierarchical agglomerative clustering as well as with Bi-Section-KMeans as an instance of a divisive clustering algorithm. Furthermore, we investigate the impact of using different measures weighting the contribution of each attribute as well as of applying a particular smoothing technique to cope with data sparseness.
Introduction
Building ontologies and taxonomies is a fundamental task for knowledge-based systems, yet it remains a significant challenge known as the knowledge acquisition bottleneck. Manually encoding relationships—such as identifying that "car" and "bike" are both "vehicles"—is a slow, labor-intensive process that must be repeated for every new domain.
While previous research has leveraged the distributional hypothesis (the idea that words appearing in similar contexts share similar meanings) through clustering algorithms, these methods often produce "black box" results. Clustering can group similar terms but fails to explain why they are grouped or to provide the multi-layered, hierarchical structures required by knowledge engineers. This paper proposes a structured alternative using Formal Concept Analysis (FCA).
Methodology
The proposed approach follows a multi-stage pipeline to transform raw text into a structured hierarchy, moving from linguistic parsing to mathematical lattice construction.
NLP Preprocessing and Context Building
The process begins with a part-of-speech tagger and a statistical parser (LoPar) to extract syntactic dependencies, specifically verb-subject, verb-object, and verb-prepositional phrase pairs. Following the FCA framework, nouns are treated as objects and their associated verbs as attributes. For instance, if a corpus contains the phrases "rent a car" and "drive a car," the object car is assigned the attributes rentable and driveable.
Lattice Construction and Pruning
FCA generates a concept lattice, a mathematical structure representing every possible grouping of objects sharing common attributes. However, raw lattices are often too complex for direct use as taxonomies. To address this, the authors apply a pruning and compaction step to remove redundant or overly abstract nodes, transforming the lattice into a directed acyclic graph that serves as a concept hierarchy.
To refine the relationships, various statistical weighting measures—including Conditional Probability, Pointwise Mutual Information, and Resnik’s measure—were tested to filter out uninformative verb-noun pairs.
Experimental Evaluation
The method was evaluated across two domains:
- Tourism: Compared against a hand-crafted ontology of 293 concepts using a corpus of 118 million tokens.
- Finance: Compared against the GETESS project ontology (1,223 concepts) using a Reuters news corpus of 185 million tokens.
The FCA-based approach was benchmarked against Hierarchical Agglomerative Clustering (Single, Average, and Complete Linkage) and Bi-Section-KMeans.
Results and Discussion
FCA significantly outperformed traditional clustering methods in structural accuracy. In the Tourism domain, FCA achieved an F-Measure of 44.69%, compared to 38.57% for the best clustering baseline. In the Finance domain, FCA led with 38.85% versus 33.35% for clustering.
The primary driver of this success was recall. FCA is exhaustive, identifying valid sub-concept/super-concept relationships that clustering algorithms often miss by forcing objects into single branches. Furthermore, FCA provides "intensional" descriptions: each node is defined by the specific verbs its members share, making the hierarchy traceable and interpretable for human engineers.
Interestingly, despite the availability of complex measures, simple conditional probability proved to be the most robust weighting method. Additionally, the inherent sparseness of linguistic data (often >98% zero values) allowed the FCA algorithm to remain computationally efficient despite its theoretical exponential complexity.
Conclusion
This research demonstrates that Formal Concept Analysis is a powerful tool for overcoming the knowledge acquisition bottleneck. By providing explainable, high-recall hierarchies, it serves as an effective assistant for ontology engineering. Future work will address challenges such as polysemy (distinguishing different meanings of the same word) and the automatic labeling of abstract nodes with nouns rather than verbs, potentially using Hearst patterns to find hypernyms.
Summary updated