Classifier for large number of labels I have a merchants dataset with 800,000 samples and 18,000 labels. Each sample is associated with a single label and the labels are independent. 

An example sample looks like

description, label
int'l 0028240525 amazon uk retail amazon.co.uk, Amazon


In addition to the existing samples there will be new retailers added to the dataset. In this case there may well only be a single sample for that new retailer. 

To summarise, I need a classifier that


handles a large number of labels (~18,000, independent, single label per sample)
is able to classify undersampled labels (i.e. a single retailer)


Is there an approach that will handle both? Perhaps two separate classifiers makes more sense?
For multiclass classification problems there are multiple algorithms which are inherently built in a way to be able to solve them.
Some examples: kNN, naive bayes, decision trees...

For the performance to be accurate on all labels and for the classifier to show little bias, you can use other approaches: you can oversample minority classes or undersample majority classes, in a way that all the labels have the same number of points associated with them.

Here you can find some interesting answers about how to fight against class imbalances on decision tree classification: https://stats.stackexchange.com/questions/28029/training-a-decision-tree-against-unbalanced-data