Quantifying trends accurately despite classifier error and class imbalance

ABSTRACT

This paper promotes a new task for supervised machine learning research: quantification - the pursuit of learning methods for accurately estimating the class distribution of a test set, with no concern for predictions on individual cases. A variant for cost quantification addresses the need to total up costs according to categories predicted by imperfect classifiers. These tasks cover a large and important family of applications that measure trends over time.The paper establishes a research methodology, and uses it to evaluate several proposed methods that involve selecting the classification threshold in a way that would spoil the accuracy of individual classifications. In empirical tests, Median Sweep methods show outstanding ability to estimate the class distribution, despite wide disparity in testing and training conditions. The paper addresses shifting class priors and costs, but not concept drift in general.

REFERENCES

• 1: Fawcett, T. ROC graphs: notes and practical considerations for data mining researchers. Hewlett-Packard Labs, Tech Report HPL-2003-4, 2003. www.hpl.hp.com/techreports
• 2: Tom Fawcett , Peter A. Flach, A Response to Webb and Ting's On the Application of ROC Analysis to Predict Classification Performance Under Varying Class Distributions, Machine Learning, v.58 n.1, p.33-38, January 2005 [doi>10.1007/s10994-005-5256-4]
• 3: George Forman , Evan Kirshenbaum , Jaap Suermondt, Pragmatic text mining: minimizing human effort to quantify many issues in call logs, 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.1150520]
• 4: Forman, G. Counting positives accurately despite inaccurate classification. In Proc. of the 16th European Conf. on Machine Learning (ECML, Porto):564--575, 2005.
• 5: George Forman, An extensive empirical study of feature selection metrics for text classification, The Journal of Machine Learning Research, 3, 3/1/2003
• 6: Eui-Hong Han , George Karypis, Centroid-Based Document Classification: Analysis and Experimental Results, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.424-431, September 13-16, 2000
• 7: Susan Havre , Elizabeth Hetzler , Paul Whitney , Lucy Nowell, ThemeRiver: Visualizing Thematic Changes in Large Document Collections, IEEE Transactions on Visualization and Computer Graphics, v.8 n.1, p.9-20, January 2002 [doi>10.1109/2945.981848]
• 8: Qiaozhu Mei , ChengXiang Zhai, Discovering evolutionary theme patterns from text: an exploration of temporal text mining, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081895]
• 9: Marco Saerens , Patrice Latinne , Christine Decaestecker, Adjusting the outputs of a classifier to new a priori probabilities: a simple procedure, Neural Computation, v.14 n.1, p.21-41, January 2002 [doi>10.1162/089976602753284446]
• 10: Slobodan Vucetic , Zoran Obradovic, Classification on Data with Biased Class Distribution, Proceedings of the 12th European Conference on Machine Learning, p.527-538, September 05-07, 2001
• 11: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 12: Gang Wu , Edward Y. Chang, KBA: Kernel Boundary Alignment Considering Imbalanced Data Distribution, IEEE Transactions on Knowledge and Data Engineering, v.17 n.6, p.786-795, June 2005 [doi>10.1109/TKDE.2005.95]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Design, Measurement

Keywords:
classification, cost quantification, quantification, text mining