0

How to define a distance function when euclidean distance doesn't apply? For instance, say I have some data involves nationality. I'll probably assign a number to each nation, but for nations that have smaller difference in numbers doesn't mean that they are more prone to be in the same cluster as nations that have bigger difference in numbers.

Is it make sense if I just define a function that return 0 if two nations are the same, and return some positive integer otherwise? If so, how big that positive integer should be?

clwen
  • 207
  • 1
  • 3
  • 8

2 Answers2

3

You cannot use k-means then.

You don't only need to have a working distance function, but you also need to have a way of computing means that is appropriate for the distance function.

The arithmetic mean and the Euclidean distance work together. Their combination makes k-means terminate: updating the means reduces variance, and reassigning points also, thus it will converge.

However, what would be the mean of "american, canadian, canadian, chilean, chinese, chinese, american"?

Sorry, but k-means is only sensible for euclidean vector spaces where the distance and mean play together well. And it has other limitations, e.g. assuming that clusters are approximately equal in size and linear separable.

Has QUIT--Anony-Mousse
  • 39,639
  • 7
  • 61
  • 96
  • Thanks. If so, is there any other algorithms can be applied to this kind of data? (for clustering) – clwen Jun 28 '12 at 22:02
  • If you have a working distance function, you can use most distance and density based methods, e.g. DBSCAN. Or try Generalized DBSCAN, which doesn't need a distance, only a "neighbor" predicate, so you only need to define a binary "similar" property. – Has QUIT--Anony-Mousse Jun 29 '12 at 06:20
1

As with many questions, the answer is most likely "it depends". If your goal is simplicity, then using 0 for matches and 1 for non-matches may be fine. Using something other than 1 can also be thought of as the more general question of how you want to weight each of the variables (nation being only one such variable), and that really depends on how relevant a variable is to its membership in a cluster. Variables that are more important to membership should be upweighted, while less important ones weighted less. Of course, clustering is an unsupervised learning technique often used when the importance of a variable is not known.

If nation is an important variable and you don't mind added complexity, then perhaps you should consider using the geographical distance between countries as your distance function for that variable. Or, even more sophisticated would be a composite of distance, shared languages, shared religious beliefs, etc. Good luck!

jman
  • 111
  • 1