4
$\begingroup$

I have to work on a binary classification task where single items to be classified are not single rows of a data matrix, but groups of rows. In other words, I have $N$ data tables of varying size $n_i \times p$ for $1 \le i \le N$, and I have to train a classification algorithm over those tables, where the target labels are $N$ in number, and of course refer to the tables.

Actually, I have already thought about some strategies to address the problem. Those are not the point of my question, so I will only dwell on the simplest one, so I can give you a clearer idea of my situation: I could simply take the mean for each of the $p$ columns, for each of the $N$ groups, and then train the algorithm, because at that point I would have a simple $N \times p$ data table: one observation, one class. Since the means alone seem too little, I could also take the variances and covariances, so to get a training set of size $N \times (p + \frac{p(p+1)}{2})$.

Anyway, my question is about literature: I can't find any paper about this kind of problem, not even one. That's probably because I couldn't look in the right places, because this doesn't appear to me as something so strange and unusual.

I want to know if this kind of problem has a name, that I ignore, and I would also like to be addressed to the scientific work that has been published about it. The more, the better.

Edit: I found this related question, where the first answer points to a python package that automatically extracts features from tables related to the main dataset. That package is cited in a few papers where the problem I expose is not really considered according to my definition. It seems to me that we are just starting to figure how we can exploit such amounts of data.

$\endgroup$
5
  • $\begingroup$ Do you mean you have $N$ data points with $N$ different labels? If so, I suppose one sensible approach would be to use nearest neighbour. Just classify any unobserved (new) table by seeing which of the existing $N$ tables it is closest to. $\endgroup$ – Tim Mak May 8 '20 at 7:43
  • $\begingroup$ well I wouldn't call them points since they are not vectors, but yes, I thought about that, even if missings are quite a problem in my case, when it comes to compute distances. $\endgroup$ – carlo May 8 '20 at 9:30
  • $\begingroup$ From the data analyst perspective, this is an aggregation problem: the shape of your data isn't ideal, so how can you meaningfully summarize the data into a better shape? Tim Mak's idea is a good one, averaging or taking a median is another. There are many, many ways to aggregate data; you need to choose one that makes sense for your application. $\endgroup$ – Adrian Keister May 8 '20 at 14:23
  • 1
    $\begingroup$ Since you mentioned you have $N$ data tables of varying size, can you tell us more about why you have these additional rows per data point? Is it so that you have repeated measurements for the observations, and number of repetitions varied during data collections? How different are these rows in individual observation tables? $\endgroup$ – PAF May 11 '20 at 21:56
  • $\begingroup$ @PAF right, I have $n_i$ independent observations related to $i$-th phenomenon. $\endgroup$ – carlo May 12 '20 at 11:17
1
+50
$\begingroup$

I would call your problem a case of a multiple instance learning problem. The wikipedia page gives an emphasis on the fact that the learning process receives a bag on instances and the presence of one of them is the reason to classify the bag as belonging to different classes. Under this view, in your case, each line of the data table is an instance, the whole data tabe is the bag, and the presence of particular lines would be the reason to classify the data table one way or another.

But I think it is more useful to think that a subset of the instances is the reason to classify the bag one way or the other. For example, finding a cat/cats in pictures is usefully thought as a multiple instance problem - the pictures are the bags, but one of other pixel is not the reason to classify the image - it is a collection of (adjacent) pixels that indicates whether there is a cat or not in the picture.

Before the deep learning approaches to image processing, the traditional solution was convert each image into a vector of both global and local descriptors (sometimes predefined descriptors - sometimes learned descriptors). You mentioned two global sets of descriptors (mean of each column and correlation among the each pair of columns). Local descriptors would aggregate values of "adjacent" instances, but the default semantics of data tables is that the order of lines is not important, and thus there are no adjacent instances. But it may be the case that your data tables have a semantically motivated order, and then local descriptors would be useful.

Finally, my experience with multiple instance problems is that the more descriptors the better. You never know which combination of descriptors will be able to distinguish between classes. In your case, if local descriptors are not meaningful, use more global descriptors that capture different aspects of the distribution of values within the columns, not just the mean. Use also other descriptors of the joint distribution of pairs of columns, not only the correlation. And let the classifier decide what to use!!!

$\endgroup$
1
  • $\begingroup$ this is really useful. I'll wait some day for other answers, but yours is already great. $\endgroup$ – carlo May 9 '20 at 18:56

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.