8
$\begingroup$

I'm reading a book "Machine learning with Spark" by Nick Pentreath, and at page 224-225 the author discusses about using K-means as a form of dimensionality reduction.

I have never seen this kind of dimensionality reduction, does it has a name or/and is useful for specific shapes of data?

I quote the book describing the algorithm:

Assume that we cluster our high-dimensional feature vectors using a K-means clustering model, with k clusters. The result is a set of k cluster centers.

We can represent each of our original data points in terms of how far it is from each of these cluster centers. That is, we can compute the distance of a data point to each cluster center. The result is a set of k distances for each data point.

These k distances can form a new vector of dimension k. We can now represent our original data as a new vector of lower dimension, relative to the original feature dimension.

Author suggests a Gaussian distance.

With 2 clusters for 2 dimensional data, I have the following:

K-means:

K-means with 2 clusters

Applying the algorithm with norm 2:

norm 2

Applying the algorithm with a Gaussian distance (applying dnorm(abs(z)):

Gaussian

R code for the previous pictures:

set.seed(1)
N1 = 1000
N2 = 500
z1 = rnorm(N1) + 1i * rnorm(N1)
z2 = rnorm(N2, 2, 0.5) + 1i * rnorm(N2, 2, 2)
z = c(z1, z2)

cl = kmeans(cbind(Re(z), Im(z)), centers = 2)

plot(z, col = cl$cluster)

z_center = function(k, cl) {
  return(cl$centers[k,1] + 1i * cl$centers[k,2])
}

xlab = "distance to cluster center 1"
ylab = "distance to cluster center 2"

out_dist = cbind(abs(z - z_center(1, cl)), abs(z - z_center(2, cl)))
plot(out_dist, col = cl$cluster, xlab = xlab, ylab = ylab)
abline(a=0, b=1, col = "blue")

out_dist = cbind(dnorm(abs(z - z_center(1, cl))), dnorm(abs(z - z_center(2, cl))))
plot(out_dist, col = cl$cluster, xlab = xlab, ylab = ylab)
abline(a=0, b=1, col = "blue")
$\endgroup$
  • 1
    $\begingroup$ Note that in your example, no dimensionality reduction takes place since your data was 2-dimensional to begin with, and you're mapping it onto 2 new dimensions (the distances to each of your 2 clusters). To reduce the dimensionality of your data, you need to use fewer clusters than the number of original dimensions in the data. $\endgroup$ – Ruben van Bergen Jul 4 '17 at 8:48
  • $\begingroup$ Yes, I did all this in 2D to allow to plot the initial picture and let everyone see the reshape; so it is not dimensionality reduction in that case. The output shape is similar for data sampled similarly in 3D and with 2 clusters. $\endgroup$ – ahstat Jul 4 '17 at 9:30
  • 3
    $\begingroup$ I like the fact that you are emphasizing distance from cluster centers. Too many data analysts discretize the data and lose information by grouping data into "distinct" clusters. $\endgroup$ – Frank Harrell Jul 4 '17 at 12:19
6
$\begingroup$

I think this is the "centroid method" (or the closely-related "centroidQR" method) described by Park, Jeon and Rosen. From Moon-Gu Jeon's thesis abstract:

Our Centroid method projects full dimensional data onto the centroid space of its classes, which gives tremendous dimensional reduction, reducing the number of dimension to the number of classes while improving the original class structure. One of its interesting properties is that even when using two different similarity measures, the results of classification for the full and the reduced dimensional space formed by the Centroid are identical when the centroid-based classification is applied. The second method, called CentroidQR, is a variant of our Centroid method, which uses as a projection space, k columns of orthogonal matrix Q from QR decomposition of the centroid matrix.

It also seems to be equivalent to the "multiple group" method from Factor Analysis.

$\endgroup$
3
$\begingroup$

Look all the literature on pivot based indexing.

But you gain little by using k-means. Usually, you can just use random points as pivots. If you choose enough, they won't be all similar.

$\endgroup$
  • $\begingroup$ Can you please elaborate why "you gain little by using k-means"? Thanks $\endgroup$ – Tagar Jun 19 '18 at 14:23
  • $\begingroup$ Because the results don't appear to be better than with random pivots. $\endgroup$ – Anony-Mousse Jun 19 '18 at 17:38
  • $\begingroup$ thanks! can you please update your response with a link to "pivot based indexing" technique? I assume that's the same as "use random points as pivots". I tried to google, but not sure if what I'm getting is directly related to this K-means approach outlined in Q. $\endgroup$ – Tagar Jun 19 '18 at 18:01
2
$\begingroup$

There are several ways to use clustering as dimension reduction. For the K-means, you can also project the points (orthogonally) onto the vector (or affine) space generated by the centres.

$\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.