I'm concerned with a supervised classification problem for the following type of data. The data consists of $N$ rows (where $N$ is not very large - this is not a big-data problem) and $M$ columns (features) and each row has a certain label I'm interested in. Every row belongs to a certain block and each block consists of 1-50 rows. The size of a block depends on the duration of a block (so the rows in each block are correlated, but the correlation between different blocks can be neglected).
The aim is to learn a classification algorithm on the data that allows to classify a new row or a new block.
Now there are two important things: The labels are constant within each block and there are some features that allow the identification of blocks.
My question is: What might be the best way to learn a model on this specific type of data?
To illustrate this problem a bit further, let me report some problems I found when I worked with Random Forests on the data set.
Suppose I take a part of the data as validation data, which contains whole blocks. If I split the remaining rows randomly in training and test data, the accuracy of the learned Random Forest is very high on training and test data but very low on the validation data. This is due to the fact that the Random Forest learns in this case to identify the individual blocks and as the validation data contains some unknown blocks, the accuracy drops. This can be also seen in the resulting importance for the features: the most important ones are those features that allow an identification of a cycle very easily.
Splitting the remaining data into training and test data and leaving the blocks whole helps a bit but doesn't fix the problem completely.
Another approach would be to remove all features that allow the identification of blocks. But this is difficult a priori and some of these features could have important information for my problem.
A simple way to overcome the problems would be to take the row mean in each block and use the resulting data for the classification problem. However, in this case you loose a lot of information.
So I'm wondering if there are more natural ways to approach this classification problem which respect the block-structure of the data.