Welcome to MathOverflow

Question

1

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.

edited Jun 22 2010 at 14:28

asked Jun 22 2010 at 7:40

DoubleJay
1,269●11●29

	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 2010 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 2010 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 2010 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 2010 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 2010 at 6:56

Cluster-preserving and distance-maximizing embedding into Hamming Space?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.