基于智能优化算法的高效用项集挖掘方法综述

高智慧，韩 萌，刘淑娟，李 昂，穆栋梁

（北方民族大学 计算机科学与工程学院，银川 750021）

0 引言

项集挖掘是数据挖掘的一个重要分支［1］，频繁项集挖掘（Frequent Itemset Mining，FIM）旨在找到客户的交易中频繁一起购买的物品［2］，但是忽略了物品的利润信息［3］，为了解决这个局限性，文献［4-5］中将物品的单位利润和数量分别视为外部效用和内部效用，进而提出了一系列的高效用项集挖掘（High Utility Itemset Mining，HUIM）方法［6-12］。比如在超市销售中，FIM 认为顾客购买3 瓶饮料比购买1 件首饰重要，忽略了1 件首饰的利润要远大于3 瓶饮料所带来的利润；而HUIM 考虑事务的效用，认为顾客购买1 件首饰要比购买3瓶饮料重要。

然而，枚举数据集中所有的高效用项集（High Utility Itemset，HUI）很难实现，且当数据集的大小和数据集中不同项的总数增加时，现有确定性算法的性能会随之降低［13］。此外，HUI 往往分散在搜索空间中，这使得挖掘算法必须考虑大量项集才能发现实际的HUI。近似算法的使用可以在结果完整性和算法的性能之间提供良好的平衡［14］，突破了传统模式挖掘方法的性能瓶颈［15］。智能优化算法具有解决复杂、线性和高度非线性问题的能力，可以探索大型问题空间，根据适应度函数找到接近最优的解决方案［16］，因此基于智能优化算法的HUIM 成为一个新兴的研究主题。

Kannimuthu 等［17］将遗传算法（Genetic Algorithm，GA）应用于 HUIM，提出HUPEUMU-GARM（High Utility Pattern Extraction using Genetic Algorithm with Ranked Mutation Using Minimum Utility threshold）方法和不需要指定最小效用阈值的 HUPEWUMU-GARM（High Utility Pattern Extraction using Genetic Algorithm with Ranked Mutation Without Using Minimum Utility threshold）方法，这是智能优化算法在HUIM中的首次应用，能够在指数搜索空间中快速有效地挖掘HUI。与基于GA 的HUIM 方法相比，基于粒子群优化（Particle Swarm Optimization，PSO）的技术需要更少的参数，无需设置合理的交叉和变异率，可以很容易实现［18］。Lin等［19-20］首次将PSO 应用于HUIM，在粒子更新过程中采用sigmoid 函数，并开发了OR/NOR-tree 结构［18］，通过提前修剪粒子的无效组合避免对数据库的多次扫描。Song 等［21］从人工蜂群（Artificial Bee Colony，ABC）算法的角度对HUIM 问题进行建模，利用位图进行信息表示和搜索空间剪枝，加速了HUI 的发现。Song 等［22］从人工鱼群（Artificial Fish swarm，AF）算法的角度研究了HUIM 问题，并提出一种名为HUIM-AF（HUIM methods based on AF algorithm）的HUIM 方法。此外，智能优化算法还可以用于挖掘HUI 的复杂模式，例 如，Song 等［23］提出了 基于标 准PSO 方法的HAUI-PSO（mining High Average-Utility Itemsets based on PSO）算法挖掘高平均效用项集（High Average Utility Itemsets，HAUI）；Lin等［24］提出了一种基于GA 的算法DcGA（Decomposition based on a compact GA），在有限的时间内高效地挖掘闭合高效用项集（Closed HUI，CHUI）；Song 等［25］提出了基于交叉熵的方法 TKU-CE+（Top-Khigh-Utility itemset mining based on Cross-Entropy method），用于启发式地挖掘top-k高效用项集。

现有的相关综述中，Logeswaran 等［26］从模式的角度对元启发式的模式挖掘方法进行介绍，并未以智能优化算法的类别为角度对HUIM 进行综述；Djenouri 等［27］从GA、PSO 和蚁群优化（Ant Colony Optimization，ACO）算法这3 个方面对频繁模式挖掘和HUIM 的个别方法进行了研究；张妮等［28］从正与负的角度划分了高效用模式挖掘方法；单芝慧等［29］从增量数据、数据流等角度对高效用模式及融合高效用模式进行了较全面的分析总结。为了使研究者能够对智能优化算法在HUIM 的应用有一个更加清晰的了解，本文从不同类型的智能优化算法的角度对HUIM 方法进行分类综述。本文的总体框架如图1所示。

图1 文章框架Fig.1 Framework of the paper

本文的主要工作如下：

1）首次把基于智能优化算法的HUIM 方法分为基于群智能优化算法、基于进化算法（Evolutionary Algorithm，EA）和基于其他算法的HUIM，并作了全面的分析与总结。

2）首次把基于PSO 的HUIM 算法从粒子更新策略的角度分为5 类进行比较，包括：基于传统更新策略、基于sigmoid函数、基于贪心、基于轮盘赌和基于集合的HUIM。

3）分析总结了现有的基于智能优化算法的HUIM 的优点和不足，从数据流、自适应、剪枝策略和复杂模式等角度给出下一步的研究方向以供参考。

1 背景介绍

1.1 高效用项集挖掘概念

令I={i1，i2，…，in}是由一组项组成的集合，令DB是一个数据库，这个数据库中有一个效用列表（表1）和一个事务列表（表2）。效用列表中的每个项I都有一个效用值。事务列表中的每个事务T都有一个唯一的标识符tid，且T是I的一个子集，其中每个项都与一个计数值相关联。若一个项是I的子集，且包含k个项，则称之为k-项集［8］。

表1 效用列表Tab.1 Utility list

表2 事务列表Tab.2 Transaction list

定义1 项i的外部效用［8］表示为eu（i），是DB效用表中i的效用值。例如，在表1 中，项a的外部效用eu（a）=9。

定义2 事务T中项i的内部效用［8］表示为iu（i，T），是DB的事务表中与T中i相关联的计数值。例如在表2 中，事务T1中项a的内部效用iu（a，T1）=5。

定义3 事务T中项i的效用［6］表示为u（i，T），是iu（i，T）和eu（i）的乘积，其中u（i，T）=iu（i，T）×eu（i）。例如，事务T1中项a的效用，为u（a，T1）=iu（a，T1）×eu（a）=5×9=45。

定义4 事务T中项集X的效用［6］表示为u（X，T），是项集X中所有项的效用之和，其中X⊆T。例如，事务T1中项集｛ab｝的效用，u（｛ab｝，T1）=u（a，T1）+u（b，T1）=5×9+3×7=66；事务T3中项集｛ab｝的效用，u（｛ab｝，T3）=u（a，T3）+u（b，T3）=9×9+3×7=102。

定义5 项集X的效用［7］表示为u（X），是数据库DB中所有包含X的事务T中，项集X的效用之和。例如，项集｛ab｝的效用为｛ab｝在事务T1中的效用加上｛ab｝在事务T3中的效用，即u（｛ab｝）=u（｛ab｝，T1）+u（｛ab｝，T3）=66+102=168。

定义6 事务T的效用［7］表示为tu（T），是T中所有项的效用之和（如式（1）所示）。

其中数据库DB的总效用是DB中所有事务的效用之和。

表2 显示了每个事务的效用，例如，事务T1的效用为tu（T1）=u（a，T1）+u（b，T1）+u（d，T1）=9×5+7×3+1×1=67。表2中数据库的总效用是409。如果u（X）不小于用户指定的最小效用阈值（用minutil表示），或者不小于minutil与被挖掘数据库的总效用（如果minutil是一个百分比）的乘积，则项集X是高效用项集［8］。给定一个数据库和一个最小效用阈值minutil，HUIM 问题是从数据库中发现效用不小于minutil的所有项集［11］。

定义7DB中项集X的事务加权效用（transactionweighted utility）［9］记为twu（X），是数据库DB中包含项集X的所有事务的效用之和（如式（2）所示）。如表1 所示，项集｛a｝的事务加权效用twu（｛a｝）=

tu（T1）+tu（T2）+tu（T5）=67+125+74=266。

1.2 智能优化算法

1.2.1 PSO 算法

PSO 算法是针对连续优化问题提出的［30-31］，但通过二进制编码可以得到离散变量的PSO 形式，因此也可用于离散系统中组合优化问题的求解。PSO 算法实现步骤如图2 所示。

图2 PSO算法的基本流程Fig.2 Basic flow of PSO algorithm

设待求解的优化问题维数为N，粒子群体规模为M。在PSO 中，xi=(xi1，xi2，…，xiN)表示第i个粒子的位置，vi=（vi1，vi2，…，viN）表示第i个粒子的速度，pbesti=（pbesti1，pbesti2，…，pbestiN）表示第i个粒子所搜寻到的最好的位置，gbest=（gbest1，gbest2，…，gbestN）表示整个群体搜寻到的最好的位置。

首先，随机初始化粒群的位置和速度，计算每个粒子的适应度函数值，一般地，在基于PSO 的HUIM 中，项集X的适应度函数值由其效用值确定［17］，如式（3）所示：

接着，计算并更新每个粒子的最好位置（pbest）和整个群体或邻域内的最好位置（gbest），根据式（4）（5）更新粒子的速度或位置，即更新候选项集，这也是相应HUIM 各算法之间的不同之处（将在2.1 节详细阐述）。若达到终止条件，即产生的HUI 在一定的时间内是重复的（即算法收敛）或者达到了一定的循环次数，算法停止；否则，算法进入循环，直到满足停止条件为止。

其中i=1，2，…，M（M为粒子群体规模）；d=1，2，…，N（N为待求解的优化问题维数）；c1、c2为学习因子；t为迭代次数；r1和r2是在［0，1］上服从均匀分布的随机数；ω是权重惯性系数，能够实现PSO 全局探索和局部开发能力的平衡。

1.2.2 遗传算法

遗传算法可以解决高度复杂的非线性问题［32］。它用于研究非常大的问题空间，在多重约束下根据适应度函数找到最佳解决方案。遗传算法从大量可行的解决方案开始，并通过交叉和变异找到更好的解决方案［17］。

遗传算法的基本流程如图3 所示。

图3 遗传算法的基本流程Fig.3 Basic flow of genetic algorithm

首先，给出一个有N个染色体（解的编码）的初始群体pop（1），对群体pop（t）中的每一个染色体popi（t）计算它的适应度函数值，与基于PSO 的HUIM 类似，在基于GA 的HUIM中，项集X的适应函数值由其效用值确定，如式（3）所示。若满足停止规则，算法停止，此时的种群即为HUI；否则，根据式（6）计算概率Pi，并以概率Pi从pop（t）中随机选择一些染色体（Chromosome）构成新的种群pop（t+1）。

以概率Pc进行交叉操作得到一个有Numr个染色体的crosspop（t+1），以较小的概率Pm，使得一个染色体的基因发生变异，形成mutpop（t+1）。根据式（7）得到一个新的种群，算法返回，计算新种群的适应度函数值，直到满足停止条件。通常，在HUIM 中，算法停止的条件为没有新的HUI 产生（即算法收敛）或者循环达到了一定的次数。

2 基于群智能优化算法

2.1 基于粒子群优化算法

粒子群优化算法具有模型简单、控制参数少、易于实现、运行速度快等优点，因此被广泛用于HUI 的挖掘工作中，并取得了可观的效果。本节从粒子更新策略的角度对基于粒子群优化算法的HUIM 方法进行了综述。

传统的粒子更新策略仅使用式（4）（5）对粒子进行速度和位置的更新。Pears 等［33］提出WARM SWARM（Weighted Association Rule Mining using particle SWARM optimization）方法，将粒子群优化与加权关联规则挖掘相结合，使用粒子群优化为关联规则挖掘分配有意义的项目权重。实验结果表明，虽然使用粒子群优化进行权重拟合有一定的开销，但该方法也明显快于标准Apriori，且可以产生有趣和有意义的规则，当数据集的大小增加时，这一点尤其明显。Sivamathi等［34］提出了SCE-PSO（Shuffled Complex Evolution of PSO）方法，首先在可行空间中随机抽取一组粒子，然后将种群划分为若干个复合体，在每个复合体中使用PSO 算法挖掘HUI。

基于sigmoid函数的粒子更新策略可以使种群具有较高的多样性。Lin 等［20］首次采用了二进制粒子群优化（Binary Particle Swarm Optimization，BPSO）［35］算法有效地挖掘HUI，提出了一种基于PSO 的HUIM-BPSOsig 方法。首先基于事务加权效用模型，将发现的高事务加权效用1-项集（High Transaction Weighted Utilization 1-Itemsets，1-HTWUIs）的数量设置为粒子的大小，大幅减少了进化过程中的组合问题。以表2 中的数据库为例，假设最小效用阈值为200，根据表1，将1-项集｛e｝从数据库中删除，找到的1-HTWUIs有｛a｝、｛b｝、｛c｝、｛d｝，粒子大小即为4。在粒子的编码阶段，利用位图编码项集，每个粒子由一组二进制变量组成，如0或1，表示粒子中存在或不存在相应的项。例如项集｛b，c｝可以用图4来表示。

图4 粒子位图编码Fig.4 Particle bitmap encoding

在粒子的更新阶段，利用式（1）更新粒子的速度，再采用sigmoid 函数更新粒子的位置，如式（8）所示：

其中：rand（·）生成（0，1）的随机数；t代表迭代次数为第i个粒子的第j个位置的位置代表第i个粒子的第j个位置的速度。

Lin 等［18］设计了HUIM-BPSO 方法，在HUIM-BPSOsig 的基础上添加了OR/NOR-tree 结构，通过提前修剪粒子的无效组合减少多次数据库扫描。例如表2 中的数据库可以用OR/NOR-tree 表示为图5。

图5 OR/NOR-tree结构Fig.5 OR/NOR-tree structure

这个过程可以减少无效粒子（即原始数据库中不存在的粒子）的计算，进而有效地从非常紧凑的数据集中识别完整的HUI。Gunawan 等［36］提出一种无需最小效用阈值挖掘高效用项集的HUIM-BPSO-nomut 方法，基于BPSO 算法将所有项集输出为按效用排序的列表，最小效用阈值则作为后续处理步骤施加在此列表之上。将具有最高效用的事务作为粒子的初始种群，并根据式（9）更新速度，然后将粒子的最大速度限制为vmax，确保每个速度分量都保持在特定的范围内，最后利用sigmoid 函数更新粒子位置（式（8））。

其中k为收缩因子，在全局最佳粒子与局部最佳粒子之间起到平衡作用。k的设置如式（10）所示：

靳晓乐等［37］对基本二元粒子群算法进行改进，提出一种双重二元粒子群优化（Double Binary PSO，DBPSO）算法。运用最小相对效用阈值和效用上界的乘积确定最小效用阈值，然后通过最小效用阈值和适应度函数分散候选子空间，挖掘HUI。

基于贪心的算法倾向于将粒子向最优的位置移动。Song 等［38］提出了一个基于仿生算法的HUIM 通用框架Bio-HUIF（Bio-inspired-algorithm-based HUIM framework）以及PEVC（Promising Encoding Vector Check）检测策略，基于此提出了Bio-HUIF-PSO 方法。在该方法中，随机初始化多个粒子，利用式（11）更新粒子的速度，每个粒子向最优值移动，所有的粒子都重复更新其速度和位置，直到找到最优解或达到最大的迭代次数。该算法可以找出90%以上的HUI，比UP-Growth［39］快两个数量级。

其中vi1始终为1，vi2和vi3由式（12）（13）给出：

其中：BitDiff表示两个向量之间的差异；r1和r2与式（4）中设置相同，为（0，1）内的随机数；xi为粒子所在的位置。

轮盘赌选择法的基本思想是个体被选中的概率与其适应函数值成正比。Song 等［23］提出了两种方法用于发现HAUI：一种是基于标准PSO 的HAUI-PSO 方法，这是PSO 在HAUI 挖掘中的首次应用；另一种是基于生物计算框架的HAUI-PSOD（High Average-Utility Itemset mining based on PSO with the Diverse optimal value framework of Bio-HUIF）方法，使用式（14）对发现的HAUI 应用轮盘赌选择以确定全局最佳值，而不是在下一个种群中保持当前最佳值，增加了种群内的平均多样性，并提高了挖掘的效率和质量。

其中：fitnessi表示第i个粒子的适应度函数值，|SHAUI|是所发现的HAUI 数，PLi为该粒子被选择的概率。

王常武等［40］提出HUIM-IPSO（High Utility Itemset Mining algorithm based on Improved PSO），通过轮盘赌选择机制在当前的HUI 的种群中以一定的概率选择下一代种群的初始值，增加了种群的多样性，可以获得更多的项集。

与BPSO 不同，Chen 等［41］提出了基于集合的粒子群优化方法S-PSO（Set-based PSO），根据速度向量中值更高的元素改变其对应的位置元素，而不是简单地通过sigmoid 函数更新。基于S-PSO，Song 等［42］提出了HUIM-SPSO（High Utility Itemset Mining based on S-PSO）方法。为了衡量整个种群的多样性，提出了位编辑距离（Bit Edit Distance，BED）、最大位编辑距离（Maximal BED，Max_BED）和平均位编辑距离（Average BED，Ave_BED），如式（15）～（17）所示。该算法具有更高的多样性，在相同的迭代次数内可以挖掘出多的高效用项集。

其中：NBits是由位置向量x变化到xt所使用的按位取反操作的次数；xi=（xi1，xi2，…，xiN）为一个种群中的位置向量；N为待求解的优化问题维数。

2.2 基于蚁群算法

与GA 和PSO 不同，ACO 算法以建设性的方式产生可行的解决方案，因而被应用于HUIM 中。本节从所挖掘模式的类型的角度梳理总结了基于蚁群算法的HUIM。式（18）代表第k只蚂蚁在t时刻从状态i转移到状态j的概率，式（19）表示信息素的更新规则。

其中：allowedk表示第k只蚂蚁下一步允许选择的状态；τij为t时刻状态i到状态j的信息素强度；ηij（t）为启发函数；α为启发式因子，表示轨迹的相对重要性；β为期望启发式因子，表示能见度的相对重要性；ρ∈［0，1）为信息素挥发系数，1-ρ为信息素残留因子；m表示蚁群的大小。

对于普通HUIM 问题，Wu 等［43-44］提出了基于ACO 的方法HUIM-ACS 来高效挖掘HUI。算法将原始数据库映射到路由图中（图6 为图2 中数据库的路由图表示，其中S为源点），采用式（21）作为状态i到状态j的启发式函数，并采用积极剪枝和递归剪枝两种策略加速算法的收敛，以保证在处理过程中不会考虑相同的可行解。Seidlova 等［45］讨论了蚁群方法的一种变体Ant-Miner，为超大型数据库中的营销和商业智能提供解决方案。

图6 路由图Fig.6 Route map

其中：twuij为项集｛i，j｝的事务加权效用；etwuij为项集｛i，j｝的估计事务加权效用。etwuij如式（22）所示：

其中：Ti是下一个候选项集的子集，Ti中的每一个项y在之前都已经被计算过其事务加权效用值。

不频繁项集不经常出现但会带来巨大的利润，因此，高效用不频繁项集的挖掘工作是非常重要的。Arunkumar等［46］提出了基于自定义蚁群算法的ACHUIIM（Ant Colony based High Utility Infrequent Itemset Mining），有效地发现高效用的不频繁项集。

此外，蚁群算法还可以用来挖掘闭合高效用项集。Pramanik 等［47］提出了CHUI-AC（Closed High Utility Itemsets mining using Ant Colony algorithm），首次使用自启发的蚁群算法挖掘CHUI。如式（23）所示，算法使用全局信息素更新规则以增加路径上的信息素；此外，算法将可行解空间映射到具有二次空间复杂度的有向图，以有效地指导搜索。

其中：ubest是特定迭代中效用最高的项集的效用，h是效用阈值。

2.3 基于其他群智能优化算法

在群智能优化算法中，人工蜂群算法、蝙蝠算法（Bat Algorithm，BA）、灰狼优化（Grey Wolf Optimization，GWO）算法［48］、人工鱼群算法等也被应用于HUIM，并能够取得较好的挖掘效果。

Song 等［21］提 出HUIM-ABC（HUIM based on the ABC algorithm），使用ABC 算法对HUIM 问题进行建模，利用位图进行信息表示和搜索空间的剪枝，加速HUI 的发现过程。引领峰根据采蜜经验，在邻域范围内利用式（24）产生一个新位置，并利用式（3）计算当前位置的适应度函数值，作为新位置的蜜源质量。若蜜源质量高于原蜜源质量，则新位置代替原位置。该方法采用直接蜜源生成（Direct Nectar Source Generation，DNSG）策略，通过所发现的HUI 的数量信息生产新的候选花蜜，从而可以在更少的迭代周期内发现更多的HUI。

其中：vij是新位置；xij是原位置；xkj是随机选取的邻居蜜源位置；φ是［-1，1］上服从均匀分布的随机数；k=｛1，2，…，M｝（M为种群规模）；j=｛1，2，…，N｝（N表示待求解的优化问题的维数）。

BA 的思想源于对蝙蝠高级回声定位能力的模拟。BA 把蝙蝠个体看作分布在搜索空间中的解，模拟蝙蝠能够在复杂环境中精确捕获食物的机制来解决优化问题。应用Bio-HUIF框架，Song 等［38］提出Bio-HUIF-BA 方法，将BA 用于HUI 的挖掘中。首先，在搜索空间随机分布若干个蝙蝠，确定种群个体的初始位置和初始速度，对种群各个蝙蝠进行适应度评价，寻找出最优个体位置gbest。然后，利用式（25）～（27），通过调整频率产生新的解并修改个体的飞行速度和位置。

其中：fi为蝙蝠i的发射频率；fmin和fmax分别是所有蝙蝠发出脉冲的最小和最大频率；β∈［0，1］是一个随机数；vi（t）和vi（t+1）是第i只蝙蝠在第t次和第t+1 次迭代时的速度；xi（t）和xi（t+1）是第i只蝙蝠在第t次和t+1 次迭代时的位置。

如式（28）（29）所示，蝙蝠在寻优过程中，通过调节脉冲发生率和响度促使蝙蝠朝着最优解方向移动。

其中：Ai（t）和Ai（t+1）代表第t次迭代和t+1 次迭代时的脉冲发射响度，ri（0）是脉冲发射率，α（0＜α＜1）为声波响度衰减系数，γ（γ＞0）为脉冲频度增强系数。所有的蝙蝠反复更新它们的速度、位置、响度和脉冲发射率，直到找到最佳解决方案或达到最大迭代次数。Bio-HUIF-BA 方法比UP-Growth 快一个数量级，可以找出90%以上的HUI。

GWO 算法［48］模拟自然界中灰狼种群等级机制和捕猎行为。通过4 种类型的灰狼（α，β，δ，ω）模拟社会等级，并基于狼群跟踪、包围、追捕、攻击猎物等过程模拟狼的捕猎行为，实现优化搜索目的。GWO 因其原理简单、并行性、易于实现、需调整的参数少且有较强的全局搜索能力等特点，被修改为使用布尔运算符以解决HUIM 问题。Pazhaniraja 等［49］提出了一种基于灰狼生物学行为的优化模型BGWO（Boolean operatorsbased modified GWO algorithm），使用加法器、差分器、多路复用器、环形移位器和德摩根与运算等5 种不同的布尔运算对连续GWO 进行转换。每个运算符都被重新定义以减少运算时间，从而可以在大型数据库中高效地挖掘HUI。与其他算法类似，BGWO 使用二进制位图编码项集，使用式（3）计算其适应度函数。与标准GWO 算法不同，修改后的GWO 算法不具备任何确保整个搜索在边界区域内进行的边界检查程序。

人工鱼群算法将动物自治体的概念引入优化算法，使得该算法的自下而上的寻优模式具有良好的全局优化能力。由于该算法对初始值和参数的选择不敏感，具有鲁棒性强、简单易实现等优点，Song 等［22］从AF 算法的角度研究了HUIM 问题，并提出了HUIM-AF 方法。用人工鱼的跟随、集群和捕食这3种行为对HUIM问题进行建模，以有效挖掘HUI。

2.4 小结

基于群智能优化算法的HUIM 方法基本上使用相同的数据集，为了更好地比较它们的性能，表3 列举了这些数据集的参数。

表3 数据集参数Tab.3 Parameters of datasets

表4对基于群智能优化算法的HUIM 方法进行了比较，其中，ω为权重惯性系数，c1与c2为学习因子，ND为迭代次数，M为种群大小，γ是信息素蒸发参数，τ为信息素量，ρ是调整信息素密度的参数，α和β是决定信息素对两个节点之间距离的相对影响的两个参数，q是平衡参数，Mn为花蜜源的数量。从表4中可以看出，虽然基于PSO 的HUIM 方法参数更少，可以很容易地实现；但在稀疏数据集中，由于粒子群是随机“跳变”的，得到的粒子很大一部分是数据集中不存在的，处理这些粒子会造成多余计算，因此PSO算法在稀疏数据集中性能普遍较差。

表4 基于群智能优化算法的HUIM方法总结Tab.4 Summary of HUIM methods based on swarm intelligence optimization algorithms

HUIM-BPSOsig 的时间复杂度为O(ND×M×m)，其中ND为迭代次数，M为种群大小，m为每个粒子的大小，即1-HTWUI的数量。变量ND和M可以由用户调整，1-HTWUI的数量由最小效用阈值决定。HUIM-BPSO 比HUIM-BPSOsig 多了OR/NOR-tree 结构，在进化过程中可以避免无效组合，因此可以大幅改进粒子在进化过程中的计算，因此在相同数据集条件下，HUIM-BPSO 比HUIM-BPSOsig 更快。在chess 数据集上，与HUIM-BPSOsig 相比，HUIM-SPSO 的耗时减少了66.1%，与HUIM-BPSO 相比减少了60.3%；在mushroom 数据集 上，HUIM-BPSOsig 的执行时间 为HUIM-SPSO 的10 倍，HUIM-BPSO 的执行 时间为HUIM-SPSO 的8.01 倍［42］。HUIM-SPSO 倾向于以高速改变位置元素，而不是简单地应用sigmoid 函数更新粒子，能够在保证种群多样性的前提下，贪心地进行收敛。因此，HUIM-SPSO比应用sigmoid函数更新的HUIM-BPSOsig 以及HUIM-BPSO 更快。SCE-PSO 的时间复杂度 为O（ND×M×m/p），其 中p为分区 数，因 此SCE-PSO 比HUIM-BPSOsig更快。

在基于GA 的方法中，HUPEumu-GRAM 方法需要O（M）时间通过轮盘赌机制选择两条染色体，需要O（m）时间对新染色体执行交叉和变异操作。因此，它需要O（M+m）时间生成新的后代，并且总时间复杂度为O（ND×M×（M+m））。从上述分析来看，基于PSO的HUIM方法普遍比基于GA的方法更快。

3 基于进化算法

本章把基于进化算法（EA）的高效用项集挖掘方法分为基于遗传算法和基于仿生算法的HUIM 进行总结分析。

Kannimuthu 等［17］提出了HUPEUMU-GARM 方法，使用最小效用阈值进行排序变异，利用遗传算法挖掘HUI。在该方法中，用户将最小效用阈值与事务数据库一起输入，使用式（30）进行变异。负效用在现实生活中具有重要意义［50］，HUPEUMU-GARM方法首次将遗传算法应用于带有负项目值的HUI挖掘中。此外，Kannimuthu 等［17］还提出了HUPEWUMU-GARM 方法，在不使用最小效用阈值的情况下挖掘HUI。

其中：Pmu为突变概率，为最大的变异率，为最小变异率，Di为当前迭代次数，T为最大迭代次数，Rank为当前的等级，R为总的等级数。

在隐私 保护数 据挖掘［51］中，Lin 等［52］提出名 为PPUMGAT+（Privacy-Preserving Utility Mining based on GA Technique using Pre-large concept）的方法挖掘敏感的HUI。它不仅可以根据用户指定的最小效用阈值生成高质量的盈利项集，而且在现实应用中具有保护隐私和安全信息的能力。基于进化的算法在事务数据库中找到完整的HUI 仍然很耗时，为了解决这个问题，Zhang 等［53］提出HUIM-IGA（HUIM algorithm based on an Improved GA）来有效地挖掘HUI。该算法对重复的HUI 采用了邻域探索策略，从而提高了算法的局部搜索能力。利用种群多样性维护策略，以扩大搜索空间，提高了种群多样性，从而避免因局部条件不成熟而导致的HUI 缺失。

Lin 等［24］提出了一种基于GA 的HUIM 方法DcGA，使用一个紧凑的遗传算法模型，在有限的时间内挖掘CHUI。该算法用估计分布策略预测种群在解空间的运动，而不是通过简单的交叉和变异操作估计交叉率和变异率。群体中的每个个体都用概率向量进行编码，代表了群体中每个基因存在的比例。算法找到闭合频繁项集（Closed Frequent Itemsets，CFIs）之后，将数据库中存在的每个项的概率pi初始化为0.5，从CFIs 中生成两个染色体，利用式（3）计算其适应度函数值，值较大的为winner，较小的为loser。利用式（31）进行概率的更新。

其中：k=1，2，…，n，n为数据库中项集的个数；winner［k］为向量winner的第k维。

Pazhaniraja 等［54］利用海 豚回声 定位优 化（Dolphin Echolocation Optimization，DEO）算法在较大的数据集中有效地挖掘高效用项集，提出了HUIM-DEO 方法。

差分进化长期以来被成功应用于解决高维问题，Krishna等［55］将差分进化用于高效用关联规则挖掘，在此上进行延伸，提出了BDE-HUIM（High Utility Itemset Mining using Binary Differential Evolution）算法［56］，利用差分进化挖掘HUI。

4 基于其他智能优化算法

本章汇总了除基于群智能优化算法和进化算法以外的其他HUIM 方法，分别是基于多目标优化算法（Multi-Objective Evolutionary Algorithm，MOEA）、基于交叉熵和基于仿自然优化的HUIM。

在HUIM 中，项集的效用和支持度经常存在着冲突，换句话说，频繁项集的效用可能会很低，效用较高的项集往往不频繁。MOEA 具有同时优化多个目标的特性［57］，因此可以很好地解决上述问题。常见的MOEA 框架有MOEA/D（Multi-Objective Evolutionary Algorithm based on Decomposition）［58］、NSGA-Ⅱ（Non-dominated Sorting Genetic Algorithm Ⅱ）［59］、SPEA2（Strength Pareto Evolutionary Algorithm improved version）［60］等。

基 于MOEA/D，Zhang 等［61］提出了MOEA-FHUI（Multi-Objective Evolutionary Approach for mining Frequent and High Utility Itemsets），首次将挖掘频繁高效用项集的问题转化为同时最大化支持度和效用的多目标优化问题，且不需要指定最小支持度阈值minsup和最小效用阈值minutil等先验参数。该方法提出了一种特定的种群初始化策略。假设种群的大小为N，利用式（32），以概率Pt选择N/2 个事务，利用式（33），以概率Pi选择N/2 个1-项集。通过MOEA/D 框架来进化种群，得到最终的结果。在进化过程中，能够达到种群的收敛性和多样性之间的平衡。

其中：Tj为原始数据库中的事务，u（Tj）为事务Tj的效用，| |

DB为数据库中事务的数目，i为原始数据库中的1-项集，supp（i）为项i的支持度，|I|为数据库中1-项集的个数。

Ahmed 等［62］提 出MOEA-HEUPM（High Expected Utility Patterns in a limit tiMe based on the Multi-Objective EvolutionAry framework）方法，采用多目标进化框架从不确定的数据库中发现有趣的高期望效用模式（High Expected Utility Patterns，HEUPs）。该方法不需要最小效用阈值和最小不确定阈值，利用基于权重的（Tchebycheff）算法来快速获得基于多目标（效用和不确定性）机制的非主导解决方案。Cao 等［63］提 出 CP-MOEA（Closed itemset Property based Multi-Objective Evolutionary Approach），采用与NSGA-Ⅱ类似的框架，同时优化支持度和效用两个目标，用于挖掘频繁高效用项集。基于闭合项集的性质，设计了两种个体更新策略USC（Updating Strategy based on Closed itemsets）和USA（Updating Strategy based on Approximate-closed itemset）加速种群收敛，提高种群多样性。

Fang 等［64］提出MOEA-PM（MOEA for high quality Pattern Mining），采用改进的多目标进化算法，利用式（34）对种群进行进化，挖掘事务数据库中同时满足高支持度、高占用率、高效用的模式。

其中：occu（X）为项集X的占用率，u(X)为X的效用，twu()为事务加权效用。

Song 等［25］提出了两种基于交叉熵的方法，分别是TKU-CE 和TKU-CE+，用于启发式地挖掘top-kHUI。首先，通过临界效用值过滤没有希望的项，避免了额外的数据结构和阈值提高策略所带来的计算成本；其次，在每次迭代中使用样本细化策略，以减少迭代阶段的计算负担；最后，提出了平滑变异，随机生成一些新的项集，提高了样本的多样性，可以用更少的迭代发现更多的top-kHUI。

为了解决算法运行时间长可能会错过许多HUI 的问题，Nawaz 等［13］基于爬山法和模拟退火（Simulated Annealing，SA）提出了两种方法，即HUIM-HC（HUIM based on Hill Climbing）和HUIM-SA（HUIM based on SA）。将数据库转换为位图的形式以进行高效的效用计算和搜索空间的修剪。在迭代过程中发现的HUI 被用作下一个种群的目标值，提高了种群的多样性。

5 结语

本文以智能优化算法的类别为角度，把基于智能优化算法的HUIM 方法分为基于群智能优化算法、基于进化算法以及基于其他算法的HUIM，并作了详细的分析与总结；首次从粒子更新策略的角度，把基于粒子群优化算法的高效用项集挖掘算法分为五类，包括基于传统更新策略、基于sigmoid 函数、基于贪心、基于轮盘赌以及基于集合的HUIM；从项集的角度，把基于蚁群算法的HUIM 分3 个类别进行介绍，包括面向普通高效用项集、面向不频繁的高效用项集和面向闭合高效用项集的HUIM；把基于进化算法的HUIM 分为基于遗传算法和基于仿生算法的HUIM；最后列举了其他智能优化算法在高效用项集中的应用，分别是MOEA、交叉熵和仿自然优化算法。

基于智能优化算法的高效用项集挖掘虽然已经取得了一定的成果，但是现有的方法仍然存在着不足之处，这为研究者提供了下一步的研究方向。

1）在数据流上用智能优化算法挖掘HUI。

目前的基于智能优化算法的HUIM 方法仅在静态数据中挖掘，而对数据流中的高效用项集的关注较少。由于传感器数据、社交网络服务数据、Web 访问日志数据等各种流数据已经成为获取现实世界中有价值信息的重要数据，流模式已经成为关联规则挖掘中的一项重要技术［65］。下一步，将尝试把智能优化算法应用于数据流中的HUI 的挖掘，通过应用滑动窗口技术和树结构分批次处理和存储数据流中的项集，然后选择合适的智能优化算法挖掘HUI。

2）改进基于智能优化算法的HUIM 的剪枝策略。

基于智能优化算法的HUIM 中，具有剪枝策略的算法屈指可数，可以以优化剪枝策略的方式，进一步加快挖掘速度。现有的剪枝策略会对没有希望的项集提前剪枝，但这样会降低种群多样性。因此，如何在剪枝与多样性之间去做一个折中是一个具有挑战性的任务。此外，智能优化算法具有较强随机性，在稀疏数据集中的表现欠佳。针对以上问题，作者将改进基于智能优化算法的HUIM 的剪枝策略，提高算法在稀疏数据集中的性能。

3）自适应地挖掘HUI。

算法中参数的不同会对结果造成很多的影响［66］，同样，智能优化算法中的参数设置也会影响最终的挖掘结果。在挖掘过程中，初始设置的最优参数可能在挖掘一段时间后会陷入局部最优，从而导致丢失HUI。未来的研究中，将设计一种自适应变换参数的基于智能优化算法的HUIM。

4）智能优化算法在HUIM 上的更广泛应用。

在现有的基于智能优化的HUIM 算法中，所应用的智能优化算法的种类较少。目前仅应用了蚁群算法、遗传算法、粒子群优化算法、蝙蝠算法等少数算法。另外，基于智能优化算法的HUIM 具有速度快、启发式挖掘的特点，非常适合挖掘各种复杂的高效用项集。下一步，会将多种类型的智能优化算法应用于挖掘更多复杂类型的高效用项集中。