数据分析方法及模型

关于数据分析方法及模型1第1页，课件共200页，创作于2023年2月2分析技术及模型

——数据预处理第2页，课件共200页，创作于2023年2月3数据预处理各种数据分析技术的对象是数据源中的数据数据源中的数据可能不完整（如某些属性的值不确定或空缺）、含噪声和不一致（如同一个属性在不同表中的名称不同）、量纲不同如果直接在这些未经处理的数据上进行分析，结果不一定准确，效率也可能较低需要使用清理、集成、变换、归约等预处理方法改善数据质量，从而提高数据分析的效率与质量主要介绍数据清理、集成、变换、规约等预处理技术第3页，课件共200页，创作于2023年2月4数据清理数据清理用于消除噪声、数据不一致及数据不完整噪声可以通过平滑、识别孤立点等方法进行消除分箱技术：将数据排序，根据等深或等宽分布规则将数据分布到不同箱中，将同一箱中的数据用用该箱中数据的平均值或中值、边界值替换（平均值平滑、中值平滑、边界平滑）每个箱中的数据个数或取值区间相等设某属性的值为18，12，3，9，7，6，15，21，16，采用分箱技术平滑数据消除噪声。分布规则为等深、深度为3，平滑规则为平均值平滑首先，将属性的值排序为3,6,7,9,12,15,16,18,21箱1：3,6,7箱2：9,12,15箱3：16,18,21箱1：5.3,5.3,5.3箱2：12,12,12箱3：18.3,18.3,18.3第4页，课件共200页，创作于2023年2月5数据清理数据不完整可以使用下列方法消除：1）使用一个全局常量填充2）使用属性平均值填充3）使用相同类的属性平均值填充4）使用最可能的值填充需要采用预测算法，预测给定样本的最可能的值并填充数据不一致可以通过元数据消除（描述数据的数据）第5页，课件共200页，创作于2023年2月6数据集成数据集成是将多个数据源中的数据结合起来存放在一个一致的数据存储（如数据仓库）中这些数据源可能包括多个数据库、数据立方体或一般文件在数据集成时，需要消除冗余——能够由另外的属性“导出”、命名的不一致的属性冗余可以通过相关分析进行检测属性A、B之间的相关性计算：rA,B>0，A与B正相关，A的值随着B的值的增加而增加rA,B<0，A与B负相关，A的值随着B的值的增加而减少rA,B=0，A与B独立。因此，|rA,B|很大时，A与B可以去除一个平均值方差第6页，课件共200页，创作于2023年2月7数据变换将属性数据按比例缩放，使之落入一个小的特定区间，如－1.0到1.0或0.0到1.0

最小-最大规格化：[minA，maxA]为数值属性A规格化前的取值区间[new_minA，new_maxA]为A规格化后的取值区间，最小-最大规格化根据下式将A的值v规格化为值v’采用最小-最大规格化方法将[－100，100]中的66规格化到区间[0，1]第7页，课件共200页，创作于2023年2月8数据变换零-均值规格化：对均值为、方差为的数值属性A将A的值v规格化为值v’设某属性的平均值、标准差分别为80、25，采用零-均值规格化66小数定标规格化

：数值属性A的最大绝对值为max|A|A，j为满足的最小整数将A的值v规格化为值v’规格化[－100，100]中的66A的最大绝对值为120，j为3

第8页，课件共200页，创作于2023年2月9数据规约数据归约技术可以用来得到数据集的归约表示，它小得多，但仍接近于保持原数据集的完整性在归约后的数据集上分析将更有效，并产生相同（或几乎相同）的分析结果归约方法主要有：属性归约、记录归约属性规约：删除不相关的或冗余的属性减小数据集，目标是找出最小属性集，使得数据在其上的概率分布尽可能地接近在原属性集上的概率分布常用方法：粗糙集中的属性约简、决策树记录规约：用少量记录代表或替换原有记录，从而减小数据集常用方法：抽样、数据概化第9页，课件共200页，创作于2023年2月10数据规约数据概化：采用面向属性归纳，根据属性的概念分层，通过阈值控制，将属性的低层属性值用相应高层概念替换，并合并由此得到的相同记录概念分层一般用树结构描述，称为概念层次树阈值控制面向属性归纳过程，每个属性都有概念层次树及阈值首先根据属性A的概念层次树，将关系表中A的属性值转换为最低层的相应概念（叶概念），统计关系表中A的不同叶概念个数如果A的不同叶概念个数大于A的属性阈值，再根据A的概念层次树，将关系表中A的叶概念转换为上一层的相应概念如此重复，直至关系表中A的不同概念个数小于等于A的属性阈值；最后合并相同记录，并统计重复记录数目第10页，课件共200页，创作于2023年2月11数据规约属性阈值均为4记录由6个归约为3个count的值表示重复记录数目第11页，课件共200页，创作于2023年2月12属性概念分层的自动生成概念分层一般由系统用户、领域专家提供，但非常耗时、乏味介绍离散属性与连续属性自动生成概念分层的方法离散属性概念分层的自动生成概念层次树中高层的概念个数一般少于低层的概念个数首先统计各个概念的不同值个数，个数最少的概念在最高层，依次类推，然后根据结构的从属关系，确定各层的概念及从属关系地址国家省市中国云南省昆明市中国云南省大理市中国四川省成都市中国贵州省贵阳市中国云南省玉溪市中国云南省曲靖市第12页，课件共200页，创作于2023年2月13属性概念分层的自动生成连续属性概念分层的自动生成连续属性可以通过离散化递归地自动生成概念分层离散化可以基于熵完成，主要步骤：1）计算关系表r中在属性A的取值区间V上的记录集合S的熵|c|：S中属于目标类c的记录数|S|：S中的记录数2）对A在V上取的每个v，用v划分V为v1（<v）、v2（≥v），划分S为S1，S2，计算在此划分下S的熵E(S1)、E(S2)分别为S1、S2的熵第13页，课件共200页，创作于2023年2月14属性概念分层的自动生成连续属性概念分层的自动生成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）就可以得到各层结点第14页，课件共200页，创作于2023年2月15属性概念分层的自动生成连续属性概念分层的自动生成设“气温”属性是目标属性，取值区间为[－100,100]属性值及记录数如表所示属性值－36182226记录数69362821划分区间[－100,100]第15页，课件共200页，创作于2023年2月16属性概念分层的自动生成连续属性概念分层的自动生成属性值－36182226记录数69362821划分区间[－100,100]G([－100,100],－3)=2.0378－2.0378=0G([－100,100],6)=2.0378－1.7465=0.2913G([－100,100],18)=2.0378－1.464=0.5738G([－100,100],22)=2.0378－1.0741=0.9637G([－100,100],26)=2.0378－1.3323=0.7055最佳划分：V1=[－100,22)(<T=22)V2=[22,100](≥T=22)第16页，课件共200页，创作于2023年2月17分析技术及模型

——关联分析第17页，课件共200页，创作于2023年2月18关联关系用关联规则表示牛奶面包（支持度=2%，置信度=60%）全部事务的2%同时购买了牛奶和面包，购买牛奶的顾客60%也购买面包关联规则挖掘有助于许多商务决策的制定，如分类设计、交叉购物和贱卖分析主要介绍关联规则概念、常用关联规则挖掘算法关联分析用于发现大量数据中项集之间有趣的关联关系或相关关系牛奶、面包谷类牛奶、面包糖、鸡蛋牛奶、面包黄油糖、鸡蛋哪些商品频繁地被顾客同时购买？第18页，课件共200页，创作于2023年2月19设I={i1,i2,…,im}是项集合，T={t1,t2,…,tn}是事务集合设A是一个项的集合，事务t包含A当且仅当A

t关联分析基本概念关联规则是形如A

B的蕴涵式，其中AI，BI，且AB=i5i1i2关联规则AB的支持度：在事务集合D中，包含的事务占全部事务的百分比，记为事务项t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3第19页，课件共200页，创作于2023年2月20关联分析基本概念关联规则AB的的置信度：在事务集合D中，包含A的事务同时也包含B的百分比，记为强规则：同时满足最小支持度阈值（min_sup）和最小置信度阈值（min_conf）的规则项集：项的集合k-项集Ik：包含k个项的项集{i1i2}是2项集Ik的支持计数（出现频率sup_count(Ik)

）

：事务集合T中，包含某k-项集Ik的事务数项集Ik满足最小支持度min_sup：项集Ik的出现频率大于或等于T中事务总数与min_sup的乘积sup_count(Ik)≥n×min_sup频繁k-项集：满足最小支持度的Ik

T中的频繁k-项集集合记为Lk

第20页，课件共200页，创作于2023年2月21关联分析关联规则挖掘算法常常假设事务中的项按字典次序存放项集按字典序从最左项到最右项依次指定这样可以避免枚举重复的事务项集事务为{abcde}3-项集的第一项（最左项）只能是a[bcde]、b[cde]、c[de][]表示随后可跟的项前二项只能是ab[cde]、ac[de]、ad[e]、bc[de]、bd[e]、cd[e]3-项集只能是{abc}、{abd}、{abe}、{acd}、{ace}、{ade}、{bcd}、{bce}、{bde}、{cde}第21页，课件共200页，创作于2023年2月22关联分析挖掘步骤关联规则挖掘算法主要包括两个步骤：（1）找出所有频繁项集（支持度测试）这些项集出现的频繁性至少和预定义的最小出现频率一样（2）由频繁项集产生强关联规则（置信度测试）这些规则必须满足最小支持度和最小置信度第一步骤是关键，它的效率影响整个关联规则挖掘算法的效率因此，关联规则挖掘算法的核心是频繁项集产生方法第22页，课件共200页，创作于2023年2月23Apriori算法Apriori性质Apriori算法采用逐层搜索策略产生所有频繁项集，同时根据Apriori性质压缩搜索空间

如果一个项集Ii是频繁项集，则它的所有非空子集Ij一定也是频繁项集

证明：

∴sup_count(Ij)≥sup_count(Ii)∵sup_count(Ii)≥n×min_sup∴sup_count(Ij)≥n×min_sup如果某个(k+1)-项集是频繁项集，则它的所有k-项集一定也是频繁项集反之，如果某个k-项集不是频繁项集，则包含它的所有(k+1)-项集也不是频繁项集因此，逐层搜索频繁项集时，频繁(k+1)-项集的产生可以在频繁k-项集的基础上通过连接、剪枝和支持计数完成，从而压缩搜索空间第23页，课件共200页，创作于2023年2月24Apriori算法Apriori算法的基本思想：首先，扫描一次事务集合，找出频繁1-项集集合L1基于L1，产生所有可能频繁的2-项集，即候选2-项集集合C2（连接）基于L1，优化C2（剪枝）基于C2，再扫描一次事务集合，找出频繁2-项集集合L2依次类推，直至不能找到频繁项集为止最后，在所有频繁项集中产生强关联规则两个关键操作：连接、剪枝两个关键步骤：确定频繁项集集合Lk+1、产生规则第24页，课件共200页，创作于2023年2月25Apriori算法连接操作基于频繁k-项集集合Lk，产生所有可能频繁的候选(k+1)-项集Ck+1设lu，lv∈Lk，li[j]（i=u或i=v，1≤j≤k）表示li的第j项，事务或项集中的项按字典序排列lu，lv可连接：lu和lv的前k-1个项相同，(lu[1]=lv[1])∧…∧(lu[k-1]=lv[k-1])∧(lu[k]＜lv[k])lu，lv的连接运算：lulv=lw=lu[1]…lu[k]lv[k]例如，{ab},{ac},{bc}∈L2，{ab}{ac}={abc}{ab}与{bc}、{ac}与{bc}不可连接保证不产生重复连接仅对频繁k-项集集合Lk中的所有可连接的频繁k-项集进行连接运算，产生候选(k+1)-项集集合Ck+1。大量压缩搜索空间第25页，课件共200页，创作于2023年2月26Apriori算法剪枝操作对候选(k+1)-项集集合Ck+1中的所有候选(k+1)-项集进行子集测试，删除非频繁的(k+1)-项集，进一步压缩搜索空间Ck+1是Lk+1的超集，即：Ck+1的成员可以是也可以不是频繁的，但所有的频繁(k+1)-项集都包含在Ck+1中根据Apriori性质，如果Ck+1中某个候选(k+1)-项集有一个k-项集不是频繁项集即不属于Lk，则这个候选(k+1)-项集肯定不是频繁(k+1)-项集，可以从Ck+1中删除例如，频繁2-项集集合L2={{bc},{bd}}，候选3-项集集合C3={{bcd}}由于2-项集{cd}不是频繁项集，所以候选3-项集{bcd}一定非频繁，可以删除第26页，课件共200页，创作于2023年2月27Apriori算法剪枝操作1-项集{a}不是频繁项集，2-项集{cd}不是频繁项集第27页，课件共200页，创作于2023年2月28Apriori算法确定Lk+1基于剪枝后的候选(k+1)-项集集合Ck+1，扫描一次事务集合，找出频繁(k+1)-项集集合Lk+1

产生规则1）对于每个频繁项集l，产生l的所有非空真子集2）对于l的每个非空真子集lu，如果l的支持计数除以lu的支持计数大于等于最小置信度阈值min_conf，则lu(l－lu)是强关联规则{bc}是频繁2-项集bcsup_count(bc)/sup_count(b)min_conf第28页，课件共200页，创作于2023年2月29Apriori算法假设事务集合T如表所示，最小支持度阈值min_sup为20%，最小置信度阈值min_conf为70%min_sup=20%n=9

n*min_sup=9*20%=1.8支持计数大于等于1.8的项集是频繁项集事务项t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3第29页，课件共200页，创作于2023年2月30Apriori算法事务项t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3第30页，课件共200页，创作于2023年2月31Apriori算法事务项t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3第31页，课件共200页，创作于2023年2月32Apriori算法事务项t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3min_conf=70%i5i1i2i1i5

i2i2i5

i1第32页，课件共200页，创作于2023年2月33Apriori算法Hash树散列为了提高Apriori算法的有效性，可以采取一些措施：1）基于散列技术压缩Ck+1中的所有候选(k+1)-项集的测试2）压缩强关联搜索空间3）不产生所有频繁项集，而仅产生较少的、代表性的、可以推导所有频繁项集的频繁项集为了确定频繁(k+1)-项集集合Lk+1，需要扫描一遍事务集合，计算Ck+1中各项的支持计数为了快速匹配和更新相应候选项集支持计数，Apriori算法采用Hash树第33页，课件共200页，创作于2023年2月34Apriori算法Hash树散列候选项集按字典序从最左项到最右项依次指定散列的Hash树分枝，最后存放于Hash树的叶节点中事务项集也按相同的方法散列到Hash树的叶节点，并仅需与叶节点中的候选项集比较，而不需与所有候选项集比较比较相符，叶节点中候选项集的支持计数增加例如，候选3-项集集合C3={{abc},{acd},{bef},{cdf},{cef},{def}}Hash树有三个分枝第34页，课件共200页，创作于2023年2月35Apriori算法Hash树散列事务为{abcde}第35页，课件共200页，创作于2023年2月36Apriori算法压缩强关联搜索空间定理对于频繁项集l及其两个非空真子集lu和lv，如果lv

lu

，并且规则lu=>(l－lu)不是强关联规则，则规则lv=>(l－lv)也不是强关联规则

证明：∴sup_count(lv)≥sup_count(lu)i1i2

i5不是强关联规则i2i1i5、i1i2i5都不可能是强关联规则l={i1i2i5}lv{i1}、{i2}lu{i1i2}第36页，课件共200页，创作于2023年2月37Apriori算法压缩强关联搜索空间对于每个频繁项集，第一层产生后件只有一项的强关联规则，并生成它们的1-后件集合R1第二层产生后件有两项的强关联规则，并生成它们的2-后件集合R2R2通过R1中的后件进行连接运算，再通过置信度计算产生依次类推，可以产生所有强关联规则第37页，课件共200页，创作于2023年2月38Apriori算法算法描述输入：事务集合T，最小支持度阈值min_sup，最小置信度阈值min_conf输出：强关联规则集合SR变量：频繁k-项集集合Lk，候选k-项集集合Ck，频繁项集集合L，k-后件集合Rk步骤：//频繁项集产生（1）forT中的每个事务t

（1.1）fort中的每个项i

（1.1.1）i.sup_count=i.sup_count+1//1-项集支持计数（2）for每个项i

（2.1）ifi.sup_count≥n×min_supthenL1=L1∪{i}//找出频繁1-项集第38页，课件共200页，创作于2023年2月39Apriori算法算法描述（3）for(k=2；Lk-1≠ø；k++)

（3.1）forLk-1中的每个项集lu

（3.1.1）forLk-1中项集lu之后的每个项集lvif(lu[1]=lv[1])∧…∧(lu[k-2]=lv[k-2])∧(lu[k-1]＜lv[k-1])then//连接

Ck=Ck∪{c}//找出候选k-项集

forc中的每个(k-1)-项集sifthenCk=Ck-{c}//剪枝（3.2）forT中的每个事务t

（3.2.1）fort中的每个k-项集sifs∈Ckthens.sup_count=s.sup_count+1//k-项集支持计数第39页，课件共200页，创作于2023年2月40Apriori算法算法描述

（3.3）forCk中的每个项集c

（3.3.1）ifc.sup_count≥n×min_supthenLk=Lk∪{c}//找出频繁k-项集（3.4）

L=L∪Lk//规则产生（4）forL中的每个频繁项集l

（4.1）forl中的每个1-项集l1

（4.1.1）ifthenSR=SR∪{(l-l1)=>l1}//找出后件只有1项的强关联规则

R1=R1∪l1//找出1-后件

第40页，课件共200页，创作于2023年2月41Apriori算法算法描述（4.2）for(j=2；Rj-1≠ø；j++)

（4.2.1）forRj-1中的每个后件luforRj-1中后件lu之后的每个后件lvif(lu[1]=lv[1])∧…∧(lu[j-2]=lv[j-2])∧(lu[j-1]＜lv[j-1])then//连接

ifthenSR=SR∪{(l-lj)=>lj}//找出后件有j项的强关联规则

Rj=Rj∪lj//找出j-后件l={i1i2i5}lu{i1}lv{i2}第41页，课件共200页，创作于2023年2月42Apriori算法影响Apriori算法时间复杂度主要因素（1）事务集合当项数m增加：候选项集的数目和长度可能增加，频繁项集的数目和长度也可能增加，从而计算频繁项集及其支持计数的时间、扫描事务集合的次数、计算强关联规则的时间可能增加事务数n、事务平均宽度w增加：每次扫描事务集合的时间增加（2）最小支持度阈值min_supmin_sup越小，候选项集和频繁项集的数目越多、长度越长，扫描事务集合的次数越多，算法的运行时间越长（3）最小置信度阈值min_confmin_conf越小，强关联规则的数目越多，产生规则的运行时间越长第42页，课件共200页，创作于2023年2月43频繁项集的紧凑表示通常，从现实事务集合中产生的频繁项集的数量庞大为了提高关联规则挖掘算法的效率，频繁项集使用紧凑表示最大频繁项集：一个频繁项集的所有直接超集都不是频繁项集由最大频繁项集可以推导所有频繁项集频繁项集非频繁项集最大频繁项集由{ad}可以推导频繁项集{a}、{d}和{ad}由{bcd}可以推导{b}、{c}、{d}、{bc}、{bd}、{cd}和{bcd}第43页，课件共200页，创作于2023年2月44频繁项集的紧凑表示为了高效找出最大频繁项集，可以将搜索空间按前缀或后缀变换为树（前缀树、后缀树），然后采用宽度或深度优先策略进行搜索前缀树后缀树第44页，课件共200页，创作于2023年2月45频繁项集的紧凑表示宽度优先是先搜索同一层的频繁项集，再搜索下一层的频繁项集深度优先是搜索到某层的一个频集时，先搜索更深层的频集，若没有频集则回溯，直至没有频项集产生也没有回溯深度优先搜索策略可以更快地检测到频繁项集边界，通常用于搜索最大频繁项集深度优先与最大频繁项集搜索第45页，课件共200页，创作于2023年2月46频繁项集的紧凑表示最大频繁项集集合是频繁项集集合的紧凑表示由最大频繁项集可以推导所有频繁项集，但由最大频繁项集不能推导它们的支持计数闭项集：一个项集的所有直接超集的支持计数都不等于该项集的支持计数频繁闭项集：一个项集是频繁项集并且是闭项集最小支持计数阈值是5第46页，课件共200页，创作于2023年2月47频繁项集的紧凑表示定理对于频繁项集l及其所有直接超集li=l∪{i}(i∈I)，如果l是最大频繁项集，则l是频繁闭项集

∵

sup_count(l)≥n×min_sup

证明：定理对于频繁项集l及其所有直接超集li=l∪{i}(i∈I)，如果l不是闭项集，则证明：基于该定理，频繁非闭项集的支持计数可以通过频繁闭项集的支持计数确定第47页，课件共200页，创作于2023年2月48频繁项集的紧凑表示项集{c}不是闭项集，它的支持计数等于项集{bc}的支持计数频繁项集、频繁闭项集与最大频繁项集的关系：第48页，课件共200页，创作于2023年2月49频繁项集的紧凑表示通过频繁闭项集的支持计数计算其它频繁非闭项集的支持计数的算法描述输入：频繁闭项集集合CL输出：频繁项集集合L步骤：（1）//找出频繁闭项集的最大长度（2）//找出最长频繁闭项集（3）//最长频繁闭项集也是最长频繁项集（4）for(k=kmax-1；k≥1；k--)//找出所有频繁项集（4.1）//找出由频繁闭(k+1)-项集推导的频繁k-项集（4.2）CLk={l|l∈CL,|l|=k}//找出频繁闭k-项集第49页，课件共200页，创作于2023年2月50频繁项集的紧凑表示通过频繁闭项集的支持计数计算其它频繁非闭项集的支持计数的算法描述（4.3）forTLk中每个项集//计算频繁非闭k-项集的支持计数（4.3.1）ifthenLk=Lk∪l（4.4）

Lk=Lk∪CLk（4.5）L=L∪Lk第50页，课件共200页，创作于2023年2月51频繁项集的紧凑表示最小支持计数阈值是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}}第51页，课件共200页，创作于2023年2月52FP-growth算法Apriori算法的不足：1）可能产生大量候选项集2）可能需要重复扫描数据库，通过模式匹配检查庞大的候选集合FP-growth算法采用一种称为FP树的结构表示事务集合中项集的关联，并在FP树上递归地找出所有频繁项集，算法并不产生候选基本思想：扫描一次事务集合，找出频繁1-项集合L1基于L1，再扫描一次事务集合，构造表示事务集合中项集关联的FP树在FP树上递归地找出所有频繁项集最后在所有频繁项集中产生强关联规则第52页，课件共200页，创作于2023年2月53FP-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第53页，课件共200页，创作于2023年2月54FP-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]第54页，课件共200页，创作于2023年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树创建一个项表项表中每一行表示一个频繁项，并有一个指针指向它在FP树中的节点FP树中相同频繁项的节点通过指针连成链表第55页，课件共200页，创作于2023年2月56FP-growth算法FP树构造事务项t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3第56页，课件共200页，创作于2023年2月57FP-growth算法由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基。然后，构造它的条件FP树，并递归地在该树上进行挖掘。模式增长通过后缀模式与由条件FP树产生的频繁模式连接实现条件模式基：一个“子数据库”，由FP树中与后缀模式一起出现的前缀路径集组成条件FP树：条件模式基中，由满足最小支持度阈值的节点构成的树FP树挖掘{i5:2}的条件模式基{null,i2,i1}:2{i5:2}与条件FP树第57页，课件共200页，创作于2023年2月58FP-growth算法递归过程：1）如果条件FP树只有一个分枝，则分枝路径上的节点的一个组合就是一个前缀模式β，一个前缀模式β与后缀模式α产生一个频繁项集β∪α（递归出口）2）否则用L中的频繁项i增长后缀模式α（{i}∪α，增长时，按逆序方式处理，即先考虑L的最后一项），然后构造增长后缀模式{i}∪α的条件模式基与条件FP树，递归上述过程初始时，α=null，null的条件FP树就是FP树FP树挖掘第58页，课件共200页，创作于2023年2月59FP-growth算法第二层递归：FP树挖掘α条件模式基条件FP树产生的频繁项集i5:2{null,i2,i1}:2<null,i2:2,i1:2>{i2i5}:2、{i1i5}:2、{i2i1i5}:2i4:2{null,i2,i1}:1、{null,i2}:1<null,i2:2>{i2i4}:2i3:5{null,i2,i1}:1、{null,i2}:2、{null,i1}:2<null,i2:3,i1:1>、<null,i1:2>i1:6{null,i2}:4、{null}:2<null,i2:4>{i2i1}:4i2:7{null}:7<null>第一层递归：α=nullnull的条件FP树有多个分枝，进入第二层递归{i3:5}的条件FP树有两个分枝，进入第三层递归第59页，课件共200页，创作于2023年2月60FP-growth算法第三层递归：FP树挖掘α条件模式基条件FP树产生的频繁项集i1i3:3{null,i2}:1、{null}:2<null>{i1i3}:3i2i3:3{null}:3<null>{i2i3}:3第60页，课件共200页，创作于2023年2月61FP-growth算法输入：事务集合T，最小支持度阈值min_sup，最小置信度阈值min_conf输出：强关联规则集合R_S步骤：（1）扫描T找出频繁1-项集合L（2）L中的项按支持计数降序排序（3）创建FP树的根节点null//创建FP树（4）forT中的每个事务t

（4.1）找出t中的频繁1-项集合Lt

（4.2）Lt中的项按L中的顺序排序（4.3）Insert-FP（Lt,null）//创建事务分枝（5）L_S=Search-FP（FP,null）//找出所有频繁项集（6）在L_S中产生强关联规则集合R_S算法描述第61页，课件共200页，创作于2023年2月62FP-growth算法算法：Insert-FP算法（Li,Tr）输入：已排序频繁1-项集合Li，FP（子）树的根节点Tr输出：FP树（1）ifLi不空then

（1.1）取出Li中的第1个项i

（1.2）ifTr的某个子节点Node是ithen

（1.2.1）Node.count=Node.count+1

（1.3）else

（1.3.1）创建Tr的子节点Node为i

（1.3.2）Node.count=1

（1.3.3）将Node加入项表链中（1.4）Insert-FP（Li-i,Node）算法描述第62页，课件共200页，创作于2023年2月63FP-growth算法算法：Search-FP算法（Tα，α）输入：（条件）FP树Tα，后缀模式α输出：频繁项集集合L_S（1）ifTα中只有一个分枝Pthen

（1.1）forP上的节点的每个组合β

（1.1.1）β=β∪α//产生频繁项集（1.1.2）L_S=L_S∪{β}（2）else

（2.1）forTα中的每个频繁项i

（2.1.1）γ={i}∪α//增长后缀模式（2.1.2）构造γ的条件模式基及其条件FP树Tγ

（2.1.3）Search-FP（Tγ,γ）算法描述第63页，课件共200页，创作于2023年2月64分析技术及模型

——聚类分析第64页，课件共200页，创作于2023年2月65将物理或抽象对象的集合分成相似的对象类的过程使得同一个簇中的对象之间具有较高的相似性，而不同簇中的对象具有较高的相异性是数据挖掘、模式识别等研究方向的重要研究内容之一，在识别数据的内在结构方面具有极其重要的作用广泛应用于模式识别、数据分析、图像处理和市场研究等领域，对生物学、心理学、考古学、地质学及地理学等研究也有重要作用主要介绍聚类概念、聚类过程、常用聚类算法聚类分析第65页，课件共200页，创作于2023年2月66Ｄ={o1,o2,……,on}表示一个对象集合oi表示第i个对象，i={1,2,……,n}Cx表示第x个簇，CxＤ，x=1，2，…，kSimilarity(oi,oj)表示对象oi与对象oj之间的相似度若各簇Cx是刚性聚类结果，则各Cx需满足如下条件：1）2）对于有3）聚类分析的形式描述第66页，课件共200页，创作于2023年2月67数据准备属性选择属性提取聚类结果评估聚类过程为聚类分析准备数据，包括属性值标准化从最初的属性中选择最有效的属性通过对所选择的属性进行转换形成新的更有代表性的属性度量对象间的相似性程度，执行聚类或分组

聚类分析的三要素是相似性测度、聚类准则和聚类算法第67页，课件共200页，创作于2023年2月68聚类分析中的数据类型聚类分析中常用的数据类型有：数据矩阵、相异度矩阵1）数据矩阵：对象在多维空间中通常表示为点（向量），其每一维表示为不同属性，这些属性描述出对象数据矩阵每行代表一个对象，每列代表对象的一个属性2）相异度矩阵：存储n个对象两两之间的近似性，d(i,j)是对象i和对象j之间相异性的量化表示第68页，课件共200页，创作于2023年2月69聚类分析三要素相似性测度、聚类准则和聚类算法相似性测度：衡量同簇对象的类似性和不同簇对象的差异性聚类准则：评价聚类结果的好坏聚类算法：用于找出使准则函数取极值的最好聚类结果实际上，确定了相似性测度和聚类准则后，聚类就变成了使准则函数取极值的优化问题了没有任何一种聚类算法可以普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构因此聚类算法有多种，不同的聚类算法使用不同的相似性度量和准则第69页，课件共200页，创作于2023年2月70对象之间的相似性根据描述对象的属性值评估，可以使用距离、密度、连通性或概念度量距离相似性度量：距离越近越相似，不同簇中任意两个对象间的距离都大于簇内任意两个对象之间的距离密度相似性度量：密度（单位区域内的对象数）越相近，相似性越高，簇是对象的稠密区域，被低密度的区域环绕连通性相似性度量：使用图的连通性度量相似性，簇定义为图的连通分支，即互相连通但不与组外对象连通的对象组概念相似性度量：共性（比如共享最近邻）越多越相似，簇定义为有某种共同性质的对象的集合相似性测度第70页，课件共200页，创作于2023年2月71主要的聚类算法大致可以分为：划分式聚类算法、基于密度的聚类算法、层次聚类算法、基于网格的聚类算法和基于模型的聚类算法聚类算法分类划分式聚类算法（partitioningmethod）预先指定聚类数目或聚类中心，通过反复迭代运算，逐步优化准则函数的值，当准则函数收敛时，得到最终聚类结果k均值算法、k中心点算法及它们的变种基于密度的聚类算法（density-basedmethod）通过数据密度来发现簇DBSCAN、OPTICS、DENCLUE第71页，课件共200页，创作于2023年2月72聚类算法分类基于网格的聚类算法（grid－basedmethod）将对象空间量化为有限数目的单元，形成网格结构，所有的聚类操作都在网格上进行，从而获得较快的处理速度STING、WaveCluster层次聚类算法（hierarchicalmethod）将数据对象组织成一棵聚类树，使用数据的联接规则，透过一种架构方式，反复将数据进行分裂或聚合，以形成一个层次序列的聚类问题解BIRCH、ROCK和Chameleon等第72页，课件共200页，创作于2023年2月73聚类算法分类基于模型的聚类算法（model-basedmethod）基于“数据根据潜在的混合概率分布生成”假设，为每个簇假定一个模型，并寻找数据对给定模型的最佳拟合这类算法通过构建反映数据点空间分布的密度函数来定位簇，能考虑“噪声”数据和离群点的影响，鲁棒性较好EM、COBWEB、SOM

第73页，课件共200页，创作于2023年2月74Ｋ均值聚类算法Ｋ均值聚类算法假定所有数据对象可分为k个簇，每个簇的中心用均值表示对象间的相似性用距离度量聚类的准则是误差平方和准则核心思想：首先选定k个初始聚类中心，根据最小距离原则将每个数据对象分配到某一簇中然后不断迭代计算各个簇的聚类中心并依新的聚类中心调整聚类情况，直至收敛（J值不再变化）第74页，课件共200页，创作于2023年2月75Ｋ均值聚类算法误差平方和准则若Nx是第Cx个簇中的对象数目，mx是这些对象的均值，J是所有簇的簇中各个对象与均值间的误差平方和之和对于不同的聚类，J的值不同使J值极小的聚类是误差平方和准则下的最优结果度量了用k个聚类中心m1,…,mk代表k个簇C1,,…,Ck时所产生的总的误差平方和第75页，课件共200页，创作于2023年2月76Ｋ均值聚类算法算法描述输入：数据对象集合D，簇数目k输出：k个簇的集合步骤：1.从D中随机选取k个不同的数据对象作为k个簇C1，…，Ck的中心m1，…，mk2.repeat

1）forD中每个数据对象o

a.寻找i，

b.将o分配给簇Ci

2）for每个簇Ci（i=1，…，k）计算

3）计算平方误差3.UntilJ不再发生变化计算新的聚类中心，|Ci|为当前簇中的对象数目第76页，课件共200页，创作于2023年2月77Ｋ均值聚类算法算法简单，计算复杂度是O(nkt)，其中n是对象的总数，k是簇的个数，t是迭代次数，通常，k<<n且t<<n能对大型数据集进行高效划分，但是不适合于发现非球形、密度或尺寸差别很大的聚类簇k的值需要用户事先确定，对噪声和离群数据敏感，因为噪声和离群数据虽然量少，但是能够对均值产生极大的影响k中心点聚类算法能够降低这种敏感性k中心点聚类不使用均值作为簇的代表点，而是在每个簇中选出一个实际的对象来代表该簇最好的代表点应该是簇的实际中心点，或是最靠近中心的对象算法特点第77页，课件共200页，创作于2023年2月78Ｋ均值聚类算法用k均值算法将如下11个数据对象聚类成2个簇：o1=(1，1)，o2=(1.2，1.2)，o3=(0.8，1.2)，o4=(0.9，0.7)，o5=(1.3，0.9)，o6=(1，1.4)，o7=(3，3)，o8=(3.1，2.8)，o9=(3.2，3.4)，o10=(2.7，3.3)，o11=(2.6，2.9)（1）第一次迭代：

1）选择o3(0.8，1.2)，o8(3.1，2.8)为簇C1，C2的中心，即m1=(0.8,1.2)，m2=(3.1,2.8)2）因为所以，将o1分配给簇C1第78页，课件共200页，创作于2023年2月79Ｋ均值聚类算法所有对象分配后，C1

和C2所包含的对象分别为：C1={o1，o2，o3，o4，o5，o6}，C2={o7，o8，o9，o10，o11}3）计算新的聚类中心、平方误差和J：（2）第二次迭代：第79页，课件共200页，创作于2023年2月80Ｋ均值聚类算法1）根据m1=(1.033,1.067)，m2=(2.92,3.08)重新对数据对象进行分配，结果为：C1={o1，o2，o3，o4，o5，o6}，C2={o7，o8，o9，o10，o11}2）新的聚类中心m1=(1.033,1.067)，m2=(2.92,3.08)，平方误差和J=1.023由于J的值没有发生变化，所以迭代停止。聚类结果为：C1={o1，o2，o3，o4，o5，o6}，C2={o7，o8，o9，o10，o11}第80页，课件共200页，创作于2023年2月81EM聚类算法EM（ExpectationMaximization，期望最大化）算法是k均值聚类算法的一种扩展核心思想：每个簇都用参数概率分布数学描述，整个数据是这些分布的混合。因此可以使用k个概率分布的有限混合密度模型对数据进行聚类，其中每个分布代表一簇问题是估计概率分布的参数，使得分布最好地拟合数据EM算法中，每个对象按照代表对象隶属概率的权重指派到每个簇新的均值基于加权的度量来计算，簇间没有严格的边界第81页，课件共200页，创作于2023年2月82EM聚类算法隶属概率及新均值计算对象oi隶属于簇Cj的概率：簇Cj的均值mj：服从均值为mj、方差为j的正态分布EM算法首先对混合模型的参数进行初始估计，然后重复执行E步和M步，直至收敛E步称为期望步，根据当前参数计算每个对象关于各个簇的隶属概率M步称为最大化步，使用E步计算的概率来更新参数估计第82页，课件共200页，创作于2023年2月83EM聚类算法算法描述输入：数据对象集合D，簇数目k输出：k个簇的参数步骤：1.对混合模型的参数作初始估计：从D中随机选取k个不同的数据对象作为k个簇C1，C2，…，Ck的中心m1，m2，…，mk，估计k个簇的方差1，2，…，k2.repeat1）E步：计算P(oiCj)，根据P(oiCj)将对象oi指派到簇Cj2）M步：利用E步计算的概率重新估计mj3.Until参数不再发生变化第83页，课件共200页，创作于2023年2月84EM聚类算法EM算法是一个迭代求精的算法计算复杂度为O(ndt)，n：对象数目，d：属性数目，t：迭代次数EM算法简单，容易实现，收敛也快，但是可能达不到全局最优算法特点假设有两个正态分布，它们具有相同的标准差2，均值分别为-4和4，并且每个分布以等概率选取。混合模型为：是混合模型的参数集，=（1，2），其中1=（-4，2），2=（4，2）。由该混合模型产生20000个数据点，用EM算法对它们聚类第84页，课件共200页，创作于2023年2月85EM聚类算法初始估计混合模型的参数，设m1=-2，m2=3这样，对于两个分布，初始参数1=（-2，2），2=（3，2）2.1）计算P(oiCj)所以设oi=0，则利用计算得：，

数据点0属于簇C1的可能性是属于簇C2的可能性的两倍第85页，课件共200页，创作于2023年2月86EM聚类算法2）计算了20000个点的簇隶属概率后，计算m1和m2的新的估计重复1）和2），直到m1和m2的估计不再改变或变化很小迭代m1m20-2.003.001-3.744.102-3.944.073-3.974.044-3.984.035-3.984.03EM算法用于20000个数据点集合的前几次迭代：第86页，课件共200页，创作于2023年2月87DBSCAN聚类算法DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise，具有噪声的基于密度的空间聚类应用）一种基于密度的聚类算法，将簇定义为密度相连的点的最大集合基本概念数据对象p的ε-邻域N(p)

以p为圆心，以ε为半径的圆形区域内的数据对象的集合，即：N(p)={q|qD∧d(p，q)ε}D:数据对象集合，d(p,q):对象p、q间的距离显然，如果qN(p)，则pN(q)第87页，课件共200页，创作于2023年2月88DBSCAN聚类算法基本概念核心对象p对象p的ε-邻域至少包含最小数目MinPts个对象直接密度可达对象p在对象q的ε-邻域内，而q是一个核心对象p是从q出发关于ε和MinPts直接密度可达的核心对象间的直接密度可达关系对称第88页，课件共200页，创作于2023年2月89DBSCAN聚类算法基本概念密度可达对象链p1=

q，p2，p3，pn=p中，pi+1从pi出发关于ε和MinPts直接密度可达对象p从对象q

出发关于ε和MinPts密度可达核心对象间的密度可达关系对称密度相连存在对象o，使对象p和q都是从o出发关于ε和MinPts密度可达对象p到q是关于ε和MinPts密度相连的密度相连关系对称第89页，课件共200页，创作于2023年2月90DBSCAN聚类算法基本概念基于密度的簇基于密度可达性的最大的密度相连对象的集合即簇C是满足如下条件的D的非空子集：1）连通性：对于任意的p，qC，有p与q是关于ε和MinPts密度相连的2）极大性：对于任意的p，q，如果pC，并且q是从p出发关于ε和MinPts密度可达的，则qCD中不包含在任何簇中的对象是噪声。即Noise={p|pDpCi，1ik}k是簇的数目第90页，课件共200页，创作于2023年2月91DBSCAN聚类算法算法思想首先，选取一个未标记类别的核心对象，并创建一个新簇然后，寻找所有从该核心对象出发关于ε和MinPts密度可达的对象，并标记为该簇重复这个过程，直至处理完所有对象，即没有未标记簇的核心对象算法描述输入：数据对象集合D，邻域半径ε，最小对象数目MinPts输出：关于ε和MinPts的所有簇第91页，课件共200页，创作于2023年2月92DBSCAN聚类算法算法描述步骤：1.初始化类别标记Cid；2.forD中的每个数据对象pifp是未标记类别的数据对象then1）ifp不是核心对象then将p标记为噪声

2）elsea.将p标记为Cidb.将所有从p出发关于ε和MinPts直接密度可达的标记为噪声的数据对象标记为Cidc.将所有从p出发关于ε和MinPts直接密度可达的未标记的数据对象标记为Cid，并放入队列Q中//寻找所有从p出发关于ε和MinPts密度可达的数据对象第92页，课件共200页，创作于2023年2月93DBSCAN聚类算法算法描述d.whileQ不空

i.从Q中取出队头数据对象oii.ifo是核心对象then

将所有从o出发关于ε和MinPts直接密度可达的标记为噪声的数据对象标记为Cid

将所有从o出发关于ε和MinPts直接密度可达的未标记的数据对象标记为Cid，并放入队列Q中

e.改变类别标记Cid

第93页，课件共200页，创作于2023年2月94DBSCAN聚类算法算法特点不使用索引时，DBSCAN的计算复杂度是O(n2)使用索引时，其计算复杂度为O(nlogn)n：数据集D中的对象数目能在具有噪声的数据中发现任意形状的簇，对噪声数据不敏感使用的参数ε和MinPts是两个全局参数，这种全局密度参数往往不能刻画高维数据内在的聚类结构，因为真实的高维数据集常常具有非常倾斜的分布ε和MinPts的值需要用户输入，比较困难第94页，课件共200页，创作于2023年2月95模糊聚类算法现实中的对象在分类问题上往往没有明确的界限，具有模糊性模糊聚类中，一个数据对象可能以不同的隶属度属于不同的簇模糊划分能够比非模糊划分提供更多的信息模糊聚类有多种方法：基于模糊等价关系的方法、基于目标函数的模糊聚类方法、基于模糊图论的方法……基于目标函数的模糊聚类方法：把聚类归结为一个带约束的非线性规划问题，通过优化求解获得数据集的模糊划分和聚类典型：模糊c-均值（fuzzyc-means,FCM）聚类算法第95页，课件共200页，创作于2023年2月96模糊c-均值聚类算法数据对象集X的c-模糊划分：给定p维空间Rp中的数据对象X={x1，x2,…,xn}，设，…，分别表示X上的c个模糊集，ij表示xj