Text classification based on n-grams and similarity

Question

I have tried to cluster hundred texts using k-means clustering. I would like to consider other algorithms to group text based on their content and try to spot news not related to other news (topic different). I would like to know if there is some other method/algorithm that could be used to classify text into two or more groups based on their level of similarity. Let’s say I have thousands of text that use the same keywords but in different context. Some text may have the same sentence structure, for example:

The pen is on the table
The black pen is on the table. 
Where is my pen? Your pen is on the table.
I cannot find my pen. I was using it a few minutes ago.

I would like to be able to cluster the sentences above based on their structure, i.e. using n-grams with n manually set.

In this way I should be able to include the first three sentences in the same cluster, as their level of similarity in using same/similar words is higher compared to the last sentence. It is about compute for each sentence the similarity with others.

Do you have any idea on how I could do that?

Answer 1

First of all, both in your question and your tags, you used Clustering and Classification interchangeably. Be careful as they are totally different problems. I give you a comprehensive tour on how to encode your texts and find similarities so you will be fine doing any of them.

Classic Solution

As you mentioned, n-gram modeling and using Bag of Words variants (for example Tf-Idf) is the classic solution. There are points about this approach:

1. It does not model the order of words in sentences. So each document/sentence is modeled as a set of vocabularies regardless of the sequence of their positions. With n-gram model where n is larger than 1, you capture some concurrences of the words but still far from understanding the text.
2. TF-IDF is sparse by nature (there are huge amount of dimensions and a huge fraction of zero values in the matrix). For short documents (like your example sentences), it will be end up in vectors with a few values and a huge amount of zeros in other dimensions. You will need to reduce that dimensionality as I will explain.
3. It can not handle out of vocabulary words in case you will use it in a classification or text search problem.
4. The good thing about it is that it is pretty simple and works as a basic algorithm for such a task. The information theoretic concepts behind TF-IDF, beautifully weights words in the document e.g. stop-words will be automatically ignored.

How To

1. Generate your TF-IDF matrix
2. Apply Singular Value Decomposition to your matrix to reduce the dimensionality to k dimensions where k is the number of different topics in your corpus. You get back a $m\times k$ matrix back which is the reduced version of your TF-IDF. $n$ is the number of your documents and $k$ the number of different topics in it
3. You need to simply run your clustering algorithm on this matrix and get your results.

What you did above is called Latent Semantic Analysis. The best topic modeling out of BoW model.

How To Choose $k$

There is not a final answer to this question. Maybe use different values for $k$ and using t-SNE or UMAP (actually use UMAP! I just mentioned t-SNE for sake of completeness of my answer but it is too stochastic and non-parametric) for visualizing your data in 2 dimensions and try to guess what is the best $k$. It will be just a guess as you lose information by reducing dimension to 2, however better than nothing! There are methods to help this as well e.g. if clusters are gaussian enough or separated enough, you may use Elbow method. Please note that Clustering problem has no evaluation so at the end of the day, it is just a smart search.

Classic Solution with Modern Tools

Increase the usage of UMAP in the above pipeline. It is a pretty strong nonlinear dimensionality reduction and visualization algorithm. You can drectly feed your TF-IDF to UMAP and see the results or after applying SVD, try to use UMAP for visualization and dimensinality reduction.

Modern Approaches to NLP/NLU

Neural-based language modeling has a long history which is out of scope here, but in 2018, Google released an algorithm which was a breakthrough in NLP and is widely used nowadays. It is called BERT. A startup called HuggingFace implemented an easy-to-use software package for BERT in Pytorch and Tensorflow called Transformers. For your use-case, I recommend another package from Technical University of Darmstadt in Germany called sentence-transformers which is based on SBERT (Sentence-BERT). You can easily find sample codes for document similarity search in their repo, for example this is an exact solution to your problem.

In case of further questions please just drop a comment.

Good Luck!