3
$\begingroup$

Given a dataset $D$ and a distance measure, I want to split the dataset into two disjoint subsets $X, Y$ of a specified size (say 80% and 20% of the original size), so that the minimum distance of all pairs $(x, y)$ with $x \in X$ and $y \in Y$ is maximized. I found references to max-margin clustering without the size constraint, however my feeling is that the constraint should make the problem easier - does it? Is there some straightforward way to solve this problem?

$\endgroup$
2
  • $\begingroup$ can you please cite these references? $\endgroup$
    – mpiktas
    Mar 7, 2011 at 8:07
  • $\begingroup$ @mpiktas - well, it was just the result of a google search on max-margin clustering, the "original" paper on it seems to be webdocs.cs.ualberta.ca/~dale/papers/nips04.ps.gz (Xu et al, NIPS 2004) $\endgroup$
    – etarion
    Mar 7, 2011 at 9:33

1 Answer 1

2
$\begingroup$

A bit vague answer, but I'll give it a chance. I always felt that the size constraint is the central idea behind this method -- without is seems just to converge to other approaches, effectively to 2-means and ideologically to unsupervised SVM. The previous rather invalidates this idea, the latter way is more intriguing while you may hope to save some pain using SVM optimization framework and kernel tricks.

$\endgroup$
2
  • $\begingroup$ I'm not quite sure I understand your answer. Did you mean that "the lack of a size constraint" is the central idea? (Then the rest of the answer makes sense to me, kind of) $\endgroup$
    – etarion
    Mar 7, 2011 at 9:36
  • $\begingroup$ @etarion No, rather that it is the method for solving a problem of clustering in two groups of a given size. And thus without the constant, it just seems to dissolve into u-s SVM. $\endgroup$
    – user88
    Mar 7, 2011 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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