Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Chebyshev distance for K-means

Subject: Chebyshev distance for K-means

From: Sandro Saitta

Date: 1 May, 2007 04:43:50

Message: 1 of 8

Hello,

I want to try k-means with the chebyshev distance. I know it is
possible to use euclidean and city block distances but what about
chebyshev? Is there a way to use this distance with the standard
k-means matlab function?

Thanks.
Sandro.

Subject: Chebyshev distance for K-means

From: Peter Perkins

Date: 1 May, 2007 06:22:11

Message: 2 of 8

Sandro Saitta wrote:
> Hello,
>
> I want to try k-means with the chebyshev distance. I know it is
> possible to use euclidean and city block distances but what about
> chebyshev? Is there a way to use this distance with the standard
> k-means matlab function?

K-means (the algorithm) requires two things:

1) a distance measure, and
2) a way to compute the centroid of a cluster so as to minimize the sum of
point-to-centroid distances.

There are lots of distance measures, but few have a simple computation for the
centroid. For example, the default distance used by KMEANS (the function) is
most definitely NOT "Euclidean", but rather "squared Euclidean", because for the
latter, the centroid is the arithmetic mean, while for the former, it is a
difficult computation requiring an iterative solution (the calculation has a
hyphenated name attached to it that escapes me).

That's why no Chebyshev distance in KMEANS.

That being said, there is a "coordinate-free" version of K-means (the algorithm)
that does not require a centroid calculation. However, it is not the standard
thing that most people want, and requires a distance matrix rather than raw
data, limiting its use for large datasets (which is what most people use K-means
for). Is that of interest to you?

It's certainly also possible to modify KMEANS to use Chebyshev distance and some
unsuitable centroid calculation, but you're on your own there.

- Peter Perkins
   The MathWorks, Inc.

Subject: Chebyshev distance for K-means

From: Sandro Saitta

Date: 1 May, 2007 08:22:02

Message: 3 of 8

Thanks for your answer. I'm not sure to understand all your
explanations. The Manhattan, Euclidean (more precisely SqEuclidean)
and Chebyshev are three special cases of the Minkowski distance.

If p is the parameter of the Minkowski distance, then Euclidean
distance corresponds to p=2, Manhattan to p=1 and Chebyshev to
P=infinity.

I base myself on a paper which compares clustering with Euclidean,
Manhattan and Chenyshev distances for clustering using SOM (that why
I thought of comparing Chebyyshev with sqEuclidean). In a book by
Webb, Chebyshev is defined as:

d(x,y) = sum(abs(x_i - y_i))

Starting from this, I don't understand why it could not simply
replace the standard sqEuclidean distance.

Thanks in advance for your help.
Regards.

Subject: Chebyshev distance for K-means

From: Peter Perkins

Date: 1 May, 2007 11:20:57

Message: 4 of 8

Sandro Saitta wrote:
> Thanks for your answer. I'm not sure to understand all your
> explanations. The Manhattan, Euclidean (more precisely SqEuclidean)
> and Chebyshev are three special cases of the Minkowski distance.
>
> If p is the parameter of the Minkowski distance, then Euclidean
> distance corresponds to p=2, Manhattan to p=1 and Chebyshev to
> P=infinity.
>
> I base myself on a paper which compares clustering with Euclidean,
> Manhattan and Chenyshev distances for clustering using SOM (that why
> I thought of comparing Chebyyshev with sqEuclidean). In a book by
> Webb, Chebyshev is defined as:
>
> d(x,y) = sum(abs(x_i - y_i))
>
> Starting from this, I don't understand why it could not simply
> replace the standard sqEuclidean distance.

What's the formula to compute the centroid? For example, the centroid for city
block distance is NOT the componentwise arithmetic mean, it's the componentwise
median. If you can compute an appropriate centroid easily for the Chebyshev
distance, then you're on your way. I haven't thought about this at all, and
there may an obvious answer for the centroid.

K-means partitions your data. The criterion for the partition is that the sum
of the point-to-centroid distances is minimized over all partitions. It makes
little or no sense to find a partition that minimizes that criterion if the
centroid itself is not the point that minimizes the point-to-centroid distances
within a cluster.

Subject: Chebyshev distance for K-means

From: Sandro Saitta

Date: 2 May, 2007 04:06:03

Message: 5 of 8

Thanks for your help. I didn't see the problem like this. Therefore,
it means that if I want to compare K-means with different distance
function I should choose measures such as Euclidean, Manhattan and
Correlation for example.

Subject: Chebyshev distance for K-means

From: alex kullik

Date: 12 May, 2008 13:54:03

Message: 6 of 8

Peter Perkins <Peter.PerkinsRemoveThis@mathworks.com> wrote
in message <f174cj$t80$1@fred.mathworks.com>...
> Sandro Saitta wrote:
> > Hello,
> >
> > I want to try k-means with the chebyshev distance. I
know it is
> > possible to use euclidean and city block distances but
what about
> > chebyshev? Is there a way to use this distance with the
standard
> > k-means matlab function?
>
> K-means (the algorithm) requires two things:
>
> 1) a distance measure, and
> 2) a way to compute the centroid of a cluster so as to
minimize the sum of
> point-to-centroid distances.
>
> There are lots of distance measures, but few have a simple
computation for the
> centroid. For example, the default distance used by
KMEANS (the function) is
> most definitely NOT "Euclidean", but rather "squared
Euclidean", because for the
> latter, the centroid is the arithmetic mean, while for the
former, it is a
> difficult computation requiring an iterative solution (the
calculation has a
> hyphenated name attached to it that escapes me).
>
> That's why no Chebyshev distance in KMEANS.
>
> That being said, there is a "coordinate-free" version of
K-means (the algorithm)
> that does not require a centroid calculation. However, it
is not the standard
> thing that most people want, and requires a distance
matrix rather than raw
> data, limiting its use for large datasets (which is what
most people use K-means
> for). Is that of interest to you?
>

I need this "coordinate-free" version of kmeans! Where can i
get it?

Subject: Chebyshev distance for K-means

From: Ashraful Alam

Date: 16 Sep, 2013 15:39:06

Message: 7 of 8

"Sandro Saitta" wrote in message <ef557a7.1@webcrossing.raydaftYaTP>...
> Thanks for your answer. I'm not sure to understand all your
> explanations. The Manhattan, Euclidean (more precisely SqEuclidean)
> and Chebyshev are three special cases of the Minkowski distance.
>
> If p is the parameter of the Minkowski distance, then Euclidean
> distance corresponds to p=2, Manhattan to p=1 and Chebyshev to
> P=infinity.
>
> I base myself on a paper which compares clustering with Euclidean,
> Manhattan and Chenyshev distances for clustering using SOM (that why
> I thought of comparing Chebyyshev with sqEuclidean). In a book by
> Webb, Chebyshev is defined as:
>
> d(x,y) = sum(abs(x_i - y_i))
>
> Starting from this, I don't understand why it could not simply
> replace the standard sqEuclidean distance.
>
> Thanks in advance for your help.
> Regards.

Subject: Chebyshev distance for K-means

From: Ashraful Alam

Date: 16 Sep, 2013 15:44:07

Message: 8 of 8

hello sir,
i am making my project on image segmentation using fcm clustering method. i have read all the discussion described above. i am intereted to know that " Can chebyshev distance measure be applied on fcm clustering method, if so then what will be the matlab funtion for fcm clsterin method?

thank you sir

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us