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.
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:
- 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.
- 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.
- It can not handle out of vocabulary words in case you will use it in a classification or text search problem.
- 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.
- Generate your TF-IDF matrix
- 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
- 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$
Just visualize! 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) for visualizing your data in 2 dimensions and try to guess what is the best $k$. Please note that Clustering problem has no evaluation. At the end of the day it is 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.