数据挖掘概念与技术CHAPTER6-分类基本概念.ppt
《数据挖掘概念与技术CHAPTER6-分类基本概念.ppt》由会员分享,可在线阅读,更多相关《数据挖掘概念与技术CHAPTER6-分类基本概念.ppt(85页珍藏版)》请在三一办公上搜索。
1、1,Chapter 6.分类:基本概念,分类:基本概念决策树归纳贝叶斯分类基于规则的分类模型评价与选择提高分类准确率的技术:集成方法Ensemble MethodsSummary,2,有监督 vs.无监督学习,有监督学习(分类)监督:训练数据(观察,测量等)都带有标签,指示观察的类别根据训练集分类新数据无监督学习(聚类)训练集的类别(标签)未知给定一个观察,测量等的集合,目标是建立数据中存在的数据的类或簇,3,分类预测分类的类标签(离散 or名义)基于训练数据和类标签 构造一个模型,并分类新数据数值预测 建连续值函数/模型,预测未知/缺失值 典型应用信用卡/贷款审批:医疗诊断:肿瘤是癌或良性?
2、欺诈检测:交易欺诈?网页分类:这是哪一类?,预测问题:分类vs.数值预测,4,分类:一个两步的过程,模型构建:描述一组预先定义的类假定每个元组/样本 属于一个类,由类标签属性设定用于构建模型的元组集合称为训练集training set模型可以表示为分类规则,决策树,数学公式模型使用:分类将来/未知对象估计模型的准确率测试集:独立于训练集的样本(避免过分拟合overfitting)比较测试样本的已知标签/由模型预测(得到)标签准确率:测试样本集中模型正确预测/分类的样本的比率如果准确率合时,使用模型来分类标签为未知的样本,5,Process(1):模型构建,TrainingData,Classi
3、ficationAlgorithms,IF rank=professorOR years 6THEN tenured=yes,Classifier(Model),6,Process(2):Using the Model in Prediction,Classifier,TestingData,Unseen Data,(Jeff,Professor,4),Tenured?,Issues:Evaluating Classification Methods,Accuracyclassifier accuracy:predicting class labelpredictor accuracy:gue
4、ssing value of predicted attributesSpeedtime to construct the model(training time)time to use the model(classification/prediction time)Robustness:handling noise and missing valuesScalability:efficiency in disk-resident databases Interpretabilityunderstanding and insight provided by the modelOther me
5、asures,e.g.,goodness of rules,such as decision tree size or compactness of classification rules,8,Chapter 6.分类:决策树归纳,分类:基本概念决策树归纳贝叶斯分类基于规则的分类模型评价与选择提高分类准确率的技术:集成方法Ensemble MethodsSummary,9,决策树归纳:例子,训练集:购买计算机结果:,10,决策树归纳的算法,基本算法(贪心算法)树构建:自顶向下递归地分治方式开始,所有的训练样本位于根节点属性是分类属性(若是连续值,事先离散化)基于选择的属性,样本被递归地分割基
6、于启发式/统计测来选择测试属性(例如 信息增益)终止划分的条件一个给定节点的所有样本属于一个类别没有属性剩下,用于进一步划分 运用多数投票来标记此节点没有样本剩下,属性选择度量,属性选择度量分裂规则,决定给定节点上的元组如何分裂具有最好度量得分的属性选定位分裂属性三种度量信息增益、增益率、Gini指标数学符号D为元组的训练集,元组属于m个不同的类Ci(i=1,m)Ci,D是D中的Ci类的元组集合|Ci,D|和|D|分别表示各自的元组个数,13,选择具有最高信息增益的属性令 pi 为D中的任一元组属于类 Ci概率,估计为|Ci,D|/|D|分类D中元组需要的期望信息(entropy):(利用 A
7、 分裂D 为v个部分后)分类D 需要的信息为:以属性A分枝得到的信息增益,属性选择度量:信息增益(ID3/C4.5),14,Class P:买电脑=“yes”Class N:买电脑=“no”,属性选择:信息增益,15,计算信息增益-连续值属性,令 A 为连续属性必须为A确定一个最佳分裂点 best split point上升序排序 A 典型地,每对相邻值的中点是一个可能的分裂点(ai+ai+1)/2 is the midpoint between the values of ai and ai+1具有最小期望信息需求的点选为A的分裂点Split:D1 为D中元组满足 A split-point
8、,D2 是元组满足 A split-point,16,增益率(C4.5),信息增益倾向于有大量不同取值的属性(划分更细,更纯)极端:每个划分子集只有一个样本,即一个类此时Info(d)=0 C4.5(ID3 后继)使用增益率来克服这一问题(规范化信息增益)GainRatio(A)=Gain(A)/SplitInfo(A)Ex.gain_ratio(income)=0.029/1.557=0.019具有最大增益率的属性选为分裂属性,17,Gini Index指标(CART),数据 D 包含n 类别的样本,gini指标,gini(D)定义为 pj 类别 j 在D中的频率数据集 D 基于属性A 分裂
9、为子集 D1 和 D2,gini 指标定义为不纯度减少:具有最小ginisplit(D)的属性(or不纯度减少最大的)用于分裂节点(需要枚举所有可能的分裂情况),18,计算 Gini Index 指标,D 有 9个元组买电脑=“yes”/5 个买电脑=“no”设属性income分裂D为包含10个元组的D1:low,medium/4个元组的D2 Ginilow,high=0.458;Ginimedium,high=0.450.因此low,medium/high分裂,由于其有最小的Gini index假设所有属性都是连续值,需要其他技术,e.g.,聚类,来获得可能的分裂点,19,比较属性选择度量,
10、通常三种度量获得较好的结果信息增益Information gain:偏向于多值属性增益率Gain ratio:倾向于不平衡的分裂,其中一个子集比其他小得多Gini index:偏向于多值属性当类数目较大时,计算困难倾向于导致大小相等的分区和纯度,20,其他属性选择度量,CHAID:一种流行的决策树算法,基于独立 2 检验的选择度量C-SEP:某些情况下比信息增益gini指标更好G-statistic:非常近似于 2 分布MDL(最小描述长度)(i.e.,首选最简单的解):最佳树为需要最小二进位的树(1)编码树,(2)编码树的异常多元划分(基于多变量组合来划分)CART:基于属性的线性组合来发现
11、多元划分哪一个是最好的?大部分可以获得较好结果,没有一个显著地优于其他,21,过拟合与数剪枝,过拟合Overfitting:一棵归纳的树 可能过分拟合训练数据分枝太多,某些反映训练数据中的异常,噪音/孤立点对未参与训练的样本的低精度预测两种处理方法 先剪枝:提前终止树构造 如果对一个节点的分裂会产生低于给定的阈值的度量,划分停止选择一个合适的阈值很难后剪枝:从完全生长的树中剪去树枝得到一个逐步修剪树例如,最小化代价复杂度(树节点个数和错误率的函数)使用不同于训练集的数据来确定哪一个是“best pruned tree”,22,决策树归纳的增强,允许连续值属性动态地定义新的离散值属性,其把连续值
12、属性分成离散的区间处理缺失属性值分配属性的最常见值为每一个可能的值分配概率属性构造基于现有的稀少出现的属性创建新的属性,这减少了分散,重复和复制,23,大型数据库中分类,分类被统计学和机器学习研究人员广泛地研究一个经典问题可伸缩性:以合理的速度分类由带有数百个属性的百万个样本组成的数据集为什么决策树归纳受欢迎?相对快的训练速度(与其他分类方法相比)转换为简单、易于理解的分类规则可用 SQL查询来访问数据库与其它方法可比的分类精度RainForest(VLDB98 Gehrke,Ramakrishnan&Ganti)Builds an AVC-list(attribute,value,class
13、 label),24,RainForest雨林的可扩展性框架,可扩展性和确定质量树的标准相分离建并维持 AVC-list:AVC(属性-值,类标号)AVC集(of an attribute X)把训练集投影到属性X和类标签上,给出属性X的每个值上的类标签计数AVC组群(在节点n)节点n上所有预测属性的AVC集合-组群,25,Rainforest:训练集和AVC集,AVC-set on income,AVC-set on Age,AVC-set on Student,Training Examples,AVC-set on credit_rating,26,BOAT(Bootstrapped O
14、ptimistic Algorithm for Tree Construction),使用一个叫做 bootstrapping 自助法的统计技术多个更小的样本集(子集),每一个可放入内存每个子集产生一个树,导致多个树 考察这些树并用他们构造一个新树T事实证明,T 非常接近于使用全部数据集构造的树Adv:只要求扫描DB两遍,并且是一个增量算法.,2023年10月14日星期六,Data Mining:Concepts and Techniques,27,分类结果的陈述/表示,2023年10月14日星期六,Data Mining:Concepts and Techniques,28,决策树可视化SG
15、I/MineSet 3.0,SGI公司和美国Standford大学联合开发的多任务数据挖掘系统。MineSet以先进的可视化显示方法闻名于世,29,Chapter 6.分类:贝叶斯分类,分类:基本概念决策树归纳贝叶斯分类基于规则的分类模型评价与选择提高分类准确率的技术:集成方法Ensemble MethodsSummary,30,贝叶斯理论,令X 为数据样本:类标签未知令H为一个假设在:X属于类别 C 分类就是确定 P(H|X)(后验概率),给定观察数据 X,假设H成立的概率P(H)(先验概率)最初的概率例,不管年龄和收入等条件 X将会购买计算机P(X):样本数据x被观察到的概率P(X|H)(
16、可能性),假设H成立,那么观测到样本X的概率E.g.,已知X购买计算机,X 为31.40且中等收入的概率,31,贝叶斯理论Bayesian Theorem,给定训练数据 X,假设 H的后验概率 P(H|X满足贝叶斯理论通俗地说,这可以写成posteriori=likelihood x prior/evidence预测X属于类别C2当且仅当概率P(Ci|X)是所有 P(Ck|X)for all the k classes最大的实际困难:需要许多可能性的初步知识,计算成本显著,32,Nave Bayesian Classifier,D为训练数据集(包含类别标签),并且每个元组表示为一个n-维的属性
17、向量X=(x1,x2,xn)假定有 m 个类别 C1,C2,Cm.分类就是推导最大的后验概率,i.e.,the maximal P(Ci|X)可以由贝叶斯理论计算由于对所有类P(X)是常量,只需要最大化,33,朴素贝叶斯分类器的推导,一个简单假定:属性是条件独立的(i.e.,属性间没有依赖关系):这样极大地减少了计算代价:只需要统计类的分布若Ak 是分类属性P(xk|Ci)=Ci 类中Ak 取值为xk 的元组数/|Ci,D|(类Ci 的大小)若Ak 是连续值,P(xk|Ci)通常基于均值 标准差 的高斯分布计算P(xk|Ci)=,34,朴素贝叶斯分类:训练数据集,两个类别:C1:buys_co
18、mputer=yesC2:buys_computer=no数据样本 X=(age=30,Income=medium,Student=yesCredit_rating=Fair),35,Nave Bayesian Classifier:例子,P(Ci):P(buys_computer=“yes”)=9/14=0.643 P(buys_computer=“no”)=5/14=0.357Compute P(X|Ci)for each class P(age=“=30”|buys_computer=“yes”)=2/9=0.222 P(age=“=30”|buys_computer=“no”)=3/5
19、=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.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=(ag
20、e=30,income=medium,student=yes,credit_rating=fair)P(X|Ci):P(X|buys_computer=“yes”)=0.222 x 0.444 x 0.667 x 0.667=0.044 P(X|buys_computer=“no”)=0.6 x 0.4 x 0.2 x 0.4=0.019P(X|Ci)*P(Ci):P(X|buys_computer=“yes”)*P(buys_computer=“yes”)=0.028 P(X|buys_computer=“no”)*P(buys_computer=“no”)=0.007Therefore,X
21、 belongs to class(“buys_computer=yes”),36,贝叶斯分类:Why?,一个统计学分类器:执行概率预测,i.e.,预测类成员的概率基础:基于贝叶斯理论 Performance:一个简单的贝叶斯分类器,朴素贝叶斯分类器,可以与决策树和经过挑选的神经网络分类器相媲美增量:每次训练的样本可以逐步增加/减少一个假设是正确的可能性先验知识可与观测数据相结合Standard:即使贝叶斯方法是难以计算的,最优决策制定提供标准(其他方法可以衡量),37,避免零概率问题,朴素贝叶斯要求每个条件概率非零.然而,预测的概率可能为零Ex.假定有1000 元组,e=low(0),inc
22、ome=medium(990),and income=high(10)Use Laplacian correction校准(or Laplacian estimator估计法)Adding 1 to each caseProb(income=low)=1/1003Prob(income=medium)=991/1003Prob(income=high)=11/1003校准的“corrected”概率估计很接近未校准的,38,Nave Bayesian Classifier:评论,Advantages Easy to implement Good results obtained in most
23、 of the casesDisadvantagesAssumption:类条件独立性,损失精度实际中,变量间存在依赖 E.g.,医院:患者:简介:年龄,家族病史等症状:发烧,咳嗽等疾病:肺癌,糖尿病等 Dependencies among these cannot be modeled by Nave Bayesian ClassifierHow to deal with these dependencies?Bayesian Belief Networks,39,Chapter 6.分类:基于规则的分类,分类:基本概念决策树归纳贝叶斯分类基于规则的分类模型评价与选择提高分类准确率的技术:集
24、成方法Ensemble MethodsSummary,40,使用IF-THEN 规则分类,使用 IF-THEN 规则表示知识R:IF age=youth AND student=yes THEN buys_computer=yes规则前件/前提 vs.规则结论评估规则:覆盖率coverage and 准确率accuracy ncovers=#规则R覆盖的元组数%给定元组,规则的前提满足覆盖元组ncorrect=#R正确分类的元组数coverage(R)=ncovers/|D|/%D:训练数据集accuracy(R)=ncorrect/ncovers如果超过1条规则被触发,需要解决冲突规模序Si
25、ze ordering:最高优先权赋予“最苛刻”的规则(即,最多属性测试)基于类的序:每个类的错误分类代价的下降序基于规则的序(决策表):根据一些规则的质量度量或由专家建议,规则被组织成一个长的优先级列表,41,Example:Rule extraction from our buys_computer decision-treeIF age=young AND student=no THEN buys_computer=noIF age=young AND student=yes THEN buys_computer=yesIF age=mid-age THEN buys_computer=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据 挖掘 概念 技术 CHAPTER6 分类 基本概念
链接地址:https://www.31ppt.com/p-6296675.html