数据分析方法及模型.pptx

《数据分析方法及模型.pptx》由会员分享，可在线阅读，更多相关《数据分析方法及模型.pptx（200页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1分析技术及模型数据预处理第1页/共200页2数据预处理各种数据分析技术的对象是数据源中的数据数据源中的数据可能不完整（如某些属性的值不确定或空缺）、含噪声和不一致（如同一个属性在不同表中的名称不同）、量纲不同如果直接在这些未经处理的数据上进行分析，结果不一定准确，效率也可能较低需要使用清理、集成、变换、归约等预处理方法改善数据质量，从而提高数据分析的效率与质量 主要介绍数据清理、集成、变换、规约等预处理技术第2页/共200页3数据清理数据清理用于消除噪声、数据不一致及数据不完整噪声可以通过平滑、识别孤立点等方法进行消除分箱技术：将数据排序，根据等深或等宽分布规则将数据分布到不同箱中，将同一箱

2、中的数据用用该箱中数据的平均值或中值、边界值替换（平均值平滑、中值平滑、边界平滑）每个箱中的数据个数或取值区间相等设某属性的值为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箱1：5.3,5.3,5.3箱2：12,12,12箱3：18.3,18.3,18.3第3页/共200页4数据清理数据不完整可以使用下列方法消除：1）使用一个全局常量填充2）使用属性平均值填充3）使用相同类的属性平均值填充4）

3、使用最可能的值填充 需要采用预测算法，预测给定样本的最可能的值并填充数据不一致可以通过元数据消除（描述数据的数据）第4页/共200页5数据集成数据集成是将多个数据源中的数据结合起来存放在一个一致的数据存储（如数据仓库）中这些数据源可能包括多个数据库、数据立方体或一般文件在数据集成时，需要消除冗余能够由另外的属性“导出”、命名的不一致的属性冗余可以通过相关分析进行检测属性A、B之间的相关性计算：rA,B0，A与B正相关，A的值随着B的值的增加而增加rA,B0，A与B负相关，A的值随着B的值的增加而减少rA,B=0，A与B独立。因此，|rA,B|很大时，A与B可以去除一个 平均值方差第5页/共20

4、0页6数据变换将属性数据按比例缩放，使之落入一个小的特定区间，如1.0到1.0或0.0到1.0 最小-最大规格化：minA，maxA为数值属性A规格化前的取值区间new_ minA，new_ maxA 为A规格化后的取值区间，最小-最大规格化根据下式将A的值v规格化为值v采用最小-最大规格化方法将100，100中的66规格化到区间0，1 第6页/共200页7数据变换零-均值规格化：对均值为 、方差为的数值属性A将A的值v规格化为值v设某属性的平均值、标准差分别为80、25，采用零-均值规格化66 小数定标规格化：数值属性A的最大绝对值为max|A|A，j为满足 的最小整数 将A的值v规格化为值

5、v规格化 100，100中的66A的最大绝对值为120，j为3 第7页/共200页8数据规约数据归约技术可以用来得到数据集的归约表示，它小得多，但仍接近于保持原数据集的完整性在归约后的数据集上分析将更有效，并产生相同（或几乎相同）的分析结果归约方法主要有：属性归约、记录归约 属性规约：删除不相关的或冗余的属性减小数据集，目标是找出最小属性集，使得数据在其上的概率分布尽可能地接近在原属性集上的概率分布 常用方法：粗糙集中的属性约简、决策树记录规约：用少量记录代表或替换原有记录，从而减小数据集常用方法：抽样、数据概化第8页/共200页9数据规约数据概化：采用面向属性归纳，根据属性的概念分层，通过阈

6、值控制，将属性的低层属性值用相应高层概念替换，并合并由此得到的相同记录 概念分层一般用树结构描述，称为概念层次树阈值控制面向属性归纳过程，每个属性都有概念层次树及阈值首先根据属性A的概念层次树，将关系表中A的属性值转换为最低层的相应概念（叶概念），统计关系表中A的不同叶概念个数如果A的不同叶概念个数大于A的属性阈值，再根据A的概念层次树，将关系表中A的叶概念转换为上一层的相应概念如此重复，直至关系表中A的不同概念个数小于等于A的属性阈值；最后合并相同记录，并统计重复记录数目第9页/共200页10数据规约属性阈值均为4记录由6个归约为3个count的值表示重复记录数目第10页/共200页11属性

7、概念分层的自动生成 概念分层一般由系统用户、领域专家提供，但非常耗时、乏味介绍离散属性与连续属性自动生成概念分层的方法 离散属性概念分层的自动生成 概念层次树中高层的概念个数一般少于低层的概念个数首先统计各个概念的不同值个数，个数最少的概念在最高层，依次类推，然后根据结构的从属关系，确定各层的概念及从属关系 地址地址国家国家省省市市中国中国云南省云南省昆明市昆明市中国中国云南省云南省大理市大理市中国中国四川省四川省成都市成都市中国中国贵州省贵州省贵阳市贵阳市中国中国云南省云南省玉溪市玉溪市中国中国云南省云南省曲靖市曲靖市第11页/共200页12属性概念分层的自动生成 连续属性概念分层的自动生成

8、 连续属性可以通过离散化递归地自动生成概念分层离散化可以基于熵完成，主要步骤：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的熵 第12页/共200页13属性概念分层的自动生成 连续属性概念分层的自动生成 3）对在V上的每个划分v1（v）、v2（v），计算在此划分下S的信息增益 4）选择使S的信息增益最大的划分作为最佳划分，记为V1（T）、V2（T）（T是使S的信息增益最大的v）5）递归地应

9、用步骤1）4）于V1、V2及S1、S2上，直至满足一定的结束条件，例如，最大信息增益小于某个阈值 属性A的取值区间V作为其概念层次树的根，形成最高层第一次划分区间V1、V2是根的两个子结点，形成次高层递归地应用步骤1）4）就可以得到各层结点第13页/共200页14属性概念分层的自动生成 连续属性概念分层的自动生成 设“气温”属性是目标属性，取值区间为100,100属性值及记录数如表所示属性值属性值3 36 6181822222626记录数记录数6 69 9363628282121划分区间100,100第14页/共200页15属性概念分层的自动生成 连续属性概念分层的自动生成 属性值属性值3 3

10、6 6181822222626记录数记录数6 69 9363628282121划分区间100,100G(100,100,3)=2.03782.0378=0G(100,100,6)=2.03781.7465=0.2913G(100,100,18)=2.03781.464=0.5738G(100,100,22)=2.03781.0741=0.9637G(100,100,26)=2.03781.3323=0.7055最佳划分：V1=100,22)(llu)不是强关联规则，则规则lv=(llv)也不是强关联规则 证明：sup_count(lv)sup_count(lu)i1i2 i5不是强关联规则i2

11、i1i5、i1i2i5都不可能是强关联规则l=i1i2i5lvi1、i2lui1i2第35页/共200页36Apriori算法压缩强关联搜索空间对于每个频繁项集，第一层产生后件只有一项的强关联规则，并生成它们的1-后件集合R1第二层产生后件有两项的强关联规则，并生成它们的2-后件集合R2R2通过R1中的后件进行连接运算，再通过置信度计算产生依次类推，可以产生所有强关联规则第36页/共200页37Apriori算法算法描述输入：事务集合T，最小支持度阈值min_sup，最小置信度阈值min_conf输出：强关联规则集合SR变量：频繁k-项集集合Lk，候选k-项集集合Ck，频繁项集集合L，k-后件

12、集合Rk步骤：/频繁项集产生（1）for T中的每个事务t （1.1）for t中的每个项i （1.1.1）i.sup_count=i.sup_count+1 /1-项集支持计数（2）for 每个项i （2.1）if i.sup_countnmin_sup then L1=L1i /找出频繁1-项集第37页/共200页38Apriori算法算法描述（3）for(k=2；Lk-1；k+)（3.1）for Lk-1中的每个项集lu （3.1.1）for Lk-1中项集lu之后的每个项集lv if (lu1=lv1)(luk-2=lvk-2)(luk-1lvk-1)then /连接 Ck=Ckc /

13、找出候选k-项集 for c中的每个(k1)-项集s if then Ck=Ck-c /剪枝 （3.2）for T中的每个事务t （3.2.1）for t中的每个k-项集s if sCk then s.sup_count=s.sup_count+1 /k-项集支持计数第38页/共200页39Apriori算法算法描述 （3.3）for Ck中的每个项集c （3.3.1）if c.sup_countnmin_sup then Lk=Lkc /找出频繁k-项集 （3.4）L=LLk/规则产生（4）for L中的每个频繁项集l （4.1）for l中的每个1-项集l1 （4.1.1）if then

14、SR=SR(l-l1)=l1 /找出后件只有1项的强关联规则 R1=R1l1 /找出1后件 第39页/共200页40Apriori算法算法描述（4.2）for(j=2；Rj-1；j+)（4.2.1）for Rj-1中的每个后件lu for Rj-1中后件lu之后的每个后件lv if (lu1=lv1)(luj-2=lvj-2)(luj-1lvj-1)then /连接 if then SR=SR(l-lj)=lj /找出后件有j项的强关联规则 Rj=Rjlj /找出j后件l=i1i2i5lui1lvi2第40页/共200页41Apriori算法影响Apriori算法时间复杂度主要因素（1）事务集

15、合当项数m增加：候选项集的数目和长度可能增加，频繁项集的数目和长度也可能增加，从而计算频繁项集及其支持计数的时间、扫描事务集合的次数、计算强关联规则的时间可能增加事务数n、事务平均宽度w增加：每次扫描事务集合的时间增加（2）最小支持度阈值min_supmin_sup越小，候选项集和频繁项集的数目越多、长度越长，扫描事务集合的次数越多，算法的运行时间越长（3）最小置信度阈值min_confmin_conf越小，强关联规则的数目越多，产生规则的运行时间越长第41页/共200页42频繁项集的紧凑表示 通常，从现实事务集合中产生的频繁项集的数量庞大为了提高关联规则挖掘算法的效率，频繁项集使用紧凑表示最

16、大频繁项集：一个频繁项集的所有直接超集都不是频繁项集由最大频繁项集可以推导所有频繁项集 频繁项集非频繁项集最大频繁项集由 ad可以推导频繁项集a、d和ad由bcd可以推导b、c、d、bc、bd、cd和bcd 第42页/共200页43频繁项集的紧凑表示 为了高效找出最大频繁项集，可以将搜索空间按前缀或后缀变换为树（前缀树、后缀树），然后采用宽度或深度优先策略进行搜索前缀树后缀树第43页/共200页44频繁项集的紧凑表示 宽度优先是先搜索同一层的频繁项集，再搜索下一层的频繁项集 深度优先是搜索到某层的一个频集时，先搜索更深层的频集，若没有频集则回溯，直至没有频项集产生也没有回溯 深度优先搜索策略可

17、以更快地检测到频繁项集边界，通常用于搜索最大频繁项集 深度优先与最大频繁项集搜索第44页/共200页45频繁项集的紧凑表示 最大频繁项集集合是频繁项集集合的紧凑表示由最大频繁项集可以推导所有频繁项集，但由最大频繁项集不能推导它们的支持计数闭项集：一个项集的所有直接超集的支持计数都不等于该项集的支持计数频繁闭项集：一个项集是频繁项集并且是闭项集最小支持计数阈值是5 第45页/共200页46频繁项集的紧凑表示 定理 对于频繁项集l及其所有直接超集li=li(iI)，如果l是最大频繁项集，则l是频繁闭项集 sup_count(l)nmin_sup 证明：定理 对于频繁项集l及其所有直接超集li=li

18、(iI)，如果l不是闭项集，则 证明：基于该定理，频繁非闭项集的支持计数可以通过频繁闭项集的支持计数确定第46页/共200页47频繁项集的紧凑表示 项集c不是闭项集，它的支持计数等于项集bc的支持计数 频繁项集、频繁闭项集与最大频繁项集的关系：第47页/共200页48频繁项集的紧凑表示通过频繁闭项集的支持计数计算其它频繁非闭项集的支持计数的算法描述输入：频繁闭项集集合CL输出：频繁项集集合L步骤：（1）/找出频繁闭项集的最大长度（2）/找出最长频繁闭项集（3）/最长频繁闭项集也是最长频繁项集（4）for(k=kmax-1；k1；k-)/找出所有频繁项集 （4.1）/找出由频繁闭(k+1)-项集

19、推导的频繁k-项集 （4.2）CLk=l|lCL,|l|=k /找出频繁闭k-项集第48页/共200页49频繁项集的紧凑表示通过频繁闭项集的支持计数计算其它频繁非闭项集的支持计数的算法描述（4.3）for TLk中每个项集 /计算频繁非闭k-项集的支持计数 （4.3.1）if then Lk=Lkl（4.4）Lk=LkCLk（4.5）L=LLk第49页/共200页50频繁项集的紧凑表示最小支持计数阈值是5，项集b:9、ad:5、bc:7、bd:6和bcd:5是频繁闭项集。写出计算频繁非闭项集的支持计数的过程 L3=CL3=bcd TL2=bc,bd,cd CL2=ad,bc,bd cd.sup

20、_count=bcd.sup_count=5 L2=ad,bc,bd,cd TL1=a,b,c,d CL1=b a.sup_count=ad.sup_count=5 c.sup_count=bc.sup_count=7 d.sup_count=bd.sup_count=6 L1=a,b,c,d第50页/共200页51FP-growth算法 Apriori算法的不足：1）可能产生大量候选项集2）可能需要重复扫描数据库，通过模式匹配检查庞大的候选集合FP-growth算法采用一种称为FP树的结构表示事务集合中项集的关联，并在FP树上递归地找出所有频繁项集，算法并不产生候选基本思想：扫描一次事务集合

21、，找出频繁1-项集合L1基于L1，再扫描一次事务集合，构造表示事务集合中项集关联的FP树在FP树上递归地找出所有频繁项集最后在所有频繁项集中产生强关联规则 第51页/共200页52FP-growth算法 1）扫描一次事务集合，找出频繁1-项集合L，并按支持计数降序排序L中的频繁项FP树构造 事务事务项项t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3min_sup=20%L=i2:7,i1:6,i3:5,i4:2,i5:2 2）创建FP树的根节点，用“null”标记null第52页/共200页

22、53FP-growth算法 3）再扫描一次事务集合，对每个事务找出其中的频繁项并按L中的顺序排序，为每个事务创建一个分枝，事务分枝路径上的节点就是该事务中的已排序频繁项对于各个事务分枝，如果可以共享路径则共享并且在各个节点上记录共享事务数目FP树构造 事务事务项项t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3L=i2:7,i1:6,i3:5,i4:2,i5:2 第53页/共200页54FP-growth算法 FP树构造 事务事务项项t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i

23、2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3L=i2:7,i1:6,i3:5,i4:2,i5:2 4）为方便遍历FP树，为FP树创建一个项表项表中每一行表示一个频繁项，并有一个指针指向它在FP树中的节点FP树中相同频繁项的节点通过指针连成链表 第54页/共200页55FP-growth算法 FP树构造 事务事务项项t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3第55页/共200页56FP-growth算法 由长度为1的频繁模式（初始后缀模式）开始

24、，构造它的条件模式基。然后，构造它的条件FP树，并递归地在该树上进行挖掘。模式增长通过后缀模式与由条件FP树产生的频繁模式连接实现条件模式基：一个“子数据库”，由FP树中与后缀模式一起出现的前缀路径集组成条件FP树：条件模式基中，由满足最小支持度阈值的节点构成的树FP树挖掘i5:2的条件模式基null,i2,i1:2 i5:2 与条件FP树 第56页/共200页57FP-growth算法 递归过程：1）如果条件FP树只有一个分枝，则分枝路径上的节点的一个组合就是一个前缀模式，一个前缀模式与后缀模式产生一个频繁项集（递归出口）2）否则用L中的频繁项i增长后缀模式（i，增长时，按逆序方式处理，即先

25、考虑L的最后一项），然后构造增长后缀模式i 的条件模式基与条件FP树，递归上述过程初始时，=null，null的条件FP树就是FP树FP树挖掘第57页/共200页58FP-growth算法 第二层递归：FP树挖掘条件模式基条件模式基条件条件FPFP树树产生的频繁项集产生的频繁项集i5:2null,i2,i1:2i2i5:2、i1i5:2、i2i1i5:2i4:2null,i2,i1:1、null,i2:1i2i4:2i3:5null,i2,i1:1、null,i2:2、null,i1:2、i1:6null,i2:4、null:2i2i1:4i2:7null:7第一层递归：=nullnull的条

26、件FP树有多个分枝，进入第二层递归i3:5的条件FP树有两个分枝，进入第三层递归 第58页/共200页59FP-growth算法 第三层递归：FP树挖掘条件模式基条件模式基条件条件FPFP树树产生的频繁项集产生的频繁项集i1i3:3null,i2:1、null:2i1i3:3i2i3:3null:3i2i3:3第59页/共200页60FP-growth算法 输入：事务集合T，最小支持度阈值min_sup，最小置信度阈值min_conf输出：强关联规则集合R_S步骤：（1）扫描T找出频繁1-项集合L（2）L中的项按支持计数降序排序（3）创建FP树的根节点null /创建FP树（4）for T中的

27、每个事务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算法描述第60页/共200页61FP-growth算法 算法：Insert-FP算法（Li,Tr）输入：已排序频繁1-项集合Li，FP（子）树的根节点Tr输出：FP树（1）if Li不空 then （1.1）取出Li中的第1个项i （1.2）if Tr的某个子节点Node是i then （1.2.1）Node.count=Node.coun

28、t+1 （1.3）else （1.3.1）创建Tr的子节点Node为i （1.3.2）Node.count=1 （1.3.3）将Node加入项表链中（1.4）Insert-FP（Lii,Node）算法描述第61页/共200页62FP-growth算法 算法：Search-FP算法（T，）输入：（条件）FP树T，后缀模式输出：频繁项集集合L_S（1）if T中只有一个分枝P then （1.1）for P上的节点的每个组合 （1.1.1）=/产生频繁项集 （1.1.2）L_S=L_S（2）else （2.1）for T中的每个频繁项i （2.1.1）=i /增长后缀模式 （2.1.2）构造的条件

29、模式基及其条件FP树T （2.1.3）Search-FP（T,）算法描述第62页/共200页63分析技术及模型聚类分析第63页/共200页64将物理或抽象对象的集合分成相似的对象类的过程使得同一个簇中的对象之间具有较高的相似性，而不同簇中的对象具有较高的相异性是数据挖掘、模式识别等研究方向的重要研究内容之一，在识别数据的内在结构方面具有极其重要的作用 广泛应用于模式识别、数据分析、图像处理和市场研究等领域，对生物学、心理学、考古学、地质学及地理学等研究也有重要作用 主要介绍聚类概念、聚类过程、常用聚类算法 聚类分析第64页/共200页65=o1,o2,on表示一个对象集合oi表示第i个对象，i

30、=1,2,nCx表示第x个簇，Cx，x=1，2，kSimilarity(oi,oj)表示对象oi与对象oj之间的相似度若各簇Cx是刚性聚类结果，则各Cx需满足如下条件：1）2）对于 有3）聚类分析的形式描述第65页/共200页66数据准备属性选择属性提取聚类结果评估聚类过程为聚类分析准备数据，包括属性值标准化从最初的属性中选择最有效的属性通过对所选择的属性进行转换形成新的更有代表性的属性度量对象间的相似性程度，执行聚类或分组 聚类分析的三要素是相似性测度、聚类准则和聚类算法第66页/共200页67聚类分析中的数据类型聚类分析中常用的数据类型有：数据矩阵、相异度矩阵1）数据矩阵：对象在多维空间中

31、通常表示为点（向量），其每一维表示为不同属性，这些属性描述出对象数据矩阵每行代表一个对象，每列代表对象的一个属性2）相异度矩阵：存储n个对象两两之间的近似性，d(i,j)是对象i和对象j之间相异性的量化表示第67页/共200页68聚类分析三要素相似性测度、聚类准则和聚类算法相似性测度：衡量同簇对象的类似性和不同簇对象的差异性 聚类准则：评价聚类结果的好坏 聚类算法：用于找出使准则函数取极值的最好聚类结果 实际上，确定了相似性测度和聚类准则后，聚类就变成了使准则函数取极值的优化问题了 没有任何一种聚类算法可以普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构 因此聚类算法有多种，不同的聚类算

32、法使用不同的相似性度量和准则第68页/共200页69对象之间的相似性根据描述对象的属性值评估，可以使用距离、密度、连通性或概念度量距离相似性度量：距离越近越相似，不同簇中任意两个对象间的距离都大于簇内任意两个对象之间的距离 密度相似性度量：密度（单位区域内的对象数）越相近，相似性越高，簇是对象的稠密区域，被低密度的区域环绕 连通性相似性度量：使用图的连通性度量相似性，簇定义为图的连通分支，即互相连通但不与组外对象连通的对象组 概念相似性度量：共性（比如共享最近邻）越多越相似，簇定义为有某种共同性质的对象的集合 相似性测度第69页/共200页70主要的聚类算法大致可以分为：划分式聚类算法、基于密

33、度的聚类算法、层次聚类算法、基于网格的聚类算法和基于模型的聚类算法聚类算法分类划分式聚类算法（partitioning method）预先指定聚类数目或聚类中心，通过反复迭代运算，逐步优化准则函数的值，当准则函数收敛时，得到最终聚类结果k均值算法、k中心点算法及它们的变种基于密度的聚类算法（density-based method）通过数据密度来发现簇DBSCAN、OPTICS、DENCLUE第70页/共200页71聚类算法分类基于网格的聚类算法（gridbased method）将对象空间量化为有限数目的单元，形成网格结构，所有的聚类操作都在网格上进行，从而获得较快的处理速度STING、Wa

34、veCluster层次聚类算法（hierarchical method）将数据对象组织成一棵聚类树，使用数据的联接规则，透过一种架构方式，反复将数据进行分裂或聚合，以形成一个层次序列的聚类问题解 BIRCH、ROCK和Chameleon 等第71页/共200页72聚类算法分类基于模型的聚类算法（model-based method）基于“数据根据潜在的混合概率分布生成”假设，为每个簇假定一个模型，并寻找数据对给定模型的最佳拟合这类算法通过构建反映数据点空间分布的密度函数来定位簇，能考虑“噪声”数据和离群点的影响，鲁棒性较好 EM、COBWEB、SOM 第72页/共200页73均值聚类算法均值聚

35、类算法假定所有数据对象可分为k个簇，每个簇的中心用均值表示对象间的相似性用距离度量聚类的准则是误差平方和准则 核心思想：首先选定k个初始聚类中心，根据最小距离原则将每个数据对象分配到某一簇中然后不断迭代计算各个簇的聚类中心并依新的聚类中心调整聚类情况，直至收敛（J 值不再变化）第73页/共200页74均值聚类算法误差平方和准则若Nx是第Cx个簇中的对象数目，mx是这些对象的均值，J是所有簇的簇中各个对象与均值间的误差平方和之和对于不同的聚类，J的值不同使J 值极小的聚类是误差平方和准则下的最优结果度量了用k个聚类中心m1,mk代表k个簇C1,Ck时所产生的总的误差平方和第74页/共200页75

36、均值聚类算法算法描述输入：数据对象集合D，簇数目k输出：k个簇的集合步骤：1.从D中随机选取k个不同的数据对象作为k个簇C1，Ck的中心m1，mk2.repeat1）for D中每个数据对象oa.寻找i，b.将o分配给簇Ci2）for 每个簇Ci（i=1，k）计算 3）计算平方误差3.Until J不再发生变化计算新的聚类中心，|Ci|为当前簇中的对象数目第75页/共200页76均值聚类算法算法简单，计算复杂度是O(nkt)，其中n是对象的总数，k是簇的个数，t是迭代次数，通常，kn且t，继续计算5步迭代后的结果：x1x2x3x4x5(0.826,0.961)T(0.501,0.981)T(0

37、.653,0.945)T(3.452,0.038)T(3.811,0.040)T(4.106,0.039)T(3.614,0.019)T(2.720,0.055)T(0.688,0.962)T(0.777,0.960)T第99页/共200页100模糊c-均值聚类算法xi相对于 的隶属度 x1x2x3x4x50.9610.9810.9460.0380.0400.0390.0190.0540.9620.960聚类过程终止 第100页/共200页101分析技术及模型分类分析第101页/共200页102分类与预测是普遍存在的问题，具有广泛的应用领域分类的任务是通过分析由已知类别数据对象组成的训练数据集

38、，建立描述并区分数据对象类别的分类函数或分类模型（分类器）分类的目的是利用分类模型判定未知类别数据对象的所属类别，判定的目标是数据对象在类别属性（离散）上的取值预测也要通过分析训练数据集建立预测模型，然后利用模型预测数据对象，预测的目标是判定数据对象在预测属性（连续）上的取值或取值区间分类与聚类有显著区别：分类中，训练样本的类别是已知的（有指导），而聚类中所有数据都没有类别标签（无指导）主要介绍分类过程、分类模型评估方法、常用分类算法分类分析第102页/共200页103分类过程分为两个阶段：学习阶段与分类阶段分类过程训练样本输入分类模型测试样本输入新数据分类算法学习过程分类过程每个训练样本由m

39、+1个属性描述，X=（A1,Am,C）Ai对应描述属性，可以是连续属性或离散属性C表示类别属性，有k个不同的类别，C=（c1,c2,ck）从描述属性矢量（XC）到类别属性C的映射函数H:（XC）C分类规则、判定树等形式X=（A1,Am）确定CX=（A1,Am,C）提供X=（A1,Am)，确定C，比较C、C用于寻找映射函数H第103页/共200页104分类算法有多种：决策树分类算法、神经网络分类算法、贝叶斯分类算法、k-最近邻分类算法、遗传分类算法、粗糙集分类算法、模糊集分类算法等 分类算法可以根据下列标准进行比较和评估：1）准确率：分类模型正确地预测新样本所属类别的能力2）速度：建立和使用分类

40、模型的计算开销3）强壮性：给定噪声数据或具有空缺值的数据，分类模型正确地预测的能力4）可伸缩性：给定大量数据，有效地建立分类模型的能力5）可解释性：分类模型提供的理解和洞察的层次分类算法评估标准第104页/共200页105利用测试数据集评估分类模型的准确率分类模型正确分类的测试样本数占总测试样本数的百分比准确率可以接受，对新样本进行分类；否则，重新建立分类模型评估分类模型准确率的方法有保持、k-折交叉确认保持方法将已知类别的样本随机地划分为训练数据集与测试数据集两个集合，一般，训练数据集占2/3，测试数据集占1/3k-折交叉确认方法将已知类别的样本随机地划分为大小大致相等的k个子集S1,Sk，

41、并进行k次训练与测试第i次，Si作为测试数据集，其余子集的并集作为训练数据集k次训练得到k个分类模型，测试时，将出现次数最多的分类结果作为最终的分类结果分类模型评估方法第105页/共200页106适宜多峰分布的分类问题 决策树以树结构的形式表示，类似流程图一棵决策树由一个根节点，一组内部节点和一组叶节点组成决策树分类算法每个分枝表示一个测试输出每个叶节点表示一个类，不同的叶节点可表示相同的类 根节点和内部节点表示在一个属性上的测试第106页/共200页107建立了决策树之后，可以对从根节点到叶节点的每条路径创建一条IF-THEN分类规则，易于理解沿着路径，每个内部节点-分枝对形成规则前件（IF

42、部分）的一个合取项，叶节点形成规则后件（THEN部分）决策树分类算法IF 年龄=41 AND 信誉=中 THEN 购买计算机=是IF 年龄=30 AND 学生=否 THEN 购买计算机=否-否新顾客：教师，年龄45岁，收入较低但信誉很好该顾客是否会购买计算机？第107页/共200页108决策树分类算法的关键是建立决策树建立一棵决策树，需要解决的问题主要有：1）如何选择测试属性？测试属性的选择顺序影响决策树的结构甚至决策树的准确率一般使用信息增益度量来选择测试属性2）如何停止划分样本？从根节点测试属性开始，每个内部节点测试属性都把样本空间划分为若干个（子）区域一般当某个（子）区域的样本同类时，就

43、停止划分样本，有时也通过阈值提前停止划分样本决策树分类算法第108页/共200页109使用递归方式完成基本思想：首先，将整个训练数据集S、所有描述属性A1,A2,Am作为分析对象如果S中的样本属于同一类别，则将S作为叶节点并用其中样本的类别标识，决策树建立完成否则在S上计算各个属性的信息增益G(C,Ak)，选择信息增益最大的属性Ai作为根节点的测试属性如果Ai的取值个数为v（取值记为a1,a2,av），则Ai将S划分为v个子集S1,S2,Sv，同时根节点产生v个分枝与之对应分别在训练数据子集S1,S2,Sv、剩余描述属性A1,Ai1,Ai+1,Am上采用相同方法递归地建立决策树子树决策树分类算

44、法建立决策树Sv：S中Ai=av的样本集合第109页/共200页110递归过程中，某节点对应的训练数据（子）集由整个训练数据集S中满足从根节点到该节点路径上所有属性测试的训练样本组成某节点对应的描述属性是去除从根节点到该节点路径上所有已选描述属性后的剩余描述属性同一层内部节点选择的测试属性可能相同也可能不同决策树分类算法建立决策树第110页/共200页111递归结束条件：1）某节点对应的训练数据（子）集中的样本属于同一类别2）某节点对应的训练数据（子）集为空此时，该节点作为叶节点并用父节点中占多数的样本类别标识3）某节点没有对应的（剩余）描述属性此时，该节点作为叶节点并用该节点中占多数的样本类

45、别标识决策树分类算法建立决策树第111页/共200页112输入：训练数据集S，描述属性集合A输出：决策树步骤：（1）创建对应S的节点Node（2）if S中的样本属于同一类别c then 以c标识Node并将Node作为叶节点返回（3）if A为空 then 以S中占多数的样本类别c标识Node并将Node作为叶节点返回（4）从A中选择对S而言信息增益最大的描述属性Ai作为Node的测试属性决策树分类算法算法描述第112页/共200页113（5）for Ai的每个可能取值aj（1jv）（5.1）产生S的一个子集Sj （5.2）if Sj为空 then 创建对应Sj的节点Nj，以S中占多数的样本

46、类别c标识Nj，并将Nj作为叶节点形成Node的一个分枝 （5.3）else 由（Sj,A-Ai）创建子树形成Node的一个分枝决策树分类算法算法描述第113页/共200页114决策树分类算法信息增益类别属性C的无条件熵：给定描述属性Ak，类别属性C的条件熵：n：样本总数 u：C的可能取值个数，即类别数si：属于类别ci的记录集合|si|：属于类别ci的记录总数v：Ak的可能取值个数 sj：Ak=aj的记录集合|sj|：Ak=aj的记录数目Sij：Ak=aj且属于类别ci的记录集合|sij|：Ak=aj且属于类别ci的记录数目 给定描述属性Ak，类别C的信息增益：G(C,Ak)=E(C)-E(

47、C,Ak)G(C,Ak)反映Ak减少C不确定性的程度，G(C,Ak)越大，Ak对减少C不确定性的贡献越大 第114页/共200页115决策树分类算法信息增益 蔬菜数据表如表所示，“颜色”、“形状”是描述属性，“蔬菜”是类别属性，分别求给定“颜色”、“形状”属性时，“蔬菜”属性的信息增益 颜色颜色形状形状蔬菜蔬菜红红圆圆蕃茄蕃茄紫紫长长茄子茄子绿绿长长黄瓜黄瓜G(蔬菜，颜色)1.5850-0=1.5850G(蔬菜，形状)1.5850-0.6667=0.9183 G(蔬菜，颜色)G(蔬菜，形状)不同描述属性减少类别属性不确定性的程度不同第115页/共200页116决策树分类算法信息增益尽量选择对减

48、少类别属性不确定性贡献最大的描述属性分类模型包含尽可能少的描述属性从而使模型简单 G(蔬菜，颜色)G(蔬菜，形状)测试属性的选择顺序影响决策树的结构甚至决策树的准确率决策树分类算法要求描述属性是离散属性，连续属性需要离散化 第116页/共200页117决策树分类算法噪声处理如果训练数据集含有噪声，决策树的某些分枝反映的是噪声而不是总体，应该剪去这些不可靠的分枝，提高决策树的分类准确率有两种剪枝策略：先剪枝策略：在建立决策树的过程中，通过某度量标准判断每个内部节点是否需要进一步划分，如果进一步划分将导致建立不可靠的分枝，则停止划分，从而达到剪枝。此时，该内部节点变成叶节点并用其中占多数的记录类别

49、标识 后剪枝策略：首先，建立完整的决策树；然后，通过某度量标准判断哪些内部节点分枝是不可靠的，将这些内部节点变成叶节点并用其中占多数的记录类别标识，从而达到剪枝第117页/共200页118前馈神经网络分类算法神经网络可以模仿人脑，通过学习训练数据集，生成分类模型适用于数据没有任何明显模式的情况 样本属性可以是连续的，也可以是离散的神经网络由许多单元（神经元）以适当的方式连接起来构成单元模仿人脑的神经元，单元之间的连接相当于人脑中神经元的连接单元之间的连接方式有多种，从而形成了多种神经网络在分类中，应用较多的是前馈神经网络主要介绍前馈神经网络结构、网络学习及网络分类方法 第118页/共200页1

50、19前馈神经网络分类算法网络结构前馈神经网络是分层网络模型，具有一个输入层和一个输出层，输入层和输出层之间有一个或多个隐藏层每个层具有若干单元，前一层单元与后一层单元之间通过有向加权边相连 ai：输入层第i个单元的输入 Ok：输出层第k个单元的输出 wij：隐藏层第j个单元与输入层第i个单元之间的连接权wjk：输出层第k个单元与隐藏层第j个单元之间的连接权 第119页/共200页120前馈神经网络分类算法网络结构输入层单元的数目与训练样本的描述属性数目对应，通常一个连续属性对应一个输入层单元，一个p值离散属性对应p个输入层单元输出层单元的数目与训练样本的类别数目对应（两类时，可以只有一个输出单