现在的位置: 首页 > 综合 > 正文

数据挖掘之频繁项集分析

2013年04月30日 ⁄ 综合 ⁄ 共 2610字 ⁄ 字号 评论关闭
文章目录

频繁项集最经典和常用的应用就是超市的购物篮分析。每个购物篮里有很多商品,每个商品都是一项元素,每个购物篮都是一个集合,所有购物篮就形成了一个系列集合。

分析哪些商品经常一起频繁出现在购物篮内,即找到频繁项集,然后,再分析其他商品与频繁项集的关系,即关联规则。

1. 什么是频繁项?什么是频繁项集?与相似性分析有什么差别? 有什么应用?

频繁项:在多个集合中,频繁出现的元素/项,就是频繁项

频繁项集:有一系列集合,这些集合有些相同的元素,集合中同时出现频率高的元素形成一个子集,满足一定阈值条件,就是频繁项集。

极大频繁项集:元素个数最多的频繁项集合,即其任何超集都是非频繁项集。

k项集:k项元素组成的一个集合

相似性分析,研究的对象是集合之间的相似性关系。而频繁项集分析,研究的集合间重复性高的元素子集。

频繁项集的应用:真实超市购物篮的分析,文档或网页的关联程序分析,文档的抄袭分析,生物标志物(疾病与某人生物生理信息的关系)

超市购物篮的分析,主要是针对实体销售商,而不是在线零售商,这是因为实体销售可以找点频繁项集合后,可以采取对一种频繁项商品促销,而抬高相关的频繁项其他商品的价格来获利,因为客户一般不会去另外一家店购买其他的商品。而这种策略在在线销售时,会忽略“长尾”客户的需求。对于实体销售,商品的数量和空间资源有限,所以只能针对一些畅销商品进行关注和指定策略。而对于在线销售,没有资源限制,而且客户切换商户很方便,所以实体店销售的策略不合适在线销售,在线销售更应该关注相似客户群的分析,虽然他们的购买的产品不是最畅销、频繁的,但对客户群的偏好分析,可以很容易做到对每个客户进行定制化广告推荐,所以,相似性分析对在线销售更为重要。

2. 频繁项集分析有哪些指标?有什么意义?

1)支持度: 包含频繁项集F的集合的数目

2)可信度:频繁项F与某项j的并集 (即F U {j})的支持度 与 频繁项集F的支持度的比值,

3)兴趣度:F U {j} 可信度 与 包含{j}的集合比率之间的差值。若兴趣度很高,则 频繁项集F会促进 j 的存在, 若兴趣度为负值,且频繁项集会抑制 j 的存在;若兴趣度为0,则频繁项集对 j 无太大影响。

频繁项集 与 某项 j 的关系就是 关联规则。

3. 频繁项对在内存中的存放方式有哪些?频繁相对{i, j}

1)三角阵存放方式:即采用一个数组来存储这个三角阵中的元素,它可以节省二维数组一半的空间

2)三元组方式{i, j, c}:当频繁项对的数目小于C(n, 2)的数目的1/3时,三元组的方式相对于三角阵比较有优势。

4. Aprior算法

是一种筛选频繁项集的优化算法。

频繁项集两个定理:

1)频繁项子集定理:频繁项集的子集都是频繁项集,而非频繁项的超集都是非频繁项集。

2)频繁项集的合并/连接定理:由k-1项集,向k项集进行合并。当两个k-1项集,拥有k-2个相同元素时,才能合并成k项集。

Aprior算法是采取逐步合并的方式,求取频繁k项集,并且在合并之前,要过滤掉非频繁项集。流程类似如下:

原始数据 --> 一级构建 --> 一级过滤 --> 二级构建 --> 二级筛选 --> 三级......

第k级会生成 k项集 和 过滤掉非频繁项集,保留下k项频繁项集。

每一级的构建都会引起数据量的增加,而每一级的过滤后,会大大减少数据量,便于下一级的运算。

逐步过滤和合并,直至生成极少数量的频繁项集,或者极大频繁项集.

Aprior有点类似广度优先的算法。

5. PCY算法

当频繁项对的数量比较大时,内存放不下,而这时对频繁项对进行计数时,可能会产生内存抖动,即内存页面频繁换入换出,因为不同的频繁项对计数器可能放在不同的页面上。

对Aprior进行改进。

在第一步扫描时,为频繁项对 创建一张hash表,hash表只是统计 hash到本桶的项对的个数。第二步,统计哪些是频繁桶,并对桶内的两个频繁项进行计数处理。这样,每个频繁桶内代表的频繁项集比较少,这样,计算更大频繁项集的计算量就大大降低了。

6. 多hash算法

PCY的形变算法,采用多个hash表和hash函数,只要桶的平均计数不小于阈值,分频繁桶的数目任然比较多。这样,一个非频繁对同时hash到两个hash表的频繁桶内的概率就更低。减少了第二遍扫描的运算量。

7. 随机化算法

前提: 当数据量非常大,整个购物篮数据无法放入内存,这时,进行统计会有一定困难

解决方法:对购物篮进行随机抽样,只要样本数据足够大,还是能够提取出逼近真实情况的频繁项集的。

由于是抽样,涉及概率p,所以频繁项支持度的阈值s也需要降低,但是由于概率的乘法定理,抽样的频繁项集肯定是小于实际的数目,所以,需要降低阈值,可以将新的阈值设置的更小点,如0.9*p*s。

抽样带来的新问题: 伪正例(非频繁项集被统计成频繁项集)、伪反例(频繁项集没有提取出来)。伪正例可以通过后续的处理,排除掉,但是无法消除伪反例的情况。

8. SON算法

对随机抽样的算法进行改进。

将所有购物篮划分成相对比较小的小组,这样每个小组都能放进内存进行处理,每个小组内的项进行统计。处理完所有小组,然后,统计项对的频率,找出频繁项集。这个算法比较适合map-reduce的处理方式。

在统计每个小组的频繁项集时,其阈值仍然是需要降低的,类似于随机抽样算法。

9. Toivonen 算法

在给给定足够内存的情况下:

刚开始,类似于随机抽样算法,对购物篮抽样,降低阈值,找出频繁项集,除此之外,还要检测反例边界,反例边界的构成:非频繁集,但去掉任何一个元素就是频繁集。

在完整的数据集中,对反例边界上的项集进行检测,若这个反例边界的项集 没伪反例,即在完整数据集中,仍然是非频繁项集,则接收此次抽样结果;若找到了伪反例,那么就再次抽样,直至成功。

10. 数据流中的频繁项集分析

面临的问题:

1)数据流可能速率很高,无法存储整个流进行分析

2)随时间的推移,频繁项集也会发生变化

解决方法:

1) 抽样技术

2)窗口的衰减模型

抽样:

定期收集数据流,存为文件后,再分析。分析期间,不再将数据流放入正在分析的文件。不过,可以存储为另一个文件,供下次分析。

窗口衰减模型:

可以将倒数第i个出现的购物篮赋予(1-c)^i 的权值。这样就形成了流中的一个衰减窗口。

当某个项集出现在当前购物篮中,并且其所有真子集已经开始计数,那么此时开始对此项集开始计数。这样需要计数的项集的规模就不会太大。

由于窗口不断衰减,将所有计数值都乘以(1-c),并去掉计数低于1/2的项集。

抱歉!评论已关闭.