As more and more data with class taxonomies emerge in diverse fields, such as pattern recognition, text classification and gene function prediction, we need to extend traditional machine learning methods to solve classification problem in such data sets, which presents more challenges over common pattern classification problems. In this paper, we define structured label classification problem and investigate two learning approaches that can learn classifier in such data sets. We also develop distance metrics with label mapping strategy to evaluate the results. We present experimental results that demonstrate the promise of the proposed approaches.