5
$\begingroup$

I have just completed a simple exercise with 2 variables (X and Y) to understand how K-Means clustering works. The results look like this,

Simple K-Means Clustering Result

My questions is, if I have another column Z, how should the scatter plot be plotted to include the new variable Z? Would a 3 dimensional scatter plot chart be required?

And how do I calculate the Euclidean distance between the coordinates for X,Y and Z?

To clarify, I am not looking for a software like R or Weka to solve the problem but more on understanding the details and how the calculation works.

$\endgroup$
  • $\begingroup$ how to make k mean algorithm, and formula $\endgroup$ – user39802 Feb 10 '14 at 4:10
  • $\begingroup$ Welcome to the site, @bhawanamathur. This isn't an answer to the OP's question. Please only use the "Your Answer" field to provide answers. If you have your own question, click the [ASK QUESTION] at the top of the page & ask it there, then we can help you properly. Since you are new here, you may want to read our tour page, which contains information for new users. $\endgroup$ – gung - Reinstate Monica Feb 10 '14 at 4:22
  • $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post - you can always comment on your own posts, and once you have sufficient reputation you will be able to comment on any post. $\endgroup$ – mpiktas Feb 10 '14 at 8:54
10
$\begingroup$

You are talking about two distinct problems here

  1. How do I visualise what k-means is doing in N>2 dimensions
  2. How do I calculate k-means in N>2 dimensions

The second one is much easier than the first to answer.

To calculate the Euclidean distance when you have X, Y and Z, you simply sum the squares and square root. This works for any number of dimensions

$D=\sqrt{\sum_i X_i^2}$

The first part, visualisation, is much harder, but also has no right answer - it is simply a tool for checking that it is doing what you think it is, and for understanding what is going on. If N gets very large, there is no simple way to do this.

For three dimensions, there are a couple of common approaches, with their own pros and cons:

  • 3D chart: You see things as you do in the real world, but you will really need to be able to rotate the image to get a feel for depth
  • Colour in the points: This is quite a nice approach, use red say for the lowest Z value and blue for the highest Z value, and then the spectrum between the two. The K-Mean centre will then have the "average" colour of the cluster.

For higher dimensions you have to resort to more approximate techniques:

  • Slices/projections: Drop one or more dimensions and project or slice onto a lower (i.e. 2D) number of dimensions. This gives you a feel for what's going on, but you'll need a lot of them to check the K-Means are in the centres (and the wrong slices/projections might completely miss the interesting structure)
  • Dimension reduction: Starting to get really hard work now (much more complex than K-Means itself). You can attempt to use things like PCA, either locally for each cluster, or globally, to find planes that are "interesting" to look at, and just plot those.

Specific to K-Means, and particularly useful when K is low (e.g. 2), you can plot the density of points at distances on the projection between a pair of clusters.

For example, suppose we go back to 2D and have a scatter chart like this:

KMeans Scatter Graph

Where the two big blobs are the KMeans centres, and I have added the line that passes through the two points. If you perpendicularly project each point onto that line, then you can view the distribution of the points around each centre like so:

KMeans dots graphs

Where I have marked on the location of the means with the thick lines. The second graph can be drawn regardless how many dimensions you are working in, and is a way of seeing how well separated the clusters are.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Don't compute Euclidean distance.

K-means minimizes the within-cluster variance aka: WCSS.

http://en.wikipedia.org/wiki/K-means_clustering

Then your question should be obvious. Sum of squared deviations, sum over all dimensions.

It is equivalent, but misleading, to think of k-means as of "minimizing the squared distances". The problem is that k-means cannot optimize arbitrary distances. The mean is not compatible with arbitrary distances, but it is a least squares estimate (in each single dimension).

So don't use Euclidean distances in the first place; use Within-Cluster-Sum-of-Squares (which will also be faster, as you don't compute the square root)

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This answer is only partly correct. It misses the fact that since k-means seeks to minimize the summed within-cluster squared deviations, it ipso facto seeks to minimize the summed within-cluster squared euclidean distances between the points, normalized by the number of points in a cluster. See also comments for this answer. $\endgroup$ – ttnphns Sep 8 '13 at 20:04
  • $\begingroup$ I think this is actually very poor way of viewing the K-means because it encourages you to badly combine different dimensions without thinking. Within clusters variance only makes sense if you have scaled your axis so that each unit of variance equally costly. Otherwise if you change the units of one axis you will get a different answer! By thinking of it as a distance, then you are forced to sort this out explicitly. Otherwise you could do K-means on kg vs cm without thinking about your cost function which will lead to disaster. $\endgroup$ – Korone Sep 8 '13 at 20:59
  • 1
    $\begingroup$ I disagree and agree at the same time. I agree that you need to carefully preprocess your data, to make the notion of "variance" have the same meaning in all dimensions. But I disagree that thinking with distances helps here. With distances, most people do not do appropriate preprocessing either; and it definitely doesn't "force" you to do so. $\endgroup$ – Has QUIT--Anony-Mousse Sep 9 '13 at 6:41
  • $\begingroup$ @Anony-Mousse that is true I suppose, it is easy enough in the computer to just calculate the "distance" of a set of numbers, and easy to calculate variance without thinking. Horses-for-courses I suppose $\endgroup$ – Korone Sep 9 '13 at 9:20
0
$\begingroup$

Generally speaking Kmeans algorithm can work for any dimensions just make sure that you when calculating the distance you take into account all the N features. You can still use euclidean distance as a similarity measure have a look at the n dimensional equation http://en.wikipedia.org/wiki/Euclidean_distance.

In order to visualize the result I would advise using Principle Component Analysis for dimensionality reduction the best results (accuracy) are from performing PCA after clustering thus you do not loose any information although you can pre process it with PCA to a smaller set dimension and cluster the data, that clustering will take less time to complete as they are less dimensions to process in the distance function. Also if you plan on pre processing it then not that much inofrmation is lost as most of it is in the first derived component. Their should be libraries in R to perfrom PCA. https://stat.ethz.ch/R-manual/R-patched/library/stats/html/princomp.html

| cite | improve this answer | |
$\endgroup$

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.