Bellwether analysis: Searching for cost-effective query-defined predictors in large databases

ABSTRACT

How to mine massive datasets is a challenging problem with great potential value. Motivated by this challenge, much effort has concentrated on developing scalable versions of machine learning algorithms. However, the cost of mining large datasets is not just computational; preparing the datasets into the “right form” so that learning algorithms can be applied is usually costly, due to the human labor that is typically required and a large number of choices in data preparation, which include selecting different subsets of data and aggregating data at different granularities. We make the key observation that, for a number of practically motivated problems, these choices can be defined using database queries and analyzed in an automatic and systematic manner. Specifically, we propose a new class of data-mining problem, called bellwether analysis, in which the goal is to find a few query-defined predictors (e.g., first week sales of Peoria, IL of an item) that can be used to accurately predict the result of a target query (e.g., first year worldwide sales of the item) from a large number of queries that define candidate predictors. To make a prediction for a new item, the data needed to generate such predictors has to be collected (e.g., selling the new item in Peoria, IL for a week and collecting the sales data). A useful predictor is one that has high prediction accuracy and a low data-collection cost. We call such a cost-effective predictor a bellwether.

This article introduces bellwether analysis, which integrates database query processing and predictive modeling into a single framework, and provides scalable algorithms for large datasets that cannot fit in main memory. Through a series of extensive experiments, we show that bellwethers do exist in real-world databases, and that our computation techniques achieve good efficiency on large datasets.

REFERENCES

• 1: Sameet Agarwal , Rakesh Agrawal , Prasad Deshpande , Ashish Gupta , Jeffrey F. Naughton , Raghu Ramakrishnan , Sunita Sarawagi, On the Computation of Multidimensional Aggregates, Proceedings of the 22th International Conference on Very Large Data Bases, p.506-521, September 03-06, 1996
• 2: Edoardo Amaldi , Viggo Kann, On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, Theoretical Computer Science, v.209 n.1-2, p.237-260, Dec. 6, 1998 [doi>10.1016/S0304-3975(97)00115-1]
• 3: Benjamini, Y. and Yekutieli, D. 1995. Controlling the false discovery rate: A practical and powerful approach to multiple testing. J. Royal Statist. Soc. B 57, 1, 289--300.
• 4: Benjamini, Y. and Yekutieli, D. 2001. The control of the false discovery rate in multiple testing under dependency. Ann. Statist. 29, 4, 1165--1188.
• 5: Kevin Beyer , Raghu Ramakrishnan, Bottom-up computation of sparse and Iceberg CUBE, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.359-370, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 6: Breiman, L., Friedman, J., Stone, C. J., and Olshen, R. A. 1984. Classification and Regression Trees. Chapman & Hall.
• 7: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 8: 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
• 9: Damianos Chatziantoniou , Michael O. Akinde , Theodore Johnson , Samuel Kim, The MD-join: An Operator for Complex OLAP, Proceedings of the 17th International Conference on Data Engineering, p.524-533, April 02-06, 2001
• 10: Bee-Chung Chen , Raghu Ramakrishnan , Jude W. Shavlik , Pradeep Tamma, Bellwether analysis: predicting global aggregates from local regions, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 11: Bee-Chung Chen , Raghu Ramakrishnan, Cube-space data mining, University of Wisconsin at Madison, Madison, WI, 2008
• 12: Lei Chen , Raghu Ramakrishnan , Paul Barford , Bee-Chung Chen , Vinod Yegneswaran, Composite subset measures, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 13: Chvatal, V. 1979. A greedy heuristic for the set-covering problem. Math. Oper. Res. 4, 3, 233--235.
• 14: David Cohn , Les Atlas , Richard Ladner, Improving Generalization with Active Learning, Machine Learning, v.15 n.2, p.201-221, May 1994 [doi>10.1023/A:1022673506211]
• 15: Gregory F. Cooper , Edward Herskovits, A Bayesian Method for the Induction of Probabilistic Networks from Data, Machine Learning, v.9 n.4, p.309-347, Oct. 1992 [doi>10.1023/A:1022649401552]
• 16: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 17: Thomas G. Dietterich , Richard H. Lathrop , Tomás Lozano-Pérez, Solving the multiple instance problem with axis-parallel rectangles, Artificial Intelligence, v.89 n.1-2, p.31-71, Jan. 1997 [doi>10.1016/S0004-3702(96)00034-3]
• 18: Efron, B. 2005. Local false discovery rates. Tech. rep. 2005-20B/234, Department of Statistics, Stanford Univerity, California.
• 19: Nir Friedman , Lise Getoor , Daphne Koller , Avi Pfeffer, Learning Probabilistic Relational Models, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1300-1309, July 31-August 06, 1999
• 20: Johannes Gehrke , Raghu Ramakrishnan , Venkatesh Ganti, RainForest - A Framework for Fast Decision Tree Construction of Large Datasets, Proceedings of the 24rd International Conference on Very Large Data Bases, p.416-427, August 24-27, 1998
• 21: Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843]
• 22: Russell Greiner , Adam J. Grove , Dan Roth, Learning cost-sensitive active classifiers, Artificial Intelligence, v.139 n.2, p.137-174, August 2002 [doi>10.1016/S0004-3702(02)00209-6]
• 23: Isabelle Guyon , André Elisseeff, An introduction to variable and feature selection, The Journal of Machine Learning Research, 3, 3/1/2003
• 24: Hamilton, J. 1994. Time Series Analysis. Princeton University Press.
• 25: Jiawei Han , Jian Pei , Guozhu Dong , Ke Wang, Efficient computation of Iceberg cubes with complex measures, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.1-12, May 21-24, 2001, Santa Barbara, California, United States
• 26: Simon Haykin, Neural Networks: A Comprehensive Foundation (3rd Edition), Prentice-Hall, Inc., Upper Saddle River, NJ, 2007
• 27: Kapoor, A. and Greiner, R. 2005. Learning and classifying under hard budgets. In Proceedings of the 16th European Conference on Machine Learning (ECML'05). Lecture Notes in Computer Science, vol. 3720, 170--181.
• 28: Xiaolei Li , Jiawei Han , Hector Gonzalez, High-dimensional OLAP: a minimal cubing approach, Proceedings of the Thirtieth international conference on Very large data bases, p.528-539, August 31-September 03, 2004, Toronto, Canada
• 29: 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]
• 30: Lizotte, D., Madani, O., and Greiner, R. 2003. Budgeted learning of naïve-Bayes classifiers. In Proceedings of the 19th Conference of Uncertainty in Artificial Intelligence (UAI'03).
• 31: Mehta, M., Rissanen, J., and Agrawal, R. 1995. MDL-Based decision tree pruning. In Proceedings of the International Conference on Knowledge Discovery and Data Mining (KDD'95), 216--221.
• 32: 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
• 33: Prem Melville , Maytal Saar-Tsechansky , Foster Provost , Raymond Mooney, An Expected Utility Approach to Active Feature-Value Acquisition, Proceedings of the Fifth IEEE International Conference on Data Mining, p.745-748, November 27-30, 2005 [doi>10.1109/ICDM.2005.23]
• 34: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 35: Raymond T. Ng , Alan Wagner , Yu Yin, Iceberg-cube computation with PC clusters, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.25-36, May 21-24, 2001, Santa Barbara, California, United States
• 36: Claudia Perlich , Foster Provost, Aggregation-based feature invention and relational concept classes, 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.956772]
• 37: J. R. Quinlan , R. L. Rivest, Inferring decision trees using the minimum description length principle, Information and Computation, v.80 n.3, p.227-248, Mar. 1989 [doi>10.1016/0890-5401(89)90010-2]
• 38: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 39: Raghu Ramakrishnan , Johannes Gehrke, Database Management Systems, McGraw-Hill Science/Engineering/Math, 2002
• 40: Raghu Ramakrishnan , Bee-Chung Chen, Exploratory mining in cube space, Data Mining and Knowledge Discovery, v.15 n.1, p.29-54, August 2007 [doi>10.1007/s10618-007-0063-0]
• 41: Soumya Ray , Mark Craven, Supervised versus multiple instance learning: an empirical comparison, Proceedings of the 22nd international conference on Machine learning, p.697-704, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102439]
• 42: Kenneth A. Ross , Divesh Srivastava , Damianos Chatziantoniou, Complex Aggregation at Multiple Granularities, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.263-277, March 23-27, 1998
• 43: David E. Rumelhart , James L. McClelland , CORPORATE PDP Research Group, Parallel distributed processing: explorations in the microstructure of cognition, vol. 2: psychological and biological models, MIT Press, Cambridge, MA, 1986
• 44: Seber, G. and Lee, A. 2003. Linear Regression Analysis. John Wiley & Sons.
• 45: Zheng Shao , Jiawei Han , Dong Xin, MM-Cubing: Computing Iceberg Cubes by Factorizing the Lattice Space, Proceedings of the 16th International Conference on Scientific and Statistical Database Management, p.213, June 21-23, 2004 [doi>10.1109/SSDBM.2004.53]
• 46: Victor S. Sheng , Charles X. Ling, Feature value acquisition in testing: a sequential batch test algorithm, Proceedings of the 23rd international conference on Machine learning, p.809-816, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143946]
• 47: 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]
• 48: Turney, P. D. 1995. Cost-Sensitive classification: Empirical evaluation of a hybrid genetic decision tree induction algorithm. J. Artif. Intell. Res. 2, 369--409.
• 49: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 50: Geoffrey I. Webb, Discovering significant rules, 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.1150451]
• 51: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 52: Dong Xin , Jiawei Han , Xiaolei Li , Benjamin W. Wah, Star-cubing: computing iceberg cubes by top-down and bottom-up integration, Proceedings of the 29th international conference on Very large data bases, p.476-487, September 09-12, 2003, Berlin, Germany
• 53: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Correlation and regression analysis

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

General Terms:
Algorithms, Design, Performance

Keywords:
Cost-effective prediction, OLAP queries, bellwether, data cube, predictive models, scalable algorithms