[精选]数据挖掘技术概述.pptx

《[精选]数据挖掘技术概述.pptx》由会员分享，可在线阅读，更多相关《[精选]数据挖掘技术概述.pptx（146页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 knowledge from huge amount o

2、f data-其他称谓：Knowledge discoverymining in databaseKDD,data/pattern analysis,business intelligence,decision-support system,knowledge extraction,data archeology,data dredging and information harvesting etc.模式有效性度量SimplicityE.g.,association rule length,decision tree size CertaintyE.g.,confidence,PA|B=#A

3、 and B/#B,classification reliability or accuracy,rule strength,etc.UtilityPotential 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,

4、but starving in knowledge Data explosion:Automated data collection tools 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关联规则关

5、联规则n序列序列n目标市场目标市场n资金分配资金分配n贸易选择贸易选择n在哪儿做广告在哪儿做广告n销售的地理位置销售的地理位置n金融金融n经济经济n政府政府n人口统计人口统计n生命周期生命周期数据挖掘的意义数据挖掘数据挖掘辅助社辅助社会管理会管理促进民促进民生改善生改善支持商支持商业决策业决策推动科推动科技进步技进步股票趋势分析股票趋势分析智能交通智能交通数据挖掘应用l银行 银行家协会ABA预测数据仓库和数据挖掘技术在 商业银行的应用增长率是14.9。分析客户使用分销渠道的情况和分销渠道的容量；建立利润评测模型；客户关系优化；风险控制等l电子商务网上商品推荐；个性化网页；自适应网站l生物制药、

6、基因研究DNA序列查询和匹配；识别基因序列的共发生性 l电信欺诈甄别；客户流失l保险、零售数据挖掘应用Debt$40KQ QQ QQ QQ QII123456factor 1factor 2factor n神经网络神经网络 Neural Networks Neural Networks聚类分析聚类分析 Clustering ClusteringOpenAccntAdd NewProductDecreaseUsage?Time序列分析序列分析 Sequence Analysis Sequence Analysis决策树决策树 Decision Trees Decision Trees 倾向性分析

7、 客户保存 客户生命周期管理 目标市场 价格弹性分析 客户细分 市场细分 倾向性分析 客户保存 目标市场 欺诈检测关联分析关联分析 Association Association 市场组合分析 套装产品分析 目录设计 交叉销售数据挖掘步骤数据预处理数据清理消除噪音或不一致数据，补缺数据集成多种数据源可以组合在一起数据变换标准化数据规约数据简化数据挖掘算法使用智能方法提取数据模式分类、聚类、关联分析、回归预测、文本挖掘质量评估识别提供知识的真正有趣模式知识表示可视化和知识表示技术数据质量：为何需要数据预处理？数据质量衡量：准确度:correct or wrong,accurate or not完

8、整度:not recorded unavailable一致性:some modified but some not,dangling时效性:timely update?可信度:how trustable the data are correct?可解释性:how easily the data can be understood?数据挖掘预处理的主要任务数据清理填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性数据集成集成多个数据库、数据立方体或文件数据变换标准化和聚集数据归约得到数据集的压缩表示，它小得多，但可以得到相同或相近的结果数据离散化数据归约的一局部，通过概念分层和数据的离散

9、化来规约数据，对数字型数据特别重要数据清洗脏数据：例如设备错误，人或者机器错误，传输错误等不完整性：属性值缺失或者只有聚集数据p例如：phone=“;噪音：包含噪声、错误或者异常值p例如：salary=-10不一致性:p例如：age=42，birthday=03-07-2010假值：p例如：使用某一值填补缺失属性缺失值In plete/Missing Data数据并不总是完整的例如：数据库表中，很多条记录的对应字段没有相应值，比方销售表中的顾客收入引起空缺值的原因设备异常与其他已有数据不一致而被删除因为误解而没有被输入的数据在输入时，有些数据因为得不到重视而没有被输入对数据的改变没有进行日志记

10、载空缺值要经过推断而补上如何补充缺失值忽略元组：当类标号缺少时通常这么做假定挖掘任务设计分类或描述，当每个属性缺少值的百分比变化很大时，它的效果非常差。人工填写空缺值：工作量大，可行性低使用一个全局变量填充空缺值：比方使用unknown或-使用属性的平均值填充空缺值使用与给定元组属同一类的所有样本的平均值使用最可能的值填充空缺值：使用像使用最可能的值填充空缺值：使用像BayesianBayesian公公式或判定树这样的基于推断的方法式或判定树这样的基于推断的方法噪声数据噪声：一个测量变量中的随机错误或偏差引起不正确属性值的原因数据收集工具的问题数据输入错误数据传输错误技术限制命名规则的不一致其

11、它需要数据清理的数据问题重复记录不完整的数据不一致的数据如何处理噪声数据分箱分箱: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 b

12、y fitting the data into regression 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 dominat

13、e presentationSkewed data is 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

14、箱2：21，21，24箱3：25，28，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通过构造函数来符合数据变化的趋势，这样可以用一个变量预测另一个变量。线性回归 多线性回归非线性回归xyy=x+1X1Y1Y1数据集成实体识别元数据可帮助防止错误知识图谱属性冗余相关分析数据重复元组冗余数据值冲突的检测与处理表示、比

15、例或编码不同数据变换标准化平滑：去掉数据中的噪声。技术包括分箱、回归、聚类。聚集：对数据进行汇总或聚集。数据泛化概化：使用概念分层，用高层概念替换低层或“原始数据。标准化：将属性数据按比例缩放，使之落入一个小的特定区间。最小-最大、Z-Score、按小数定标标准化。数据变换平滑，聚集数据概化，标准化属性构造特征构造有限区间的归一化：无限区间的归一化：模糊隶属度：数据规约海量数据 代表性数据对海量数据进行复杂的数据分析和挖掘将需要很长时间，使得这种分析不现实或不可行。数据归约技术可以用来得到数据集的归约表示，它小得多，但仍接近保持原数据的完整性。对归约后的数据集挖掘将更有效，并产生相同或几乎相同

16、的结果。数据规约数据归约策略：1数据立方体聚集：对数据立方体做聚集操作2属性子集选择：检测并删除不相关、弱相关或冗余的属性和维。3维度归约：删除不重要的属性4数值归约：用规模较小的数据表示、替换或估计原始数据5离散化和概念分层产生属性的原始数值用区间值或较高层的概念替换数据立方体据立方体存储多维聚集信息，提供对预计算的汇总数据进行快速访问。如：立方体内存储季度销售额，假设对年销售额感兴趣，可对数据执行聚集操作，例如sum等。属性子集选择通过删除不相关或冗余的属性或维减小数据集。其目标是找出最小属性集，使得数据类的概率分布尽可能地接近使用所有属性得到的原分布。通过穷举搜索找出有属性的最正确子集是

17、不现实的。通常采用压缩搜索空间的启发式算法。如贪心算法：从局部最优到全局最优。逐步向前选择逐步向后删除向前选择和向后删除的结合决策树归纳维度规约维度归约使用数据编码或变换，以便得到原数据的归约或“压缩表示。分为无损和有损两种。主要方法：串压缩：无损，但只允许有限的数据操作。小波变换DWT：有损，适合高维数据。主成分分析PCA：有损，能更好地处理稀疏数据。数值规约通过选择替代的、“较小的数据表示形式来减少数据量。可以分为参数方法和非参数方法。参数方法：回归regression 和对数线性模型非参数方法：直方图、聚类、抽样离散化离散化的用途：1适应某些仅接受离散值的算法；2减小数据的尺度。离散化的

18、方法包括几下几种。1等距分割；2聚类分割；3直方图分割；4基于熵的分割；5基于自然属性的分割。抽样用数据的小得多的随机样本子集不是大型数据集。抽样方法s个样本无放回简单随机抽样s个样本有放回简单随机抽样聚类抽样分层抽样分类分类分类是指将数据映射到预先定义好的群组或类。在分析测试数据之前，类别就已经被确定了，所以分类统称被称作有指导的学习。分类算法要求基于数据属性来定义类别。分类算法通常通过观察所属类别的数据的特征来描述类别。分类应用分类具有广泛的应用，例如医疗诊断、信用卡系统的信用分级、图像模式识别等。为了识别乘客是否是潜在的 分子或罪犯，机场安全摄像站需要对乘客的脸部进行扫描并辨识脸部的基本

19、模式例如双眼间距、嘴的大小及形状、头的形状，然后将得到的模式与数据库中的 分子或罪犯的模式进行逐个比较，看看是否与其中的某一模式相匹配。分类步骤1建立一个模型，描述预定的数据类集或概念集数据元组也称作样本、实例或对象。为建立模型而被分析的数据元组形成训练数据集。训练数据集中的单个元组称作训练样本，假定每个元组属于一个预定义的类，由一个称作类标号。通过分析训练数据集来构造分类模型，可用分类规则、决策树或数学公式等形式提供。2.使用模型进行分类首先评估模型分类法的预测准确率。p将的类标号与该样本的学习模型类预测比较p准确率等于测试集的样本中被模型正确分类的百分比p测试集应该与训练集的内容相互独立，

20、否则会出现过分适应的情况如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行分类。1模型的构建TrainingDataClassificationAlgorithmsIF rank=professorOR years 6THEN tenured=yes Classifier(Model)NAME RANKYEARSTENUREDMikeAssistant Prof3noMaryAssistant Prof7yesBill Professor2yesJimAssociate Prof7yesDaveAssistant Prof6noAnneAssociate Prof3no2

21、利用模型分类ClassifierTestingDataUnseen Data(Jeff,Professor,4)Tenured?分类方法评价预测的准确率l这涉及模型正确地预测新的或先前未见过的数据的类标号的能力速度l构造模型的速度l利用模型进行分类的速度强壮性l给定噪声数据或具有空缺值的数据，模型正确预测的能力可伸缩性l当给定大量数据时，有效地构造模型的能力可解释性 l涉及学习模型提供的理解和洞察的层次分类器性能评价方式准确率和召回率-混淆矩阵等给定一个类Cj和一个数据库元组ti，ti可能被分类器判定为属于Cj或不属于Cj，其实ti本身可能属于Cj或不属于Cj，这样就会产生如下一些情况：真正:

22、判定ti在Cj中，实际上确实在其中。假正:判定ti在Cj中，实际上不在其中。真负:判定ti不在Cj中，实际上不在其中。假负:判定ti不在Cj中，实际上确实在其中。准确率:P=A/A+B召回率:R=A/A+C评估分类方法的准确性保持方法给定数据随机划分为两个集合：训练集2/3和测试集1/3训练集导出分类法，测试集对其准确性进行评估k-折交叉验证初始数据被划分为k个不相交的，大小大致相同的子集S1,S2Sk进行k次训练和测试，第i次时，以Si做测试集，其他做训练集准确率为k次迭代正确分类数除以初始数据集样本总数分类方法基于距离的分类方法与一个类中的成员和另一个类中的成员之间的相似性相比，被映射到同

23、一个类中的成员彼此之间被认为是更加相似的。相似性距离度量可以用来识别数据库中不同成员之间的“相似程度。基于距离的分类方法的直观解释a类定义类定义b待分类样例待分类样例c分类结果分类结果距离计算方法闵可夫斯基距离:当p=2时，为欧几里得距离当p=1时，为曼哈顿距离当p-时，为切比雪夫距离向量内积：夹角余弦：Jaccard：还有信息熵、相关系数等其他的度量方法基于距离的分类方法的一般性描述算法算法 基于距离的分类算法基于距离的分类算法输入：每个类的中心输入：每个类的中心C1，Cm；待分类的元组；待分类的元组t。输出：输出类别输出：输出类别c。1dist=；/距离初始化距离初始化2FOR i:=1

24、to m DO 3 IF disci，tdist THEN BEGIN4cCi；5distdistCi，t；6 END.算法通过对每个元组和各个类的中心来比较，从而可算法通过对每个元组和各个类的中心来比较，从而可以找出他的最近的类中心，得到确定的类别标记。以找出他的最近的类中心，得到确定的类别标记。K近邻算法KNNK K Nearest Nearest neighborneighborKNNKNN通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的K个训练数据，K个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类别。训练样本用n维数值属性描述。每个样本代表n维空间的一个点。

25、所有的训练样本都放在n维模式空间中。给定一个样本，k-最临近分类法搜索模式空间，找出最接近未知样本的k个训练样本。K近邻算法KNN要求的信息要求的信息训练集训练集距离计算值距离计算值要获取的最邻近的邻居的数目要获取的最邻近的邻居的数目k k一个未知的记录进行分类一个未知的记录进行分类计算与其它训练记录之间的距离计算与其它训练记录之间的距离识别出识别出k k个最近的邻居个最近的邻居使用最近邻居的类标号来标识未知元组的类使用最近邻居的类标号来标识未知元组的类by taking by taking majority votemajority voteK近邻算法KNN算法算法 K-近邻分类算法近邻分类

26、算法输入：输入：训练数据训练数据T；近邻数目；近邻数目K；待分类的元组；待分类的元组t。输出：输出：输出类别输出类别c。1N=；2FOR each d T DO BEGIN3 IF|N|K THEN4 N=Nd；5 ELSE6 IF uN such that simt，u40000高负债高负债工作时间工作时间5年年是是否否是是否否“年收入大于￥40000并且“高负债的用户被认为是“高风险；“年收入小于￥40000但“工作时间大于5年的申请，是“低风险；NYYNNY决策树buys_ puter的决策树示意的决策树示意 Age?Credit_rating?student?yesnoyesyesno

27、403040yesnofairexcellent决策树l决策树决策树decision treedecision treel19861986年年 Quinlan Quinlan提出了著名的提出了著名的ID3ID3算法。算法。l在在ID3ID3算法的基础上，算法的基础上，19931993年年QuinlanQuinlan又提出了又提出了C4.5C4.5算法。算法。l为了适应处理大规模数据集的需要，后来又提出了假为了适应处理大规模数据集的需要，后来又提出了假设干改进的算法，其中设干改进的算法，其中SLIQ SLIQ super-vised learning in super-vised learnin

28、g in questquest和和SPRINT SPRINT scalable scalable parallelizableparallelizable induction induction of of decision treesdecision trees是比较有代表性的两个算法。是比较有代表性的两个算法。决策树的步骤使用决策树进行分类分为两步：使用决策树进行分类分为两步：第1步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。第2步：利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性值，直到到达某

29、个叶结点，从而找到该记录所在的类。决策树算法递归执行的终止条件停止分支的条件算法递归执行的终止条件停止分支的条件对于给定的节点，所有的例子都属于同一个类对于给定的节点，所有的例子都属于同一个类虽然对于某一个节点当前的例子不属于同一个类，但虽然对于某一个节点当前的例子不属于同一个类，但是已经没有属性可用来选择继续进行分支处理是已经没有属性可用来选择继续进行分支处理分裂属性选择选择属性的方法选择属性的方法选择具有最大信息增益的属性作为当前节点的选择具有最大信息增益的属性作为当前节点的测试属性测试属性该属性使得对结果划分中的样本分类所需的信该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分

30、的最小随机性。息量最小，并反映划分的最小随机性。用信息增益这种信息论的理论方法，使得对一用信息增益这种信息论的理论方法，使得对一个对象分类所需要的期望测试数目到达最小，个对象分类所需要的期望测试数目到达最小，并确保找到一棵简单的树。并确保找到一棵简单的树。分裂属性选择怎样计算信息增益怎样计算信息增益information gaininformation gain信息增益被定义为原始分割的熵与划分以后各信息增益被定义为原始分割的熵与划分以后各分割的熵累加得到的总熵之间的差。分割的熵累加得到的总熵之间的差。信息增益是指划分前后进行正确预测所需的信信息增益是指划分前后进行正确预测所需的信息量之差。息

31、量之差。选择具有最高信息增益的属性作为当前节点的选择具有最高信息增益的属性作为当前节点的测试属性。测试属性。信息增益的计算 设S是有s个训练样本数据的集合，类标号属性具有m个不同值，定义m个不同类Cii=1,2,m，si是类Ci中的样本数，则对一个给定的训练样本分类所需要的期望信息为：其中其中p pi i是任意样本属于是任意样本属于C Ci i的概率，可用的概率，可用s si i/s/s来估计来估计决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良

32、买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买决策属性“买计算机？。该属性分两类：买/不买S1买=641 S2不买=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740IS1,S2=I641,383 =-P1Log2P

33、1-P2Log2P2 =-P1Log2P1+P2Log2P2 =0.9537第第1步计算决策属性的熵步计算决策属性的熵决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2步计算条件属性的熵步计算条件属性的熵条件属性共有4个。分别是年龄、收入、学生、信誉。分别计算不同属性的信息增益。决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不

34、买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-1步计算年龄的熵步计算年龄的熵年龄共分三个组：青年、中年、老年青年买与不买比例为128/256S1买=128 S2不买=256S=S1+S2=384P1=128/384P2=256/384IS1,S2=I128,256 =-P1Log2P1-P2Log2P2 =-P1Log2P1+P2Log2P2 =0.9183决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64

35、青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-2步计算年龄的熵步计算年龄的熵年龄共分三个组：青年、中年、老年中年买与不买比例为256/0S1买=256 S2不买=0S=S1+S2=256P1=256/256P2=0/256IS1,S2=I256，0 =-P1Log2P1-P2Log2P2 =-P1Log2P1+P2Log2P2 =0决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64

36、青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-3步计算年龄的熵步计算年龄的熵年龄共分三个组：青年、中年、老年老年买与不买比例为125/127S1买=125 S2不买=127S=S1+S2=252P1=125/252P2=127/252IS1,S2=I125，127 =-P1Log2P1-P2Log2P2 =-P1Log2P1+P2Log2P2 =0.9157决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否

37、良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-4步计算年龄的熵步计算年龄的熵年龄共分三个组：青年、中年、老年所占比例青年组 384/1025=0.375中年组 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决策树算法计数年龄收入学生

38、信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第3步计算收入的熵步计算收入的熵收入共分三个组：高、中、低E收入=0.9361收入信息增益=0.9537-0.9361 =0.0176 2决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良

39、买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第4步计算学生的熵步计算学生的熵学生共分二个组：学生、非学生E学生=0.7811年龄信息增益=0.9537-0.7811 =0.1726 3决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第5步计算信誉的熵步计算信誉的熵信誉分二个组：良好，优秀E信誉=0.9048信

40、誉信息增益=0.9537-0.9048 =0.0453 4决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买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.904

41、8 =0.0453 4决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买年龄年龄青年中年老年买/不买买买/不买叶子决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买青年买与不买比例为128/256S1买=128 S2不买=256S=S1+S2=384P1=128/384P2=256/384IS1,S2=I128,256 =-P1Log2P1-P2Log2P2 =-P1Log2P1+P2Log2P2 =0.9183决策

42、树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买如果选择收入作为节点分高、中、低平均信息期望加权总和：E收入=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain收入=I128,256-E收入=0.9183 0.4592=0.4591I0,128=0 比例:128/384=0.3333I64,128=0.9183 比例:192/384=0.5I64,0=0比例:64/384=0.1667 注意决策树算法计数年龄收入学生信誉归类：买计算机归类：买计算机？64青高否良不买64青高否优不

43、买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买年龄年龄青年中年老年学生买信誉叶子否否是是优优良良买不买买/不买买叶子叶子叶子决策树分类规则提取决策树所表示的分类知识可以被抽取出来并可用IF-THEN 分类规则形式加以表示。从决策树的根结点到任一个叶结点所形成的一条路径就构成了一条分类规则。沿着决策树的一条路径所形成的属性-值对就构成了分类规则条件局部IF 局部中的一个合取项，叶结点所标记的类别就构成了规则的结论内容THEN 局部。IF-THEN分

44、类规则表达方式易于被人理解，且当决策树较大时，IF-THEN规则表示形式的优势就更加突出。贝叶斯分类贝叶斯分类贝叶斯定理 贝叶斯定理给出了如下计算PC|X的简单有效的方法:PC:是先验概率，或称C的先验概率。PX:样本数据被观察的概率。PX|C代表假设C成立的情况下，观察到X的概率。PC|X是后验概率，或称条件X下C的后验概率。后验概率PC|X 比先验概率PC基于更多的信息。PC是独立于X的。朴素贝叶斯分类l朴素贝叶斯分类的工作过程如下：1每个数据样本用一个n维特征向量X=x1,x2xn表示，分别描述n个属性A1，An样本的n个度量。2假定有m个类C1，C2，Cm，给定一个未知的数据样本X即没

45、有类标号，分类器将预测X属于具有最高后验概率条件X下的类。朴素贝叶斯分类将未知的样本分配给类Ci1im当且仅当PCi|XPCj|X，ji。即最大化PCi|XPCi|X最大的类Ci称为最大后验假定。朴素贝叶斯分类3由于PX对于所有类为常数，PX|Ci*PCi最大即可。如果Ci类的先验概率未知，则通常假定这些类是等概率的，即PC1=PC2=PCm，因此问题就转换为对PX|Ci的最大化PX|Ci常被称为给定Ci时数据X的似然度，而使PX|Ci最大的假设Ci称为最大似然假设。否则，需要最大化PX|Ci*PCi。类的先验概率可以用PCi=si/s计算，其中si是类Ci中的训练样本数，而s是训练样本总数。

46、朴素贝叶斯分类4给定具有许多属性的数据集，计算PX|Ci的开销可能非常大。为降低计算PX|Ci的开销，可以做类条件独立的朴素假定。给定样本的类标号，假定属性值相互条件独立，即在属性间，不存在依赖关系。这样概率Px1|Ci，Px2|Ci，Pxn|Ci由训练样本估值。-如果Ak是离散属性，则Pxk|Ci=sik/si，其中sik是在属性Ak上具有值xk的类Ci的训练样本数，si是Ci中的训练样本数。-如果Ak是连续值属性，常用的处理方法有两种：一是对其离散化，然后按照离散值处理；另一种假定这一属性服从某一分布，通常假定该属性服从高斯分布。5对未知样本X分类，也就是对每个类Ci，计算PX|Ci*PC

47、i。样本X被指派到类Ci，当且仅当PCi|X PCj|X，1jm，ji。即X被指派到其PX|Ci*PCi最大的类。朴素贝叶斯分类举例希望分类的未知样本为希望分类的未知样本为:X=age=“=30，in e=“medium，student=“yes，credit_rating=“fair思路思路:计算每一个类的计算每一个类的PCi|X=PX|CiPCi/PX,Ci代代表任意一个类，表任意一个类，X代表代表需要判断的查询条件需要判断的查询条件朴素贝叶斯分类举例设 C1对应于类buys_ puter=“yes，C2对应于类buys_ puter=“no。1 需要最大化PX|Ci*PCi，i=1，2。

48、每个类的先验概率PCi可以根据训练样本计算：Pbuys_ puter=yes=9/14=0.643，Pbuys_ puter=no=5/14=0.357。朴素贝叶斯分类举例2 为计算PX|Ci，i=1，2，计算下面的条件概率：Page=30|buys_ puter=“yes=2/9=0.222，Page=30|buys_ puter=“no=3/5=0.600，Pin e=“medium|buys_ puter=“yes=4/9=0.444，Pin e=“medium|buys_ puter=“no=2/5=0.400，Pstudent=“yes|buys_ puter=“yes=6/9=0.

49、677，Pstudent=“yes|buys_ puter=“no=1/5=0.200，Pcredit_rating=“fair|buys_ puter=“yes=6/9=0.667，Pcredit_rating=“fair|buys_ puter=“no=2/5=0.400。朴素贝叶斯分类举例 3 假设条件独立性，使用以上概率，得到：PX|buys_ puter=“yes=0.222*0.444*0.667*0.667=0.044，PX|buys_ puter=“no=0.600*0.400*0.200*0.400=0.019，PX|buys_ puter=“yes*Pbuys_ puter

50、=“yes=0.044*0.643=0.028，PX|buys_ puter=“no*Pbuys_ puter=“no=0.019*0.357=0.007。因因此，对于样本此，对于样本X，朴素贝叶斯分类预测朴素贝叶斯分类预测buys_ puter=“yesX=age=“Head support,confidencebuysx,“diapers=buysx,“beers 0.5%,60%majorx,“CS takesx,“DB=gradex,“A 1%,75%规则度量：支持度与可信度规则度量：支持度与可信度查找所有的规则 X&Y=Z 具有最小支持度和可信度支持度,s,一次交易中包含X、Y、Z的