When do we say that the dataset is not classifiable? I have many times analysed a dataset on which I could not really do any sort of classification. To see whether I can get a classifier I have usually used the following steps:


Generate box plots of label against numerical values.
Reduce the dimensionality to 2 or 3 to see if classes are separable, also tried LDA sometimes.
Forcefully try to fit SVMs and Random Forests and look at feature-importance to see if the features make any sense or not.
Try to change the balance of classes and techniques like under-sampling and over-sampling to check if class imbalance might be an issue.


There are many other approaches I can think of, but have not tried. Sometimes I know that these features are not good and not at all related to the label we are trying to predict. I then use that business intuition to end the exercise, concluding that we need better features or totally different labels.

My question is how does a Data Scientist report that the classification can not be done with these features. Is there any statistical way to report this or fitting the data in different algorithms first and looking at validation metric is the best option?
Take a sample element from one class and a sample element from the other class. Is it possible for these two elements to have the exact same feature vector? If that can ever happen then the two classes are not completely seperable using your current feature vectors (since the classification decision is based entirely in the feature vector for a given element).

On the other hand, if *every" element in one class has a corresponding element in the other class such that the two elements have the same feature vectors, then the two classes are indistinguishable using your current feature vectors. 

Furthermore, if that condition holds for only some of your elements and not others, then you are somewhere in between, and you can use that as a basis to measure how well you can hope a classifier to perform using your current feature set. 

All of these evaluations can be used to argue to varying degrees that you need to extract more features.