A Survey of Logic Based Classifiers
---
paper_title: Supervised Machine Learning: A Review of Classification Techniques

paper_content:

The goal of supervised learning is to build a concise model of the distribution of class labels in terms of predictor features. The resulting classifier is then used to assign class labels to the testing instances where the values of the predictor features are known, but the value of the class label is unknown. This paper describes various supervised machine learning classification techniques. Of course, a single chapter cannot be a complete review of all supervised machine learning classification algorithms (also known induction classification algorithms), yet we hope that the references cited will cover the major theoretical issues, guiding the researcher in interesting research directions and suggesting possible bias combinations that have yet to be explored.
---
paper_title: Induction of decision trees

paper_content:

The technology for building knowledge-based systems by inductive inference from examples has been demonstrated successfully in several practical applications. 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. Results from recent studies show ways in which the methodology can be modified to deal with information that is noisy and/or incomplete. A reported shortcoming of the basic algorithm is discussed and two means of overcoming it are compared. The paper concludes with illustrations of current research directions.
---
paper_title: SLIQ: A fast scalable classifier for data mining

paper_content:

Classification is an important problem in the emerging field of data mining. Although classification has been studied extensively in the past, most of the classification algorithms are designed only for memory-resident data, thus limiting their suitability for data mining large data sets. This paper discusses issues in building a scalable classifier and presents the design of SLIQ, a new classifier. SLIQ is a decision tree classifier that can handle both numeric and categorical attributes. It uses a novel pre-sorting technique in the tree-growth phase. This sorting procedure is integrated with a breadth-first tree growing strategy to enable classification of disk-resident datasets. SLIQ also uses a new tree-pruning algorithm that is inexpensive, and results in compact and accurate trees. The combination of these techniques enables SLIQ to scale for large data sets and classify data sets irrespective of the number of classes, attributes, and examples (records), thus making it an attractive tool for data mining.
---
paper_title: Elegant decision tree algorithm for classification in data mining

paper_content:

Decision trees have been found very effective for classification especially in Data Mining. This paper aims atimproving the performance of the SLIQ decision tree algorithm (Mehta et. al,1996) for classification in datamining The drawback of this algorithm is that large number of gini indices have to be computed at each node ofthe decision tree. In order to decide which attribute is to be split at each node, the gini indices have to becomputed for all the attributes and for each successive pair of values for all patterns which have not beenclassified. An improvement over the SLIQ algorithm has been proposed to reduce the computationalcomplexity. In this algorithm, the gini index is computed not for every successive pair of values of an attributebut over different ranges of attribute values. Classification accuracy of this technique was compared with theexisting SLIQ and the Neural Network technique on three real life datasets consisting of the effect of differentchemicals on water pollution, Wisconsin Breast Cancer Data and Image data It was observed that the decisiontree constructed using the proposed decision tree algorithm gave far better classification accuracy than theclassification accuracy obtained using the SLIQ algorithm irrespective of the dataset under consideration. Theclassification accuracy of this algorithm was even better compared to the neural network classificationtechnique. Overall, it was observed that this decision tree algorithm not only reduces the number ofcomputations of gini indices but also leads to better classification accuracy.
---
paper_title: RainForest—A Framework for Fast Decision Tree Construction of Large Datasets

paper_content:

Classification of large datasets is an important data mining problem. Many classification algorithms have been proposed in the literature, but studies have shown that so far no algorithm uniformly outperforms all other algorithms in terms of quality. In this paper, we present 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. The generic algorithm is easy to instantiate with specific split selection methods from the literature (including C4.5, CART, CHAID, FACT, ID3 and extensions, SLIQ, SPRINT and QUEST). ::: ::: In addition to its generality, in that it yields scalable versions of a wide range of classification algorithms, our approach also offers performance improvements of over a factor of three over the SPRINT algorithm, the fastest scalable classification algorithm proposed previously. In contrast to SPRINT, however, our generic algorithm requires a certain minimum amount of main memory, proportional to the set of distinct values in a column of the input relation. Given current main memory costs, this requirement is readily met in most if not all workloads.
---
paper_title: SLIQ: A fast scalable classifier for data mining

paper_content:

Classification is an important problem in the emerging field of data mining. Although classification has been studied extensively in the past, most of the classification algorithms are designed only for memory-resident data, thus limiting their suitability for data mining large data sets. This paper discusses issues in building a scalable classifier and presents the design of SLIQ, a new classifier. SLIQ is a decision tree classifier that can handle both numeric and categorical attributes. It uses a novel pre-sorting technique in the tree-growth phase. This sorting procedure is integrated with a breadth-first tree growing strategy to enable classification of disk-resident datasets. SLIQ also uses a new tree-pruning algorithm that is inexpensive, and results in compact and accurate trees. The combination of these techniques enables SLIQ to scale for large data sets and classify data sets irrespective of the number of classes, attributes, and examples (records), thus making it an attractive tool for data mining.
---
paper_title: PUBLIC: A Decision Tree Classifier that Integrates Building and Pruning

paper_content:

Classification is an important problem in data mining. Given a database of records, each with a class label, a classifier generates a concise and meaningful description for each class that can be used to classify subsequent records. A number of popular classifiers construct decision trees to generate class models. These classifiers first build a decision tree and then prune subtrees from the decision tree in a subsequent pruning phase to improve accuracy and prevent “overfitting”.Generating the decision tree in two distinct phases could result in a substantial amount of wasted effort since an entire subtree constructed in the first phase may later be pruned in the next phase. In this paper, we propose PUBLIC, an improved decision tree classifier that integrates the second “pruning” phase with the initial “building” phase. In PUBLIC, a node is not expanded during the building phase, if it is determined that it will be pruned during the subsequent pruning phase. In order to make this determination for a node, before it is expanded, PUBLIC computes a lower bound on the minimum cost subtree rooted at the node. This estimate is then used by PUBLIC to identify the nodes that are certain to be pruned, and for such nodes, not expend effort on splitting them. Experimental results with real-life as well as synthetic data sets demonstrate the effectiveness of PUBLIC's integrated approach which has the ability to deliver substantial performance improvements.
---
paper_title: CLOUDS: A Decision Tree Classifier for Large Datasets

paper_content:

Classification for very large datasets has many practical applications in data mining. Techniques such as discretization and dataset sampling can be used to scale up decision tree classifiers to large datasets. Unfortunately, both of these techniques can cause a significant loss in accuracy. We present a novel decision tree classifier called CLOUDS, which samples the splitting points for numeric attributes followed by an estimation step to narrow the search space of the best split. CLOUDS reduces computation and I/O complexity substantially compared to state of the art classifiers, while maintaining the quality of the generated trees in terms of accuracy and tree size. We provide experimental results with a number of real and synthetic datasets.
---
paper_title: RainForest—A Framework for Fast Decision Tree Construction of Large Datasets

paper_content:

Classification of large datasets is an important data mining problem. Many classification algorithms have been proposed in the literature, but studies have shown that so far no algorithm uniformly outperforms all other algorithms in terms of quality. In this paper, we present 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. The generic algorithm is easy to instantiate with specific split selection methods from the literature (including C4.5, CART, CHAID, FACT, ID3 and extensions, SLIQ, SPRINT and QUEST). ::: ::: In addition to its generality, in that it yields scalable versions of a wide range of classification algorithms, our approach also offers performance improvements of over a factor of three over the SPRINT algorithm, the fastest scalable classification algorithm proposed previously. In contrast to SPRINT, however, our generic algorithm requires a certain minimum amount of main memory, proportional to the set of distinct values in a column of the input relation. Given current main memory costs, this requirement is readily met in most if not all workloads.
---
paper_title: RainForest—A Framework for Fast Decision Tree Construction of Large Datasets

paper_content:

Classification of large datasets is an important data mining problem. Many classification algorithms have been proposed in the literature, but studies have shown that so far no algorithm uniformly outperforms all other algorithms in terms of quality. In this paper, we present 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. The generic algorithm is easy to instantiate with specific split selection methods from the literature (including C4.5, CART, CHAID, FACT, ID3 and extensions, SLIQ, SPRINT and QUEST). ::: ::: In addition to its generality, in that it yields scalable versions of a wide range of classification algorithms, our approach also offers performance improvements of over a factor of three over the SPRINT algorithm, the fastest scalable classification algorithm proposed previously. In contrast to SPRINT, however, our generic algorithm requires a certain minimum amount of main memory, proportional to the set of distinct values in a column of the input relation. Given current main memory costs, this requirement is readily met in most if not all workloads.
---

Title: A Survey of Logic Based Classifiers

Section 1: INTRODUCTION
Description 1: Introduce the need for automated data mining techniques due to data growth and discuss various logic-based algorithms for classification.

Section 2: DECISION TREE ALGORITHMS
Description 2: Describe historical decision tree algorithms such as CLS, IDE 3.0, C 4.5, and C 5.0, and discuss their development, features, and limitations.

Section 3: EVALUATION AND ANALYSIS OF CLASSIFIERS
Description 3: Evaluate major logic-based classifiers, discussing their strengths and weaknesses compared to each other.

Section 4: IDE 3.0
Description 4: Examine the initial work on IDE 3.0 by Quinlan, highlighting its shortcomings.

Section 5: C 4.5 and C 5.0
Description 5: Discuss improvements of C 4.5 over IDE 3.0 and the advancements made in C 5.0, including accuracy issues and handling of numeric data.

Section 6: CART
Description 6: Detail how CART differs from and addresses some limitations of C 4.5, while highlighting its unique features and drawbacks.

Section 7: SLIQ
Description 7: Explain how the SLIQ algorithm operates, its speed and efficiency, and memory constraints.

Section 8: SPRINT
Description 8: Describe SPRINT as an extension of SLIQ, focusing on its scalability, disk residence of attribute lists, and time complexity.

Section 9: PUBLIC
Description 9: Outline the PUBLIC classifier, emphasizing its integrated pruning and building phases for improved performance.

Section 10: CLOUDS
Description 10: Introduce the CLOUDS algorithm, noting its enhancements over SPRINT and its computational efficiencies.

Section 11: RainForest
Description 11: Explain the RainForest framework that separates quality and scalability concerns for decision tree algorithms, and its performance superiority over SPRINT.

Section 12: BOAT
Description 12: Discuss the BOAT algorithm's dynamic updates, speed advantages, and dependency on small training subsets.

Section 13: CONCLUSION
Description 13: Summarize the importance of understanding classifier features for selecting the most relevant one depending on the dataset size and complexity, with recommendations for different scenarios.