《数据挖掘导论第四章ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据挖掘导论第四章ppt课件.ppt（88页珍藏版）》请在三一办公上搜索。
1、数据挖掘导论,Pang-ning Tan, Michael Stieinbach, and Vipin Kumar著Pearson Education LTD.范明 等译人民邮电出版社,第4章分类：基本概念、决策树与模型评估,引言: 预备知识, 解决分类问题的一般方法 决策树归纳 模型的过分拟合 评估分类器的性能,引言,2022年12月26日星期一,数据挖掘导论,4,分类:定义,Given a collection of records (training set )Each record contains a set of attributes, one of the attributes
2、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
3、sets, with training set used to build the model and test set used to validate it,2022年12月26日星期一,数据挖掘导论,5,分类:解释,2022年12月26日星期一,数据挖掘导论,6,分类任务的例子,肿瘤：Predicting tumor cells as benign or malignant信用卡交易：Classifying credit card transactions as legitimate or fraudulent蛋白质结构：Classifying secondary structures
4、of protein as alpha-helix, beta-sheet, or random coil新闻：Categorizing news stories as finance, weather, entertainment, sports, etc,2022年12月26日星期一,数据挖掘导论,7,分类:技术,Decision Tree based MethodsRule-based MethodsMemory based reasoningNeural NetworksNave Bayes and Bayesian Belief NetworksSupport Vector Mach
5、ines,4.3 决策树归纳,2022年12月26日星期一,数据挖掘导论,9,2022年12月26日星期一,数据挖掘导论,10,决策树: 例子,2022年12月26日星期一,数据挖掘导论,11,决策树,树中包含三种结点 根结点(root node): 没有入边, 有零条或多条出边内部结点(internal node): 恰有一条入边和两条或多条出边叶结点(leaf node)或终端结点(terminal node): 恰有一条入边，但没有出边,2022年12月26日星期一,数据挖掘导论,12,决策树分类任务: 应用模型,2022年12月26日星期一,数据挖掘导论,13,决策树: 使用模型,20
6、22年12月26日星期一,数据挖掘导论,14,决策树: 使用模型,2022年12月26日星期一,数据挖掘导论,15,决策树: 使用模型,2022年12月26日星期一,数据挖掘导论,16,决策树: 使用模型,2022年12月26日星期一,数据挖掘导论,17,决策树: 使用模型,2022年12月26日星期一,数据挖掘导论,18,决策树: 使用模型,2022年12月26日星期一,数据挖掘导论,19,决策树分类任务:学习模型,2022年12月26日星期一,数据挖掘导论,20,决策树归纳,Many Algorithms:Hunts Algorithm (one of the earliest)CARTI
7、D3, C4.5SLIQ, SPRINT,2022年12月26日星期一,数据挖掘导论,21,Hunt算法的一般结构,Let Dt be the set of training records that reach a node tGeneral Procedure:If Dt contains records that belong the same class yt, then t is a leaf node labeled as ytIf Dt is an empty set, then t is a leaf node labeled by the default class, ydI
8、f Dt contains records that belong to more than one class, use an attribute test to split the data into smaller subsets. Recursively apply the procedure to each subset.,2022年12月26日星期一,数据挖掘导论,22,Hunt算法: 例,2022年12月26日星期一,数据挖掘导论,23,决策树归纳,Greedy strategy.Split the records based on an attribute test that
9、optimizes certain criterion.IssuesDetermine how to split the recordsHow to specify the attribute test condition?How to determine the best split?Determine when to stop splittingDiscuss above three issues in details,2022年12月26日星期一,数据挖掘导论,24,如何指定属性测试条件,Depends on attribute typesNominalOrdinalContinuous
10、Depends on number of ways to split2-way splitMulti-way split,2022年12月26日星期一,数据挖掘导论,25,划分: 标称属性,Multi-way split: Use as many partitions as distinct values. Binary split: Divides values into two subsets. Need to find optimal partition from all possible partitions.,2022年12月26日星期一,数据挖掘导论,26,划分: 序数属性,Mul
11、ti-way split: Use as many partitions as distinct values. Binary split: Divides values into two subsets. Need to find optimal partition from all possible partitions.What about this split?,2022年12月26日星期一,数据挖掘导论,27,划分: 连续属性,Different ways of handlingDiscretization to form an ordinal categorical attribu
12、teStatic discretize once at the beginningCan be treated as ordinal attributeDynamic ranges can be found by equal interval bucketing, equal frequency bucketing (percentiles), or clustering.Binary Decision: (A v) or (A v) consider all possible splits and finds the best cut can be more compute intensiv
13、e,2022年12月26日星期一,数据挖掘导论,28,划分: 连续属性(续),2022年12月26日星期一,数据挖掘导论,29,如何确定最佳划分,Before Splitting: 10 records of class 0, 10 records of class 1,Which test condition is the best?,Own,Car?,C0: 6,C1: 4,C0: 4,C1: 6,C0: 1,C1: 3,C0: 8,C1: 0,C0: 1,C1: 7,Car,Type?,Yes,No,Family,Sports,Luxury,2022年12月26日星期一,数据挖掘导论,3
14、0,如何确定最佳划分(续),Greedy approach: Nodes with homogeneous class distribution are preferredNeed a measure of node impurity,2022年12月26日星期一,数据挖掘导论,31,结点的不纯度,结点的不纯度设有c个类, t是结点, p(i|t)表示给定结点t中属于类i的记录所占的比例 Entropy Gini IndexMisclassification error,2022年12月26日星期一,数据挖掘导论,32,标准比较,不同的不纯性度量是一致的 对于二类问题,2022年12月26日星
15、期一,数据挖掘导论,33,划分的增益,划分的增益设结点parent上有N个记录设结点parent被划分成k部分, 即parent有k个子女v1,vk设I(vj)是结点vj的不纯度, 则划分的增益为其中, N(vj)是结点vj的记录数, I(.)可以是entropy(.), Gini(.), error(.)等 反映结点parent划分为v1,vk后不纯度的降低越大，越有利于分类信息增益(information gain)当不纯度用entropy度量时，称为信息增益info(Gain),2022年12月26日星期一,数据挖掘导论,34,如何确定最佳划分(续),基本思想如果采用二元划分, 则对非二
16、元属性确定最佳划分对于分类和序数属性, 需要考虑所有可能对于连续属性, 如果不离散化, 需要采用二元划分如何确定最佳划分点, 见后面的例子属性最佳划分是不纯度最低的划分对每个属性的最佳划分, 计算划分增益结点的最佳划分是划分增益最大的属性(最佳)划分,2022年12月26日星期一,数据挖掘导论,35,连续属性的最佳划分点,确定最佳划分点把属性值由小到大排序v(1) v(2) v(k)(取相邻值的中点为划分点:如果v(i) v(i+1), 则取(v(i) + v(i+1)/2为划分点评估每个划分点，选取不纯度最低的划分,2022年12月26日星期一,数据挖掘导论,36,连续属性的最佳划分点(续)
17、,确定连续属性的最佳划分点的计算开销可能很大需要计算k1个可能的划分点产生的划分的不纯度减少待考察的划分点方法如果v(i) v(i+1), 但是v(i)和v(i+1),是同类元组的取值, 则最佳划分点一定不在v(i)和v(i+1)之间.,2022年12月26日星期一,数据挖掘导论,37,增益率,熵和Gini指标等不纯性度量往往有利于具有大量不同值的属性 一个极端的例子: 顾客ID（如身份证号）导致最纯的划分，但无助于分类解决方案使用二元划分使用增益率,2022年12月26日星期一,数据挖掘导论,38,增益率(续),增益率是划分增益与划分信息的比GainRatio=/SplitInfo其中划分信
18、息SplitInfo划分信息又称划分的熵用来克服信息增益的缺点C4.5采用增益率,2022年12月26日星期一,数据挖掘导论,39,停止条件,Stop expanding a node when all the records belong to the same classStop expanding a node when all the records have similar attribute valuesStop expanding a node when there is no attribute availableEarly termination (to be discuss
19、ed later),2022年12月26日星期一,数据挖掘导论,40,其他问题：缺失属性值,如何让处理缺失属性值Missing values affect decision tree construction in three different ways:Affects how impurity measures are computedAffects how to distribute instance with missing value to child nodesAffects how a test instance with missing value is classified,
20、2022年12月26日星期一,数据挖掘导论,41,缺失属性值: 计算不纯度量,2022年12月26日星期一,数据挖掘导论,42,缺失属性值:实例分布,Probability that Refund=Yes is 3/9Probability that Refund=No is 6/9Assign record to the left child with weight = 3/9 and to the right child with weight = 6/9,2022年12月26日星期一,数据挖掘导论,43,缺失属性值:实例分类,New record:,Probability that Ma
21、rital Status = Married is 3.67/6.67Probability that Marital Status =Single,Divorced is 3/6.67,4.3 决策树归纳,2022年12月26日星期一,数据挖掘导论,45,决策树归纳算法,createdNode()为决策树建立新结点决策树的结点或者是一个测试条件, 记作node.test_cond; 或者是一个类标号, 记作node.labe find_best_split()确定应当选择哪个属性作为划分训练记录的测试条件计算 或GainRatioClassify(t)为叶结点t确定类标号 TreeGrowt
22、h(E, F)E: 当前数据集, F:当前属性集,2022年12月26日星期一,数据挖掘导论,46,决策树归纳算法(续),算法4.1 决策树归纳算法的框架TreeGrowth(E, F) 1：if stopping_cond(E, F) = true then 2： leaf = createNode() 3： leaf.label = Classify(E) 4： return leaf 5：else 6： root = createNode() 7： root.test_cond = find_best_split(E, F) 8： 令V = v | v是root.test_cond的一个
23、可能的输出 9： for 每个vV do10： Ev = e | root.test_cond (e) = v 并且e E11： child = TreeGrowth(Ev, F)12： 将child作为root的派生结点添加到树中, 并将边(root child)标记为v13： end for14：end if15：return root,2022年12月26日星期一,数据挖掘导论,47,决策树:例,Web Robot/Crawler Detection建立分类模型, 区分人类用户与Web机器人有Web服务器日志导出Web会话记录Web会话记录包含12个属性（见下页）数据集包含2916个记录
24、Web机器人（类1）和人类用户（类2）会话的个数相等10%的数据用于训练90%的数据用于检验,2022年12月26日星期一,数据挖掘导论,48,决策树:例(续),由Web服务器日志 导出的Web会话记录,2022年12月26日星期一,数据挖掘导论,49,决策树:例(续),决策树,2022年12月26日星期一,数据挖掘导论,50,决策树:例(续),从以下4个方面区分出Web机器人和人类用户：Web机器人的访问倾向于宽而浅，而人类用户访问比较集中（窄而深）与人类用户不同，Web机器人很少访问与Web文档相关的图片页Web机器人的会话的长度趋于较长，包含了大量请求页面Web机器人更可能对相同的文档发
25、出重复的请求，因为人类用户访问的网页常常会被浏览器保存,2022年12月26日星期一,数据挖掘导论,51,决策树归纳的特点,一般特点构建分类模型的非参数方法不要求任何先验假设, 不假定类和其他属性服从一定的概率分布贪心的、自顶向下的递归划分策略建立决策树 找到最佳的决策树是NP完全问题 决策边界是直线(平面), 平行于“坐标轴”,2022年12月26日星期一,数据挖掘导论,52,决策树归纳的特点(续),优点快速建立模型, 快速分类如果数据集可以放在内存，建立决策树很快分类时间复杂度：最坏情况下为O(w)，其中w是树的最大深度 分类准确率高特别适合包含固定属性（维度不高）的记录数据决策树相对容易
26、解释小型决策树容易解释对于噪声的干扰具有相当好的鲁棒性 可以采用避免过拟合的方法不受冗余属性、不相关属性影响自动选择最好的属性进行划分,2022年12月26日星期一,数据挖掘导论,53,决策树归纳的特点(续),存在问题数据碎片（data fragmentation）问题 在叶结点, 记录可能太少, 对于叶结点代表的类, 不能做出具有统计意义的判决子树可能在决策树中重复多次 使得决策树过于复杂, 难以解释,2022年12月26日星期一,数据挖掘导论,54,决策树归纳的特点(续),其他问题平行于坐标轴的边界限制了决策树的能力一个需要斜边界的例子使用斜边界x + y 1更好,4.4 模型的过分拟合,
27、2022年12月26日星期一,数据挖掘导论,56,概述,训练误差 vs 泛化误差训练误差(training error) 又称再代入误差(resubstitution error), 表现误差(apparent error)模型在训练集上误分类样本所占的比例泛化误差(generalization error)模型在未知记录上的期望误差 通常在检验集上估计，因此又称检验误差欠拟合 vs 过拟合欠拟合(underfitting): 训练和检验误差都很大 过拟合(overfitting): 训练误差小，但检验误差大,2022年12月26日星期一,数据挖掘导论,57,概述(续),训练误差和检验误差与模
28、型复杂度的关系,2022年12月26日星期一,数据挖掘导论,58,噪声导致的过拟合,哺乳动物的分类问题 训练集中，蝙蝠和鲸被错误地标记为非哺乳类动物这类错误可以视为噪声,2022年12月26日星期一,数据挖掘导论,59,噪声导致的过拟合(续),检验数据集,2022年12月26日星期一,数据挖掘导论,60,噪声导致的过拟合(续),基于含噪声训练数据建立的决策树左: 训练误差为0, 但在检验集上, 人和海豚都被误分类为非哺乳类动物. 针鼹是个例外, 其检验记录中的类标号与训练集中相似的记录的类标号相反 右: 训练误差20%, 检验误差10%,2022年12月26日星期一,数据挖掘导论,61,缺乏代
29、表性样本导致的过分拟合,训练样本太少缺乏代表性样本学习算法仍然继续细化模型 过拟合例: 一个小训练集,2022年12月26日星期一,数据挖掘导论,62,缺乏代表性样本(续),基于小样本的决策树人、大象和海豚都被误分类,2022年12月26日星期一,数据挖掘导论,63,过拟合,过拟合导致具有不必要的复杂度的决策树需要对决策树剪枝, 降低复杂度如何评估一个分支是否需要剪去-估计泛化误差在训练集上估计使用再代入估计 结合模型复杂度 估计统计上界 在确认集(validation set)上估计确认集是训练集的一部分，不是检验集,2022年12月26日星期一,数据挖掘导论,64,Occam剃刀,Occa
30、ms RazorGiven two models of similar generalization errors, one should prefer the simpler model over the more complex modelEinsteinEverything should be made as simple as possible, but not simpler.,2022年12月26日星期一,数据挖掘导论,65,估计泛化误差,使用再代入误差:再代入误差就是训练误差假设训练数据集可以很好地代表整体数据 提供对泛化误差的乐观估计, 一般很难剪枝,2022年12月26日星期
31、一,数据挖掘导论,66,估计泛化误差(续),结合模型复杂度 悲观误差评估 最小描述长度悲观误差评估用训练误差与模型复杂度罚项的和估计泛化误差eg(T)其中，n(t)是结点t分类的训练记录数e(t)是被误分类的记录数k是决策树的叶结点数e(T)决策树的总训练误差Nt是训练记录数(ti)是每个结点ti对应的罚项，(T)是树的罚项（结点罚项和）,2022年12月26日星期一,数据挖掘导论,67,悲观误差评估: 例,例：24个记录，TL有7个树叶，TR有4个树叶取(ti)=0.5意味对于二路划分，(ti)=0.5意味只要减少一个错误就可以划分一个结点,2022年12月26日星期一,数据挖掘导论,68,
32、最小描述长度,最小描述长度（Minimum Description Length, MDL）原则Cost(Model,Data) = Cost(Data|Model) + Cost(Model)Cost is the number of bits needed for encoding.Search for the least costly model.Cost(Data|Model) encodes the misclassification errors.Cost(Model) uses node encoding (number of children) plus splitting c
33、ondition encoding,2022年12月26日星期一,数据挖掘导论,69,使用确认集,训练数据集分为两个较小的子集，一个子集用于训练，而另一个称作确认集，用于估计泛化误差典型的做法三分之二的训练集来建立模型三分之一用作误差估计 优点：简单，较好地估计泛化误差缺点：减少了用于训练的记录,2022年12月26日星期一,数据挖掘导论,70,处理过拟合: 剪枝,Pre-Pruning (Early Stopping Rule)Stop the algorithm before it becomes a fully-grown treeTypical stopping conditions
34、for a node:Stop if all instances belong to the same classStop if all the attribute values are the sameMore restrictive conditions:Stop if number of instances is less than some user-specified thresholdStop if class distribution of instances are independent of the available features (e.g., using 2 tes
35、t)Stop if expanding the current node does not improve impurity measures (e.g., Gini or information gain).,2022年12月26日星期一,数据挖掘导论,71,处理过拟合: 剪枝,Post-pruningGrow decision tree to its entiretyTrim the nodes of the decision tree in a bottom-up fashionIf generalization error improves after trimming, replac
36、e sub-tree by a leaf node.Class label of leaf node is determined from majority class of instances in the sub-treeCan use MDL for post-pruning,2022年12月26日星期一,数据挖掘导论,72,后剪枝: 例,Training Error (Before splitting) = 10/30Pessimistic error = (10 + 0.5)/30 = 10.5/30Training Error (After splitting) = 9/30Pes
37、simistic error (After splitting)= (9 + 4 0.5)/30 = 11/30PRUNE!,2022年12月26日星期一,数据挖掘导论,73,后剪枝: 例,Web机器人检测决策树的后剪枝,2022年12月26日星期一,数据挖掘导论,74,评估度量,Focus on the predictive capability of a modelRather than how fast it takes to classify or build models, scalability, etc.Accuracy：Most widely-used metric 被正确分类
38、样本所占的比例Confusion Matrix(二类问题),a: TP (true positive)b: FN (false negative)c: FP (false positive)d: TN (true negative),2022年12月26日星期一,数据挖掘导论,75,分类准确率的局限性,Consider a 2-class problemNumber of Class 0 examples = 9900Number of Class 1 examples = 100If a model predicts everything to be class 0, its accurac
39、y is 9900/10000 = 99 %Accuracy is misleading because model does not detect any class 1 exampleWill discuss in the next chapter,2022年12月26日星期一,数据挖掘导论,76,评估方法,保持（Holdout）方法 2/3 用于训练, 1/3用于检验局限性用于训练的被标记样本较少 模型可能高度依赖于训练集和检验集的构成 训练集越小, 模型的方差越大; 如果训练集太大, 根据用较小的检验集估计的准确率又不太可靠 随机二次抽样（random subsampling）重复保持
40、方法k次模型准确率,2022年12月26日星期一,数据挖掘导论,77,评估方法(续),交叉验证（cross-validation） k-fold cross-validationPartition data into k disjoint subsetsk-fold: train on k1 partitions, test on the remaining oneThis procedure is repeated k times, each partition is used for testing exactly onceLeave-one-out: k=nStratified k-fo
41、ld cross-validationThe class distribution of samples in each fold is approximatly the same as in the initial dataStratified 10-fold cross-validation is recommendedRelatively low bias an variance,2022年12月26日星期一,数据挖掘导论,78,评估方法(续),自助法（bootstrap）采用有放回抽样得到自助样本, 作为训练集 自助样本大约包含原始数据中63.2%的记录 一个记录被抽取的概率是1 (1
42、 1/N)N1 e1 = 0.632未抽中的样本作为检验集 抽样过程重复b次，产生b个自助样本 计算分类准确率的.632自助法 其中, i是第i个分类器在检验集上的分类准确率, accs是第i个分类器在原数据集上的分类准确率,比较分类器的性能,2022年12月26日星期一,数据挖掘导论,80,检验的显著性,Given two models:Model M1: accuracy = 85%, tested on 30 instancesModel M2: accuracy = 75%, tested on 5000 instancesCan we say M1 is better than M2
43、?How much confidence can we place on accuracy of M1 and M2?Can the difference in performance measure be explained as a result of random fluctuations in the test set?,2022年12月26日星期一,数据挖掘导论,81,准确率的置信区间,Prediction can be regarded as a Bernoulli trialA Bernoulli trial has 2 possible outcomesPossible out
44、comes for prediction: correct or wrongCollection of Bernoulli trials has a Binomial distribution: x Bin(N, p) x: number of correct predictions e.g: Toss a fair coin 50 times, how many heads would turn up? Expected number of heads = Np = 50 0.5 = 25Given x (# of correct predictions) or equivalently,
45、acc=x/N, and N (# of test instances),Can we predict p (true accuracy of model)?,2022年12月26日星期一,数据挖掘导论,82,准确率的置信区间,For large test sets (N 30), acc has a normal distribution with mean p and variance p(1p)/NConfidence Interval for p:,Area = 1 - ,Z/2,Z1- /2,2022年12月26日星期一,数据挖掘导论,83,准确率的置信区间:例,Consider a
46、 model that produces an accuracy of 80% when evaluated on 100 test instances:N=100, acc = 0.8Let 1 = 0.95 (95% confidence)From probability table, Z/2=1.96,2022年12月26日星期一,数据挖掘导论,84,比较两个模型的性能,Given two models, say M1 and M2, which is better?M1 is tested on D1 (size=n1), found error rate = e1M2 is test
47、ed on D2 (size=n2), found error rate = e2Assume D1 and D2 are independentIf n1 and n2 are sufficiently large, thenApproximate:,2022年12月26日星期一,数据挖掘导论,85,比较两个模型的性能,To test if performance difference is statistically significant, let d = e1 e2d N(dt,t) where dt is the true differenceSince D1 and D2 are
48、independent, their variance adds up: At (1-) confidence level,2022年12月26日星期一,数据挖掘导论,86,比较两个模型的性能:例,Given: M1: n1 = 30, e2 = 0.15 M2: n2 = 5000, e2 = 0.25d = |e2 e2| = 0.1 (2-sided test)At 95% confidence level, Z/2=1.96= Interval contains 0 = difference may not be statistically significant,2022年12月26
49、日星期一,数据挖掘导论,87,比较两个算法的性能,Each learning algorithm may produce k models:L1 may produce M11 , M12, , M1kL2 may produce M21 , M22, , M2kIf models are generated on the same test sets D1,D2, , Dk (e.g., via cross-validation)For each set: compute dj = e1j e2jdj has mean dt and variance tOverall varance: Use t-distribution to compute confidence interval,2022年12月26日星期一,数据挖掘导论,88,比较两个算法的性能:例,例: 两个分类技术产生的模型使用30-折交叉验证方法估计准确率准确率估计差的均值等于0.05，标准差等于0.002在95%置信水平下，真实准确率差为 dt= 0.05 t(1),k1 0.002 = 0.05 1.70 0.002 其中, t(1),k1 = 1.70通过查t-分布表得到因为置信区间不跨越0值，两个分类法的观察差是统计显著的,
