Classification techniques in data mining

This slide provides the overview of the various classification techniques used in data mining

1. Outline Of The Chapter Basics Decision Tree Classifier Rule Based Classifier Nearest Neighbor Classifier Bayesian Classifier Artificial Neural Network Classifier Issues : Over-fitting, Validation, Model Comparison Compiled By: Kamal Acharya

2. Supervised Learning Supervised learning (classification) Supervision: The training data (observations, measurements, etc.) are accompanied by labels indicating the class of the observations New data is classified based on the training set Compiled By: Kamal Acharya

3. Classification: predicts categorical class labels classifies data (constructs a model) based on the training set and the values ( class labels ) in a classifying attribute and uses it in classifying new data Regression: models continuous-valued functions, i.e., predicts unknown or missing values Typical Applications credit approval target marketing medical diagnosis treatment effectiveness analysis Classification vs. Prediction Compiled By: Kamal Acharya

4. Credit approval A bank wants to classify its customers based on whether they are expected to pay back their approved loans The history of past customers is used to train the classifier The classifier provides rules, which identify potentially reliable future customers Classification rule: If age = “31...40” and income = high then credit_rating = excellent Future customers Paul: age = 35, income = high  excellent credit rating John: age = 20, income = medium  fair credit rating Why Classification? A motivating application Compiled By: Kamal Acharya

5. Classification—A Two-Step Process Model construction : describing a set of predetermined classes Each tuple /sample is assumed to belong to a predefined class, as determined by the class label attribute The set of tuples used for model construction: training set The model is represented as classification rules, decision trees, or mathematical formulae Compiled By: Kamal Acharya

6. Classification Process (1): Model Construction: E.g. Training Data Classification Algorithms IF rank = ‘professor’ OR years > 6 THEN tenured = ‘yes’ Classifier (Model) Compiled By: Kamal Acharya

7. Classification—A Two-Step Process Model usage : for classifying future or unknown objects Estimate accuracy of the model The known label of test samples is compared with the classified result from the model Accuracy rate is the percentage of test set samples that are correctly classified by the model Test set is independent of training set, otherwise over-fitting will occur Compiled By: Kamal Acharya

8. Classification Process (2): Use the Model in Prediction Classifier Testing Data Unseen Data (Jeff, Professor, 4) Tenured? Compiled By: Kamal Acharya

9. Classification by Decision Tree Induction Decision tree A flow-chart-like tree structure Internal node denotes a test on an attribute Branch represents an outcome of the test Leaf nodes represent class labels or class distribution Compiled By: Kamal Acharya

10. Classification by Decision Tree Induction Decision tree generation consists of two phases Tree construction At start, all the training examples are at the root Partition examples recursively based on selected attributes Tree pruning Identify and remove branches that reflect noise or outliers Use of decision tree: Classifying an unknown sample Test the attribute values of the sample against the decision tree Compiled By: Kamal Acharya

11. Example of a Decision Tree categorical categorical continuous class Home Owner MarSt Income YES NO NO NO Yes No Married Single, Divorced < 80K > 80K Splitting Attributes Training Data Model: Decision Tree Compiled By: Kamal Acharya

12. Apply Model to Test Data Home Owner MarSt Income YES NO NO NO Yes No Married Single, Divorced < 80K > 80K Test Data Start from the root of tree. Compiled By: Kamal Acharya

13. Apply Model to Test Data MarSt Income YES NO NO NO Yes No Married Single, Divorced < 80K > 80K Test Data Home Owner Compiled By: Kamal Acharya

14. Apply Model to Test Data MarSt Income YES NO NO NO Yes No Married Single, Divorced < 80K > 80K Test Data Home Owner Compiled By: Kamal Acharya

15. Apply Model to Test Data MarSt Income YES NO NO NO Yes No Married Single, Divorced < 80K > 80K Test Data Home Owner Compiled By: Kamal Acharya

16. Apply Model to Test Data MarSt Income YES NO NO NO Yes No Married Single, Divorced < 80K > 80K Test Data Home Owner Compiled By: Kamal Acharya

17. Apply Model to Test Data MarSt Income YES NO NO NO Yes No Married Single, Divorced < 80K > 80K Test Data Assign Defaulted to “No” Home Owner Compiled By: Kamal Acharya

18. Decision Tree Classification Task Decision Tree Compiled By: Kamal Acharya

19. Algorithm for Decision Tree Induction Basic algorithm (a greedy algorithm) Tree is constructed in a top-down recursive divide-and-conquer manner At start, all the training examples are at the root Attributes are categorical (if continuous-valued, they are discretized in advance) Samples are partitioned recursively based on selected attributes Test attributes are selected on the basis of a heuristic or statistical measure (e.g., information gain ) Conditions for stopping partitioning All samples for a given node belong to the same class There are no remaining attributes for further partitioning – majority voting is employed for classifying the leaf There are no samples left Compiled By: Kamal Acharya

20. Algorithm for Decision Tree Induction ( pseudocode ) Algorithm GenDecTree (Sample S, Attlist A) create a node N If all samples are of the same class C then label N with C; terminate; If A is empty then label N with the most common class C in S ( majority voting ); terminate; Select a A , with the highest information gain ; Label N with a; For each value v of a: Grow a branch from N with condition a=v; Let S v be the subset of samples in S with a=v; If S v is empty then attach a leaf labeled with the most common class in S; Else attach the node generated by GenDecTree( S v , A-a) Compiled By: Kamal Acharya

21. Attribute Selection Measure: Information Gain (ID3) Select the attribute with the highest information gain Let p i be the probability that an arbitrary tuple in D (data set) belongs to class C i , estimated by | C i , D |/|D| Expected information (entropy) needed to classify a tuple in D: Information needed (after using A to split D into v partitions) to classify D: Information gained by branching on attribute A Compiled By: Kamal Acharya

22. Input: Training Dataset Compiled By: Kamal Acharya

23. Output: A Decision Tree for “ buys_computer ” age? overcast student? credit rating? no yes fair excellent <=30 >40 no no yes yes yes 30..40 Compiled By: Kamal Acharya

24. Attribute Selection: Information Gain Class P: buys_computer = “yes” Class N: buys_computer = “no” Compiled By: Kamal Acharya

25. Splitting the samples using age age? <=30 30...40 >40 labeled yes Because age has the highest information gain among the attributes, it is selected as the splitting attribute Compiled By: Kamal Acharya

26. Over-fitting and Tree Pruning Over-fitting: An induced tree may over-fit the training data Good accuracy on training data but poor on test data Symptoms: Too many branches, some may reflect anomalies due to noise or outliers Results in Poor accuracy for unseen samples Two approaches to avoid over-fitting Pre-pruning: Halt tree construction early—do not split a node if this would result in the goodness measure(Information gain) falling below a threshold Difficult to choose an appropriate threshold Post-pruning: Remove branches from a “fully grown” tree—get a sequence of progressively pruned trees Use a set of data different from the training data to decide which is the “best pruned tree” Compiled By: Kamal Acharya

27. Decision Tree Based Classification Advantages: Inexpensive to construct Extremely fast at classifying unknown records Easy to interpret for small-sized trees Robust to noise (especially when methods to avoid over-fitting are employed) Can easily handle redundant or irrelevant attributes (unless the attributes are interacting ) Compiled By: Kamal Acharya

28. Decision Tree Based Classification Disadvantages : Space of possible decision trees is exponentially large. Greedy approaches are often unable to find the best tree. Does not take into account interactions between attributes Each decision boundary involves only a single attribute Compiled By: Kamal Acharya

29. Class work Study the table given below and construct a decision tree based on the greedy algorithm using information gain. Compiled By: Kamal Acharya

30. Compiled By: Kamal Acharya We build the final tree Contd..

31. Home work Study the table given below and construct a decision tree based on the greedy algorithm using information gain. Compiled By: Kamal Acharya Day Outlook Temperature Humidity Wind Play Tennis D1 SUNNY HOT HIGH WEAK NO D2 SUNNY HOT HIGH STRONG NO D3 OVERCAST HOT HIGH WEAK YES D4 RAIN MILD HIGH WEAK YES D5 RAIN COOL NORMAL WEAK YES D6 RAIN COOL NORMAL STRONG NO D7 OVERCAST COOL NORMAL STRONG YES D8 SUNNY MILD HIGH WEAK NO D9 SUNNY COOL NORMAL WEAK YES D10 RAIN MILD NORMAL WEAK YES D11 SUNNY MILD NORMAL STRONG YES D12 OVERCAST MILD HIGH STRONG YES D13 OVERCAST HOT NORMAL WEAK YES D14 RAIN MILD HIGH STRONG NO

32. Rule Based Classifier In Rule based classifiers learned model is represented as a set of If-Then rules. A rule-based classifier uses a set of IF-THEN rules for classification. An IF-THEN rule is an expression of the form IF condition THEN conclusion. An example is : IF (Give Birth = no)  (Can Fly = yes) THEN Birds The “IF” part (or left side) of a rule is known as the rule antecedent or precondition. The “THEN” part (or right side) is the rule consequent. In the rule antecedent, the condition consists of one or more attribute tests (e.g., (Give Birth = no)  (Can Fly = yes) ) That are logically ANDed . The rule’s consequent contains a class prediction. Compiled By: Kamal Acharya

33. Contd.. Rule-based Classifier (Example) Compiled By: Kamal Acharya R1: (Give Birth = no)  (Can Fly = yes)  Birds R2: (Give Birth = no)  (Live in Water = yes)  Fishes R3: (Give Birth = yes)  (Blood Type = warm)  Mammals R4: (Give Birth = no)  (Can Fly = no)  Reptiles R5: (Live in Water = sometimes)  Amphibians

34. How does Rule-based Classifier Work? R1: (Give Birth = no)  (Can Fly = yes)  Birds R2: (Give Birth = no)  (Live in Water = yes)  Fishes R3: (Give Birth = yes)  (Blood Type = warm)  Mammals R4: (Give Birth = no)  (Can Fly = no)  Reptiles R5: (Live in Water = sometimes)  Amphibians A lemur triggers rule R3, so it is classified as a mammal A turtle triggers both R4 and R5 A dogfish shark triggers none of the rules Compiled By: Kamal Acharya

35. Compiled By: Kamal Acharya age? student? credit rating? <=30 >40 no yes yes yes 31..40 no fair excellent yes no Example : Rule extraction from our buys_computer decision-tree IF age = young AND student = no THEN buys_computer = no IF age = young AND student = yes THEN buys_computer = yes IF age = mid-age THEN buys_computer = yes IF age = old AND credit_rating = excellent THEN buys_computer = yes IF age = young AND credit_rating = fair THEN buys_computer = no Rule Extraction from a Decision Tree Rules are easier to understand than large trees 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 holds the class prediction

36. Rule Coverage and Accuracy A Rule R can be assessed by its coverage and accuracy Coverage of a rule : Fraction of records that satisfy the antecedent of a rule Accuracy of a rule : Fraction of records that satisfy the antecedent that also satisfy the consequent of a rule (Status=Single)  No Coverage = 40%, Accuracy = 50% Compiled By: Kamal Acharya

37. Contd.. Advantages of Rule-Based Classifiers: As highly expressive as decision trees Easy to interpret Easy to generate Can classify new instances rapidly Performance comparable to decision trees Compiled By: Kamal Acharya

38. Compiled By: Kamal Acharya Bayesian Classification: Why? A statistical classifier : performs probabilistic prediction, i.e., predicts class membership probabilities Foundation: Based on Bayes ’ Theorem. Performance: A simple Bayesian classifier, naïve Bayesian classifier , has comparable performance with decision tree and selected neural network classifiers Incremental : Each training example can incrementally increase/decrease the probability that a hypothesis is correct. Standard : Even when Bayesian methods are computationally intractable, they can provide a standard of optimal decision making against which other methods can be measured

39. Compiled By: Kamal Acharya Bayesian Theorem: Basics Let X be a data sample (“ evidence ”): class label is unknown Let H be a hypothesis that X belongs to class C Classification is to determine P(H| X ), the probability that the hypothesis holds given the observed data sample X P(H) ( prior probability ), the initial probability E.g., X will buy computer, regardless of age, income, … P( X ): probability that sample data is observed P( X |H) ( posteriori probability ), the probability of observing the sample X , given that the hypothesis holds E.g., Given that X will buy computer, the prob. that X is 31..40, medium income

40. Compiled By: Kamal Acharya Bayesian Theorem Given training data X , posteriori probability of a hypothesis H , P(H| X ) , follows the Bayes theorem Predicts X belongs to C i iff the probability P( C i | X ) is the highest among all the P( C k |X ) for all the k classes

41. Compiled By: Kamal Acharya Towards Naïve Bayesian Classifier Let D be a training set of tuples and their associated class labels, and each tuple is represented by an n-D attribute vector X = (x 1 , x 2 , …, x n ) Suppose there are m classes C 1 , C 2 , …, C m . Classification is to derive the maximum posteriori, i.e., the maximal P( C i | X ) This can be derived from Bayes ’ theorem Since P(X) is constant for all classes, only needs to be maximized

42. Compiled By: Kamal Acharya Derivation of Naïve Bayes Classifier A simplified assumption : attributes are conditionally independent (i.e., no dependence relation between attributes ): This greatly reduces the computation cost: Only counts the class distribution

43. Compiled By: Kamal Acharya Naïve Bayesian Classifier: Training Dataset Class: C1:buys_computer = ‘yes’ C2:buys_computer = ‘no’ Data sample X = (age <=30, Income = medium, Student = yes Credit_rating = Fair)

44. Compiled By: Kamal Acharya Naïve Bayesian Classifier: An Example P( C i ): P( buys_computer = “yes”) = 9/14 = 0.643 P( buys_computer = “no”) = 5/14= 0.357 Compute P( X|C i ) for each class P(age = “<=30” | buys_computer = “yes”) = 2/9 = 0.222 P(age = “<= 30” | buys_computer = “no”) = 3/5 = 0.6 P(income = “medium” | buys_computer = “yes”) = 4/9 = 0.444 P(income = “medium” | buys_computer = “no”) = 2/5 = 0.4 P(student = “yes” | buys_computer = “yes) = 6/9 = 0.667 P(student = “yes” | buys_computer = “no”) = 1/5 = 0.2 P( credit_rating = “fair” | buys_computer = “yes”) = 6/9 = 0.667 P( credit_rating = “fair” | buys_computer = “no”) = 2/5 = 0.4 X = (age <= 30 , income = medium, student = yes, credit_rating = fair) P( X|C i ) : P( X|buys_computer = “yes”) = 0.222 x 0.444 x 0.667 x 0.667 = 0.044 P( X|buys_computer = “no”) = 0.6 x 0.4 x 0.2 x 0.4 = 0.019 P( X|C i )*P( C i ) : P( X|buys_computer = “yes”) * P( buys_computer = “yes”) = 0.028 P( X|buys_computer = “no”) * P( buys_computer = “no”) = 0.007 Therefore, X belongs to class (“ buys_computer = yes”)

45. Compiled By: Kamal Acharya Avoiding the 0-Probability Problem Naïve Bayesian prediction requires each conditional prob. be non-zero. Otherwise, the predicted prob. will be zero Ex. Suppose a dataset with 1000 tuples , income=low (0), income= medium (990), and income = high (10), Use Laplacian correction Adding 1 to each case Prob (income = low) = 1/1003 Prob (income = medium) = 991/1003 Prob (income = high) = 11/1003 The “corrected” prob. estimates are close to their “uncorrected” counterparts

46. Compiled By: Kamal Acharya Naïve Bayesian Classifier: Comments Advantages Easy to implement Good results obtained in most of the cases Disadvantages Assumption: class conditional independence, therefore loss of accuracy Practically, dependencies exist among variables E.g., hospitals: patients: Profile: age, family history, etc. Symptoms: fever, cough etc., Disease: lung cancer, diabetes, etc. Dependencies among these cannot be modeled by Naïve Bayesian Classifier

47. Naive Bayesian Classifier Example play tennis? Compiled By: Kamal Acharya

48. Naive Bayesian Classifier Example 9 5 Compiled By: Kamal Acharya

49. Naive Bayesian Classifier Example Given the training set, we compute the probabilities: We also have the probabilities P = 9/14 N = 5/14 Compiled By: Kamal Acharya

50. Naive Bayesian Classifier Example To classify a new sample X: outlook = sunny temperature = cool humidity = high windy = false Prob (P|X) = Prob (P)* Prob ( sunny|P )* Prob ( cool|P )* Prob ( high|P )* Prob ( false|P ) = 9/14*2/9*3/9*3/9*6/9 = 0.01 Prob (N|X) = Prob (N)* Prob ( sunny|N )* Prob ( cool|N )* Prob ( high|N )* Prob ( false|N ) = 5/14*3/5*1/5*4/5*2/5 = 0.013 Therefore X takes class label N Compiled By: Kamal Acharya

51. Second example X = <rain, hot, high, false> P( X|p )·P(p) = P( rain|p )·P( hot|p )·P( high|p )·P( false|p )·P(p) = 3/9·2/9·3/9·6/9·9/14 = 0.010582 P( X|n )·P(n) = P( rain|n )·P( hot|n )·P( high|n )·P( false|n )·P(n) = 2/5·2/5·4/5·2/5·5/14 = 0.018286 Sample X is classified in class N (don’t play) Naive Bayesian Classifier Example Compiled By: Kamal Acharya

52. Compiled By: Kamal Acharya Lazy vs. Eager Learning Lazy vs. eager learning Lazy learning (e.g., instance-based learning): Simply stores training data (or only minor processing) and waits until it is given a test tuple Eager learning: Given a set of training set, constructs a classification model before receiving new (e.g., test) data to classify Lazy: less time in training but more time in predicting Accuracy Lazy method effectively uses a richer hypothesis space since it uses many local linear functions to form its implicit global approximation to the target function Eager: must commit to a single hypothesis that covers the entire instance space

53. Compiled By: Kamal Acharya Lazy Learner: Instance-Based Methods Instance-based learning: Store training examples and delay the processing (“lazy evaluation”) until a new instance must be classified Typical approach : k -nearest neighbor approach Instances represented as points in a Euclidean space .

54. Compiled By: Kamal Acharya The k -Nearest Neighbor Algorithm All instances correspond to points in the n-D space The nearest neighbor are defined in terms of Euclidean distance, dist( X 1 , X 2 ) Target function could be discrete- or real- valued . _ + _ x q + _ _ + _ _ +

55. Compiled By: Kamal Acharya Contd … For discrete-valued, k -NN returns the most common value among the k training examples nearest to x q k-NN for real-valued prediction for a given unknown tuple Returns the mean values of the k nearest neighbors Distance-weighted nearest neighbor algorithm Weight the contribution of each of the k neighbors according to their distance to the query x q Give greater weight to closer neighbors

56. Compiled By: Kamal Acharya Contd … Advantages: Robust to noisy data by averaging k-nearest neighbors Disadvantages: Curse of dimensionality: distance between neighbors could be dominated by irrelevant attributes To overcome it elimination of the least relevant attributes

57. Compiled By: Kamal Acharya Classification by Backpropagation Backpropagation : A neural network learning algorithm Started by psychologists and neurobiologists to develop and test computational analogues of neurons A neural network : A set of connected input/output units where each connection has a weight associated with it During the learning phase, the network learns by adjusting the weights so as to be able to predict the correct class label of the input tuples Also referred to as connectionist learning due to the connections between units

58. Compiled By: Kamal Acharya Neural Network as a Classifier Weakness Long training time Require a number of parameters typically best determined empirically, e.g., the network topology or ``structure." Poor interpretability: Difficult to interpret the symbolic meaning behind the learned weights and of ``hidden units" in the network Strength High tolerance to noisy data Ability to classify untrained patterns Well-suited for continuous-valued inputs and outputs Successful on a wide array of real-world data Algorithms are inherently parallel Techniques have recently been developed for the extraction of rules from trained neural networks

59. Compiled By: Kamal Acharya A Neuron (= a perceptron ) The n -dimensional input vector x is mapped into variable y by means of the scalar product and a nonlinear function mapping - f weighted sum Input vector x output y Activation function weight vector w å w w 1 w n x x 1 x n bj

60. Compiled By: Kamal Acharya A Multi-Layer Feed-Forward Neural Network Output layer Input layer Hidden layer Output vector Input vector: X w ij

61. Compiled By: Kamal Acharya How A Multi-Layer Neural Network Works? The inputs to the network correspond to the attributes measured for each training tuple Inputs are fed simultaneously into the units making up the input layer They are then weighted and fed simultaneously to a hidden layer The number of hidden layers is arbitrary, although usually only one The weighted outputs of the last hidden layer are input to units making up the output layer , which emits the network's prediction The network is feed-forward in that none of the weights cycles back to an input unit or to an output unit of a previous layer From a statistical point of view, networks perform nonlinear regression : Given enough hidden units and enough training samples, they can closely approximate any function

62. Compiled By: Kamal Acharya Defining a Network Topology First decide the network topology: # of units in the input layer , # of hidden layers (if > 1), # of units in each hidden layer , and # of units in the output layer Normalizing the input values for each attribute measured in the training tuples to [0.0—1.0] One input unit per domain value, each initialized to 0 Output , if for classification and more than two classes, one output unit per class is used Once a network has been trained and its accuracy is unacceptable , repeat the training process with a different network topology or a different set of initial weights

63. Compiled By: Kamal Acharya Backpropagation Iteratively process a set of training tuples & compare the network's prediction with the actual known target value For each training tuple , the weights are modified to minimize the mean squared error between the network's prediction and the actual target value Modifications are made in the “ backwards ” direction: from the output layer, through each hidden layer down to the first hidden layer, hence “ backpropagation ” Steps Initialize weights (to small random #s) and biases in the network Propagate the inputs forward (by applying activation function) Backpropagate the error (by updating weights and biases) Terminating condition (when error is very small, etc.)

64. Issues regarding classification and prediction (1): Data Preparation Data cleaning Preprocess data in order to reduce noise and handle missing values Relevance analysis (feature selection) Remove the irrelevant or redundant attributes Data transformation Generalize and/or normalize data numerical attribute income  categorical {low, medium, high} normalize all numerical attributes to [0,1) Compiled By: Kamal Acharya

65. Issues regarding classification and prediction (2): Evaluating Classification Methods accuracy Speed time to construct the model time to use the model Robustness handling noise and missing values Scalability efficiency in disk-resident databases Interpretability : understanding and insight provided by the model Goodness of rules (quality) decision tree size compactness of classification rules Compiled By: Kamal Acharya

66. Compiled By: Kamal Acharya Evaluation methods Holdout Method : The available data set D is divided into two disjoint subsets, the training set D train (for learning a model) the test set D test (for 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. The test set is also called the holdout set . (the examples in the original data set D are all labeled with classes.) This method is mainly used when the data set D is large.

67. Compiled By: Kamal Acharya Evaluation methods (cont…) k-fold cross-validation : T he available data is partitioned into k 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 k times, which give k accuracies. The final estimated accuracy of learning is the average of the k accuracies. 10-fold and 5-fold cross-validations are commonly used. This method is used when the available data is not large.

68. Compiled By: Kamal Acharya Evaluation methods (cont…) Leave-one-out cross-validation : This method is used when the data set is very small. It is a special case of cross-validation Each fold of the cross validation has only a single test example and all the rest of the data is used in training. If the original data has m examples, this is m-fold cross-validation

69. Compiled By: Kamal Acharya Evaluation methods (cont…) Validation set : the available data is divided into three subsets, a training set, a test set and a validation set A validation set is used frequently for estimating parameters in learning algorithms. In such cases, the values that give the best accuracy on the validation set are used as the final parameter values. Cross-validation can be used for parameter estimating as well.

70. Home Work What is supervised classification? In what situations can this technique be useful? Briefly outline the major steps of decision tree classification. Why naïve Bayesian classification called naïve? Briefly outline the major idea of naïve Bayesian classification. Compare the advantages and disadvantages of eager classification versus lazy classification. Write an algorithm for k-nearest- neighbor classification given k, the nearest number of neighbors, and n, the number of attributes describing each tuple . Compiled By: Kamal Acharya

71. Thank You ! Compiled By: Kamal Acharya