6
$\begingroup$

I have a dataset which contains vectors generated from subtitles (each column represents a genre, each row is a movie name), my purpose is to find the most similar movie titles, I want to use different distance/similarity measurements and compare them, what is the best method to use?

For now, I tried L1 distance, cosine similarity, Euclidean distance, Mahalanobis Distance, I got the results of top n most similar titles, but all the results seem very reasonable, how can I compare them to see which method perform best?

I also tried to do k-means, when I implement K-means clustering, it used Euclidean distance by default, how to use other distance to implement K-means?Also any suggestions about other similarity measurements? Many thanks

$\endgroup$
1
  • $\begingroup$ K-means cannot use other distances. Use k-medoids instead. $\endgroup$ – Has QUIT--Anony-Mousse Jul 31 '19 at 15:42
2
$\begingroup$

I would try a different approach than clustering.

For now, I tried L1 distance, cosine similarity, Euclidean distance, Mahalanobis Distance

First, you could have a look at approximate string matching measures. These are likely to give you much better similarity results on a pair of movie titles. It's usually a good idea to use not only word-based measures but also character-based or char n-grams based measures.

how can I compare them to see which method perform best?

A proper evaluation framework would require annotating manually a large amount of pairs of titles as similar/not similar (or even a degree of similarity). Unless you have a lot of time, this is completely impractical because there is certainly a massive imbalance between positive and negative pairs. So instead you could use bootstrapping, which means running a few similarity measures on your data, extract the top N pairs for each measure, then manually annotate only these. It's likely that this would give you a high amount of (rare) positive cases, and you can build a labeled dataset by assuming that other instances are negative. It's obviously a simplification, otherwise you can take the time to annotate a lot of negative cases as well (it's still much faster than without bootstrapping, since you already have your positive cases).

my purpose is to find the most similar movie titles, I want to use different distance/similarity measurements and compare them, what is the best method to use?

Based on the dataset you have built, you can now train a supervised model, with a pair of titles as instance. You can use various similarity measures as features, and you should vary the type of similarity (char-based, ngram-based, word-based) across these features in order to provide the model with a diversity of characteristics.

Then you can predict the similarity between any two pairs. This gives you a graph of similarity relations between all the movies, from which you can extract groups which are similar together.

Note that this is just a general strategy, many parts of it can be refined/adapted to your data and of course it depends how much time you want to spend on this problem.

$\endgroup$
3
  • $\begingroup$ Hi thanks for the answer, by 'train a supervised model, with a pair of titles as an instance', the labelled data is something like each row: movie name, each column: different similarity measures with the distance values, but what is our label?? I don't understand this part, could you please be specific or maybe give me a sample? I feel if we make label manually it would not be accurate and for now I prefer to try clustering, I also used PCA to reduce the dimensions and compare the cluster results compare with the original cluster results, not sure if this makes sense. $\endgroup$ – Cecilia Jul 31 '19 at 9:00
  • $\begingroup$ The labels are positive (similar) or negative (not similar), they come from the annotated dataset you build by bootstrapping as I described above, you can use some of it for training and some of it for evaluation. I encourage you to try clustering anyway as it's more directly applicable, my method requires a fair amount of time. My intuition is that clustering might not work very well with many small clusters, especially because you probably have many movies not similar to any other. but I could be wrong :) $\endgroup$ – Erwan Jul 31 '19 at 11:20
  • $\begingroup$ Thanks, I've got some ideas. $\endgroup$ – Cecilia Jul 31 '19 at 13:54
2
$\begingroup$

I got the results of top n most similar titles, but all the results seem very reasonable, how can I compare them to see which method performs best?

I'm afraid there's no meaningful definition of "best" unless you specify some concrete metric. If the results in each case seem reasonable, then all you can do is be educated about the various distance metrics and decide which makes the most sense for your use-case. (For example, Euclidean distance measures spatial difference, while cosine similarity measures directional difference.)

I also tried to do k-means, when I implement K-means clustering, it used Euclidean distance by default, how to use other distance to implement K-means?

Keep in mind that k-means is designed for Euclidean distance, which is why many implementations (such as scikit-learn) do not allow the use of any other distance function. For many other distance metrics, such as cosine similarity, taking the mean of the points in the cluster is not appropriate, so you'd also need to replace the centroid-estimation function as well.

If you really want to, then the K-Means implementation from NLTK allows you to specify a custom distance metric. Just keep in mind the GIGO principle. If you violate the assumptions of the model, don't be surprised if you get poor results.

$\endgroup$
1
  • $\begingroup$ so basically I can only compare the similar titles and do some discussion, and in terms of k-means, maybe I can implement after feature extraction (like PCA) and compare them only by euclidean distance, seems to make more sense. $\endgroup$ – Cecilia Jul 30 '19 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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