数据分析方法及模型讲稿.ppt

《数据分析方法及模型讲稿.ppt》由会员分享，可在线阅读，更多相关《数据分析方法及模型讲稿.ppt（200页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于数据分析方法及模型关于数据分析方法及模型1第一页，讲稿共二百页哦2分析技术及模型分析技术及模型数据预处理数据预处理第二页，讲稿共二百页哦3数据预处理数据预处理各种数据分析技术的对象是数据源中的数据各种数据分析技术的对象是数据源中的数据数据源中的数据可能不完整（如某些属性的值不确定或空缺）、数据源中的数据可能不完整（如某些属性的值不确定或空缺）、含噪声和不一致（如同一个属性在不同表中的名称不同）含噪声和不一致（如同一个属性在不同表中的名称不同）、量纲、量纲不同不同如果直接在这些未经处理的数据上进行分析，结果不一定准确，如果直接在这些未经处理的数据上进行分析，结果不一定准确，效率也可能较低效率

2、也可能较低需要使用清理、集成、变换、归约等预处理方法改善数据质量，需要使用清理、集成、变换、归约等预处理方法改善数据质量，从而提高数据分析的效率与质量从而提高数据分析的效率与质量 主要介绍数据清理、集成、变换、规约等预处理技术主要介绍数据清理、集成、变换、规约等预处理技术第三页，讲稿共二百页哦4数据清理数据清理数据清理用于消除噪声、数据不一致及数据不完整数据清理用于消除噪声、数据不一致及数据不完整噪声可以通过平滑、识别孤立点等方法进行消除噪声可以通过平滑、识别孤立点等方法进行消除分箱技术：分箱技术：将数据排序，根据等深或等宽分布规则将数据分布到不将数据排序，根据等深或等宽分布规则将数据分布到不

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

4、：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第四页，讲稿共二百页哦5数据清理数据清理数据不完整可以使用下列方法消除：数据不完整可以使用下列方法消除：1）使用一个全局常量填充）使用一个全局常量填充2）使用属性平均值填充）使用属性平均值填充3）使用相同类的属性平均值填充）使用相同类的属性平均值填充4）使用最可能的值填充）使用最可能的值填充 需要采用预测算法，预测给定样本的最可需要采用预测算法，预测给定样本的最可能的值并填充能的值并填充数据不一致可以通过元数据消除（描述数据的数据）数据不一致可以通过元数据消除（描述

5、数据的数据）第五页，讲稿共二百页哦6数据集成数据集成数据集成是将多个数据源中的数据结合起来存放在一个一致的数据存储数据集成是将多个数据源中的数据结合起来存放在一个一致的数据存储（如数据仓库）中（如数据仓库）中这些数据源可能包括多个数据库、数据立方体或一般文件这些数据源可能包括多个数据库、数据立方体或一般文件在数据集成时，需要消除冗余在数据集成时，需要消除冗余能够由另外的属性能够由另外的属性“导出导出”、命名的、命名的不一致的属性不一致的属性冗余可以通过相关分析进行检测冗余可以通过相关分析进行检测属性属性A、B之间的相关性计算：之间的相关性计算：rA,B0，A与与B正相关，正相关，A的值随着的值

6、随着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规格化后的取

7、值区间，最小规格化后的取值区间，最小-最大规格化根最大规格化根据下式将据下式将A的值的值v规格化为值规格化为值v采用最小采用最小-最大规格化方法将最大规格化方法将100，100中的中的66规格化到区间规格化到区间0，1 第七页，讲稿共二百页哦8数据变换数据变换零零-均值规格化：均值规格化：对均值为对均值为 、方差为、方差为 的数值属性的数值属性A将将A的值的值v规格化为值规格化为值v设某属性的平均值、标准差分别为设某属性的平均值、标准差分别为80、25，采用零，采用零-均值规格化均值规格化66 小数定标规格化小数定标规格化：数值属性数值属性A的最大绝对值为的最大绝对值为max|A|A，j为满足

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

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

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

11、阈值，再根据的属性阈值，再根据A的概念层次树，将关的概念层次树，将关系表中系表中A的叶概念转换为上一层的相应概念的叶概念转换为上一层的相应概念如此重复，直至关系表中如此重复，直至关系表中A的不同概念个数小于等于的不同概念个数小于等于A的属性阈值；最后合的属性阈值；最后合并相同记录，并统计重复记录数目并相同记录，并统计重复记录数目第十页，讲稿共二百页哦11数据规约数据规约属性阈值均为属性阈值均为4记录由记录由6个归约为个归约为3个个count的值表示重复记录数目的值表示重复记录数目第十一页，讲稿共二百页哦12属性概念分层的自动生成属性概念分层的自动生成 概念分层一般由系统用户、领域专家提供，但非

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

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

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

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

16、为100,100属性值及记录数如表所示属性值及记录数如表所示属性值36182226记录数69362821划分区间划分区间100,100第十五页，讲稿共二百页哦16属性概念分层的自动生成属性概念分层的自动生成 连续属性概念分层的自动生成连续属性概念分层的自动生成 属性值36182226记录数69362821划分区间划分区间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,10

17、0,26)=2.03781.3323=0.7055最佳划分：最佳划分：V1=100,22)(llu)不是强关联规则，则规则不是强关联规则，则规则lv=(llv)也不是强关联规则也不是强关联规则 证明：证明：sup_count(lv)sup_count(lu)i1i2 i5不是强关联规则不是强关联规则i2i1i5、i1i2i5都不可能是强都不可能是强关联规则关联规则l=i1i2i5lvi1、i2lui1i2第三十六页，讲稿共二百页哦37Apriori算法算法压缩强关联搜索空间压缩强关联搜索空间对于每个频繁项集，第一层产生后件只有一项的强关联规则，并生成对于每个频繁项集，第一层产生后件只有一项的强

18、关联规则，并生成它们的它们的1-后件集合后件集合R1第二层产生后件有两项的强关联第二层产生后件有两项的强关联规则，并生成它们的规则，并生成它们的2-后件集合后件集合R2R2通过通过R1中的后件进行连接运算，中的后件进行连接运算，再通过置信度计算产生再通过置信度计算产生依次类推，可以产生所有强关联规依次类推，可以产生所有强关联规则则第三十七页，讲稿共二百页哦38Apriori算法算法算法描述算法描述输入：事务集合输入：事务集合T，最小支持度阈值，最小支持度阈值min_sup，最小置信度阈值，最小置信度阈值min_conf输出：强关联规则集合输出：强关联规则集合SR变量：频繁变量：频繁k-项集集合

19、项集集合Lk，候选，候选k-项集集合项集集合Ck，频繁项集集合，频繁项集集合L，k-后件集合后件集合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-项集项集第三十八页，讲稿共二百页哦39Apriori算法算法算法描述算法描述（3）for(k=2；Lk-1；k+)（3.1）for Lk-1中

20、的每个项集中的每个项集lu （3.1.1）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 （3.2.1）for t中的每个中的每个k-项集项集s if sCk then s.sup_count=s.sup_count+1 /k-项集支持计数项集支持计数第三十九页，讲稿共二百页哦40Apriori算

21、法算法算法描述算法描述 （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 SR=SR(l-l1)=l1 /找出后件只有找出后件只有1项的强关联规则项的强关联规则 R1=R1l1 /找出找出1-后件后件 第四十页，讲稿共二百页哦41Apriori算法算法算法描述算法描述（4.2）for(j=2；Rj-1；j+)

22、（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第四十一页，讲稿共二百页哦42Apriori算法算法影响影响Apriori算法时间复杂度主要因素算法时间复杂度主要因素（1）事务集合）事务集合当项数当项数m增加：候选项集的数目和长度可能增加，频繁项集的数目和

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

24、3）最小置信度阈值）最小置信度阈值min_confmin_conf越小，强关联规则的数目越多，产生规则的运行时间越长越小，强关联规则的数目越多，产生规则的运行时间越长第四十二页，讲稿共二百页哦43频繁项集的紧凑表示频繁项集的紧凑表示 通常，从现实事务集合中产生的频繁项集的数量庞大通常，从现实事务集合中产生的频繁项集的数量庞大为了提高关联规则挖掘算法的效率，频繁项集使用紧凑表示为了提高关联规则挖掘算法的效率，频繁项集使用紧凑表示最大频繁项集：最大频繁项集：一个频繁项集的所有直接超集都不是频繁项集一个频繁项集的所有直接超集都不是频繁项集由最大频繁项集可以推导所有频繁项集由最大频繁项集可以推导所有频

25、繁项集 频繁项集频繁项集非频繁项集非频繁项集最大频繁项集最大频繁项集由由 ad可以推导频繁项集可以推导频繁项集a、d和和ad由由bcd可以推导可以推导b、c、d、bc、bd、cd和和bcd 第四十三页，讲稿共二百页哦44频繁项集的紧凑表示频繁项集的紧凑表示 为了高效找出最大频繁项集，可以将搜索空间按前缀或后缀变换为树为了高效找出最大频繁项集，可以将搜索空间按前缀或后缀变换为树（前缀树、后缀树（前缀树、后缀树），然后采用宽度或深度优先策略进行搜索），然后采用宽度或深度优先策略进行搜索前缀树前缀树后缀树后缀树第四十四页，讲稿共二百页哦45频繁项集的紧凑表示频繁项集的紧凑表示 宽度优先是先搜索同一层

26、的频繁项集，再搜索下一层的频繁项集宽度优先是先搜索同一层的频繁项集，再搜索下一层的频繁项集 深度优先是搜索到某层的一个频集时，先搜索更深层的频集，若没有深度优先是搜索到某层的一个频集时，先搜索更深层的频集，若没有频集则回溯，直至没有频项集产生也没有回溯频集则回溯，直至没有频项集产生也没有回溯 深度优先搜索策略可以更快地检测深度优先搜索策略可以更快地检测到频繁项集边界，通常用于搜索最到频繁项集边界，通常用于搜索最大频繁项集大频繁项集 深度优先与最大频繁项集搜索深度优先与最大频繁项集搜索第四十五页，讲稿共二百页哦46频繁项集的紧凑表示频繁项集的紧凑表示 最大频繁项集集合是频繁项集集合的紧凑表示最大

27、频繁项集集合是频繁项集集合的紧凑表示由最大频繁项集可以推导所有频繁项集，但由最大频繁项集不能推导它们的支由最大频繁项集可以推导所有频繁项集，但由最大频繁项集不能推导它们的支持计数持计数闭项集：闭项集：一个项集的所有直接超集的支持计数都不等于该项集的支持计数一个项集的所有直接超集的支持计数都不等于该项集的支持计数频繁闭项集：频繁闭项集：一个一个项集是频繁项集并项集是频繁项集并且是闭项集且是闭项集最小支持计数最小支持计数阈值是阈值是5 第四十六页，讲稿共二百页哦47频繁项集的紧凑表示频繁项集的紧凑表示 定理定理 对于频繁项集对于频繁项集l及其所有直接超集及其所有直接超集li=li(iI)，如果，如

28、果l是最大频繁项是最大频繁项集，则集，则l是频繁闭项集是频繁闭项集 sup_count(l)nmin_sup 证明：证明：定理定理 对于频繁项集对于频繁项集l及其所有直接超集及其所有直接超集li=li(iI)，如果，如果l不是闭项集，不是闭项集，则则 证明：证明：基于该定理，频繁非闭项基于该定理，频繁非闭项集的支持计数可以通过频集的支持计数可以通过频繁闭项集的支持计数确定繁闭项集的支持计数确定第四十七页，讲稿共二百页哦48频繁项集的紧凑表示频繁项集的紧凑表示 项集项集c不是闭项集，它的支持计数不是闭项集，它的支持计数等于项集等于项集bc的支持计数的支持计数 频繁项集、频繁闭项集与最大频繁项集的

29、关系频繁项集、频繁闭项集与最大频繁项集的关系：第四十八页，讲稿共二百页哦49频繁项集的紧凑表示频繁项集的紧凑表示通过频繁闭项集的支持计数计算其它频繁非闭项集的支持计数的算法描述通过频繁闭项集的支持计数计算其它频繁非闭项集的支持计数的算法描述输入：频繁闭项集集合输入：频繁闭项集集合CL输出：频繁项集集合输出：频繁项集集合L步骤：步骤：（1）/找出频繁闭项集的最大长度找出频繁闭项集的最大长度（2）/找出最长频繁闭项集找出最长频繁闭项集（3）/最长频繁闭项集也是最长频繁项集最长频繁闭项集也是最长频繁项集（4）for(k=kmax-1；k1；k-)/找出所有频繁项集找出所有频繁项集 （4.1）/找出由

30、频繁闭找出由频繁闭(k+1)-项集推导的频繁项集推导的频繁k-项集项集 （4.2）CLk=l|lCL,|l|=k /找出频繁闭找出频繁闭k-项集项集第四十九页，讲稿共二百页哦50频繁项集的紧凑表示频繁项集的紧凑表示通过频繁闭项集的支持计数计算其它频繁非闭项集的支持计数的算法描述通过频繁闭项集的支持计数计算其它频繁非闭项集的支持计数的算法描述（4.3）for TLk中每个项集中每个项集 /计算频繁非闭计算频繁非闭k-项集的支持计数项集的支持计数 （4.3.1）if then Lk=Lkl（4.4）Lk=LkCLk（4.5）L=LLk第五十页，讲稿共二百页哦51频繁项集的紧凑表示频繁项集的紧凑表示

31、最小支持计数阈值是最小支持计数阈值是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=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第五十一页，讲稿共

32、二百页哦52FP-growth算法算法 Apriori算法的不足：算法的不足：1）可能产生大量候选项集）可能产生大量候选项集2）可能需要重复扫描数据库，通过模式匹配检查庞大的候选集合）可能需要重复扫描数据库，通过模式匹配检查庞大的候选集合FP-growth算法采用一种称为算法采用一种称为FP树的结构表示事务集合中项集的关联，并树的结构表示事务集合中项集的关联，并在在FP树上递归地找出所有频繁项集，算法并不产生候选树上递归地找出所有频繁项集，算法并不产生候选基本思想：基本思想：扫描一次事务集合，找出频繁扫描一次事务集合，找出频繁1-项集合项集合L1基于基于L1，再扫描一次事务集合，构造表示事务集

33、合中项集关联的，再扫描一次事务集合，构造表示事务集合中项集关联的FP树树在在FP树上递归地找出所有频繁项集树上递归地找出所有频繁项集最后在所有频繁项集中产生强关联规则最后在所有频繁项集中产生强关联规则 第五十二页，讲稿共二百页哦53FP-growth算法算法 1）扫描一次事务集合，找出频繁）扫描一次事务集合，找出频繁1-项集合项集合L，并按支，并按支持计数降序排序持计数降序排序L中的频繁项中的频繁项FP树构造树构造 事务项t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3min_sup=20%L

34、=i2:7,i1:6,i3:5,i4:2,i5:2 2）创建）创建FP树的根节点，用树的根节点，用“null”标记标记null第五十三页，讲稿共二百页哦54FP-growth算法算法 3）再扫描一次事务集合，对每个事务找出其中的）再扫描一次事务集合，对每个事务找出其中的频繁项并按频繁项并按L中的顺序排序，为每个事务创建一个分中的顺序排序，为每个事务创建一个分枝，事务分枝路径上的节点就是该事务中的已排序频枝，事务分枝路径上的节点就是该事务中的已排序频繁项繁项对于各个事务分枝，如果可以共享路径则共享对于各个事务分枝，如果可以共享路径则共享并且在各个节点上记录共享事务数目并且在各个节点上记录共享事务

35、数目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 第五十四页，讲稿共二百页哦55FP-growth算法算法 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 4）为方便遍历）为方便遍历FP树，为树，为FP树创建一个项表树创建一个项表项表中每

36、一行表示一个频繁项，并有一个指针指项表中每一行表示一个频繁项，并有一个指针指向它在向它在FP树中的节点树中的节点FP树中相同频繁项的节点通过指针连成链表树中相同频繁项的节点通过指针连成链表 第五十五页，讲稿共二百页哦56FP-growth算法算法 FP树构造树构造 事务项t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3第五十六页，讲稿共二百页哦57FP-growth算法算法 由长度为由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基。的频繁模式（初始后缀模式）开始，构造它的条件模式基

37、。然后，构造它的条件然后，构造它的条件FP树，并递归地在该树上进行挖掘。模式增长通过树，并递归地在该树上进行挖掘。模式增长通过后缀模式与由条件后缀模式与由条件FP树产生的频繁模式连接实现树产生的频繁模式连接实现条件模式基：条件模式基：一个一个“子数据库子数据库”，由，由FP树中与后缀模式一起出现的前树中与后缀模式一起出现的前缀路径集组成缀路径集组成条件条件FP树：树：条件模式基中，由满足最小支持度阈值的节点构成的树条件模式基中，由满足最小支持度阈值的节点构成的树FP树挖掘树挖掘i5:2的条件模式基的条件模式基null,i2,i1:2 i5:2 与条件与条件FP树树 第五十七页，讲稿共二百页哦5

38、8FP-growth算法算法 递归过程：递归过程：1）如果条件）如果条件FP树只有一个分枝，则分枝路径上的节点的一个组合就是一树只有一个分枝，则分枝路径上的节点的一个组合就是一个前缀模式个前缀模式，一个前缀模式，一个前缀模式与后缀模式与后缀模式产生一个频繁项集产生一个频繁项集（递（递归出口）归出口）2）否则用）否则用L中的频繁项中的频繁项i增长后缀模式增长后缀模式（i，增长时，按逆序方，增长时，按逆序方式处理，即先考虑式处理，即先考虑L的最后一项），然后构造增长后缀模式的最后一项），然后构造增长后缀模式i 的条的条件模式基与条件件模式基与条件FP树，递归上述过程树，递归上述过程初始时，初始时，

39、=null，null的条件的条件FP树就是树就是FP树树FP树挖掘树挖掘第五十八页，讲稿共二百页哦59FP-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树有多个树有多个分枝，进入第二层递分枝，进入第二层递

40、归归i3:5的条件的条件FP树有两个分枝，树有两个分枝，进入第三层递归进入第三层递归 第五十九页，讲稿共二百页哦60FP-growth算法算法 第三层递归：第三层递归：FP树挖掘树挖掘条件模式基条件FP树产生的频繁项集i1i3:3null,i2:1、null:2i1i3:3i2i3:3null:3i2i3:3第六十页，讲稿共二百页哦61FP-growth算法算法 输入：事务集合输入：事务集合T，最小支持度阈值，最小支持度阈值min_sup，最小置信度阈值，最小置信度阈值min_conf输出：强关联规则集合输出：强关联规则集合R_S步骤：步骤：（1）扫描）扫描T找出频繁找出频繁1-项集合项集合L

41、（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_S=Search-FP（FP,null）/找出所有频繁项集找出所有频繁项集（6）在）在L_S中产生强关联规则集合中产生强关联规则集合R_S算法描述算法描述第六十一页，讲稿共二百页哦62FP-growth算法算法 算法：算法：Inse

42、rt-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.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）算法描述算法

43、描述第六十二页，讲稿共二百页哦63FP-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）构造）构造的条件模式基及其条件的条件模式基及其条件FP树树T （2.1.3

44、）Search-FP（T,）算法描述算法描述第六十三页，讲稿共二百页哦64分析技术及模型分析技术及模型聚类分析聚类分析第六十四页，讲稿共二百页哦65将物理或抽象对象的集合分成相似的对象类的过程将物理或抽象对象的集合分成相似的对象类的过程使得同一个簇中的对象之间具有较高的相似性，而不同簇中的对使得同一个簇中的对象之间具有较高的相似性，而不同簇中的对象具有较高的相异性象具有较高的相异性是数据挖掘、模式识别等研究方向的重要研究内容之一，在识别是数据挖掘、模式识别等研究方向的重要研究内容之一，在识别数据的内在结构方面具有极其重要的作用数据的内在结构方面具有极其重要的作用 广泛应用于模式识别、数据分析、

45、图像处理和市场研究等领域，对广泛应用于模式识别、数据分析、图像处理和市场研究等领域，对生物学、心理学、考古学、地质学及地理学等研究也有重要作用生物学、心理学、考古学、地质学及地理学等研究也有重要作用 主要介绍聚类概念、聚类过程、常用聚类算法主要介绍聚类概念、聚类过程、常用聚类算法 聚类分析聚类分析第六十五页，讲稿共二百页哦66=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个簇，个簇，C Cx x，x=x=1 1，2 2，k kSimilarity(Simil

46、arity(o oi i,o,oj j)表示对象表示对象o oi i与对象与对象o oj j之间的相似度之间的相似度若各簇若各簇CxCx是刚性聚类结果，则各是刚性聚类结果，则各CxCx需满足如下条件：需满足如下条件：1 1）2 2）对于）对于 有有3 3）聚类分析的形式描述聚类分析的形式描述第六十六页，讲稿共二百页哦67数据数据准备准备属性选择属性选择属性提取属性提取聚聚类类结果结果评估评估聚类过程聚类过程为聚类分析准备为聚类分析准备数据，包括属性数据，包括属性值标准化值标准化从最初的属性中选择从最初的属性中选择最有效的属性最有效的属性通过对所选择的属性进行通过对所选择的属性进行转换形成新的更

47、有代表性转换形成新的更有代表性的属性的属性度量对象间的相似性程度，度量对象间的相似性程度，执行聚类或分组执行聚类或分组 聚类分析的三要素是相似性测度、聚类准则和聚类算法聚类分析的三要素是相似性测度、聚类准则和聚类算法第六十七页，讲稿共二百页哦68聚类分析中的数据类型聚类分析中的数据类型聚类分析中常用的数据类型有：数据矩阵、相异度矩阵聚类分析中常用的数据类型有：数据矩阵、相异度矩阵1）数据矩阵：对象在多维空间中通常表示为点（向量），其每一维表）数据矩阵：对象在多维空间中通常表示为点（向量），其每一维表示为不同属性，这些属性描述出对象示为不同属性，这些属性描述出对象数据矩阵每行代表一个对象，每列代

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

49、好聚类结果 实际上，确定了相似性测度和聚类准则后，聚类就变成了使准则函数实际上，确定了相似性测度和聚类准则后，聚类就变成了使准则函数取极值的优化问题了取极值的优化问题了 没有任何一种聚类算法可以普遍适用于揭示各种多维数据集所呈现出没有任何一种聚类算法可以普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构来的多种多样的结构 因此聚类算法有多种，不同的聚类算法使用不同的相似性度量和准因此聚类算法有多种，不同的聚类算法使用不同的相似性度量和准则则第六十九页，讲稿共二百页哦70对象之间的相似性根据描述对象的属性值评估，可以使用距离、密度、对象之间的相似性根据描述对象的属性值评估，可以使用距离、密度

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