jmlr jmlr2007 jmlr2007-52 jmlr2007-52-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Robert Tibshirani, Trevor Hastie
Abstract: We propose a method for the classification of more than two classes, from high-dimensional features. Our approach is to build a binary decision tree in a top-down manner, using the optimal margin classifier at each split. We implement an exact greedy algorithm for this task, and compare its performance to less greedy procedures based on clustering of the matrix of pairwise margins. We compare the performance of the “margin tree” to the closely related “all-pairs” (one versus one) support vector machine, and nearest centroids on a number of cancer microarray data sets. We also develop a simple method for feature selection. We find that the margin tree has accuracy that is competitive with other methods and offers additional interpretability in its putative grouping of the classes. Keywords: maximum margin classifier, support vector machine, decision tree, CART
A. Alizadeh, M. Eisen, R. E. Davis, C. Ma, I. Lossos, A. Rosenwal, J. Boldrick, H. Sabet, T. Tran, X. Yu, Pwellm J., G. Marti, T. Moore, J. Hudsom, L. Lu, D. Lewis, R. Tibshirani, G. Sherlock, W. Chan, T. Greiner, D. Weisenburger, K. Armitage, R. Levy, W. Wilson, M. Greve, J. Byrd, D. Botstein, P. Brown, and L. Staudt. Identification of molecularly and clinically distinct substypes of diffuse large b cell lymphoma by gene expression profiling. Nature, 403:503–511, 2000. K. Bennett and J. Blue. A support vector machine approach to decision trees. Technical report, Rensselaer Polytechnic Institute, Troy, NY, 1997. R.P.I Math Report No. 97-100. L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, 1984. I. Guyon, J. Weston, S. Barnhill, and V. Vapnik. Gene selection for cancer classification using support vector machines. Machine Learning, pages 389–422, 2002. J. Khan, J. S. Wei, M. Ringn´ r, L. H. Saal, M. Ladanyi, F. Westermann, F. Berthold, M. Schwab, e C. R. Antonescu, C. Peterson, and P. S. Meltzer. Classification and diagnostic prediction of cancers using gene expression profiling and artificial neural networks. Nature Medicine, 7:673– 679, 2001. H. Kim and W.Y. Loh. Classification trees with unbiased multiway splits. Journal of the American Statistical Association, 96:589–604, 2001. Y. Lee, Y. Lin, and G. Wahba. Multicategory support vector machines, theory, and application to the classification of microarray data and satellite radiance data. Journal of the Amer. Statist. Assoc., 99:67–81, 2004. W.Y. Loh and N. Vanichsetakul. Tree structured classification via generalized discriminant analysis. Journal of the American Statistical Association, 83:715–728, 1988. 651 T IBSHIRANI AND H ASTIE K. Munagala, R. Tibshirani, and P. Brown. Cancer characterization and feature set extraction by discriminative margin clustering. BMC Bioinformatics, 5:5–21, 2004. M. Y. Park and T. Hastie. Hierarchical classification using shrunken centroids. Technical report, Stanford University, 2005. S. L. Pomeroy, P Tamayo, M. Gaasenbeek, L. M. Sturla, M. Angelo, M. E. McLaughlin, J. Y. Kim, L. C. Goumnerova, P. M. Black, C. Lau, J. C. Allen, D. Zagzag, J. M. Olson, T. Curran, C. Wetmore, J. A. Biegel, T. Poggio, S. Mukherjee, R. Rifkin, A. Califano, G. Stolovitzky, D. N. Louis, J. P. Mesirov, E. S. Lander, and T. R. Golub. Prediction of central nervous system embryonal tumour outcome based on gene expression. Nature, 5:436–42, 2002. R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, San Mateo, 1993. S. Ramaswamy, P. Tamayo, R. Rifkin, S. Mukherjee, C. Yeang, M. Angelo, C. Ladd, M. Reich, E. Latulippe, J. Mesirov, T. Poggio, W. Gerald, M. Loda, E. Lander, and T. Golub. Multiclass cancer diagnosis using tumor gene expression signature. PNAS, 98:15149–15154, 2001. S. Rosset, J. Zhu, and T. Hastie. Margin maximizing loss functions. In Advances in Neural Information Processing Systems, (NIPS*2005), 2005. A. Statnikov, C.F. Aliferis, I. Tsamardinos, D. Hardin, and S. Levy. A comprehensive evaluation of multicategory classification methods for microarray gene expression cancer diagnosis. Bioinformatics, pages 631–43, 2004. J.E. Staunton, D.K. Slonim, H.A. Coller, P. Tamayo, M.J. Angelo, U. Park, J. Scherf, J.K. Lee, W.O. Reinhold, and J.N. Weinstein. Chemosensitivity prediction by transcriptional profiling. Proc. Natl Acad. Sci. USA, 98:10787–10792, 2001. A.I. Su, J.B. Welsh, L.M. Sapinoso, S.G. Kern, P. Dimitrov, H. Lapp, P.G. Schultz, S.M. Powell, C.A. Moskaluk, H.F. Frierson, Jr, and G.M. Hampton. Molecular classification of human carcinomas by use of gene expression signatures. Cancer Research, 61:7388–7393, 2001. R. Tibshirani. The lasso method for variable selection in the cox model. Statistics in Medicine, 16: 385–395, 1997. R. Tibshirani, T. Hastie, B. Narasimhan, and G Chu. Diagnosis of multiple cancer types by shrunken centroids of gene expression. Proc. Natl. Acad. Sci., 99:6567–6572, 2001. V. Vural and J. G. Dy. A hierarchical method for multi-class support vector machines. 2004. International Conference on Machine Learning; Proceeding Series; Vol. 69. J. Weston and C. Watkins. Multi-class support vector machines. In M. Verleysen, editor, Proceedings of ESANN99. D. Facto Press, Brussels, 1999. J. Zhu, S. Rosset, T. Hastie, and R. Tibshirani. L1 norm support vector machines. Technical report, Stanford University, 2003. 652