web数据挖掘课件CS583-supervised-learning.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,CS583,Bing Liu,UIC,*,Chapter 3:Supervised Learning,1,CS583,Bing Liu,UIC,Road Map,Basic concepts,Decision tree induction,Evaluation of classifiers,Rule induction,Classification using association rules,Nave Bayesian classification,Nave Bayes for text classification,Support vector machines,K-nearest neighbor,Ensemble methods:Bagging and Boosting,Summary,2,CS583,Bing Liu,UIC,An example application,An emergency room in a hospital measures 17 variables(e.g.,blood pressure,age,etc)of newly admitted patients.,A decision is needed,:whether to put a new patient in an intensive-care unit.,Due to the high cost of ICU,those patients who may survive less than a month are given higher priority.,Problem,:to predict,high-risk patients,and discriminate them from,low-risk patients,.,3,CS583,Bing Liu,UIC,Another application,A credit card company receives thousands of applications for new cards.Each application contains information about an applicant,age,Marital status,annual salary,outstanding debts,credit rating,etc.,Problem,:to decide whether an application should approved,or to classify applications into two categories,approved,and,not approved,.,4,CS583,Bing Liu,UIC,Machine learning and our focus,Like human learning from past experiences.,A computer does not have“experiences”.,A computer system learns from data,which represent some“past experiences”of an application domain.,Our focus:,learn,a target function,that can be used to predict the values of a discrete class attribute,e.g.,approve,or,not-approved,and,high-risk,or,low risk,.,The task is commonly called:,Supervised learning,classification,or,inductive learning.,5,CS583,Bing Liu,UIC,An example:the learning task,Learn a classification model,from the data,Use the model to classify future loan applications into,Yes(approved)and,No(not approved),What is the class for following case/instance?,8,CS583,Bing Liu,UIC,Supervised vs.unsupervised Learning,Supervised learning:,classification is seen as supervised learning from examples.,Supervision,:The data(observations,measurements,etc.)are labeled with pre-defined classes.It is like that a“teacher”gives the classes(,supervision,).,Test data are classified into these classes too.,Unsupervised learning,(clustering),Class labels of the data are unknown,Given a set of data,the task is to establish the existence of classes or clusters in the data,9,CS583,Bing Liu,UIC,Supervised learning process:two steps,Learning(training),:Learn a model using the,training data,Testing:,Test the model using,unseen,test data,to assess the model accuracy,10,CS583,Bing Liu,UIC,What do we mean by learning?,Given,a data set,D,a task,T,and,a performance measure,M,a computer system is said to,learn,from,D,to perform the task,T,if after learning the systems performance on,T,improves as measured by,M,.,In other words,the learned model helps the system to perform,T,better as,compared to no learning,.,11,CS583,Bing Liu,UIC,An example,Data,:Loan application data,Task,:Predict whether a loan should be approved or not.,Performance measure,:accuracy.,No learning,:classify all future applications(test data)to the majority class(i.e.,Yes,):,Accuracy=9/15=60%,.,We can do better than 60%with learning.,12,CS583,Bing Liu,UIC,Fundamental assumption of learning,Assumption:,The distribution of training examples is,identical,to the distribution of test examples(including future unseen examples).,In practice,this assumption is often violated to certain degree.,Strong violations will clearly result in poor classification accuracy.,To achieve good accuracy on the test data,training examples must be sufficiently representative of the test data,.,13,CS583,Bing Liu,UIC,Road Map,Basic concepts,Decision tree induction,Evaluation of classifiers,Rule induction,Classification using association rules,Nave Bayesian classification,Nave Bayes for text classification,Support vector machines,K-nearest neighbor,Ensemble methods:Bagging and Boosting,Summary,14,CS583,Bing Liu,UIC,Introduction,Decision tree learning is one of the most widely used techniques for classification.,Its classification accuracy is competitive with other methods,and,it is very efficient.,The classification model is a tree,called,decision tree,.,C4.5,by Ross Quinlan is perhaps the best known system.It can be downloaded from the Web.,15,CS583,Bing Liu,UIC,The loan data(reproduced),Approved or not,16,CS583,Bing Liu,UIC,A decision tree from the loan data,Decision nodes,and,leaf nodes(classes),17,CS583,Bing Liu,UIC,Use the decision tree,No,18,CS583,Bing Liu,UIC,Is the decision tree unique?,No,.Here is a simpler tree.,We want,smaller tree,and,accurate tree,.,Easy to understand and perform better.,Finding the best tree is NP-hard.,All current tree building algorithms are heuristic algorithms,19,CS583,Bing Liu,UIC,From a decision tree to a set of rules,A decision tree can be converted to a set of rules,Each path from the root to a leaf is a rule.,20,CS583,Bing Liu,UIC,Algorithm for decision tree learning,Basic algorithm(a greedy,divide-and-conquer,algorithm),Assume attributes are categorical now(continuous attributes can be handled too),Tree is constructed in a,top-down recursive manner,At start,all the training examples are at the root,Examples are partitioned recursively based on selected attributes,Attributes are selected on the basis of an impurity function(e.g.,information gain,),Conditions for stopping partitioning,All examples for a given node belong to the same class,There are no remaining attributes for further partitioning majority class is the leaf,There are no examples left,21,CS583,Bing Liu,UIC,Decision tree learning algorithm,22,CS583,Bing Liu,UIC,Choose an attribute to partition data,The,key,to building a decision tree-which attribute to choose in order to branch.,The objective is to reduce impurity or uncertainty in data as much as possible.,A subset of data is,pure,if all instances belong to the same class,.,The,heuristic,in C4.5 is to choose the attribute with the maximum,Information Gain,or,Gain Ratio,based on information theory.,23,CS583,Bing Liu,UIC,The loan data(reproduced),Approved or not,24,CS583,Bing Liu,UIC,Two possible roots,which is better?,Fig.(B)seems to be better.,25,CS583,Bing Liu,UIC,Information theory,Information theory,provides a mathematical basis for measuring the information content.,To understand the notion of information,think about it as providing the answer to a question,for example,whether a coin will come up heads.,If one already has a good guess about the answer,then the actual answer is less informative.,If one already knows that the coin is rigged so that it will come with heads with probability 0.99,then a message(advanced information)about the actual outcome of a flip is worth less than it would be for a honest coin(50-50).,26,CS583,Bing Liu,UIC,Information theory(cont),For a fair(honest)coin,you have no information,and you are willing to pay more(say in terms of$)for advanced information-less you know,the more valuable the information.,Information theory,uses this same intuition,but instead of measuring the value for information in dollars,it measures information contents in,bits,.,One bit of information is enough to answer a yes/no question about which one has no idea,such as the flip of a fair coin,27,CS583,Bing Liu,UIC,Information theory:Entropy measure,The entropy formula,Pr(,c,j,)is the probability of class,c,j,in data set,D,We use entropy as a,measure of impurity or disorder,of data set,D,.(Or,a measure of information in a tree),28,CS583,Bing Liu,UIC,Entropy measure:let us get a feeling,As the data become purer and purer,the entropy value becomes smaller and smaller.,This is useful to us!,29,CS583,Bing Liu,UIC,Information gain,Given a set of examples,D,we first compute its entropy:,If we make attribute,A,i,with v values,the root of the current tree,this will partition,D,into,v,subsets,D,1,D,2,D,v,.The expected entropy if,A,i,is used,as the current root:,30,CS583,Bing Liu,UIC,Information gain(cont),Information gained,by selecting attribute,A,i,to branch or to partition the data is,We choose the attribute with the highest gain to branch/split the current tree.,31,CS583,Bing Liu,UIC,An example,Own_house,is the best choice for the root.,32,CS583,Bing Liu,UIC,We build the final tree,We can use information gain ratio to evaluate the impurity as well(see the handout),33,CS583,Bing Liu,UIC,Handling continuous attributes,Handle continuous attribute by splitting into two intervals(can be more)at each node.,How to find the best threshold to divide?,Use information gain or gain ratio again,Sort all the values of an continuous attribute in increasing order,v,1,v,2,v,r,One possible threshold between two adjacent values,v,i,and,v,i+1,.Try all possible thresholds and find the one that maximizes the gain(or gain ratio).,34,CS583,Bing Liu,UIC,An example in a continuous space,35,CS583,Bing Liu,UIC,Avoid overfitting in classification,Overfitting,:A tree may overfit the training data,Good accuracy on training data but poor on test data,Symptoms:tree too deep and too many branches,some may reflect anomalies due to noise or outliers,Two approaches to avoid overfitting,Pre-pruning,:Halt tree construction early,Difficult to decide because we do not know what may happen subsequently if we keep growing the tree.,Post-pruning,:Remove branches or sub-trees from a“fully grown”tree.,This method is commonly used.C4.5 uses a statistical method to estimates the errors at each node for pruning.,A validation set may be used for pruning as well.,36,CS583,Bing Liu,UIC,An example,Likely to overfit the data,37,CS583,Bing Liu,UIC,Other issues in decision tree learning,From tree to rules,and rule pruning,Handling of miss values,Handing skewed distributions,Handling attributes and classes with different costs.,Attribute construction,Etc.,38,CS583,Bing Liu,UIC,Road Map,Basic concepts,Decision tree induction,Evaluation of classifiers,Rule induction,Classification using association rules,Nave Bayesian classification,Nave Bayes for text classification,Support vector machines,K-nearest neighbor,Ensemble methods:Bagging and Boosting,Summary,39,CS583,Bing Liu,UIC,Evaluating classification methods,Predictive accuracy,Efficiency,time to construct the model,time to use the model,Robustness,:handling noise and missing values,Scalability,:efficiency in disk-resident databases,Interpretability,:,understandable and insight provided by the model,Compactness of the model,:size of the tree,or the number of rules.,40,CS583,Bing Liu,UIC,Evaluation methods,Holdout set,:,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.,41,CS583,Bing Liu,UIC,Evaluation methods(cont),n-fold cross-validation,:T,he 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 commonly used.,This method is used when the available data is not large.,42,CS583,Bing Liu,UIC,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,43,CS583,Bing Liu,UIC,Evaluation methods(cont),Validation set,:,the available data is divided into three subsets,a training set,a validation set and,a test 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.,44,CS583,Bing Liu,UIC,Classification measures,Accuracy is only one measure(error=1-accuracy).,Accuracy is not suitable in some applications,.,In text mining,we may only be interested in the documents of a particular topic,which are only a small portion of a big document collection.,In classification involving skewed or highly imbalanced data,e.g.,network intrusion and financial fraud detections,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,.,45,CS583,Bing Liu,UIC,Precision,and,recall,measures,Used in information retrieval and text classification.,We use a confusion matrix to introduce them.,46,CS583,Bing Liu,UIC,Precision,and,recall,measures(cont),Precision,p,is the number of,correctly classified positive examples,divided by the total number of examples that are classified as positive.,Recall,r,is the number of,correctly classified positive examples,divided by the total number of actual positive examples in the test set.,47,CS583,Bing Liu,UIC,An example,This confusion matrix gives,precision,p,=100%and,recall,r,=1%,because we only classified one positive example correctly and no negative examples wrongly.,Note:,precision and recall only measure classification on the positive class.,48,CS583,Bing Liu,UIC,F,1,-value(also called F,1,-score),It is hard to compare two classifiers using two measures.F,1,score combines precision and recall into one measure,The harmonic mean of two numbers tends to be closer to the smaller of the two.,For F,1,-value to be large,both,p,and,r,much be large.,49,CS583,Bing Liu,UIC,Another evaluation method,:Scoring and ranking,Scoring,is related to classification.,We are interested in a single class(,positive class,),e.g.,buyers class in a marketing database.,Instead of assigning each test instance a definite class,scoring assigns a probability estimate(PE)to indicate the likelihood that the example belongs to the positive class.,50,CS583,Bing Liu,UIC,Ranking and lift analysis,After each example is given a PE score,we can rank all examples according to their PEs.,We then divide the data into n(say 10)bins.A lift curve can be drawn according how many positive examples are in each bin.This is called,lift analysis,.,Classification systems can be used for scoring.Need to produce a probability estimate.,E.g.,in decision trees,we can use the confidence value at each leaf node as the score.,51,CS583,Bing Liu,UIC,A