数据分析方法及模型课件

资源描述

《数据分析方法及模型课件》由会员分享，可在线阅读，更多相关《数据分析方法及模型课件（200页珍藏版）》请在金锄头文库上搜索。

1、分析技术及模型分析技术及模型数据预处理数据预处理关联分析技术关联分析技术聚类分析技术聚类分析技术分类分析技术分类分析技术异常分析技术异常分析技术贝叶斯网贝叶斯网影响图影响图1分析技术及模型分析技术及模型数据预处理数据预处理2数据预处理数据预处理各种数据分析技术的对象是数据源中的数据各种数据分析技术的对象是数据源中的数据数据源中的数据可能不完整（如某些属性的值不确定或空缺）、数据源中的数据可能不完整（如某些属性的值不确定或空缺）、含噪声和不一致（如同一个属性在不同表中的名称不同）含噪声和不一致（如同一个属性在不同表中的名称不同）、量、量纲不同纲不同如果直接在这些未经处理的数据上进行分析，结果不

2、一定准确，如果直接在这些未经处理的数据上进行分析，结果不一定准确，效率也可能较低效率也可能较低需要使用清理、集成、变换、归约等预处理方法改善数据质量，需要使用清理、集成、变换、归约等预处理方法改善数据质量，从而提高数据分析的效率与质量从而提高数据分析的效率与质量主要介绍数据清理、集成、变换、规约等预处理技术主要介绍数据清理、集成、变换、规约等预处理技术3数据清理数据清理数据清理用于消除噪声、数据不一致及数据不完整数据清理用于消除噪声、数据不一致及数据不完整噪声可以通过平滑、识别孤立点等方法进行消除噪声可以通过平滑、识别孤立点等方法进行消除分箱技术：分箱技术：将数据排序，根据等深或等宽分布规则

3、将数据分布将数据排序，根据等深或等宽分布规则将数据分布到不同箱中，将同一箱中的数据用用该箱中数据的平均值或中到不同箱中，将同一箱中的数据用用该箱中数据的平均值或中值、边界值替换（平均值平滑、中值平滑、边界平滑）值、边界值替换（平均值平滑、中值平滑、边界平滑）每个箱中的每个箱中的数据个数或数据个数或取值区间相取值区间相等等设某属性的值为设某属性的值为18，12，3，9，7，6，15，21，16，采用分箱技术平滑数据，采用分箱技术平滑数据消除噪声。分布规则为等深、深度为消除噪声。分布规则为等深、深度为3，平滑规则为平均值平滑，平滑规则为平均值平滑首先，将属性的值排序为首先，将属性的值排序为3,

4、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.34数据清理数据清理数据不完整可以使用下列方法消除：数据不完整可以使用下列方法消除：1）使用一个全局常量填充）使用一个全局常量填充2）使用属性平均值填充）使用属性平均值填充3）使用相同类的属性平均值填充）使用相同类的属性平均值填充4）使用最可能的值填充）使用最可能的值填充需要采用预测算法，预测给定样需要采用预测算法，预测给定样本的最可能的值并填充本的最可能的值并填充

5、数据不一致可以通过元数据消除（描述数据的数据）数据不一致可以通过元数据消除（描述数据的数据）5数据集成数据集成数据集成是将多个数据源中的数据结合起来存放在一个一致的数据集成是将多个数据源中的数据结合起来存放在一个一致的数据存储（如数据仓库）中数据存储（如数据仓库）中这些数据源可能包括多个数据库、数据立方体或一般文件这些数据源可能包括多个数据库、数据立方体或一般文件在数据集成时，需要消除冗余在数据集成时，需要消除冗余能够由另外的属性能够由另外的属性“导出导出”、命名的不一致的属性命名的不一致的属性冗余可以通过相关分析进行检测冗余可以通过相关分析进行检测属性属性A、B之间的相关性计算：之间的相关性

6、计算：rA,B0，A与与B正相关，正相关，A的值随着的值随着B的值的增加而增加的值的增加而增加rA,B0，A与与B负相关，负相关，A的值随着的值随着B的值的增加而减少的值的增加而减少rA,B=0，A与与B独立。因此，独立。因此，|rA,B|很大时，很大时，A与与B可以去除一个可以去除一个平均值平均值方差方差6数据变换数据变换将属性数据按比例缩放，使之落入一个小的特定区间，如将属性数据按比例缩放，使之落入一个小的特定区间，如1.0到到1.0或或0.0到到1.0 最小最小-最大规格化：最大规格化：minA，maxA为数值属性为数值属性A规格化前的取值区间规格化前的取值区间new_ minA，ne

7、w_ maxA 为为A规格化后的取值区间，最小规格化后的取值区间，最小-最最大规格化根据下式将大规格化根据下式将A的值的值v规格化为值规格化为值v采用最小采用最小-最大规格化方法将最大规格化方法将100，100中的中的66规格化到区间规格化到区间0，1 7数据变换数据变换零零-均值规格化：均值规格化：对均值为对均值为、方差为、方差为的数值属性的数值属性A将将A的值的值v规格化为值规格化为值v设某属性的平均值、标准差分别为设某属性的平均值、标准差分别为80、25，采用零，采用零-均值规格化均值规格化66 小数定标规格化小数定标规格化：数值属性数值属性A的最大绝对值为的最大绝对值为max|A

8、|A，j为满足为满足的最小整的最小整数数将将A的值的值v规格化为值规格化为值v规格化规格化 100，100中的中的66A的最大绝对值为的最大绝对值为120，j为为3 8数据规约数据规约数据归约技术可以用来得到数据集的归约表示，它小得多，但仍数据归约技术可以用来得到数据集的归约表示，它小得多，但仍接近于保持原数据集的完整性接近于保持原数据集的完整性在归约后的数据集上分析将更有效，并产生相同（或几乎相同）在归约后的数据集上分析将更有效，并产生相同（或几乎相同）的分析结果的分析结果归约方法主要有：属性归约归约方法主要有：属性归约、记录归约、记录归约属性规约：属性规约：删除不相关的或冗余的属性

9、减小数据集，目标是找出删除不相关的或冗余的属性减小数据集，目标是找出最小属性集，最小属性集，使得数据在其上的概率分布尽可能地接近在原属性使得数据在其上的概率分布尽可能地接近在原属性集上的概率分布集上的概率分布常用方法：粗糙集中的属性约简、决策树常用方法：粗糙集中的属性约简、决策树记录规约：记录规约：用少量记录代表或替换原有记录，从而减小数据集用少量记录代表或替换原有记录，从而减小数据集常用方法：常用方法：抽样、数据概化抽样、数据概化9数据规约数据规约数据概化：数据概化：采用面向属性归纳，根据属性的概念分层，通过阈值采用面向属性归纳，根据属性的概念分层，通过阈值控制，将属性的低层属性值用相

10、应高层概念替换，并合并由此得控制，将属性的低层属性值用相应高层概念替换，并合并由此得到的相同记录到的相同记录概念分层一般用树结构描述，称为概念层次树概念分层一般用树结构描述，称为概念层次树阈值控制面向属性归纳过程，每个属性都有概念层次树及阈值阈值控制面向属性归纳过程，每个属性都有概念层次树及阈值首先根据属性首先根据属性A的概念层次树，将关系表中的概念层次树，将关系表中A的属性值转换为最低的属性值转换为最低层的相应概念（叶概念），统计关系表中层的相应概念（叶概念），统计关系表中A的不同叶概念个数的不同叶概念个数如果如果A的不同叶概念个数大于的不同叶概念个数大于A的属性阈值，再根据的属性阈值，再

11、根据A的概念层次的概念层次树，将关系表中树，将关系表中A的叶概念转换为上一层的相应概念的叶概念转换为上一层的相应概念如此重复，直至关系表中如此重复，直至关系表中A的不同概念个数小于等于的不同概念个数小于等于A的属性阈值；的属性阈值；最后合并相同记录，并统计重复记录数目最后合并相同记录，并统计重复记录数目10数据规约数据规约属性阈值均为属性阈值均为4记录由记录由6个归约为个归约为3个个count的值表示重复记录数目的值表示重复记录数目11属性概念分层的自动生成属性概念分层的自动生成概念分层一般由系统用户、领域专家提供，但非常耗时、乏味概念分层一般由系统用户、领域专家提供，但非常耗时、乏味介绍离

12、散属性与连续属性自动生成概念分层的方法介绍离散属性与连续属性自动生成概念分层的方法离散属性概念分层的自动生成离散属性概念分层的自动生成概念层次树中高层的概念个数一般少于低层的概念个数概念层次树中高层的概念个数一般少于低层的概念个数首先统计各个概念的不同值个数，个数最少的概念在最高层，依首先统计各个概念的不同值个数，个数最少的概念在最高层，依次类推，然后根据结构的从属关系，确定各层的概念及从属关系次类推，然后根据结构的从属关系，确定各层的概念及从属关系地址地址国家国家省省市市中国中国云南省云南省昆明市昆明市中国中国云南省云南省大理市大理市中国中国四川省四川省成都市成都市中国中国贵州省贵州省

13、贵阳市贵阳市中国中国云南省云南省玉溪市玉溪市中国中国云南省云南省曲靖市曲靖市12属性概念分层的自动生成属性概念分层的自动生成连续属性概念分层的自动生成连续属性概念分层的自动生成连续属性可以通过离散化递归地自动生成概念分层连续属性可以通过离散化递归地自动生成概念分层离散化可以基于熵完成，主要步骤：离散化可以基于熵完成，主要步骤：1）计算关系表）计算关系表r中在属性中在属性A的取值区间的取值区间V上的记录集合上的记录集合S的熵的熵 |c|：S中属于目标类中属于目标类c的记录数的记录数|S|：S中的记录数中的记录数 2）对）对A在在V上取的每个上取的每个v，用，用v划分划分V为为v1（v）、）、

14、v2（v），划分），划分S为为S1，S2，计算在此划分下，计算在此划分下S的熵的熵 E(S1)、E(S2)分别为分别为S1、S2的熵的熵 13属性概念分层的自动生成属性概念分层的自动生成连续属性概念分层的自动生成连续属性概念分层的自动生成 3）对在）对在V上的每个划分上的每个划分v1（v）、）、v2（v），计算在此划分下），计算在此划分下S的的信息增益信息增益 4）选择使）选择使S的信息增益最大的划分作为最佳划分，记为的信息增益最大的划分作为最佳划分，记为V1（T）、）、V2（T）（）（T是使是使S的信息增益最大的的信息增益最大的v）5）递归地应用步骤）递归地应用步骤1）4）于）于V1、V2

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

16、所示属性值及记录数如表所示属性值属性值3 36 6181822222626记录数记录数6 69 9363628282121划分区间划分区间100,10015属性概念分层的自动生成属性概念分层的自动生成连续属性概念分层的自动生成连续属性概念分层的自动生成属性值属性值3 36 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

17、, 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不是强关联规则不是强关联规则i2i1i5、 i1i2i5都不可能是都不可能是强关联规则强关联规则l=i1i2i5lvi1、i2lui1i236Apriori算法算法压缩强关联搜索空间压缩强关联搜索空间对于每个频繁项集，第一层产生后件只有一项的强关联

18、规则，对于每个频繁项集，第一层产生后件只有一项的强关联规则，并生成它们的并生成它们的1-后件集合后件集合R1第二层产生后件有两项的强第二层产生后件有两项的强关联规则，并生成它们的关联规则，并生成它们的2-后后件集合件集合R2R2通过通过R1中的后件进行连接中的后件进行连接运算，再通过置信度计算产运算，再通过置信度计算产生生依次类推，可以产生所有强依次类推，可以产生所有强关联规则关联规则37Apriori算法算法算法描述算法描述输入：事务集合输入：事务集合T，最小支持度阈值，最小支持度阈值min_sup，最小置信度阈值，最小置信度阈值min_conf输出：强关联规则集合输出：强关联规则集合SR变

19、量：频繁变量：频繁k-项集集合项集集合Lk，候选，候选k-项集集合项集集合Ck，频繁项集集合，频繁项集集合L，k-后件集合后件集合Rk步骤：步骤：/频繁项集产生频繁项集产生（1）for T中的每个事务中的每个事务t （1.1）for t中的每个项中的每个项i （）（）i.sup_count=i.sup_count+1 /1-项集支持计数项集支持计数（2）for 每个项每个项i （2.1）if i.sup_countnmin_sup then L1=L1i /找出频繁找出频繁1-项集项集38Apriori算法算法算法描述算法描述（3）for (k=2；Lk-1；k+) （3.1）for Lk-1

20、中的每个项集中的每个项集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 /剪枝剪枝（3.2）for T中的每个事务中的每个事务t （）（）for t中的每个中的每个k-项集项集s if sCk then s.sup_count=s.sup_count+1 /k-项集支持计数项集支持计数39Apriori算法算法算法描述算法描述（3.3）

21、for Ck中的每个项集中的每个项集c （）（）if c.sup_countnmin_sup then Lk=Lkc /找出频繁找出频繁k-项集项集（3.4） L=LLk /规则产生规则产生（4）for L中的每个频繁项集中的每个频繁项集l （4.1）for l中的每个中的每个1-项集项集l1 （）（） if then SR=SR(l-l1)=l1 /找出后件只有找出后件只有1项的强关联规则项的强关联规则 R1=R1l1 /找出找出1-后件后件 40Apriori算法算法算法描述算法描述（4.2）for (j=2；Rj-1；j+) （）（）for Rj-1中的每个后件中的每个后件lu for

22、 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=i1i2i5lui1lvi241Apriori算法算法影响影响Apriori算法时间复杂度主要因素算法时间复杂度主要因素（1）事务集合）事务集合当项数当项数m增加：候选项集的数目和长度可能增加，频繁项集的数目增加：候选项集的数目和长度可能增加，频繁项集的数目和长度也可能增加，从而计算频繁项集及其支持

23、计数的时间、扫描和长度也可能增加，从而计算频繁项集及其支持计数的时间、扫描事务集合的次数、计算强关联规则的时间可能增加事务集合的次数、计算强关联规则的时间可能增加事务数事务数n、事务平均宽度事务平均宽度w增加：每次扫描事务集合的时间增加增加：每次扫描事务集合的时间增加（2）最小支持度阈值）最小支持度阈值min_supmin_sup越小，候选项集和频繁项集的数目越多、长度越长，扫描越小，候选项集和频繁项集的数目越多、长度越长，扫描事务集合的次数越多，算法的运行时间越长事务集合的次数越多，算法的运行时间越长（3）最小置信度阈值）最小置信度阈值min_confmin_conf越小，强关联规则的数目越

24、多，产生规则的运行时间越长越小，强关联规则的数目越多，产生规则的运行时间越长42频繁项集的紧凑表示频繁项集的紧凑表示通常，从现实事务集合中产生的频繁项集的数量庞大通常，从现实事务集合中产生的频繁项集的数量庞大为了提高关联规则挖掘算法的效率，频繁项集使用紧凑表示为了提高关联规则挖掘算法的效率，频繁项集使用紧凑表示最大频繁项集：最大频繁项集：一个频繁项集的所有直接超集都不是频繁项集一个频繁项集的所有直接超集都不是频繁项集由最大频繁项集可以推导所有频繁项集由最大频繁项集可以推导所有频繁项集频繁项集频繁项集非频繁项集非频繁项集最大频繁项集最大频繁项集由由 ad可以推导频繁项集可以推导频繁项集a、d

25、和和ad由由bcd可以推导可以推导b、c、d、bc、bd、cd和和bcd 43频繁项集的紧凑表示频繁项集的紧凑表示为了高效找出最大频繁项集，可以将搜索空间按前缀或后缀变换为为了高效找出最大频繁项集，可以将搜索空间按前缀或后缀变换为树（前缀树、后缀树树（前缀树、后缀树），然后采用宽度或深度优先策略进行搜索），然后采用宽度或深度优先策略进行搜索前缀树前缀树后缀树后缀树44频繁项集的紧凑表示频繁项集的紧凑表示宽度优先是先搜索同一层的频繁项集，再搜索下一层的频繁项集宽度优先是先搜索同一层的频繁项集，再搜索下一层的频繁项集深度优先是搜索到某层的一个频集时，先搜索更深层的频集，若没深度优先是搜索到

26、某层的一个频集时，先搜索更深层的频集，若没有频集则回溯，直至没有频项集产生也没有回溯有频集则回溯，直至没有频项集产生也没有回溯深度优先搜索策略可以更快地检测深度优先搜索策略可以更快地检测到频繁项集边界，通常用于搜索最到频繁项集边界，通常用于搜索最大频繁项集大频繁项集深度优先与最大频繁项集搜索深度优先与最大频繁项集搜索45频繁项集的紧凑表示频繁项集的紧凑表示最大频繁项集集合是频繁项集集合的紧凑表示最大频繁项集集合是频繁项集集合的紧凑表示由最大频繁项集可以推导所有频繁项集，但由最大频繁项集不能推由最大频繁项集可以推导所有频繁项集，但由最大频繁项集不能推导它们的支持计数导它们的支持计数闭项集：

27、闭项集：一个项集的所有直接超集的支持计数都不等于该项集的支一个项集的所有直接超集的支持计数都不等于该项集的支持计数持计数频繁闭项集：频繁闭项集：一一个项集是频繁项个项集是频繁项集并且是闭项集集并且是闭项集最小支持计最小支持计数阈值是数阈值是5 46频繁项集的紧凑表示频繁项集的紧凑表示定理定理对于频繁项集对于频繁项集l及其所有直接超集及其所有直接超集li=li(iI)，如果，如果l是最大是最大频繁项集，则频繁项集，则l是频繁闭项集是频繁闭项集 sup_count(l) nmin_sup 证明：证明：定理定理对于频繁项集对于频繁项集l及其所有直接超集及其所有直接超集li=li(iI)，如果

28、，如果l不是闭不是闭项集，则项集，则证明：证明：基于该定理，频繁非基于该定理，频繁非闭项集的支持计数可闭项集的支持计数可以通过频繁闭项集的以通过频繁闭项集的支持计数确定支持计数确定47频繁项集的紧凑表示频繁项集的紧凑表示项集项集c不是闭项集，它的支持不是闭项集，它的支持计数等于项集计数等于项集bc的支持计数的支持计数频繁项集、频繁闭项集与最大频繁项集的关系频繁项集、频繁闭项集与最大频繁项集的关系： 48频繁项集的紧凑表示频繁项集的紧凑表示通过频繁闭项集的支持计数计算其它频繁非闭项集的支持计数通过频繁闭项集的支持计数计算其它频繁非闭项集的支持计数的算法描述的算法描述输入：频繁闭项集集合

29、输入：频繁闭项集集合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-项集项集49频繁项集的紧凑表示频繁项集的紧凑表示通过频繁闭项集的支持计数计算其它频繁非闭项集的支持计数通过频

30、繁闭项集的支持计数计算其它频繁非闭项集的支持计数的算法描述的算法描述（4.3）for TLk中每个项集中每个项集 /计算频繁非闭计算频繁非闭k-项集的支持计数项集的支持计数（）（）if then Lk= Lkl（4.4） Lk= LkCLk（4.5）L=LLk50频繁项集的紧凑表示频繁项集的紧凑表示最小支持计数阈值是最小支持计数阈值是5，项集，项集b:9、ad:5、bc:7、bd:6和和bcd:5是是频繁闭项集。写出计算频繁非闭项集的支持计数的过程频繁闭项集。写出计算频繁非闭项集的支持计数的过程 L3 = CL3 = bcd TL2 = bc,bd,cd CL2 = ad,bc,bd cd.

31、sup_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,d51FP-growth算法算法 Apriori算法的不足：算法的不足：1）可能产生大量候选项集）可能产生大量候选项集2）可能需要重复扫描数据库，通过模式匹配检查庞大的候选集合）可能需要重复扫描数据库，通过模式匹配检查庞大的候选集合FP-growth算法

32、采用一种称为算法采用一种称为FP树的结构表示事务集合中项集的关树的结构表示事务集合中项集的关联，并在联，并在FP树上递归地找出所有频繁项集，算法并不产生候选树上递归地找出所有频繁项集，算法并不产生候选基本思想：基本思想：扫描一次事务集合，找出频繁扫描一次事务集合，找出频繁1-项集合项集合L1基于基于L1，再扫描一次事务集合，构造表示事务集合中项集关联的，再扫描一次事务集合，构造表示事务集合中项集关联的FP树树在在FP树上递归地找出所有频繁项集树上递归地找出所有频繁项集最后在所有频繁项集中产生强关联规则最后在所有频繁项集中产生强关联规则 52FP-growth算法算法 1）扫描一次事务集合，找出

33、频繁）扫描一次事务集合，找出频繁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”标标记记null53FP-growth算法算法 3）再扫描一次事务集合，对每个事务找出其）再扫描一次事务集合，对每个事务找出其中的频繁项并按中的频繁项并按L中的顺

34、序排序，为每个事务中的顺序排序，为每个事务创建一个分枝，事务分枝路径上的节点就是创建一个分枝，事务分枝路径上的节点就是该事务中的已排序频繁项该事务中的已排序频繁项对于各个事务分枝，如果可以共享路径则共对于各个事务分枝，如果可以共享路径则共享并且在各个节点上记录共享事务数目享并且在各个节点上记录共享事务数目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 54FP-growth算法算法 FP树构造树构造事

35、务事务项项t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3L=i2:7, i1:6, i3:5, i4:2, i5:2 4）为方便遍历）为方便遍历FP树，为树，为FP树创建一个项表树创建一个项表项表中每一行表示一个频繁项，并有一个指项表中每一行表示一个频繁项，并有一个指针指向它在针指向它在FP树中的节点树中的节点FP树中相同频繁项的节点通过指针连成链表树中相同频繁项的节点通过指针连成链表 55FP-growth算法算法 FP树构造树构造事务事务项项t1i1，i2，i5t2i2，i4t3i2，

36、i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i356FP-growth算法算法由长度为由长度为1的频繁模式（初始后缀模式）开始，构造它的条件的频繁模式（初始后缀模式）开始，构造它的条件模式基。然后，构造它的条件模式基。然后，构造它的条件FP树，并递归地在该树上进行挖树，并递归地在该树上进行挖掘。模式增长通过后缀模式与由条件掘。模式增长通过后缀模式与由条件FP树产生的频繁模式连接树产生的频繁模式连接实现实现条件模式基：条件模式基：一个一个“子数据库子数据库”，由，由FP树中与后缀模式一起出树中与后缀模式一起出现的前缀路径集组成现的前缀路

37、径集组成条件条件FP树：树：条件模式基中，由满足最小支持度阈值的节点构成条件模式基中，由满足最小支持度阈值的节点构成的树的树FP树挖掘树挖掘i5:2的条件模式基的条件模式基null,i2,i1:2 i5:2 与条件与条件FP树树 57FP-growth算法算法递归过程：递归过程：1）如果条件）如果条件FP树只有一个分枝，则分枝路径上的节点的一个树只有一个分枝，则分枝路径上的节点的一个组合就是一个前缀模式组合就是一个前缀模式，一个前缀模式，一个前缀模式与后缀模式与后缀模式产生一产生一个频繁项集个频繁项集（递归出口）（递归出口）2）否则用）否则用L中的频繁项中的频繁项i增长后缀模式增长后缀模式

38、（i ，增长时，增长时，按逆序方式处理，即先考虑按逆序方式处理，即先考虑L的最后一项），然后构造增长后的最后一项），然后构造增长后缀模式缀模式i 的条件模式基与条件的条件模式基与条件FP树，递归上述过程树，递归上述过程初始时，初始时，=null，null的条件的条件FP树就是树就是FP树树FP树挖掘树挖掘58FP-growth算法算法第二层递归：第二层递归：FP树挖掘树挖掘条件模式基条件模式基条件条件FPFP树树产生的频繁项集产生的频繁项集i5:2null,i2,i1:2i2i5:2、i1i5:2、i2i1i5:2i4:2null,i2,i1:1、null,i2:1i2i4 :2i3:5nu

39、ll,i2,i1:1、null,i2:2、null,i1:2、i1:6null,i2:4、null:2i2i1 :4i2:7null:7第一层递归：第一层递归：=nullnull的条件的条件FP树有树有多个分枝，进入第多个分枝，进入第二层递归二层递归i3:5的条件的条件FP树有两个树有两个分枝，进入第三层递归分枝，进入第三层递归 59FP-growth算法算法第三层递归：第三层递归：FP树挖掘树挖掘条件模式基条件模式基条件条件FPFP树树产生的频繁项集产生的频繁项集i1i3:3null,i2:1、null:2i1i3:3i2i3:3null:3i2i3:360FP-growth算法算法输入

40、：事务集合输入：事务集合T，最小支持度阈值，最小支持度阈值min_sup，最小置信度阈值，最小置信度阈值min_conf输出：强关联规则集合输出：强关联规则集合R_S步骤：步骤：（1）扫描）扫描T找出频繁找出频繁1-项集合项集合L（2）L中的项按支持计数降序排序中的项按支持计数降序排序（3）创建）创建FP树的根节点树的根节点null /创建创建FP树树（4）for T中的每个事务中的每个事务t （4.1）找出）找出t中的频繁中的频繁1-项集合项集合Lt （4.2）Lt中的项按中的项按L中的顺序排序中的顺序排序（4.3）Insert-FP（Lt, null） /创建事务分枝创建事务分枝（5）L

41、_S=Search-FP（FP, null） /找出所有频繁项集找出所有频繁项集（6）在）在L_S中产生强关联规则集合中产生强关联规则集合R_S算法描述算法描述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 （）（）Node.count=Node.count+1 （1.3）else （）创

42、建（）创建Tr的子节点的子节点Node为为i （）（）Node.count=1 （）将（）将Node加入项表链中加入项表链中（1.4）Insert-FP（Li-i, Node）算法描述算法描述62FP-growth算法算法算法：算法：Search-FP算法（算法（T，）输入：（条件）输入：（条件）FP树树T，后缀模式，后缀模式输出：频繁项集集合输出：频繁项集集合L_S（1）if T中只有一个分枝中只有一个分枝P then （1.1）for P上的节点的每个组合上的节点的每个组合（）（）= /产生频繁项集产生频繁项集（）（）L_S= L_S（2）else （2.1）for T中的每个频繁项

43、中的每个频繁项i （）（）=i /增长后缀模式增长后缀模式（）构造（）构造的条件模式基及其条件的条件模式基及其条件FP树树T （）（） Search-FP（T, ）算法描述算法描述63分析技术及模型分析技术及模型聚类分析聚类分析64将物理或抽象对象的集合分成相似的对象类的过程将物理或抽象对象的集合分成相似的对象类的过程使得同一个簇中的对象之间具有较高的相似性，而不同簇中的使得同一个簇中的对象之间具有较高的相似性，而不同簇中的对象具有较高的相异性对象具有较高的相异性是数据挖掘、模式识别等研究方向的重要研究内容之一，在识是数据挖掘、模式识别等研究方向的重要研究内容之一，在识别数据的内在结构方面具

44、有极其重要的作用别数据的内在结构方面具有极其重要的作用广泛应用于模式识别、数据分析、图像处理和市场研究等领域，广泛应用于模式识别、数据分析、图像处理和市场研究等领域，对生物学、心理学、考古学、地质学及地理学等研究也有重要对生物学、心理学、考古学、地质学及地理学等研究也有重要作用作用主要介绍聚类概念、聚类过程、常用聚类算法主要介绍聚类概念、聚类过程、常用聚类算法聚类分析聚类分析65=o o1 1, o, o2 2, , o, , on n 表示一个对象集合表示一个对象集合o oi i表示第表示第i i个对象，个对象，i i=1=1, , 2 2,n,n C Cx x表示第表示第x x个簇，

45、个簇，C Cx x ，x=x=1 1，2 2，k kSimilarity(Similarity(o oi i, o, oj j) )表示对象表示对象o oi i与对象与对象o oj j之间的相似度之间的相似度若各簇若各簇CxCx是刚性聚类结果，则各是刚性聚类结果，则各CxCx需满足如下条件：需满足如下条件：1 1）2 2）对于）对于有有3 3）聚类分析的形式描述聚类分析的形式描述66数据数据准备准备属性选择属性选择属性提取属性提取聚聚类类结果结果评估评估聚类过程聚类过程为聚类分析准备为聚类分析准备数据，包括属性数据，包括属性值标准化值标准化从最初的属性中从最初的属性中选择最有效的属选择最有效

46、的属性性通过对所选择的属性通过对所选择的属性进行转换形成新的更进行转换形成新的更有代表性的属性有代表性的属性度量对象间的相似性程度量对象间的相似性程度，执行聚类或分组度，执行聚类或分组聚类分析的三要素是相似性测度、聚类准则和聚类算法聚类分析的三要素是相似性测度、聚类准则和聚类算法67聚类分析中的数据类型聚类分析中的数据类型聚类分析中常用的数据类型有：数据矩阵、相异度矩阵聚类分析中常用的数据类型有：数据矩阵、相异度矩阵1）数据矩阵：对象在多维空间中通常表示为点（向量），其每）数据矩阵：对象在多维空间中通常表示为点（向量），其每一维表示为不同属性，这些属性描述出对象一维表示为不同属性，这些属性描

47、述出对象数据矩阵每行代表一个对象，每列代表对象的一个属性数据矩阵每行代表一个对象，每列代表对象的一个属性2）相异度矩阵：存储）相异度矩阵：存储n个对象两两之间的近似性，个对象两两之间的近似性，d(i,j)是对象是对象i和对象和对象j之间相异性的量化表示之间相异性的量化表示68聚类分析三要素聚类分析三要素相似性测度、聚类准则和聚类算法相似性测度、聚类准则和聚类算法相似性测度：相似性测度：衡量同簇对象的类似性和不同簇对象的差异性衡量同簇对象的类似性和不同簇对象的差异性聚类准则：聚类准则：评价聚类结果的好坏评价聚类结果的好坏聚类算法：聚类算法：用于找出使准则函数取极值的最好聚类结果用于找出使准则

48、函数取极值的最好聚类结果实际上，确定了相似性测度和聚类准则后，聚类就变成了使准实际上，确定了相似性测度和聚类准则后，聚类就变成了使准则函数取极值的优化问题了则函数取极值的优化问题了没有任何一种聚类算法可以普遍适用于揭示各种多维数据集所没有任何一种聚类算法可以普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构呈现出来的多种多样的结构因此聚类算法有多种，不同的聚类算法使用不同的相似性度量因此聚类算法有多种，不同的聚类算法使用不同的相似性度量和准则和准则69对象之间的相似性根据描述对象的属性值评估，可以使用距离、对象之间的相似性根据描述对象的属性值评估，可以使用距离、密度、连通性或概念度量

49、密度、连通性或概念度量距离相似性度量：距离相似性度量：距离越近越相似，不同簇中任意两个对象间距离越近越相似，不同簇中任意两个对象间的距离都大于簇内任意两个对象之间的距离的距离都大于簇内任意两个对象之间的距离密度相似性度量：密度相似性度量：密度（单位区域内的对象数密度（单位区域内的对象数）越相近，相）越相近，相似性越高，簇是对象的稠密区域，被低密度的区域环绕似性越高，簇是对象的稠密区域，被低密度的区域环绕连通性相似性度量：连通性相似性度量：使用图的连通性度量相似性，簇定义为图使用图的连通性度量相似性，簇定义为图的连通分支，即互相连通但不与组外对象连通的对象组的连通分支，即互相连通但不与组外

50、对象连通的对象组概念相似性度量：概念相似性度量：共性（比如共享最近邻）越多越相似共性（比如共享最近邻）越多越相似，簇，簇定义为有某种共同性质的对象的集合定义为有某种共同性质的对象的集合相似性测度相似性测度70主要的聚类算法大致可以分为：划分式聚类算法、基于密度的聚主要的聚类算法大致可以分为：划分式聚类算法、基于密度的聚类算法、层次聚类算法、基于网格的聚类算法和基于模型的聚类类算法、层次聚类算法、基于网格的聚类算法和基于模型的聚类算法算法聚类算法分类聚类算法分类划分式聚类算法（划分式聚类算法（partitioning partitioning methodmethod）预先指定聚类数目或聚

51、类中心，通过反复迭代运算，逐步优化准预先指定聚类数目或聚类中心，通过反复迭代运算，逐步优化准则函数的值，当准则函数收敛时，得到最终聚类结果则函数的值，当准则函数收敛时，得到最终聚类结果k k均值算法、均值算法、k k中心点算法及它们的变种中心点算法及它们的变种基于密度的聚类算法（基于密度的聚类算法（density-based method）通过数据密度来发现簇通过数据密度来发现簇DBSCANDBSCAN、OPTICSOPTICS、DENCLUEDENCLUE71聚类算法分类聚类算法分类基于网格的聚类算法（基于网格的聚类算法（gridgridbased methodbased method）将对

52、象空间量化为有限数目的单元，形成网格结构，所有的聚类将对象空间量化为有限数目的单元，形成网格结构，所有的聚类操作都在网格上进行，从而获得较快的处理速度操作都在网格上进行，从而获得较快的处理速度STINGSTING、WaveClusterWaveCluster层次聚类算法（层次聚类算法（hierarchical hierarchical methodmethod）将数据对象组织成一棵聚类树，使用数据的联接规则，透过一种将数据对象组织成一棵聚类树，使用数据的联接规则，透过一种架构方式，反复将数据进行分裂或聚合，以形成一个层次序列的架构方式，反复将数据进行分裂或聚合，以形成一个层次序列的聚类问题解聚

53、类问题解 BIRCHBIRCH、ROCKROCK和和Chameleon Chameleon 等等72聚类算法分类聚类算法分类基于模型的聚类算法（基于模型的聚类算法（model-based methodmodel-based method）基于基于“数据根据潜在的混合概率分布生成数据根据潜在的混合概率分布生成”假设，为每个簇假定假设，为每个簇假定一个模型，并寻找数据对给定模型的最佳拟合一个模型，并寻找数据对给定模型的最佳拟合这类算法通过构建反映数据点空间分布的密度函数来定位簇，能这类算法通过构建反映数据点空间分布的密度函数来定位簇，能考虑考虑“噪声噪声”数据和离群点的影响，鲁棒性较好数据和离群点

54、的影响，鲁棒性较好 EM EM 、COBWEB COBWEB 、SOMSOM 73均值聚类算法均值聚类算法均值聚类算法假定所有数据对象可分为均值聚类算法假定所有数据对象可分为k k个簇，每个簇的中心用个簇，每个簇的中心用均值表示均值表示对象间的相似性用距离度量对象间的相似性用距离度量聚类的准则是误差平方和准则聚类的准则是误差平方和准则核心思想：核心思想：首先选定首先选定k个初始聚类中心，根据最小距离原则将每个个初始聚类中心，根据最小距离原则将每个数据对象分配到某一簇中数据对象分配到某一簇中然后不断迭代计算各个簇的聚类中心并依新的聚类中心调整聚类然后不断迭代计算各个簇的聚类中心并依新的聚类中心

55、调整聚类情况，直至收敛（情况，直至收敛（J 值不再变化）值不再变化）74均值聚类算法均值聚类算法误差平方和准则误差平方和准则若若N Nx x是第是第C Cx x个簇中的对象数目，个簇中的对象数目，m mx x是这些对象的均值，是这些对象的均值， J J是所有是所有簇的簇中各个对象与均值间的误差平方和之和簇的簇中各个对象与均值间的误差平方和之和对于不同的聚类，对于不同的聚类，J J的值不同的值不同使使J J 值极小的聚类是误差平方和准则下的最优结果值极小的聚类是误差平方和准则下的最优结果度量了用度量了用k个聚类中个聚类中心心m1,mk代表代表k个个簇簇C1,Ck时所产生时所产生的总的误差平方和的

56、总的误差平方和75均值聚类算法均值聚类算法算法描述算法描述输入：数据对象集合输入：数据对象集合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|为当前簇中的对象数目为当前簇中的对象数目7

57、6均值聚类算法均值聚类算法算法简单，计算复杂度是算法简单，计算复杂度是O(nkt)，其中，其中n是对象的总数，是对象的总数，k是簇的是簇的个数，个数，t是迭代次数，是迭代次数，通常，通常，kn且且t e=0.832 ，继续计算，继续计算55步迭代后的结果：步迭代后的结果：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)T(0.777,0.960)T100模糊模糊c-均值聚类算

58、法均值聚类算法xi相对于相对于的隶属度的隶属度 x1x2x3x4x50.9610.9810.9460.0380.0400.0390.0190.0540.9620.960聚类过程终止聚类过程终止 101分析技术及模型分析技术及模型分类分析分类分析102分类与预测是普遍存在的问题，具有广泛的应用领域分类与预测是普遍存在的问题，具有广泛的应用领域分类的任务是通过分析由已知类别数据对象组成的训练数据集，分类的任务是通过分析由已知类别数据对象组成的训练数据集，建立描述并区分数据对象类别的分类函数或分类模型（分类器）建立描述并区分数据对象类别的分类函数或分类模型（分类器）分类的目的是利用分类模型判定未知

59、类别数据对象的所属类别，分类的目的是利用分类模型判定未知类别数据对象的所属类别，判定的目标是数据对象在类别属性（离散）上的取值判定的目标是数据对象在类别属性（离散）上的取值预测也要通过分析训练数据集建立预测模型，然后利用模型预测预测也要通过分析训练数据集建立预测模型，然后利用模型预测数据对象，预测的目标是判定数据对象在预测属性（连续）上的数据对象，预测的目标是判定数据对象在预测属性（连续）上的取值或取值区间取值或取值区间分类与聚类有显著区别：分类中，训练样本的类别是已知的（有分类与聚类有显著区别：分类中，训练样本的类别是已知的（有指导），而聚类中所有数据都没有类别标签（无指导）指导），而聚类中

60、所有数据都没有类别标签（无指导）主要介绍分类过程、分类模型评估方法、常用分类算法主要介绍分类过程、分类模型评估方法、常用分类算法分类分析分类分析103分类过程分为两个阶段：学习阶段与分类阶段分类过程分为两个阶段：学习阶段与分类阶段分类过程分类过程训练样本输入训练样本输入分类模型分类模型测试样本输入测试样本输入新数据新数据分类算法分类算法学习过程学习过程分类过程分类过程每个训练样本由每个训练样本由m+1个属性描述，个属性描述，X=（A1, , Am, C）Ai对应描述属性，可以是连续属性或离散属性对应描述属性，可以是连续属性或离散属性C表示类别属性，有表示类别属性，有k个不同的类别，个不同的类别

61、，C=（c1, c2, , ck）从描述属性矢量从描述属性矢量（XC）到类别）到类别属性属性C的映射函的映射函数数H:（XC）C分类规则、判定分类规则、判定树等形式树等形式X=（A1, , Am）确定确定CX=（A1, , Am,C）提供提供X=（A1, , Am)，确定确定C，比较，比较C、C用于寻找映射函数用于寻找映射函数H104分类分类算法有多种：决策树分类算法、神经网络分类算法、贝叶斯算法有多种：决策树分类算法、神经网络分类算法、贝叶斯分类算法、分类算法、k-最近邻分类算法、遗传分类算法、粗糙集分类算法、最近邻分类算法、遗传分类算法、粗糙集分类算法、模糊集分类算法等模糊集分类算法等分

62、类算法可以根据下列标准进行比较和评估：分类算法可以根据下列标准进行比较和评估：1）准确率：分类模型正确地预测新样本所属类别的能力）准确率：分类模型正确地预测新样本所属类别的能力2）速度：建立和使用分类模型的计算开销）速度：建立和使用分类模型的计算开销3）强壮性：给定噪声数据或具有空缺值的数据，分类模型正确）强壮性：给定噪声数据或具有空缺值的数据，分类模型正确地预测的能力地预测的能力4）可伸缩性：给定大量数据，有效地建立分类模型的能力）可伸缩性：给定大量数据，有效地建立分类模型的能力5）可解释性：分类模型提供的理解和洞察的层次）可解释性：分类模型提供的理解和洞察的层次分类算法评估标准分类算法评估

63、标准105利用测试数据集评估分类模型的准确率利用测试数据集评估分类模型的准确率分类模型正确分类的分类模型正确分类的测试样本数占总测试样本数的百分比测试样本数占总测试样本数的百分比准确率可以接受，对新样本进行分类；否则，重新建立分类模型准确率可以接受，对新样本进行分类；否则，重新建立分类模型评估分类模型准确率的方法有评估分类模型准确率的方法有保持、保持、k-折交叉确认折交叉确认保持方法保持方法将已知类别的样本随机地划分为训练数据集与测试数据将已知类别的样本随机地划分为训练数据集与测试数据集两个集合，一般，训练数据集占集两个集合，一般，训练数据集占2/3，测试数据集占，测试数据集占1/3k-折交叉

64、确认方法折交叉确认方法将已知类别的样本随机地划分为大小大致相等将已知类别的样本随机地划分为大小大致相等的的k个子集个子集S1, , Sk，并进行，并进行k次训练与测试次训练与测试第第i次，次，Si作为测试数据集，其余子集的并集作为训练数据集作为测试数据集，其余子集的并集作为训练数据集k次训练得到次训练得到k个分类模型，测试时，将出现次数最多的分类结果个分类模型，测试时，将出现次数最多的分类结果作为最终的分类结果作为最终的分类结果分类模型评估方法分类模型评估方法106适宜多峰分布的分类问题适宜多峰分布的分类问题决策树以树结构的形式表示，类似流程图决策树以树结构的形式表示，类似流程图一棵决策树由

65、一个根节点，一组内部节点和一组叶节点组成一棵决策树由一个根节点，一组内部节点和一组叶节点组成决策树分类算法决策树分类算法每个分枝表示一个测试输出每个分枝表示一个测试输出每个叶节点表示一个类，不同的叶节点可表示相同的类每个叶节点表示一个类，不同的叶节点可表示相同的类根节点和内部节点表示根节点和内部节点表示在一个属性上的测试在一个属性上的测试107建立了决策树之后，可以对从根节点到叶节点的每条路径创建一条建立了决策树之后，可以对从根节点到叶节点的每条路径创建一条IF-THEN分类规则，易于理解分类规则，易于理解沿着路径，每个内部节点沿着路径，每个内部节点-分枝对形成规则前件（分枝对形成规则前件（

66、IF部分）的一个部分）的一个合取项，叶节点形成规则后件（合取项，叶节点形成规则后件（THEN部分）部分）决策树分类算法决策树分类算法IF 年龄年龄=41 AND 信誉信誉=中中 THEN 购买计算机购买计算机=是是IF 年龄年龄=30 AND 学生学生=否否 THEN 购买计算机购买计算机=否否-否否新顾客：教师，年龄新顾客：教师，年龄45岁，收入较低但信誉很好岁，收入较低但信誉很好该顾客是否会购买计算机？该顾客是否会购买计算机？108决策树分类算法的关键是建立决策树决策树分类算法的关键是建立决策树建立一棵决策树，需要解决的问题主要有：建立一棵决策树，需要解决的问题主要有：1）如何选择测试属性

67、？）如何选择测试属性？测试属性的选择顺序影响决策树的结构甚至决策树的准确率测试属性的选择顺序影响决策树的结构甚至决策树的准确率一般使用信息增益度量来选择测试属性一般使用信息增益度量来选择测试属性2）如何停止划分样本？）如何停止划分样本？从根节点测试属性开始，每个内部节点测试属性都把样本空间划从根节点测试属性开始，每个内部节点测试属性都把样本空间划分为若干个（子）区域分为若干个（子）区域一般当某个（子）区域的样本同类时，就停止划分样本，有时也一般当某个（子）区域的样本同类时，就停止划分样本，有时也通过阈值提前停止划分样本通过阈值提前停止划分样本决策树分类算法决策树分类算法109使用递归方式完成使

68、用递归方式完成基本思想：基本思想：首先，将整个训练数据集首先，将整个训练数据集S、所有描述属性、所有描述属性A1, A2, , Am作为分析对象作为分析对象如果如果S中的样本属于同一类别，则将中的样本属于同一类别，则将S作为叶节点并用其中样本的作为叶节点并用其中样本的类别标识，决策树建立完成类别标识，决策树建立完成否则在否则在S上计算各个属性的信息增益上计算各个属性的信息增益G(C, Ak)，选择信息增益最，选择信息增益最大的属性大的属性Ai作为根节点的测试属性作为根节点的测试属性如果如果Ai的取值个数为的取值个数为v（取值记为（取值记为a1, a2, , av），则），则Ai将将S划划分为分

69、为v个子集个子集S1, S2, , Sv，同时根节点产生同时根节点产生v个分枝与之对应个分枝与之对应分别在训练数据子集分别在训练数据子集S1, S2, , Sv、剩余描述属性、剩余描述属性A1, , Ai1, Ai+1, , Am上采用相同方法递归地建立决策树子树上采用相同方法递归地建立决策树子树决策树分类算法决策树分类算法建立决策树建立决策树Sv：S中中Ai=av的样本集合的样本集合110递归过程中，某节点对应的训练数据（子）集由整个训练数据集递归过程中，某节点对应的训练数据（子）集由整个训练数据集S中满足从根节点到该节点路径上所有属性测试的训练样本组成中满足从根节点到该节点路径上所有属性测

70、试的训练样本组成某节点对应的描述属性是去除从根节点到该节点路径上所有已选某节点对应的描述属性是去除从根节点到该节点路径上所有已选描述属性后的剩余描述属性描述属性后的剩余描述属性同一层内部节点选择的测试属性可能相同也可能不同同一层内部节点选择的测试属性可能相同也可能不同决策树分类算法决策树分类算法建立决策树建立决策树111递归结束条件：递归结束条件：1）某节点对应的训练数据（子）集中的样本属于同一类别）某节点对应的训练数据（子）集中的样本属于同一类别2）某节点对应的训练数据（子）集为空）某节点对应的训练数据（子）集为空此时，该节点作为叶节点并用父节点中占多数的样本类别标识此时，该节点作为叶节点并

71、用父节点中占多数的样本类别标识3）某节点没有对应的（剩余）描述属性）某节点没有对应的（剩余）描述属性此时，该节点作为叶节点并用该节点中占多数的样本类别标识此时，该节点作为叶节点并用该节点中占多数的样本类别标识决策树分类算法决策树分类算法建立决策树建立决策树112输入：训练数据集输入：训练数据集S，描述属性集合，描述属性集合A输出：决策树输出：决策树步骤：步骤：（1）创建对应）创建对应S的节点的节点Node（2）if S中的样本属于同一类别中的样本属于同一类别c then 以以c标识标识Node并将并将Node作为叶节点返回作为叶节点返回（3）if A为空为空 then 以以S中占多数的样本类别

72、中占多数的样本类别c标识标识Node并将并将Node作为叶节点返回作为叶节点返回（4）从）从A中选择对中选择对S而言信息增益最大的描述属性而言信息增益最大的描述属性Ai作为作为Node的测试属性的测试属性决策树分类算法决策树分类算法算法描述算法描述113（5）for Ai的每个可能取值的每个可能取值aj（1jv）（5.1）产生）产生S的一个子集的一个子集Sj （5.2）if Sj为空为空 then 创建对应创建对应Sj的节点的节点Nj，以，以S中占多数的样本类别中占多数的样本类别c标识标识Nj，并将，并将Nj作作为叶节点形成为叶节点形成Node的一个分枝的一个分枝（5.3）else 由（由

73、（Sj, A-Ai）创建子树形成）创建子树形成Node的一个分枝的一个分枝决策树分类算法决策树分类算法算法描述算法描述114决策树分类算法决策树分类算法信息增益信息增益类别属性类别属性C的无条件熵：的无条件熵：给定描述属性给定描述属性Ak，类，类别属性别属性C的条件熵：的条件熵：n：样本总数：样本总数 u：C的可能取值个数，的可能取值个数，即类别数即类别数si：属于类别：属于类别ci的记录集合的记录集合 |si|：属于类别：属于类别ci的记录总数的记录总数v：Ak的可能取值个数的可能取值个数 sj：Ak=aj的记录集合的记录集合 |sj|：Ak=aj的记的记录数目录数目Sij：Ak=aj且属于

74、类别且属于类别ci的记录集合的记录集合 |sij|：Ak=aj且属于类别且属于类别ci的记录的记录数目数目给定描述属性给定描述属性Ak，类别，类别C的信息增益：的信息增益：G(C, Ak)=E(C)-E(C, Ak) G(C, Ak)反映反映Ak减少减少C不确定性的程度，不确定性的程度，G(C, Ak)越大，越大，Ak对对减少减少C不确定性的贡献越大不确定性的贡献越大 115决策树分类算法决策树分类算法信息增益信息增益蔬菜数据表如表所示，蔬菜数据表如表所示，“颜色颜色”、“形形状状”是描述属性，是描述属性，“蔬菜蔬菜”是类别属性，是类别属性，分别求给定分别求给定“颜色颜色”、“形状形状”属

75、性时，属性时，“蔬菜蔬菜”属性的信息增益属性的信息增益颜色色形状形状蔬菜蔬菜红圆蕃茄蕃茄紫紫长茄子茄子绿长黄瓜黄瓜G(蔬菜，颜色蔬菜，颜色)1.5850-0=1.5850G(蔬菜，形状蔬菜，形状)1.5850-0.6667=0.9183 G(蔬菜，颜色蔬菜，颜色)G(蔬菜，形状蔬菜，形状) 不同描述属性减少类别属性不确不同描述属性减少类别属性不确定性的程度不同定性的程度不同116决策树分类算法决策树分类算法信息增益信息增益尽量选择对减少类别属性不确定性贡献最大的描述属性尽量选择对减少类别属性不确定性贡献最大的描述属性分类模型包含尽可能少的描述属性从而使模型简单分类模型包含尽可能少的描述属性从

76、而使模型简单 G(蔬菜，颜色蔬菜，颜色)G(蔬菜，形状蔬菜，形状) 测试属性的选择顺序影响决策树的结构甚至决策树的准确率测试属性的选择顺序影响决策树的结构甚至决策树的准确率决策树分类算法要求描述属性是离散属性，连续属性需要离散化决策树分类算法要求描述属性是离散属性，连续属性需要离散化 117决策树分类算法决策树分类算法噪声处理噪声处理如果训练数据集含有噪声，决策树的某些分枝反映的是噪声而不如果训练数据集含有噪声，决策树的某些分枝反映的是噪声而不是总体，应该剪去这些不可靠的分枝，提高决策树的分类准确率是总体，应该剪去这些不可靠的分枝，提高决策树的分类准确率有两种剪枝策略：有两种剪枝策略：先剪枝

77、策略：先剪枝策略：在建立决策树的过程中，通过某度量标准判断每在建立决策树的过程中，通过某度量标准判断每个内部节点是否需要进一步划分，如果进一步划分将导致建立不个内部节点是否需要进一步划分，如果进一步划分将导致建立不可靠的分枝，则停止划分，从而达到剪枝。此时，该内部节点变可靠的分枝，则停止划分，从而达到剪枝。此时，该内部节点变成叶节点并用其中占多数的记录类别标识成叶节点并用其中占多数的记录类别标识后剪枝策略：后剪枝策略：首先，建立完整的决策树；然后，通过某度量标首先，建立完整的决策树；然后，通过某度量标准判断哪些内部节点分枝是不可靠的，将这些内部节点变成叶节准判断哪些内部节点分枝是不可靠的，将

78、这些内部节点变成叶节点并用其中占多数的记录类别标识，从而达到剪枝点并用其中占多数的记录类别标识，从而达到剪枝118前馈神经网络分类算法前馈神经网络分类算法神经网络可以模仿人脑，通过学习训练数据集，生成分类模型神经网络可以模仿人脑，通过学习训练数据集，生成分类模型适用于数据没有任何明显模式的情况适用于数据没有任何明显模式的情况样本属性可以是连续的，也可以是离散的样本属性可以是连续的，也可以是离散的神经网络由许多单元（神经元）以适当的方式连接起来构成神经网络由许多单元（神经元）以适当的方式连接起来构成单元模仿人脑的神经元，单元之间的连接相当于人脑中神经元的单元模仿人脑的神经元，单元之间的连接相当

79、于人脑中神经元的连接连接单元之间的连接方式有多种，从而形成了多种神经网络单元之间的连接方式有多种，从而形成了多种神经网络在分类中，应用较多的是前馈神经网络在分类中，应用较多的是前馈神经网络主要介绍前馈神经网络结构、网络学习及网络分类方法主要介绍前馈神经网络结构、网络学习及网络分类方法 119前馈神经网络分类算法前馈神经网络分类算法网络结构网络结构前馈神经网络是分层网络模型，具有一个输入层和一个输出层，前馈神经网络是分层网络模型，具有一个输入层和一个输出层，输入层和输出层之间有一个或多个隐藏层输入层和输出层之间有一个或多个隐藏层每个层具有若干单元，前一层单元与后一层单元之间通过有向加每个层具有若

80、干单元，前一层单元与后一层单元之间通过有向加权边相连权边相连 ai：输入层：输入层第第i个单元个单元的输入的输入 Ok：输出：输出层第层第k个单个单元的输出元的输出 wij：隐藏层第：隐藏层第j个单元与输入个单元与输入层第层第i个单元之间的连接权个单元之间的连接权wjk：输出层第：输出层第k个单元与隐个单元与隐藏层第藏层第j个单元之间的连接权个单元之间的连接权 120前馈神经网络分类算法前馈神经网络分类算法网络结构网络结构输入层单元的数目与训练样本的描述属性数目对应，通常一个连输入层单元的数目与训练样本的描述属性数目对应，通常一个连续属性对应一个输入层单元，一个续属性对应一个输入层单元，一个p

81、值离散属性对应值离散属性对应p个输入层单个输入层单元元输出层单元的数目与训练样本的类别数目对应（两类时，可以只输出层单元的数目与训练样本的类别数目对应（两类时，可以只有一个输出单元）有一个输出单元）隐层的层数及隐层的单元数尚无理论指导，一般通过实验选取隐层的层数及隐层的单元数尚无理论指导，一般通过实验选取输入层，各单元的输出可以等于输入，也可以按一定比例调节，输入层，各单元的输出可以等于输入，也可以按一定比例调节，使其值落在使其值落在1和和+1之间之间其他层，每个单元的输入都是前一层各单元输出的加权和，输出其他层，每个单元的输入都是前一层各单元输出的加权和，输出是输入的某种函数，称为激活函数是

82、输入的某种函数，称为激活函数121前馈神经网络分类算法前馈神经网络分类算法网络结构网络结构隐藏层、输出层任意单元隐藏层、输出层任意单元j的输入：的输入：输出输出： Oj= f (netj) 如果如果f采用采用S型激活函数：型激活函数：对于隐藏层、输出层对于隐藏层、输出层任意单元任意单元j，由输入计，由输入计算输出的过程算输出的过程：单元单元i的输出的输出单元单元j与前一层单元与前一层单元i之间的连接权之间的连接权改变单元改变单元j活性的活性的偏置，偏置，1，1上上取值取值则则122前馈神经网络分类算法前馈神经网络分类算法网络学习网络学习不同的单元的偏置及单元之间的连接权会获得不同的输出

83、不同的单元的偏置及单元之间的连接权会获得不同的输出学习过程就是调整各单元的偏置及单元之间的连接权值，使每个学习过程就是调整各单元的偏置及单元之间的连接权值，使每个训练样本在输出层单元上获得的输出与其期望输出间的误差最小训练样本在输出层单元上获得的输出与其期望输出间的误差最小学习使用误差后向传播算法学习使用误差后向传播算法基本思想：基本思想：首先赋予每条有向加权边初始权值、每个隐藏层与输首先赋予每条有向加权边初始权值、每个隐藏层与输出层单元初始偏置出层单元初始偏置然后迭代地处理每个训练样本，输入它的描述属性值，计算实际然后迭代地处理每个训练样本，输入它的描述属性值，计算实际输出，获取实际输出与期

84、望输出间的误差输出，获取实际输出与期望输出间的误差将误差从输出层经每个隐藏层到输入层将误差从输出层经每个隐藏层到输入层“后向传播后向传播”，根据误差，根据误差修改权值和单元的偏置，使实际输出与期望输出之间的误差最小修改权值和单元的偏置，使实际输出与期望输出之间的误差最小123前馈神经网络分类算法前馈神经网络分类算法网络学习网络学习样本实际输出与期望输出的误差样本实际输出与期望输出的误差Error： c：输出层的单元数目：输出层的单元数目 Tk：输出层单元：输出层单元k的期望输出的期望输出 Ok：单元：单元k的实际输的实际输出出输出层单元输出层单元k与前一层单元与前一层单元j之间的权值之间的权

85、值wjk的修改量的修改量wjk、单元、单元k的偏置修改量的偏置修改量为使为使Error最小，采用使最小，采用使Error沿梯度方向下降的方式沿梯度方向下降的方式单元单元j的输出的输出Error对单元对单元k的输的输入入netk的负偏导数的负偏导数学习率，学习率，l 0, 1，避免陷入局部最优解，避免陷入局部最优解单元单元k的输出的输出124前馈神经网络分类算法前馈神经网络分类算法网络学习网络学习隐藏层单元隐藏层单元j与前一层单元与前一层单元i之间的权值之间的权值wij的修改量的修改量wij、单元、单元j的的偏置偏置j的修改量的修改量j ：单元单元i的输出的输出单元单元j的输出的输出与单元与单元

86、j相连的后一相连的后一层单元层单元k的误差的误差权值、偏置的修改权值、偏置的修改：权值、偏置的更新有两种策略：权值、偏置的更新有两种策略：1）实例更新：处理一个训练样本更新一次，常采用）实例更新：处理一个训练样本更新一次，常采用2）周期更新：处理所有训练样本后再一次更新）周期更新：处理所有训练样本后再一次更新处理所有训练样本一次，称为一个周期处理所有训练样本一次，称为一个周期125前馈神经网络分类算法前馈神经网络分类算法网络学习网络学习结束条件：结束条件：1）误差）误差Error小于设定阈值小于设定阈值，此时认为网络收敛，结束迭代，此时认为网络收敛，结束迭代2）前一周期所有的权值变化都很

87、小，小于某个设定阈值）前一周期所有的权值变化都很小，小于某个设定阈值3）前一周期预测的准确率很大，大于某个设定阈值）前一周期预测的准确率很大，大于某个设定阈值3）周期数大于某个设定阈值）周期数大于某个设定阈值在实际应用中，训练样本很多，学习需要很多次迭代才能完成在实际应用中，训练样本很多，学习需要很多次迭代才能完成迭代次数与网络结构、初始权值与偏置、学习率的值有很大关系迭代次数与网络结构、初始权值与偏置、学习率的值有很大关系这些参数都是凭经验选取这些参数都是凭经验选取算法特点算法特点126前馈神经网络分类算法前馈神经网络分类算法网络学习网络学习设训练样本设训练样本s的描述属性值与类别属性值分

88、别为的描述属性值与类别属性值分别为1, 0, 1与与1，前馈神经网络前馈神经网络NT如图所示，如图所示，NT中每条有向加权边的权值、每个中每条有向加权边的权值、每个隐藏层与输出层单元的偏置如表所示，学习率为隐藏层与输出层单元的偏置如表所示，学习率为0.9。写出输入。写出输入s训练训练NT的过程的过程 x x1 1x x2 2x x3 3w w1414w w1515w w2424w w2525w w3434w w3535w w4646w w56564 45 56 61 10 01 10.0.2 20.30.30.0.4 40.0.1 10.50.50.0.2 20.30.30.20.20.40.

89、40.0.2 20.0.1 1127前馈神经网络分类算法前馈神经网络分类算法网络学习网络学习x x1 1x x2 2x x3 3w w1414w w1515w w2424w w2525w w3434w w3535w w4646w w56564 45 56 61 10 01 10.0.2 20.30.30.0.4 40.0.1 10.50.50.0.2 20.30.30.20.20.40.40.0.2 20.0.1 1单元元j j输入入netnetj j输出出O Oj j4 40.2*1+0.4*0+(0.2*1+0.4*0+(0.5)*1+(0.5)*1+(0.4)=0.4)=0.70.71/

90、(1+e1/(1+e( (0.7)0.7)=0.332)=0.3325 5( (0.3)*1+0.1*0+(0.2)*1+0.2=0.10.3)*1+0.1*0+(0.2)*1+0.2=0.11/(1+e1/(1+e0.10.1)=0.525)=0.5256 6( (0.3)*0.332+(0.3)*0.332+(0.2)*0.525+0.1=0.2)*0.525+0.1=0.1050.1051/(1+e1/(1+e( (0.105)0.105)=0.474)=0.474单元元j jErrErrj j6 60.474*(10.474)*(10.474)=0.13115 50.525*(10.5

91、25*(10.525)*(0.1311*(0.525)*(0.1311*(0.2)=0.2)=0.00650.00654 40.332*(10.332)*(0.1311*(0.3)=0.0087128前馈神经网络分类算法前馈神经网络分类算法网络学习网络学习x x1 1x x2 2x x3 3w w1414w w1515w w2424w w2525w w3434w w3535w w4646w w56564 45 56 61 10 01 10.20.20.30.30.40.40.10.10.50.50.20.20.30.30.20.20.40.40.20.20.10.1w w34340.5+0.9

92、*(0.5+0.9*(0.0087)*1=0.0087)*1=0.5080.508w w35350.2+0.9*(0.2+0.9*(0.0065)*1=0.0065)*1=0.1940.1946 60.1+0.9*0.1311=0.2180.1+0.9*0.1311=0.2185 50.2+0.9*(0.2+0.9*(0.0065)=0.1940.0065)=0.1944 40.4+0.9*(0.4+0.9*(0.0087)=0.0087)=0.4080.408w w46460.3+0.9*0.1311*0.332=0.3+0.9*0.1311*0.332=0.2610.261w w56560

93、.2+0.9*0.1311*0.525=0.2+0.9*0.1311*0.525=0.1380.138w w14140.2+0.9*(0.2+0.9*(0.0087)*1=0.1920.0087)*1=0.192w w15150.3+0.9*(0.3+0.9*(0.0065)*1=0.0065)*1=0.3060.306w w24240.4+0.9*(0.4+0.9*(0.0087)*0=0.40.0087)*0=0.4w w25250.1+0.9*(0.1+0.9*(0.0065)*0=0.10.0065)*0=0.1单元元j jErrErrj j6 60.13115 50.00650.00

94、654 40.0087单元元j j输出出O Oj j4 40.3320.3325 50.5250.5256 60.4740.474129前馈神经网络分类算法前馈神经网络分类算法算法描述算法描述输入：训练数据集输入：训练数据集S，前馈神经网络，前馈神经网络NT，学习率，学习率l输出：经过训练的前馈神经网络输出：经过训练的前馈神经网络NT步骤：步骤：（1）在区间）在区间-1, 1上随机初始化上随机初始化NT中每条有向加权边的权值、每个隐藏层中每条有向加权边的权值、每个隐藏层与输出层单元的偏置与输出层单元的偏置（2）while 结束条件不满足结束条件不满足（2.1）for S中每个训练样本中每个训

95、练样本s （）（）for 隐藏层与输出层中每个单元隐藏层与输出层中每个单元j （）（）for 输出层中每个单元输出层中每个单元k Errk=Ok(1- Ok)( Tk - Ok)从第一个隐藏层开从第一个隐藏层开始向前传播输入始向前传播输入 130前馈神经网络分类算法前馈神经网络分类算法算法描述算法描述（）（）for 隐藏层中每个单元隐藏层中每个单元j （）（）for NT中每条有向加权边的权值中每条有向加权边的权值wij wij= wij+lErrjOi （）（）for 隐藏层与输出层中每个单元的偏置隐藏层与输出层中每个单元的偏置j j=j+lErrj从最后一个隐藏层从最后一个隐藏层开始向后

96、传播误差开始向后传播误差学习过程由正向传播和反向传播组成学习过程由正向传播和反向传播组成正向传播过程：正向传播过程：训练样本从输入层，经隐藏层，传向输出层，每一层单元的训练样本从输入层，经隐藏层，传向输出层，每一层单元的状态只影响下一层单元的状态状态只影响下一层单元的状态反向传播过程：反向传播过程：输出层不能得到期望输出，则将误差沿原来的连接通路传回，输出层不能得到期望输出，则将误差沿原来的连接通路传回，通过修改权值和偏置，使误差最小通过修改权值和偏置，使误差最小 131前馈神经网络分类算法前馈神经网络分类算法网络分类网络分类学习结束后，神经网络得到一组固定的权值及偏置学习结束后，神经网络得

97、到一组固定的权值及偏置新样本到来后，将其描述属性值送入输入层各单元，从输入层到新样本到来后，将其描述属性值送入输入层各单元，从输入层到输出层正向传播，计算输出层各单元的值输出层正向传播，计算输出层各单元的值O1, O2, , On令令r=max(O1, O2, , On)，则第，则第r个输出层单元所代表的类别个输出层单元所代表的类别就是该样本所属的类别就是该样本所属的类别新样本新样本X=（x1, x2, x3）送入输入）送入输入层层计算出计算出O61，则表示，则表示X应属于应属于A类类O60，则表示，则表示X应属于应属于B类类若若O60.5，则拒绝分类，则拒绝分类132贝叶斯分类算法贝叶斯分类

98、算法贝叶斯分类：应用贝叶斯公式求解分类问题贝叶斯分类：应用贝叶斯公式求解分类问题贝叶斯公式：贝叶斯公式：贝叶斯分类公式：贝叶斯分类公式：m个描述属性个描述属性A1=a1, , Am=am的联合概率的联合概率类别属性类别属性C=c的概的概率（先验概率率（先验概率）已知已知C=c时，时，A1=a1, , Am=am的条件概的条件概率（类条件概率率（类条件概率）已知已知A1=a1, , Am=am时，时，C=c的条件概的条件概率（类别率（类别c的后验概率）的后验概率）贝叶斯分类的分类就是给定新样本的描述属性值贝叶斯分类的分类就是给定新样本的描述属性值a1,am，计算，计算各个类别的后验概率，

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

102、是优是是3030中中否否中中否否3030低低是是中中是是4141中中是是中中是是3030中中是是优是是31403140中中否否优是是31403140高高是是中中是是4141中中否否优否否136贝叶斯分类算法贝叶斯分类算法输入：训练数据集输入：训练数据集S、新样本新样本r( ar1, , arm )输出：新样本的类别输出：新样本的类别cr步骤：步骤：（1）for S中每个训练样本中每个训练样本s(as1, , asm, cs) （1.1）增加类别）增加类别cs的计数的计数cs.count （1.2）for 每个描述属性值每个描述属性值asi 增加类别增加类别cs中描述属性值中描述属性值asi的计

103、数的计数cs.asi.count（2）for 每个类别每个类别c （2.1）算法描述算法描述137贝叶斯分类算法贝叶斯分类算法（2.2）for 每个描述属性每个描述属性Ai （）（）for 每个描述属性值每个描述属性值ai （2.3）for 每个每个a1, , am（3）算法描述算法描述朴素贝叶斯分类假设各个描述属性在给定类别属性时条件独立朴素贝叶斯分类假设各个描述属性在给定类别属性时条件独立这个条件独立假设在现实应用中可能不成立这个条件独立假设在现实应用中可能不成立树增强朴素贝叶斯分类削弱了这个限制树增强朴素贝叶斯分类削弱了这个限制138 树增强朴素贝叶斯分类算法树增强朴素贝叶斯分类算法

104、树增强朴素贝叶斯分类假设树增强朴素贝叶斯分类假设C和和A1, ., Am有直接依赖关系，有直接依赖关系，A1, ., Am之间也有依赖关系（允许各个描述属性之间形成树之间也有依赖关系（允许各个描述属性之间形成树型结构），削弱了各个描述属性在给定类别属性时条件独立假设，型结构），削弱了各个描述属性在给定类别属性时条件独立假设，增强了朴素贝叶斯分类增强了朴素贝叶斯分类节点节点C和节点和节点A1, ., Am有有向边有有向边相连，相连，C是是A1, ., Am的父节点的父节点A1, ., Am之间有有向边相连并形之间有有向边相连并形成树，根节点的父节点只有成树，根节点的父节点只有C，其它，其它节点的

105、父节点除了节点的父节点除了C之外还有一个节之外还有一个节点点新样本新样本a1, , a5的类别：的类别：139 树增强朴素贝叶斯分类算法树增强朴素贝叶斯分类算法树增强朴素贝叶斯分类树型结构构造方法的基本思想：树增强朴素贝叶斯分类树型结构构造方法的基本思想：首先，计算在给定类别属性首先，计算在给定类别属性C时，描述属性时，描述属性A1, ., Am之间的之间的依赖强度，共得到依赖强度，共得到个依赖强度个依赖强度然后，根据从强到弱的原则选择然后，根据从强到弱的原则选择m1个依赖强度，添加相应描述个依赖强度，添加相应描述属性之间的无向边，并使各个描述属性之间形成无向树属性之间的无向边，并使各个描

106、述属性之间形成无向树最后，选择根节点，为无向边添加方向形成有向树最后，选择根节点，为无向边添加方向形成有向树在给定类别属性在给定类别属性C时，描述属性时，描述属性Ai和和 Aj之间的依赖强度可以利用之间的依赖强度可以利用条件互信息描述：条件互信息描述：140 树增强朴素贝叶斯分类算法树增强朴素贝叶斯分类算法输入：训练数据集输入：训练数据集S输出：树增强朴素贝叶斯分类的贝叶斯网结构输出：树增强朴素贝叶斯分类的贝叶斯网结构TAN步骤：步骤：（1）扫描）扫描S，计算在给定类别属性，计算在给定类别属性C时，描述属性时，描述属性A1, ., Am之间的条件之间的条件互信息互信息（2）构造一个无向完全图，

107、以描述属性为节点，以条件互信息为边的权重）构造一个无向完全图，以描述属性为节点，以条件互信息为边的权重（3）构造上述无向完全图的最大生成树）构造上述无向完全图的最大生成树（4）在上述最大生成树中选择一个节点为根节点，为无向边添加方向形成有）在上述最大生成树中选择一个节点为根节点，为无向边添加方向形成有向树向树（5）在上述有向树中添加节点）在上述有向树中添加节点C和和C到各个到各个A1, ., Am的有向边，得到的有向边，得到TAN算法描述算法描述141树增强朴素贝叶斯分类算法树增强朴素贝叶斯分类算法I(年龄；收入年龄；收入|购买计算机购买计算机)0.4196I(年龄；学生年龄；学生 | 购买计

108、算机购买计算机)0.2228I(年龄；信誉年龄；信誉 | 购买计算机购买计算机)0.3118I(收入；学生收入；学生 | 购买计算机购买计算机)0.4196I(收入；信誉收入；信誉 | 购买计算机购买计算机)0.1689I(学生；信誉学生；信誉 | 购买计算机购买计算机)0.0611年年龄收入收入学生学生信誉信誉购买计算算机机3030高高否否中中否否3030高高否否优否否31403140高高否否中中是是4141中中否否中中是是4141低低是是中中是是4141低低是是优否否31403140低低是是优是是3030中中否否中中否否3030低低是是中中是是4141中中是是中中是是3030中中是是优是是

110、1p(优优 | 否否，3140)0 新样本类别为新样本类别为是是143分析技术及模型分析技术及模型异常检测异常检测144异常在数据集中所占的比例很小，异常对象被称为离群点、例异常在数据集中所占的比例很小，异常对象被称为离群点、例外、野点等外、野点等许多数据挖掘算法试图使异常的影响最小化，或者排除它们许多数据挖掘算法试图使异常的影响最小化，或者排除它们一个人的噪声可能是另一个人的信号，异常检测可能会揭示隐一个人的噪声可能是另一个人的信号，异常检测可能会揭示隐藏在数据中的重要信息藏在数据中的重要信息目标是发现与大部分其他对象不同的对象，它是发现新知识、目标是发现与大部分其他对象不同的对象，它是发现

111、新知识、新类别的一条有效途径新类别的一条有效途径对于欺诈检测、入侵检测、伪造信用卡检测、机械设备故障诊对于欺诈检测、入侵检测、伪造信用卡检测、机械设备故障诊断、自然灾害预测、医疗分析等许多任务非常有用断、自然灾害预测、医疗分析等许多任务非常有用主要介绍异常概念、异常的成因、常用异常检测算法主要介绍异常概念、异常的成因、常用异常检测算法异常检测异常检测145异常有多种定义异常有多种定义异常是显然严重偏离了样本集合中其它观测值的数据点异常是显然严重偏离了样本集合中其它观测值的数据点异常是远离其它观测点的一个观测点，由于离得太远以至于产异常是远离其它观测点的一个观测点，由于离得太远以至于产生怀疑，

112、认为它是由一个不同的机制产生的生怀疑，认为它是由一个不同的机制产生的异常是集合中严重偏离大部分数据所呈现趋势的小部分数据点异常是集合中严重偏离大部分数据所呈现趋势的小部分数据点异常检测可以分为两个子问题：异常检测可以分为两个子问题：1 1）定义在给定的数据集合中什么样的数据认为是不一致的）定义在给定的数据集合中什么样的数据认为是不一致的 2 2）找到一个有效的方法挖掘这样的异常）找到一个有效的方法挖掘这样的异常异常概念异常概念146数据集中可能有多种原因产生异常数据集中可能有多种原因产生异常常见的异常成因有：常见的异常成因有：1 1）数据来源于不同的类：数据来源于不同的类：一个数据对象可能不

113、同于其他数据对一个数据对象可能不同于其他数据对象（即异常），因为它属于一个不同的类型或类象（即异常），因为它属于一个不同的类型或类异常检测的关注点异常检测的关注点2 2）自然变异：自然变异：属于同类的数据对象由于自然变异出现了异常属于同类的数据对象由于自然变异出现了异常3 3）数据测量或收集误差数据测量或收集误差不提供有趣的信息，只会降低数据和数据分析的质量，应该删不提供有趣的信息，只会降低数据和数据分析的质量，应该删除，数据预处理的关注点除，数据预处理的关注点异常的成因异常的成因147主要的异常检测算法大致可以分为：基于统计分布的异常检测、基主要的异常检测算法大致可以分为：基于统计分布的异

114、常检测、基于偏差的异常检测、基于距离的异常检测和基于密度的异常检测于偏差的异常检测、基于距离的异常检测和基于密度的异常检测异常检测算法分类异常检测算法分类基于统计分布的异常检测（基于统计分布的异常检测（Distribution-based outlier detection）对给定的数据集假设一个分布或概率模型（如，正态分布或泊松对给定的数据集假设一个分布或概率模型（如，正态分布或泊松分布），然后根据模型采用不和谐检验识别异常分布），然后根据模型采用不和谐检验识别异常异常是那些同模型不能完美拟合的对象异常是那些同模型不能完美拟合的对象绝大多数检验是针对单个属性的，不能在多维空间中发现异常绝大

115、多数检验是针对单个属性的，不能在多维空间中发现异常需要数据集参数知识，但参数知识很难获得需要数据集参数知识，但参数知识很难获得基于偏差的异常检测（基于偏差的异常检测（Deviation-based outlier detection）通过检查一组对象的主要特征来识别异常通过检查一组对象的主要特征来识别异常148异常检测算法分类异常检测算法分类基于距离的异常检测（基于距离的异常检测（Distance-based outlier detection）基于距离的异常是没有基于距离的异常是没有“足够多足够多”近邻的对象，也就是那些远近邻的对象，也就是那些远离大部分其他对象的对象离大部分其他对象的对

116、象检测的关键在于搜索每个对象的近邻，避免了与观测分布拟合检测的关键在于搜索每个对象的近邻，避免了与观测分布拟合到某个标准分布和选择不和谐检验相关联的过多计算到某个标准分布和选择不和谐检验相关联的过多计算基于密度的异常检测（基于密度的异常检测（Density-based outlier detection）这种方法不将异常看作一种二元性质，而是使用局部异常因子这种方法不将异常看作一种二元性质，而是使用局部异常因子（Local outlier factor，LOF）来评估一个对象是异常的程度）来评估一个对象是异常的程度该程度依赖于对象相对于其邻域的孤立情况该程度依赖于对象相对于其邻域的孤立情况

117、149基于距离的异常检测基于距离的异常检测定义：定义：如果数据集合如果数据集合D中的对象至少有中的对象至少有pct部分与对象部分与对象o的距离大于的距离大于dmin，则称对象则称对象o是以是以pct和和dmin为参数的基于距离的异常，记为为参数的基于距离的异常，记为DB(pct,dmin)dmin是邻域半径，是邻域半径，pct是一个异常的是一个异常的dmin邻域外的最少对象比例邻域外的最少对象比例基于索引的算法、嵌套基于索引的算法、嵌套-循环算法、基于单元的算法循环算法、基于单元的算法采用多维索引结构搜索每个采用多维索引结构搜索每个对象的近邻，如果某个对象对象的近邻，如果某个对象在给定半径范围

118、内的近邻数在给定半径范围内的近邻数大于阈值，该对象不是异常大于阈值，该对象不是异常避免索引结构的构建，通过内存避免索引结构的构建，通过内存缓冲空间和数据集合的划分及选缓冲空间和数据集合的划分及选择数据块装入缓冲区域的顺序，择数据块装入缓冲区域的顺序，有效改善有效改善I/O效率效率将数据空间划分为有限数目的将数据空间划分为有限数目的单元，逐个单元地判定异常单元，逐个单元地判定异常150嵌套嵌套-循环（循环（Nested-Loop，NL）算）算法法假设缓冲区的大小为数据集大小的假设缓冲区的大小为数据集大小的B%将整个缓冲区分成两个阵列，分别称为第一阵列和第二阵列将整个缓冲区分成两个阵列，分别称为第

119、一阵列和第二阵列将数据集中的数据划分成块，每块大小为将数据集中的数据划分成块，每块大小为0.5B%对象以块为单位读入阵列中，然后直接计算数据对象间的距离对象以块为单位读入阵列中，然后直接计算数据对象间的距离第一阵列中的每个对象都有一个计数器，用于记录对象第一阵列中的每个对象都有一个计数器，用于记录对象dmin邻域邻域内的对象数目内的对象数目某个计数器的值一旦大于一个异常的某个计数器的值一旦大于一个异常的dmin邻域内最多对象数目邻域内最多对象数目M，该计数器就停止计数，该计数器就停止计数，M=N(1-pct)，N是数据集中对象数是数据集中对象数算法思想算法思想151嵌套嵌套-循环（循环（Ne

120、sted-Loop，NL）算）算法法设设NL算法用算法用50%的缓冲区。数据集被分成的缓冲区。数据集被分成A、B、C、D 四个逻辑四个逻辑块。每个阵列和块能容纳块。每个阵列和块能容纳1/4数据集的对象数数据集的对象数第一阵列第一阵列第二阵列第二阵列数据块填充阵列的顺序为：数据块填充阵列的顺序为：序号序号第一阵列第一阵列第二阵列第二阵列1 A B、C、D 读读4块块A、B、C、D 2 D A、B、C 读读2块块B、C3 C D、A、B 读读2个块个块A、B4 B C、A、D 读读2个块个块A、D循环循环4次，总共读了次，总共读了10个块个块遍历数据库的次数总计为遍历数据库的次数总计为10/

121、4=2.5次次 152嵌套嵌套-循环（循环（Nested-Loop，NL）算）算法法输入：数据对象集合输入：数据对象集合D，邻域半径，邻域半径dmin，一个异常的一个异常的dmin邻域内最多对象数目邻域内最多对象数目M输出：输出：D中的异常对象中的异常对象步骤：步骤：（1）用数据集）用数据集D中的一个数据块填充第一阵列中的一个数据块填充第一阵列（2）for 第一阵列中每个数据对象第一阵列中每个数据对象ti，do （2.1）counti=0 （2.2）for第一阵列中的每个对象第一阵列中的每个对象tj （）（）if dist(ti,tj) dmin，then counti+1 （）（）if co

122、untiM，then 标记标记ti不是一个异常，处理下一个不是一个异常，处理下一个ti 算法描述算法描述考察第一阵列考察第一阵列中对象间的距中对象间的距离离153嵌套嵌套-循环（循环（Nested-Loop，NL）算）算法法（3）当第一阵列中的对象都比较完后，）当第一阵列中的对象都比较完后，do （3.1）用另一个数据块填充第二阵列，将那些从未填充过第一阵列的数据块）用另一个数据块填充第二阵列，将那些从未填充过第一阵列的数据块记录下来记录下来（3.2）for第一阵列中未标记的每个数据对象第一阵列中未标记的每个数据对象ti （）（）for第二阵列中的每个对象第二阵列中的每个对象tj if di

123、st(ti,tj) dmin，then counti+1 if countiM，则标记，则标记ti不是一个异常，处理下一个不是一个异常，处理下一个ti（4）输出第一阵列中每一个未被标记的对象）输出第一阵列中每一个未被标记的对象ti，表示它是一个异常表示它是一个异常（5）if第二阵列曾经充当过第一阵列，第二阵列曾经充当过第一阵列，then stop else交换第一阵列和第二阵列的角色，转（交换第一阵列和第二阵列的角色，转（2）算法描述算法描述考察第一和第考察第一和第二阵列中对象二阵列中对象间的距离间的距离保证每个对象保证每个对象都能被作为中都能被作为中心心154嵌套嵌套-循环（循环（Neste

124、d-Loop，NL）算）算法法NL算法的复杂性为算法的复杂性为O(kN2)与不划分缓冲区和数据集的蛮力方法相比，与不划分缓冲区和数据集的蛮力方法相比，NL算法较优越，因为算法较优越，因为它将它将I/O最小化最小化NL算法不受数据集大小和维数的限制算法不受数据集大小和维数的限制但是当数据集较大时，但是当数据集较大时，NL算法需要多次遍历数据库算法需要多次遍历数据库如果数据集被划分为如果数据集被划分为n= 200/B 个块（个块（B是缓冲区的百分比）是缓冲区的百分比）那么（那么（i）算法）算法NL需读的块的总数为需读的块的总数为n+(n-2)(n-1) （ii）遍历数据库的次数）遍历数据库的次数

125、n-2 算法特点算法特点155基于单元（基于单元（Cell-Based）算法）算法基于单元的算法将空间区域划分为矩形单元，通过使用单元基于单元的算法将空间区域划分为矩形单元，通过使用单元-单元单元的处理来代替的处理来代替NL算法中对象算法中对象-对象的处理，避免了复杂性中的对象的处理，避免了复杂性中的N2项，从而提高效率项，从而提高效率先考虑维数先考虑维数k=2的数据集的数据集将空间区域划分为边长将空间区域划分为边长的矩形单元的矩形单元Cx,y表示位于表示位于x行、行、y列的单元列的单元每个对象按照其属性值大小映射到相应单元中每个对象按照其属性值大小映射到相应单元中相关概念相关概念156基于

126、单元（基于单元（Cell-Based）算法）算法单元单元Cx,y的的1层邻域层邻域L1L1(Cx,y)= Cu,v|u=x 1, v=y 1, Cu,v Cx,y 相关概念相关概念性质性质1：同一单元中两个对象间的：同一单元中两个对象间的最远距离为最远距离为dmin/2，即，即性质性质2：若：若Cu,v是是Cx,y的的L1邻域，那么邻域，那么Cu,v中的对象中的对象ti与与Cx,y中对象中对象tj间间的最大距离为的最大距离为dmin，即，即157基于单元（基于单元（Cell-Based）算法）算法单元单元Cx,y的的2层邻域层邻域L2L2(Cx,y)= Cu,v|u=x 3, v=y 3, C

127、u,v L1(Cx,y), Cu,v Cx,y 每个非边界单元有每个非边界单元有72-32=40个个L2邻域邻域相关概念相关概念性质性质3：假如：假如Cu,v Cx,y，Cu,v既不是既不是Cx,y的的L1邻域，也不是邻域，也不是Cx,y的的L2邻域，邻域，那么那么Cu,v中的对象中的对象ti与与Cx,y中对象中对象tj间间的距离一定大于的距离一定大于dmin，即，即 158基于单元（基于单元（Cell-Based）算法）算法相关概念相关概念性质性质4：若若Cx,y中的对象数中的对象数M，那么，那么Cx,y中的对象都不异常中的对象都不异常若若Cx,y中的对象数中的对象数+L1(Cx,y)

128、中的中的对象数对象数M，那么，那么Cx,y中的对象都不中的对象都不异常异常若若Cx,y中的对象数中的对象数+ L1(Cx,y)中的中的对象数对象数+ L2(Cx,y)中的对象数中的对象数 M，那么那么Cx,y中的每一个对象都是异常中的每一个对象都是异常 159基于单元（基于单元（Cell-Based）算法）算法FM算法算法基于单元的算法分为两个：基于单元的算法分为两个：FindAlloutsM（FM）和）和FindAlloutsD（FD）FM适用于检测存储于主存的数据集中的异常适用于检测存储于主存的数据集中的异常FM算法使用性质算法使用性质1性质性质4来检测异常和非异常来检测异常和非异常这种

129、检测是以单元这种检测是以单元-单元为基础，而不是以对象单元为基础，而不是以对象-对象为基础，从对象为基础，从而可以将大量不可能是异常的对象排除而可以将大量不可能是异常的对象排除只有不满足性质只有不满足性质4的单元内的对象才进行对象的单元内的对象才进行对象-对象的处理对象的处理 160基于单元（基于单元（Cell-Based）算法）算法FM算法描述算法描述输入：数据对象集合输入：数据对象集合D，邻域半径，邻域半径dmin，一个异常的一个异常的dmin邻域内最多对象数目邻域内最多对象数目M输出：输出：D中的异常对象中的异常对象步骤：步骤：（1）for q=1 to m countq=0 /m是单元

130、数，单元的对象计数器清零是单元数，单元的对象计数器清零（2）将）将 D中每个对象中每个对象p映射到合适的单元映射到合适的单元Cq中，存储中，存储p，countq+1（3）检测各个单元，）检测各个单元，if countq M，then 将将Cq标记为红色标记为红色 /Cq中的所有对象都不是异常中的所有对象都不是异常（4）对每一个红色单元）对每一个红色单元Cr，将它的每一个，将它的每一个L1邻域标记为粉红色，提供未曾被邻域标记为粉红色，提供未曾被标记为红色的邻域标记为红色的邻域（5）for 每一个非空的白色单元每一个非空的白色单元Cw（未被标记颜色）（未被标记颜色）161基于单元（基于单元（Ce

131、ll-Based）算法）算法FM算法描述算法描述（5.1）（5.2）if countw2 M，then 标记标记Cw为粉红色为粉红色（5.3）else （）（）（）（）if countw3 M，then 输出输出Cw中的所有对象中的所有对象 /都是异常都是异常（）（）else for Cw中的每一个对象中的每一个对象p countp= countw2 for L2(Cw)中的每一个对象中的每一个对象 if then countp+1 if countp M then 输出输出p /p是异常是异常 Cw中的对象中的对象p必须必须与与Cw的的L2邻域中的邻域中的对象对象p 比较，决比较，决定有

132、多少个定有多少个p 在在p的的dmin邻域内邻域内 162基于单元（基于单元（Cell-Based）算法）算法FM算法描述算法描述设设M=10在在k=2维的情况下，维的情况下，FM算法的时间复杂性为算法的时间复杂性为O(m+N)m是单元数，是单元数，N是对象数是对象数在实际中，有很多单元都是红色和粉红色，白色单元较少在实际中，有很多单元都是红色和粉红色，白色单元较少因此，对象因此，对象-对象的比较也较少，算法所需的时间也会减少对象的比较也较少，算法所需的时间也会减少163基于单元（基于单元（Cell-Based）算法）算法FD算法算法FD算法适用于适用于处理大型、磁盘数据集算法适用于适用于处理

133、大型、磁盘数据集对于大型磁盘数据集，无法将整个数据集存储于主存中，因此，对于大型磁盘数据集，无法将整个数据集存储于主存中，因此，将数据集分页，各页依次读入主存处理将数据集分页，各页依次读入主存处理提高效率的关键在于使读页的次数或遍历数据库的次数最小化提高效率的关键在于使读页的次数或遍历数据库的次数最小化在基于单元的算法中，有两个阶段需要读页：在基于单元的算法中，有两个阶段需要读页：1）初始映射阶段：在算法）初始映射阶段：在算法FM的（的（2），每个对象被映射到合适的），每个对象被映射到合适的单元中单元中遍历数据库一次遍历数据库一次2）对象成对比较阶段：在算法）对象成对比较阶段：在算法FM的步

134、，每一对对象（的步，每一对对象（p，p ）的比较可能要求读一页的比较可能要求读一页 p、p不一定相邻不一定相邻 I/O次数多次数多164基于单元（基于单元（Cell-Based）算法）算法FD算法算法FD算法的方法：挑选对象子集保存在主存中，将磁盘上的数据页算法的方法：挑选对象子集保存在主存中，将磁盘上的数据页分类分类各类数据页按一定顺序读入，从而使读页次数最小化各类数据页按一定顺序读入，从而使读页次数最小化被挑选的子集由映射到白色单元中的对象（白色对象）构成被挑选的子集由映射到白色单元中的对象（白色对象）构成白色对象需要进行对象白色对象需要进行对象-对象的计算对象的计算白色单元中的对象数目被

135、限定在白色单元中的对象数目被限定在M以内以内165基于单元（基于单元（Cell-Based）算法）算法FD算法算法在在FD算法中，所有页分成算法中，所有页分成A、B、C三种类型：三种类型：1）A类页：包含白色对象的页类页：包含白色对象的页2）B类页：不包含白色对象，但是包含映射到白色单元的类页：不包含白色对象，但是包含映射到白色单元的L2邻域邻域的非白色单元中的对象的页的非白色单元中的对象的页3）C类页：所有其它页类页：所有其它页FD算法先读算法先读A类页，并将所类页，并将所有白色对象存储在主存有白色对象存储在主存然后读然后读B类页，若必要再读类页，若必要再读A类页，类页，C类页不需要再读类页

136、不需要再读 166基于单元（基于单元（Cell-Based）算法）算法FD算法算法设第设第i页中的对象页中的对象p映射到白色单元映射到白色单元Cw中，为了判断对象中，为了判断对象p是否异是否异常，需要计算对象常，需要计算对象p与下列三种对象间的距离：与下列三种对象间的距离：1）被映射到）被映射到Cw的的L2邻域的白色单元中的白色对象邻域的白色单元中的白色对象；2）被映射到）被映射到Cw的的L2邻域的非白色单元中的非白色对象邻域的非白色单元中的非白色对象，位于第位于第j页，且页，且j i3）被映射到）被映射到Cw的的L2邻域的非白色单元中的非白色对象邻域的非白色单元中的非白色对象，位于

137、第位于第j页，但页，但jM then 将将Cq标记为红色标记为红色可以获取一个给定可以获取一个给定单元的对象，也可单元的对象，也可以知道一个特定页以知道一个特定页中的对象被映射到中的对象被映射到了哪些单元中了哪些单元中 168基于单元（基于单元（Cell-Based）算法）算法FD算法描述算法描述（4）对每一个红色单元）对每一个红色单元Cr，将它的每一个，将它的每一个L1邻域标记为粉红色，提供未曾被邻域标记为粉红色，提供未曾被标记为红色的邻域标记为红色的邻域（5）for 每一个非空的白色单元每一个非空的白色单元Cw （5.1）（5.2）if countw2 M，then 标记标记Cw为粉红色

138、为粉红色（5.3）else （）（）（）（）if countw3 M，then 将将Cw标记为黄色标记为黄色 /Cw中的所有对象都是异常中的所有对象都是异常（）（）else sumw=countw2169基于单元（基于单元（Cell-Based）算法）算法FD算法描述算法描述（6）for 每一个至少包含一个白色对象或黄色对象的页每一个至少包含一个白色对象或黄色对象的页i （6.1）读第）读第i页页（6.2）for 每一个有对象在页每一个有对象在页i中的白色单元或黄色单元中的白色单元或黄色单元Cq （）（）for 页页i中被映射到中被映射到Cq中的每一个对象中的每一个对象p 将将p存在存

139、在Cq中中 kcountp=sumq（7）for 每一个非空白色单元每一个非空白色单元Cw中的每一个对象中的每一个对象p （7.1）for 每一个白色单元或黄色单元每一个白色单元或黄色单元CL，CL L2(Cw) （）（）for CL中的每一个对象中的每一个对象 if ，then kcountp+1 if kcountpM，then 标记标记p不是异常，处理下一个不是异常，处理下一个pA类页类页将将dmin-邻域计数器初始邻域计数器初始化为化为Cw L1(Cw)中的对中的对象数象数 170基于单元（基于单元（Cell-Based）算法）算法FD算法描述算法描述（8）标记黄色单元中的所有对象是

140、异常，输出这些异常）标记黄色单元中的所有对象是异常，输出这些异常（9）for 至少包含一个（至少包含一个（i）既不是白色对象，也不是黄色对象，（）既不是白色对象，也不是黄色对象，（ii）映射）映射到某白色单元到某白色单元Cw的的L2邻域内的对象的页邻域内的对象的页i （9.1）读页）读页i （9.2）for 每一个既不是白色单元，也不是黄色单元，并且有对象在页每一个既不是白色单元，也不是黄色单元，并且有对象在页i中的单元中的单元Cq，Cq L2(Cw) （）（）for 页页i中映射到中映射到Cq中的每一个对象中的每一个对象 for 每一个非空白色单元每一个非空白色单元Cw，Cw L2(Cq)

141、 for Cw中的每个对象中的每个对象p if ，then kcountp+1 if kcountpM，then 标记标记p不是异常不是异常读读B类页或重读类页或重读A类页类页仅用新从磁盘仅用新从磁盘读入的对象检读入的对象检测每个白色单测每个白色单元中的对象元中的对象 171基于单元（基于单元（Cell-Based）算法）算法FD算法描述算法描述（10）for 每一个非空白色单元中的每个对象每一个非空白色单元中的每个对象p （10.1）If p未被标记为非异常，未被标记为非异常，then 标记标记p是异常，输出是异常，输出pFD算法的复杂性也与算法的复杂性也与N呈线性关系呈线性关系FD算法遍

142、历数据库的次数不超过算法遍历数据库的次数不超过3次次对于特别大型的数据集，对于特别大型的数据集，FD算法遍历数据库的次数比算法遍历数据库的次数比NL算法少算法少当维数不超过当维数不超过4维时，维时，FD算法比算法比NL算法优越算法优越当当k=5之后，之后，NL算法开始显现出优势算法开始显现出优势FD算法特点算法特点172基于密度的异常检测基于密度的异常检测基于距离的异常检测依赖于给定数据集基于距离的异常检测依赖于给定数据集D的的“全局全局”分布分布通常将这种依据通常将这种依据“全局全局”分布检测出的异常称为分布检测出的异常称为全局异常全局异常对于均匀分布的数据集，基于距离的异常检测能较好地识别

143、异常，对于均匀分布的数据集，基于距离的异常检测能较好地识别异常，但是当数据的分布密度相差很大时，基于距离的异常检测会遇到但是当数据的分布密度相差很大时，基于距离的异常检测会遇到困难困难使用基于距离的异常检测算法，无法找到使用基于距离的异常检测算法，无法找到合适的距离合适的距离dmin使得算法只检测出使得算法只检测出o1和和o2dmin大于大于o2和和C2之间的最小距离，只能发现之间的最小距离，只能发现o1，o2不能被检测出来不能被检测出来dmin小于小于o2和和C2之间的最小距离，可以将之间的最小距离，可以将o2检测出来，检测出来，C1中的所有对象也被当作异常中的所有对象也被当作异常173基

144、于密度的异常检测基于密度的异常检测基于密度的异常检测使用局部异常因子（基于密度的异常检测使用局部异常因子（Local outlier factor，LOF）来评估一个对象是异常的程度）来评估一个对象是异常的程度克服了基于距离的异常检测方法在数据的分布密度相差很大时遇克服了基于距离的异常检测方法在数据的分布密度相差很大时遇到的困难到的困难对象对象p的的k距离距离kdistance(p)p到它的到它的k最近邻的最大距离，定义为最近邻的最大距离，定义为p与对象与对象o D之间的距离之间的距离d(p，o)，满足：，满足：（1）D中至少存在中至少存在k个对象到个对象到p的距离小于或等于的距离小于或等于p

145、到到o的距离的距离（2）D中最多有中最多有k-1个对象到个对象到p的距离比的距离比p到到o的距离小的距离小相关概念相关概念174基于密度的异常检测基于密度的异常检测对象对象p的的k距离邻域距离邻域Nk_distance(p)(p)包含所有与包含所有与p的距离不超过的距离不超过k_distance(p)的对象，即：的对象，即： Nkdistance(p)(p)=q Dp|d(p，q) kdistance(p) 相关概念相关概念 op1p2reach-distk(p2,o)reach-distk(p1,o)=k-distance(o)若对象若对象p远离远离o，可达距离是它们间的实际距离，可达距离是

146、它们间的实际距离若若p在在o的的k距离邻域内，可达距离是距离邻域内，可达距离是o的的k距离距离对象对象p关于对象关于对象o的可达距离的可达距离reach_distk(p，o) reach_distk(p，o)=maxk_distance(o)，d(p，o)175基于密度的异常检测基于密度的异常检测对象对象p的局部可达密度的局部可达密度对象对象p与它的与它的MinPts-邻域的平均可达距离的倒数邻域的平均可达距离的倒数相关概念相关概念对象对象p的局部异常因子的局部异常因子对象对象p和它的最近邻的局部可达密度的比率的平均值和它的最近邻的局部可达密度的比率的平均值 p的局部可达密度越小，最近邻的局

147、部可达密度越大，的局部可达密度越小，最近邻的局部可达密度越大，LOFMinPts (p)越高越高LOF表征了表征了p的异常程度：如果的异常程度：如果p不是不是局部异常，则局部异常，则LOF接近于接近于1p是局部异常的程度越大，是局部异常的程度越大，LOF越高越高 p的邻域中最少的邻域中最少的对象个数的对象个数176基于密度的异常检测算法基于密度的异常检测算法算法描述算法描述基于密度的异常检测算法通过计算基于密度的异常检测算法通过计算LOF(p)来判断对象来判断对象p是否是局是否是局部异常部异常核心是对于指定的近邻个数核心是对于指定的近邻个数k，基于对象的最近邻计算对象的基于对象的最近邻计算对象

148、的LOF输入：数据对象集合输入：数据对象集合D，近邻个数，近邻个数MinPts，异常对象数目异常对象数目k输出：输出：k个异常个异常步骤：步骤：（1）for D中每个数据对象中每个数据对象p （1.1）确定）确定p的的MinPts距离邻域距离邻域NMinpts_distance(p)(p) （1.2）使用）使用p的最近邻（即的最近邻（即NMinPts_distance(p)(p)中的对象），中的对象），计算计算p的局部可达密度的局部可达密度lrdMinPts(p)177基于密度的异常检测算法基于密度的异常检测算法算法描述算法描述（1.3）计算）计算NMinPts_distance(p)(p)

149、中每个对象中每个对象o的局部可达密度的局部可达密度lrdMinPts(o) （1.4）计算）计算p的局部异常因子的局部异常因子LOFMinPts(p)（2）输出）输出D中中LOF值最大的值最大的k个对象个对象算法特点算法特点提出了局部异常的概念：如果一个对象相对于它的局部邻域，特提出了局部异常的概念：如果一个对象相对于它的局部邻域，特别是关于邻域密度，它是远离的，则这个对象是局部异常别是关于邻域密度，它是远离的，则这个对象是局部异常算法的时间复杂度为算法的时间复杂度为O(n2)（n：D中对象个数）中对象个数）算法给出了对象异常程度的定量度量，并且在数据具有不同密度算法给出了对象异常程度的定量

150、度量，并且在数据具有不同密度的区域也能够很好地识别局部异常的区域也能够很好地识别局部异常 178分析技术及模型分析技术及模型贝叶斯网贝叶斯网179贝叶斯网贝叶斯网（Bayesian Network，BN）贝叶斯网是一种帮助人们将概率、统计应用于复杂领域、进行贝叶斯网是一种帮助人们将概率、统计应用于复杂领域、进行不确定性推理和数据分析的有效工具不确定性推理和数据分析的有效工具它起源于它起源于20世纪世纪80年代中期对人工智能中的不确定性问题的研年代中期对人工智能中的不确定性问题的研究，已经成为人工智能的一个重要领域究，已经成为人工智能的一个重要领域近年来在国际上的影响不断扩大，对众多其它领域也产

151、生了重近年来在国际上的影响不断扩大，对众多其它领域也产生了重要影响要影响贝叶斯网的主要应用是贝叶斯网的主要应用是进行概率推理进行概率推理，即计算一些事件发生的，即计算一些事件发生的概率概率主要介绍贝叶斯网的基本概念、贝叶斯网推理、贝叶斯网学习主要介绍贝叶斯网的基本概念、贝叶斯网推理、贝叶斯网学习180图论的基本概念图论的基本概念介绍贝叶斯网的定义之前，先引入几个图论中的基本概念介绍贝叶斯网的定义之前，先引入几个图论中的基本概念父节点、子节点：父节点、子节点：在一个有向图中，如果从节点在一个有向图中，如果从节点X到节点到节点Y有一有一条边，那么条边，那么X为为Y的父节点，的父节点，Y为为X的子

152、节点的子节点邻居节点：邻居节点：一个节点的所有父节点和子节点称为它的邻居节点一个节点的所有父节点和子节点称为它的邻居节点根节点：根节点：没有父节点的节点没有父节点的节点叶节点：叶节点：没有子节点的节点没有子节点的节点ABEMJ祖先节点：祖先节点：一个节点的祖先节点包括其一个节点的祖先节点包括其父节点及父节点的祖先节点父节点及父节点的祖先节点根节点无根节点无祖先节点祖先节点 B、E、A都是都是J的祖先节点的祖先节点181图论的基本概念图论的基本概念后代节点：后代节点：一个节点的后代节点包括其子节点及子节点的后代一个节点的后代节点包括其子节点及子节点的后代节点节点叶节点无后代节点叶节点无后代节

153、点非后代节点：非后代节点：一个节点的非后代节点包括所有不是其后代节点一个节点的非后代节点包括所有不是其后代节点的节点的节点有向环：有向环：在一个有向图中，若某节点是它自己的祖先节点，则在一个有向图中，若某节点是它自己的祖先节点，则该图包含一个有向环该图包含一个有向环有向无环图：有向无环图：不包含有向环的有向图不包含有向环的有向图182贝叶斯网定义贝叶斯网定义贝叶斯网是一个有限无环图贝叶斯网是一个有限无环图其中节点代表随机变量，节点间的边代表变量之间的直接依赖其中节点代表随机变量，节点间的边代表变量之间的直接依赖关系关系每个节点都附有一个概率分布，根节点每个节点都附有一个概率分布，根节点X所附的

154、是它的边缘分所附的是它的边缘分布布P(X)，非根节点，非根节点X所附的是条件概率分布所附的是条件概率分布P(X/Par(X)结构图蕴含了条件独立假结构图蕴含了条件独立假设，即给定一个变量的父设，即给定一个变量的父节点集，该变量独立于它节点集，该变量独立于它的非子孙节点的非子孙节点节点之间的连接关系代表节点之间的连接关系代表了贝叶斯网络的条件语义了贝叶斯网络的条件语义183贝叶斯网定义贝叶斯网定义贝叶斯网也可以从定性和定量两个层面来理解贝叶斯网也可以从定性和定量两个层面来理解在定性层面在定性层面，它用一个有向无环图描述了节点之间的依赖和独，它用一个有向无环图描述了节点之间的依赖和独立关系立关系在

155、定量层面在定量层面，它用条件概率分布刻画了变量对其父节点的依赖，它用条件概率分布刻画了变量对其父节点的依赖关系关系在语义上，贝叶斯网是联合概率分布的分解的一种表示：如果在语义上，贝叶斯网是联合概率分布的分解的一种表示：如果网络中的变量为网络中的变量为，那么，那么的联合概率分的联合概率分布为各变量所附的概率分布的乘积，即布为各变量所附的概率分布的乘积，即其中当其中当时，时，就是边缘分布就是边缘分布184贝叶斯网定义贝叶斯网定义贝叶斯网的联合概率分布分解降低了概率模型的复杂度，使知贝叶斯网的联合概率分布分解降低了概率模型的复杂度，使知识的获取与表达得以简化，为概率计算提供了很大方便识的获取

156、与表达得以简化，为概率计算提供了很大方便贝叶斯网贝叶斯网的优点：的优点：是严格的数学语言，适合于是严格的数学语言，适合于计算机处理计算机处理直观易懂，方便人们讨论交直观易懂，方便人们讨论交流和建立模型流和建立模型提供了人类推理过程的一个提供了人类推理过程的一个模型模型因为依赖和独立关系是人们日常推理的基本工具，而且人类知识的基本结因为依赖和独立关系是人们日常推理的基本工具，而且人类知识的基本结构也可以用依赖图来表达构也可以用依赖图来表达185贝叶斯网与概率推理贝叶斯网与概率推理推理（推理（inference）是通过计算回答查询（）是通过计算回答查询（query）的过程）的过程使用概率方法进

157、行不确定性推理就是：使用概率方法进行不确定性推理就是：（1）把问题用一组随机变量）把问题用一组随机变量来刻画来刻画（2）把关于问题的知识表示为一个联合概率分布）把关于问题的知识表示为一个联合概率分布（3）已知某些变量的取值，计算另外一些变量的后验概率分布）已知某些变量的取值，计算另外一些变量的后验概率分布已知变量通常称为证据变量，记为已知变量通常称为证据变量，记为（），它们的取值记），它们的取值记为为；需要计算其后验概率分布的变量称为查询变量，记为；需要计算其后验概率分布的变量称为查询变量，记为，（）概率推理的根本任务就是给定证据变量集合后，计算查询变量集的概率推理的根本任务就是给

158、定证据变量集合后，计算查询变量集的概率分布，即：概率分布，即：186贝叶斯网与概率推理贝叶斯网与概率推理由于由于和和可以根据联合概率可以根据联合概率P(X)的边缘化而求的边缘化而求得，因此要在一些随机变量之间进行概率推理，理论上只需要得，因此要在一些随机变量之间进行概率推理，理论上只需要一个联合概率分布一个联合概率分布P(X)即可即可但是，直接使用联合概率分布但是，直接使用联合概率分布P(X)进行不确定性推理的困难很进行不确定性推理的困难很明显，即它的复杂度极高明显，即它的复杂度极高一般地，一般地，n个二值变量的联合概率分布包含个独立参数个二值变量的联合概率分布包含个独立参数2n-1所以，

159、联合分布的复杂度相对于变量的个数成指数增长。当变所以，联合分布的复杂度相对于变量的个数成指数增长。当变量很多时，联合概率的获取、存储和运算都变得十分困难，推量很多时，联合概率的获取、存储和运算都变得十分困难，推理变得不可行理变得不可行187贝叶斯网与概率推理贝叶斯网与概率推理贝叶斯网的提出就是要解决推理的复杂性问题，构造贝叶斯网贝叶斯网的提出就是要解决推理的复杂性问题，构造贝叶斯网的主要目的就是进行概率推理的主要目的就是进行概率推理从技术层面讲，贝叶斯网是一种系统地描述随机变量之间关系从技术层面讲，贝叶斯网是一种系统地描述随机变量之间关系的语言，它利用变量间的独立关系将联合概率分布分解成多个的

160、语言，它利用变量间的独立关系将联合概率分布分解成多个复杂度较低的概率分布，从而大大降低了知识获取的难度和模复杂度较低的概率分布，从而大大降低了知识获取的难度和模型表达的复杂度，提高推理效率，使得人们可以应用概率方法型表达的复杂度，提高推理效率，使得人们可以应用概率方法来解决大型问题来解决大型问题贝叶斯网是概率论与图论相结合的产物，它一方面用图论的语贝叶斯网是概率论与图论相结合的产物，它一方面用图论的语言直观揭示问题的结构，另一方面又按照概率论的原则对问题言直观揭示问题的结构，另一方面又按照概率论的原则对问题的结构加以利用，降低推理的计算复杂度的结构加以利用，降低推理的计算复杂度利用贝叶斯网可以

161、完成因果推理、诊断推理、原因关联推理及利用贝叶斯网可以完成因果推理、诊断推理、原因关联推理及混合推理混合推理 188贝叶斯网与概率推理贝叶斯网与概率推理1.因果推理因果推理是从原因到结果的预测推理是从原因到结果的预测推理已知已知R=t，计算，计算P(W=t/R=t) 2.诊断推理诊断推理是从结果到原因的预测推理是从结果到原因的预测推理已知已知W=t，计算，计算P(R=t/W=t) 3.原因关联推理原因关联推理是对同一结果的不同原因之间的关联推理是对同一结果的不同原因之间的关联推理已知已知R=t和和S=t都是导致都是导致W=t的原因，已知的原因，已知W=t后，对后，对R=t的信度为的信度为P(R

162、=t/W=t)，如果又知道，如果又知道S=t，对，对R=t的信度为的信度为P(R=t/W=t,S=t)4.混合推理混合推理是上述是上述3种类型的混合种类型的混合已知已知C=t和和W=t，计算，计算P(S=t/W=t,C=t) 有因果推理，又有诊断推理有因果推理，又有诊断推理 189贝叶斯网与概率推理贝叶斯网与概率推理贝叶斯网推理算法包括精确推理和近似推理两类贝叶斯网推理算法包括精确推理和近似推理两类精确推理得到精确的概率值，近似推理得到近似的概率值精确推理得到精确的概率值，近似推理得到近似的概率值常用的精确推理算法有变量消元算法和团树传播算法常用的精确推理算法有变量消元算法和团树传播算法变量消

163、元算法是首先设置证据变量变量消元算法是首先设置证据变量E的值，然后逐步消除非查的值，然后逐步消除非查询变量，得到一个关于查询变量询变量，得到一个关于查询变量A的概率函数，基于此函数计的概率函数，基于此函数计算算P(A/E=e)证据证据F=0，计算，计算P(A/F=0) 消去变量（消去变量（C，E，B，D），获得），获得h(A)，利用，利用h(A)计算计算P(A/F=0) 变量消元算法逐一处理推理问题，不考虑多次推理步骤共享，效率变量消元算法逐一处理推理问题，不考虑多次推理步骤共享，效率较低较低团树传播算法能利用步骤共享加快推理，它能用大约两倍于变量消团树传播算法能利用步骤共享加快推理，它能用大

164、约两倍于变量消元法计算一个变量的后验概率的时间，计算出网络中每个变量的后元法计算一个变量的后验概率的时间，计算出网络中每个变量的后验概率验概率190贝叶斯网与概率推理贝叶斯网与概率推理精确推理算法精度高，但是当网络节点众多并且连接稠密时，精确推理算法精度高，但是当网络节点众多并且连接稠密时，它们的计算复杂度高，不适用它们的计算复杂度高，不适用近似推理算法降低了对精度的要求，以求在限定的时间内得到近似推理算法降低了对精度的要求，以求在限定的时间内得到一个近似解一个近似解随机抽样算法是一种常用的近似推理算法，其基本思想是从某随机抽样算法是一种常用的近似推理算法，其基本思想是从某个概率分布随机抽样，

165、生成一组样本，然后从样本出发近似估个概率分布随机抽样，生成一组样本，然后从样本出发近似估计要计算的量计要计算的量随机抽样算法可以分为重要性抽样算法和马尔科夫链蒙特卡洛随机抽样算法可以分为重要性抽样算法和马尔科夫链蒙特卡洛算法（算法（MCMC算法）算法）两种算法的主要区别在于重要性抽样算法产生的样本之间相互两种算法的主要区别在于重要性抽样算法产生的样本之间相互独立，而独立，而MCMC算法产生的样本却互相关联算法产生的样本却互相关联191重要性抽样法重要性抽样法精确推理算法精度高，但是当网络节点众多并且连接稠密时，精确推理算法精度高，但是当网络节点众多并且连接稠密时，它们的计算复杂度高，不适用它们

166、的计算复杂度高，不适用近似推理算法降低了对精度的要求，以求在限定的时间内得到近似推理算法降低了对精度的要求，以求在限定的时间内得到一个近似解一个近似解随机抽样算法是一种常用的近似推理算法，其基本思想是从某随机抽样算法是一种常用的近似推理算法，其基本思想是从某个概率分布随机抽样，生成一组样本，然后从样本出发近似估个概率分布随机抽样，生成一组样本，然后从样本出发近似估计要计算的量计要计算的量随机抽样算法可以分为重要性抽样算法和马尔科夫链蒙特卡洛随机抽样算法可以分为重要性抽样算法和马尔科夫链蒙特卡洛算法（算法（MCMC算法）算法）两种算法的主要区别在于重要性抽样算法产生的样本之间相互两种算法的主要区

167、别在于重要性抽样算法产生的样本之间相互独立，而独立，而MCMC算法产生的样本却互相关联算法产生的样本却互相关联192重要性抽样法重要性抽样法N：贝叶斯网：贝叶斯网 X ：N中所有变量的集合中所有变量的集合P(X)：N所表示的联合概率分布所表示的联合概率分布E=e：观测到的证据：观测到的证据 Q：查询变量：查询变量推理就是求推理就是求Q取某个值取某个值q的后验概率的后验概率P(Q=q/E=e)设设W是一些变量的集合，是一些变量的集合，Y是是W的一个子集，的一个子集，Z=WY，y是是Y的的一个取值，定义函数一个取值，定义函数按条件概率的定义，有按条件概率的定义，有P(Q=q,E=e)和和P(E=e

168、)可以表示成可以表示成193重要性抽样法重要性抽样法使用重要性抽样法求解使用重要性抽样法求解P(Q=q,E=e)和和P(E=e)，需要选择重要性，需要选择重要性分布和抽样样本的拓扑序分布和抽样样本的拓扑序有向无环图的拓扑序是图中所有节点的一个线性序，其中美国有向无环图的拓扑序是图中所有节点的一个线性序，其中美国节点都在它的子节点之前出现节点都在它的子节点之前出现有有2种具体方法：逻辑抽样法、似然加权法种具体方法：逻辑抽样法、似然加权法1.逻辑抽样法逻辑抽样法逻辑抽样法使用联合概率分布逻辑抽样法使用联合概率分布P(X)作为重要性分布作为重要性分布194贝叶斯网的应用贝叶斯网的应用1.医疗诊断医疗

169、诊断从一系列临床观测和化验结果出发，对病人所患疾病的类别及从一系列临床观测和化验结果出发，对病人所患疾病的类别及其程度进行判断其程度进行判断PATHFINDER网络网络疾病节点有疾病节点有63取值，代表淋巴结取值，代表淋巴结的的63种不同的疾病种不同的疾病其它节点代表病人的症状其它节点代表病人的症状疾病节点是所有症状节点的父节疾病节点是所有症状节点的父节点点用用PATHFINDER网络进行诊断：网络进行诊断：给定症状变量的取值，计算疾病变量的后验分布，然后把后验概率最大给定症状变量的取值，计算疾病变量的后验分布，然后把后验概率最大的那个疾病作为诊断结果的那个疾病作为诊断结果195贝叶斯网的

170、应用贝叶斯网的应用2.工业应用工业应用贝叶斯网在工业中的应用很广，涉及金融分析、产品设计、生贝叶斯网在工业中的应用很广，涉及金融分析、产品设计、生产制作工艺、工业过程监控管理、在线故障诊断、可靠性分析产制作工艺、工业过程监控管理、在线故障诊断、可靠性分析故障诊断故障诊断目的是找出导致一个控制系统失灵的故障部件目的是找出导致一个控制系统失灵的故障部件自动故障诊断往往需要在系统中嵌入各种传感器，以监视系统部件的运行状自动故障诊断往往需要在系统中嵌入各种传感器，以监视系统部件的运行状态，并通过实时推理，及时发现出故障的部件态，并通过实时推理，及时发现出故障的部件汽车启动故障诊断贝叶斯网汽车启动故障

171、诊断贝叶斯网导致汽车无法启动的原因有多个，导致汽车无法启动的原因有多个，故障诊断就是根据观测到的证据进故障诊断就是根据观测到的证据进行概率推理，找出后验概率最大的行概率推理，找出后验概率最大的那个原因那个原因196贝叶斯网的应用贝叶斯网的应用3.金融分析金融分析在金融分析中，贝叶斯网被用于解决石油价格预测、证券风险在金融分析中，贝叶斯网被用于解决石油价格预测、证券风险与回报、风险投资决策、运筹风险分析等问题与回报、风险投资决策、运筹风险分析等问题证券风险回报分析的贝叶斯网证券风险回报分析的贝叶斯网ABX、AEM、BGO是是3家从事黄家从事黄金开采的公司，图中表示各自的股金开采的公司，图中表示

172、各自的股票回报票回报回报都依赖于股票市场、黄金价格回报都依赖于股票市场、黄金价格及与各自股票相关的一个效应因子及与各自股票相关的一个效应因子基于这个贝叶斯网进行分析的结果是一个证券回报概率分布，进一基于这个贝叶斯网进行分析的结果是一个证券回报概率分布，进一步还可以计算回报的期望值、期望方差及风险等信息步还可以计算回报的期望值、期望方差及风险等信息197贝叶斯网的应用贝叶斯网的应用4.计算机系统计算机系统贝叶斯网在计算机系统中的应用包括程序理解、软件测试、垃贝叶斯网在计算机系统中的应用包括程序理解、软件测试、垃圾邮件过滤、决策信息显示、信息提取、用户特征提取等圾邮件过滤、决策信息显示、信息提取

173、、用户特征提取等打印机故障诊断贝叶斯网局部打印机故障诊断贝叶斯网局部当出现打印颜色过浅的问题时，可当出现打印颜色过浅的问题时，可能的故障有多个，包括墨粉不均匀、能的故障有多个，包括墨粉不均匀、墨盒故障、数据出错、打印驱动故墨盒故障、数据出错、打印驱动故障等障等这些故障可以采取措施修复：摇晃这些故障可以采取措施修复：摇晃重置墨盒、换墨盒、关电源重启重置墨盒、换墨盒、关电源重启198贝叶斯网的应用贝叶斯网的应用5.军事应用军事应用战场上局势复杂多变，充满不确定性，涉及的问题往往具有实战场上局势复杂多变，充满不确定性，涉及的问题往往具有实时性、动态性及离散和连续变量相混合的特点时性、动态性及离散和连

174、续变量相混合的特点贝叶斯网在军事上的应用包括目标识别、多目标跟踪、自动防贝叶斯网在军事上的应用包括目标识别、多目标跟踪、自动防御、战场推理、训练仿真等御、战场推理、训练仿真等作战飞机身份识别的贝叶斯网作战飞机身份识别的贝叶斯网分类：飞机类型分类：飞机类型雷达：飞机的雷达信号类型雷达：飞机的雷达信号类型身份：敌、友、中性身份：敌、友、中性根据收集到的证据，计算飞机身份根据收集到的证据，计算飞机身份的后验概率分布，最终决定是否射的后验概率分布，最终决定是否射击击199贝叶斯网的应用贝叶斯网的应用6.生态学生态学生态学家和野生动物学家面临的一个任务是分析人类活动对环生态学家和野生动物学家面临的一个

175、任务是分析人类活动对环境及濒临灭绝物种的影响境及濒临灭绝物种的影响数据采集比较困难，需要有效地将珍贵数据与专家的主观评价数据采集比较困难，需要有效地将珍贵数据与专家的主观评价结合起来支持有关决策结合起来支持有关决策河口藻化现象的贝叶斯网河口藻化现象的贝叶斯网藻化现象指的是由于人为因素的影响使藻化现象指的是由于人为因素的影响使得某个水域的藻类植物过分生长的现象得某个水域的藻类植物过分生长的现象藻化现象涉及在不同时空尺度上多个过藻化现象涉及在不同时空尺度上多个过程的相互作用，传统方法效果不好程的相互作用，传统方法效果不好网络描述了藻化现象中多个变量之间的网络描述了藻化现象中多个变量之间的因果关系，为生态环境的监控和干涉后因果关系，为生态环境的监控和干涉后果的预测提供了可行的方法果的预测提供了可行的方法200

展开阅读全文

数据分析方法及模型课件

最新文档