MathOverflow is a question and answer site for professional mathematicians. 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 have a set of data, each instance in the real $[0,1]^{d}$. However, it's actually all in a relatively small range around 0.5, clustered into classes in even smaller ranges. The actual origin of the data is the output of an untrained neural network, but don't worry about that.

The distribution is correlated between variables in an unknown but not ridiculously ill-conditioned way, and I have no guarantee that the intra-cluster distance is dramatically smaller than the inter-cluster distance (it may be of the same order of magnitude).

I would like a method for embedding into d-dimensional Hamming Space that:

1) Preserves clusters as best as possible

2) Maximizes inter-cluster distance

3) Maintains relative inter-cluster distances

4) Minimizes intra-cluster distance

In that order.

The obvious solution is some sort of machine learning method, but since i'm actually trying to apply this to improve a different machine learning method, I want a method that's rather quick and simple instead. What I was doing was just rounding, but that failed #2 spectacularly. Rounding based on centroids or mediods of the data instead would be a little more sophisticated, but still wouldn't do a great job of #2, #3, and sometimes #1.

share|cite|improve this question
not sure this question is within scope for MO. There are things you could try, but they're mostly heuristics, especially given the constraints on your data – Suresh Venkat Jun 22 '10 at 12:07
My guess is that what you are looking for does not exist, especially with the "quick and simple" stipulation. Perhaps if you mapped into a higher-dimensional Hamming space... – Joseph O'Rourke Jun 22 '10 at 13:49
I know that there won't be anything terrific, but just whatever is decent works for me. I mean, there are good techniques for rank minimization and low-dimensional embedding - I figure this is something slightly similar. – DoubleJay Jun 22 '10 at 14:28
this is an incredibly silly idea, but it might help reveal more structure in your problem. What if you merely numbered each cluster in binary, and encoded each point in the cluster with the (binary) cluster label ? For bonus points, you could instead find a maximally distance set of points in a (log k)-dimensional hamming space. It would satisfy all the constraints - but of course it would collapse points together. The question is, where in your constraints is this viewed as a bad thing ? – Suresh Venkat Jun 23 '10 at 7:27
This doesn't really help in my application. I'm trying to use the hamming embedding to assign targets for machine learning training. I currently have two ways to do this: one is to take my result vector for the centroid of a cluster and find the closest (by L1 or L2 norm) binary vector that hasn't already been used, and apply this label to all the elements of the cluster (you had this right - sorry for not being clear). The other way is the assign random bit vectors. The former has structure, but not intercluster distance. The latter has the opposite problem, but performs better. – DoubleJay Jun 24 '10 at 6:56

Your Answer


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

Browse other questions tagged or ask your own question.