I have to cluster a movie dataset of 10000 movies. A movie has attributes like Genres, Actors, Directors, Year. Earlier I thought that we can use a simple clustering algorithm like k-medoids and the distance can be pre-computed between two movies by subtracting genres & actors.

Initialise d(movie1, movie2) = 0

d(movie1, movie2) -= number of common genres
d(movie1, movie2) -= number of common actors
d(movie1, movie2) -= 1 (if they have a common director)
d(movie1, movie2) -= 1 (if they belong to same decade)

Is this approach correct? Is k-medoids fast enough to cluster this dataset (I doubt it isn't)? If it isn't fast enough any better clustering algorithm and strategy to cluster this dataset?

  • $\begingroup$ What programming language is your code sample? What distance function are you using? What do you hope to do with the final clustering when you have it? (I don't think any clustering algorithm can be called "correct" / "incorrect" in the abstract.) $\endgroup$ May 4, 2014 at 16:04
  • $\begingroup$ Basically we are clustering all the movies this way that have at least one of the three genres ['Action', 'Animation', 'Adventure'] and we are clustering them using the distance measure I described. $\endgroup$
    – khirod
    May 4, 2014 at 16:23
  • $\begingroup$ Finally after clustering is done, we can lookup for an attribute say a specific actor which has a good frequency in a cluster's movies, and ask questions to users about "Do you like this actor?" and all this is done as a part of Movie Recommendation System. We are trying something different than collaborative filtering. About programmng language - Python (preferable), Java $\endgroup$
    – khirod
    May 4, 2014 at 16:27

1 Answer 1


There is no "correct" approach. Either the results are to your liking, or they aren't, so why not just try it out?

Negative distances may or may not work: if the k-medoids implementation you have uses squared distances, then you must not have negative values! If it minimizes the sum of distances, negative values should be okay; but nonstandard (i.e. not a distance by the mathematical definition of a distance).

10000 is not particularly large. You should be fine.

  • $\begingroup$ "Either it works or doesn't" appears to skirt some key issues. The concerns with any such algorithm are (1) Does it ever terminate? Are there conditions under which it will not terminate? (2) If it does terminate, what can we expect of its solution: will it be any good? If it is not guaranteed to be optimal, can we guarantee that it will be within some factor of optimal? These concerns come to the fore when negative "distances" appear in any distance-based algorithm. Another issue is that the d of this question isn't a distance at all (but it can be made into a Hamming distance). $\endgroup$
    – whuber
    May 5, 2014 at 15:05
  • $\begingroup$ I use "work" to refer to: produce satisfactory results. Because even a terminating, guaranteed optimal algorithm may yield a solution that doesn't meet the user needs. The point I was trying to make is to actually try if it works. K-Medoids does not need metric properties; and usually should not need the values to be positive. Just like single-link hierarchical clustering; which does work just fine with negative, non-metrical distances. $\endgroup$ May 5, 2014 at 15:43

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.