基于长度约束的蝙蝠高效用项集挖掘算法_袁泉.pdf

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）和长度约束构建高效用项集挖掘（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能有效挖掘具有长度约束的HUI，并减少挖掘模式的数量。关键词：高效用项集挖掘；蝙蝠算法；长度约束；位图矩阵；轮盘赌注选择法中图分类号：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，Chongqing 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 Algorithm 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 calculation 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 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 stable 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;roulette bet selection method0 引言 高效用项集挖掘（High Utility Itemset Mining，HUIM）是频繁项集1问题的推广，主要目标是从事物数据库中挖掘出具有高效用（如高利润）的项集。不同于频繁项集挖掘，HUIM综合考虑了项目出现的次数和用户对于项目的偏好，因此具有更广泛的应用，如零售业的交叉营销2、网络点击流分析3、生物医学应用4以及物联网应用5等。高效用项集（High Utility Itemset，HUI）一般由多个不同的项目组成，因为包含多个项目的项集更有可能是高效用项集。然而在实际生活中，包含较多项目的项集通常表示更具体的情况，可能很少见，有时不如包含较少项目的项集有用。例如，一个零售商店长在交易数据库中发现了2个高效用项集 意大利面，鸡蛋 和 橙子，奶酪，可乐，意大利面，鸡蛋。如果店长想增加商店的整体利润，促销推广第一套商品比第二套更有效。因为前者只包含两种商品，在生活中很常见，购买的客户相对较多；而第二套包含五种商品，在生活中较少见，客户购买相对较少。此外，传统的 HUIM 算法会返回大量的高效用项集，这可能会耗尽存储空间，而且对用户而言分析大量的结果集也非常耗时。因此，为了给用户提供更有用的HUI，同时过滤掉不太有用的项集，在HUIM中有必要考虑项集长度的影响。为了挖掘具有长度约束的HUI，一种简单的方法是挖掘出所有的高效用项集之后再筛选出符合长度需求的项集，但文章编号：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 卷计算机应用这种方法效率很低，因为没有利用长度约束来缩减搜索空间，且筛选也会带来额外的时间开销。文献 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。实验表明，在时间和内存都充足的条件下，这些算法可以精确找到数据库中所有的HUI。然而，由于传统的算法递归地将项附加到项集中，当数据集较大或项目数量较多时，传统算法将面临呈指数增长的搜索空间，算法挖掘效率变得很低。为探索HUI巨大的搜索空间，众多学者提出采用演化算法来挖掘HUI。如文献 9 中首次将遗传算法（Genetic Algorithm，GA）应用于HUIM，提 出 了 HUP-GA（High-Utility Pattern extraction using Genetic Algorithm，HUP-GA），该算法利用染色体选择、交叉、突 变 的 特 性 寻 找 HUI；文 献10中 提 出 了 粒 子 群 优 化（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中以一定概率选择下一代种群的初始优化值，提高了种群的多样性；文献 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 中提出了一个基于生物启发式挖掘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结合长度约束，提出一种基于长度约束的蝙蝠高效用项集挖掘算法（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）提出长度修剪策略，使用轮盘赌注选择法确定修剪的项目，并使用深度优先搜索将项集的长度修剪至用户定义的范围。该策略可以很容易集成其他生物启发式算法，具有良好的可扩展性。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)，称为内部效用（如购买数量）。例如表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的效用记作TU（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。用户定义项集的最小长度为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 期袁泉等：基于长度约束的蝙蝠高效用项集挖掘算法项集，且包含的项目数量在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(Tc)，定义为：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 Weighted 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中，一个蝙蝠个体表示一个项集，适应值表示项集的总效用，通过设置合适的迭代次数、声波响度衰减系数、脉冲增强系数，就可以进行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 Tj0，其他（13）即当项目ik出现在事务Tj中，布尔矩阵B(D)中第j行、第k列这个位置为1，否则该位置为0。定义13 位图覆盖。在位图矩阵中，项目ik的位图覆盖是B(D)中的第k列向量，定义为Bit(ik)。同理，项集 X的位图覆盖定义为Bit(X)=i X(Bit(i)，即项集 X 的位图覆盖是通过项集X中每一个项目的位图覆盖按位与运算得到。2.1.2RTWU剪枝策略定义 14 设项目ij，若RTWU(ij)min_util，则项目ij是低重新定义的事物加权效用，记为1-LRTWUI。由性质2可知1-LRTWUI及其所有的超集都是低效用项集。因此，可以先计算所有项目的 RTWU，然后删除掉1-LRTWUI的项目，以有效缩减搜索空间。在表1和表2的事务表中，设min_util=30，lmax=3，由于项目 f和 g是 1-LRTWUI，故不会出现在位图中，则整理后的事务数据库转换为位图如表4所示。2.1.3无希望编码向量剪枝策略在 HUIM-LC-BA 中，每个蝙蝠个体就是一个编码向量。编码向量由0或1组成，表示个体中某个项目出现或不出现。如果一个个体中对应的第j位为1，就表示第j位置中对应的项目出现在项集中；反之，则表示第j位置对应的项目没有出现 在 项 集 中。每 个 蝙 蝠 对 应 的 编 码 向 量 的 长 度 为|1-HRTWU，如项集 a，c，d 的编码向量如图1所示。定义15 设Vec为只有0和1组成的关于项集X的编码向量。如果Bit(X)只由0组成，那么该Vec被称为无希望编表 3事物效用以及重新定义的事物效用Tab.3Transaction utility and redefined transaction utilityTidT1T2T3T4T5Transaction（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）TU242082711RTU201782291475第 43 卷计算机应用码向量（Unpromising Encoding Vector，UPEV）；反之，则称为有希望编码向量（Promising Encoding Vector，PEV）10。因为蝙蝠个体随机生成，不可避免地会生成一些数据库中不存在的项集，即无希望项集。为了避免无希望项集效用的计算，需要对无希望的编码向量进行修剪。无希望编码向量剪枝策略的伪代码由算法1给出。算法1 无希望编码向量（UPEV）剪枝策略。输入 表示蝙蝠的编码向量Vec。输出 有希望编码向量Vec。1）计算Vec中1的数量，记为VN2）定义VN个项目i1，i2，iVN表示Vec3）RV=Bit(i1)/初始化RV为Bit(i1)4）For k从2到VN do5）RV=RV Bit(ik)6）If RV是一个UPEV then7）RV=RV8）将Vec中的ik从1变为09）End If10）RV=RV11）End For12）Return RV2.1.4项集长度修剪策略在文献 7 中，FHM+算法首先建立一个存放所有项目对的 三 元 组 结 构 EUCS（Estimated Utility Co-occurrence Structure），定义为(a，b，c)I I R，即RTWU(a，b)=c。FHM+算法从单个项目开始，通过深度优先搜索逐渐追加单个项目，直到最大长度。在搜索的过程中，当 EUCS 中不存在元组(x，y，c)满足c min_util，则进行修剪，即项集 x，y 及其所有的超集都是低效用项集，不再探索。在BA中，由于蝙蝠个体随机生成，故不能直接使用上述EUCS结构来剪枝。因此本文利用蝙蝠个体随机变化的特性提出一种新的项集长度修剪策略，通过将PEV添加、删除若干个项目，使它的长度l满足lmin l lmax。该策略包含以下三种情况：1）如果l lmax，则生成一个随机整数 n，满足l-lmaxn l-lmin，然后使用轮盘赌注选择法确定删除的n个项目，将编码向量中这些位置由1变为0。因为有希望的编码向量减去部分项集仍是有希望的编码向量，故无需再使用算法1检验。3）如果lmin l lmax，编码向量满足长度约束，故不做改动。算法2 Search。输入 待增加项目数n；编码向量Vec；存放 0位置索引的集合zero。输出 有希望编码向量Vec。1）If zero.size()=0 or n=02）return Vec3）在zero 中使用轮盘赌注选择法确定项目im4）将Vec中im位置对应的0变为1，并删除zerom 5）执行算法16）If Vec的长度加17）Search(n-1，Vec，zero)8）Else9）Search(n，Vec，zero)项集长度修剪策略算法的伪代码由算法3给出。算法3 项集长度约束修剪策略。输入 有希望的编码向量 Vec；最小项集长度 lmin；最大项集长度lmax。输出 满足长度约束的有希望编码向量Vec。1）For i从0到|1-HRTWU do2）one i/记录1位置索引的集合3）zero i/记录0位置索引的集合4）End For5）If one.size()lmax，do/第2）种情况9）生成一个随机数n10）For i 从1到 n do11）在one 中使用轮盘赌注选择法确定项目m12）将Vec中im位置对应的1变为0，并在one中删除im13）End For14）Else/第3）种情况，不做改动15）End If16）Return lc-项集2.2种群初始化种群初始化的主要作用是随机产生若干个蝙蝠个体。在算法 4中，首先扫描数据库一次，删除 1-LRTWUI；接着将修剪后的事务数据库转换为位图矩阵。第3）10）行循环生成初始蝙蝠个体，其中：第4）行生成一个随机数n，并且满足lmin l lmax+C（C 为一个常数，可根据|1-RHTWUI适应性调整，以大概率生成符合长度约束的项集）；第5）行设置Vec中n个位置1，其余全为0。式（14）为项目ij被设为1的概率。Pj=RTWU(ij)k=1HNRTWU(ik)（14）其中：HN=|1-LRTWUI表示高重新定义的事务加权效用1-项集的个数。由式（14）可知项目ij的RTWU值越大，则在初始化种群中有更大的概率被选中。第 6）8）行修剪初始向量，使该向量是有希望编码向量并且满足长度约束条件。算法4 种群初始化。输入 事务数据库D；种群包含的蝙蝠个数SN。表 4事务数据的位图表示Tab.4Bitmap representation of transaction databaseTidT1T2T3T4T5a10110b11001c11111d01100e11011图1项集 a，c，d 的编码向量Fig.1Coding vector of itemset a，c，d 1476第 5 期袁泉等：基于长度约束的蝙蝠高效用项集挖掘算法输出 初始种群。1）扫描D一次，删除1-LRTWUI2）将新的数据库转为位图矩阵3）For i从1到SN do4）生成一个随机数n lmin，lmax+C 5）生成一个编码向量Veci，并通过轮盘赌注选择法将向量中n个位置设为16）If n 1 then7）使用算法1生成PEV的Veci8）使用算法3修剪向量Veci长度9）End If10）End For2.3HUIM-LC-BA设计本文提出的HUIM-LC-BA利用了前面介绍的几种策略。算法5为主算法，将事物数据库D、最小阈值min_util、项集的长度范围以及最大迭代次数作为输入，输出lc-高效用项集。第1）4）行分别表示初始化蝙蝠种群，初始化迭代次数iter 为 1，gbest表示全局最优解初始为空，SHUI（Set of High Utility Itemset）表示高效用项集的集合。第5）20）行为主循环，表示通过一个种群到下一个种群的迭代逐个发现符合长度约束的高效用项集。第 6）14）行循环遍历每个蝙蝠个体，如果当前种群是第一个种群，则初始化当前蝙蝠的Ai和ri；第10）行计算蝙蝠Bi对应数据库中的项集，函数IS（）通过项目 i 在蝙蝠 Bi中对应位置是否为 1，返回对应的项集；第11）13）行查找并记录还没有被发现的符合长度约束的高效用项集；第15）行更新当前蝙蝠经历过的最好位置；第16）行使用新的gbest并调用算法 6 生成下一个种群；第 17）行在所有发现的SHUI使用轮盘赌注选择法确定下一个种群的初始gbest；第18）行更新迭代次数；最后，在第20）行输出lc-高效用项集。算法5 HUIM-LC-BA。输入 事务数据库D；最小效用阈值min_util；最大迭代次数max_iter；最小长度lmin和最大长度lmax。输出 lc-高效用项集。1）调用算法4，初始化种群；2）iter=1；/初始迭代次数设为13）gbest=；/初始全局最优解为空集4）SHUI=；/将所有高效用项集的集合设为空集5）While iter ri then9）X=IS(Bi)/蝙蝠Bi对应的项集X10）If u(X)min_util且X SHUI 且lmin l lmax then11）X存入SHUI12）End If13）用位与运算随机改变Bi的一位14）调用算法1，生成新的编码向量Bi15）调用算法3，修剪向量长度16）End If17）If rand2 Ai&u(X)3，故需要修剪。在算法2中，首先随机生成一个1477第 43 卷计算机应用数n=1，使用轮盘赌注选择法将第5位变成0，得到长度为3的项集 a，b，c，因为u(a，b，c)=18 min_util，所以项集 a，c，e是一个lc-高效用项集，且SHUI=a，c，e：33，其中冒号后面表示项集的效用值。同理，b3代表项集d，e，因为u(d，e)=18 min_util。因此，b，e是一个lc-高效用项集，将它存入SHUI，同时更新gbest。最后，通过逐位补码操作随机改变以为来进一步处理b1。假设第2位从1变为0，得到新的b1=00001，虽然b1长度为1且是期望编码向量，但u(e)=15 min_util，gbest和SHUI保持不变。类似的，可以通过相同的方法获得b2、b3的新值。重复上述步骤，直到达到最大迭代次数。3 实验与结果分析 3.1实验环境本实验所有程序均用 Java 进行编写，实验环境为 Intel Core i7-11700 2.5 GHz，8 GB 内存，Windows11 64 位操作系统。本实验采用了4个公开的真实数据集，各个数据集的特征如表5所示。其中，mushroom数据集包含各种蘑菇种类及特征，如形状、气味和栖息地；chess和 connect数据集来源于游戏步骤；accident_10%数据集记录了某地的交通事故数据，与之前的研究相似，本文只取了其中10%。这些数据都可以从SPMF网站上下载。表 5真实事务数据集统计Tab.5Statistics of real transaction datasets数据集mushroomchessconnectaccident_10%平均长度23374334项数11975130468事物数8 1243 19667 55734 018本文中所有的实验的最大迭代次数设置为 6 000，种群的初始大小为100，默认最小长度为1。3.2高效用项集挖掘对比实验3.2.1RTWU策略本节评估了 RTWU策略在不同长度约束条件下对搜索空间的影响，主要考虑编码向量的长度，即 1-HRTWUI的个数，并和包含所有长度的编码向量作比较。为了便于观察和分析，在文献 7 的基础上，设置最大长度约束为 2、4、6、8、10 进行仿真实验，并在 4 个数据集上不断增加效用阈值，运行HUIM-LC-BA和传统的HUIM-BA。在各数据集和各约束下的编码向量长度由表6给出。其中：lmax表示在 HUIM-LC-BA 中设置的最大长度值；all-len 表示传统算法 HUIM-BA挖掘所有长度的项集的运行情况。观察表 6发现，在各效用阈值下，具有长度约束的编码向量的长度都小于包含所有长度的编码向量，并且随着长度的减少而减少。尤其是在项数较多的accident_10%数据集中，与all_len情况相比，lmax=2编码向量长度平均减少了 60%。因此，RTWU策略能有效减小编码向量的长度，缩小搜索空间，且在最大长度较小时效果更好。3.2.2不同长度约束下挖掘数量的比较本 节 评 估 了 在 不 同 长 度 约 束 下 挖 掘 模 式 的 数 量。HUIM-LC-BA 和其他的基于演化算法的高效用项集挖掘算法一样，不能保证在一定的迭代次数内找到所有的高效用项集，而FHM+算法在时间和内存都充足的条件下可以找到所有的高效用项集。因此，为验证HUIM-LC-BA挖掘的项集数量，令lmax=6，运行 FHM+算法和 HUIM-LC-BA，计算 HUIM-LC-BA挖掘的项集数量与FHM+算法挖掘项集数量的比值，实验结果如表7所示。观察表 7可知，在挖掘数量方面，各数据集平均挖掘百分比都达到了90%，且在效用阈值较大时达到了100%，说明所提出的算法能有效挖掘具有长度约束的高效用项集。为了继续比较不同长度约束下算法挖掘的模式数量，在4个数据集上运行HUIM-LC-BA和传统的HUIM-BA，结果如图3所示。在图3中观察到，通过设置不同长度约束可以大幅减少表 6在不同数据集上Vec的长度Tab.6Length of Vec on different datasets数据集mushroomchessconnectaccident_10%min_util/1031501752002252502002503003504008 5009 0009 50010 00010 500200250300350400lmax25248454541453937342430282524198474614937459555452495249444037383737363411092847870662605654545552504540414140383811811097888386861605654565352504643434241411291171101079210686661605657555251504945444343133123116110107all_len777268646161585856556362616059190171158148142图2算法示例Fig.2Algorithm example1478第 5 期袁泉等：基于长度约束的蝙蝠高效用项集挖掘算法模式数量，且在 lmax=2或 4时，由于项集数量太少导致无法在图上正常显示。在mushroom、chess、connect、accident_10%数据集上，当最大长度为 6时，与 HUIM-BA 相比，HUIM-LC-BA 挖掘的模式数量减小了 91%、98%、99%、97%，并且随着最大长度的减小模式数量也不断减少。观察图 3（c），在connect 数据集中，HUIM-LC-BA 挖掘数量远小于 HUIM-BA，并结合表10可知此时挖掘的百分比为100%，说明该数据集中长度为5的高效用项集很少，通过HUIM-LC-BA明显减少了无效项集的生成。因此，通过HUIM-LC-BA可过滤掉高效用但不符合长度约束的项集，只输出少量的lc-高效用项集，有利于用户的分析和决策。3.2.3运行时间本节评估了 HUIM-LC-BA 在不同长度约束下运行时间的性能。结果如图4所示，其中lmax表示最大长度约束。由图4可以看出，由于HUIM-BA要挖掘所有的高效用项集，所以运行时间不随长度增加而变化。在图4中可以清晰看 到 HUIM-LC-BA 的 运 行 时 间 远 小 于 HUIM-BA。因 为HUIM-LC-BA 利用长度约束在蝙蝠种群初始化时修剪了更多无期望的项目，缩小了搜索空间。在mushroom、connect和accident_10%数据集中，当lmax 8时，FHM+算法运行时间急剧增加，而 HUIM-LC-BA 的运行时间增长相对稳定。因为FHM+算法从单个项目开始不断枚举增加额外的项目直到达到最大长度，在lmax较小时，很容易找到符合长度约束的高效用项集；但当lmax逐渐增加，需要组合的项目和项集数量增多，FHM+面临指数的搜索空间导致开销很大。同样观察图4（b）的chess数据集，由于chess数据集中项目和事物数量相对较少，所以在lmax=10时FHM+算法仍具有良好的性能，但依然可以看出FHM+算法的运行时间急剧增长。此外，通过观察HUIM-LC-BA在每50次迭代后挖掘的lc-高效用项集数量发现，当lmax较小时，HUIM-LC-BA在较少的迭代次数就已经发现了所有的lc-高效用项集，但由于HUIM-LC-BA的随机性并不知道已经找到了所有的 lc-高效用项集，所以会继续迭代下去直到达到最大迭代次数，导致 HUIM-LC-BA 在lmax较小时运行时间远大于 FHM+算法，但实际找到所有的lc-高效用项集运行时间小于统计值。因此，HUIM-LC-BA能表7挖掘6-HUI的百分比Tab.7Percentage of mined 6-HUIs数据集mushroommin_util/1031501752002252506-HUI/%92.197.9100.0100.0100.0数据集chessmin_util/1032002503003504006-HUI/%83.394.798.1100.0100.0数据集connectmin_util/1038 5009 0009 50010 00010 5006-HUI/%100100100100100数据集accident_10%min_util/1032002503003504006-HUI/%81.8