Classification: Basic Concepts and Decision Trees A programming task Classification: Definition Given a collection of records (training set ) Each record contains a set of attributes, one of the attributes is the class. Find a model for class attribute as a function of the values of other attributes. Goal: previously unseen records should be assigned a class as accurately as possible. A test set is used to determine the accuracy of the model. Usually, the given data set is divided into training and test sets, with training set used to build the model and test set used to validate it. Illustrating Classification Task Tid Attrib1 Yes Attrib2 Attrib3 Class Large 125K No No Medium 100K No No Small 70K Yes Medium 120K No No Large 95K Yes No Medium 60K No Yes Large 220K No No Small 85K Yes No Medium 75K No No Small 90K Yes Learning algorithm Induction Learn Model Model 10 Training Set Tid Attrib1 11 No 12 Attrib2 Attrib3 Class Small 55K ? Yes Medium 80K ? 13 Yes Large 110K ? 14 No Small 95K ? 15 No Large 67K ? 10 Test Set Apply Model Deduction Examples of Classification Task Predicting tumor cells as benign or malignant Classifying credit card transactions as legitimate or fraudulent Classifying secondary structures of protein as alpha-helix, beta-sheet, or random coil Categorizing news stories as finance, weather, entertainment, sports, etc Classification Using Distance Place items in class to which they are “closest”. Must determine distance between an item and a class. Classes represented by Centroid: Central value. Medoid: Representative point. Individual points Algorithm: KNN Classification Techniques Decision Tree based Methods Rule-based Methods Memory based reasoning Neural Networks Naïve Bayes and Bayesian Belief Networks Support Vector Machines A first example Database of 20,000 images of h