|
|
|
| A Survey of Hierarchical Classification Methods |
| LU Yan-Ting, LU Jian-Feng, YANG Jing-Yu |
| School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094 |
|
|
|
|
Abstract Hierarchical classification (HC), decomposing problem and organizing the classifiers according to the category hierarchy, is an efficient solution for multi-class classification problem. Depending on whether an explicit hierarchical relationship among categories is required, HC methods can be divided into two types. In this paper, the HC methods which do not require explicit hierarchical relationship among categories are reviewed systematically. Firstly, the basic framework of this type of methods is outlined. Then, the research progresses of several key techniques are elaborated and analyzed. Next, the related research work at home and abroad is described in detail from both algorithm and application perspectives. Finally, the existing methods are summarized and several future research directions are pointed out.
|
|
Received: 30 May 2013
|
|
|
|
|
|
[1] Zhou Dengyong, Xiao Lin, Wu Mingrui. Hierarchical Classification via Orthogonal Transfer // Proc of the 28th International Conference on Machine Learning. Washington, USA, 2011: 801-808
[2] Cai L, Hofmann T. Hierarchical Document Categorization with Su-pport Vector Machines // Proc of the ACM International Conference on Information and Knowledge Management. New York, USA, 2004: 78-87
[3] Binder A, Müller K, Kawanabe M. On Taxonomies for Multi-Class Image Categorization. International Journal of Computer Vision, 2011, 99(3): 281-301
[4] Silla C N, Freitas A A. A Survey of Hierarchical Classification across Different Application Domains. Data Mining and Knowledge Discovery, 2011, 22(1/2): 31-72
[5] Chen Yangchi, Crawford M M, Ghosh J. Integrating Support Vector Machines in a Hierarchical Output Space Decomposition Framework // Proc of the IEEE International Geoscience and Remote Sensing Symposium. Piscataway, USA, 2004: 949-952
[6] Kumar S, Ghosh J, Crawford M M. Hierarchical Fusion of Multiple Classifiers for Hyperspectral Data Analysis. Pattern Analysis and Applications, 2002, 5(2): 210-220
[7] Casasent D, Wang Y F. A Hierarchical Classifier Using New Su-pport Vector Machines for Automatic Target Recognition. Neural Networks, 2005, 18(5/6): 541-548
[8] Wang Y F, Casasent D. New Support Vector-Based Design Method for Binary Hierarchical Classifiers for Multi-Class Classification Problems. Neural Networks, 2008, 21(2/3): 502-510
[9] Marszaek M, Schmid C. Semantic Hierarchies for Visual Object Recognition // Proc of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Minneapolis, USA, 2007: 1-7
[10] Zweig A, Weinshall D. Exploiting Object Hierarchy: Combining Models from Different Category Levels // Proc of the 11th International Conference on Computer Vision. Rio de Janeiro, Brazil, 2007: 1-8
[11] Yuan Xun, Lai Wei, Mei Tao, et al. Automatic Video Genre Categorization Using Hierarchical SVM // Proc of the International Conference on Image Processing. Atlanta, USA, 2006: 2905-2908
[12] Vural V, Dy J G. A Hierarchical Method for Multi-Class Support Vector Machines // Proc of the 21st International Conference on Machine Learning. New York, USA, 2004: 831-838
[13] Lei H, Govindaraju V. Half-Against-Half Multi-Class Support Vector Machines // Proc of the 6th International Conference on Multiple Classifier Systems. Berlin, Germany: Springer, 2005: 156-164
[14] Zhang Guoyun, Zhang Jin. A Novel SVM Multi-Class Classifier Based on Divisive Hierarchical Clustering. Control and Decision, 2005, 20(8): 931-934 (in Chinese)
(张国云,章 兢.一种新的分裂层次聚类SVM多值分类器.控制与决策, 2005, 20(8): 931-934)
[15] Liu Song, Yi Haoran, Chia L T, et al. Adaptive Hierarchical Multi-Class SVM Classifier for Texture-Based Image Classification // Proc of the IEEE International Conference on Multimedia and Expo. Amsterdam, The Netherlands, 2005: 1190-1193
[16] Zhang Guoxuan, Kong Rui, Shi Zesheng, et al. Hierarchical Su-pport Vector Machines Based on Kernel Clustering. Control and Decision, 2004, 19(11): 1305-1307, 1311 (in Chinese)
(张国宣,孔 锐,施泽生,等.基于核聚类方法的多层次支持向量机分类树.控制与决策, 2004, 19(11): 1305-1307, 1311)
[17] Liu Lei, Comar P M, Saha S, et al. Recursive NMF: Efficient Label Tree Learning for Large Multi-Class Problems // Proc of the 21st International Conference on Pattern Recognition. Tsukuba, Japan, 2012: 2148-2151
[18] Lorena A C, Carvalho A C. Minimum Spanning Trees in Hierarchical Multiclass Support Vector Machines Generation // Ali M, Esposito F, eds. Lecture Notes in Artificial Intelligence. Berlin, Germany: Springer-Verlag, 2005, 3533: 422-431
[19] Lorena A C, Carvalho A C. Building Binary-Tree-Based Multiclass Classifiers Using Separability Measures. Neurocomputing, 2010, 73(16/17/18): 2837-2845
[20] Wang Y F, Casasent D. Hierarchical K-means Clustering Using New Support Vector Machines for Multi-Class Classification // Proc of the International Joint Conference on Neural Networks. Vancouver, Canada, 2006: 3457-3464
[21] Marszaek M, Schmid C. Constructing Category Hierarchies for Visual Recognition // Proc of the 10th European Conference on Computer Vision. Berlin, Germany: Springer, 2008: 479-491
[22] Cevikalp H. New Clustering Algorithms for the Support Vector Machine Based Hierarchical Classification. Pattern Recognition Le-tters, 2010, 31(11): 1285-1291
[23] Wang Y F, Casasent D. New Weighted Support Vector K-means Clustering for Hierarchical Multi-Class Classification // Proc of the International Joint Conference on Neural Networks. Orlando, USA, 2007: 471-476
[24] Griffin G, Perona P. Learning and Using Taxonomies for Fast Visual Categorization // Proc of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Alaska, USA, 2008: 1-8
[25] Bengio S, Weston J, Grangier D. Label Embedding Trees for Large Multi-Class Tasks // Lafferty J, Williams C, Shawe-Taylor J, eds. Advances in Neural Information Processing Systems. Red Hook, USA: Curran Associates, 2011, 23: 163-171
[26] Deng Jia, Satheesh S, Berg A C, et al. Fast and Balanced: Efficient Label Tree Learning for Large Scale Object Recognition // Shawe-Taylor J, Zemel R S, Bartlett P L, eds. Advances in Neural Information Processing Systems. Red Hook, USA: Curran Associates, 2012, 24: 567-575
[27] Duda R O, Hart P E, Stork D G. Pattern Classification. 2nd Edition. New York, USA: John Wiley, 2001
[28] Zhao Bin, Li Feifei, Xing E P. Large-Scale Category Structure Aware Image Categorization // Shawe-Taylor J, Zemel R S, Bartlett P L, eds. Advances in Neural Information Processing Systems. Red Hook, USA: Curran Associates, 2012, 24: 1251-1259
[29] Yang Yiming. Expert Network: Effective and Efficient Learning from Human Decisions in Text Categorization and Retrieval // Proc of the 17th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, USA: Springer-Verlag, 1994: 13-22
[30] Tsai M, Tsai S, Huang T S. Hierarchical Image Feature Extraction and Classification // Proc of the 18th International Conference on Multimedia. New York, USA, 2010: 1007-1010
[31] Weigend A S, Wiener E D, Pedersen J O. Exploiting Hierarchy in Text Categorization. Information Retrieval, 1999, 1(3): 193-216
[32] Koller D, Sahami M. Hierarchically Classifying Documents Using Very Few Words // Proc of the 14th International Conference on Machine Learning. San Francisco, USA, 1997: 170-178
[33] Wang Z F, Wang Z H, Xie W J. Tree-Structured Bayesian Network Learning with Application to Scene Classification. Electronics Letters, 2011, 47(9): 540-541
[34] Gao T, Koller D. Discriminative Learning of Relaxed Hierarchy for Large-Scale Visual Recognition // Proc of the IEEE International Conference on Computer Vision. Piscataway, USA, 2011: 2072-2079
[35] Freeman C, Kulic D, Basir O. Joint Feature Selection and Hierarchical Classifier Design // Proc of the IEEE International Conference on Systems, Man and Cybernetics. Anchorage, USA, 2011: 1728-1734
[36] Lu Yanting, Lu Jianfeng, Yang Jingyu. Adaptive Kernel Learning Based on Centered Alignment for Hierarchical Classification // Proc of the 21st International Conference on Pattern Recognition. Tsukuba, Japan, 2012: 569-572
[37] Lu Yanting, Lu Jianfeng, Wang Liantao, et al. Constructing Class Hierarchy via Adaptive Kernel Learning // Proc of the Chinese Conference on Pattern Recognition. Berlin, Germany: Springer-Verlag, 2012: 72-79
[38] Casasent D, Wang Y F. Automatic Target Recognition Using New Support Vector Machine // Proc of the International Joint Conference on Neural Networks. Montreal, Canada, 2005: 84-89
[39] Wang Y F, Casasent D. Soft-Decision Hierarchical Classification Using SVM-Type Classifiers // Proc of the International Joint Conference on Neural Networks. Hong Kong, China, 2008: 1793-1800
[40] Wang Y F, Casasent D. A Support Vector Hierarchical Method for Multi-Class Classification and Rejection // Proc of the International Joint Conference on Neural Networks. Atlanta, USA, 2009: 3281-3288
[41] Yuan C, Casasent D. Support Vector Machines for Class Representation and Discrimination // Proc of the International Joint Conference on Neural Networks. Portland, USA, 2003: 1611-1616
[42] Shi J, Mali J. Normalized Cuts and Image Segmentation. IEEE Trans on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905
[43] Hua Ye, Zhang Tao, Xi Houwei, et al. Research on Method of Hyperspectral Remote Sensing Image Classification Based on Decision Tree. Computer Technology and Development, 2012, 22(6): 198-202 (in Chinese)
(华 晔,张 涛,奚后玮,等.基于决策树的高光谱遥感影像分类方法研究.计算机技术与发展, 2012, 22(6): 198-202)
[44] Ma Yingying. Spaceborne Lidar Retrieval Based on Layer Classification and Data Fusion. Ph. D Dissertation. Wuhan, China: Wuhan University, 2010 (in Chinese)
(马盈盈.基于层次分类与数据融合的星载激光雷达数据反演.博士学位论文.武汉:武汉大学, 2010)
[45] Yu Xianchuan, Zhou Xin, Kang Zengji, et al. Hierarchical Classification of Rock and Soil Based on Characteristic Multi-Band Image. Journal of Jilin University: Earth Science Edition, 2012, 42(6): 1825-1833 (in Chinese)
(余先川,周 鑫,康增基,等.一种基于多特征波段岩土层次分类方法.吉林大学学报:地球科学版, 2012, 42(6): 1825-1833)
[46] He Chu, Liu Ming, Xu Lianyu, et al. A Hierarchical Classification Method Based on Feature Selection and Adaptive Decision Tree for SAR Image. Geomatics and Information Science of Wuhan University, 2012, 37(1): 46-49 (in Chinese)
(何 楚,刘 明,许连玉,等.利用特征选择自适应决策树的层次SAR图像分类.武汉大学学报:信息科学版, 2012, 37(1): 46-49)
[47] Li Feifei, Fergus R, Perona P. Learning Generative Visual Models from Few Training Examples: An Incremental Bayesian Approach Tested on 101 Object Categories. Computer Vision and Image Understanding, 2007, 106(1): 59-70
[48] Griffin G, Holub A, Perona P. Caltech-256 Object Category Dataset[EB/OL]. [2013-03-30]. http://authors.library.caltech.edu/7694/1/CNS-TR-2007-001.pdf
[49] Deng J, Dong W, Socher R, et al. Imagenet: A Large-Scale Hierarchical Image Database // Proc of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Miami, USA, 2009: 248-255
[50] Torralba A, Fergus R, Freeman W T. 80 Million Tiny Images: A Large Data Set for Nonparametric Object and Scene Recognition. IEEE Trans on Pattern Analysis and Machine Intelligence, 2008, 30(11): 1958-1970
[51] Wang Mei, Zhou Xiangdong, Xu Hongtao, et al. Effective Image Auto-Annotation via Discriminative Hyperplane Tree Based Generative Model. Journal of Software, 2009, 20(9): 2450-2461 (in Chinese)
(王 梅,周向东,许红涛,等.基于可判别超平面树的生成模型图像标注方法.软件学报, 2009, 20(9): 2450-2461)
[52]Jiang Lixing, Hou Jin. Image Annotation Using the Ensemble Learning. Acta Automatica Sinica, 2012, 38(8): 1257-1262 (in Chinese)
(蒋黎星,侯 进.基于集成分类算法的自动图像标注.自动化学报, 2012, 38(8): 1257-1262)
[53] Breiman L, Friedman J H, Olshen R A, et al. Classification and Regression Trees. New York, USA: Wadsworth, 1984
[54] Quinlan J R. C4.5: Programs for Machine Learning. San Francisco, USA: Morgan Kaufmann, 1993
[55] Jordan M I, Jacobs R A. Hierarchical Mixtures of Experts and the EM algorithm. Neural Computation, 1994, 6(2): 181-214
[56] Bishop C M, Svensén M. Bayesian Hierarchical Mixtures of Experts // Proc of the 19th Conference on Uncertainty in Artificial Intelligence. Burlington, Canada, 2003: 57-64
[57] Zhou Zhihua. Ensemble Methods: Foundations and Algorithms. Boca Raton, USA: CRC Press, 2012
[58] Cesa-Bianchi N, Gentile C, Zaniboni L. Incremental Algorithms for Hierarchical Classification. Journal of Machine Learning Research, 2006, 7: 31-54
[59] Rousu J, Saunders C, Szedmak S, et al. Kernel-Based Learning of Hierarchical Multilabel Classification Models. Journal of Machine Learning Research, 2006, 7: 1601-1626
[60] Vens C, Struyf J, Schietgat L, et al. Decision Trees for Hierarchical Multi-Label Classification. Machine Learning, 2008, 73(2): 185-214
[61] Bi W, Kwok J T. Multilabel Classification on Tree- and Dag-Structured Hierarchies // Proc of the 28th International Conference on Machine Learning. New York, USA, 2011: 17-24
[62] Vateekul P. Hierarchical Multi-Label Classification: Going beyond Generalization Trees[EB/OL]. [2013-03-30]. http://scholarlyrepository.miami.edu/oa_dissertations/723/ |
|
|
|
2013, Vol. 26 
