Efficient progressive sampling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient progressive sampling

Full text

Pdf (1.21 MB)

Source

International Conference on Knowledge Discovery and Data Mining archive
Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining table of contents

San Diego, California, United States

Pages: 23 - 32

Year of Publication: 1999

ISBN:1-58113-143-7

Authors

Foster Provost	Bell Atlantic Science and Technology, 500 Westchester Avenue, White Plains, New York
David Jensen	Computer Science Department, University of Massachusetts, Amherst, MA
Tim Oates	Computer Science Department, University of Massachusetts, Amherst, MA

Sponsors

SIGKDD: ACM Special Interest Group on Knowledge Discovery in Data
AAAI : Am Assoc for Artifical Intelligence
SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 66, Citation Count: 56

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/312129.312188 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
	2	CATLETT, J. Megainduction: A test flight. In Proceedings of the Eighth International Workshop on Machine Learning (1991), Morgan Kaufmann, pp. 596-599.
	3	CATLETT, J. Megainduction: Machine learning on very large databases. PhD thesis, School of Computer Science, University of Technology, Sydney, Australia, 1991.
	4	FREY, L. J., AND FISHER, D. H. Modeling decision tree performance with the power law. In Proceedings of the Seventh International Workshop on Artificial Intelligence and Statistics (1999), D. Heckerman and J. Whittaker, Eds., San Francisco, CA: Morgan Kaufmann.
	5	F/JRNKRANZ, J. Integrative windowing. Journal of Artificial Intelligence Research 8 (1998), 129-164.
	6	HARRIS-JONES, C., AND HAINES, T. L. Sample size and misclassification: Is more always better? Working Paper AMSCAT-WP-97-118, AMS Center for Advanced Technologies, 1997.
	7	David Haussler , Michael Kearns , H. Sebastian Seung , Naftali Tishby, Rigorous learning curve bounds from statistical mechanics, Machine Learning, v.25 n.2-3, p.195-236, Nov./Dec. 1996 [doi>10.1007/BF00114010]
	8	JOHN, G., AND LANGLEY, P. Static versus dynamic sampling for data mining. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (1996), AAAI Press, pp. 367-370.
	9	Richard E. Korf, Depth-first iterative-deepening: an optimal admissible tree search, Artificial Intelligence, v.27 n.1, p.97-109, Sept. 1985 [doi>10.1016/0004-3702(85)90084-0]
	10	MERz, C. J., AND MURPHY, P. M. UCI repository of machine learning databases, http-// www. ics. uci. edu/~mlearn/MLRepository, html, 1997.
	11	MUSICK, R., CATLETT, J., AND RUSSELL, S. Decision theoretic subsampling for induction on large databases. In Proceedings of the Tenth International Conference on Machine Learning (San Mateo, CA, 1993), Morgan Kaufmann, pp. 212-219.
	12	Tim Oates , David Jensen, The Effects of Training Set Size on Decision Tree Complexity, Proceedings of the Fourteenth International Conference on Machine Learning, p.254-262, July 08-12, 1997
	13	OATES, T., AND JENSEN, D. Large data sets lead to overly complex models: an explanation and a solution. In Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD-99) (1998), R. Agrawal and P. Stolorz, Eds., Menlo Park, CA: AAAI Press, pp. 294-298.
	14	Foster Provost , Venkateswarlu Kolluri, A Survey of Methods for Scaling Up Inductive Algorithms, Data Mining and Knowledge Discovery, v.3 n.2, p.131-169, June 1999 [doi>10.1023/A:1009876119989]
	15	PROVOST, F. J. Iterative weakening: Optimal and near-optimal policies for the selection of search bias. In Proceedings of the Eleventh National Conference on Artificial Intelligence (749-755, 1993), AAAI Press, pp. Menlo Park, CA.
	16	QUINLAN, J. Learning efficient classification procedures and their application to chess endgames. In Machine Learning: An AI approach, R. Michalski, C. J., and T. Mitchell, Eds. Morgan Kaufmann., Los Altos, CA, 1983.
	17	J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
	18	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
	19	WATKIN, T., RAU, A., AND BIEHL, M. The statistical mechanics of learning a rule. Reviews of Modern Physics 65 (1993), 499-556.

CITED BY 56

	Dimuthu Makawita , Kian-Lee Tan , Huan Liu, Sampling from databases using B+-trees, Proceedings of the ninth international conference on Information and knowledge management, p.158-164, November 06-11, 2000, McLean, Virginia, United States
	Wenke Lee, Applying data mining to intrusion detection: the quest for automation, efficiency, and credibility, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.35-42, December 2002
	Vijay S. Iyengar , Chidanand Apte , Tong Zhang, Active learning using adaptive resampling, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.91-98, August 20-23, 2000, Boston, Massachusetts, United States
	Tapio Elomaa , Matti Kääriäinen, Progressive rademacher sampling, Eighteenth national conference on Artificial intelligence, p.140-145, July 28-August 01, 2002, Edmonton, Alberta, Canada
	Claudia Perlich , Foster Provost , Jeffrey S. Simonoff, Tree induction vs. logistic regression: a learning-curve analysis, The Journal of Machine Learning Research, 4, p.211-255, 12/1/2003
	Nitesh V. Chawla , Thomas E. Moore , Lawrence O. Hall , Kevin W. Bowyer , W. Philip Kegelmeyer , Clayton Springer, Distributed learning with bagging-like performance, Pattern Recognition Letters, v.24 n.1-3, p.455-471, January 2003
	Pedro Domingos, Machine learning, Handbook of data mining and knowledge discovery, Oxford University Press, Inc., New York, NY, 2002
	Geoff Hulten , Pedro Domingos, Mining complex models from arbitrarily large databases in constant time, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
	Hang Yu , Ee-Chien Chang, Distributed multivariate regression based on influential observations, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	Foster Provost , Venkateswarlu Kolluri, Data mining tasks and methods: scalability, Handbook of data mining and knowledge discovery, Oxford University Press, Inc., New York, NY, 2002
	Pedro Domingos , Geoff Hulten, Mining high-speed data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.71-80, August 20-23, 2000, Boston, Massachusetts, United States
	Deok-Hwan Kim , Seok-Lyong Lee , Chin-Wan Chung, Heterogeneous image database selection on the web, Journal of Systems and Software, v.64 n.2, p.131-149, 15 November 2002
	Christopher Meek , Bo Thiesson , David Heckerman, The learning-curve sampling method applied to model-based clustering, The Journal of Machine Learning Research, 2, p.397-418, 3/1/2002
	Iris Hendrickx , Antal van den Bosch, Memory-based one-step named-entity recognition: effects of seed list features, classifier stacking, and unannotated data, Proceedings of the seventh conference on Natural language learning at HLT-NAACL 2003, p.176-179, May 31, 2003, Edmonton, Canada
	David Madigan , Martha Nason, Data reduction: sampling, Handbook of data mining and knowledge discovery, Oxford University Press, Inc., New York, NY, 2002
	Erwin Marsi , Martin Reynaert , Antal van den Bosch , Walter Daelemans , Véronique Hoste, Learning to predict pitch accents and prosodic boundaries in Dutch, Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, p.489-496, July 07-12, 2003, Sapporo, Japan
	Abraham Bernstein , Foster Provost , Shawndra Hill, Toward Intelligent Assistance for a Data Mining Process: An Ontology-Based Approach for Cost-Sensitive Classification, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.503-518, April 2005
	Piroska Lendvai, Learning to identify fragmented words in spoken discourse, Proceedings of the tenth conference on European chapter of the Association for Computational Linguistics, April 12-17, 2003, Budapest, Hungary
	Aloak Kapoor , Russell Greiner, Reinforcement learning for active model selection, Proceedings of the 1st international workshop on Utility-based data mining, p.17-23, August 21-21, 2005, Chicago, Illinois
	H. Wang , S. Parthasarathy , A. Ghoting , S. Tatikonda , G. Buehrer , T. Kurc , J. Saltz, Design of a next generation sampling service for large scale data analysis applications, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts
	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
	Rui Leite , Pavel Brazdil, Predicting relative performance of classifiers from samples, Proceedings of the 22nd international conference on Machine learning, p.497-503, August 07-11, 2005, Bonn, Germany
	Mehmet Koyuturk , Ananth Grama , Naren Ramakrishnan, Compression, Clustering, and Pattern Discovery in Very High-Dimensional Discrete-Attribute Data Sets, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.447-461, April 2005
	Nitesh V. Chawla , Lawrence O. Hall , Kevin W. Bowyer , W. Philip Kegelmeyer, Learning Ensembles from Bites: A Scalable and Accurate Approach, The Journal of Machine Learning Research, 5, p.421-451, 12/1/2004
	Jaekyung Yang , Sigurdur Olafsson, Optimization-based feature selection with adaptive instance sampling, Computers and Operations Research, v.33 n.11, p.3088-3106, November 2006
	Cai-Yan Jia , Xie-Ping Gao, Multi-scaling sampling: an adaptive sampling method for discovering approximate association rules, Journal of Computer Science and Technology, v.20 n.3, p.309-318, May 2005
	Dimuthu Makawita , Kian-Lee Tan and , Huan Liu, Sampling from databases using B$^+$-Trees, Intelligent Data Analysis, v.6 n.4, p.359-377, September 2002
	Tao Li , Mitsunori Ogihara , Shenghuo Zhu, Association-based similarity testing and its applications, Intelligent Data Analysis, v.7 n.3, p.209-232, August 2003
	Tapio Elomaa , Juho Rousu, On the Computational Complexity of Optimal Multisplitting, Fundamenta Informaticae, v.47 n.1-2, p.35-52, January 2001
	Ravi Aron , Arun Sundararajan , Siva Viswanathan, Intelligent agents in electronic markets for information goods: customization, preference revelation and pricing, Decision Support Systems, v.41 n.4, p.764-786, May 2006
	Jesús M. Pérez , Javier Muguerza , Olatz Arbelaitz , Ibai Gurrutxaga , José I. Martín, Combining multiple class distribution modified subsamples in a single tree, Pattern Recognition Letters, v.28 n.4, p.414-422, March, 2007
	Gary M. Weiss , Ye Tian, Maximizing classifier utility when training data is costly, ACM SIGKDD Explorations Newsletter, v.8 n.2, p.31-38, December 2006
	Xingquan Zhu , Xindong Wu , Qijun Chen, Bridging Local and Global Data Cleansing: Identifying Class Noise in Large, Distributed Data Datasets, Data Mining and Knowledge Discovery, v.12 n.2-3, p.275-308, May 2006
	Ben Kao , Minghua Zhang , Chi-Lap Yip , David W. Cheung , Usama Fayyad, Efficient Algorithms for Mining and Incremental Update of Maximal Frequent Sequences, Data Mining and Knowledge Discovery, v.10 n.2, p.87-116, March 2005
	Huan Liu , Hiroshi Motoda, On Issues of Instance Selection, Data Mining and Knowledge Discovery, v.6 n.2, p.115-130, April 2002
	Carlos Domingo , Ricard Gavaldà , Osamu Watanabe, Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms, Data Mining and Knowledge Discovery, v.6 n.2, p.131-152, April 2002
	Thomas Reinartz, A Unifying View on Instance Selection, Data Mining and Knowledge Discovery, v.6 n.2, p.191-210, April 2002
	Foster Provost , Venkateswarlu Kolluri, A Survey of Methods for Scaling Up Inductive Algorithms, Data Mining and Knowledge Discovery, v.3 n.2, p.131-169, June 1999
	Tapio Elomaa , Juho Rousu, Efficient Multisplitting Revisited: Optima-Preserving Elimination of Partition Candidates, Data Mining and Knowledge Discovery, v.8 n.2, p.97-126, March 2004
	Selwyn Piramuthu, Input data for decision trees, Expert Systems with Applications: An International Journal, v.34 n.2, p.1220-1226, February, 2008
	Christopher Jermaine, Online Random Shuffling of Large Database Tables, IEEE Transactions on Knowledge and Data Engineering, v.19 n.1, p.73-84, January 2007
	Kun-Ta Chuang , Jiun-Long Huang , Ming-Syan Chen, Power-law relationship and self-similarity in the itemset support distribution: analysis and applications, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.1121-1141, August 2008
	Boštjan Brumen , Matjaž B. Jurič , Tatjana Welzer , Ivan Rozman , Hannu Jaakkola , Apostolos Papadopoulos, Assessment of Classification Models with Small Amounts of Data, Informatica, v.18 n.3, p.343-362, August 2007
	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
	Ignacio Ponzoni , Francisco Azuaje , Juan Augusto , David Glass, Inferring Adaptive Regulation Thresholds and Association Rules from Gene Expression Data through Combinatorial Optimization Learning, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.4, p.624-634, October 2007
	Kun-Ta Chuang , Keng-Pei Lin , Ming-Syan Chen, Quality-Aware Sampling and Its Applications in Incremental Data Mining, IEEE Transactions on Knowledge and Data Engineering, v.19 n.4, p.468-484, April 2007
	Kun-Ta Chuang , Hung-Leng Chen , Ming-Syan Chen, Feature-preserved sampling over streaming data, ACM Transactions on Knowledge Discovery from Data (TKDD), v.2 n.4, p.1-45, January 2009
	Carina Lopes , Gerson Zaverucha, HTILDE: scaling up relational decision trees for very large databases, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
	Hyontai Sug, An effective sampling method for decision trees considering comprehensibility and accuracy, WSEAS Transactions on Computers, v.8 n.4, p.631-640, April 2009
	Gladys Castillo , João Gama, Adaptive Bayesian network classifiers, Intelligent Data Analysis, v.13 n.1, p.39-59, January 2009
	Hyontai Sug, An experimental decision of samples for RBF neural networks, Proceedings of the 9th WSEAS international conference on Multimedia systems & signal processing, p.249-252, May 20-22, 2009, Hangzhou, China
	Mark Last, Improving data mining utility with projective sampling, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France
	Gary M. Weiss , Foster Provost, Learning when training data are costly: the effect of class distribution on tree induction, Journal of Artificial Intelligence Research, v.19 n.1, p.315-354, July 2003
	Hyontai Sug, Performance comparison of RBF networks and MLPs for classification, Proceedings of the 9th WSEAS international conference on Applied informatics and communications, p.450-454, August 20-22, 2009, Moscow, Russia
	Hyontai Sug, A pilot sampling method for multi-layer perceptrons, Proceedings of the WSEAES 13th international conference on Computers, p.629-633, July 23-25, 2009, Rodos, Greece
	Hyontai Sug, The relationship of sample size and accuracy in radial basis function networks, WSEAS Transactions on Computers, v.8 n.7, p.1175-1184, July 2009