2
$\begingroup$

Given some large set of documents, how would one find a human usable hierarchical clustering to them (ie. place them into a file system such that one can find a document in the minimal time)?

My initial intuition was to use HDBSCAN (using text embeddings and cosine similarity), but this turns out to have too many intermediate nodes in the tree (in general, the number of intermediate nodes equals the number of leaf nodes). I thought some greedy pruning metric for intermediate notes with two few children would solve this, but this is trivially incorrect; the pruning metric is hard to get right such that we have a useful tree that we have neither too few nor too many internal nodes (in practice, ended up with either 1 or 10,000 internal nodes). Then I thought that we could use a tree index (such as the one implemented by llama index), but this seems relatively inefficient/prone to hallucination as it just asks an LLM to either create a new internal node or place it within an existing path.

$\endgroup$

1 Answer 1

3
$\begingroup$

One thing you might like to consider is hierarchical topic modelling.

But first, let's talk about topic modelling.

One way to think about a document is that it covers certain topics. A news article about a new stadium, for example, might involve the topics "professional sport", "urban planning", and "finance".

A document can be thought of as a frequency histogram of topics. In turn, a topic can be thought of as a frequency histogram of words.

Note that this is more general than cosine similarity based on words, because a word can have different meanings in different topics; the word "play", for example, belongs to the topics "sport", "theatre", and "early childhood education", all with different meanings.

The problem is, given a bunch of documents, to discover the topics and how much each document "belongs to" each topic.

The model that we typically use is Latent Dirichlet Allocation, which assumes that documents "choose" their topics according to a Dirichlet distribution. The intuition behind this is a little difficult to explain, but something that may help is the so-called "Chinese restaurant process".

Suppose we have a restaurant where customers enter one by one. The first customer sits at table 1. Let $\alpha$ be a parameter between 0 and 1. Then each subsequent customer makes a choice:

  • With probability $\alpha$, they sit at a new table.
  • With probability $1-\alpha$, they sit at an existing table, in proportion to the number of people already at that table.

The resulting distribution of seating is a random sample of a Dirichlet process. If the restaurant has an unlimited number of tables, the resulting distribution is an infinite-dimensional Dirichlet distribution.

The reason why this is a plausible model is that topics that the process that generates it is self-reinforcing: a topic that is already popular becomes even more popular as more documents get written.

The LDA problem can be solved by standard Bayesian techniques, such as Gibbs sampling.

It is straightforward in principle to extend the idea to inferring multiple levels of "topic", a Hierarchical Dirichlet Process. Or, alternatively, you could use a cosine-like measure (e.g some variant of tf-idf) on topics, rather than documents, to cluster them.

This should give you enough information to start looking, if you want to go down this rabbit hole.

$\endgroup$
2
  • $\begingroup$ Why would we use a Hierarchical Dirichlet Process instead of a hierarchical Latent Dirichlet Allocation given the points made above? If we choose a HDP, isn’t this functionality the same as running DBSCAN over embedding, getting some level 1 clusters, clustering the level 1 into level 2 clusters, etc.? $\endgroup$
    – olivarb
    Commented Jun 11 at 23:21
  • $\begingroup$ There are lots of possible models, for sure. But the difference between this and clustering (e.g. DBSCAN) is that a hierarchical generative model is meant to be a (statistical) model of the process by which the documents were generated. The generative model tries to "explain" the data, whereas clustering tries to "fit" the data. $\endgroup$
    – Pseudonym
    Commented Jun 11 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.