数据分析方法及模型PPT课件

.,1,分析技术及模型,数据预处理关联分析技术聚类分析技术分类分析技术异常分析技术贝叶斯网影响图,.,2,分析技术及模型数据预处理,.,3,数据预处理,各种数据分析技术的对象是数据源中的数据数据源中的数据可能不完整（如某些属性的值不确定或空缺）、含噪声和不一致（如同一个属性在不同表中的名称不同）、量纲不同如果直接在这些未经处理的数据上进行分析，结果不一定准确，效率也可能较低需要使用清理、集成、变换、归约等预处理方法改善数据质量，从而提高数据分析的效率与质量主要介绍数据清理、集成、变换、规约等预处理技术,.,4,数据清理,数据清理用于消除噪声、数据不一致及数据不完整噪声可以通过平滑、识别孤立点等方法进行消除分箱技术：将数据排序，根据等深或等宽分布规则将数据分布到不同箱中，将同一箱中的数据用用该箱中数据的平均值或中值、边界值替换（平均值平滑、中值平滑、边界平滑）,每个箱中的数据个数或取值区间相等,设某属性的值为18，12，3，9，7，6，15，21，16，采用分箱技术平滑数据消除噪声。分布规则为等深、深度为3，平滑规则为平均值平滑,首先，将属性的值排序为3,6,7,9,12,15,16,18,21,箱1：3,6,7箱2：9,12,15箱3：16,18,21,.,5,数据清理,数据不完整可以使用下列方法消除：1）使用一个全局常量填充2）使用属性平均值填充3）使用相同类的属性平均值填充4）使用最可能的值填充需要采用预测算法，预测给定样本的最可能的值并填充数据不一致可以通过元数据消除（描述数据的数据）,.,6,数据集成,数据集成是将多个数据源中的数据结合起来存放在一个一致的数据存储（如数据仓库）中这些数据源可能包括多个数据库、数据立方体或一般文件在数据集成时，需要消除冗余能够由另外的属性“导出”、命名的不一致的属性冗余可以通过相关分析进行检测属性A、B之间的相关性计算：rA,B0，A与B正相关，A的值随着B的值的增加而增加rA,B0，A与B负相关，A的值随着B的值的增加而减少rA,B=0，A与B独立。因此，|rA,B|很大时，A与B可以去除一个,平均值,方差,.,7,数据变换,将属性数据按比例缩放，使之落入一个小的特定区间，如1.0到1.0或0.0到1.0最小-最大规格化：minA，maxA为数值属性A规格化前的取值区间new_minA，new_maxA为A规格化后的取值区间，最小-最大规格化根据下式将A的值v规格化为值v,采用最小-最大规格化方法将100，100中的66规格化到区间0，1,.,8,数据变换,零-均值规格化：对均值为、方差为的数值属性A将A的值v规格化为值v,设某属性的平均值、标准差分别为80、25，采用零-均值规格化66,小数定标规格化：数值属性A的最大绝对值为max|A|A，j为满足的最小整数将A的值v规格化为值v,规格化100，100中的66,A的最大绝对值为120，j为3,.,9,数据规约,数据归约技术可以用来得到数据集的归约表示，它小得多，但仍接近于保持原数据集的完整性在归约后的数据集上分析将更有效，并产生相同（或几乎相同）的分析结果归约方法主要有：属性归约、记录归约属性规约：删除不相关的或冗余的属性减小数据集，目标是找出最小属性集，使得数据在其上的概率分布尽可能地接近在原属性集上的概率分布常用方法：粗糙集中的属性约简、决策树记录规约：用少量记录代表或替换原有记录，从而减小数据集常用方法：抽样、数据概化,.,10,数据规约,数据概化：采用面向属性归纳，根据属性的概念分层，通过阈值控制，将属性的低层属性值用相应高层概念替换，并合并由此得到的相同记录概念分层一般用树结构描述，称为概念层次树阈值控制面向属性归纳过程，每个属性都有概念层次树及阈值首先根据属性A的概念层次树，将关系表中A的属性值转换为最低层的相应概念（叶概念），统计关系表中A的不同叶概念个数如果A的不同叶概念个数大于A的属性阈值，再根据A的概念层次树，将关系表中A的叶概念转换为上一层的相应概念如此重复，直至关系表中A的不同概念个数小于等于A的属性阈值；最后合并相同记录，并统计重复记录数目,.,11,数据规约,属性阈值均为4记录由6个归约为3个count的值表示重复记录数目,.,12,属性概念分层的自动生成,概念分层一般由系统用户、领域专家提供，但非常耗时、乏味介绍离散属性与连续属性自动生成概念分层的方法,离散属性概念分层的自动生成,概念层次树中高层的概念个数一般少于低层的概念个数首先统计各个概念的不同值个数，个数最少的概念在最高层，依次类推，然后根据结构的从属关系，确定各层的概念及从属关系,.,13,属性概念分层的自动生成,连续属性概念分层的自动生成,连续属性可以通过离散化递归地自动生成概念分层离散化可以基于熵完成，主要步骤：1）计算关系表r中在属性A的取值区间V上的记录集合S的熵,|c|：S中属于目标类c的记录数|S|：S中的记录数,2）对A在V上取的每个v，用v划分V为v1（v）、v2（v），划分S为S1，S2，计算在此划分下S的熵,E(S1)、E(S2)分别为S1、S2的熵,.,14,属性概念分层的自动生成,连续属性概念分层的自动生成,3）对在V上的每个划分v1（v）、v2（v），计算在此划分下S的信息增益,4）选择使S的信息增益最大的划分作为最佳划分，记为V1（(llv)也不是强关联规则,证明：,sup_count(lv)sup_count(lu),i1i2i5不是强关联规则i2i1i5、i1i2i5都不可能是强关联规则,l=i1i2i5lvi1、i2lui1i2,.,37,Apriori算法,压缩强关联搜索空间,对于每个频繁项集，第一层产生后件只有一项的强关联规则，并生成它们的1-后件集合R1,第二层产生后件有两项的强关联规则，并生成它们的2-后件集合R2R2通过R1中的后件进行连接运算，再通过置信度计算产生依次类推，可以产生所有强关联规则,.,38,Apriori算法,算法描述,输入：事务集合T，最小支持度阈值min_sup，最小置信度阈值min_conf输出：强关联规则集合SR变量：频繁k-项集集合Lk，候选k-项集集合Ck，频繁项集集合L，k-后件集合Rk步骤：/频繁项集产生（1）forT中的每个事务t（1.1）fort中的每个项i（1.1.1）i.sup_count=i.sup_count+1/1-项集支持计数（2）for每个项i（2.1）ifi.sup_countnmin_supthenL1=L1i/找出频繁1-项集,.,39,Apriori算法,算法描述,（3）for(k=2；Lk-1；k+)（3.1）forLk-1中的每个项集lu（3.1.1）forLk-1中项集lu之后的每个项集lvif(lu1=lv1)(luk-2=lvk-2)(luk-1lvk-1)then/连接Ck=Ckc/找出候选k-项集forc中的每个(k-1)-项集sifthenCk=Ck-c/剪枝（3.2）forT中的每个事务t（3.2.1）fort中的每个k-项集sifsCkthens.sup_count=s.sup_count+1/k-项集支持计数,.,40,Apriori算法,算法描述,（3.3）forCk中的每个项集c（3.3.1）ifc.sup_countnmin_supthenLk=Lkc/找出频繁k-项集（3.4）L=LLk/规则产生（4）forL中的每个频繁项集l（4.1）forl中的每个1-项集l1（4.1.1）ifthenSR=SR(l-l1)=l1/找出后件只有1项的强关联规则R1=R1l1/找出1-后件,.,41,Apriori算法,算法描述,（4.2）for(j=2；Rj-1；j+)（4.2.1）forRj-1中的每个后件luforRj-1中后件lu之后的每个后件lvif(lu1=lv1)(luj-2=lvj-2)(luj-1lvj-1)then/连接ifthenSR=SR(l-lj)=lj/找出后件有j项的强关联规则Rj=Rjlj/找出j-后件,l=i1i2i5lui1lvi2,.,42,Apriori算法,影响Apriori算法时间复杂度主要因素,（1）事务集合当项数m增加：候选项集的数目和长度可能增加，频繁项集的数目和长度也可能增加，从而计算频繁项集及其支持计数的时间、扫描事务集合的次数、计算强关联规则的时间可能增加事务数n、事务平均宽度w增加：每次扫描事务集合的时间增加（2）最小支持度阈值min_supmin_sup越小，候选项集和频繁项集的数目越多、长度越长，扫描事务集合的次数越多，算法的运行时间越长（3）最小置信度阈值min_confmin_conf越小，强关联规则的数目越多，产生规则的运行时间越长,.,43,频繁项集的紧凑表示,通常，从现实事务集合中产生的频繁项集的数量庞大为了提高关联规则挖掘算法的效率，频繁项集使用紧凑表示最大频繁项集：一个频繁项集的所有直接超集都不是频繁项集由最大频繁项集可以推导所有频繁项集,频繁项集,非频繁项集,最大频繁项集,由ad可以推导频繁项集a、d和ad由bcd可以推导b、c、d、bc、bd、cd和bcd,.,44,频繁项集的紧凑表示,为了高效找出最大频繁项集，可以将搜索空间按前缀或后缀变换为树（前缀树、后缀树），然后采用宽度或深度优先策略进行搜索,前缀树,后缀树,.,45,频繁项集的紧凑表示,宽度优先是先搜索同一层的频繁项集，再搜索下一层的频繁项集深度优先是搜索到某层的一个频集时，先搜索更深层的频集，若没有频集则回溯，直至没有频项集产生也没有回溯,深度优先搜索策略可以更快地检测到频繁项集边界，通常用于搜索最大频繁项集,深度优先与最大频繁项集搜索,.,46,频繁项集的紧凑表示,最大频繁项集集合是频繁项集集合的紧凑表示由最大频繁项集可以推导所有频繁项集，但由最大频繁项集不能推导它们的支持计数闭项集：一个项集的所有直接超集的支持计数都不等于该项集的支持计数,频繁闭项集：一个项集是频繁项集并且是闭项集,最小支持计数阈值是5,.,47,频繁项集的紧凑表示,定理对于频繁项集l及其所有直接超集li=li(iI)，如果l是最大频繁项集，则l是频繁闭项集,sup_count(l)nmin_sup,证明：,定理对于频繁项集l及其所有直接超集li=li(iI)，如果l不是闭项集，则,证明：,基于该定理，频繁非闭项集的支持计数可以通过频繁闭项集的支持计数确定,.,48,频繁项集的紧凑表示,项集c不是闭项集，它的支持计数等于项集bc的支持计数,频繁项集、频繁闭项集与最大频繁项集的关系：,.,49,频繁项集的紧凑表示,通过频繁闭项集的支持计数计算其它频繁非闭项集的支持计数的算法描述,输入：频繁闭项集集合CL输出：频繁项集集合L步骤：（1）/找出频繁闭项集的最大长度（2）/找出最长频繁闭项集（3）/最长频繁闭项集也是最长频繁项集（4）for(k=kmax-1；k1；k-)/找出所有频繁项集（4.1）/找出由频繁闭(k+1)-项集推导的频繁k-项集（4.2）CLk=l|lCL,|l|=k/找出频繁闭k-项集,.,50,频繁项集的紧凑表示,通过频繁闭项集的支持计数计算其它频繁非闭项集的支持计数的算法描述,（4.3）forTLk中每个项集/计算频繁非闭k-项集的支持计数（4.3.1）ifthenLk=Lkl（4.4）Lk=LkCLk（4.5）L=LLk,.,51,频繁项集的紧凑表示,最小支持计数阈值是5，项集b:9、ad:5、bc:7、bd:6和bcd:5是频繁闭项集。写出计算频繁非闭项集的支持计数的过程,L3=CL3=bcdTL2=bc,bd,cdCL2=ad,bc,bdcd.sup_count=bcd.sup_count=5L2=ad,bc,bd,cdTL1=a,b,c,dCL1=ba.sup_count=ad.sup_count=5c.sup_count=bc.sup_count=7d.sup_count=bd.sup_count=6L1=a,b,c,d,.,52,FP-growth算法,Apriori算法的不足：1）可能产生大量候选项集2）可能需要重复扫描数据库，通过模式匹配检查庞大的候选集合FP-growth算法采用一种称为FP树的结构表示事务集合中项集的关联，并在FP树上递归地找出所有频繁项集，算法并不产生候选基本思想：扫描一次事务集合，找出频繁1-项集合L1基于L1，再扫描一次事务集合，构造表示事务集合中项集关联的FP树在FP树上递归地找出所有频繁项集最后在所有频繁项集中产生强关联规则,.,53,FP-growth算法,1）扫描一次事务集合，找出频繁1-项集合L，并按支持计数降序排序L中的频繁项,FP树构造,min_sup=20%,L=i2:7,i1:6,i3:5,i4:2,i5:2,2）创建FP树的根节点，用“null”标记,.,54,FP-growth算法,3）再扫描一次事务集合，对每个事务找出其中的频繁项并按L中的顺序排序，为每个事务创建一个分枝，事务分枝路径上的节点就是该事务中的已排序频繁项对于各个事务分枝，如果可以共享路径则共享并且在各个节点上记录共享事务数目,FP树构造,L=i2:7,i1:6,i3:5,i4:2,i5:2,.,55,FP-growth算法,FP树构造,L=i2:7,i1:6,i3:5,i4:2,i5:2,4）为方便遍历FP树，为FP树创建一个项表项表中每一行表示一个频繁项，并有一个指针指向它在FP树中的节点FP树中相同频繁项的节点通过指针连成链表,.,56,FP-growth算法,FP树构造,.,57,FP-growth算法,由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基。然后，构造它的条件FP树，并递归地在该树上进行挖掘。模式增长通过后缀模式与由条件FP树产生的频繁模式连接实现条件模式基：一个“子数据库”，由FP树中与后缀模式一起出现的前缀路径集组成条件FP树：条件模式基中，由满足最小支持度阈值的节点构成的树,FP树挖掘,i5:2的条件模式基null,i2,i1:2,i5:2与条件FP树,.,58,FP-growth算法,递归过程：1）如果条件FP树只有一个分枝，则分枝路径上的节点的一个组合就是一个前缀模式，一个前缀模式与后缀模式产生一个频繁项集（递归出口）2）否则用L中的频繁项i增长后缀模式（i，增长时，按逆序方式处理，即先考虑L的最后一项），然后构造增长后缀模式i的条件模式基与条件FP树，递归上述过程初始时，=null，null的条件FP树就是FP树,FP树挖掘,.,59,FP-growth算法,第二层递归：,FP树挖掘,第一层递归：=nullnull的条件FP树有多个分枝，进入第二层递归,i3:5的条件FP树有两个分枝，进入第三层递归,.,60,FP-growth算法,第三层递归：,FP树挖掘,.,61,FP-growth算法,输入：事务集合T，最小支持度阈值min_sup，最小置信度阈值min_conf输出：强关联规则集合R_S步骤：（1）扫描T找出频繁1-项集合L（2）L中的项按支持计数降序排序（3）创建FP树的根节点null/创建FP树（4）forT中的每个事务t（4.1）找出t中的频繁1-项集合Lt（4.2）Lt中的项按L中的顺序排序（4.3）Insert-FP（Lt,null）/创建事务分枝（5）L_S=Search-FP（FP,null）/找出所有频繁项集（6）在L_S中产生强关联规则集合R_S,算法描述,.,62,FP-growth算法,算法：Insert-FP算法（Li,Tr）输入：已排序频繁1-项集合Li，FP（子）树的根节点Tr输出：FP树（1）ifLi不空then（1.1）取出Li中的第1个项i（1.2）ifTr的某个子节点Node是ithen（1.2.1）Node.count=Node.count+1（1.3）else（1.3.1）创建Tr的子节点Node为i（1.3.2）Node.count=1（1.3.3）将Node加入项表链中（1.4）Insert-FP（Li-i,Node）,算法描述,.,63,FP-growth算法,算法：Search-FP算法（T，）输入：（条件）FP树T，后缀模式输出：频繁项集集合L_S（1）ifT中只有一个分枝Pthen（1.1）forP上的节点的每个组合（1.1.1）=/产生频繁项集（1.1.2）L_S=L_S（2）else（2.1）forT中的每个频繁项i（2.1.1）=i/增长后缀模式（2.1.2）构造的条件模式基及其条件FP树T（2.1.3）Search-FP（T,）,算法描述,.,64,分析技术及模型聚类分析,.,65,将物理或抽象对象的集合分成相似的对象类的过程使得同一个簇中的对象之间具有较高的相似性，而不同簇中的对象具有较高的相异性是数据挖掘、模式识别等研究方向的重要研究内容之一，在识别数据的内在结构方面具有极其重要的作用广泛应用于模式识别、数据分析、图像处理和市场研究等领域，对生物学、心理学、考古学、地质学及地理学等研究也有重要作用主要介绍聚类概念、聚类过程、常用聚类算法,聚类分析,.,66,=o1,o2,on表示一个对象集合oi表示第i个对象，i=1,2,nCx表示第x个簇，Cx，x=1，2，kSimilarity(oi,oj)表示对象oi与对象oj之间的相似度若各簇Cx是刚性聚类结果，则各Cx需满足如下条件：1）2）对于有3）,聚类分析的形式描述,.,67,聚类过程,为聚类分析准备数据，包括属性值标准化,从最初的属性中选择最有效的属性,通过对所选择的属性进行转换形成新的更有代表性的属性,度量对象间的相似性程度，执行聚类或分组,聚类分析的三要素是相似性测度、聚类准则和聚类算法,.,68,聚类分析中的数据类型,聚类分析中常用的数据类型有：数据矩阵、相异度矩阵,1）数据矩阵：对象在多维空间中通常表示为点（向量），其每一维表示为不同属性，这些属性描述出对象数据矩阵每行代表一个对象，每列代表对象的一个属性,2）相异度矩阵：存储n个对象两两之间的近似性，d(i,j)是对象i和对象j之间相异性的量化表示,.,69,聚类分析三要素,相似性测度、聚类准则和聚类算法相似性测度：衡量同簇对象的类似性和不同簇对象的差异性聚类准则：评价聚类结果的好坏聚类算法：用于找出使准则函数取极值的最好聚类结果,实际上，确定了相似性测度和聚类准则后，聚类就变成了使准则函数取极值的优化问题了,没有任何一种聚类算法可以普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构因此聚类算法有多种，不同的聚类算法使用不同的相似性度量和准则,.,70,对象之间的相似性根据描述对象的属性值评估，可以使用距离、密度、连通性或概念度量距离相似性度量：距离越近越相似，不同簇中任意两个对象间的距离都大于簇内任意两个对象之间的距离密度相似性度量：密度（单位区域内的对象数）越相近，相似性越高，簇是对象的稠密区域，被低密度的区域环绕连通性相似性度量：使用图的连通性度量相似性，簇定义为图的连通分支，即互相连通但不与组外对象连通的对象组概念相似性度量：共性（比如共享最近邻）越多越相似，簇定义为有某种共同性质的对象的集合,相似性测度,.,71,主要的聚类算法大致可以分为：划分式聚类算法、基于密度的聚类算法、层次聚类算法、基于网格的聚类算法和基于模型的聚类算法,聚类算法分类,划分式聚类算法（partitioningmethod）,预先指定聚类数目或聚类中心，通过反复迭代运算，逐步优化准则函数的值，当准则函数收敛时，得到最终聚类结果k均值算法、k中心点算法及它们的变种,基于密度的聚类算法（density-basedmethod）,通过数据密度来发现簇DBSCAN、OPTICS、DENCLUE,.,72,聚类算法分类,基于网格的聚类算法（gridbasedmethod）,将对象空间量化为有限数目的单元，形成网格结构，所有的聚类操作都在网格上进行，从而获得较快的处理速度STING、WaveCluster,层次聚类算法（hierarchicalmethod）,将数据对象组织成一棵聚类树，使用数据的联接规则，透过一种架构方式，反复将数据进行分裂或聚合，以形成一个层次序列的聚类问题解BIRCH、ROCK和Chameleon等,.,73,聚类算法分类,基于模型的聚类算法（model-basedmethod）,基于“数据根据潜在的混合概率分布生成”假设，为每个簇假定一个模型，并寻找数据对给定模型的最佳拟合这类算法通过构建反映数据点空间分布的密度函数来定位簇，能考虑“噪声”数据和离群点的影响，鲁棒性较好EM、COBWEB、SOM,.,74,均值聚类算法,均值聚类算法假定所有数据对象可分为k个簇，每个簇的中心用均值表示对象间的相似性用距离度量聚类的准则是误差平方和准则核心思想：首先选定k个初始聚类中心，根据最小距离原则将每个数据对象分配到某一簇中然后不断迭代计算各个簇的聚类中心并依新的聚类中心调整聚类情况，直至收敛（J值不再变化）,.,75,均值聚类算法,误差平方和准则,若Nx是第Cx个簇中的对象数目，mx是这些对象的均值，J是所有簇的簇中各个对象与均值间的误差平方和之和对于不同的聚类，J的值不同使J值极小的聚类是误差平方和准则下的最优结果,度量了用k个聚类中心m1,mk代表k个簇C1,Ck时所产生的总的误差平方和,.,76,均值聚类算法,算法描述,输入：数据对象集合D，簇数目k输出：k个簇的集合步骤：1.从D中随机选取k个不同的数据对象作为k个簇C1，Ck的中心m1，mk2.repeat1）forD中每个数据对象oa.寻找i，b.将o分配给簇Ci2）for每个簇Ci（i=1，k）计算3）计算平方误差3.UntilJ不再发生变化,计算新的聚类中心，|Ci|为当前簇中的对象数目,.,77,均值聚类算法,算法简单，计算复杂度是O(nkt)，其中n是对象的总数，k是簇的个数，t是迭代次数，通常，kn且tG(蔬菜，形状),不同描述属性减少类别属性不确定性的程度不同,.,117,决策树分类算法,信息增益,尽量选择对减少类别属性不确定性贡献最大的描述属性分类模型包含尽可能少的描述属性从而使模型简单,G(蔬菜，颜色)G(蔬菜，形状),测试属性的选择顺序影响决策树的结构甚至决策树的准确率,决策树分类算法要求描述属性是离散属性，连续属性需要离散化,.,118,决策树分类算法,噪声处理,如果训练数据集含有噪声，决策树的某些分枝反映的是噪声而不是总体，应该剪去这些不可靠的分枝，提高决策树的分类准确率有两种剪枝策略：先剪枝策略：在建立决策树的过程中，通过某度量标准判断每个内部节点是否需要进一步划分，如果进一步划分将导致建立不可靠的分枝，则停止划分，从而达到剪枝。此时，该内部节点变成叶节点并用其中占多数的记录类别标识后剪枝策略：首先，建立完整的决策树；然后，通过某度量标准判断哪些内部节点分枝是不可靠的，将这些内部节点变成叶节点并用其中占多数的记录类别标识，从而达到剪枝,.,119,前馈神经网络分类算法,神经网络可以模仿人脑，通过学习训练数据集，生成分类模型适用于数据没有任何明显模式的情况样本属性可以是连续的，也可以是离散的神经网络由许多单元（神经元）以适当的方式连接起来构成单元模仿人脑的神经元，单元之间的连接相当于人脑中神经元的连接单元之间的连接方式有多种，从而形成了多种神经网络在分类中，应用较多的是前馈神经网络主要介绍前馈神经网络结构、网络学习及网络分类方法,.,120,前馈神经网络分类算法,网络结构,前馈神经网络是分层网络模型，具有一个输入层和一个输出层，输入层和输出层之间有一个或多个隐藏层每个层具有若干单元，前一层单元与后一层单元之间通过有向加权边相连,ai：输入层第i个单元的输入,Ok：输出层第k个单元的输出,wij：隐藏层第j个单元与输入层第i个单元之间的连接权,wjk：输出层第k个单元与隐藏层第j个单元之间的连接权,.,121,前馈神经网络分类算法,网络结构,输入层单元的数目与训练样本的描述属性数目对应，通常一个连续属性对应一个输入层单元，一个p值离散属性对应p个输入层单元输出层单元的数目与训练样本的类别数目对应（两类时，可以只有一个输出单元）隐层的层数及隐层的单元数尚无理论指导，一般通过实验选取输入层，各单元的输出可以等于输入，也可以按一定比例调节，使其值落在1和+1之间其他层，每个单元的输入都是前一层各单元输出的加权和，输出是输入的某种函数，称为激活函数,.,122,前馈神经网络分类算法,网络结构,隐藏层、输出层任意单元j的输入：,输出：Oj=f(netj)如果f采用S型激活函数：,对于隐藏层、输出层任意单元j，由输入计算输出的过程：,单元i的输出,单元j与前一层单元i之间的连接权,改变单元j活性的偏置，1，1上取值,则,.,123,前馈神经网络分类算法,网络学习,不同的单元的偏置及单元之间的连接权会获得不同的输出学习过程就是调整各单元的偏置及单元之间的连接权值，使每个训练样本在输出层单元上获得的输出与其期望输出间的误差最小学习使用误差后向传播算法基本思想：首先赋予每条有向加权边初始权值、每个隐藏层与输出层单元初始偏置然后迭代地处理每个训练样本，输入它的描述属性值，计算实际输出，获取实际输出与期望输出间的误差将误差从输出层经每个隐藏层到输入层“后向传播”，根据误差修改权值和单元的偏置，使实际输出与期望输出之间的误差最小,.,124,前馈神经网络分类算法,网络学习,样本实际输出与期望输出的误差Error：,c：输出层的单元数目Tk：输出层单元k的期望输出Ok：单元k的实际输出,输出层单元k与前一层单元j之间的权值wjk的修改量wjk、单元k的偏置修改量为使Error最小，采用使Error沿梯度方向下降的方式,单元j的输出,Error对单元k的输入netk的负偏导数,学习率，l0,1，避免陷入局部最优解,单元k的输出,.,125,前馈神经网络分类算法,网络学习,隐藏层单元j与前一层单元i之间的权值wij的修改量wij、单元j的偏置j的修改量j：,单元i的输出,单元j的输出,与单元j相连的后一层单元k的误差,权值、偏置的修改：,权值、偏置的更新有两种策略：1）实例更新：处理一个训练样本更新一次，常采用2）周期更新：处理所有训练样本后再一次更新处理所有训练样本一次，称为一个周期,.,126,前馈神经网络分类算法,网络学习,结束条件：1）误差Error小于设定阈值，此时认为网络收敛，结束迭代2）前一周期所有的权值变化都很小，小于某个设定阈值3）前一周期预测的准确率很大，大于某个设定阈值3）周期数大于某个设定阈值,在实际应用中，训练样本很多，学习需要很多次迭代才能完成迭代次数与网络结构、初始权值与偏置、学习率的值有很大关系这些参数都是凭经验选取,算法特点,.,127,前馈神经网络分类算法,网络学习,设训练样本s的描述属性值与类别属性值分别为1,0,1与1，前馈神经网络NT如图所示，NT中每条有向加权边的权值、每个隐藏层与输出层单元的偏置如表所示，学习率为0.9。写出输入s训练NT的过程,.,128,前馈神经网络分类算法,网络学习,.,129,前馈神经网络分类算法,网络学习,.,130,前馈神经网络分类算法,算法描述,输入：训练数据集S，前馈神经网络NT，学习率l输出：经过训练的前馈神经网络NT步骤：（1）在区间-1,1上随机初始化NT中每条有向加权边的权值、每个隐藏层与输出层单元的偏置（2）while结束条件不满足（2.1）forS中每个训练样本s（2.1.1）for隐藏层与输出层中每个单元j（2.1.2）for输出层中每个单元kErrk=Ok(1-Ok)(Tk-Ok),从第一个隐藏层开始向前传播输入,.,131,前馈神经网络分类算法,算法描述,（2.1.3）for隐藏层中每个单元j（2.1.4）forNT中每条有向加权边的权值wijwij=wij+lErrjOi（2.1.5）for隐藏层与输出层中每个单元的偏置jj=j+lErrj,从最后一个隐藏层开始向后传播误差,学习过程由正向传播和反向传播组成正向传播过程：训练样本从输入层，经隐藏层，传向输出层，每一层单元的状态只影响下一层单元的状态反向传播过程：输出层不能得到期望输出，则将误差沿原来的连接通路传回，通过修改权值和偏置，使误差最小,.,132,前馈神经网络分类算法,网络分类,学习结束后，神经网络得到一组固定的权值及偏置新样本到来后，将其描述属性值送入输入层各单元，从输入层到输出层正向传播，计算输出层各单元的值O1,O2,On令r=max(O1,O2,On)，则第r个输出层单元所代表的类别就是该样本所属的类别,新样本X=（x1,x2,x3）送入输入层计算出O61，则表示X应属于A类O60，则表示X应属于B类若O60.5，则拒绝分类,.,133,贝叶斯分类算法,贝叶斯分类：应用贝叶斯公式求解分类问题,贝叶斯公式：,贝叶斯分类公式：,m个描述属性A1=a1,Am=am的联合概率,类别属性C=c的概率（先验概率）,已知C=c时，A1=a1,Am=am的条件概率（类条件概率）,已知A1=a1,Am=am时，C=c的条件概率（类别c的后验概率）,贝叶斯分类的分类就是给定新样本的描述属性值a1,am，计算各个类别的后验概率，后验概率最大的类别就是新样本的类别,.,134,贝叶斯分类算法,怎样算、？,先验概率p(c)可以通过统计训练数据集中每个类别训练样本所占比例进行估计在计算各个类条件概率时，一般应用条件独立假设简化计算朴素贝叶斯分类C和A1,.,Am有直接依赖关系，A1,.,Am之间相互独立,.,135,贝叶斯分类算法,新样本为（3140，中，否，优）p(是)9/14p(3140|是)4/9；p(中|是)4/9；p(否|是)3/9；p(优|是)3/9；p(是)p(3140|是)p(中|是)p(否|是)p(优|是)9/144/94/93/93/98/567,.,136,贝叶斯分类算法,新样本为（3140，中，否，优）p(否)5/14；p(3140|否)0；p(中|否)2/5；p(否|否)4/5；p(优|否)3/5；p(否)p(3140|否)p(中|否)p(否|否)p(优|否)5/1402/54/53/50所以新样本的类别为是,.,137,贝叶斯分类算法,输入：训练数据集S、新样本r(ar1,arm)输出：新样本的类别cr步骤：（1）forS中每个训练样本s(as1,asm,cs)（1.1）增加类别cs的计数cs.count（1.2）for每个描述属性值asi增加类别cs中描述属性值asi的计数cs.asi.count（2）for每个类别c（2.1）,算法描述,.,138,贝叶斯分类算法,（2.2）for每个描述属性Ai（2.2.1）for每个描述属性值ai（2.3）for每个a1,am（3）,算法描述,朴素贝叶斯分类假设各个描述属性在给定类别属性时条件独立这个条件独立假设在现实应用中可能不成立树增强朴素贝叶斯分类削弱了这个限制,.,139,树增强朴素贝叶斯分类算法,树增强朴素贝叶斯分类假设C和A1,.,Am有直接依赖关系，A1,.,Am之间也有依赖关系（允许各个描述属性之间形成树型结构），削弱了各个描述属性在给定类别属性时条件独立假设，增强了朴素贝叶斯分类,节点C和节点A1,.,Am有有向边相连，C是A1,.,Am的父节点A1,.,Am之间有有向边相连并形成树，根节点的父节点只有C，其它节点的父节点除了C之外还有一个节点,新样本a1,a5的类别：,.,140,树增强朴素贝叶斯分类算法,树增强朴素贝叶斯分类树型结构构造方法的基本思想：首先，计算在给定类别属性C时，描述属性A1,.,Am之间的依赖强度，共得到个依赖强度然后，根据从强到弱的原则选择m-1个依赖强度，添加相应描述属性之间的无向边，并使各个描述属性之间形成无向树最后，选择根节点，为无向边添加方向形成有向树在给定类别属性C时，描述属性Ai和Aj之间的依赖强度可以利用条件互信息描述：,.,141,树增强朴素贝叶斯分类算法,输入：训练数据集S输出：树增强朴素贝叶斯分类的贝叶斯网结构TAN步骤：（1）扫描S，计算在给定类别属性C时，描述属性A1,.,Am之间的条件互信息（2）构造一个无向完全图，以描述属性为节点，以条件互信息为边的权重（3）构造上述无向完全图的最大生成树（4）在上述最大生成树中选择一个节点为根节点，为无向边添加方向形成有向树（5）在上述有向树中添加节点C和C到各个A1,.,Am的有向边，得到TAN,算法描述,.,142,树增强朴素贝叶斯分类算法,I(年龄；收入|购买计算机)0.4196I(年龄；学生|购买计算机)0.2228I(年龄；信誉|购买计算机)0.3118I(收入；学生|购买计算机)0.4196I(收入；信誉|购买计算机)0.1689I(学生；信誉|购买计算机)0.0611,.,143,树增强朴素贝叶斯分类算法,p(是)9/14p(3140|是)4/9p(中|是，3140)1/4p(否|是，中)2