18
$\begingroup$

There are words from "The Elements of Statistical Learning" on page 91:

The K centroids in p-dimensional input space span at most K-1 dimensional subspace, and if p is much larger than K, this will be a considerable drop in dimension.

I have two questions:

  1. Why the K centroids in p-dimensional input space span at most K-1 dimensional subspace?
  2. How are the K centroids located?

There is no explain in the book and I didn't find the answer from related papers.

$\endgroup$
  • 3
    $\begingroup$ The $K$ centroids lie in an at most $K-1$ dimensional affine subspace. For example, two points lie on a line, a $2-1$ dimensional subspace. This is just the definition of an affine subspace and some elementary linear algebra. $\endgroup$ – deinst Feb 15 '12 at 12:56
  • $\begingroup$ A very similar question: stats.stackexchange.com/q/169436/3277. $\endgroup$ – ttnphns Aug 31 '15 at 12:24
16
$\begingroup$

Discriminants are the axes and the latent variables which differentiate the classes most strongly. Number of possible discriminants is $min(k-1,p)$. For example, with k=3 classes in p=2 dimensional space there can exist at most 2 discriminants such as on the graph below. (Note that discriminants are not necessarily orthogonal as axes drawn in the original space, although they, as variables, are uncorrelated.) The centroids of the classes are located within the discriminant subspace according to the their perpendicular coordinates onto the discriminants.

enter image description here

Algebra of LDA at the extraction phase is here.

$\endgroup$
  • $\begingroup$ Nice graph, what software/package did you use to create it? $\endgroup$ – Michelle Feb 15 '12 at 18:18
  • $\begingroup$ SPSS. Self-written macro for SPSS. $\endgroup$ – ttnphns Feb 15 '12 at 18:53
  • $\begingroup$ Does this mean that you won't see good class separation in an LDA with, say, three classes with overlap, until you rescale the axis?? I mean, I'm running an LDA, and my classes separate...but they are right on top of eachother in every discriminate axis except the first one...and that one is huge. $\endgroup$ – donlan Feb 10 '16 at 22:26
14
$\begingroup$

While "The Elements of Statistical Learning" is a brilliant book, it requires a relatively high level of knowledge to get the most from it. There are many other resources on the web to help you to understand the topics in the book.

Lets take a very simple example of linear discriminant analysis where you want to group a set of two dimensional data points into K = 2 groups. The drop in dimensions will be only be K-1 = 2-1 = 1. As @deinst explained, the drop in dimensions can be explained with elementary geometry.

Two points in any dimension can be joined by a line, and a line is one dimensional. This is an example of a K-1 = 2-1 = 1 dimensional subspace.

Now, in this simple example, the set of data points will be scattered in two-dimensional space. The points will be represented by (x,y), so for example you could have data points such as (1,2), (2,1), (9,10), (13,13). Now, using linear discriminant analysis to create two groups A and B will result in the data points being classified as belonging to group A or to group B such that certain properties are satisfied. Linear discriminant analysis attempts to maximize the variance between the groups compared to the variance within the groups.

In other words, groups A and B will be far apart and contain data points that are close together. In this simple example, it is clear that the points will be grouped as follows. Group A = {(1,2), (2,1)} and Group B = {(9,10), (13,13)}.

Now, the centroids are calculated as the centroids of the groups of data points so

Centroid of group A = ((1+2)/2, (2+1)/2) = (1.5,1.5) 

Centroid of group B = ((9+13)/2, (10+13)/2) = (11,11.5)

The Centroids are simply 2 points and they span a 1-dimensional line which joins them together.

Figure 1

You can think of linear discriminant analysis as a projection of the data points on a line so that the two groups of data points are as "separated as possible"

If you had three groups (and say three dimensional data points) then you would get three centroids, simply three points, and three points in 3D space define a two dimensional plane. Again the rule K-1 = 3-1 = 2 dimensions.

I suggest you search the web for resources that will help explain and expand on the simple introduction I have given; for example http://www.music.mcgill.ca/~ich/classes/mumt611_07/classifiers/lda_theory.pdf

$\endgroup$
  • 1
    $\begingroup$ Welcome to our site, Martino! $\endgroup$ – whuber Feb 15 '12 at 15:00
  • $\begingroup$ thanks @whuber, nice graph, I didn't have any such tools at hand :( $\endgroup$ – martino Feb 15 '12 at 15:14
  • $\begingroup$ I didn't think you had the reputation to post an image anyway, Martino: that's why I made one for you. But now--or soon--you will have enough rep. If nothing is handy, you can use freely available software with geometric drawing capabilities like R or Geogebra. (You will find that illustrated replies get more attention: they are more attractive and readable.) $\endgroup$ – whuber Feb 15 '12 at 15:19
  • $\begingroup$ Why the downvote? If there's an issue with the answer it'd be helpful to point it out - I can't see one $\endgroup$ – martino Oct 10 '14 at 11:44

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.