【数据挖掘】关联规则之Eclat算法
发布日期:2021-06-23 04:28:53 浏览次数:3 分类:技术文章

本文共 1186 字,大约阅读时间需要 3 分钟。

Eclat算法


        前面介绍过的Apriori算法和FP-growth算法都是从TID-项集格式(即{TID:itemset})的事务集中挖掘频繁模式,其中TID是事务标识符,而itemset是事务TID中购买的商品。这种数据格式称为水平数据格式。或者,数据也可以用项-TID集格式(即{item:TID_set})表示,其中item是项的名称,而TIDb_set是包含item的事务的标识符集合。这种格式称为垂直数据格式

        下面介绍使用垂直数据格式有效挖掘频繁项集,它是等价类变换(Equivalence CLAss Transformation,Eclat)算法的要点。

        先举例说明使用垂直数据格式挖掘频繁项集。

        考虑表1的事务数据库D的水平数据格式。扫描一次该数据集就可以把它转换成表2所示的垂直数据格式。

                                                                      表1:事务数据库D的水平数据格式

                                                                  表2: 表1中事务数据库D的垂直数据格式

        通过取每对频繁项的TID集的交,可以在该数据集上进行挖掘。设最小支持度计数为2。由于表2的每个项都是频繁的,因此总共进行10次交运算,导致8个非空2项集,如表3所示。注意,项集{I1,I4}和{I3,I5}都只包含一个事务,因此它们都不属于频繁2项集的集合。

                                                                           表3:垂直数据格式的2项集

        根据先验性质,一个给定的3项集是候选3项集,仅当它的每一个2项集子集都是频繁的。这里候选产生过程将仅产生两个3项集:{I1,I2,I3},{I1,I2,I5}。通过取这些候选3项集任意对应2项集的TID集的交,得到表4,其中只有两个频繁3项集:{I1,I2,I3:2}和{I1,I2,I5:2}

                                                                                 表4:垂直数据格式的3项集

       Eclat算法最大的特点便是倒排思想,也就是生成一个统计每一个项在哪些事务中出现过的倒排表,表中的每一行由项和它对应的TID集组成,TID集即包含此项目的所有事务的集合。

Eclat算法挖掘频繁项集的过程如下:

  1. 通过扫描一次数据集,把水平格式的数据转换成垂直格式;
  2. 项集的支持度计数简单地等于项集的TID集的长度;
  3. 从k=1开始,可以根据先验性质,使用频繁k项集来构造候选(k+1)项集;
  4. 通过取频繁k项集的TID集的交,计算对应的(k+1)项集的TID集。
  5. 重复该过程,每次k增加1,直到不能再找到频繁项集或候选项集。

Eclat算法产生候选项集的理论基础是:频繁K-项集可以通过或运算生成候选的K+1-项集,频繁K-项集中的项是按照字典序排列,并且进行或运算的频繁K-项集的前K-1个项是完全相同的。

Eclat算法的优缺点:优点:在产生候选(k+1)项集时利用先验性质,而且不需要扫描数据库来确定(k+1)项集的支持度(k>=1),这是因为每个k项集的TID集携带了计算支持度的完整信息。缺点是TID集可能很长,需要大量的内存空间,长集合的交运算还需要大量的计算时间。

转载地址:https://xinzhe.blog.csdn.net/article/details/86632408 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:数据结构与算法——堆的应用
下一篇:我的编程故事

发表评论

最新留言

不错!
[***.144.177.141]2024年03月12日 15时41分39秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java图片延迟加载_jQuery实现图片延迟加载 2019-04-21
java开发加入购物车功能_java web开发——购物车功能实现 2019-04-21
Java虚拟机不能满足_深入理解Java虚拟机--读书笔记1/3 2019-04-21
python 协程 asyncio_python – asyncio.as_completed是否会产生期货或协同程序? 2019-04-21
java设定xml文件的encoding_配置web-xml解决中文乱码问题,及各种乱码问题集结 2019-04-21
hanlp java api_java分词工具hanlp介绍 2019-04-21
nginx php 源码安装,Nginx1.12.2加php7.2.0的编译安装 2019-04-21
php 删除字节,php – 删除无效/不完整的多字节字符 2019-04-21
php 实现版本号对比,如何在PHP中实现比较版本号 2019-04-21
php sql 给数据库追加内容,php如何向数据库中的某串数据后追加内容【急】 2019-04-21
php微信小程序获取用户信息,微信小程序授权获取用户详细信息openid的实例详解... 2019-04-21
Java三元运算和if,Java三元运算符与<JDK8兼容性中的if / else 2019-04-21
graphql-php enum,php – 如何在不写长查询的情况下查询所有的GraphQL类型字段? 2019-04-21
php date 函数用法,php中date()日期时间函数使用方法 2019-04-21
php除法获取整数和余数,PHP除法取整和取余数 2019-04-21
java迷宫路径,Java中的迷宫路径查找器 2019-04-21
php substr cnblog,php中substr用法示例 2019-04-21
php链接怎么截取,PHP 截取网页中的固定种子链接 2019-04-21
iis运行不起来php报500,解决IIS上安装thinkphp6运行报500错误 2019-04-21
php ajax上传图片过大500错误,javascript – JQuery AJAX文件上传错误500 2019-04-21