Improving data mining utility with projective sampling

ABSTRACT

Overall performance of the data mining process depends not just on the value of the induced knowledge but also on various costs of the process itself such as the cost of acquiring and pre-processing training examples, the CPU cost of model induction, and the cost of committed errors. Recently, several progressive sampling strategies for maximizing the overall data mining utility have been proposed. All these strategies are based on repeated acquisitions of additional training examples until a utility decrease is observed. In this paper, we present an alternative, projective sampling strategy, which fits functions to a partial learning curve and a partial run-time curve obtained from a small subset of potentially available data and then uses these projected functions to analytically estimate the optimal training set size. The proposed approach is evaluated on a variety of benchmark datasets using the RapidMiner environment for machine learning and data mining processes. The results show that the learning and run-time curves projected from only several data points can lead to a cheaper data mining process than the common progressive sampling methods.

REFERENCES

• 1: Asuncion, A.&Newman, D.J. 2007. UCI Machine Learning Repository {http://www.ics.uci.edu/~mlearn/MLRepository.html}. Irvine, CA: University of California, School of Information and Computer Science.
• 2: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 3: Rich Caruana , Thorsten Joachims , Lars Backstrom, KDD-Cup 2004: results and analysis, ACM SIGKDD Explorations Newsletter, v.6 n.2, December 2004 [doi>10.1145/1046456.1046470]
• 4: Everitt, B. 2001 Statistics for Psychologists: An Intermediate Course. Lawrence Erlbaum Associates.
• 5: Frey L. J. and Fisher, D. H. 1999. Modeling Decision Tree Performance with the Power Law. In Proceedings of the Seventh International Workshop on Artificial Intelligence and Statistics, 59--65.
• 6: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 7: Hastie, T., Tibshirani, R., and Friedman, J. 2003 The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Verlag.
• 8: Hettich, S. and Bay, S. D. 1999 The UCI KDD Archive {http://kdd.ics.uci.edu}. Irvine, CA: University of California, Department of Information and Computer Science.
• 9: John G. and Langley, P. 1996. Static versus dynamic sampling for data mining. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, AAAI Press, 367--370.
• 10: Mark Last, Predicting and Optimizing Classifier Utility with the Power Law, Proceedings of the Seventh IEEE International Conference on Data Mining Workshops, p.219-224, October 28-31, 2007 [doi>10.1109/ICDMW.2007.73]
• 11: Mark Last , Oded Maimon, A Compact and Accurate Model for Classification, IEEE Transactions on Knowledge and Data Engineering, v.16 n.2, p.203-215, February 2004 [doi>10.1109/TKDE.2004.1269598]
• 12: Ingo Mierswa , Michael Wurst , Ralf Klinkenberg , Martin Scholz , Timm Euler, YALE: rapid prototyping for complex data mining tasks, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150531]
• 13: Minium, E.W., Clarke, R.C., and Coladarci, T. 1999. Elements of Statistical Reasoning. New York: John Wiley&Sons, Inc. 2nd Ed.
• 14: Montgomery, D.C., Runger, G.C., Hubele, N.F. 2007. Engineering Statistics, John Wiley&Sons, Inc. 4th Edition.
• 15: Foster Provost , David Jensen , Tim Oates, Efficient progressive sampling, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.23-32, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312188]
• 16: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 17: Maytal Saar-Tsechansky , Foster Provost, Active Sampling for Class Probability Estimation and Ranking, Machine Learning, v.54 n.2, p.153-178, February 2004 [doi>10.1023/B:MACH.0000011806.12374.c3]
• 18: Victor S. Sheng , Charles X. Ling, Partial example acquisition in cost-sensitive learning, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281261]
• 19: Victor S. Sheng , Foster Provost , Panagiotis G. Ipeirotis, Get another label? improving data quality and data mining using multiple, noisy labelers, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401965]
• 20: Singh, S. 2005 Modeling Performance of Different Classification Methods: Deviation from the Power Law. Project Report, Department of Computer Science, Vanderbilt University, USA (April 2005).
• 21: Gary M. Weiss , Ye Tian, Maximizing classifier utility when there are data acquisition and modeling costs, Data Mining and Knowledge Discovery, v.17 n.2, p.253-282, October 2008 [doi>10.1007/s10618-007-0082-x]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

General Terms:
Algorithms, Economics, Experimentation, Measurement, Performance

Keywords:
active learning, classification, cost-sensitive learning, data acquisition, optimization, utility-based data mining