1
$\begingroup$

I want to redistribute the data in classes according to new proportions and wonder what is the optimal way to do it. For example I have

10 30 60 elements in each class a,b,c

and apparently the fractions in each class are as follows:

0.1 0.3 0.6

What if I want to set the fractions as follows:

0.3 0.2 0.5

and to throw away the other data. New data cannot be generated and the maximum number of data points should be kept. Can it be generalized to a hundred of classes?

UPD: I derived some minimization problem:

$$ min_\textbf{n} \; f(\textbf{n}) = - \sum p^{new}_i \log{\hat p_i} = - \sum p^{new}_i \log{(\hat n_i/ \hat N)} $$

$$ = \log(\hat N)- \sum p^{new}_i \log{(\hat n_i)} $$ s.t $$\hat n_i \le n_i^c \; , \forall i \in 1:C$$ $$ \hat N = \sum_i \hat n_i $$

But I don't know how to fomulate the condition that $\hat n_i$ should be also maximized at the same time.

where $\hat n$ is a number of elements in the i-th class, that i'm looking for, $N$ is total number of elements and $C$ is a number of classes. $p^{new}_i$ is a class partition. $n_i$ is an original number of elements in the given class

How to solve it?

$\endgroup$
6
  • $\begingroup$ a simple way is to: 1) remove one data from the most populated class and re-calculate the proportions. 2) go to step 1) untill the desired proportions are met (within some reasonable bounds) $\endgroup$
    – Nikos M.
    Jun 1 at 18:28
  • $\begingroup$ there can be variations on the above algorithm, eg if a certain min number of data points should be in each class, then step 1) can go tothe next most populated class and so on.. $\endgroup$
    – Nikos M.
    Jun 1 at 18:29
  • $\begingroup$ Doesn't it take too long? My dataset size is of the order of $10^5$, the number of classes are under 10 but a few dozens should be treated as well $\endgroup$ Jun 1 at 20:36
  • 1
    $\begingroup$ You can use Random Under Sampler?? $\endgroup$ Jun 2 at 8:00
  • 1
    $\begingroup$ You can remove more than one data item at the same step, if it is faster. There are many variations of that simple algorithm $\endgroup$
    – Nikos M.
    Jun 2 at 8:08
2
$\begingroup$

I think there is a simple way to calculate this:

  1. For each class calculate the ratio new proportion / old proportion:
  • a: 0.3 / 0.1 = 3
  • b: 0.2 / 0.3 = 0.67
  • c: 0.5 / 0.6 = 0.83
  1. The max of these ratios is the only one which matters because it defines the hard limit in number of instances. For example in this case class a needs 3 times more data, so the full sample has to be reduced by 3. Let's say you have 1000 instances:
  • a keeps its 100 instances so the full size of the sample must be 100/0.3 = 333
  • b has 0.2 * 333 = 67
  • c has 0.5 * 333 = 166

(I didn't check that this works in every case)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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