Classification and Prediction

• The lecture is about classification and decision trees.

Classification

• It predicts categorical class labels.
• It classifies data by constructing a model based on a training set and class labels in a classifying attribute.
• Applications include categorizing bank loan applications as safe or risky.
• Numeric prediction models continuous-valued functions, predicting unknown or missing values.
• Applications include predicting expenditures of potential customers on computer equipment.
• Typical applications of classification include credit approval, target marketing, medical diagnosis, and treatment effectiveness analysis.

Classification and Prediction

• Step 1, model construction: Describes a predetermined set of data classes.
• Each tuple or sample is assumed to belong to a predefined class that is determined by the class label attribute.
• The training set describes the set of tuples used for model construction.
• The training samples are individual tuples making up the training set.
• Supervised learning is the learning of the model given a training set.
• A learned model is represented as classification rules, decision trees, or mathematical formulae.
• Step 2, model usage: The model classifies future or unseen objects.
• The accuracy of the model is estimated.
• The known label of a test sample is compared with the classified result from the model.
• The accuracy rate shows the percentage of test set samples correctly classified by the model.
• The test set is independent of the training set to avoid over-fitting.
• If the accuracy is acceptable, the model classifies future data tuples with unknown class labels.

Supervised learning

• The training data has labels indicating the class of the observations.
• New data is classified based on the training set.

Unsupervised learning

• The class labels of the training data is unknown.
• Given a set of measurements or observations it aims to establish the existence of classes or clusters in the data.

Issues Regarding Classification

• Data preparation: Preprocesses data to reduce noise and handle missing values.
• Relevance analysis: Removes irrelevant or redundant attributes.
• Data transformation: Data generalizes to higher level concepts and normalizes when methods needing distance measurements are used.
• Evaluating classification methods takes into account predictive accuracy, speed, scalability, robustness, interpretability and goodness of rules.
• Issues include time to construct and use the model, handling noise and missing values, efficiency in disk-resident databases and understanding provided by the model.

Decision Tree Induction

• It has a flow-chart-like tree structure to perform classification.
• An internal node represents a test on an attribute.
• A branch represents an outcome of the test.
• Leaf nodes represent class labels or class distribution.
• It is used by classifying an unknown sample where the attribute values of the sample are tested against the decision tree.
• A decision tree can be obtained through manual construction or decision tree induction, which discovers a tree from data automatically
• Tree construction: At the start, all training examples are at the root and are partitioned recursively based on selected attributes.
• Tree pruning identifies and removes branches that reflect noise or outliers.

Algorithm for Decision Tree Induction

• It uses a basic, greedy algorithm.
• It creates a tree in a top-down recursive divide-and-conquer manner.
• It starts with all training examples at the root.
• All attributes are categorical, and if the values are continuous, they are discretized in advance.
• Examples are partitioned recursively based on selected attributes.
• The recursive partitioning stops when one of the following conditions is true.
• All samples for a given node belong to the same class.
• There are no remaining attributes on which the samples may be further partitioned, where majority voting is employed.
• There are no samples for the branch test-attribute=ai, so a leaf is created with the majority class in samples.

Basic Algorithm for Decision Tree Induction

• If the tuples in D are all of the same class, then node N becomes a leaf and is labeled with that class.
• The algorithm calls Attribute_selection_method to determine the splitting criterion otherwise.
• The splitting criterion indicates the splitting attribute, which is to be tested at node N.
• The splitting criterion leads to specific branches from node N.

Attribute Selection by Information Gain Computation

• The information gain (ID3/C4.5) measures the degree of diversity using the entropy function.
• Information gain in decision tree induction assumes attribute A partitions set S.
• The attribute with the highest information gain is the test attribute for the set S.

Gain Ratio

• Gain Ratio: It is a successor of ID3, and attempts to overcome the bias in information gain.
• Instead of information gain, the attribute with the maximum gain ratio is selected as the splitting attribute.

Extracting Rules from Trees

• Knowledge is represented in the form of IF-THEN rules.
• One rule is created for each path from the root to a leaf.
• Each attribute-value pair along a path forms a conjunction.
• The leaf node holds the class prediction.

Classification in Large Databases

• Scalability: Classifying data sets with millions of examples and hundreds of attributes with reasonable speed.
• Decision tree induction is used, because it has a relatively fast learning speed, it is convertible to simple classification rules and it has a comparable classification accuracy to other methods.