Voting with a parameterized veto strategy: solving the KDD Cup 2006 problem by means of a classifier committee

ABSTRACT

This paper presents our winner solution for the KDD Cup 2006 problem. It is based on the results of three different supervised learning techniques which are then combined in a classifier committee, and finally a single solution is obtained with a voting procedure. The voting procedure assigns weights to each member of the committee according to their average performance on a ten-fold cross-validation test and it also takes into account the confidence values returned by the three algorithms. The final decision of the committee is determined by means of a parameterized veto strategy, which takes into consideration the maximal allowed error rate beside the confidence values of the committee members. The solution presented here won Task 2 and became runner-up at Task 1 in the competition.

REFERENCES

• 1: A. Blum. Empirical support for Winnow and weighted-majority based algorithms: results on a calendar scheduling domain. In Proc. of 12th Int. Conf. on Machine Learning, pages 64--72, San Francisco, CA, 1995. Morgan Kaufmann.
• 2: S.-B. Cho and J. Ryu. Classifying gene expression data of cancer using classifier ensemble with mutually exclusive features. Proc. IEEE, 90:1744--1753, 2002.
• 3: William W. Cohen , Yoram Singer, Context-sensitive learning methods for text categorization, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.307-315, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243278]
• 4: I. Dagan, Y. Karov, and D. Roth. Mistake-driven learning in text categorization. In C. Cardie and R. Weischedel, editors, Proc. of the 2nd Conf. on Empirical Methods in Natural Language Processing (EMNLP 97), pages 55--63. Association for Computational Linguistics, Somerset, New Jersey, 1997.
• 5: P. A. Devijver and J. Kittler. Pattern Recognition: A Statistical Approach. Prentice Hall, London, 1982.
• 6: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 7: A. A. Ghaibeh, S. Kuroyanagi, and A. Iwata. Efficient subspace learning using a large scale neural network Combnet-II. In Proc. of the 9th Int. Conf. on Neural Information Processing (ICONIP'02), volume 1, pages 447--451, Singapore, 2002.
• 8: A. R. Golding and D. Roth. Applying Winnow to context-sensitive spelling correction. In Proc. of 13th Int. Conf. on Machine Learning, pages 182--190, Bari, Italy, 1996. Morgan Kaufmann.
• 9: T. Hastie, R. Tibshirani, and J. H. Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer, 2001.
• 10: Zsolt T. Kardkovács , Domonkos Tikk , Zoltán Bánsághi, The Ferrety algorithm for the KDD Cup 2005 problem, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.111-116, December 2005 [doi>10.1145/1117454.1117468]
• 11: J. Kittler. Feature set search algorithms. In C. H. Chen, editor, Pattern Recognition and Signal Processing, pages 41--60. Sijthoff & Noordhoff, Alphen aan den Rijn, The Netherlands, 1978.
• 12: M. Kugler, K. Aoki, S. Kuroyanagi, A. Iwata, and A. S. Nugroho. Feature subset selection for support vector machines using confident margin. In Proc. of the IEEE Int. Joint Conf. on Neural Networks (IJCNN'05), volume 2, pages 907--912, Montréal, Canada, 2005.
• 13: Y. H. Li and A. K. Jain. Classification of text documents. The Computer Journal, 41(8):537--546, 1998.
• 14: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• 15: N. Littlestone. Comparing sereval linear-threshold learning algorithm on tasks involving superfluous attributes. In Proc. of 12th Int. Conf. on Machine Learning, pages 353--361, San Francisco, CA, 1995. Morgan Kaufmann.
• 16: T. Marill and D. Green. On the effectiveness of receptors in recognition systems. IEEE Trans. on Information Theory, 9:11--17, 1963.
• 17: F. Rosenblatt, The perception: a probabilistic model for information storage and organization in the brain, Neurocomputing: foundations of research, MIT Press, Cambridge, MA, 1988
• 18: Robert E. Schapire , Yoram Singer, BoosTexter: A Boosting-based Systemfor Text Categorization, Machine Learning, v.39 n.2-3, p.135-168, May-June 2000
• 19: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 20: Dou Shen , Rong Pan , Jian-Tao Sun , Jeffrey Junfeng Pan , Kangheng Wu , Jie Yin , Qiang Yang, Q²C@UST: our winning solution to query classification in KDDCUP 2005, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.100-110, December 2005 [doi>10.1145/1117454.1117467]
• 21: Dou Shen , Jian-Tao Sun , Qiang Yang , Zheng Chen, Building bridges for web query classification, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148196]
• 22: W. Siedlecki and J. Sklansky. On automatic feature selection. Int. J. of Pattern Recognition and Artificial Intelligence, 2(2):197--220, 1988.
• 23: Domonkos Tikk , György Biró, Experiment with a hierarchical text categorization method on the WIPO-alpha patent collection, Proceedings of the 4th International Symposium on Uncertainty Modelling and Analysis, p.104, September 21-24, 2003
• 24: D. Tikk, G. Biró, and A. Törcsvári. A hierarchical online classifier for patent categorization. In H. A. do Prado and E. Ferneda, editors, Emerging Technologies of Text Mining: Techniques and Applications. Idea Group Inc., 2006. (in press).
• 25: D. Tikk, G. Biró, and J. D. Yang. A hierarchical text categorization approach and its application to FRT expansion. Australian Journal of Intelligent Information Processing Systems, 8(3):123--131, 2004.
• 26: D. Tikk, T. D. Gedeon, and K. W. Wong. A feature ranking algorithm for fuzzy modelling problems. In J. Casillas, O. Cordón, F. Herrera, and L. Magdalena, editors, Interpretability Issues in Fuzzy Modeling, number 128 in Studies in Fuzziness and Soft Computing, pages 176--192. Springer-Verlag, Heidelberg, 2003.
• 27: K. Tumer and J. Ghosh. Error correlation and error reduction in ensemble classifiers. Connection Sci., 8(3--4):385--403, 1996.
• 28: Haixun Wang , Wei Fan , Philip S. Yu , Jiawei Han, Mining concept-drifting data streams using ensemble classifiers, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956778]
• 29: Sholom M. Weiss , Chidanand Apte , Fred J. Damerau , David E. Johnson , Frank J. Oles , Thilo Goetz , Thomas Hampp, Maximizing Text-Mining Performance, IEEE Intelligent Systems, v.14 n.4, p.63-69, July 1999 [doi>10.1109/5254.784086 ]