【免费】基于GPU异构计算的关联规则挖掘算法及增量式情况的研究和简单实现1

需积分: 0 129 浏览量 2022-08-08 19:17:44 上传评论收藏 420KB DOCX 举报

资源详情

资源评论

资源推荐

基于 GPU 异构计算的关联规则挖掘算法及增量式情况的研究和简单实现

本文将从以下方面进行阐述：

1. 关联规则问题描述

2. 关于关联规则挖掘算法 Apriori 的说明

3. 关于 FUP 增量式关联规则挖掘算法的说明

4. 关于在使用 CUDA 进行关联规则挖掘算法前数据的预处理

5. 使用字典树来产生候选项

6. 候选项集支持度计数的计算方法

7. 使用 GPU 计算支持度

8. 关于优化的一些简单的说明

9. 将上面谈到的计算支持度计数的思想运用到增量式的关联规则中

10. 性能比较

11. 缺陷总结

一、关联规则问题描述

购物篮分析是频繁项集挖掘的一个典型例子。该过程通过发现顾客放入他们“购

物篮”中的商品之间的关联，分析顾客的购物习惯，这种关联的发现可以帮助零售商

了解哪些商品频繁地被顾客同时购买，从而帮助他们指定更好的销售策略。

假设记录“购物篮”信息的数据库称为交易数据库，其中每一条记录代表一个交

易，包括唯一的交易标识（TID）和一个数据项的集合，如表 1-1 中所示。其中商品

ID 列表中，每一列中的一个数字代表一个单品唯一的 ID 值，如假设 ID 值 11 可以代

表牛奶，ID 值 13 可以代表面包。

表 1-1 销售事务数据库片段

Trans_ID（TID）

商品 ID 的列表

T100

11,13,18,116,…

T200

12,18,50,…

…

如果我们想象全域是商品中商品的集合，则每种商品有一个布尔变量，表示该商

品是否出现，则每个购物篮可以用一个布尔向量来表示。通过分析布尔向量，得到反

映商品频繁关联或同时购买的模式。这种模式可以用关联规则的形式表示。量化这种

规则的标准需要引入支持度和置信度这两个度量。它们分别反映所发现规则的有用性

和确定性。

关联规则的挖掘问题的形式化描述如下：设是项的集合。任

务相关的数据

是数据库事务的集合，其中每个事务是一个非空项集，使得。

每个事物有一个标识符，称作

TID

。项的集合称为项集（itemset）。设

是一个项集，

事务

包含

当且仅当。如果项集 A 中包括

个项，则称为

项集。关联规则

是形如的蕴含式，其中，，，，并且。规

则在事务集

中成立并且具有支持度

，

是

中包含（即集合

和

的

并或

和

二者）事务占全部事务的百分比，它的概率表示为

P( )

。如果

中包

含

的事务同时也包含

的事务的百分比

，则规则在事务集

中具有的置信

度

，它是条件概率

P(B|A)

。

support( ) = P( )

(1-1)

confidence( ) = P(B | A)

(1-2)

支持度和置信度两个阈值是描述关联规则的两个重要概念，支持度反映的是关联

规则在数据库中的重要性，表示规则出现的频度；置信度衡量关联规则的可信程度，

表示规则的强度。

项集的出现频度是包含项集的事务数，简称为项集的频度、支持度计数或技数。

（1-1）式定义的项集支持度有时称为相对支持度，而出现频度称为绝对支持度。同时

满足最小支持度阈值（min_sup）和最小置信度阈值的规则称强规则（min_conf）。

最小支持度表示项集在统计意义上的最低重要性，最小置信度表示规则的最低可靠性。

如果项集的出现频度大于或者等于最小支持度阈值 min_sup 与 D 中事务总的乘积，

则成项集满足最小支持度。如果一个项集 A 满足最小支持度（A 的支持度大于等于

min_sup），则称它为频繁项集。频繁 k-项集的集合通常记作 L

。

由（1-2）式，有

confidence( ) = P(B | A) = =

(1-3)

（1-3）式表明规则 A=>B 的置信度容易从 A 和 A∪B 的支持度计数推出。也就是

说，一旦得到 A，B 和 A∪B 的支持度计数，则可导出对应的关联规则 A=>B 和 B=>A，

并检查它们是否是强规则。因此挖掘关联规则的问题可以归结为挖掘频繁项集。

关联规则的挖掘是一个两步的过程：第一步利用候选项集找出所有的频繁项集，

第二步由频繁项集产生强关联规则。步骤二操作开销远低于第一步，因此关联挖掘算

法规则的总体性能由第一步决定。

二、关于关联规则挖掘算法 Apriori 的说明：

Apriori 算法是 Agrawal 和 R.Srikant 于 1994 年提出的，为布尔关联规则挖掘频繁

项集的原创性算法。算法使用频繁项集性质的先验知识，所以称为 Apriori 算法。

Apriori 算法在数据挖掘和机器学习领域被广泛的应用。算法大致思想如下：首先扫描

数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁 1-项集的集合，

该集合记作 L

。之后使用 L

找出频繁 2-项集的集合 L

，使用 L

找出 L

，依次类推，

直到不能再找出频繁 k-项集。找出每一个 L

需要一次数据库的完整扫描。

利用先验性质（频繁项集的所有非空子集也一定是频繁的。即如果一个集合不能

通过最小支持度阈值测试，则它的所有超集也不能通过最小支持度阈值测试）来提高

频繁项集逐层产生的效率。通过 L

k-1

找出 L

，其中主要包括连接步和剪枝步两个步骤。

连接步：通过将 Lk-1 与自身连接产生候选 k-项集的集合 C

。设

和

是项集

k-1

中的项集

，l

[

]表示

的第

项。Apriori 算法中假定事务或者项集中的项按字典序排序。

对于（k-1）项集

，这意味着

[1]<

[2]<…<

[k-1]。执行连接操作，其中

k-1

的元素

是可连接的，如果他们前（k-2）个项相同。即，

k-1

的元素

和

是可连接的，如果

（

[1]=

[1]）∧（

[2]=

[2]）∧…∧（

[k-2]=

[k-2]）∧（

[k-1]<

[k-1]）。

和

连接的结果项集是{

[1]，

[2]，…，

[k-2]，

[k-1]，

[k-1]}。

剪枝步：C

是 L

的超集，即它的成员可以是频繁的也可能是不频繁的，但所有的

频繁 k-项集都包含在 C

中。通过先验性质来压缩 C

。因为任何非频繁的（k-1）项集

都不是频繁 k 项集的子集。所以，如果一个候选 k-项集的（k-1）项子集不在 Lk-1 中，

则该候选项不可能是频繁的，从而可以将其从 C

中删除。

Apriori 算法是一种广度优先算法，需要对事务数据库进行多次扫描来发现所有的

频繁项集，并且一次扫描只能解决同一长度为 k 的所有项集。

三、关于 FUP 增量式关联规则挖掘算法的说明

Apriori 算法是在事务数据库中数据不变的前提下进行的，当数据增加时，若使用

Apriori 算法则会导致上一次生成的频繁项集不再有用，而重新执行 Apriori 算法的时间

开销太大，增量式关联规则挖掘算法用于这种情况的数据挖掘。FUP 算法的基本思想

很简单，主要描述如下：

设原事务数据库的数据集为 D，新增的数据集为 d，则变化后的事务数据库为

（D+d）。设 L(D)为使用 Apriori 算法对数据集 D 进行挖掘得到的全部频繁项集。

1) 利用 Apriori 算法生成新事物数据集 d 的频繁项集 L(d)，对 L(D)和 L(d)进行比

较，找出公共相同的部分。则相同部分的频繁项集一定属于更新后的事务集（D+d）

的频繁项集。

2) 设某一项集为 t，若 t 属于 L(d)，但不属于 L(D)，则扫描 D 得到 t 在 D 中的支

持度计数 Sup

，再根据 d 中已经得出的 t 的支持度 Sup

，求出 t 在（D+d）中的支持

度 Sup

+d，如果 Sup

D+d

≥min_sup，则将 t 放入到变化后的数据集（D+d）中，否则

t 将不是频繁项集。

3) 若 t 属于 L(D)，但不属于 L(d)，则扫描 d 得到 t 在 d 中的支持度计数 Sup

，再

根据 D 中已经得出的 t 的支持度 Sup

，求出 t 在（D+d）中的支持度 Sup

D+d

，如果

Sup

D+d

≥min_sup，则将 t 放入到变化后的数据集（D+d）中，否则 t 将不是频繁项集。

四、关于在使用 CUDA 进行关联规则挖掘算法前数据的预处理

剩余10页未读，继续阅读

评论收藏

内容反馈

kdbshi

粉丝: 55
资源: 300

基于GPU异构计算的关联规则挖掘算法及增量式情况的研究和简单实现1

评论0

最新资源

基于GPU异构计算的关联规则挖掘算法及增量式情况的研究和简单实现1

评论0

论文研究-基于GPU的并行关联规则挖掘算法的设计与实现 .pdf

基于关联规则挖掘算法的分析型CRM的设计与实现

fim_gpu:“加速图形处理单元上的频繁项集挖掘”一文中的GPU关联规则挖掘算法的实现，请CITE

C++简单实现关联规则挖掘中Apriori算法

基于关联规则挖掘算法的用电负荷能效研究

基于CPU GPU异构计算编程研究.pdf

基于GPU的复杂网络社区挖掘算法并行计算.pdf

基于GPU并行计算的图像去噪研究.pdf

一种基于GPU异构计算的混合编程模型1

大数据-算法-蚁群算法在加权关联规则挖掘中的研究与实现.pdf

论文研究-基于逻辑运算的关联规则挖掘算法 .pdf

论文研究-基于AprioriTid的关联规则增量式更新算法 .pdf

论文研究-基于二进制的关联规则挖掘算法.pdf

论文研究-基于矩阵的增量式关联规则挖掘算法.pdf

行业分类-设备装置-基于GPU异构计算平台的字符串匹配方法及系统.zip

论文研究-基于GPU的复杂网络社区挖掘算法并行计算.pdf

基于GPU计算的并行PLS算法研究与实现.pdf

基于负载均衡的CPU-GPU异构计算平台任务调度策略.pdf

基于GPU通用计算的并行算法和计算框架的实现.pdf

论文研究-一种基于Can树的分布式关联规则增量挖掘算法 .pdf

基于CPU GPU异构计算的多聚焦图像融合.pdf

基于GPU并行计算的星载SAR影像数据高效重采样算法研究.pdf

CPU GPU异构并行的矩阵转置算法研究.pdf

论文研究-基于GPU的并行协同过滤算法.pdf

基于GPU通用计算的深度学习模型性能分析.pdf

基于GPU的AES算法实现

论文研究-基于GPU的力导引图绘制算法加速 .pdf

一种基于CPU-GPU异构计算的混合编程模型.pdf

论文研究-基于GPU的单幅图像去雾的实现及优化.pdf

最新资源