文档介绍:第7章 数据挖掘基本算法
第七章 数据挖掘基本算法
数据挖掘基本分析方法
1
关联分析
2
序列模式分析
3
分类分析
4
东北财经大学电子商务学院
聚类分析
(1)单层的关联规则:所有的变量仅涉及单一层次的项或属性。
(2)多层的关联规则:变量涉及不同抽象层次的项或属性。
4)根据所挖掘的模式类型分类
(1)频繁项集挖掘:从事务或关系数据集挖掘频繁项集(项的集合)。
(2)序列模式挖掘:从序列数据集中搜索频繁子序列,其中序列记录了事件的次序。
关联分析
(1)发现所有的事务支持度大于最小支持度的项集。
(2)产生强关联规则
在找到了事务数据库中的所有频繁项集后,利用这些频繁项集可以产生关联规则,产生关联规则的步骤如下:
①对于每个频繁项集L,产生L的所有非空子集。
②对于L的每个非空子集m,如果support(L)/support(m)≥min_conf,则输出规则“m (L-m)”。
例如,在上例中产生的频繁项集L={A,B,E},L的非空子集有{A,B}、{A,E}、{B,E}、{A}、{B}和{E},则运用上述产生关联规则的方法可以得到以下关联规则:
A B E confidence=(2/9)/(4/9)=
A E B confidence=(2/9)/(2/9)=1
B E A confidence=(2/9)/(2/9)=1
A B E confidence=(2/9)/(6/9)=
B A E confidence=(2/9)/(7/9)=
E A B confidence=(2/9)/(2/9)=1
Apriori算法
关联分析
3)Apriori算法中存在的两个问题
由以上的分析可以看出,在许多情况下,Apriori算法大幅度地压缩了侯选项集的大小,并且导致很好的性能。但该算法中存在的两个问题,在有些情况下不能忽视:
(1)该算法在计算的过程中需要产生大量的候选项集。
(2)该算法需要对数据库进行多次扫描,并通过模式匹配检查候选项集。
Apriori算法
关联分析
Apriori算法的几种优化方法
为了减小Apriori算法中存在的问题所带来的影响,提高Apriori算法的执行性能,许多学者提出了一些优化的算法。通常把这些在Apriori基础上优化的算法称为类Apriori算法。
1)Apriori算法几种典型的改进方法
(1)基于散列的优化方法(散列项集到对应的桶中)
(2)基于事务压缩的优化方法(压缩未来迭代扫描的事务数)
(3)基于划分的优化方法(为寻找候选项集划分数据)
(4)基于抽样的优化方法(对给定数据的子集挖掘)
(5)基于动态项集计数的优化方法(在扫描的不同点添加候选项集)
2)频繁模式增长
关联分析
3)关联分析的应用
关联分析的研究近年来发展迅速,市场前景十分广阔。近年来随着数据库和网络技术的广泛应用,加上使用先进的自动数据生成和采集工具,人们所拥有的数据量急剧增加,使关联分析在市场营销、零售等行业已得到了比较广泛的应用。
Apriori算法的几种优化方法
关联分析
4)关联分析的发展趋势
Apriori算法的几种优化方法
的交互性
1. 关联规则的兴趣度
序列模式分析
给定一个序列集,每一个序列由项集构成,然后给定由用户确定的最小支持度阈值,序列模式挖掘就是发现所有出现频率不小于给定的最小支持度的频繁子序列。
定义4
定义3
定义2
定义1
项集:各个项(item)组成的集合。集合I={il,i2,...,im},其中每个ik(1≤k≤m)是一个项。
序