Clustering Approach to Solve Hierarchical Classification Problem Complexity

Abstract

In a large domain of classification problems for real applications, like human activity recognition, separable spaces between groups of concepts are easier to learn than each concept alone. This is because the search space biases required to separate groups of classes (or concepts) are more relevant than the ones needed to separate classes individually. For example, it is easier to learn the activities related to the body movements group (running, walking) versus "on-wheels" activities group (bicycling, driving a car), before learning more specific classes inside each of these groups. Despite the obvious interest of this approach, our theoretical analysis shows a high complexity for finding an exact solution. We propose in this paper an original approach based on the association of clustering and classification approaches to overcome this limitation. We propose a better approach to learn the concepts by grouping classes recursively rather than learning them class by class. We introduce an effective greedy algorithm and two theoretical measures, namely cohesion and dispersion, to evaluate the connection between the clusters and the classes. Extensive experiments on the SHL dataset show that our approach improves classification performances while reducing the number of instances used to learn each concept.