A Survey of Methods for Scaling Up Inductive Algorithms
Data Mining and Knowledge DiscoveryPublished 1 June 1999
Foster Provost, Venkateswarlu Kolluri
Citations278
SJR quartileQ1
SJR score1.02
SNIP1.88
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper summarizes, categorizes, and compares existing work on scaling up inductive algorithms, focusing on algorithms that build decision trees and rule sets, in order to provide focus and specific details.
Abstract
One of the defining challenges for the KDD research community is to enable inductive learning algorithms to mine very large databases. This paper summarizes, categorizes, and compares existing work on scaling up inductive algorithms. We concentrate on algorithms that build decision trees and rule sets, in order to provide focus and specific details; the issues and techniques generalize to other types of data mining. We begin with a discussion of important issues related to scaling up. We highlight similarities among scaling techniques by categorizing them into three main approaches. For each approach, we then describe, compare, and contrast the different constituent techniques, drawing on specific examples from published papers. Finally, we use the preceding analysis to suggest how to proceed when dealing with a large problem, and where to focus future research.
Keywords
Computer Science
BiometricsClassification and Regression Trees.
23,841 Citations1984Alexander Gordon, Leo Breiman +3 more
C4.5: Programs for Machine Learning
23,665 Citations1992J. R. Quinlan
A complete guide to the C4.5 system as implemented in C for the UNIX environment, which starts from simple core learning methods and shows how they can be elaborated and extended to deal with typical problems such as missing data and over hitting.
Machine LearningInduction of Decision Trees
14,815 Citations1986J. R. Quinlan
This paper summarizes an approach to synthesizing decision trees that has been used in a variety of systems, and it describes one such system, ID3, in detail, which is described in detail.
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
Fast algorithms for mining association rules
10,739 Citations1998Rakesh Agrawal, Ramakrishnan Srikant
Artificial IntelligenceWrappers for feature subset selection
8,925 Citations1997Ron Kohavi, George H. John
The wrapper method searches for an optimal feature subset tailored to a particular algorithm and a domain and compares the wrapper approach to induction without feature subset selection and to Relief, a filter approach tofeature subset selection.
IEEE ExpertData mining and knowledge discovery: making sense out of data
4,643 Citations1996U.M. Feyyad
Find loads of the data mining and knowledge discovery making sense out of data book catalogues in this site as the choice of you visiting this page.
A theory of the learnable
4,242 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
Elsevier eBooksFast Effective Rule Induction
3,767 Citations1995William W. Cohen
This paper evaluates the recently-proposed rule learning algorithm IREP on a large and diverse collection of benchmark problems, and proposes a number of modifications resulting in an algorithm RIPPERk that is very competitive with C4.5 and C 4.5rules with respect to error rates, but much more efficient on large samples.
Communications of the ACMA theory of the learnable
3,268 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
Lecture notes in computer scienceEstimating attributes: Analysis and extensions of RELIEF
2,950 Citations1994Igor Kononenko
In the context of machine learning from examples this paper deals with the problem of estimating the quality of attributes with and without dependencies among them and is analysed and extended to deal with noisy, incomplete, and multi-class data sets.
International Journal of Man-Machine StudiesSimplifying decision trees
2,502 Citations1987J. R. Quinlan
Techniques for simplifying decision trees while retaining their accuracy are discussed, described, illustrated, and compared on a test-bed of decision trees from a variety of domains.
IEEE Transactions on Knowledge and Data EngineeringData mining: an overview from a database perspective
2,221 Citations1996Ming-Syan Chen⋆, Jiawei Han +1 more
This article provides a survey, from a database researcher's point of view, on the data mining techniques developed recently, a classification of the available data mining Techniques, and a comparative study of such techniques is presented.
Machine LearningVery Simple Classification Rules Perform Well on Most Commonly Used Datasets
1,798 Citations1993Robert C. Holte
On most datasets studied, the best of very simple rules that classify examples on the basis of a single attribute is as accurate as the rules induced by the majority of machine learning systems.
An Efficient Algorithm for Mining Association Rules in Large Databases
1,598 Citations1995Ashoka Savasere, Edward Omiecinski +1 more
This paper presents an efficient algorithm for mining association rules that is fundamentally different from known algorithms and not only reduces the I/O overhead significantly but also has lower CPU overhead for most cases.
Mining quantitative association rules in large relational tables
1,484 Citations1996Ramakrishnan Srikant, Rakesh Agrawal
This work deals with quantitative attributes by fine-partitioning the values of the attribute and then combining adjacent partitions as necessary and introduces measures of partial completeness which quantify the information lost due to partitioning.
TechnometricsSubset Selection in Regression
1,482 Citations2003
Subset Selection in Regression: A Review of the Foundations of Regression, edited by A. J. Miller.
Machine LearningLearning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
1,376 Citations1988Nick Littlestone
This work presents one such algorithm that learns disjunctive Boolean functions, along with variants for learning other classes of Boolean functions.
Machine LearningA Comparison of Prediction Accuracy, Complexity, and Training Time of Thirty-Three Old and New Classification Algorithms
1,132 Citations2000Tjen-Sien Lim, Wei‐Yin Loh +1 more
Among decision tree algorithms with univariate splits, C4.5, IND-CART, and QUEST have the best combinations of error rate and speed, but C 4.5 tends to produce trees with twice as many leaves as those fromIND-Cart and QUEST.
Machine LearningLearning Efficient Classification Procedures and Their Application to Chess End Games
1,106 Citations1983J. R. Quinlan
A series of experiments dealing with the discovery of efficient classification procedures from large numbers of examples is described, with a case study from the chess end game king-rook versus king-knight.
Sampling Large Databases for Association Rules
1,079 Citations1996Hannu Toivonen
New algorithms that reduce the database activity considerably by picking a Random sample, to find using this sample all association rules that probably hold in the whole database, and then to verify the results with the rest of the database.
Data Mining and Knowledge DiscoveryAdaptive Fraud Detection
873 Citations1997Tom Fawcett, Foster Provost
This paper uses a rule-learning program to uncover indicators of fraudulent behavior from a large database of customer transactions, which are used to create a set of monitors, which profile legitimate customer behavior and indicate anomalies.
Knowledge discovery and data mining: towards a unifying framework
847 Citations1996Usama M. Fayyad, Gregory Piatetsky-Shapiro +1 more
The KDD process and basic data mining algorithms are defined, links between data mining, knowledge discovery, and other related fields are described, and an analysis of challenges facing practitioners in the field is analyzed.
Applied IntelligenceOvercoming the Myopia of Inductive Learning Algorithms with RELIEFF
798 Citations1997Igor Kononenko, Edvard Šimec +1 more
This work reimplemented Assistant, a system for top down induction of decision trees, using RELIEFF, an extension of RELIEF, as an estimator of attributes at each selection step for heuristic guidance of inductive learning algorithms.
Machine LearningIncremental Induction of Decision Trees
790 Citations1989Paul E. Utgoff
An incremental algorithm for inducing decision trees equivalent to those formed by Quinlan's nonincremental ID3 algorithm, given the same training instances is presented, named ID5R.
SPRINT: A Scalable Parallel Classifier for Data Mining
781 Citations1996John Shafer, Rakesh Agrawal +1 more
A new decision-tree-based classification algorithm, called SPRINT, is presented that removes all of the memory restrictions, and is fast and scalable, and designed to be easily parallelized, allowing many processors to work together to build a single consistent model.
Lecture notes in computer scienceSLIQ: A fast scalable classifier for data mining
753 Citations1996Manish Mehta, Rakesh Agrawal +1 more
Issues in building a scalable classifier are discussed and the design of SLIQ, a new classifier that uses a novel pre-sorting technique in the tree-growth phase to enable classification of disk-resident datasets is presented.
Journal of the ACMEfficient noise-tolerant learning from statistical queries
712 Citations1998Michael Kearns
This paper formalizes a new but related model of learning from statistical queries, and demonstrates the generality of the statistical query model, showing that practically every class learnable in Valiant's model and its variants can also be learned in the new model (and thus can be learning in the presence of noise).
Artificial IntelligenceQuantifying inductive bias: AI learning algorithms and Valiant's learning framework
499 Citations1988David Haussler
It is shown that the notion of inductive bias in concept learning can be quantified in a way that directly relates to learning performance in the framework recently introduced by Valiant.
Artificial IntelligenceDendral and meta-dendral: Their applications dimension
465 Citations1978Bruce G. Buchanan, Edward A. Feigenbaum
The DENDRAL and Meta-DENDRAL programs assist chemists with data interpretation problems and some chemical results produced by the programs are mentioned.
Toward scalable learning with non-uniform class and cost distributions: a case study in credit card fraud detection
448 Citations1998Philip K. Chan, Salvatore J. Stolfo
A multi-classifier meta-learning approach to address very large databases with skewed class distributions and non-uniform cost per error and empirical results indicate that the approach can significantly reduce loss due to illegitimate transactions.
Machine LearningBoolean Feature Discovery in Empirical Learning
398 Citations1990Giulia Pagallo, David Haussler
Two new methods that adaptively introduce relevant features while learning a decision tree from examples are presented, showing empirically that these methods outperform a standard decision tree algorithm for learning small random DNF functions when the examples are drawn at random from the uniform distribution.
Elsevier eBooksIncremental Reduced Error Pruning
363 Citations1994Johannes Fürnkranz, Gerhard Widmer
Experiments show that in many noisy domains this method is much more efficient than alternative algorithms, along with a slight gain in accuracy, however, the experiments show that the use of the algorithm cannot be recommended for domains which require a very specific concept description.
Elsevier eBooksInduction of One-Level Decision Trees
359 Citations1992Wayne Iba, Pat Langley
This paper presents an average-case analysis of a simple algorithm that induces one-level decision trees for concepts defined by a single relevant attribute, and derives the expected classification accuracy over the entire instance space.
IEEE Transactions on Knowledge and Data EngineeringAn information theoretic approach to rule induction from databases
357 Citations1992Padhraic Smyth, R.M. Goodman
An algorithm for the induction of rules from examples is introduced, which is novel in the sense that it not only learns rules for a given concept, but it simultaneously learns rules relating multiple concepts.
Efficient progressive sampling
353 Citations1999Foster Provost, David Jensen +1 more
This work analyzes methods for progressive sampling using progressively larger samples as long as model accuracy improves, and concludes that progressive sampling can be remarkably efficient.
Data Mining and Knowledge DiscoveryRainForest—A Framework for Fast Decision Tree Construction of Large Datasets
349 Citations2000Johannes Gehrke, Raghu Ramakrishnan +1 more
This paper presents a unifying framework called Rain Forest for classification tree construction that separates the scalability aspects of algorithms for constructing a tree from the central features that determine the quality of the tree.
Concept learning and the problem of small disjuncts
342 Citations1989Robert C. Holte, Liane Acker +1 more
Various approaches to this problem are evaluated, including the novel approach of using a bias different than the "maximum generality" bias, which prove partly successful, but the problem of small disjuncts remains open.
Integrating association rule mining with relational database systems
304 Citations1998Sunita Sarawagi, Shiby Thomas +1 more
JAM: java agents for meta-learning over distributed databases
287 Citations1997Salvatore J. Stolfo, Andreas L. Prodromidis +4 more
The overall architecture of the JAM system is described and the specific implementation currently under development at Columbia University is described, one of JAM's target applications is fraud and intrusion detection in financial information systems.
Machine LearningSymbolic and Neural Learning Algorithms: An Experimental Comparison
285 Citations1991Jude Shavlik, Raymond J. Mooney +1 more
Experimental results suggest that backpropagation can work significantly better on data sets containing numerical data, and occasionally outperforms the other two systems when given relatively small amounts of training data.
Wrappers for Performance Enhancements and Oblivious Decision Graphs.
254 Citations1995Ron Kohavi
This doctoral dissertation concludes that repeated runs of five-fold cross-validation give a good tradeoff between bias and variance for the problem of model selection used in later chapters.
Machine LearningError Reduction through Learning Multiple Descriptions
249 Citations1994Kamal Ali, Michael J. Pazzani
It is empirically shown that it is possible to learn descriptions that make less correlated errors in domains in which many ties in the search evaluation measure (e.g. information gain) are experienced during learning.
Machine LearningMultiple Comparisons in Induction Algorithms
243 Citations2000David Jensen, Paul R. Cohen
This work analyzes the statistical properties of MCPs and shows how failure to adjust for these properties leads to the pathologies of induction algorithms, including attribute selection errors, overfitting, and oversearching.
Minds at UW (University of Wisconsin)Extracting comprehensible models from trained neural networks
234 Citations1996Mark Craven, Jude Shavlik
An algorithm, called Trepan, is an algorithm that overcomes the significant limitations of previous methods by taking a novel approach to the task of extracting comprehensible models from trained neural networks, and provides an appealing combination of strengths.
Elsevier eBooksEfficient Algorithms for Minimizing Cross Validation Error
227 Citations1994Andrew Moore, Mary S. Lee
It is shown how experimental design methods can achieve this, using a technique similar to a Bayesian version of Kaelbling's Interval Estimation, to reduce the computational burden of large scale cross validation searches.
Journal of Artificial Intelligence ResearchOPUS: An Efficient Admissible Algorithm for Unordered Search
209 Citations1995Geoffrey I. Webb
The use of admissible search is of potential value to the machine learning community as it means that the exact learning biases to be employed for complex learning tasks can be precisely specified and manipulated.
Journal of Artificial Intelligence ResearchCached Sufficient Statistics for Efficient Machine Learning with Large Datasets
206 Citations1998Andrew W. Moore, M. S. Lee
A very sparse data structure, the ADtree, is provided to minimize memory use and it is empirically demonstrated that tractably-sized data structures can be produced for large real-world datasets by using a sparse tree structure that never allocates memory for counts of zero.
Mining Very Large Databases with Parallel Processing
205 Citations2000Alex A. Freitas, Simon Lavington
Mining Very Large Databases with Parallel Processing addresses the problem of large-scale data mining, describing advances in the integration of three computer science areas, namely: "intelligent" (machine learning-based) data mining techniques; relational databases and parallel processing.
Communications of the ACMDigital libraries
204 Citations1995Edward A. Fox, Robert M. Akscyn +2 more
This report outlines IBM’s perspective on key supporting technologies and on the unique challenges highlighted by the emergence of digital libraries.
Machine LearningAn Experimental Comparison of the Nearest-Neighbor and Nearest-Hyperrectangle Algorithms
203 Citations1995Dietrich Wettschereck, Thomas G. Dietterich
In domains where the decision boundaries are axis-parallel, the NGE approach can produce excellent generalization with interpretable hypotheses, and in all domains tested, NGE algorithms require much less memory to store generalized exemplars than is required by NN algorithms.
Credit Card Fraud Detection Using Meta-Learning: Issues and Initial Results 1
191 Citations1997Salvatore J. Stolfo, David W. Fan +3 more
It is argued that, for the fraud detection domain, fraud catching rate and false alarm rate are better metrics than the overall accuracy when evaluating the learned fraud classifiers, and that given a skewed distribution in the original data, artificially more balanced training data leads to better classifiers.
International Journal of Parallel ProgrammingParallel depth first search. Part II. Analysis
172 Citations1987Vipin Kumar, V. Nageshwara Rao
A work-distribution algorithm is presented that guarantees close to optimal performance on a shared-memory/ω-network-with-message-combining architecture (e.g. RP3) and is applicable to other parallel algorithms in which work is dynamically shared between different processors.
Static versus dynamic sampling for data mining
171 Citations1996George H. John, Pat Langley
The "Probably Close Enough" criterion is introduced to describe the desired properties of a sample and dynamic sampling methods, which take into account the mining tool being used and can thus give better samples are discussed.
International Journal of Parallel ProgrammingParallel depth first search. Part I. Implementation
168 Citations1987V. Nageshwara Rao, Vipin Kumar
A parallel formulation of depth-first search which retains the storage efficiency of sequential depth- first search and can be mapped on to anyMIMD architecture is presented and results show that hypercube and sharedmemory architectures are significantly better.
Machine LearningError reduction through learning multiple descriptions
162 Citations1996Kamal Ali, Michael J. Pazzani
It is empirically shown that it is possible to learn descriptions that make less correlated errors in domains in which many ties in the search evaluation measure (e.g. information gain) are experienced during learning.
Journal of Intelligent Information SystemsOn the Accuracy of Meta-learning for Scalable Data Mining
160 Citations1997Philip K. Chan, Salvatore J. Stolfo
This paper focussed primarily on issues related to the accuracy and efficacy of meta-learning as ageneral strategy, demonstrating that meta- learning is technically feasible in wide-area, network computing environments.
DBMiner: a system for mining knowledge in large relational databases
157 Citations1996Jiawei Han, Yongjian Fu +10 more
A data mining system, DBMiner, has been developed for interactive mining of multiple-level knowledge in large relational databases that provides a user-friendly, interactive data mining environment with good performance.
Toward parallel and distributed learning by meta-learning
151 Citations1993Philip K. Chan, Salvatore J. Stolfo
Several meta-learning strategies for integrating independently learned classifiers by the same learner in a parallel and distributed computing environment are outlined, particularly suited for massive amounts of data that main-memory-based learning algorithms cannot efficiently handle.
Machine LearningEvaluation and selection of biases in machine learning
135 Citations1995Diana F. Gordon, Marie desJardins
This introduction motivates the importance of automated methods for evaluating and selecting biases using a framework of bias selection as search in bias and meta-bias spaces.
Applied Artificial IntelligenceREPRESENTATION DESIGN AND BRUTE-FORCE INDUCTION IN A BOEING MANUFACTURING DOMAIN
126 Citations1994Patricia Riddle, Richard Segal +1 more
This work applied inductive classification techniques to data collected in a Boeing plant with the goal of uncovering possible flaws in the manufacturing process, and formulated an algorithm that conducts an exhaustive, depth-bounded search for accurate predictive rules.
Elsevier eBooksEfficiently Inducing Determinations: A Complete and Systematic Search Algorithm that Uses Optimal Pruning
121 Citations1993Jeffrey C. Schlimmer
This paper presents an efficient, batch algorithm for inducing all minimal determinations from observed data based on breadth-first search and runs in polynomial time and space given a user-supplied parameter limiting the maximum size of a determination.
The Effects of Training Set Size on Decision Tree Complexity
120 Citations1997Tim Oates, David Jensen
This paper presents experiments with 19 datasets and 5 decision tree pruning algorithms that show that increasing training set size often results in a linear increase in tree size, even when that additional complexity results in no significant increase in classification accuracy.
An experimental comparison of symbolic and connectionist learning algorithms
116 Citations1989Raymond J. Mooney, Jude Shavlik +2 more
The results show that ID3 and perceptron run significantly faster than does backpropagation, both during learning and during classification of novel examples, however, the probability of correctly classifying new examples is about the same for the three systems.
Scaling up: distributed machine learning with cooperation
110 Citations1996Foster Provost, Daniel N. Hennessy
This paper investigates the use of distributed processing to take advantage of the often dormant PCs and workstations available on local networks and demonstrates the power of the method by learning from a massive data set taken from the domain of cellular fraud detection.
Developing tightly-coupled data mining applications on a relational database system
107 Citations1996Rakesh Agrawal, Kyuseok Shim
This work presents a methodology for tightly coupling data mining applications to database systems to build high-performance applications, without requiring any change to the database software.
Elsevier eBooksTheory and Applications of Agnostic PAC-Learning with Small Decision Trees
102 Citations1995Peter Auer, Robert C. Holte +1 more
The performance of this theoretically founded algorithm T2, an agnostic PAC-learning of decision trees of at most 2 levels, is evaluated on 15 common “real-world” datasets, and it is shown that for most of these datasets T2 provides simple decision trees with little or no loss in predictive power.
Data Mining and Knowledge DiscoveryScaling Up Inductive Logic Programming by Learning from Interpretations
102 Citations1999Hendrik Blockeel, Luc De Raedt +2 more
This paper relates the setting to propositional data mining and to the classical ILP setting, and shows that learning from interpretations corresponds to learning from multiple relations and thus extends the expressiveness of propositional learning, while maintaining its efficiency to a large extent.
Journal of the American Chemical SocietyApplications of artificial intelligence for chemical inference. 22. Automatic rule formation in mass spectrometry by means of the meta-DENDRAL program
101 Citations1976B. G. Buchanan, Dennis H. Smith +5 more
Parallel classification for data mining on shared-memory multiprocessors
100 Citations1999Mohammed J. Zaki, Ching‐Tien Ho +1 more
Presents parallel algorithms for building decision-tree classifiers on shared-memory multiprocessor (SMP) systems and shows that the construction of a decision-Tree classifier can be effectively parallelized on an SMP machine with good speedup.
[1990] Proceedings of the 2nd International IEEE Conference on Tools for Artificial IntelligenceRL4: a tool for knowledge-based induction
99 Citations2002Scott H. Clearwater, Foster Provost
The induction program RL4 is used as an induction tool, and several examples of its past and present uses are presented, and the directions in which RL4 can go in the future are considered.
KDD for science data analysis: issues and examples
94 Citations1996Usama M. Fayyad, David Haussler +1 more
An overview of the main issues in the exploitation of scientific datasets is given, five case studies where KDD tools play important and enabling roles are presented, and future challenges for data mining and KDD techniques in science data analysis are concluded.
Elsevier eBooksMega induction: a Test Flight
88 Citations1991Jason Catlett
This case study examines the application of Quinlan's C4.5 to the task of diagnosing a subsystem of NASA's Space Shuttle, finding the trees produced to be highly accurate, moderately small, and to contain new knowledge that might otherwise have remained undiscovered.
Machine LearningInductive policy: The pragmatics of bias selection
88 Citations1995Foster Provost, Bruce G. Buchanan
A framework for representing and automatically selecting a wide variety of biases is presented and experiments with an instantiation of the framework addressing various pragmatic tradeoffs of time, space, accuracy, and the cost of errors are described.
On the efficient gathering of sufficient statistics for classification from large SQL databases
83 Citations1998Goetz Graefe, Usama M. Fayyad +1 more
This work presents a new SQL operator (Unpivot) that enables efficient gathering of statistics with minimal changes to the SQL backend and shows analytically how this approach outperforms an alternative that requires changing in the data layout.
Efficient Pruning Methods for Separate-and-Conquer Rule Learning Systems.
82 Citations1993William W. Cohen
This paper presents a solution in the form of new pruning techniques that dramatically improve the runtime of rule induction methods with no loss in accuracy: formal analysis shows an improvement in asymp-totic time complexity, and experiments show an order-of-magnitude speedup.
Elsevier eBooksAN OUNCE OF KNOWLEDGE IS WORTH A TON OF DATA: Quantitative Studies of the Trade-Off between Expertise and Data based on Statistically Well-Founded Empirical Induction
79 Citations1989Brian R. Gaines
Measureting the amount of data required to attain knowledge through empirical induction given different forms and levels of expertise gives a principled economic evaluation of knowledge which can be used to guide knowledge acquisition theory and practice.
An overview of issues in developing industrial data mining and knowledge discovery applications
72 Citations1996Gregory Piatetsky-Shapiro, Ron Brachman +3 more
This paper surveys the growing number of industrial applications of data mining and knowledge discovery, and describes some representative applications, and examines how to assess the potential of a knowledge discovery application.
Artificial IntelligenceMaximizing the predictive value of production rules
71 Citations1990Sholom M. Weiss, Robert S. Galen +1 more
P predictive value maximization (PVM), a heuristic search procedure through the hypothesis space of conjunctions and disjunctions of variables and their cutoff values, is outlined, where the goal is to find the best combination of tests for making a diagnosis.
Elsevier eBooksSmall Disjuncts in Action: Learning to Diagnose Errors in the Local Loop of the Telephone Network
71 Citations1993Andrea Danyluk, Foster Provost
The need for smaller disjuncts is a major reason that it is difficult to learn from errorful data in this domain of NYNEX MAX, an expert system that diagnoses the local loop in a telephone network.
Large datasets lead to overly complex models: an explanation and a solution
68 Citations1998Tim Oates, David Jensen
This paper proposes a general solution to the problem of large datasets and compact models based on a statistical technique known as randomization testing, and empirically evaluates its utility.
Elsevier eBooksAn SE-tree based Characterization of the Induction Problem
63 Citations1993Ron Rymon
This paper proposes a new structure, called SE-tree, as a more general alternative to decision trees, used in induction programs both as the basis for their search, and as a representation of their classifier solution.
Machine LearningScaling Up Inductive Learning with Massive Parallelism
54 Citations1996Foster Provost, John M. Aronis
A parallel implementation of one inductive learning program on the CM-2 Connection Machine is described, it is shown that it scales up to millions of examples, and it uncovers special-case rules that sequential learning programs, running on smaller datasets, would miss.
Elsevier eBooksSKICAT: A Machine Learning System for Automated Cataloging of Large Scale Sky Surveys
53 Citations1993Usama M. Fayyad, N. Weir +1 more
The application of decision tree based classification techniques to the development of an automated tool for the reduction of a large scientific data set is described and SKICAT represents a system in which machine learning played a powerful and enabling role, and solved a difficult, scientifically significant problem.
Elsevier eBooksDecision Theoretic Subsampling for Induction on Large Databases
52 Citations1993Ron Musick, Jason Catlett +1 more
This paper addresses the questions of assessing when the choice may be made with a given expected error, and determining a sampling strategy that minimizes the computation cost of making it, by using a subsample for this calculation.
Knowledge discovery from multiple databases
49 Citations1995James S. Ribeiro, Kenneth A. Kaufman +1 more
The methodology and system for performing knowledge discovery across multiple databases are described and the incorporation of primary and foreign keys as well as the development and processing of knowledge segments are integrated.
Learning decision lists using homogeneous rules
48 Citations1994Richard Segal, Oren Etzioni
It is proved that the problem of finding a maximally accurate decision list can be reduced to the problemOf finding maximally inaccurate homogeneous rules, rules whose classification accuracy does not change with their position in the decision list.
PubMedDistributed machine learning: scaling up with coarse-grained parallelism.
31 Citations1994Foster Provost, Daniel N. Hennessy
A distributed learning system that takes advantage of the invariant-partitioning property to learn from very large data sets is described, and results demonstrating CorPRL's effectiveness in analyzing data from two databases are presented.
Kluwer international series in engineering and computer scienceIncremental Batch Learning
30 Citations1990Scott H. Clearwater
The information processed by incremental version-space merging need not correspond directly training data; as long as a piece of information can be converted into a version space of viable concept definitions it can be used by incrementally merging.
Evaluation of sampling for data mining of association rules
29 Citations2002Mohammed J. Zaki, S Parthasarathy +2 more
Sampling can speed up the mining process by more than an order of magnitude by reducing I/O costs and drastically shrinking the number of transactions to be considered and accurately represent the data patterns in the database with high confidence.
Elsevier eBooksOn Handling Tree-Structured Attributes in Decision Tree Learning
28 Citations1995Hussein Almuallim, Yasuhiro Akiba +1 more
This paper describes two pre-processing approaches, the Quinlan- encoding and the bit-per- category methods, that re-encode the training examples in terms of new nominal attributes and introduces an approach which handles tree- structured attributes directly without the need for pre- processing.
Journal of Artificial Intelligence ResearchIntegrative Windowing
28 Citations1998J. Fuernkranz
Integrative windowing is a new type of algorithm that further exploits this property of windowing by integrating good rules into the final theory right after they have been discovered, thus it avoids re-learning these rules in subsequent iterations of the windowing process.
Increasing the efficiency of data mining algorithms with Breadth-first marker propagation
26 Citations1997John M. Aronis, Poster J. Provost
This paper describes how to increase the efficiency of inductive data mining algorithms by replacing the central matching operation with a marker propagation technique, which is most beneficial when the data are linked to hierarchical background knowledge or when the attributes describing the data have many values.
Scalable data mining for rules
25 Citations1998Mohammed J. Zaki, Wei Li
In classification rule mining, this thesis presents disk-based parallel algorithms on shared-memory multiprocessors, the first such study.
Linear-time rule induction
24 Citations1996Pedro Domingos
CWS is a new algorithm with guaranteed O(e) complexity, and it is verified that it outperforms C4.5RULES and CN2 in time, accuracy and output size on two large datasets.
Exploiting background knowledge in automated discovery
24 Citations1996John M. Aronis, Foster Provost +1 more
The work described in this paper places data in the context of large bodies of background knowledge represented as inheritance networks, which has made a practical impact on botanical toxicology research, which required linking examples of cases of plant exposures to databases of botanical, geographical, and climate background knowledge.
…