Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to apply k-means clustering to a (sparse) adjacency graph. For this I need to assign the nodes to a position in an euclidean space. Trivially I can do this by having a space with as many dimensions as there are nodes where each component corresponds to another node.

Now, in order to make the clustering a bit more understandable, or maybe just different, I'm thinking about whether there are ways of "folding" the n-dimensional space of points into a more manageable space, perhaps 3-dim or maybe just m-dim where m < n. While doing this I want to maintain distance relations between nodes - so I want to minimize the deviation between the straight line distance between any two points before the fold compared to after the fold, or in other words, the sum of all deviations.

So I can't seem to find any to-the-point info on this when looking. Perhaps I'm missing terminology. What good/efficient methods are there for this? Algorithms? It seems like a somewhat archetypical optimization/mean square minimization problem.

A simple base case:

P1 = (1,1,1)
P2 = (1,1,0)
p3 = (1,0,1)
newPoints = spacefold(2,[P1,P2,P3])

// example output:
// newPoints = [(1,1),
//              (1,0),
//              (0,1)]

For this example they happened to be conveniently placed in a plane - removing the x component gives an optimal solution.

share|improve this question
Hmm, I'm beginning to find some leads now: And: – worldsayshi Jan 23 '13 at 14:28
Yes, like cited in your references, Principal Components Analysis (PCA) is a term to look for. Classical authors include Loéve and Karhunen (KLT = Karhunen Loéve Transform). – Axel Kemper Feb 25 '13 at 21:46

Multidimensional scaling is probably what you're looking for. It takes as input a distance matrix and assigns to each object a vector of the target dimension.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.