积分商城

最新搜索： ispLEVER ESAM sonar STM8S003 BRIGHTEK 电解电容封装库
您现在的位置是：首页 > 技术资料 > 基于差集的高效用项集挖掘方法
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

基于差集的高效用项集挖掘方法

更新时间：2019-12-24 13:13:03 大小：1M 上传用户：守着阳光1985查看TA发布的资源 标签：关联规则高效用项集 下载积分：1分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

高效用项集挖掘已成为关联规则中的一个热点研究问题.一些基于垂直结构的算法已用来挖掘高效用项集,此类算法的主要优点是将项集的事务和效用信息存储到效用列表中.在求一个项集的超集所在事务可以通过对它的子集进行一次交集运算得到.这种算法在稀疏数据集中非常的有效.但在稠密数据集中存在一个问题,即列表中存储的事务太多,在计算用于剪枝的效用上界时,需要耗费大量的存储空间,同时也影响运行速度.并且在现有的算法中,缺乏针对稠密数据集的高效用项集挖掘算法,往往需要设置很高的最小效用阈值,影响算法的运行效率.针对此问题,提出一个新的算法D-HUI(mining High Utility Itemsets using Diffsets)以及一个新的数据结构—项集列表,首次在高效用项集挖掘中引入差集的概念.利用事务的差集求项集的效用上界,减少计算量以及存储空间,从而提高算法的运行效率.实验结果表明,提出的算法在稠密数据集中,执行速度更快,内存消耗更少.


部分文件列表

文件名 大小
基于差集的高效用项集挖掘方法.pdf 1M

【关注视频号领20积分】   【关注公众号立即送20积分】

部分页面预览

（完整内容请下载后查看）
8
Vol． 46 No． 8  
Aug． 2018  
第
期
电
子
学
报
2018  
8
ACTA ELECTRONICA SINICA  
年
月
基于差集的高效用项集挖掘方法  
1
2
2
， ，  
黄 坤 吴玉佳 李 晶  
( 1．  
，
中国舰船研究设计中心 湖北武汉  
430064; 2．  
，
武汉大学计算机学院 湖北武汉  
430072)  
:
．
高效用项集挖掘已成为关联规则中的一个热点研究问题 一些基于垂直结构的算法已用来挖掘高效用  
摘
要
， ．  
项集 此类算法的主要优点是将项集的事务和效用信息存储到效用列表中 在求一个项集的超集所在事务可以通过对  
． ． ，  
它的子集进行一次交集运算得到 这种算法在稀疏数据集中非常的有效 但在稠密数据集中存在一个问题 即列表中  
， ， ， ．  
存储的事务太多 在计算用于剪枝的效用上界时 需要耗费大量的存储空间 同时也影响运行速度 并且在现有的算法  
， ， ， ．  
中 缺乏针对稠密数据集的高效用项集挖掘算法 往往需要设置很高的最小效用阈值 影响算法的运行效率 针对此问  
，
题 提出一个新的算法  
D-HUI( mining High Utility Itemsets using Diffsets)  
— ，  
以及一个新的数据结构 项集列表 首次在高  
． ， ，  
效用项集挖掘中引入差集的概念 利用事务的差集求项集的效用上界 减少计算量以及存储空间 从而提高算法的运  
． ， ， ，  
行效率 实验结果表明 提出的算法在稠密数据集中 执行速度更快 内存消耗更少  
．
:
;
;
;
;
关键词  
中图分类号  
URL: http: / /www． ejournal． org． cn  
关联规则 高效用项集 稠密数据集 垂直结构 差集  
:
TP311  
:
A
:
文章编号  
0372-2112 ( 2018) 08-1804-11  
文献标识码  
DOI: 10． 3969 /j． issn． 0372-2112． 2018． 08． 002  
电子学报  
Mining High Utility Itemsets Using Diffsets  
1
2
2
HUANG Kun ，WU Yu-jia ，LI Jing  
( 1． China Ship Development and Design Center，Wuhan，Hubei 430072，China;  
2． School of Computer，Wuhan University，Wuhan，Hubei 430072，China)  
Abstract: High utility itemsets mining ( HUIM) has become an emerging topic in association rules． Some algorithms  
based on vertical data structure have been used for mining high utility itemsets( HUIs) ，and the main advantage of the algo-  
rithms are to maintain transaction and utility information of itemsets in some utility lists( ULs) ． The transactions of superset  
of an itemsets can be calculated by its subset doing an intersection． These algorithms are very effective in sparse datasets．  
However，in the dense datasets，a problem is that: too many transactions maintained in ULs，not only required a lot of memo-  
ry space，but also affected the runtime when computing the upper bound of utility in order to prune search space． Few of ex-  
isting HUIM algorithm focused on dense datasets and it often need to set a high minimum threshold utility which affect the  
running efficiency of the algorithm． To solve this problem，propose a new algorithm D-HUI( mining High Utility Itemsets u-  
sing Diffsets) and a new data structure，namely Itemset Lists ( ILs) ． Introduce the concept of diffsets in the HUIM． Calculate  
upper bound of utility by using diffsets of transaction for pruning search space． The runtime and memory consumption are re-  
duced，and the running efficiency of the algorithm is improved． Experimental results show that the proposed algorithm in the  
dense datasets outperforms state-of-the-art algorithms in terms of both running time and memory consumption．  
Key words: association rules; high utility itemsets; dense datasets; vertical structure; diffsets  
、 ． ，  
也需要考虑此项出现的次数 权重等因素 因此 发现高  
1
引言  
( High Utility Itemsets，HUIs)  
效用项集  
掘领域中的一个研究热点问题之一  
迅速成为数据挖  
．
数据挖掘中的一个重要任务是关联分析 关联分  
．
［1 ～ 4］  
．
，
然而 在频繁  
析中最主要的步骤是频繁项集挖掘  
，
从另一个角度 频繁项集挖掘可以看成是高效用  
［5，6］  
，
项集挖掘的框架中  
没有考虑项在事务中的数量以  
．
项集挖掘的一种特殊情况 如果不考虑项的效用值的  
( 、 、 ) ．  
及项的重要性 如单位利润 价格 权重等 然而在一  
，
具体大小而只考虑项在事务中出现或不出现 或者设  
，
些实际应用中 有时不仅仅需要考虑项是否频繁出现  
，
1，  
置效用值为 高效用项集挖掘就等同于频繁项集挖  
: 2016-11-26;  
: 2017-06-30; :  
责任编辑 梅志强  
收稿日期  
修回日期  
:
基金项目 国家自然科学基金  
( No． 61303046)  
1805  
8
:
坤 基于差集的高效用项集挖掘方法  
第
期
黄
［14］  
． ， ，  
掘 通常情况下 因为附加条件较少 频繁项集挖掘比高  
． Philippe  
HUI-Miner  
FHM  
的基础上提出了  
项集  
等
在
， ，  
效用项集挖掘的效率更高 但是缺点也较为明显 即无  
，
算法 增加了一个新的策略  
EUCP，  
用于减少连接操作的  
［15］  
，
法扩展到更多的应用领域 因为很多应用领域是需要  
． Krishnamoorthy  
HUP-Miner ，  
算 法 同  
数量  
等 提 出 了  
、
考虑项的出现次数 权重等因素  
．
HUI-Miner  
， ，  
一样 这也是一种基于垂直结构的算法 此算  
，
所以 挖掘  
HUIs  
．
并不是一个简单的任务 相对于频  
，
法应用两个新的剪枝策略 称为划分效用剪枝和前向效  
， ． ，  
繁项集挖掘 它常常更加困难 在频繁项集挖掘中 多数  
，
HUI-Miner．  
用剪枝 算法在效率上略胜于  
由于不产生任何候选项集 在许多数据集上 基于  
UP-Growth  
， ，  
算法使用了向下闭性质 即如果一个项集是频繁的 它  
，
，
， ，  
的超集也都是频繁的 反之 如果一个项集是非频繁的  
，
垂直结构的算法性能都优于  
等基于树结构  
［1，2］  
．
则它的超集都是非频繁的  
利用这个性质对搜索空  
． ，  
的算法 但是 这些基于垂直的算法不仅需要存储项集  
， ．  
间进行剪枝 能大大减少计算量并降低内存消耗 然而  
，
，
的事务和效用信息 也需要存储用于对搜索空间进行  
．
这个性质在高效用项集挖掘中却不能直接使用 因为  
，
，
剪枝的额外剩余效用信息 这也降低了算法性能并占  
，
如果一个项集是低效用项集 不能断定它的超集是否  
．
用了更多的内存资源 尤其是在稠密数据集的情况下  
，
， ，  
为低效用项集 或者一个项集是高效用项集 也不能断  
． ，  
这种情况更加的严重 在计算项集的效用上界时 也需  
．
定它的超集是否为高效用项集 这个问题给高效用项  
．
要增加更多的运算时间和内存消耗  
．
集挖掘带来了一个巨大挑战  
， —  
针对上述问题 提出一个新的数据结构 项集列  
，
鉴于此 一些算法使用效用上界估计方法来对搜  
( Itemset Lists，ILs)  
D-HUI，  
和一个挖掘算法 在稠密数  
表
［7 ～ 9］  
，
索空间进行剪枝 以提升高效用项集挖掘的性能  
．
HUIs．  
据集中挖掘  
项集列表仅存储项集的事务和效用  
［7］  
Liu  
Two-Phase  
，
算法 算法通过两个阶段来确  
等
提出  
． ，  
信息 提出使用差集的方法计算项集的剩余效用 从而  
［8］  
HUIs． Yao  
UMining  
，
算法 使用一种估计  
定
等
提出了  
． Li  
， ．  
计算得到项集的效用上界估计值 减少运算时间 算法  
［9］  
方法来减少搜索空间  
等
提出一个孤立项丢弃策  
D-HUI，  
直接从项集列表中直接发现所有的  
HUIs  
而不  
， ． ，  
略 用于减少候选项集的数量 在这些方法中 挖掘过程  
．
产生任何候选项集  
， ，  
一般分为两个阶段 第一阶段 寻找潜在的  
HUIs(  
效用  
2
相关工作与问题定义  
， ) ，  
上界大于或等于最小效用阈值 称为候选项集 第二  
， ，  
阶段 根据这些候选项集 再次扫描数据库计算其真实  
，
在这部分 首先给出高效用项集挖掘的问题定义  
，
，
的效用 以确定最终的  
HUIs．  
，
在这些方法中 使用包含  
．
然后介绍相关工作  
2． 1  
问题定义  
，
每个候选项集的事务效用之和来满足向下闭性质 从  
， ．  
而对搜索空间进行剪枝 以降低候选项集的数量 虽然  
I = { i ，i ，…，i } ．  
m
，
其中 每  
给定一个有限的一组项  
1
2
HUIs  
，
都能够被发现 但这些方法经常会产生大  
所有的  
i ( 1  
k
k m)  
≤ ≤ 都有一个外部效用值  
EU( i ) ，  
在这里  
k
个项  
，
量的候选项集 并且需要多次扫描数据库  
．
， 1 ． P  
的外部效用为单位利润值 如表 所示 一个项集 由  
［10］  
，Ahmed  
为了避免多次扫描数据库  
IHUP  
等
提出一个基  
k
{ i ，i ，…，i }  
k
，i I，1  
∈
j
j
≤ ≤  
k，k  
P
是项集 的  
个项  
组成  
1
2
．
用于挖掘高效用项集 使用一个树  
于树结构的算法  
． k k-  
长度 长度为 的项集称为 项集  
．
． IHUP  
结构来存储项的事务和效用信息  
IIDS  
和
获得比  
1
表
利润表  
Two-Phase  
Tseng  
IHUP ，  
的基础上 提出了  
更好的性能  
在
Item  
Profit  
A
B
C
D
E
F
G
［11］  
+
［12］  
UP-Growth  
UP-Growth  
，
并提出一些剪  
算法  
和
算法  
7
2
1
2
3
2
3
， ， ．  
枝策略 减少候选项集的数量 从而提高算法的性能 但  
D = { T ，T ，…，T } ，  
包含一组事  
n
一个事务数据库  
1
2
， ，  
是 以上两阶段算法都需要先产生候选项集 再根据候选  
． ，  
务 其中 每一个事务  
T ( 1 id n)  
≤ ≤  
id  
I
都是 的一个子集  
，
，
项集重新扫描数据库计算其真实的效用 以确定最终的  
，
T ．  
id  
包含一个或多个项 具有一个唯一的标识符  
IU( i ，T ) ，  
在
每个事  
HUIs，  
这对算法的挖掘性能产生了较大的影响  
．
T
i
务
中的一个项 具有一个内部效用值  
［13］  
id  
k
k
id  
，Liu  
为了解决这个问题  
HUI-Miner．  
的算法  
等
提出一种的用于挖掘  
， 2  
这里内部效用值为项在事务中的数量 如表 所示  
．
HUIs  
，
它和两阶段算法有着本质区别  
2
表
事务数据库  
，
是一种基于垂直数据结构的算法 它不需要产生候选项  
TID  
Transaction  
TU  
HUIs．  
集而是直接产生  
( Utility Lists，ULs)  
、
首先产生一系列称为效用列表  
T
( A，1) ( C，10) ( E，2)  
( A，2) ( B，1) ( C，6) ( E，1) ( G，5)  
( B，1) ( D，4) ( F，1)  
23  
40  
12  
26  
23  
01  
，
的数据结构 用于存储项集的事务信  
T
02  
T
03  
息 项的效用信息以及能对搜索空间进行剪枝的额外剩  
T
( B，3) ( C，11) ( D，3) ( E，1)  
( A，1) ( B，2) ( C，3) ( E，1) ( G，2)  
04  
．
余效用信息 在产生完所有的  
ULs  
， ULs  
之后 通过扫描 的  
T
05  
HUIs，  
而这一过程不需要产生任何候选  
方式生成所有的  

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号