1、大数据分析和内存计算第4讲 数据挖掘技术概述李国良清华大学计算机系提纲数据挖掘概览数据预处理分类（Classification）聚类（Cluster）关联规则（Association Rule）回归（Regression）数据挖掘概览What?数据挖掘的定义Why?数据挖掘的动机How?哪些数据可以用来挖掘？数据挖掘的主要内容数据挖掘定义什么是数据挖掘（Data Mining）？-Extraction of interesting(non-trivial,implicit,previously unknown and potentially useful)patterns or knowled
2、ge from huge amount of data-其他称谓：Knowledge discovery(mining)in database(KDD),data/pattern analysis,business intelligence,decision-support system,knowledge extraction,data archeology,data dredging and information harvesting etc.DatapreprocessingDataminingpostprocessingknowledgeraw dataFeature selecti
3、onDimension reductionNormalizationData subsettingFiltering patternsVisuaralizationPattern interpretationData Mining Process模式有效性度量SimplicityE.g.,(association)rule length,(decision)tree size CertaintyE.g.,confidence,P(A|B)=#(A and B)/#(B),classification reliability or accuracy,rule strength,etc.Utili
4、tyPotential usefulness,e.g.,support(association),noise threshold(description)NoveltyNot previously known,surprising(used to remove redundant rules)为何需要数据挖掘？1.数据量大2.缺乏理论知识3.数据挖掘可以帮助产生新的假说或者使数据变得有意义为何需要数据挖掘？We are drowning in data,but starving in knowledge Data explosion:Automated data collection tool
5、s and mature database technology lead to tremendous amounts of data accumulated and/or to be analyzed in databases,data warehouses,and other information repositories.苦恼:淹没在数据中;不能制定合适的决策!n模式模式n趋势趋势n事实事实n关系关系n模型模型n关联规则关联规则n序列序列n目标市场目标市场n资金分配资金分配n贸易选择贸易选择n在哪儿做广告在哪儿做广告n销售的地理位置销售的地理位置n金融金融n经济经济n政府政府n人口统计
6、人口统计n生命周期生命周期数据挖掘的意义数据数据挖掘挖掘辅助辅助社会社会管理管理促进促进民生民生改善改善支持支持商业商业决策决策推动推动科技科技进步进步数据挖掘应用l 银行 美国银行家协会(ABA)预测数据仓库和数据挖掘技术在美国商业银行的应用增长率是14.9。分析客户使用分销渠道的情况和分销渠道的容量；建立利润评测模型；客户关系优化；风险控制等l 电子商务 网上商品推荐；个性化网页；自适应网站l 生物制药、基因研究 DNA序列查询和匹配；识别基因序列的共发生性 l 电信 欺诈甄别；客户流失l 保险、零售数据挖掘应用Debt$40KQ QQ QQ QQ QI II I1 12 23 34 45
7、 56 6factor 1factor 2factor n神经网络神经网络 Neural Networks Neural Networks聚类分析聚类分析 Clustering ClusteringOpenAccntAdd NewProductDecreaseUsage?Time序列分析序列分析 Sequence Analysis Sequence Analysis决策树决策树 Decision Trees Decision Trees 倾向性分析 客户保留 客户生命周期管理 目标市场 价格弹性分析 客户细分 市场细分 倾向性分析 客户保留 目标市场 欺诈检测关联分析关联分析 Associat
8、ion Association 市场组合分析 套装产品分析 目录设计 交叉销售数据挖掘步骤数据预处理数据清理（消除噪音或不一致数据，补缺）数据集成（多种数据源可以组合在一起）数据变换（规范化）数据规约（数据简化）数据挖掘算法（使用智能方法提取数据模式）分类、聚类、关联分析、回归预测、文本挖掘质量评估（识别提供知识的真正有趣模式）知识表示（可视化和知识表示技术）数据质量：为何需要数据预处理？数据质量衡量：准确度:correct or wrong,accurate or not完整度:not recorded unavailable一致性:some modified but some not,da
9、ngling时效性:timely update?可信度:how trustable the data are correct?可解释性:how easily the data can be understood?数据挖掘预处理的主要任务 数据清理 填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性 数据集成 集成多个数据库、数据立方体或文件 数据变换 规范化和聚集 数据归约 得到数据集的压缩表示，它小得多，但可以得到相同或相近的结果 数据离散化 数据归约的一部分，通过概念分层和数据的离散化来规约数据，对数字型数据特别重要数据清洗脏数据：例如设备错误，人或者机器错误，传输错误等不完整性：
10、属性值缺失或者只有聚集数据p例如：phone=“”;噪音：包含噪声、错误或者异常值p例如：salary=-10不一致性:p例如：age=42，birthday=03-07-2010假值：p例如：使用某一值填补缺失属性缺失值（Incomplete/Missing Data)数据并不总是完整的例如：数据库表中，很多条记录的对应字段没有相应值，比如销售表中的顾客收入引起空缺值的原因设备异常与其他已有数据不一致而被删除因为误解而没有被输入的数据在输入时，有些数据因为得不到重视而没有被输入对数据的改变没有进行日志记载空缺值要经过推断而补上如何补充缺失值忽略元组：当类标号缺少时通常这么做（假定挖掘任务设计
11、分类或描述），当每个属性缺少值的百分比变化很大时，它的效果非常差。人工填写空缺值：工作量大，可行性低使用一个全局变量填充空缺值：比如使用unknown或-使用属性的平均值填充空缺值使用与给定元组属同一类的所有样本的平均值使用最可能的值填充空缺值：使用像使用最可能的值填充空缺值：使用像BayesianBayesian公公式或判定树这样的基于推断的方法式或判定树这样的基于推断的方法噪声数据 噪声：一个测量变量中的随机错误或偏差 引起不正确属性值的原因 数据收集工具的问题 数据输入错误 数据传输错误 技术限制 命名规则的不一致 其它需要数据清理的数据问题 重复记录 不完整的数据 不一致的数据如何处理
12、噪声数据分箱分箱:first sort data and partition into(equi-depth)binsthen one can smooth by bin means,smooth by bin median,smooth by bin boundaries,etc.聚类聚类detect and remove outliers人机融合人机融合detect suspicious values and check by human(e.g.,deal with possible outliers)回归回归smooth by fitting the data into regress
13、ion functions分箱(Binning)等宽Equal-width(distance)partitioning:Divides the range into N intervals of equal size:uniform gridif A and B are the lowest and highest values of the attribute,the width of intervals will be:W=(B A)/N.The most straightforward,but outliers may dominate presentationSkewed data i
14、s not handled well.等深Equal-depth(frequency)partitioning:Divides the range into N intervals,each containing approximately same number of samplesGood data scalingManaging categorical attributes can be tricky.数据平滑的分箱方法 price的排序后数据（单位：美元）：4，8，15，21，21，24，25，28，34 划分为（等深的）箱：箱1：4，8，15 箱2：21，21，24 箱3：25，28
15、，34 用箱平均值平滑：箱1：9，9，9 箱2：22，22，22 箱3：29，29，29 用箱边界平滑：箱1：4，4，15 箱2：21，21，24 箱3：25，25，34聚类：Cluster Analysis每个簇中的数据用其中心值代替忽略孤立点先通过聚类等方法找出孤立点。这些孤立点可能包含有用的信息。人工再审查这些孤立点Regression通过构造函数来符合数据变化的趋势，这样可以用一个变量预测另一个变量。线性回归 多线性回归非线性回归XY2211XXY33221XXXYxyy=x+1X1Y1Y1数据集成实体识别元数据可帮助避免错误知识图谱属性冗余相关分析数据重复（元组冗余）数据值冲突的检测
16、与处理表示、比例或编码不同 数据变换（规范化）平滑：去掉数据中的噪声。技术包括分箱、回归、聚类。聚集：对数据进行汇总或聚集。数据泛化（概化）：使用概念分层，用高层概念替换低层或“原始”数据。规范化：将属性数据按比例缩放，使之落入一个小的特定区间。最小-最大、Z-Score、按小数定标规范化。数据变换平滑，聚集数据概化，规范化属性构造(特征构造)有限区间的归一化：无限区间的归一化：模糊隶属度：minmaxminvv-vev-11数据规约海量数据 代表性数据对海量数据进行复杂的数据分析和挖掘将需要很长时间，使得这种分析不现实或不可行。数据归约技术可以用来得到数据集的归约表示，它小得多，但仍接近保持
17、原数据的完整性。对归约后的数据集挖掘将更有效，并产生相同（或几乎相同）的结果。数据规约数据归约策略：（1）数据立方体聚集：对数据立方体做聚集操作（2）属性子集选择：检测并删除不相关、弱相关或冗余的属性和维。（3）维度归约：删除不重要的属性（4）数值归约：用规模较小的数据表示、替换或估计原始数据（5）离散化和概念分层产生属性的原始数值用区间值或较高层的概念替换数据立方体据立方体存储多维聚集信息，提供对预计算的汇总数据进行快速访问。如：立方体内存储季度销售额，若对年销售额感兴趣，可对数据执行聚集操作，例如sum()等。属性子集选择通过删除不相关或冗余的属性（或维）减小数据集。其目标是找出最小属性集
18、，使得数据类的概率分布尽可能地接近使用所有属性得到的原分布。通过穷举搜索找出有属性的最佳子集是不现实的。通常采用压缩搜索空间的启发式算法。如贪心算法：从局部最优到全局最优。逐步向前选择逐步向后删除向前选择和向后删除的结合决策树归纳维度规约维度归约使用数据编码或变换，以便得到原数据的归约或“压缩”表示。分为无损和有损两种。主要方法：串压缩：无损，但只允许有限的数据操作。小波变换（DWT）：有损，适合高维数据。主成分分析（PCA）：有损，能更好地处理稀疏数据。数值规约通过选择替代的、“较小的”数据表示形式来减少数据量。可以分为参数方法和非参数方法。参数方法：回归（regression）和对数线性模
19、型非参数方法：直方图、聚类、抽样离散化离散化的用途：（1）适应某些仅接受离散值的算法；（2）减小数据的尺度。离散化的方法包括几下几种。（1）等距分割；（2）聚类分割；（3）直方图分割；（4）基于熵的分割；（5）基于自然属性的分割。抽样用数据的小得多的随机样本（子集）不是大型数据集。抽样方法s个样本无放回简单随机抽样s个样本有放回简单随机抽样聚类抽样分层抽样分类分类分类是指将数据映射到预先定义好的群组或类。在分析测试数据之前，类别就已经被确定了，所以分类统称被称作有指导的学习。分类算法要求基于数据属性来定义类别。分类算法通常通过观察已知所属类别的数据的特征来描述类别。分类应用分类具有广泛的应用，
20、例如医疗诊断、信用卡系统的信用分级、图像模式识别等。为了识别乘客是否是潜在的恐怖分子或罪犯，机场安全摄像站需要对乘客的脸部进行扫描并辨识脸部的基本模式（例如双眼间距、嘴的大小及形状、头的形状），然后将得到的模式与数据库中的已知恐怖分子或罪犯的模式进行逐个比较，看看是否与其中的某一模式相匹配。分类步骤1建立一个模型，描述预定的数据类集或概念集 数据元组也称作样本、实例或对象。为建立模型而被分析的数据元组形成训练数据集。训练数据集中的单个元组称作训练样本，假定每个元组属于一个预定义的类，由一个称作类标号。通过分析训练数据集来构造分类模型，可用分类规则、决策树或数学公式等形式提供。2.使用模型进行分
21、类首先评估模型（分类法）的预测准确率。p将已知的类标号与该样本的学习模型类预测比较p准确率等于测试集的样本中被模型正确分类的百分比p测试集应该与训练集的内容相互独立，否则会出现过分适应的情况如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行分类。（1）模型的构建TrainingDataClassificationAlgorithmsIF rank=professorOR years 6THEN tenured=yes Classifier(Model)NAME RANKYEARSTENUREDMikeAssistant Prof3noMaryAssistant Prof7
22、yesBill Professor2yesJimAssociate Prof7yesDaveAssistant Prof6noAnneAssociate Prof3no（2）利用模型分类ClassifierTestingDataN A M ER A N KY E A R S TE N U R E DTomA ssistant P rof2noM erlisaA ssociate P rof7noG eorge P rofessor5yesJoseph A ssistant P rof7yesUnseen Data(Jeff,Professor,4)Tenured?分类方法评价预测的准确率l这涉
23、及模型正确地预测新的或先前未见过的数据的类标号的能力速度l构造模型的速度l利用模型进行分类的速度强壮性l给定噪声数据或具有空缺值的数据，模型正确预测的能力可伸缩性l当给定大量数据时，有效地构造模型的能力可解释性 l涉及学习模型提供的理解和洞察的层次分类器性能评价方式 准确率和召回率-混淆矩阵等 给定一个类Cj和一个数据库元组ti，ti可能被分类器判定为属于Cj或不属于Cj，其实ti本身可能属于Cj或不属于Cj，这样就会产生如下一些情况：真正:判定ti在Cj中，实际上的确在其中。假正:判定ti在Cj中，实际上不在其中。真负:判定ti不在Cj中，实际上不在其中。假负:判定ti不在Cj中，实际上的确
24、在其中。准确率:P=A/(A+B)召回率:R=A/(A+C)评估分类方法的准确性保持方法给定数据随机划分为两个集合：训练集(2/3)和测试集(1/3)训练集导出分类法，测试集对其准确性进行评估k-折交叉验证初始数据被划分为k个不相交的，大小大致相同的子集S1,S2Sk进行k次训练和测试，第i次时，以Si做测试集，其他做训练集准确率为k次迭代正确分类数除以初始数据集样本总数分类方法基于距离的分类方法与一个类中的成员和另一个类中的成员之间的相似性相比，被映射到同一个类中的成员彼此之间被认为是更加相似的。相似性（距离）度量可以用来识别数据库中不同成员之间的“相似程度”。基于距离的分类方法的直观解释（
25、a）类定义）类定义（b）待分类样例）待分类样例（c）分类结果）分类结果距离计算方法闵可夫斯基距离:当p=2时，为欧几里得距离当p=1时，为曼哈顿距离当p-时，为切比雪夫距离向量内积：夹角余弦：Jaccard：还有信息熵、相关系数等其他的度量方法(|xi-yi|pi1n)1/pInner(x,y)x,y xiyiicosqx1x2y1y2x12y12x22y22J(A,B)|AB|AB|基于距离的分类方法的一般性描述 算法算法 基于距离的分类算法基于距离的分类算法 输入：每个类的中心输入：每个类的中心C1，Cm；待分类的元组；待分类的元组t。输出：输出类别输出：输出类别c。（1）dist=；/距
26、离初始化距离初始化（2）FOR i:=1 to m DO（3）IF dis(ci，t)dist THEN BEGIN（4）cCi；（5）distdist(Ci，t)；（6）END.算法通过对每个元组和各个类的中心来比较，从而可算法通过对每个元组和各个类的中心来比较，从而可以找出他的最近的类中心，得到确定的类别标记。以找出他的最近的类中心，得到确定的类别标记。K近邻算法（KNN）K K Nearest Nearest neighbor(KNN)neighbor(KNN)通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的K个训练数据，K个数据中哪个类别的训练数据占多数，则待分类元组就
27、属于哪个类别。训练样本用n维数值属性描述。每个样本代表n维空间的一个点。所有的训练样本都放在n维模式空间中。给定一个样本，k-最临近分类法搜索模式空间，找出最接近未知样本的k个训练样本。K近邻算法（KNN）要求的信息要求的信息训练集训练集距离计算值距离计算值要获取的最邻近的邻居的数目要获取的最邻近的邻居的数目k k 一个未知的记录进行分类一个未知的记录进行分类计算与其它训练记录之间的距离计算与其它训练记录之间的距离识别出识别出k k个最近的邻居个最近的邻居使用最近邻居的类标号来标识未知元组的类（使用最近邻居的类标号来标识未知元组的类（by taking by taking majority v
28、otemajority vote）K近邻算法（KNN）算法算法 K-近邻分类算法近邻分类算法输入：输入：训练数据训练数据T；近邻数目；近邻数目K；待分类的元组；待分类的元组t。输出：输出：输出类别输出类别c。（1）N=；（2）FOR each d T DO BEGIN（3）IF|N|K THEN（4）N=Nd；（5）ELSE（6）IF uN such that sim(t，u)40000高负债高负债工作时间工作时间5年年是是否否是是否否“年收入大于￥40000”并且“高负债”的用户被认为是“高风险”；“年收入小于￥40000”但“工作时间大于5年”的申请，是“低风险”；NYYNNY决策树buy
29、s_computer的决策树示意的决策树示意 Age?Credit_rating?student?yes no yesyes no 40 3040yes no fairexcellent 决策树l决策树（决策树（decision treedecision tree）l19861986年年 Quinlan Quinlan提出了著名的提出了著名的ID3ID3算法。算法。l在在ID3ID3算法的基础上，算法的基础上，19931993年年QuinlanQuinlan又提出了又提出了C4.5C4.5算法算法。l为了适应处理大规模数据集的需要，后来又提出了若为了适应处理大规模数据集的需要，后来又提出了若干
30、改进的算法，其中干改进的算法，其中SLIQ(super-vised learning in quest)SLIQ(super-vised learning in quest)和和SPRINT(scalable SPRINT(scalable parallelizableparallelizable induction induction of decision of decision trees)trees)是比较有代表性的两个算法。是比较有代表性的两个算法。决策树的步骤使用决策树进行分类分为两步：使用决策树进行分类分为两步：第1步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际
31、上是一个从数据中获取知识，进行机器学习的过程。第2步：利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类。决策树算法递归执行的终止条件（停止分支的条件）算法递归执行的终止条件（停止分支的条件）对于给定的节点，对于给定的节点，所有的例子都属于同一个类所有的例子都属于同一个类虽然对于某一个节点当前的例子不属于同一个类，但虽然对于某一个节点当前的例子不属于同一个类，但是已经是已经没有属性没有属性可用来选择继续进行分支处理可用来选择继续进行分支处理分裂属性选择选择属性的方法选择属性的方法选择具有选择具有最大信息增益最大信息增益
32、的属性作为当前节点的的属性作为当前节点的测试属性测试属性该属性使得对结果划分中的样本分类所需的该属性使得对结果划分中的样本分类所需的信信息量最小息量最小，并反映划分的最小随机性。，并反映划分的最小随机性。用信息增益这种用信息增益这种信息论信息论的理论方法，使得对一的理论方法，使得对一个对象分类所需要的期望测试数目达到最小，个对象分类所需要的期望测试数目达到最小，并确保找到一棵简单的树。并确保找到一棵简单的树。分裂属性选择怎样计算信息增益（怎样计算信息增益（information gaininformation gain）信息增益被定义为信息增益被定义为原始分割的熵原始分割的熵与划分以后各与划分
33、以后各分割的熵分割的熵累加得到的总熵之间的差。累加得到的总熵之间的差。信息增益信息增益是指划分前后进行正确预测所需的是指划分前后进行正确预测所需的信信息量之差息量之差。选择具有选择具有最高信息增益最高信息增益的属性作为当前节点的的属性作为当前节点的测试属性。测试属性。信息增益的计算 设S是有s个训练样本数据的集合，类标号属性具有m个不同值，定义m个不同类Ci（i=1,2,m），si是类Ci中的样本数，则对一个给定的训练样本分类所需要的期望信息为：-miiimppsssI1221log,其中其中p pi i是任意样本属于是任意样本属于C Ci i的概率，可用的概率，可用s si i/s/s来估计
34、来估计决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买决策属性“买计算机
35、？”。该属性分两类：买/不买S1(买)=641 S2（不买）=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0.9537第第1步计算决策属性的熵步计算决策属性的熵决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买6
36、3老中否优不买1 老中否优买第第2步计算条件属性的熵步计算条件属性的熵条件属性共有4个。分别是年龄、收入、学生、信誉。分别计算不同属性的信息增益。决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-1步计算年龄的熵步计算年龄的熵年龄共分三个组：青年、中年、老年青年买与不买比例为128/256S1(买)=128 S2（不买）=256S=S1+S2=384P
37、1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0.9183决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-2步计算年龄的熵步计算年龄的熵年龄共分三个组：青年、中年、老年中年买与不买比例为256/0S1(买)=256 S2（不买）=0S=S
38、1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-3步计算年龄的熵步计算年龄的熵年龄共分三个组：青年、中年、老年老年买与不买比例为125/127S1(买)=125 S2（不买）=12
39、7S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0.9157决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-4步计算年龄的熵步计算年龄的熵年龄共分三个组：青年、中年、老年所占比例青年组 384/1025=0.375
40、中年组 256/1024=0.25老年组 384/1024=0.375计算年龄的平均信息期望E（年龄）=0.375*0.9183+0.25*0+0.375*0.9157 =0.6877G（年龄信息增益）=0.9537-0.6877 =0.2660 （1）决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第3步计算收入的熵步计算收入的熵收入共分三个组：高、中、
41、低E（收入）=0.9361收入信息增益=0.9537-0.9361 =0.0176(2)决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第4步计算学生的熵步计算学生的熵学生共分二个组：学生、非学生E（学生）=0.7811年龄信息增益=0.9537-0.7811 =0.1726 （3）决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良
42、不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第5步计算信誉的熵步计算信誉的熵信誉分二个组：良好，优秀E（信誉）=0.9048信誉信息增益=0.9537-0.9048 =0.0453 （4）决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否
43、优买32中高是良买63老中否优不买1 老中否优买第第6步计算选择节点步计算选择节点 年龄信息增益=0.9537-0.6877 =0.2660 （1）收入信息增益=0.9537-0.9361 =0.0176 （2）年龄信息增益=0.9537-0.7811 =0.1726 （3）信誉信息增益=0.9537-0.9048 =0.0453 （4）决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买年龄年龄青年中年老年买/不买买买/不买叶子决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买
44、64青高否优不买128青中否良不买64青低是良买64青中是优买青年买与不买比例为128/256S1(买)=128 S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0.9183决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买如果选择收入作为节点分高、中、低平均信息期望（加权总和）：E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0
45、.4592Gain(收入)=I(128,256)-E(收入)=0.9183 0.4592=0.4591I(0,128)=0 比例:128/384=0.3333I(64,128)=0.9183 比例:192/384=0.5I(64,0)=0比例:64/384=0.1667 注意决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买年龄年龄青年中年老年学生买信誉叶子否
46、否是是优优良良买不买买/不买买叶子叶子叶子决策树分类规则提取 决策树所表示的分类知识可以被抽取出来并可用IF-THEN 分类规则形式加以表示。从决策树的根结点到任一个叶结点所形成的一条路径就构成了一条分类规则。沿着决策树的一条路径所形成的属性-值对就构成了分类规则条件部分（IF 部分）中的一个合取项，叶结点所标记的类别就构成了规则的结论内容（THEN 部分）。IF-THEN分类规则表达方式易于被人理解，且当决策树较大时，IF-THEN规则表示形式的优势就更加突出。贝叶斯分类贝叶斯分类 贝叶斯定理 贝叶斯定理给出了如下计算P(C|X)的简单有效的方法:P(C):是先验概率，或称C的先验概率。P(
47、X):样本数据被观察的概率。P(X|C)代表假设C成立的情况下，观察到X的概率。P(C|X)是后验概率，或称条件X下C的后验概率。后验概率P(C|X)比先验概率P(C)基于更多的信息。P(C)是独立于X的。P(C|X)P(X|C)P(C)P(X)朴素贝叶斯分类l朴素贝叶斯分类的工作过程如下：(1)每个数据样本用一个n维特征向量X=x1,x2xn表示，分别描述n个属性A1，An样本的n个度量。(2)假定有m个类C1，C2，Cm，给定一个未知的数据样本X（即没有类标号），分类器将预测X属于具有最高后验概率（条件X下）的类。朴素贝叶斯分类将未知的样本分配给类Ci（1im）当且仅当P(Ci|X)P(C
48、j|X)，ji。即最大化P(Ci|X)P(Ci|X)最大的类Ci称为最大后验假定。朴素贝叶斯分类(3)由于P(X)对于所有类为常数，P(X|Ci)*P(Ci)最大即可。如果Ci类的先验概率未知，则通常假定这些类是等概率的，即P(C1)=P(C2)=P(Cm)，因此问题就转换为对P(X|Ci)的最大化（P(X|Ci)常被称为给定Ci时数据X的似然度，而使P(X|Ci)最大的假设Ci称为最大似然假设）。否则，需要最大化P(X|Ci)*P(Ci)。类的先验概率可以用P(Ci)=si/s计算，其中si是类Ci中的训练样本数，而s是训练样本总数。)()()|()|(XPCPCXPXCPiii朴素贝叶斯分
49、类（4）给定具有许多属性的数据集，计算P(X|Ci)的开销可能非常大。为降低计算P(X|Ci)的开销，可以做类条件独立的朴素假定。给定样本的类标号，假定属性值相互条件独立，即在属性间，不存在依赖关系。这样)|()|(1inkkiCxPCXP概率P(x1|Ci)，P(x2|Ci)，P(xn|Ci)由训练样本估值。-如果Ak是离散属性，则P(xk|Ci)=sik/si，其中sik是在属性Ak上具有值xk的类Ci的训练样本数，si是Ci中的训练样本数。-如果Ak是连续值属性，常用的处理方法有两种：一是对其离散化，然后按照离散值处理；另一种假定这一属性服从某一分布，通常假定该属性服从高斯分布。(5)对
50、 未 知 样 本X分 类，也 就 是 对 每 个 类Ci，计 算P(X|Ci)*P(Ci)。样本X被指派到类Ci，当且仅当P(Ci|X)P(Cj|X)，1jm，ji。即X被指派到其P(X|Ci)*P(Ci)最大的类。朴素贝叶斯分类举例希望分类的未知样本为希望分类的未知样本为:X=（age=“=30”，income=“medium”，student=“yes”，credit_rating=“fair”）思路思路:计算每一个类的计算每一个类的P(Ci|X)=P(X|Ci)P(Ci)/P(X),Ci代表任意一个代表任意一个类，类，X代表需要判断的代表需要判断的查询条件查询条件朴素贝叶斯分类举例设 C
