Partial example acquisition in cost-sensitive learning

ABSTRACT

It is often expensive to acquire data in real-world data mining applications. Most previous data mining and machine learning research, however, assumes that a fixed set of training examples is given. In this paper, we propose an online cost-sensitive framework that allows a learner to dynamically acquire examples as it learns, and to decide the ideal number of examples needed to minimize the total cost. We also propose a new strategy for Partial Example Acquisition (PAS), in which the learner can acquire examples with a subset of attribute values to reduce the data acquisition cost. Experiments on UCI datasets show that the new PAS strategy is an effective method in reducing the total cost for data acquisition.

REFERENCES

• 1: Yoram Baram , Ran El-Yaniv , Kobi Luz, Online Choice of Active Learning Algorithms, The Journal of Machine Learning Research, 5, p.255-291, 12/1/2004
• 2: Blake, C. L., and Merz, C. J. 1998. UCI Repository of machine learning databases (website). Irvine, CA: University of California, Department of Information and Computer Science.
• 3: Cestnik, B. 1990. Estimating probabilities: A crucial task in machine learning. In Proceedings of the 9th European Conference on Artificial Intelligence, 147--149, Sweden.
• 4: Xiaoyong Chai , Lin Deng , Qiang Yang , Charles X. Ling, Test-Cost Sensitive Naive Bayes Classification, Proceedings of the Fourth IEEE International Conference on Data Mining, p.51-58, November 01-04, 2004
• 5: Pedro Domingos, MetaCost: a general method for making classifiers cost-sensitive, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.155-164, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312220]
• 6: Elkan, C. 2001. The Foundations of Cost-Sensitive Learning. In Proceedings of the Seventeenth International Joint Conference of Artificial Intelligence, 973--978. Seattle, Washington: Morgan Kaufmann.
• 7: Fayyad, U. M., and Irani, K. B. 1993. Multi-interval discretization of continuous-valued attributes for classification learning. In Proceedings of the 13th International Joint Conference on Artificial Intelligence, 1022--1027. France: Morgan Kaufmann.
• 8: Good, I. J. 1965. The estimation of probabilities: An essay on modern Bayesian methods. M.I.T. Press, Cambridge, Mass.
• 9: Kapoor, A., and Greiner, R. 2005. Learning and Classifying under Hard Budgets. In Proceedings of the 16th European Conference on Machine Learning (Porto, Portugal), Springer, 170--181.
• 10: Lizotte, D., Madani, O., and Greiner R. 2003. Budgeted Learning of Naive--Bayes Classifiers. In Proceeding of the Conference on Uncertainty in Artificial Intelligence, Acapulco, Mexico, August 2003.
• 11: Charles X. Ling , Qiang Yang , Jianning Wang , Shichao Zhang, Decision trees with minimal costs, Proceedings of the twenty-first international conference on Machine learning, p.69, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015369]
• 12: Margineantu, D.D. 2005. Active Cost-Sensitive Learning. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Edinburgh, Scotland.
• 13: Prem Melville , Maytal Saar-Tsechansky , Foster Provost , Raymond Mooney, Active Feature-Value Acquisition for Classifier Induction, Proceedings of the Fourth IEEE International Conference on Data Mining, p.483-486, November 01-04, 2004
• 14: Prem Melville , Foster Provost , Maytal Saar-Tsechansky , Raymond Mooney, Economical active feature-value acquisition through Expected Utility estimation, Proceedings of the 1st international workshop on Utility-based data mining, p.10-16, August 21-21, 2005, Chicago, Illinois [doi>10.1145/1089827.1089828]
• 15: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 16: Nicholas Roy , Andrew McCallum, Toward Optimal Active Learning through Sampling Estimation of Error Reduction, Proceedings of the Eighteenth International Conference on Machine Learning, p.441-448, June 28-July 01, 2001
• 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: Kai Ming Ting, Inducing Cost-Sensitive Trees via Instance Weighting, Proceedings of the Second European Symposium on Principles of Data Mining and Knowledge Discovery, p.139-147, September 23-26, 1998
• 19: Simon Tong , Daphne Koller, Support vector machine active learning with applications to text classification, The Journal of Machine Learning Research, 2, p.45-66, 3/1/2002 [doi>10.1162/153244302760185243]
• 20: Turney, P. D. 2000. Types of cost in inductive concept learning. In Proceedings of the Workshop on Cost-Sensitive Learning at the Seventeenth International Conference on Machine Learning, Stanford University, California.
• 21: Turney, P. D. 1995. Cost-Sensitive Classification: Empirical Evaluation of a Hybrid Genetic Decision Tree Induction Algorithm. Journal of Artificial Intelligence Research 2:369--409.
• 22: Sarah Zelikovitz , Haym Hirsh, Improving Short-Text Classification using Unlabeled Data for Classification Problems, Proceedings of the Seventeenth International Conference on Machine Learning, p.1191-1198, June 29-July 02, 2000
• 23: Xingquan Zhu , Xindong Wu, Cost-Constrained Data Acquisition for Intelligent Data Preparation, IEEE Transactions on Knowledge and Data Engineering, v.17 n.11, p.1542-1556, November 2005 [doi>10.1109/TKDE.2005.176]
• 24: Valentina Bayer Zubek , Thomas G. Dietterich, Pruning Improves Heuristic Search for Cost-Sensitive Learning, Proceedings of the Nineteenth International Conference on Machine Learning, p.19-26, July 08-12, 2002

INDEX TERMS

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

General Terms:
Algorithms, Economics, Measurement, Performance

Keywords:
active cost-sensitive learning, active learning, cost-sensitive learning, data acquisition, data mining, induction, interactive and online data mining, machine learning