  Using hierarchies of classes is one of the standard methods to solve
multi-class classification problems. In the literature, selecting the right
hierarchy is considered to play a key role in improving classification
performance. Although different methods have been proposed, there is still a
lack of understanding of what makes one method to extract hierarchies perform
better or worse. To this effect, we analyze and compare some of the most
popular approaches to extracting hierarchies. We identify some common pitfalls
that may lead practitioners to make misleading conclusions about their methods.
In addition, to address some of these problems, we demonstrate that using
random hierarchies is an appropriate benchmark to assess how the hierarchy's
quality affects the classification performance. In particular, we show how the
hierarchy's quality can become irrelevant depending on the experimental setup:
when using powerful enough classifiers, the final performance is not affected
by the quality of the hierarchy. We also show how comparing the effect of the
hierarchies against non-hierarchical approaches might incorrectly indicate
their superiority. Our results confirm that datasets with a high number of
classes generally present complex structures in how these classes relate to
each other. In these datasets, the right hierarchy can dramatically improve
classification performance.
