Enhance Top-down method with Meta-Classification for Very Large-scale Hierarchical Classification

Proceedings of the 5th International Joint Conference on Natural Language Processing, pages 1089–1097, Chiang Mai, Thailand, November 8 – 13, 2011. c⃝2011 AFNLP Enhance Top-down method with Meta-Classification for Very Large-scale Hierarchical Classification ∗ Xiao-Lin Wang1,2, Hai Zhao1,2, Bao-Liang Lu1,2† 1Center for Brain-Like Computing and Machine Intelligence Department of Computer Science and Engineering, Shanghai Jiao Tong University 2MOE-Microsoft Key Laboratory for Intelligent Computing and Intelligent Systems Shanghai Jiao Tong University 800 Dong Chuan Rd., Shanghai 200240, China arthur.xl.wang@gmail.com, {zhaohai; blu}@cs.sjtu.edu.cn Abstract Recent large-scale hierarchical classifica- tion tasks typically have tens of thousand- s of classes as well as a large number of samples, for which the dominant solution is the top-down method due to computa- tional complexity. However, the top-down method suffers from accuracy deficiency, that is, its accuracy is generally lower than that of the flat approach of 1-vs-Rest. In this paper, we employ meta-classification technique to enhance the classifying pro- cedure of the top-down method. We an- alyze the proposed method on the aspect of accuracy, and then test it with two real- world large-scale data sets. Our method both maintains the efficiency of the con- ventional top-down method and provides competitive classification accuracies. 1 Introduction Test categorization, as a key technology of data mining, has received intensive study for decades. Recently, real-world applications have raised some large-scale tasks that typically have tens of t- housands of classes, where many established tech- niques such as the 1-vs-Rest multiclass classifica- tion fail due to computational complexity. Mean- while, those large-scale tasks usually employ hi- erarchies to organize the huge number of class- es that they have, which provides a clue to solve them. Such kind of tasks include categorizing ∗ This work was partially supported by the National Natural Science Foundation of China (Grant No. 60903119, Grant No. 61170114 and Grant No. 90820018), the National Basic Research Program of China (Grant No. 2009CB320901), the Science and Technology Commis- sion of Shanghai Municipality (Grant No. 09511502400), and the European Union Seventh Framework Programme (Grant No. 247619). † Corresponding author patent documents into the taxonomy of Interna- tional Patent Classification (IPC) (Fall et al., 2003; Fujii et al., 2007) and categorizing web pages into the directories of Open Directory Project (ODP) or Yahoo! (Labrou and Finin, 1999; Liu et al., 2005). The existing approaches to hierarchical classifi- cation mainly fall into two categories. One cate- gory aims at raising classification accuracy, which generally takes hierarchies as additional clue for classifying a sample besides its content. Such re- searches include hierarchical support vector ma- chines (SVM) (Cai and Hofmann, 2004; Tsochan- taridis et al., 2005), hierarchical Rocchio-like clas- sifiers (Labrou and Finin, 1999), min-max mod- ular network (Lu and Ito, 2002; Lu and Wang, 2009) and ensemble classifications (Punera and Ghosh, 2008). The other category aims at reducing computa- tional complexity. The main approach in this cat- egory is an ensemble classification method called top-down method (Bennett and Nguyen, 2009; Ce- ci and Malerba, 2007a; Koller and Sahami, 1997; Liu et al., …

Content truncated to 500 words