数据挖掘算法培训讲义-分类和预测课件

DM算法-1

分类和预测

出处：《数据挖掘：概念与技术》

©JiaweiHanandMichelineKamber2022/12/91数据挖掘：概念与技术（翻译张磊）DM算法-1分类和预测什么是分类?什么是预测?关于分类与预测的问题通过决策树归纳来分类贝叶斯分类通过反向传播来分类基于关联规则挖掘的概念来分类其它分类方法预测分类准确率总结2022/12/92数据挖掘：概念与技术（翻译张磊）分类:

预测分类标签基于训练集和分类属性值(分类标签)构造分类模型，然后用该模型分类新数据预测:对连续函数建模,即预测未知的或缺失的数据典型应用信用审核目标营销医疗诊断治疗效果分析分类与预测2022/12/93数据挖掘：概念与技术（翻译张磊）分类过程(1):模型创建训练数据分类算法IFrank=‘professor’ORyears>6THENtenured=‘yes’分类器(模型)2022/12/95数据挖掘：概念与技术（翻译张磊）分类过程(2):使用模型来预测分类器测试数据新数据(Jeff,Professor,4)Tenured?2022/12/96数据挖掘：概念与技术（翻译张磊）有指导的vs.无指导的学习有指导的学习(分类)指导:模型的学习在被告知每个训练样本属于哪个类的“指导”下进行基于训练集对新数据进行分类无指导的学习

(聚类)训练数据的类标签是未知的给定一组样本,试图建立分类或数据的聚类2022/12/97数据挖掘：概念与技术（翻译张磊）DM算法-1分类和预测什么是分类?什么是预测?关于分类与预测的问题通过决策树归纳来分类贝叶斯分类通过反向传播来分类基于关联规则挖掘的概念来分类其它分类方法预测分类准确率总结2022/12/98数据挖掘：概念与技术（翻译张磊）分类与预测的相关问题(2):分类方法的评估预测准确率速度和扩展能力创建模型所需时间应用模型所需时间健壮性可以处理噪声和缺失值扩展能力在大型数据库上的处理能力可解释性模型能否增强用户对数据的理解和洞察力是否良好的规则决策树的大小分类规则的简洁程度2022/12/910数据挖掘：概念与技术（翻译张磊）通过决策树归纳进行分类决策树类似于流程图的树型结构内部节点代表对某个属性的一次测试分支代表测试的输出结果叶节点代表分类标签或分布决策树的生成包括两个阶段树的创建首先,所有训练样本都位于根节点递归地基于选择属性来划分样本集树的修剪识别并删除那些反映噪声或孤立点的分支应用决策树:对未知样本进行分类在决策树上测试样本的各个属性值2022/12/912数据挖掘：概念与技术（翻译张磊）输出:预测“是否会购买计算机”的决策树age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..402022/12/914数据挖掘：概念与技术（翻译张磊）决策树归纳算法基本算法(贪婪算法)树的创建是一种自顶向下递归的分而治之方法首先,所有训练样本都位于根节点属性都是类别型变量(若为连续值,则需先离散化)基于选择的属性,对样本进行递归划分通过启发式搜索或统计量来选取测试属性(例如,信息增益)停止划分的条件对于某个给定节点,所有样本都属于同一分类没有剩余属性可供进一步划分–按照少数服从多数的原则来确定叶节点的分类所有样本都已分类完毕2022/12/915数据挖掘：概念与技术（翻译张磊）属性选取的度量信息增益

(ID3/C4.5)所有属性应为类别型变量可以通过改进来处理连续值属性Gini索引(IBMIntelligentMiner)所有属性应为连续值变量对于每个属性,假定已存在若干可能的切分点可能需要其它工具(如聚类)的辅助来获取切分点可以通过改进来处理类别型属性2022/12/916数据挖掘：概念与技术（翻译张磊）信息增益(ID3/C4.5)选取具有最高信息增益的属性假定存在两个分类,P

和N样本集S中包含p个样本属于类别P,n个样本属于类别N用于判别S中任意样本属于类别P

或N

的信息量,定义为2022/12/917数据挖掘：概念与技术（翻译张磊）决策树归纳中的信息增益假定通过属性A可以将样本集S划分为多个集合{S1,S2,…,Sv}如果Si

包含pi

个P类样本和ni

个N类样本,熵,或将S所有子树中的对象进行分类所需的期望信息i

定义为在A上分枝将获得的编码信息是2022/12/918数据挖掘：概念与技术（翻译张磊）Gini

索引(IBMIntelligentMiner)如果数据集T

包含n种类别的样本,giniindex,gini(T)定义如下

其中pj

是类别j

在T中所占的百分比如果数据集T

被划分为两个子集T1

和T2,大小分别为N1

和N2,该划分的giniindexgini(T)定义为选取具有最小ginisplit(T)的属性,对T进行分裂(对每个属性,需枚举出所有可能的切分点).2022/12/920数据挖掘：概念与技术（翻译张磊）从树中抽取分类规则用IF-THEN规则来作为知识表示从根节点到叶节点的每条路径,对于于一条规则路径上的每个(属性-值)对被联合起来叶节点给出了类别预测规则非常易懂示例IFage=“<=30”ANDstudent=“no”THENbuys_computer=“no”IFage=“<=30”ANDstudent=“yes”THENbuys_computer=“yes”IFage=“31…40” THENbuys_computer=“yes”IFage=“>40”ANDcredit_rating=“excellent”THENbuys_computer=“yes”IFage=“>40”ANDcredit_rating=“fair”THENbuys_computer=“no”2022/12/921数据挖掘：概念与技术（翻译张磊）决定最终树大小的方法将数据集的2/3作为训练集,1/3作为测试集使用交叉验证,例如,10-fold交叉验证使用全部数据来训练但运用统计检验(例如,chi-square)来估计对某个节点的分裂或修剪是否能改善整体分布使用最小描述长度(MDL)原则:当编码量达到最小时停止树的生长2022/12/923数据挖掘：概念与技术（翻译张磊）决策树归纳的改进允许处理连续值属性动态地对连续属性值离散化(划分为若干区间)处理缺失的属性值赋以最常见的属性值计算各种取值的概率属性创建基于树中很少出现的那些属性,创建新的属性(例如对类别型变量分组,因为信息增益偏向于取值多的属性)避免碎片(过细的分支),重复(属性在路径上被多次测试)和复制(出现相同子树)2022/12/924数据挖掘：概念与技术（翻译张磊）DM算法-1分类和预测什么是分类?什么是预测?关于分类与预测的问题通过决策树归纳来分类贝叶斯分类通过反向传播来分类基于关联规则挖掘的概念来分类其它分类方法预测分类准确率总结2022/12/926数据挖掘：概念与技术（翻译张磊）贝叶斯分类:为什么?概率学习:计算假设的先验概率,是处理某些学习问题的常见方法递增的:每个训练样本可以逐步增加/降低假设正确的概率.已有知识可以与观察数据合并.概率预测:对多个假设进行预测,根据概率赋于不同权重标志的:尽管贝叶斯分类方法不容易实施,它们依然可以提供决策制定的优化标准,对其它方法进行评估2022/12/927数据挖掘：概念与技术（翻译张磊）贝叶斯定理给定训练数据D,假设h的后验概率,P(h|D)满足贝叶斯定理MAP(最大后验概率)假设难以实施:需要首先知道多个概率,计算开销大2022/12/928数据挖掘：概念与技术（翻译张磊）朴素贝叶斯分类器(II)给定一个训练集,可以计算如下概率2022/12/930数据挖掘：概念与技术（翻译张磊）贝叶斯分类分类问题被形式化为计算后验概率:计算P(C|X)=元组X(=<x1,…,xk>)属于类别C的概率例如P(类别=N|outlook=sunny,windy=true,…)主要思想:将样本X分类到P(C|X)取最大值的类别标签C2022/12/931数据挖掘：概念与技术（翻译张磊）后验概率的估计贝叶斯定理:P(C|X)=P(X|C)·P(C)/P(X)对于所有类别来说,P(X)是不变的P(C)=属于类别C的样本占总体的比率使得P(C|X)取最大值的类别C=

使得P(X|C)·P(C)取最大值的类别C问题:要计算P(X|C)并不容易!2022/12/932数据挖掘：概念与技术（翻译张磊）朴素贝叶斯分类朴素假设:属性无关性P(x1,…,xk|C)=P(x1|C)·…·P(xk|C)如果第i个属性是类别型属性:

将P(xi|C)估计为类别C中第i个属性取值为xi的样本所占百分比如果第i个属性是连续型属性:

将P(xi|C)估计为其高斯密度函数两种情况下都容易计算出来2022/12/933数据挖掘：概念与技术（翻译张磊）“去不去打网球”示例:估计P(xi|C)outlookP(sunny|p)=2/9P(sunny|n)=3/5P(overcast|p)=4/9P(overcast|n)=0P(rain|p)=3/9P(rain|n)=2/5temperatureP(hot|p)=2/9P(hot|n)=2/5P(mild|p)=4/9P(mild|n)=2/5P(cool|p)=3/9P(cool|n)=1/5humidityP(high|p)=3/9P(high|n)=4/5P(normal|p)=6/9P(normal|n)=2/5windyP(true|p)=3/9P(true|n)=3/5P(false|p)=6/9P(false|n)=2/5P(p)=9/14P(n)=5/142022/12/934数据挖掘：概念与技术（翻译张磊）“去不去打网球”示例:对X分类未知样本X=<rain,hot,high,false>P(X|p)·P(p)=

P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p)=3/9·2/9·3/9·6/9·9/14=0.010582P(X|n)·P(n)=

P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n)=2/5·2/5·4/5·2/5·5/14=0.018286样本X被分类为类别n(不去打网球)2022/12/935数据挖掘：概念与技术（翻译张磊）无关性假设……方便了计算…当假设满足时可以得到最佳的分类器…但实际上该假设很难满足,因为属性(变量)常常是相关的克服限制的做法:贝叶斯网络,将贝叶斯推理和属性间的因果关系相结合决策树,每次仅对单个属性进行判断,首先考虑最重要的属性2022/12/936数据挖掘：概念与技术（翻译张磊）贝叶斯信念网络(I)家族病史肺癌X光透视为+烟民肺气肿呼吸困难LC~LC(FH,S)(FH,~S)(~FH,S)(~FH,~S)0.80.20.50.50.70.30.10.9贝叶斯信念网络肺癌(LungCancer)变量的条件概率2022/12/937数据挖掘：概念与技术（翻译张磊）贝叶斯信念网络(II)贝叶斯信念网络允许变量子集是条件无关的因果关系的图模型在以下情况下训练贝叶斯信念网络(权重的计算)给定网状结构和全部变量:容易给定网状结构和部分变量(梯度下降方法)事先未知网状结构2022/12/938数据挖掘：概念与技术（翻译张磊）DM算法-1分类和预测什么是分类?什么是预测?关于分类与预测的问题通过决策树归纳来分类贝叶斯分类通过反向传播来分类基于关联规则挖掘的概念来分类其它分类方法预测分类准确率总结2022/12/939数据挖掘：概念与技术（翻译张磊）神经网络优点预测准确率一般较高稳定,可以适应包含脏数据的训练样本可以输出离散值,连续值,或者由多个(离散或连续)属性组成的向量对训练好的模型可以快速评估缺点训练时间长模型(权重)难以理解难以结合领域知识2022/12/940数据挖掘：概念与技术（翻译张磊）神经元通过向量积和非线性函数,将n维输入向量x

映射到向量ymk-f加权求和输入向量x输出y激活函数权重向量wåw0w1wnx0x1xn2022/12/941数据挖掘：概念与技术（翻译张磊）训练神经网络训练的最终目标得到一组权重,使得训练集中的绝大多数元组可以被正确分类步骤用随机数来初始化权重逐个处理元组,作为神经网络的输入层对于每个单元计算该单元全部输入的线性组合,作为其净输入使用激活函数来计算该单元的输出值误差的计算调整权重和偏置2022/12/942数据挖掘：概念与技术（翻译张磊）多层感知器输出层节点输入层节点隐层节点输出向量输入向量:xiwij2022/12/943数据挖掘：概念与技术（翻译张磊）网络修剪与规则抽取网络修剪完全连接的网络难以解释N

个输入节点,h

个隐层节点和m

个输出节点的网络具有h(m+N)

个权重修剪:删除那些对网络分类准确率影响很小的连接从训练好的神经网络中抽取规则对活跃值进行离散化;用聚类来替代单个活跃值,同时保证一定的网络准确率根据这些活跃值来枚举出全部输出值,从而可以总结出活跃值和输出值间的关系发现输入值和活跃值的关系综合以上两个步骤,产生输入值和输出值之间的规则(关系)2022/12/944数据挖掘：概念与技术（翻译张磊）DM算法-1分类和预测什么是分类?什么是预测?关于分类与预测的问题通过决策树归纳来分类贝叶斯分类通过反向传播来分类基于关联规则挖掘的概念来分类其它分类方法预测分类准确率总结2022/12/945数据挖掘：概念与技术（翻译张磊）其它分类方法K-近邻分类器(k-nearestneighborclassifier)基于案例的推理(case-basedreasoning)遗传算法 (Geneticalgorithm)粗糙集方法 (Roughsetapproach)模糊集方法 (Fuzzysetapproaches)2022/12/946数据挖掘：概念与技术（翻译张磊）基于实例的方法基于实例的学习:保存训练样本并延迟处理(“懒惰的评估”),知道需要对新的实例进行分类时再进行学习常见方法k近邻方法用欧式空间中的点来代表实例局部加权回归构造局部估计值基于案例的推理使用符号表达方式和基于知识的推理2022/12/947数据挖掘：概念与技术（翻译张磊）K-近邻算法所有实例都对应于n维空间中的点根据欧式距离来定义最近的邻居目标函数可以输出离散值或连续值对于离散值,k-NN返回xq的k个近邻中最常见的值Vonoroi图:决策面由某个典型训练集的1-NN决定.

._+_xq+__+__+.....2022/12/948数据挖掘：概念与技术（翻译张磊）k-NN算法讨论k-NN算法对连续值的处理计算k

近邻的均值加权距离的近邻算法根据每个邻居和查询点xq之间的距离予以加权越近的邻居,权重越大对于实数值的处理与之类似由于用k个近邻来判别,因此在脏数据上表现稳定维度的负面影响:无关属性可能会严重影响距离的准确计算可以拉伸坐标轴或者除去最不相关的属性2022/12/949数据挖掘：概念与技术（翻译张磊）基于案例的推理(CBR)同样采用:

懒惰评估+分析类似实例差异:

实例不再是“欧式空间中的点”示例:CADET中的水龙头问题(Sycaraetal’92)方法使用符号描述来表示实例(例如,功能图)合并多个检索出来的案例案例检索,基于知识的推理,和问题解决的紧密耦合研究问题基于句法相似度的索引技术,如果解答之间出现不相容，可能需要退回搜索其它解2022/12/950数据挖掘：概念与技术（翻译张磊）评论懒惰学习和积极学习基于实例的学习:

懒惰评估决策树和贝叶斯分类:积极学习主要差异懒惰方法进行决策时要在训练集D上对新实例xq查询积极方法则不需要,因为它们已经有了全局估计效率:懒惰学习-训练时间短,但预测所需时间长准确率懒惰方法可以有效利用一个更广阔的假设空间,因为采用了多个局部线性函数来构造出目标函数的全局估计积极方法:必须对整个实例空间提交单个假设,来覆盖整个空间2022/12/951数据挖掘：概念与技术（翻译张磊）遗传算法GA:基于对生物进化的模拟每个规则用位串(stringofbits)表达创建一个由随机产生的规则组成的初始群体例如,规则”IFA1andNotA2thenC2”,可被编码为100根据适者生存的原则,形成由当前群体中最适合的规则组成新的群体,以及这些规则的子女规则的适应程度,用它对训练样本集的分类准确率评估子女通过使用诸如交叉和变异等遗传操作来创建2022/12/952数据挖掘：概念与技术（翻译张磊）粗糙集方法粗糙集用于近似地(粗糙地)定义等价类给定类C的粗糙集定义用两个集合近似：C的下近似(确定为C类)和C的上近似(不能判断它不属于C类)找出最小属性子集(用于特征选取)是NP-难处理的,但可以使用识别矩阵存放每对数据样本属性值之间的差别,以降低计算复杂度2022/12/953数据挖掘：概念与技术（翻译张磊）模糊集方法模糊逻辑使用0.0和1.0之间的真值(truthvalue)表示一个特定的值属于给定类的程度，而不是用类或集合的精确截断(例如使用模糊关系图)属性值被转换为模糊值例如,将连续属性”收入”的值映射到离散分类{low,medium,high}上,并计算模糊成员关系或真值一个给定值可以对应多个模糊值每个可用规则对样本的分类进行投票组合上面得到的和,得到一个系统返回的值2022/12/954数据挖掘：概念与技术（翻译张磊）DM算法-1分类和预测什么是分类?什么是预测?关于分类与预测的问题通过决策树归纳来分类贝叶斯分类通过反向传播来分类基于关联规则挖掘的概念来分类其它分类方法预测分类准确率总结2022/12/955数据挖掘：概念与技术（翻译张磊）什么是预测?预测和分类相似首先,建立一个模型然后,使用模型来预测未知值主要的预测方法是回归线性和多元回归非线性回归预测和分类不同分类用于预测类别标签预测对连续函数建模2022/12/956数据挖掘：概念与技术（翻译张磊）建立预测模型:预测数据的取值,或者是基于数据库中的数据建立泛化的线性模型只能预测值域或类别分布一般步骤:

最小的泛化

属性相关分析

创建泛化的线性模型

预测识别出对预测产生影响的主要因子数据相关分析:不确定性度量,熵分析,专家判断,等待多层次预测:下钻和上卷分析数据库中建立预测模型2022/12/957数据挖掘：概念与技术（翻译张磊）线性回归:Y=+X两个参数,和决定一条直线.可以根据数据估计出这两个参数的值在已知数据Y1,Y2,…,X1,X2,…上使用最小二乘法求解多元回归:Y=b0+b1X1+b2X2.很多非线性函数可转换为上述形式对数-线性模型:通过低阶表的乘积来近似出联合概率多路表概率:p(a,b,c,d)=abacadbcd预测中的回归分析和对数-线性模型2022/12/958数据挖掘：概念与技术（翻译张磊）局部加权回归在查询实例xq附近的局部区域创建f的显式近似局部加权线性回归:在xq附近用线性函数来近似目标函数f:最小化平方误差:距离递减的权重K梯度下降训练法:大多数情况下,目标函数被近似为常数、线性函数或二次函数2022/12/959数据挖掘：概念与技术（翻译张磊）预测:数值型数据2022/12/960数据挖掘：概念与技术（翻译张磊）预测:类别型数据2022/12/961数据挖掘：概念与技术（翻译张磊）DM算法-1