CIS664-Knowledge Discovery and Data MiningAgendaClassification vs. PredictionClassification—A Two-Step ProcessClassification Process: Model ConstructionClassification Process: Model usage in PredictionSupervised vs. Unsupervised LearningSlide 8Issues regarding classification and prediction: Data PreparationIssues regarding classification and prediction: Evaluating Classification MethodsSlide 11Classification by Decision Tree InductionGini Index (IBM IntelligentMiner)Approaches to Determine the Final Tree SizeEnhancements to basic decision tree inductionClassification in Large DatabasesScalable Decision Tree InductionData Cube-Based Decision-Tree InductionPresentation of Classification ResultsSlide 20Bayesian Classification: Why?Bayesian TheoremBayesian classificationEstimating a-posteriori probabilitiesNaïve Bayesian ClassificationPlay-tennis example: estimating P(xi|C)Play-tennis example: classifying XThe independence hypothesis…Bayesian Belief NetworksSlide 32Slide 33Neural NetworksA NeuronNetwork TrainingMulti-Layer PerceptronSlide 39SVM—Support Vector MachinesSVM—History and ApplicationsSVM—General PhilosophySVM—Margins and Support VectorsSVM—When Data Is Linearly SeparableSVM—Linearly SeparableWhy Is SVM Effective on High Dimensional Data?SVM—Linearly InseparableSVM—Kernel functionsScaling SVM by Hierarchical MicroClusteringCB-SVM: Clustering-Based SVMCF-Tree: Hierarchical Micro-clusterCB-SVM Algorithm: OutlineSelective DeclusteringExperiment on Synthetic DatasetExperiment on a Large Data SetSVM vs. Neural NetworkSVM Related LinksSVM—Introduction LiteratureSlide 59Association-Based ClassificationSlide 61Other Classification MethodsInstance-Based MethodsThe k-Nearest Neighbor AlgorithmDiscussion on the k-NN AlgorithmCase-Based ReasoningRemarks on Lazy vs. Eager LearningGenetic Algorithms – Evolutionary ApproachRough Set ApproachFuzzy Set ApproachesSlide 71What Is Prediction?Predictive Modeling in DatabasesRegress Analysis and Log-Linear Models in PredictionRegress Analysis and Log-Linear Models in PredictionLocally Weighted RegressionPrediction: Numerical DataPrediction: Categorical DataSlide 79Classifier Accuracy MeasuresPredictor Error MeasuresEvaluating the Accuracy of a Classifier or Predictor (I)Evaluating the Accuracy of a Classifier or Predictor (II)Slide 84Ensemble Methods: Increasing the AccuracyBagging: Boostrap AggregationBoostingAdaboost (Freund and Schapire, 1997)Model Selection: ROC CurvesSlide 90Summary (I)Summary (II)References (1)References (2)Slide 95CIS664-Knowledge Discovery and Data MiningVasileios MegalooikonomouDept. of Computer and Information SciencesTemple UniversityClassification and Prediction(based on notes by Jiawei Han and Micheline Kamber)Agenda•What is classification? What is prediction?•Issues regarding classification and prediction•Classification by decision tree induction•Bayesian Classification•Classification by backpropagation•Classification based on concepts from association rule mining•Other Classification Methods•Prediction•Classification accuracy•Summary•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•Prediction: –models continuous-valued functions, i.e., predicts unknown or missing values •Typical Applications–credit approval–target marketing–medical diagnosis–treatment effectiveness analysis•Large data sets: disk-resident rather than memory-resident dataClassification vs. PredictionClassification—A Two-Step Process •Model construction: describing a set of predetermined classes–Each tuple is assumed to belong to a predefined class, as determined by the class label attribute (supervised learning)–The set of tuples used for model construction: training set–The model is represented as classification rules, decision trees, or mathematical formulae•Model usage: for classifying previously unseen objects–Estimate accuracy of the model using a test set•The known label of test sample 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 occurClassification Process: Model ConstructionTrainingDataNAME RAN K YEARS TENUREDMike Assistant Prof 3 noMary Assistant Prof 7 yesBill Professor 2 yesJim Associate Prof 7 yesDave Assistant Prof 6 noAnne Associate Prof 3 noClassificationAlgorithmsIF rank = ‘professor’OR years > 6THEN tenured = ‘yes’ Classifier(Model)Classification Process: Model usage in PredictionClassifierTestingDataNAME RANK YEAR S TE NUREDTom Assistant Prof 2 noMerlisa Associate Prof 7 noGeorge Professor 5 yesJoseph Assistant Prof 7 yesUnseen Data(Jeff, Professor, 4)Tenured?Supervised vs. Unsupervised 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•Unsupervised learning (clustering)–The class labels of training data is unknown–Given a set of measurements, observations, etc. the aim is to establish the existence of classes or clusters in the dataAgenda•What is classification? What is prediction?•Issues regarding classification and prediction•Classification by decision tree induction•Bayesian Classification•Classification by backpropagation•Classification based on concepts from association rule mining•Other Classification Methods•Prediction•Classification accuracy•SummaryIssues regarding classification and prediction: 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 dataIssues regarding classification and prediction: Evaluating Classification Methods•Predictive accuracy•Speed and scalability–time to construct the model–time to use the model–efficiency in disk-resident databases•Robustness–handling noise and missing values•Interpretability: –understanding and insight provided by the model•Goodness of rules–decision tree size–compactness of classification rulesAgenda•What is classification? What is