# How to classify data having sub-instance features?

I am trying to use machine learning on some peculiar (at least for me) data. Usually, when I do machine learning I am use to have the data in this format:

    Feat1 Feat2 Feat3 Feat4  Class
I1 | .0  | .0  | .2  | .3  | TRUE  |
I2 | .5  | .0  | .1  | .3  | TRUE  |
I3 | .0  | .0  | .1  | .3  | FALSE |


In this case, my data is in this format:

        F1   F2   F3   Class
I1 a | .0 | .2 | .3 |
b | .0 | .2 | .3 |
c | .0 | .2 | .3 | TRUE  |

I2 a | .9 | .1 | .1 |
b | .0 | .0 | .0 |
c | .0 | .0 | .0 | TRUE  |

I3 a | .0 | .0 | .1 |
b | .0 | .2 | .3 |
c | .0 | .2 | .1 | FALSE |


So I have multiple rows concurring to the final classification of an instance, and I can compute the features only at this sub-level.

One way to aggregate the features in a single row would be to, for example, using things such as 'mean', 'min/max', etc. But there is no clear choice for these aggregations in our dataset.

The number of rows is not known a-priori, so I cannot create a single row aggregating the multiple rows to model the instance. For example, I cannot have:

       F1-a  F2-a  F3-a  F1-b  F2-b  F3-b  F1-c  F2-c  F3-c  Class
I1 a | .0  | .2  | .3  | .0  | .2  | .3  | .0  | .2  | .3 | TRUE  |


Moreover, this does not seem to be a multiple-instance learning problem, because I am not trying to classify the single row, but the instances (which are made of features from multiple rows).

Thank you!

• Thank you for the welcome! No, answers can be in any software. – Alberto Bacchelli Jul 25 '13 at 0:03

Your problem belongs to the area of sequence classification. For a general overview I recommend A Brief Survey on Sequence Classification by Xing et. al.

According to this survey, the data can be treated as mulitvariate time series or complex event data. I do not have enough expertise to answer the question from the former point of view, hence I focus on the latter one.

Classification of complex event sequences

The classification of complex event sequences is one of the hardest problems. Unfortunately, the literature is rare or hard to find. I stumbled on this paper recently (Dynamic classification of Online Customers by Bertsimas et. al), but I have not read it yet. In general, this is a common problem in the area of web usage mining, dealing with classification of visitors based on their multiple visits.

Based on a one-time-experience I suggest the following:

1. Build one static classification model per step (a,b,c ...). This was only possible because it made sense in the application domain, i.e. the first, second step etc. shared the same meaning across different instances (although they did not happen at the same time)
2. Combine all these models into one in such a way, that the ensemble model does not only perform the classification decision but additionally determines when a decision has to be made (mostly due to the fact that the application required, that a decision can performed only once and may not change afterwards). The when-decision is based on internal crossvalidation performed during training to estimate the confidence and the accuracy of the models of the different steps.

The results from this type of model were good, but not brilliant. Feature construction by application of domain knowledge can improve the results dramatically.