Unsupervised topic modeling via implication clustering

This paper introduces a novel topic modeling framework using Formal Concept Analysis (FCA). By clustering the canonical basis of implications from a text, our method automatically discovers the optimal number of topics, offering a competitive, logic-based alternative to LDA.

Keywords

Unsupervised topic modeling, Implication clustering, Canonical basis, LDA, K-medoids, Silhouette score, fcaR

Traditional topic modeling algorithms like Latent Dirichlet Allocation (LDA) require the number of topics to be specified a priori, a significant limitation in exploratory data analysis. This paper introduces a novel, fully unsupervised framework for topic modeling based on Formal Concept Analysis (FCA). Instead of clustering documents directly, we first extract the canonical basis of implications from the document-term context. We then define a metric space on these implications and apply a clustering algorithm (e.g., K-medoids with silhouette score optimization) to group them. We demonstrate that the resulting clusters of implications correspond to coherent topics and, crucially, that the optimal number of clusters can be determined automatically from the data. We propose a method to project this implication-level clustering back onto the documents, yielding a document-topic assignment. Our experiments show that this FCA-based approach not only discovers the number of topics automatically but also achieves comparable or superior performance to LDA in terms of topic coherence and document classification purity.

Introduction

Unsupervised topic modeling is a fundamental task in Natural Language Processing (NLP), with Latent Dirichlet Allocation (LDA) being the most prominent method. A key practical challenge with LDA and similar methods is the need for the user to pre-specify the number of topics, $K$. An incorrect choice of $K$ can lead to topics that are either too broad or too granular, hindering interpretability.

In previous work, we have explored the idea of clustering implication bases to find “core implications” and used FCA for lexicon-based sentiment analysis. This paper unifies and extends these ideas to create a complete, unsupervised topic modeling pipeline. We argue that the implication basis of a document-term context provides a finer-grained representation of the semantic relationships than the document-term matrix alone. By clustering these logical rules, we can discover thematic structures more naturally.

Our contributions are:

1. a complete framework for topic modeling based on clustering the implication basis of a document-term context.
2. a method for automatically determining the number of topics by optimizing a clustering validity index (e.g., silhouette score) on the implication space.
3. an empirical comparison against LDA, demonstrating our method’s competitive performance and its ability to discover a meaningful number of topics without supervision.

Methodology

Our proposed pipeline consists of four main steps.

Step 1: Context and implication extraction

Given a corpus of documents, we construct a binary document-term matrix, which serves as our formal context $\mathbb{K}$. We then compute the canonical basis of implications, $\Sigma$, using an efficient algorithm.

Step 2: Defining the implication metric space

To cluster the implications, we must define a distance metric between them. As proposed in, for two implications $\varphi_1: P_1 \to Q_1$ and $\varphi_2: P_2 \to Q_2$, we define the closure distance as: $$d(\varphi_1, \varphi_2) = |(P_1 \cup Q_1)^+ \triangle (P_2 \cup Q_2)^+|$$ where $(\cdot)^+$ denotes the closure operator and $\triangle$ is the symmetric difference. This metric captures the semantic similarity of the rules by comparing the full set of attributes they entail.

Step 3: Implication clustering and topic discovery

We apply a clustering algorithm to the set of implications $\Sigma$ using the distance metric $d$. The K-medoids algorithm is a natural choice as it operates directly on a distance matrix and returns actual implications (the medoids) as cluster exemplars. Crucially, we can run K-medoids for a range of $K$ values (e.g., $K=2, \ldots, 20$) and use an internal validity index like the average silhouette score to automatically determine the optimal number of clusters, $K^*$. Each of the $K^*$ clusters of implications represents a discovered topic, and its medoid serves as an interpretable “prototype rule” for that topic.

Step 4: Document-topic assignment

With the topics (implication clusters) identified, we assign each document to a topic. We propose a “Nearest Medoid” strategy: for each document $g$ (represented by its attribute set $g^\uparrow$), we assign it to the topic whose medoid implication $\varphi_j$ is closest: $$\text{Topic}(g) = \arg\min_{j=1..K^*} d(g^\uparrow, (P_j \cup Q_j)^+)$$ where $d$ is the set distance. This provides a hard clustering of documents.

Work plan

• Weeks 1-2: formalize the complete pipeline and implement the document-assignment strategy in `fcaR`.
• Weeks 3-6: conduct experiments on standard NLP benchmark datasets (e.g., 20 Newsgroups, Reuters). For each dataset, run our method to discover $K^*$ and compare the resulting topics’ coherence (e.g., using NPMI score) against LDA run with the true number of topics.
• Weeks 7-9: perform a qualitative analysis of the discovered topics and their medoid implications to demonstrate interpretability.
• Weeks 10-12: write the full manuscript, positioning the work as a novel, logic-based alternative to probabilistic topic models.

Potential target journals

1. Expert Systems with Applications (Q1): an excellent venue, as the work is a novel application of an AI technique (FCA) to a well-known problem (topic modeling) with strong practical results.
2. Knowledge-Based Systems (Q1): similar to the above, it values novel methods for knowledge extraction and their application.
3. ACL/EMNLP Conferences (Top Tier): submitting to a top NLP conference would be a high-risk, high-reward strategy to introduce these FCA-based ideas to the mainstream NLP community.

Minimum viable article (MVA) strategy

The core contribution here is the unsupervised pipeline. The extension to fuzzy contexts is a natural next step.

• Paper 1 (The MVA - the unsupervised binary framework):
  • Scope: this paper details the complete pipeline for binary contexts as described above. It must include the method for automatically selecting $K^*$ and a solid empirical comparison against LDA on 2-3 standard datasets.
  • Goal: to establish the viability and competitiveness of the implication clustering approach for topic modeling.
  • Target venue: a strong application-oriented journal like Expert Systems with Applications or a conference like ECML-PKDD.
• Paper 2 (The fuzzy extension):
  • Scope: this paper extends the framework to handle term frequencies by using L-FCA. This involves defining a metric space on fuzzy implications, which is a non-trivial theoretical contribution. The experiments would then show how using term frequency information improves topic coherence and granularity compared to the binary model and standard topic models.
  • Goal: to demonstrate the added value of the fuzzy paradigm and make a theoretical contribution to the analysis of fuzzy implications.
  • Target venue: a journal that appreciates both the theoretical novelty and the application, such as the International Journal of Approximate Reasoning or Fuzzy Sets and Systems.