基于长度约束的蝙蝠高效用项集挖掘算法_袁泉.pdf
《基于长度约束的蝙蝠高效用项集挖掘算法_袁泉.pdf》由会员分享,可在线阅读,更多相关《基于长度约束的蝙蝠高效用项集挖掘算法_袁泉.pdf(8页珍藏版)》请在咨信网上搜索。
1、2023-05-10计算机应用,Journal of Computer Applications2023,43(5):1473-1480ISSN 1001-9081CODEN JYIIDUhttp:/基于长度约束的蝙蝠高效用项集挖掘算法袁泉1,2,唐成亮1,2*,徐雲鹏1,2(1.重庆邮电大学 通信与信息工程学院,重庆 400065;2.重庆邮电大学 通信新技术应用研究中心,重庆 400065)(通信作者电子邮箱)摘要:为了挖掘满足用户特殊需求,如含指定项目数量的高效用项集(HUI),提出一种基于长度约束的蝙蝠高效用项集挖掘算法(HUIM-LC-BA)。该算法融合蝙蝠算法(BA)和长度约束构建
2、高效用项集挖掘(HUIM)模型,首先将数据库转换为位图矩阵,实现高效的效用计算和数据库扫描;其次,采用重新定义的事务加权效用(RTWU)策略缩减搜索空间;最后,对项集进行长度修剪,使用深度优先搜索和轮盘赌注选择法确定修剪项目。在4个数据集的仿真实验中,当最大长度为6时,与HUIM-BA相比,HUIM-LC-BA挖掘的模式数量分别减少了91%、98%、99%与97%,同时运行时间也少于HUIM-BA;且在不同长度约束条件下,与FHM+(Faster High-utility itemset Ming plus)算法相比运行时间更稳定。实验结果表明,HUIM-LC-BA能有效挖掘具有长度约束的HU
3、I,并减少挖掘模式的数量。关键词:高效用项集挖掘;蝙蝠算法;长度约束;位图矩阵;轮盘赌注选择法中图分类号:TP301.6 文献标志码:ABat algorithm for high utility itemset mining based on length constraintYUAN Quan1,2,TANG Chengliang1,2*,XU Yunpeng1,2(1.School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications,Chongq
4、ing 400065,China;2.Research Center of New Communication Technology Applications,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)Abstract:In order to mine the High Utility Itemsets(HUIs)that meet the special needs of users,such as the specified number of items,a Bat Algori
5、thm for High Utility Itemset Mining based on Length Constraint(HUIM-LC-BA)was proposed.By combining the Bat Algorithm(BA)and length constraints,a new High Utility Itemset Mining(HUIM)model was constructed,in which the database was transformed into a bitmap matrix to realize efficient utility calcula
6、tion and database scanning.Then the search space was reduced by using the Redefined Transaction Weighted Utility(RTWU)strategy.Finally,the lengths of the itemsets were pruned according to the items determined by roulette bet selection method and depth first search.Experiments on four datasets showed
7、 that,when the maximum length was 6,the number of patterns mined by HUIM-LC-BA was reduced by 91%,98%,99%and 97%respectively compared with that of HUIM-BA(High Utility Itemset Mining-Bat Algorithm)with less running time;and under different length constraints,the running time of HUIM-LC-BA is more st
8、able compared to the FHM+(Faster High-utility itemset Ming plus)algorithm.Experimental results indicate that HUIM-LC-BA can effectively mine HUIs with length constraints and reduce the number of mined patterns.Key words:High Utility Itemset Mining(HUIM);bat algorithm;length constraint;bitmap matrix;
9、roulette bet selection method0 引言 高效用项集挖掘(High Utility Itemset Mining,HUIM)是频繁项集1问题的推广,主要目标是从事物数据库中挖掘出具有高效用(如高利润)的项集。不同于频繁项集挖掘,HUIM综合考虑了项目出现的次数和用户对于项目的偏好,因此具有更广泛的应用,如零售业的交叉营销2、网络点击流分析3、生物医学应用4以及物联网应用5等。高效用项集(High Utility Itemset,HUI)一般由多个不同的项目组成,因为包含多个项目的项集更有可能是高效用项集。然而在实际生活中,包含较多项目的项集通常表示更具体的情况,可能很
10、少见,有时不如包含较少项目的项集有用。例如,一个零售商店长在交易数据库中发现了2个高效用项集 意大利面,鸡蛋 和 橙子,奶酪,可乐,意大利面,鸡蛋。如果店长想增加商店的整体利润,促销推广第一套商品比第二套更有效。因为前者只包含两种商品,在生活中很常见,购买的客户相对较多;而第二套包含五种商品,在生活中较少见,客户购买相对较少。此外,传统的 HUIM 算法会返回大量的高效用项集,这可能会耗尽存储空间,而且对用户而言分析大量的结果集也非常耗时。因此,为了给用户提供更有用的HUI,同时过滤掉不太有用的项集,在HUIM中有必要考虑项集长度的影响。为了挖掘具有长度约束的HUI,一种简单的方法是挖掘出所有
11、的高效用项集之后再筛选出符合长度需求的项集,但文章编号:1001-9081(2023)05-1473-08DOI:10.11772/j.issn.1001-9081.2022040622收稿日期:2022-05-07;修回日期:2022-07-28;录用日期:2022-08-02。作者简介:袁泉(1976),男,湖南邵阳人,高级工程师,硕士,主要研究方向:大数据、数据挖掘、自然语言处理;唐成亮(1997),男,四川德阳人,硕士研究生,主要研究方向:数据挖掘;徐雲鹏(1998),男,河南漯河人,硕士研究生,主要研究方向:数据挖掘。第 43 卷计算机应用这种方法效率很低,因为没有利用长度约束来缩减
12、搜索空间,且筛选也会带来额外的时间开销。文献 6 中提出了MinFHM(Minimal Faster High-utility itemset Mining)算法挖掘最小HUI(各项集不被包含在另外的HUI中),有效减少了返回 结 果 集 的 数 量。文 献7中 对 FHM(Fast High utility Miner)8算法进行改进,引入了长度约束(Length Constraint)和两个关于长度约束的新上界,提出了 FHM+(Faster High-utility itemset Mining plus)算法,该算法可以通过定义不同的长度约束范围来挖掘具有长度约束的HUI。实验表明,在
13、时间和内存都充足的条件下,这些算法可以精确找到数据库中所有的HUI。然而,由于传统的算法递归地将项附加到项集中,当数据集较大或项目数量较多时,传统算法将面临呈指数增长的搜索空间,算法挖掘效率变得很低。为探索HUI巨大的搜索空间,众多学者提出采用演化算法来挖掘HUI。如文献 9 中首次将遗传算法(Genetic Algorithm,GA)应用于HUIM,提 出 了 HUP-GA(High-Utility Pattern extraction using Genetic Algorithm,HUP-GA),该算法利用染色体选择、交叉、突 变 的 特 性 寻 找 HUI;文 献10中 提 出 了 粒
14、 子 群 优 化(Particle Swarm Optimization,PSO)和 OR/NOR 树相结合的HUIM-BPSO(High-Utility Itemset Mining-Binary Particle Swarm Optimization,HUIM-BPSO)算法,所提出的树结构可以有效降低无效用项集效用的计算;文献 11 中对 HUIM-BPSO 算法进行改进,提出了 HUIM-IPSO(High Utility Itemset Mining-Improved PSO,HUIM-IPSO)算法,该算法通过轮盘赌选择法在当前代种群的HUI中以一定概率选择下一代种群的初始优化值,
15、提高了种群的多样性;文献 12 中采用位图矩阵来表 示 事 务 数 据 库 并 结 合 人 工 蜂 群 算 法(Artificial Bee Algorithm,ABC)提 出 了 HUIM-ABC(High-Utility Itemset Mining-Artificial Bee Algorithm,HUIM-ABC)。实验结果表明,位图矩阵能有效加快数据库的扫描和项集效用的计算;文献 13 中基于人工鱼群(Artificial Fish,AF)提出了HUIM-AF(High-Utility Itemset Mining-Artificial Fish,HUIM-AF)算法;文献 14 中
16、提出了一个基于生物启发式挖掘HUI的框架(Biology inspired-High Utility Itemset Framework,Bio-HUIF),该框架对GA、PSO和蝙蝠算法(Bat Algorithm,BA)进行改进与 优 化,提 出 了 Bio-HUIF-GA、Bio-HUIF-PSO 和 Bio-HUIF-BA,其中Bio-HUIF-BA相较于另外两个改进算法在迭代寻优方面具有很大优势,需要调整的参数较少,且实验结果表明它在收敛性、运行时间、占用内存方面都优于另外两种算法。目前,演化算法在 HUIM 方面取得了不错的进展,但都未考虑项集长度的影响。因此本文选择目前较优的GA
17、结合长度约束,提出一种基于长度约束的蝙蝠高效用项集挖掘算法(Bat Algorithm for High Utility Itemset Mining based on Length Constraint,HUIM-LC-BA),以挖掘具有长度约束的 HUI。本文主要工作如下:1)HUIM-LC-BA 将数据库转为位图矩阵以加快效用计算和数据库的扫描,并使用重新定义的事务加权效用(Redefined Transaction Weighted Utility,RTWU)策略缩减搜索空间,提升HUIM-LC-BA的效率。2)提出长度修剪策略,使用轮盘赌注选择法确定修剪的项目,并使用深度优先搜索将项
18、集的长度修剪至用户定义的范围。该策略可以很容易集成其他生物启发式算法,具有良好的可扩展性。3)在 4 个真实数据集上的实验结果表明,HUIM-LC-BA能有效挖掘具有长度约束的HUI,大幅减少了模式的数量和运行时间。1 基本概念 1.1高效用项集令I=i1,i2,iN是N个不同项目的集合,其中每个项目ik I(1 k N)对应一个正数p(ik),表示该项目的权重(如单位利润)。事务数据库D=T1,T2,TM由M条不同事务构成,其中每个事务Tc(1 c M)都是I的子集(即Tc I),同时有一个唯一的 Tid来记录每个不同的事务。事务Tc中每一个项目ik都有一个对应的正数q(i,Tc),称为内部
19、效用(如购买数量)。例如表1共包含5个事务,每个事物中记录了不同的项目以及项目出现的次数,表2的外部效用表记录了每个项目对应的外部效用。定义1 项在事物中的效用2。项目ik在事务Tc中的效用记作u(ik,Tc),定义为:u(ik,Tc)=p(ik)q(ik,Tc)(1)定义2 项在事物中的效用2。项集X在事务Tc中的效用记作u(X,Tc),定义为:u(X,Tc)=i Xu(i,Tc)(2)定义3 项集在数据库中的效用2。项集X在数据库D中的效用记作u(X),定义为:u(X)=X Tc Du(X,Tc)(3)定义4 事物效用(Transaction Utility,TU)2。事务Tc的效用记作T
20、U(Tc),定义为:TU(Tc)=i Tcu(i,Tc)(4)定义 5 事 物 加 权 效 用(Transaction Weighted Utility,TWU)2。项 集 X 在 数 据 库 D 中 的 事 务 加 权 效 用 记 作TWU(X),定义为:TWU(X)=X Tc Tc DTU(Tc)(5)定 义 6 高 效 用 项 集2。用 户 定 义 最 小 效 用 阈 值min_util,如果项集 X 的效用值u(X)min_util,则项集 X 是高效用项集,反之为低效用项集。1.2项集长度属性和定义定义 7 lc-HUI(length contrained-HUI)7。用户定义项集的
21、最小长度为lmin、最大长度为lmax。如果项集X是高效用表 1事务表Tab.1Transaction tableTidT1T2T3T4T5Transaction(a,1),(b,5),(c,1),(d,3),(e,1),(f,5)(b,4),(c,3),(d,3),(e,1)(a,1),(c,1),(d,1)(a,2),(c,6),(e,2),(g,4)(b,2),(c,2),(e,1),(g,2)表 2外部效用Tab.2External utility项目ab效用52项目cd效用12项目ef效用31项目g效用11474第 5 期袁泉等:基于长度约束的蝙蝠高效用项集挖掘算法项集,且包含的项目
22、数量在lmin,lmax,则称项集X为lc-HUI。严格的上界对于高效地修剪搜索空间至关重要,为了进一步使用TWU属性修剪具有长度约束高效用项集的搜索空间,FHM+算法重新定义了相关概念。定义8 事物的最大效用7。设事务Tc=i1,i2,ik,用户定义最大长度为lmax。事物 Tc中的最大效用为集合u(i1,Tc),u(i2,Tc),u(ik,Tc)中最大长度值的集合,记为L(Tc)。定义 9 重新定义的事物效用(Redefined Transaction Utility,RTU)7。设事务Tc=i1,i2,ik,重新定义的事务效用表示事物Tc在最大长度约束条件下拥有的最大效用,记作RTU(T
23、c),定义为:RTU(Tc)=L(Tc)(6)例 如,令lmax=2,则 事 物 T2重 新 定 义 的 事 物 效 用RTU(T2)=u(b,T2)+u(d,T2)=14。通过计算不超过lmax项的最大效用之和来减少事物效用。表 3列出了每条事物的TU和RTU。定义10 重新定义的事务加权效用(RTWU)7。项集X重新定义的事物加权效用记作RTWU(X),定义为RTWU(X)=X Tc Tc DRTU(Tc)(7)定义11 如果项集 X 满足RTWU(X)min_util,则称 X为高重新定义的事务加权效用项集,记为 HRTWUI(High Redefined Transaction Wei
24、ghted Utility Itemset);反之,则称 X为低重新定义的事务加权效用项集LRTWUI(Low Redefined Transaction Weighted Utility Itemset)。定义 12 包含 k 个项目的 HRTWUI 和 LRTWUI 分别记为k-HRTWUI和k-LRTWUI。重新定义的事物加权效用具有如下性质:性质1对于任何一个项集X,满足RTWU(X)u(X)。性质2对 于 任 何 一 个 项 集X,如 果RTWU(X)0是脉冲频度增强系数;r0i表示蝙蝠i初始脉冲频率。基于 BA 的 HUIM 算法12中,一个蝙蝠个体表示一个项集,适应值表示项集的总
25、效用,通过设置合适的迭代次数、声波响度衰减系数、脉冲增强系数,就可以进行HUI的挖掘。2 HUIM-LC-BA 本章将详细介绍HUIM-LC-BA,包括重新定义的事物加权效用策略、原始事务数据库位图的表示、无希望编码向量的剪枝、项集长度修剪策略、种群初始化以及算法的伪代码。2.1数据的位图表示和剪枝策略2.1.1数据的位图表示设一个有限项集I=i1,i2,iN和一个事务数据库D=T1,T2,TM,则位图是一个M N的布尔矩阵,定义为B(D)。在事务Tj(1 j N)中,项目ik(1 k N)的位置记为(j,k),即位于B(D)的第 j 行、第 k 列。Bj,k的值定义如下:Bj,k=1,ik
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 长度 约束 蝙蝠 高效 用项 挖掘 算法 袁泉
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。