0
$\begingroup$

I have cluster consisting of two points and I am working with non-Euclidean distance. I wonder if it is appropriate to talk about center of cluster in this case and how we can interpret it? We can start with simpler case when distance is weighted Euclidean.

Update: Here is clarification. Assume we are using Manhattan distance to find centroid of our 2 point cluster. As far as I understand centroid is not unique in this case if we use PAM algorithm. We need to work with whole set of centroids for one cluster. Hence, clustering might produce random results on each iteration. It looks to me that problem is not well posed.

| improve this question | |
$\endgroup$
  • $\begingroup$ Can you be more specific?? I didn't understand the question. How can you have a cluster with only 2 points??? $\endgroup$ – hoaphumanoid Dec 25 '15 at 20:06
4
$\begingroup$

The easiest solution for a non-Euclidean cluster center is the medoid, as in the algorithm PAM. This works with arbitrary metrics, but unfortunately for a 2-element cluster the result by definition is random (by metric properties, each point is an equally good medoid).

Or you step back and rethink what the center is. It is the point which has the least squared error. So "all" you need to do is solve some math for your distance function, how to optimize this least-squares estimation. People have been solving such problems since Gauss. For example with the deviation abs(x-mu) the least-squares objective is minimized by the arithmetic mean, an the one dimensional result carries over to the n-dimensional case and thus Euclidean distance!

Obviously, this needs to be done for every distance function again.

So if you want to interpolate a center for an other distance function, solve that optimization problem (efficiently, but try to find an existing solution first, of course).

| improve this answer | |
$\endgroup$
  • $\begingroup$ If we increase number of points in the cluster are we guaranteed to have unique medoid in non-Euclidean case? I am guessing that some non-Euclidean metrics will have unique medoid and some not. To start, I am not sure if weighted Euclidean will have unique medoid. I read PAM description and it looks like it only takes "euclidean" and "manhattan" metrics. It looks like flexclust works with arbitrary metric, but I have not tried it yet. $\endgroup$ – user1700890 Dec 26 '15 at 14:36
  • $\begingroup$ Medoids are never unique, e.g. with the discrete metric. The algorithm PAM works with any metric - the implementation you have been looking at may have limitations. The flexclust R package is horribly slow (like anything that is pure R). $\endgroup$ – Has QUIT--Anony-Mousse Dec 26 '15 at 15:14
  • $\begingroup$ Thank you. Is there way to estimate non-uniqueness? How bad does it get? Is possible that set of medoids (for one cluster) is so big that whole clustering analysis is useless? $\endgroup$ – user1700890 Dec 26 '15 at 15:22
  • 1
    $\begingroup$ Does it matter? Never trust a clustering result, but analyze it carefully and draw conclusions. $\endgroup$ – Has QUIT--Anony-Mousse Dec 27 '15 at 0:33
1
$\begingroup$

I guess the centre of a cluster of two points is a point that is the same distance from each of them. Is there such a point in your system? If not, maybe you should go to the point in your space with the smallest difference in distance from each of your other points, in other words, C such that |d(A, C) - d(A, B)| is minimised, where A and B are the points in your cluster.

What distance metric are you using?

Are you planning to generalise this to clusters with more points?

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. I updated my question. My concern is that center of the cluster is not unique. I will surely expand to more points, it is just simpler to analyze question of uniqueness with two points. I would like to answer question of uniqueness with weighted Euclidean first. $\endgroup$ – user1700890 Dec 26 '15 at 14:54
  • 1
    $\begingroup$ If you have two points in a Manhattan space (0, 0) and (1, 1), what point would you want to use as the centre? The two points of minimum distance from them are (0, 1) and (1, 0). If you want a unique point, maybe you should decide a scheme for preferring a particular point over another. On the other hand, since Manhattan space is a subset of Euclidean space, maybe you can use the Euclidean centre (0.5, 0.5). $\endgroup$ – Deschutron Jan 29 '16 at 2:30

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.