Data Mining - Decision Trees

Data Mining - Decision Trees

1. CLASSIFICATION TECHNIQUES

   • C4.5 (and its Java implementation called J48)
   • Naive Bayesian Classifier
     • To-Do: 15 slides; starts 2. page 79
     • ADVANTAGES: easy to implement, very efficient, good results in many applications
     • DISADVANTAGES: Assumption: class conditional independence, therefore loss of accuracy when the assumption is seriously violated (those highly correlated data sets)
   • Hunt's Algorithm
     • To-Do
   • many others like: Rule Induction; Bayesian Networks; Support Vector Machine, K-Nearest Neighbor, Neural Networks, Genetic Algorithms, Fuzzy Classification

2. Impurity functions

   • used to decide the splitting attribute
   • Entropy
   • Gini
     • To-Do

3. EVALUATION

   • What to evaluate
     • Predictive Accuracy
       • Accuracy = (# of correct classifications) / (# of all cases) Error = 1 - Accuracy
       • Accuracy is not suitable in some cases!
         • Classifying skewed or highly imbalanced data, e.g., network intrusion and financial fraud detection, searching for documents of particular topic; we are interested only in the minority class. High accuracy does not mean any intrusion is detected. e.g., 1% intrusion. Achieve 99% accuracy by doing nothing. The class of interest is commonly called the positive class, and the rest negative classes.
     • Efficiency
       • time to construct the model or to use the model
     • Robustness
       • handling noise and missing values
     • Scalability
       • efficiency in disk-resident databases
     • Interpret-ability
       • understandable and insight provided by the model
     • Compactness
       • of the model: size of the tree, or the number of rules
   • Methods/Techniques
     • Holdout set (Test set)
       • Used when the data set is large. The available data set D is divided into two disjoint subsets: training set (learning a model) and test set (testing the model)
         • Important: training set should not be used in testing and the test set should not be used in learning. Unseen test set provides a unbiased estimate of accuracy.
     • N-fold cross-validation
       • Used when the data set is not large. The available data is partitioned into n equal-size disjoint subsets. Use each subset as the test set and combine the rest n-1 subsets as the training set to learn a classifier. The procedure is run n times, which give n accuracies. The final estimated accuracy of learning is the average of the n accuracies. 10-fold and 5-fold cross-validations are common.
     • Leave-one-out cross-validation
       • Used when the data set is very small. It's a special case of cross-validation. Each fold of the cross validation has only a single test instance and all the rest of the data is used in training. If the original data has m instances, this is m-fold cross-validation
     • Validation set
       • The data set is divided into three subsets, a training set, a validation set and a test set.Used frequently for estimating parameters in learning algorithms (Cross-validation can be used too). The values that give the best accuracy on the validation set are used as the final parameter values.
   • CLASSIFICATION MEASURES
     • Precision and Recall
       • Used in information retrieval and text classification. We use a confusion matrix to introduce them. Precision and Recall only measure classification on the positive class.
       • Confusion Matrix
         • TP: correctly classified positive instances FN: FP: TN:
       • Precision p = (correctly classified positive instances) / (total instances classified as positive)
       • Recall r = (correctly classified positive instances) / (total number of actual positive instances in the test set.)
     • F1-value (aka F1-score)
       • It is hard to compare two classifiers using two measures. F1 score combines precision and recall into one measure.
     • ROC curve
       • Receive Operating Characteristics curve. It's a plot of TPR against FPR.
     • Sensitivity
       • Same as TPR
     • Specificity
       • True Negative Rate

Bilder und Dateien der Mindmap