I have a multiclass classification problem with more than 1,000 classes. I've trained several classifiers (SVM, kNN, Random forests, etc) for 10, 100, 500 and 1000 of the classes to estimate the tendency of classifier's accuracy as the number of classes increases.
I have around 100 samples per each class and do 10-fold cross-validation. What I observe is that the accuracy (# correct classified samples divided by total tested samples) saturates as I increase the number of classes ( 100% accuracy for 10 classes, 87% for 50 classes, 75% for 100 classes, 67% accuracy for 500 classes and 63% for 1,000 classes...).
I'm trying to understand this phenomenon because I was expecting the accuracy to steadily drop to zero. What I had in my mind is that as the number of classes increases, it is more likely to find two classes that are similar to each other and, thus, have more errors.
Can anybody provide an insight on what is happening?