When do we speak of imbalanced data? I was wondering, what the threshold is for a dataset to be called 'imbalanced'? 
Technically every dataset where the target-classes aren't evenly distributed is not balanced. Yet small imbalance seems to have little effect in the used methods (i.e. decision trees, Cluster Analysis, etc.) and outcomes. So when do we call data truly imbalanced so that we have to adjust our procedure (different sampling methods / algorithms)?
Is there a value of percentage, that should be kept in mind?   
 A: I think that there is no universal answer that will make everybody happy. Let us concentrate on binary (i.e. two class) predictive classification task with labels 'true' (positive samples) and 'false' (negative samples). Technically, (as you state correctly) every dataset where the amount of positive samples is unequal to the number of negative samples is imbalanced. The very silly answer to your question therefore is:
A dataset is imbalanced when the model(s) that you compute work 'better' when they are being told that the dataset is imbalanced.
What do I mean by that? First of all the term 'better' is subjective. To this very end, you have to decide when a model outperforms another one. This may depend on technical terms like AUC (etc.) but may also depend on very practical influences like in the Netflix challenge: The winning team was indeed a 'meta team', i.e. a group of original teams that joined their ideas to one big models comprehensing over 100 'smaller' models. I think that I have read that Netflix only choose to implement three of them (otherwise this would have been a maintenance nightmare!). However, once we are satisfied with the definition of 'better', I can explain the second part formally.
What is the 'bad thing' about imbalancedness? Let us assume that we have 99% negative samples and 1% positive ones. Then every natural model will tend to degenerate to the 'always false' model and it has an impressive accuracy of 99%! However, in reality this is rarely what we want. Hence, one has to 'punish' the model more for a misclassification of the rare class than of the bigger. One can do that in different ways:
The meta-way: Just downsample the bigger class or repeat random samples from the rare class.
The mathematical way: Adapt the cost function and punish a misclassification of the rare class more than the misclassification of the bigger class. This can be done in SVMs for example.
The evaluation way (also kind of adapting part of the cost function): Use a measure for the model perfomance that does take the imbalancedness into account. For example, when comparing two binary classifiers, the AUC is one of the criteria that should not fooled by the imbalancedness of the data. Also , sometimes peopla claim that the F-Score is robust against imbalanced data as well but I do not know about that because I never use it. I tend to use measures that can be understood by the users (i.e. this model will increase revenue by xyz% or dollars or ... or will reduce the error by ...).
Also, some of the classification algorithms or setups of them may be robust natively against imbalanced training sets. For example, if you actually need a recommender and you chose gradient boosting as your algorithm and you use the 'original' sigmoidal output between 0 and 1 of the gradient booster (and not the true/false prediction) and you just rate by the value then all values will be really small but it could be that (also in imbalanced cases) the values of the positives are just a tiny bit smaller than the negative ones and will therefor end up at the top of the list although their values lie around 0.0000001 or so.
