2
$\begingroup$

I'm working on a problem, I was wondering if there are any methods available to do the following.

I have a data set with information on people (continuous and categorical data). I have 3 categories to assign to these people {A, B, C}, and I want to try and develop some rules of how to assign each person a category.

However the tricky part is, the 'target' I'm looking for is a distribution. So for example I would like to be able to pass in {.2, .05, .75} as the distribution of {A, B, C} and then have an algorithm try out different rules and splits of the data (similar to a decision tree) until it achieves the given distribution.

Are there any machine learning type methods suited to this problem? Is there a name for this type of problem? I wasn't finding anything with my googling...

Thanks

edit: Just for a little more information, the way I'm currently going to approach it is random assignment, give everyone a random number, if it's below .2 then give Category A and so on. Not ideal, but the fact that it's random is a major issue for the problem. Although I would much prefer to have a set of rules that I could use instead.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ To what extent do you need the groups to be well described by the information you have on the people? You currently use random, is the only problem that it isn't stable each time you run the algo? Or would you like group A to be "similar" to each other, and group B etc $\endgroup$
    – Corvus
    Mar 5, 2013 at 10:00
  • $\begingroup$ The stability isn't really an issue as I can seed the random variable, I would prefer group A to be similar to each other. It would also be handy (but not essential) to be able to look at maybe a few different decision tree type rules and pick amongst them, for example if one makes more business sense but doesn't exactly provide the right distribution. $\endgroup$
    – Ger
    Mar 5, 2013 at 10:38
  • $\begingroup$ What order of magnitude are we talking for the number of people? 10s, 1000s or millions+? $\endgroup$
    – Corvus
    Mar 5, 2013 at 10:42
  • $\begingroup$ 1000s, ~4,000 at the moment, will increase in the future but not by an order of magnitude. $\endgroup$
    – Ger
    Mar 5, 2013 at 10:43
  • 1
    $\begingroup$ It is only a global constraint, not a response. Supervised learning techniques need a "response" of some sort for each individual - i.e. to know what class they should be in, or some score that can act as a proxy. A global constraint doesn't contain any information on the individuals - as you found, random will happily satisfy the constraint. It seems your hidden criteria is actually that people in the same group should be "similar". This makes it a classic unsupervised classification problem. $\endgroup$
    – Corvus
    Mar 5, 2013 at 12:09

1 Answer 1

Reset to default
1
$\begingroup$

Given that your primary criteria is to get the relative sizes of the classes to be as specified, you are obviously not going to have "optimal" clustering in other senses.

I don't know if this is state of the art for this problem, but I would consider using a k-means style approach to but only grow the clusters to the appropriate sizes.

For example

  1. Select 3 random points in the feature space (class centres)
  2. Assign the nearest fraction of points to each class centre
  3. Recalculate the mean of each cluster
  4. Repeat
  5. Stop when bored or convergence has occured

Basically follow the same algorithm as k-means with the added criteria that membership is restricted to the proportions you specify.

Obviously, as with ordinary k-means, this won't neccessarily give you the same clustering when you rerun with different starting points. You could try decide on a measure of intraclass correlation, and then run the algo a few times and pick the best.

k-medians

Thinking some more, you may find k-medians more to taste for your problem. This will result in classification based on $L_1$ norm and so will create orthogonal splits of your feature-space rather like a tree would.

Improve this answer
$\endgroup$

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.