本文共 4926 字,大约阅读时间需要 16 分钟。
假定作为超市的销售经理,你想更多地了解顾客的购物习惯,尤其是,你想知道“顾客可能会在一次购物同时购买哪些商品?”经常同时购买的商品可以摆放的近一些,以便进一步刺激这些商品同时销售。也可以将硬件和软件摆放在商店的两头,可能诱发买这些商品的顾客一路挑选其它的商品。
TID | 项集 |
1 | { 面包,牛奶} |
2 | { 面包,尿布,啤酒,鸡蛋} |
3 | { 牛奶,尿布,啤酒,可乐} |
4 | { 面包,牛奶,尿布,啤酒} |
5 | { 面包,牛奶,尿布,可乐} |
其中 TID为事务的标号,可以理解为顾客的一次购买行为,例如TID=1表示,某一次一位顾客同时购买了面包与牛奶。
项集是项的集合,包含k个项的集合称为k项集,例如{ 面包,牛奶}为2项集,{ 面包,尿布,啤酒,鸡蛋}为4项集。
例如:购买计啤酒的人趋向于同时购买尿布
啤酒=> 尿布[ support = 60% ; confidence = 100% ]
Support:支持度百分之60显示所有事务中有百分之60显示啤酒和尿布被同时购买。
confidence:置信度百分之100表明所有购买啤酒的顾客有百分之100同时购买了尿布。
规则的支持度和规则的置信度是规则度量的两种方式。
支持度:确定规则可以用于给定数据集的频繁程度,给定一个最小支持度阈值,若一个项集的支持度大于阈值,则可以把此项集叫做频繁项集。
置信度:确定B在包含A的事务中出现的频繁程度。
Support( A=> B ) = P ( A U B )
support(A U B ) support_count(A U B )
Confidence( A => B )=P(B|A)= —————————= ———————————
support( A ) support_count(A )
其中support_count是支持度计数,和支持度的区别在于,支持度是支持度计数和所有事务的比值,
即: support_count(A )
support(A ) = ———————————— ,其中U为全集。
support_count(U )
1.5 关联规则的产生方式
(1)在所有项集中找出满足最小支持度阈值的所有项集,这些项集称作频繁项集。
(2)从上一步找到的频繁项集中提取所有高置信度的规则,这些规则称作强规则。
1.6 查找频繁项集的原始方法
采用原始方法查找上面购物篮实例里的频繁项集:示例中所有的事务产生的项的集合为{面包、牛奶、尿布、啤酒、鸡蛋、可乐},设最小支持度阈值为60%。
对于1项集{面包},依次比较事务1至5,得出support({面包})=80%;
对于2项集{啤酒、尿布}依次比较事务1至5得出support({啤酒、尿布})= 60%;
...
此6项集包含 个1项集,个2项集,个3项集等,对于所有子集都采用以上方式去进行计算,然后我们找到所有的满足最小支持为60%阈值的项集。
1.7 原始方法查找频繁项集的缺点
(1)候选项集数目过大
上例中候选项集为++=2~6 - 1 =63,随着项的总数的增多,例如一家超市有一千种商品,则有2~1000 - 1 的候选项集,呈指数增长。
(2)比较次数过多
上例中每个项集都要和五个事务比较,随着事务数量的增大,计算次数会越来越多。
2 Apriori算法
2.1 先验定理
先验定理: 如果一个项集是频繁的,则它的所有的子集一定也是频繁的。
逆否,如果一个项集是非频繁的,则它的所有超集也一定是非频繁的。
2.2 Apriori算法
开创性地使用基于支持度的剪枝技术,系统地控制候选项集指数增长。
基于先验定理的剪枝技术,仅通过频繁k-1项集来产生候选k项集。
例如:上面实例,假若支持度阈值为60%,则支持度计数阈值5*0.6=3
1项集,可乐,鸡蛋不是频繁的,则它们的超集必定不是频繁的;
2项集{ 啤酒,面包}、{ 啤酒、牛奶}不是频繁的,则它们的超级也必定不是频繁的。
2.3 Apriori算法伪代码描述
产生候选k项集的几种方式
1、初始单遍扫描数据集,确定每个项的支持度。得到所有频繁1项集F1;
2、使用上一次迭代发现的频繁(k-1)项集,产生新的候选k项集;
3、再次扫描数据集,确定候选k项集的支持度;
4、删除不是频繁的候选k项集;
5、循环2-3步,当没有新的频繁项集产生,则算法结束。
问题:如何通过频繁的候选(k-1)项集,产生候选k项集?
1、蛮力法
先通过所有1项集产生所有的k项集,然后删除包含不频繁的(k-1)项集的k项集。
例:
频繁项集的格
用其它频繁项来产生候选k项集,然后候选剪枝掉非频繁3项集。
例:通过频繁2项集和频繁1项集来产生候选3项集
该方法存在的问题:
(1)在具体合并的时候,不同的项集合并可能产生相同的项集,例如{面包、尿布}和{牛奶}合并,与{面包、牛奶}和{尿布}合并会得到同样的{面包、尿布、牛奶},解决此问题的方法:确保每个频繁项集中的项都以字典序存储,每个频繁(k-1)项集x,只用字典序比x中所有的项都大的频繁项进行合并。例如,可以用{牛奶(milk)}来拓展{面包(bread)、尿布(diapers)},{面包、牛奶}不能用尿布拓展,因为m为首的单词在字典中的位置是在b和d后面。
假使上述单词用中文表示,{面包(mianbao)、尿布(niaobu)},{牛奶(niunai)},牛奶和尿布的首写字母一样,可以继续比较第二位都是i,再比较第三位u在a后面,以此类推,然后长度短放后面等等,即将集合通过某种方式进行序列化。
(2)尽管此方法优于蛮力法,但也同样产生许多不必要的候选k项集,然后需要剪枝进一步确定频繁k项集。
(1)通过合并两个候选k-1项集来产生候选k项集
合并规则:如果两个频繁k-1项集的前k-2项相同,则合并此两个候选k-1项集。
*注意,此合并方法在各向集都采用”字典序"存储的情况下使用较好。
(2)合并后产生候选k项集,然后通过剪枝方法产生频繁k项集
通过理解了上面的几个算法,知道了产生候选k项集的几种常用方式,然后通过支持度阈值来剪枝掉低于支持度阈值的项集,从而产生频繁项集,那么如何得到一个项集的支持度计数?
方法一:将候选项集依次与每个事务做比较,然后更新包含在事务中的候选项集的支持度计数。
缺点:当事务和候选项集的数目都很大的时候开销过大。
方法二:枚举每个事务所包含的所有项集,并且更新它们所对应的候选项集的支持度,那些不与候选项集的事务对应的事务项集的自己可以忽略。
问题:为什么方法二优于方法一?
解答:以超市购物为例,顾客同一单购买的东西一般不会特别多,但是超市每天的交易单数会特别庞大。一个事物产生的项集不会特别多。
在Apriori算法中可以将候选集划分为不同的桶,并存放在对应的Hash树中。在支持度计数期间,包含在事务中的项集也散列到相应的桶中。此种方法可以不必要将事务产生的项集与所有的候选项集进行比较,而只需要和桶内的候选项集比较,从而节约了时间。
例如: 上例中候选2项集通过字典序分到不同的桶中,然后通过遍历事务集来增加对应项的支持度计数。
一旦由数据库D中的事务找出频繁项集,就可以直接由它们产生强关联规则(强关联规则满足最小支持度和最小置信度)。
通过频繁项集产生强关联规则的步骤如下:
1、 对于每个频繁项集L,产生L的所有非空真子集。
2、 对于每个非空真子集S,如果置信度大于最小置信度,则输出规则“S=> (L – S);
由于规则由频繁项集产生,则规则一定满足最小支持度,只用计算规则的最小置信度即可。
示例:上面最终产生的频繁3项集为{ 面包、尿布、牛奶}
该频繁项集的非空子集为{ 面包},{ 尿布},{ 牛奶},{ 面包、尿布},{ 面包、牛奶},{ 尿布、牛奶}。
{ 面包}=> { 尿布、牛奶} confidence= 3 / 4 = 75%
{
尿布}=> { 面包、牛奶} confidence = 3 / 4 = 75%{
牛奶}=> { 面包、尿布} confidence = 3 / 4 = 75%{
面包、尿布}= > { 牛奶}confidence = 3 / 3 = 100%{
面包、牛奶}=> { 尿布}confidence = 3/3 = 100%{
尿布、牛奶}=> { 面包}confidence = 3/3 = 100%
Apriori算法在早期成功地处理了频繁项集产生的组合爆炸问题的算法之一。它通过使用先验定理对指数搜索空间进行剪枝,成功地处理了组合爆炸的问题。但是通过以上的讲解,我们可以知道该算法需要经常扫描数据集,对于每个事务的平均项集很大的数据集来说,由于每个事务项集的子集非常多,大大地降低了apriori算法的效率。
示例:
规则的提取由最后的结点e开始,按照与建树相反的顺序进行提取。(假定支持度计数为2)
以结点e为例:
1、收集包含e结点的所有路径,这些初始的路径称为前缀路径(prefixpath)。
2、如图所示的前缀路径,通过把与结点e相关联的支持度计数相加得到e的支持度计数。假定最小的支持度为2,因为{e}的支持度是3所以它是频繁项集。
3、由于{e}是频繁的,因此算法必须解决发现以de、ce、be和ae结尾的频繁项集的子问题。在解决这些子问题之前,必须先将前缀路径转换成条件fp树。除了用于发现以某特定后缀结尾的频繁项集之外,条件fp树的结果与fp树类似。
条件fp树通过以下步骤得到:
a、首先,必须更新前缀路径上的支持度计数。因为某些计数包含哪些不含项e的事务。例如图中最右边路径null->b:2->c:2->e:1,包含并不包含项e事务{b、c}。因此,必须将该前缀路径上的计数调整为1,以反映包含{b,c,e}的事务的实际个数。
b、删除e的结点,修剪前缀路径.删除这些结点是因为,沿这些前缀路径的支持度计数已经更新,以反映包含e的那些事务,并且以发现de、ce、be和ae结尾的频繁项集问题的子问题不再需要结点e信息。
c、更新沿前缀路径上的支持度计数后,某些项可能不是频繁的,删除那些不是频繁的项。
4、FP增长使用e的条件fp树来解决发现以de、ce、be和ae结尾的频繁项子问题。为了发现以de结尾的频繁项集,从项e的条件fp树来收集d的所有前缀路径。通过将与结点d相关联的频度计数求和,得到项集{d、e}的支持度计数。因为{d、e}支持度为2,是频繁的,保留。再构建{de}的条件FP树,该树只包含一个支持度等于最小支持度的项a,所以提取出{a、d、e}。用同样的方法去判断{c、e}、{b、e}、{a、e}。
提取结果如下:
后缀 | 频繁项集 |
e | {e},{ d,e},{ a,d,e},{ c,e},{ a,e} |
d | {d},{ c,d},{ b,c,d},{ b,d},{ a,b,d},{ a,d} |
c | {c},{ b,c},{ a,b,c},{ a,c} |
b | {b},{ a,b} |
a | {a} |
FP算法特点:
FP树是一种输入数据的压缩表示,它通过逐个读入事务,并把每个事务映射到FP树种的一条路径来
构造。由于不同的事务可能会有若干个相同的项,因此它们的路径可能部分重叠。路径相互重叠的
越多,使用FP树结构获得的压缩效果越好。如果FP树足够小,则能够存放在内存中,就可以直接从
这个内存中的结构提出频繁项集,而不必重复扫描存放在硬盘上的数据。