# Good strategy for multiclass classification (when there is hierarchical class structure )

Combining binary classifiers, I want to solve multi-class classification problem in the following setting. Suppose there is a dataset and each data is in one of four classes: A1, A2, B1 and B2. A1 and A2 are somehow similar. B1 and B2 are also somehow similar. (e.g. A1=rose, A2=iris, B1=cow, B2=horse)

Intuitively, it seems a good idea to classify data in the following manner: first, split 'A1 and A2' from 'B1 and B2' then split A1 from A2 and B1 from B2. (so we make three classifiers.) I call this approach as 'Hierarchical strategy.'

Of course, we can perform standard '1 vs rest strategy' or '1 vs 1 strategy' alternatively.

Here are my questions:

1. Which is the best strategy from classification performance viewpoint. (I don't care about computational cost.)
2. I know the performance depends on data. Under what kind of property the 'Hierarchical strategy' is good? I'm happy if someone can formalize the problem in mathematical terms.
3. Are there research paper on this kind of considerations?

I can suggest a strategy from a classification performance viewpoint. Since the classification problem relies not only on the amount of classes and how 'similar' they are, but also on the features which describe this classification problem, I can't say if it is necessarily 'optimal'. Assuming your features have similar values for A1 and A2 (and also B1 and B2), I believe a good strategy for you is to grow a classification tree. See this Wikipedia article, the following paper and these videos for in depth details. The idea behind this classification is what you intuitively phrased as a 'Hierarchical strategy'.

The idea behind this strategy is to iteratively subdivide the feature space into regions. At each iteration, choose the 'best' feature and value that divides the data (according to some purity measure). As you stated "split 'A1 and A2' from 'B1 and B2' then split A1 from A2 and B1 from B2". Provided that your feature space can be separated, this classification strategy should work.

The final output will look like the image below. The nodes contain decisions (based on your training set) and the leaves represent the class outcome. The algorithm is interpretable, so you can easily see how well your classification strategy worked.

• Thank you for your answer. According to my intuition, I agree that the 'Hierarchical strategy' works good if A and B are well separated. However I'm not completely sure.. Can you justify it in mathematical terms?
– ywat
Dec 6, 2013 at 5:23
• I think the best way to about such a proof would be to watch the videos in the link, they are very informative and will provide a step by step explanation of the way this classification strategy works. Dec 7, 2013 at 13:40

It's best to use models that can deal with structured output instead of doing a hierarchical classification. The fact there is a structure in the possible outcomes is prior information which you can use to obtain a better overall model.

One technique that can handle this kind of information is the structured SVM, an implementation of which is available in SVM$^{struct}$.

• How do you use structured SVM? The problem I want to solve is standard classification problem. (though the set of class labels has some structure.)
– ywat
Dec 6, 2013 at 2:47