分析技术分类及模型分析

1、分析技术分类及模型分析1数据预处理关联分析技术聚类分析技术分类分析技术异常分析技术影响图分析技术及模型数据预处理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数据清理数据不完整可以使用下列方法消除：1）使用一

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

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

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

6、替换，并合并由此得到的相同记录 概念分层一般用树结构描述，称为概念层次树阈值控制面向属性归纳过程，每个属性都有概念层次树及阈值首先根据属性A的概念层次树，将关系表中A的属性值转换为最低层的相应概念（叶概念），统计关系表中A的不同叶概念个数如果A的不同叶概念个数大于A的属性阈值，再根据A的概念层次树，将关系表中A的叶概念转换为上一层的相应概念如此重复，直至关系表中A的不同概念个数小于等于A的属性阈值；最后合并相同记录，并统计重复记录数目数据规约属性阈值均为4记录由6个归约为3个count的值表示重复记录数目属性概念分层的自动生成 概念分层一般由系统用户、领域专家提供，但非常耗时、乏味介绍离散属性

7、与连续属性自动生成概念分层的方法 离散属性概念分层的自动生成 概念层次树中高层的概念个数一般少于低层的概念个数首先统计各个概念的不同值个数，个数最少的概念在最高层，依次类推，然后根据结构的从属关系，确定各层的概念及从属关系 地址国家省市中国云南省昆明市中国云南省大理市中国四川省成都市中国贵州省贵阳市中国云南省玉溪市中国云南省曲靖市属性概念分层的自动生成 连续属性概念分层的自动生成 连续属性可以通过离散化递归地自动生成概念分层离散化可以基于熵完成，主要步骤：1）计算关系表r中在属性A的取值区间V上的记录集合S的熵 |c|：S中属于目标类c的记录数|S|：S中的记录数 2）对A在V上取的每个v，用

8、v划分V为v1（v）、v2（v），划分S为S1，S2，计算在此划分下S的熵 E(S1)、E(S2)分别为S1、S2的熵 属性概念分层的自动生成 连续属性概念分层的自动生成 3）对在V上的每个划分v1（v）、v2（v），计算在此划分下S的信息增益 4）选择使S的信息增益最大的划分作为最佳划分，记为V1（T）、V2（T）（T是使S的信息增益最大的v）5）递归地应用步骤1）4）于V1、V2及S1、S2上，直至满足一定的结束条件，例如，最大信息增益小于某个阈值 属性A的取值区间V作为其概念层次树的根，形成最高层第一次划分区间V1、V2是根的两个子结点，形成次高层递归地应用步骤1）4）就可以得到各层结点

9、属性概念分层的自动生成 连续属性概念分层的自动生成 设“气温”属性是目标属性，取值区间为100,100属性值及记录数如表所示属性值36182226记录数69362821划分区间100,100属性概念分层的自动生成 连续属性概念分层的自动生成 属性值36182226记录数69362821划分区间100,100G(100, 100, 2.0378=0G(G(G(G(最佳划分：V1=100, 22) (llu)不是强关联规则，则规则lv=(llv)也不是强关联规则 证明： sup_count(lv)sup_count(lu)i1i2 i5不是强关联规则i2i1i5、 i1i2i5都不可能是强关联规则

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

11、）=+1 /1-项集支持计数（2）for 每个项i （）if nmin_sup then L1=L1i /找出频繁1-项集Apriori算法算法描述（3）for (k=2；Lk-1；k+) （）for Lk-1中的每个项集lu （）for Lk-1中项集lu之后的每个项集lv if (lu1=lv1)(luk-2=lvk-2)(luk-1lvk-1) then /连接 Ck=Ckc /找出候选k-项集 for c中的每个(k-1)-项集s if then Ck=Ck-c /剪枝 （）for T中的每个事务t （）for t中的每个k-项集s if sCk then =+1 /k-项集支持计数A

12、priori算法算法描述 （）for Ck中的每个项集c （）if nmin_sup then Lk=Lkc /找出频繁k-项集 （） L=LLk /规则产生（4）for L中的每个频繁项集l （）for l中的每个1-项集l1 （） if then SR=SR(l-l1)=l1 /找出后件只有1项的强关联规则 R1=R1l1 /找出1-后件 Apriori算法算法描述（）for (j=2；Rj-1；j+) （）for Rj-1中的每个后件lu for Rj-1中后件lu之后的每个后件lv if (lu1=lv1)(luj-2=lvj-2)(luj-1lvj-1) then /连接 if th

13、en SR=SR(l-lj)=lj /找出后件有j项的强关联规则 Rj=Rjlj /找出j-后件l=i1i2i5lui1lvi2Apriori算法影响Apriori算法时间复杂度主要因素（1）事务集合当项数m增加：候选项集的数目和长度可能增加，频繁项集的数目和长度也可能增加，从而计算频繁项集及其支持计数的时间、扫描事务集合的次数、计算强关联规则的时间可能增加事务数n、事务平均宽度w增加：每次扫描事务集合的时间增加（2）最小支持度阈值min_supmin_sup越小，候选项集和频繁项集的数目越多、长度越长，扫描事务集合的次数越多，算法的运行时间越长（3）最小置信度阈值min_confmin_co

14、nf越小，强关联规则的数目越多，产生规则的运行时间越长频繁项集的紧凑表示 通常，从现实事务集合中产生的频繁项集的数量庞大为了提高关联规则挖掘算法的效率，频繁项集使用紧凑表示最大频繁项集：一个频繁项集的所有直接超集都不是频繁项集由最大频繁项集可以推导所有频繁项集 频繁项集非频繁项集最大频繁项集由 ad可以推导频繁项集a、d和ad由bcd可以推导b、c、d、bc、bd、cd和bcd 频繁项集的紧凑表示 为了高效找出最大频繁项集，可以将搜索空间按前缀或后缀变换为树（前缀树、后缀树 ），然后采用宽度或深度优先策略进行搜索前缀树后缀树频繁项集的紧凑表示 宽度优先是先搜索同一层的频繁项集，再搜索下一层的频

15、繁项集 深度优先是搜索到某层的一个频集时，先搜索更深层的频集，若没有频集则回溯，直至没有频项集产生也没有回溯 深度优先搜索策略可以更快地检测到频繁项集边界，通常用于搜索最大频繁项集 深度优先与最大频繁项集搜索频繁项集的紧凑表示 最大频繁项集集合是频繁项集集合的紧凑表示由最大频繁项集可以推导所有频繁项集，但由最大频繁项集不能推导它们的支持计数闭项集：一个项集的所有直接超集的支持计数都不等于该项集的支持计数频繁闭项集：一个项集是频繁项集并且是闭项集最小支持计数阈值是5 频繁项集的紧凑表示 定理 对于频繁项集l及其所有直接超集li=li(iI)，如果l是最大频繁项集，则l是频繁闭项集 sup_cou

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

17、有频繁项集 （） /找出由频繁闭(k+1)-项集推导的频繁k-项集 （）CLk=l|lCL,|l|=k /找出频繁闭k-项集频繁项集的紧凑表示通过频繁闭项集的支持计数计算其它频繁非闭项集的支持计数的算法描述（）for TLk中每个项集 /计算频繁非闭k-项集的支持计数 （）if then Lk= Lkl（） Lk= LkCLk（）L=LLk频繁项集的紧凑表示最小支持计数阈值是5，项集b:9、ad:5、bc:7、bd:6和bcd:5是频繁闭项集。写出计算频繁非闭项集的支持计数的过程 L3 = CL3 = bcd TL2 = bc,bd,cd CL2 = ad,bc,bd cd.sup_count

18、 = 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,dFP-growth算法 Apriori算法的不足：1）可能产生大量候选项集2）可能需要重复扫描数据库，通过模式匹配检查庞大的候选集合FP-growth算法采用一种称为FP树的结构表示事务集合中项集的关联，并在FP树上递归地找出所有频繁项集，算法并不产生候选基本思想：扫描

19、一次事务集合，找出频繁1-项集合L1基于L1，再扫描一次事务集合，构造表示事务集合中项集关联的FP树在FP树上递归地找出所有频繁项集最后在所有频繁项集中产生强关联规则 FP-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”标记nullFP-growth算法 3）

20、再扫描一次事务集合，对每个事务找出其中的频繁项并按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 FP-growth算法 FP树构造 事务项t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，

21、i2，i5t9i1，i2，i3L=i2:7, i1:6, i3:5, i4:2, i5:2 4）为方便遍历FP树，为FP树创建一个项表项表中每一行表示一个频繁项，并有一个指针指向它在FP树中的节点FP树中相同频繁项的节点通过指针连成链表 FP-growth算法 FP树构造 事务项t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3FP-growth算法 由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基。然后，构造它的条件FP树，并递归地在该树上进行挖掘。模式增长通过后缀模式与由条件FP

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

23、FP树FP树挖掘FP-growth算法 第二层递归：FP树挖掘条件模式基条件FP树产生的频繁项集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的条件FP树有多个分枝，进入第二层递归i3:5的条件FP树有两个分枝，进入第三层递归 FP-growth算法 第三层递归：FP树挖掘条件模式基条件FP树产生的频繁项集i1i3:3nul

24、l,i2:1、null:2i1i3:3i2i3:3null:3i2i3:3FP-growth算法 输入：事务集合T，最小支持度阈值min_sup，最小置信度阈值min_conf输出：强关联规则集合R_S步骤：（1）扫描T找出频繁1-项集合L（2）L中的项按支持计数降序排序（3）创建FP树的根节点null /创建FP树（4）for T中的每个事务t （）找出t中的频繁1-项集合Lt （）Lt中的项按L中的顺序排序 （）Insert-FP（Lt, null） /创建事务分枝（5）L_S=Search-FP（FP, null） /找出所有频繁项集（6）在L_S中产生强关联规则集合R_S算法描述FP-

25、growth算法 算法：Insert-FP算法（Li, Tr）输入：已排序频繁1-项集合Li，FP（子）树的根节点Tr输出：FP树（1）if Li不空 then （）取出Li中的第1个项i （）if Tr的某个子节点Node是i then （）=+1 （）else （）创建Tr的子节点Node为i （）=1 （）将Node加入项表链中（）Insert-FP（Li-i, Node）算法描述FP-growth算法 算法：Search-FP算法（T，）输入：（条件）FP树T，后缀模式输出：频繁项集集合L_S（1）if T中只有一个分枝P then （）for P上的节点的每个组合 （）= /产生频繁

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

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

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

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

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

31、一棵聚类树，使用数据的联接规则，透过一种架构方式，反复将数据进行分裂或聚合，以形成一个层次序列的聚类问题解 BIRCH、ROCK和Chameleon 等聚类算法分类基于模型的聚类算法（model-based method）基于“数据根据潜在的混合概率分布生成”假设，为每个簇假定一个模型，并寻找数据对给定模型的最佳拟合这类算法通过构建反映数据点空间分布的密度函数来定位簇，能考虑“噪声”数据和离群点的影响，鲁棒性较好 EM 、COBWEB 、SOM 均值聚类算法均值聚类算法假定所有数据对象可分为k个簇，每个簇的中心用均值表示对象间的相似性用距离度量聚类的准则是误差平方和准则 核心思想：首先选定k个

32、初始聚类中心，根据最小距离原则将每个数据对象分配到某一簇中然后不断迭代计算各个簇的聚类中心并依新的聚类中心调整聚类情况，直至收敛（J 值不再变化）均值聚类算法误差平方和准则若Nx是第Cx个簇中的对象数目，mx是这些对象的均值， J是所有簇的簇中各个对象与均值间的误差平方和之和对于不同的聚类，J的值不同使J 值极小的聚类是误差平方和准则下的最优结果度量了用k个聚类中心m1,mk代表k个簇C1,Ck时所产生的总的误差平方和均值聚类算法算法描述输入：数据对象集合D，簇数目k输出：k个簇的集合步骤：1. 从D中随机选取k个不同的数据对象作为k个簇C1，Ck的中心m1，mk2. repeat1）for

33、D中每个数据对象oa. 寻找i，b. 将o分配给簇Ci2）for 每个簇Ci（i=1，k）计算 3）计算平方误差3. Until J不再发生变化计算新的聚类中心，|Ci|为当前簇中的对象数目均值聚类算法算法简单，计算复杂度是O(nkt)，其中n是对象的总数，k是簇的个数，t是迭代次数，通常，kn且t ，继续计算5步迭代后的结果：x1x2x3x4x5(0.826,0.961)T(0.501,0.981)T(0.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)

34、T(0.777,0.960)T模糊c-均值聚类算法xi相对于 的隶属度 x1x2x3x4x50.9610.9810.9460.0380.0400.0390.0190.0540.9620.960聚类过程终止 分析技术及模型分类分析103分类与预测是普遍存在的问题，具有广泛的应用领域分类的任务是通过分析由已知类别数据对象组成的训练数据集，建立描述并区分数据对象类别的分类函数或分类模型（分类器）分类的目的是利用分类模型判定未知类别数据对象的所属类别，判定的目标是数据对象在类别属性（离散）上的取值预测也要通过分析训练数据集建立预测模型，然后利用模型预测数据对象，预测的目标是判定数据对象在预测属性（连续

35、）上的取值或取值区间分类与聚类有显著区别：分类中，训练样本的类别是已知的（有指导），而聚类中所有数据都没有类别标签（无指导）主要介绍分类过程、分类模型评估方法、常用分类算法分类分析分类过程分为两个阶段：学习阶段与分类阶段分类过程训练样本输入分类模型测试样本输入新数据分类算法学习过程分类过程每个训练样本由m+1个属性描述，X=（A1, , Am, C）Ai对应描述属性，可以是连续属性或离散属性C表示类别属性，有k个不同的类别，C=（c1, c2, , ck）从描述属性矢量（X-C）到类别属性C的映射函数H:（X-C）C分类规则、判定树等形式X=（A1, , Am）确定CX=（A1, , Am,C

36、）提供X=（A1, , Am)，确定C，比较C、C用于寻找映射函数H分类算法有多种：决策树分类算法、神经网络分类算法、贝叶斯分类算法、k-最近邻分类算法、遗传分类算法、粗糙集分类算法、模糊集分类算法等 分类算法可以根据下列标准进行比较和评估：1）准确率：分类模型正确地预测新样本所属类别的能力2）速度：建立和使用分类模型的计算开销3）强壮性：给定噪声数据或具有空缺值的数据，分类模型正确地预测的能力4）可伸缩性：给定大量数据，有效地建立分类模型的能力5）可解释性：分类模型提供的理解和洞察的层次分类算法评估标准利用测试数据集评估分类模型的准确率分类模型正确分类的测试样本数占总测试样本数的百分比准确率

37、可以接受，对新样本进行分类；否则，重新建立分类模型评估分类模型准确率的方法有保持、k-折交叉确认保持方法将已知类别的样本随机地划分为训练数据集与测试数据集两个集合，一般，训练数据集占2/3，测试数据集占1/3k-折交叉确认方法将已知类别的样本随机地划分为大小大致相等的k个子集S1, , Sk，并进行k次训练与测试第i次，Si作为测试数据集，其余子集的并集作为训练数据集k次训练得到k个分类模型，测试时，将出现次数最多的分类结果作为最终的分类结果分类模型评估方法适宜多峰分布的分类问题 决策树以树结构的形式表示，类似流程图一棵决策树由一个根节点，一组内部节点和一组叶节点组成决策树分类算法每个分枝表示

38、一个测试输出每个叶节点表示一个类，不同的叶节点可表示相同的类 根节点和内部节点表示在一个属性上的测试建立了决策树之后，可以对从根节点到叶节点的每条路径创建一条IF-THEN分类规则，易于理解沿着路径，每个内部节点-分枝对形成规则前件（IF部分）的一个合取项，叶节点形成规则后件（THEN部分）决策树分类算法IF 年龄=41 AND 信誉=中 THEN 购买计算机=是IF 年龄=30 AND 学生=否 THEN 购买计算机=否-否新顾客：教师，年龄45岁，收入较低但信誉很好该顾客是否会购买计算机？决策树分类算法的关键是建立决策树建立一棵决策树，需要解决的问题主要有：1）如何选择测试属性？测试属性的

39、选择顺序影响决策树的结构甚至决策树的准确率一般使用信息增益度量来选择测试属性2）如何停止划分样本？从根节点测试属性开始，每个内部节点测试属性都把样本空间划分为若干个（子）区域一般当某个（子）区域的样本同类时，就停止划分样本，有时也通过阈值提前停止划分样本决策树分类算法使用递归方式完成基本思想：首先，将整个训练数据集S、所有描述属性A1, A2, , Am作为分析对象如果S中的样本属于同一类别，则将S作为叶节点并用其中样本的类别标识，决策树建立完成否则在S上计算各个属性的信息增益G(C, Ak)，选择信息增益最大的属性Ai作为根节点的测试属性如果Ai的取值个数为v（取值记为a1, a2, , a

40、v），则Ai将S划分为v个子集S1, S2, , Sv，同时根节点产生v个分枝与之对应分别在训练数据子集S1, S2, , Sv、剩余描述属性A1, , Ai-1, Ai+1, , Am上采用相同方法递归地建立决策树子树决策树分类算法建立决策树Sv：S中Ai=av的样本集合递归过程中，某节点对应的训练数据（子）集由整个训练数据集S中满足从根节点到该节点路径上所有属性测试的训练样本组成某节点对应的描述属性是去除从根节点到该节点路径上所有已选描述属性后的剩余描述属性同一层内部节点选择的测试属性可能相同也可能不同决策树分类算法建立决策树递归结束条件：1）某节点对应的训练数据（子）集中的样本属于同一类

41、别2）某节点对应的训练数据（子）集为空此时，该节点作为叶节点并用父节点中占多数的样本类别标识3）某节点没有对应的（剩余）描述属性此时，该节点作为叶节点并用该节点中占多数的样本类别标识决策树分类算法建立决策树输入：训练数据集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的测试属性决策树分类算法算法描述（5）for Ai的每个可能取值aj

42、（1jv） （）产生S的一个子集Sj （）if Sj为空 then 创建对应Sj的节点Nj，以S中占多数的样本类别c标识Nj，并将Nj作为叶节点形成Node的一个分枝 （）else 由（Sj, A-Ai）创建子树形成Node的一个分枝决策树分类算法算法描述决策树分类算法信息增益类别属性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且属于类

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

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

45、过某度量标准判断哪些内部节点分枝是不可靠的，将这些内部节点变成叶节点并用其中占多数的记录类别标识，从而达到剪枝前馈神经网络分类算法神经网络可以模仿人脑，通过学习训练数据集，生成分类模型适用于数据没有任何明显模式的情况 样本属性可以是连续的，也可以是离散的神经网络由许多单元（神经元）以适当的方式连接起来构成单元模仿人脑的神经元，单元之间的连接相当于人脑中神经元的连接单元之间的连接方式有多种，从而形成了多种神经网络在分类中，应用较多的是前馈神经网络主要介绍前馈神经网络结构、网络学习及网络分类方法 前馈神经网络分类算法网络结构前馈神经网络是分层网络模型，具有一个输入层和一个输出层，输入层和输出层之间

46、有一个或多个隐藏层每个层具有若干单元，前一层单元与后一层单元之间通过有向加权边相连 ai：输入层第i个单元的输入 Ok：输出层第k个单元的输出 wij：隐藏层第j个单元与输入层第i个单元之间的连接权wjk：输出层第k个单元与隐藏层第j个单元之间的连接权 前馈神经网络分类算法网络结构输入层单元的数目与训练样本的描述属性数目对应，通常一个连续属性对应一个输入层单元，一个p值离散属性对应p个输入层单元输出层单元的数目与训练样本的类别数目对应（两类时，可以只有一个输出单元）隐层的层数及隐层的单元数尚无理论指导，一般通过实验选取输入层，各单元的输出可以等于输入，也可以按一定比例调节，使其值落在1和+1之

47、间其他层，每个单元的输入都是前一层各单元输出的加权和，输出是输入的某种函数，称为激活函数前馈神经网络分类算法网络结构隐藏层、输出层任意单元j的输入： 输出 ： Oj= f (netj) 如果f采用S型激活函数：对于隐藏层、输出层任意单元j，由输入计算输出的过程 ： 单元i的输出单元j与前一层单元i之间的连接权改变单元j活性的偏置，1，1上取值则前馈神经网络分类算法网络学习不同的单元的偏置及单元之间的连接权会获得不同的输出学习过程就是调整各单元的偏置及单元之间的连接权值，使每个训练样本在输出层单元上获得的输出与其期望输出间的误差最小学习使用误差后向传播算法基本思想：首先赋予每条有向加权边初始权值

48、、每个隐藏层与输出层单元初始偏置然后迭代地处理每个训练样本，输入它的描述属性值，计算实际输出，获取实际输出与期望输出间的误差将误差从输出层经每个隐藏层到输入层“后向传播”，根据误差修改权值和单元的偏置，使实际输出与期望输出之间的误差最小前馈神经网络分类算法网络学习样本实际输出与期望输出的误差Error： c：输出层的单元数目 Tk：输出层单元k的期望输出 Ok：单元k的实际输出 输出层单元k与前一层单元j之间的权值wjk的修改量wjk、单元k的偏置修改量为使Error最小，采用使Error沿梯度方向下降的方式单元j的输出Error对单元k的输入netk的负偏导数学习率，l 0, 1，避免陷入局

49、部最优解单元k的输出前馈神经网络分类算法网络学习隐藏层单元j与前一层单元i之间的权值wij的修改量wij、单元j的偏置j的修改量j ：单元i的输出单元j的输出与单元j相连的后一层单元k的误差 权值、偏置的修改 ：权值、偏置的更新有两种策略：1）实例更新：处理一个训练样本更新一次，常采用2）周期更新：处理所有训练样本后再一次更新处理所有训练样本一次，称为一个周期前馈神经网络分类算法网络学习结束条件：1）误差Error小于设定阈值，此时认为网络收敛，结束迭代2）前一周期所有的权值变化都很小，小于某个设定阈值3）前一周期预测的准确率很大，大于某个设定阈值3）周期数大于某个设定阈值在实际应用中，训练样

50、本很多，学习需要很多次迭代才能完成迭代次数与网络结构、初始权值与偏置、学习率的值有很大关系这些参数都是凭经验选取 算法特点前馈神经网络分类算法网络学习设训练样本s的描述属性值与类别属性值分别为1, 0, 1与1，前馈神经网络NT如图所示，NT中每条有向加权边的权值、每个隐藏层与输出层单元的偏置如表所示，学习率为。写出输入s训练NT的过程 x1x2x3w14w15w24w25w34w35w46w564561010.20.30.40.10.50.20.30.20.40.20.1前馈神经网络分类算法网络学习x1x2x3w14w15w24w25w34w35w46w564561010.20.30.40.

51、10.50.20.30.20.40.20.1单元j输入netj输出Oj40.2*1+0.4*0+(0.5)*1+(0.4)=0.71/(1+e(0.7)=0.3325(0.3)*1+0.1*0+(0.2)*1+0.2=0.11/(1+e0.1)=0.5256(0.3) *0.332+(0.2)*0.525+0.1=0.1051/(1+e(0.105)=0.474单元jErrj60.474*(10.474)*(10.474)=0.131150.525*(10.525)*(0.1311*(0.2)=0.006540.332*(10.332)*(0.1311*(0.3)=0.0087前馈神经网络分类

52、算法网络学习x1x2x3w14w15w24w25w34w35w46w564561010.20.30.40.10.50.20.30.20.40.20.1w340.5+0.9*(0.0087)*1=0.508w350.2+0.9*(0.0065)*1=0.19460.1+0.9*0.1311=0.21850.2+0.9*(0.0065)=0.19440.4+0.9*(0.0087)=0.408w460.3+0.9*0.1311*0.332=0.261w560.2+0.9*0.1311*0.525=0.138w140.2+0.9*(0.0087)*1=0.192w150.3+0.9*(0.0065)

53、*1=0.306w240.4+0.9*(0.0087)*0=0.4w250.1+0.9*(0.0065)*0=0.1单元jErrj60.131150.006540.0087单元j输出Oj40.33250.52560.474前馈神经网络分类算法算法描述输入：训练数据集S，前馈神经网络NT，学习率l输出：经过训练的前馈神经网络NT步骤：（1）在区间-1, 1上随机初始化NT中每条有向加权边的权值、每个隐藏层与输出层单元的偏置（2）while 结束条件不满足 （）for S中每个训练样本s （）for 隐藏层与输出层中每个单元j （）for 输出层中每个单元k Errk=Ok(1- Ok)( Tk

54、- Ok)从第一个隐藏层开始向前传播输入 前馈神经网络分类算法算法描述 （）for 隐藏层中每个单元j （）for NT中每条有向加权边的权值wij wij= wij+lErrjOi （）for 隐藏层与输出层中每个单元的偏置j j=j+lErrj从最后一个隐藏层开始向后传播误差 学习过程由正向传播和反向传播组成正向传播过程：训练样本从输入层，经隐藏层，传向输出层，每一层单元的状态只影响下一层单元的状态反向传播过程：输出层不能得到期望输出，则将误差沿原来的连接通路传回，通过修改权值和偏置，使误差最小 前馈神经网络分类算法网络分类学习结束后，神经网络得到一组固定的权值及偏置新样本到来后，将其描述

55、属性值送入输入层各单元，从输入层到输出层正向传播，计算输出层各单元的值O1, O2, , On令r=max(O1, O2, , On)，则第r个输出层单元所代表的类别就是该样本所属的类别新样本X=（x1, x2, x3）送入输入层计算出O61，则表示X应属于A类O60，则表示X应属于B类若O6，则拒绝分类贝叶斯分类算法贝叶斯分类：应用贝叶斯公式求解分类问题 贝叶斯公式：贝叶斯分类公式：m个描述属性A1=a1, , Am=am的联合概率 类别属性C=c的概率（先验概率 ）已知C=c时，A1=a1, , Am=am的条件概率（类条件概率 ）已知A1=a1, , Am=am时，C=c的条件概率（类别

56、c的后验概率）贝叶斯分类的分类就是给定新样本的描述属性值a1,am，计算各个类别的后验概率，后验概率最大的类别就是新样本的类别贝叶斯分类算法怎样算 、 ？先验概率p(c) 可以通过统计训练数据集中每个类别训练样本所占比例进行估计在计算各个类条件概率时，一般应用条件独立假设简化计算朴素贝叶斯分类 C和A1, ., Am有直接依赖关系，A1, ., Am之间相互独立 贝叶斯分类算法新样本为（3140，中，否，优） p(是)9/14 p(3140|是)4/9；p(中|是)4/9；p(否|是)3/9；p(优|是)3/9；p(是)p(3140|是)p(中|是)p(否|是)p(优|是)9/144/94/9

57、3/93/98/567年龄收入学生信誉购买计算机30高否中否30高否优否3140高否中是41中否中是41低是中是41低是优否3140低是优是30中否中否30低是中是41中是中是30中是优是3140中否优是3140高是中是41中否优否贝叶斯分类算法新样本为（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所以新样本的类别为是 年龄收入学生信誉购买计算机30高否中否30高否优否3140高否中是41中否中是41低是中是41低是优否314

58、0低是优是30中否中否30低是中是41中是中是30中是优是3140中否优是3140高是中是41中否优否贝叶斯分类算法输入：训练数据集S、新样本r( ar1, , arm )输出：新样本的类别cr步骤：（1）for S中每个训练样本s(as1, , asm, cs) （）增加类别cs的计数cs.count （）for 每个描述属性值asi 增加类别cs中描述属性值asi的计数cs.asi.count（2）for 每个类别c （） 算法描述贝叶斯分类算法 （）for 每个描述属性Ai （）for 每个描述属性值ai （）for 每个a1, , am（3）算法描述朴素贝叶斯分类假设各个描述属性在给定

59、类别属性时条件独立这个条件独立假设在现实应用中可能不成立树增强朴素贝叶斯分类削弱了这个限制 树增强朴素贝叶斯分类算法树增强朴素贝叶斯分类假设C和A1, ., Am有直接依赖关系，A1, ., Am之间也有依赖关系（允许各个描述属性之间形成树型结构），削弱了各个描述属性在给定类别属性时条件独立假设，增强了朴素贝叶斯分类节点C和节点A1, ., Am有有向边相连，C是A1, ., Am的父节点A1, ., Am之间有有向边相连并形成树，根节点的父节点只有C，其它节点的父节点除了C之外还有一个节点 新样本a1, , a5的类别： 树增强朴素贝叶斯分类算法树增强朴素贝叶斯分类树型结构构造方法的基本思想

60、：首先，计算在给定类别属性C时，描述属性A1, ., Am之间的依赖强度，共得到 个依赖强度然后，根据从强到弱的原则选择m-1个依赖强度，添加相应描述属性之间的无向边，并使各个描述属性之间形成无向树最后，选择根节点，为无向边添加方向形成有向树在给定类别属性C时，描述属性Ai和 Aj之间的依赖强度可以利用条件互信息描述： 树增强朴素贝叶斯分类算法输入：训练数据集S输出：树增强朴素贝叶斯分类的贝叶斯网结构TAN步骤：（1）扫描S，计算在给定类别属性C时，描述属性A1, ., Am之间的条件互信息（2）构造一个无向完全图，以描述属性为节点，以条件互信息为边的权重（3）构造上述无向完全图的最大生成树（