《数据仓库与数据挖掘》第9章603.pptx

《《数据仓库与数据挖掘》第9章603.pptx》由会员分享，可在线阅读，更多相关《《数据仓库与数据挖掘》第9章603.pptx（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第7 7章章:分类和预测分类和预测nWhat is classification?What is prediction?nIssues regarding classification and predictionnClassification by decision tree inductionnBayesian ClassificationnClassification by Neural NetworksnClassification by Support Vector Machines(SVM)nClassification based on concepts from associ

2、ation rule miningnOther Classification MethodsnPredictionnClassification accuracynSummary2023/3/131Data Mining:Concepts and TechniquesnClassification:npredicts categorical class labels(discrete or nominal)nclassifies data(constructs a model)based on the training set and the values(class labels)in a

3、classifying attribute and uses it in classifying new datanPrediction:nmodels continuous-valued functions,i.e.,predicts unknown or missing values nTypical Applicationsncredit approvalntarget marketingnmedical diagnosisntreatment effectiveness analysisClassification vs.Prediction2023/3/132Data Mining:

4、Concepts and TechniquesClassificationA Two-Step Process nModel construction:describing a set of predetermined classesnEach tuple/sample is assumed to belong to a predefined class,as determined by the class label attributenThe set of tuples used for model construction is training setnThe model is rep

5、resented as classification rules,decision trees,or mathematical formulaenModel usage:for classifying future or unknown objectsnEstimate accuracy of the modelnThe known label of test sample is compared with the classified result from the modelnAccuracy rate is the percentage of test set samples that

6、are correctly classified by the modelnTest set is independent of training set,otherwise over-fitting will occurnIf the accuracy is acceptable,use the model to classify data tuples whose class labels are not known2023/3/133Data Mining:Concepts and TechniquesClassification Process(1):Model Constructio

7、nTrainingDataClassificationAlgorithmsIF rank=professorOR years 6THEN tenured=yes Classifier(Model)2023/3/134Data Mining:Concepts and TechniquesClassification Process(2):Use the Model in PredictionClassifierTestingDataUnseen Data(Jeff,Professor,4)Tenured?2023/3/135Data Mining:Concepts and TechniquesS

8、upervised vs.Unsupervised LearningnSupervised learning(classification)nSupervision:The training data(observations,measurements,etc.)are accompanied by labels indicating the class of the observationsnNew data is classified based on the training setnUnsupervised learning(clustering)nThe class labels o

9、f training data is unknownnGiven a set of measurements,observations,etc.with the aim of establishing the existence of classes or clusters in the data2023/3/136Data Mining:Concepts and Techniques第第7 7章章:分类和预测分类和预测nWhat is classification?What is prediction?nIssues regarding classification and predicti

10、onnClassification by decision tree inductionnBayesian ClassificationnClassification by Neural NetworksnClassification by Support Vector Machines(SVM)nClassification based on concepts from association rule miningnOther Classification MethodsnPredictionnClassification accuracynSummary2023/3/137Data Mi

11、ning:Concepts and TechniquesIssues Regarding Classification and Prediction(1):Data PreparationnData cleaningnPreprocess data in order to reduce noise and handle missing valuesnRelevance analysis(feature selection)nRemove the irrelevant or redundant attributesnData transformationnGeneralize and/or no

12、rmalize data2023/3/138Data Mining:Concepts and TechniquesIssues regarding classification and prediction(2):Evaluating Classification MethodsnPredictive accuracynSpeed and scalabilityntime to construct the modelntime to use the modelnRobustnessnhandling noise and missing valuesnScalabilitynefficiency

13、 in disk-resident databases nInterpretability:nunderstanding and insight provided by the modelnGoodness of rulesndecision tree sizencompactness of classification rules2023/3/139Data Mining:Concepts and Techniques第第7 7章章:分类和预测分类和预测nWhat is classification?What is prediction?nIssues regarding classific

14、ation and predictionnClassification by decision tree inductionnBayesian ClassificationnClassification by Neural NetworksnClassification by Support Vector Machines(SVM)nClassification based on concepts from association rule miningnOther Classification MethodsnPredictionnClassification accuracynSummar

15、y2023/3/1310Data Mining:Concepts and TechniquesTraining DatasetThis follows an example from Quinlans ID32023/3/1311Data Mining:Concepts and TechniquesOutput:A Decision Tree for“buys_computer”age?overcaststudent?credit rating?noyesfairexcellent40nonoyesyesyes30.402023/3/1312Data Mining:Concepts and T

16、echniquesAlgorithm for Decision Tree InductionnBasic algorithm(a greedy algorithm)nTree is constructed in a top-down recursive divide-and-conquer mannernAt start,all the training examples are at the rootnAttributes are categorical(if continuous-valued,they are discretized in advance)nExamples are pa

17、rtitioned recursively based on selected attributesnTest attributes are selected on the basis of a heuristic or statistical measure(e.g.,information gain)nConditions for stopping partitioningnAll samples for a given node belong to the same classnThere are no remaining attributes for further partition

18、ing majority voting is employed for classifying the leafnThere are no samples left2023/3/1313Data Mining:Concepts and TechniquesAttribute Selection Measure:Information Gain(ID3/C4.5)nSelect the attribute with the highest information gainnS contains si tuples of class Ci for i=1,m ninformation measur

19、es info required to classify any arbitrary tuplenentropy of attribute A with values a1,a2,avninformation gained by branching on attribute A2023/3/1314Data Mining:Concepts and TechniquesAttribute Selection by Information Gain ComputationgClass P:buys_computer=“yes”gClass N:buys_computer=“no”gI(p,n)=I

20、(9,5)=0.940gCompute the entropy for age:means“age=30”has 5 out of 14 samples,with 2 yeses and 3 nos.HenceSimilarly,2023/3/1315Data Mining:Concepts and TechniquesOther Attribute Selection MeasuresnGini index(CART,IBM IntelligentMiner)nAll attributes are assumed continuous-valuednAssume there exist se

21、veral possible split values for each attributenMay need other tools,such as clustering,to get the possible split valuesnCan be modified for categorical attributes2023/3/1316Data Mining:Concepts and TechniquesGini Index(IBM IntelligentMiner)nIf a data set T contains examples from n classes,gini index

22、,gini(T)is defined as where pj is the relative frequency of class j in T.nIf a data set T is split into two subsets T1 and T2 with sizes N1 and N2 respectively,the gini index of the split data contains examples from n classes,the gini index gini(T)is defined asnThe attribute provides the smallest gi

23、nisplit(T)is chosen to split the node(need to enumerate all possible splitting points for each attribute).2023/3/1317Data Mining:Concepts and TechniquesExtracting Classification Rules from TreesnRepresent the knowledge in the form of IF-THEN rulesnOne rule is created for each path from the root to a

24、 leafnEach attribute-value pair along a path forms a conjunctionnThe leaf node holds the class predictionnRules are easier for humans to understandnExampleIF age=“=30”AND student=“no”THEN buys_computer=“no”IF age=“40”AND credit_rating=“excellent”THEN buys_computer=“yes”IF age=“=30”AND credit_rating=

25、“fair”THEN buys_computer=“no”2023/3/1318Data Mining:Concepts and TechniquesAvoid Overfitting in ClassificationnOverfitting:An induced tree may overfit the training data nToo many branches,some may reflect anomalies due to noise or outliersnPoor accuracy for unseen samplesnTwo approaches to avoid ove

26、rfitting nPrepruning:Halt tree construction earlydo not split a node if this would result in the goodness measure falling below a thresholdnDifficult to choose an appropriate thresholdnPostpruning:Remove branches from a“fully grown”treeget a sequence of progressively pruned treesnUse a set of data d

27、ifferent from the training data to decide which is the“best pruned tree”2023/3/1319Data Mining:Concepts and TechniquesApproaches to Determine the Final Tree SizenSeparate training(2/3)and testing(1/3)setsnUse cross validation,e.g.,10-fold cross validationnUse all the data for trainingnbut apply a st

28、atistical test(e.g.,chi-square)to estimate whether expanding or pruning a node may improve the entire distributionnUse minimum description length(MDL)principlenhalting growth of the tree when the encoding is minimized2023/3/1320Data Mining:Concepts and TechniquesEnhancements to basic decision tree i

29、nductionnAllow for continuous-valued attributesnDynamically define new discrete-valued attributes that partition the continuous attribute value into a discrete set of intervalsnHandle missing attribute valuesnAssign the most common value of the attributenAssign probability to each of the possible va

30、luesnAttribute constructionnCreate new attributes based on existing ones that are sparsely representednThis reduces fragmentation,repetition,and replication2023/3/1321Data Mining:Concepts and TechniquesClassification in Large DatabasesnClassificationa classical problem extensively studied by statist

31、icians and machine learning researchersnScalability:Classifying data sets with millions of examples and hundreds of attributes with reasonable speednWhy decision tree induction in data mining?nrelatively faster learning speed(than other classification methods)nconvertible to simple and easy to under

32、stand classification rulesncan use SQL queries for accessing databasesncomparable classification accuracy with other methods2023/3/1322Data Mining:Concepts and TechniquesScalable Decision Tree Induction Methods in Data Mining StudiesnSLIQ(EDBT96 Mehta et al.)nbuilds an index for each attribute and o

33、nly class list and the current attribute list reside in memorynSPRINT(VLDB96 J.Shafer et al.)nconstructs an attribute list data structure nPUBLIC(VLDB98 Rastogi&Shim)nintegrates tree splitting and tree pruning:stop growing the tree earliernRainForest (VLDB98 Gehrke,Ramakrishnan&Ganti)nseparates the

34、scalability aspects from the criteria that determine the quality of the treenbuilds an AVC-list(attribute,value,class label)2023/3/1323Data Mining:Concepts and TechniquesData Cube-Based Decision-Tree InductionnIntegration of generalization with decision-tree induction(Kamber et al97).nClassification

35、 at primitive concept levelsnE.g.,precise temperature,humidity,outlook,etc.nLow-level concepts,scattered classes,bushy classification-treesnSemantic interpretation problems.nCube-based multi-level classificationnRelevance analysis at multi-levels.nInformation-gain analysis with dimension+level.2023/

36、3/1324Data Mining:Concepts and TechniquesPresentation of Classification Results2023/3/1325Data Mining:Concepts and TechniquesVisualization of a Decision Tree in SGI/MineSet 3.02023/3/1326Data Mining:Concepts and TechniquesInteractive Visual Mining by Perception-Based Classification(PBC)2023/3/1327Da

37、ta Mining:Concepts and Techniques第第7 7章章:分类和预测分类和预测nWhat is classification?What is prediction?nIssues regarding classification and predictionnClassification by decision tree inductionnBayesian ClassificationnClassification by Neural NetworksnClassification by Support Vector Machines(SVM)nClassificat

38、ion based on concepts from association rule miningnOther Classification MethodsnPredictionnClassification accuracynSummary2023/3/1328Data Mining:Concepts and TechniquesBayesian Classification:Why?nProbabilistic learning:Calculate explicit probabilities for hypothesis,among the most practical approac

39、hes to certain types of learning problemsnIncremental:Each training example can incrementally increase/decrease the probability that a hypothesis is correct.Prior knowledge can be combined with observed data.nProbabilistic prediction:Predict multiple hypotheses,weighted by their probabilitiesnStanda

40、rd:Even when Bayesian methods are computationally intractable,they can provide a standard of optimal decision making against which other methods can be measured2023/3/1329Data Mining:Concepts and TechniquesBayesian Theorem:BasicsnLet X be a data sample whose class label is unknownnLet H be a hypothe

41、sis that X belongs to class C nFor classification problems,determine P(H/X):the probability that the hypothesis holds given the observed data sample XnP(H):prior probability of hypothesis H(i.e.the initial probability before we observe any data,reflects the background knowledge)nP(X):probability tha

42、t sample data is observednP(X|H):probability of observing the sample X,given that the hypothesis holds2023/3/1330Data Mining:Concepts and TechniquesBayesian TheoremnGiven training data X,posteriori probability of a hypothesis H,P(H|X)follows the Bayes theoremnInformally,this can be written as poster

43、ior=likelihood x prior/evidencenMAP(maximum posteriori)hypothesisnPractical difficulty:require initial knowledge of many probabilities,significant computational cost2023/3/1331Data Mining:Concepts and TechniquesNave Bayes Classifier nA simplified assumption:attributes are conditionally independent:n

44、The product of occurrence of say 2 elements x1 and x2,given the current class is C,is the product of the probabilities of each element taken separately,given the same class P(y1,y2,C)=P(y1,C)*P(y2,C)nNo dependence relation between attributes nGreatly reduces the computation cost,only count the class

45、 distribution.nOnce the probability P(X|Ci)is known,assign X to the class with maximum P(X|Ci)*P(Ci)2023/3/1332Data Mining:Concepts and TechniquesTraining datasetClass:C1:buys_computer=yesC2:buys_computer=noData sample X=(age=30,Income=medium,Student=yesCredit_rating=Fair)2023/3/1333Data Mining:Conc

46、epts and TechniquesNave Bayesian Classifier:ExamplenCompute P(X/Ci)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.

47、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 credit approval(Yes/No)nTemp,Humidity-Rain(Yes/No)ClassificationMathematically2023/3/1340Data Mining:Concepts and TechniquesLinear Classific

48、ationnBinary Classification problemnThe data above the red line belongs to class xnThe data below red line belongs to class onExamples SVM,Perceptron,Probabilistic Classifiersxxxxxxxxxxooooooooooooo2023/3/1341Data Mining:Concepts and TechniquesDiscriminative ClassifiersnAdvantagesnprediction accurac

49、y is generally high n(as compared to Bayesian methods in general)nrobust,works when training examples contain errorsnfast evaluation of the learned target functionn(Bayesian networks are normally slow)nCriticismnlong training timendifficult to understand the learned function(weights)n(Bayesian netwo

50、rks can be used easily for pattern discovery)nnot easy to incorporate domain knowledgen(easy in the form of priors on the data or distributions)2023/3/1342Data Mining:Concepts and TechniquesNeural NetworksnAnalogy to Biological Systems(Indeed a great example of a good learning system)nMassive Parall