基于长度约束的蝙蝠高效用项集挖掘算法

为了挖掘满足用户特殊需求，如含指定项目数量的高效用项集（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，并减少挖掘模式的数量。     

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

高效用项集挖掘（HUIM）能够挖掘事务数据库中具有重要意义的项集,从而帮助用户更好地进行决策。针对智能优化算法的应用能够显著提高海量数据中高效用项集的挖掘效率这一现状,对基于智能优化算法的HUIM方法进行了综述。首先,以智能优化算法的类别为角度,从基于群智能优化、基于进化以及基于其他智能优化算法的方法这3个方面对基于智能优化算法的HUIM方法进行了详细的分析与总结。同时,从粒子更新方式的角度对基于粒子群优化（PSO）的HUIM方法进行了详细梳理,包括基于传统更新策略、基于sigmoid函数、基于贪心、基于轮盘赌以及基于集合的方法。另外,从种群更新方法、对比算法、参数设置、优缺点等角度对比分析了基于群智能优化算法的HUIM方法。然后,从遗传和仿生两个方面对基于进化的HUIM方法进行总结概括。最后,针对目前基于智能优化算法的HUIM方法所存在的问题,提出了下一步的研究方向。     

基于数据索引结构的跨级高效用项集挖掘算法

针对现有的跨级高效用项集挖掘（HUIM）算法非常耗时且占用大量内存的问题，提出一种基于数据索引结构的跨级高效用项集挖掘算法（DISCH）。首先，为了高效存储和快速检索到搜索空间中的所有项集，拓展带有分类信息和索引信息的效用链表为数据索引结构（DIS）；然后，为了提高内存利用率，对不满足条件的效用链表所占的内存进行回收再分配；最后，在构建效用链表时使用提前结束策略，以减少效用链表的产生。基于真实零售数据集和合成数据集进行的实验结果表明，与CLH-Miner(Cross-Level High utility itemsets Miner)算法相比，DISCH在运行时间上平均降低了77.6%，同时在内存消耗上平均降低了73.3%，可见该算法能高效完成跨级高效用项集的搜索，并且降低算法的内存消耗。     

含负项top-k高效用项集挖掘算法

含负项高效用项集（HUI）挖掘是新兴的数据挖掘任务之一。为了挖掘满足用户需求的含负项HUI结果集,提出了含负项top-k高效用项集（THN）挖掘算法。为了提升THN算法的时空性能,提出了自动提升最小效用阈值的策略,并采用模式增长方法进行深度优先搜索;使用重新定义的子树效用和重新定义的本地效用修剪搜索空间;使用事务合并技术和数据集投影技术解决多次扫描数据库的问题;为了提高效用计数的速度,使用效用数组计数技术计算项集的效用。实验结果表明,THN算法的内存消耗约为HUINIV-Mine算法的1/60,约为FHN算法的1/2;THN算法的执行时间是FHN算法的1/10;而且该算法在密集数据集上的性能更好。     

HHUIM：一种新的启发式高效用项集挖掘方法

针对基于启发式的高效用项集挖掘算法在挖掘过程中可能丢失大量项集的问题,提出一种新的启发式高效用项集挖掘算法HHUIM。HHUIM利用哈里斯鹰优化算法进行种群的更新,能够有效减少项集的丢失。提出并设计了鹰的替换策略,解决了搜索空间较大的问题,降低了适应度函数值低于最小效用阈值的鹰的数量。此外,提出存储回溯策略,可有效防止算法收敛过快达到局部最优。大量的实验表明,所提算法优于目前最先进的启发式高效用项集挖掘算法。     

基于项集归减的高维频繁高效用项集挖掘多目标优化方法

频繁高效用项集挖掘是数据挖掘的一项重要任务,挖掘到的项集由支持度和效用这2个指标衡量.在一系列用于解决这类问题的方法中,进化多目标方法能够提供1组高质量解以满足不同用户的需求,避免传统算法中支持度和效用的阈值难以确定的问题.但是已有多目标算法多采用0-1编码,使得决策空间的维度与数据集中项数成正比,因此,面对高维数据集会出现维度灾难问题.鉴于此,设计一种项集归减策略,通过在进化过程中不断对不重要项进行归减以减小搜索空间.基于此策略,进而提出一种基于项集归减的高维频繁高效用项集挖掘多目标优化算法(IR-MOEA),并针对可能存在的归减过度或未归减到位的个体提出基于学习的种群修复策略用以调整进化方向.此外还提出一种基于项集适应度的初始化策略,使得算法在进化初期生成利于后期进化的稀疏解.多个数据集上的实验结果表明,所提出算法优于现有的多目标优化算法,特别是在高维数据集上.     

基于Spark的并行化高效用项集挖掘算法

针对传统基于链表结构的Top-K高效用挖掘算法在大数据环境下不能满足挖掘需求的问题,提出一种基于Spark的并行化高效用项集挖掘算法(STKO)。首先从阈值提升、搜索空间缩小等方面对TKO算法进行改进;然后选择Spark平台,改变原有数据存储结构,利用广播变量优化迭代过程,在避免大量重新计算的同时使用负载均衡思想实现Top-K高效用项集的并行挖掘。实验结果表明,该并行算法能有效地挖掘出大数据集中的高效用项集。     

一种基于划分的高效用长项集挖掘算法

效用（utility）可弥补支持度在表现语义重要性方面的不足。现有的几种基于效用的关联规则挖掘算法都采用了类似Apriori自底向上的搜索方法,不适合长模式的挖掘。提出了一种双向搜索高效用项集的模型及一种基于划分的inter-transaction算法。inter-transaction利用了长事务相交迅速变短的特性和新的减枝策略,能同时输出项集的效用与支持度。实验表明,该方法对蕴含长模式的高维数据库非常有效。     

基于M-H采样的快速反向微分进化算法

反向微分进化(ODE)算法基于反向优化对种群进行初始化更新以保持种群多样性。但该算法中反向个体容易偏离全局最优个体,不能很快达到全局最优,在函数优化过程中收敛速度慢且容易陷入局部最优。为此,提出一种基于M-H采样的快速反向微分进化算法。M-H采样用于ODE算法的变异操作,满足马尔可夫链可逆条件。马尔可夫链的一步转移概率根据个体等级分配的选择概率进行计算,既能选择最优个体,又能寻找优化方向并保持种群多样性。仿真结果表明,M-H采样得到的个体具有马尔可夫链平稳分布特性,该算法在单峰函数和多峰函数优化中都能快速收敛,全局和局部搜索性能达到平衡,具有较高的搜索精度及较好的鲁棒性。     

面向数据流的一个高效用项集挖掘算法

近年来,在数据流中进行高效用项集挖掘成为一个重要的研究课题。已存在的算法在挖掘过程中产生大量的候选项集,使用户很难从大量候选模式中筛选出有用的信息。针对这种情况,提出一个数据流高效用项集挖掘算法HUIDE(High-Utility Itemsets Over Data Streams)。算法首先综合考虑数据的信息特征,提出一种有效的效用度量方法。然后采用基于时间的滑动窗口技术更加准确地描述数据分布,构建一种树结构HUI-tree(High Utility Itemsets tree)。最后遍历构建的树结构HUI-tree挖掘高效用项集。在人工和真实数据流上的实验结果表明该算法通过扫描一次数据库获取挖掘结果,减少了候选项集的产生及时间和空间的消耗。该算法在数据流中能够有效地挖掘高效用项集。     

基于多策略融合的混合多目标蝗虫优化算法

为提高蝗虫优化算法（GOA）求解多目标问题的性能，提出一种基于多策略融合的混合多目标蝗虫优化算法（HMOGOA）。首先，利用Halton序列建立初始种群，保证种群在初始阶段具有均匀分布和较高多样性；然后，通过差分变异算子引导种群变异，促进种群向优势个体移动同时进行更大范围寻优；最后，利用自适应权重因子根据种群优化情况动态调整算法全局搜索和局部寻优能力，提高优化效率及解集质量。选取7个典型函数进行实验测试，并将HMOGOA与多目标蝗虫优化、多目标粒子群（MOPSO）、基于分解的多目标进化（MOEA/D）及非支配排序遗传算法（NSGA Ⅱ）对比分析。实验结果表明，该算法避免了其他四种算法的局部最优问题，明显提高了解集分布均匀性和分布广度，具有更好的收敛精度和稳定性。     

基于小生境的混沌变异差分进化算法

针对高维复杂函数的优化问题,提出了基于小生境的混沌变异差分进化算法（CNDE）。算法结合小生境策略,使子种群高效独立地进行搜索,并引入混沌变异进行精细的遍历搜索,在运行中根据迭代次数自动地调整交叉概率因子从而使搜索的初始阶段提高种群多样性,而在搜索后期加强局部搜索能力。对3种经典函数的测试表明,新算法不仅具有很强的全局搜索能力,而且能有效避免早熟收敛问题。     

针对混合变量优化问题的协同进化蚁群优化算法

针对由连续变量和分类变量构成的混合变量优化问题（MVOP）,采用协同进化策略来对混合变量决策空间进行搜索,提出了一种协同进化蚁群优化算法（CACOA_MV）。CACOA_MV分别采用连续和离散蚁群优化（ACO）策略生成连续和分类变量子种群,通过合作者来对连续和分类变量子向量进行评价,分别对连续和分类变量子种群进行更新来实现对混合变量决策空间的高效协同搜索。进一步地,利用信息素平滑机制增强对分类变量解空间的全局探索能力,并设计了一种面向协同进化框架的“最佳+随机合作者”的重启策略来提高协同搜索效率。与混合变量的蚁群（ACO_MV）算法和种群规模线性变小的差分进化-蚁群混合变量优化算法（L-SHADE_ACO）的比较表明,CACOA_MV能够进行更有效的局部开发,从而提高最终结果在目标空间中的近似精度;与基于集合的混合变量差分进化算法（DE_MV）相比较,CACOA_MV能够在决策空间中更好地逼近全局最优解,具有更好的全局探索能力。综上,采用协同进化机制的CACOA_MV能有效保持全局探索和局部开发的平衡,从而具有更好的寻优性能。     

求解动态优化问题的多种群竞争差分进化算法

针对动态优化问题（DOP）的求解,提出结合多种群方法和竞争策略的差分进化算法（DECS）。首先,将一个种群作为侦测种群,通过监测种群中所有个体的评价值和种群维度来判断环境是否发生变化。其次,将余下多个种群作为搜索种群,独立搜索环境中的最优值。在搜索过程中,引入排除规则,避免多个搜索种群聚集在同一个局部最优的邻域。在迭代若干代后对各搜索种群执行竞争操作,保留评估值最优个体所在的种群并对该种群的下一代个体生成采用量子个体生成机制,而对其他搜索种群重新初始化。最后,利用7个测试函数的49个动态变化问题对DECS进行验证,并将实验结果与人工免疫算法（Dopt-aiNet）、复位粒子群优化（rPSO）算法、改进差分进化（MDE）算法进行比较。实验结果表明,在49个问题上,DECS有34个问题的平均离线误差期望小于Dopt-aiNet算法,所有问题的平均离线误差期望都小于rPSO算法和MDE算法,因此DECS对DOP求解动态优化问题是可行的。     

基于R-list的Top-K高效用项集挖掘算法

针对现有的一阶段Top-K高效用项集挖掘算法挖掘过程中阈值提升慢,迭代时生成大量候选项集造成内存占用过多等问题,提出一种基于重用链表(R-list)的Top-K高效用挖掘算法RHUM。使用一种新的数据结构R-list来存储并快速访问项集信息,无需第2次扫描数据库进行项集挖掘。该算法重用内存以保存候选集信息,结合改进的RSD阈值提升策略对数据进行预处理,期间采用更严格的剪枝参数在递归搜索的过程中同时计算多个项集的效用来缩小搜索空间。在不同类型数据集中的实验结果表明:RHUM算法在内存效率方面均优于其他一阶段算法,且在K值变化时能保持稳定。     

树-投影关联规则挖掘方法的水平优化与搜索策略研究

基于树-投影的TreeProject关联规则挖掘算法有效解决了现有各种算法在数据量过大时会失效的问题，通过对该算法及相关算法的研究，发现在现有这类算法中存在冗余投影，为此提出的水平优化策略通过消除这种冗余投影，既可减少树-投影的搜索空间，加快频繁项的挖掘；还可减少树-投影算法需要的内存空间，克服了原有树-投影算法对内存要求较大的不足；该优化策略包括挖掘时的合并策略和挖掘后的生成策略两大部分，此外，冗余投影的判断，可从投影数据库T间的关系简化为相应事务编号数据库Tid间的关系，这种简化极大减少了判断的计算量，而且可用于投影，从而使得进行水平优化无需增加额外开销，基于水平优化策略的HOP-TreeProject算法从时间和空间上都对现有的树一投影算法有很大改进，实验结果表明，HOP-TreePrcject在性能上显著优于TreeProject。     

协同进化算法在关联规则挖掘中的应用

文中采用了一种协同进化算法,分别利用改进的遗传算法和粒子群算法对两个种群同时进行迭代,并在种群之间引入一种信息交互机制,使两个种群协同进化。文中最后通过实验对该协同进化算法、传统的遗传算法以及粒子群算法应用于关联规则挖掘时的性能进行比较,证明了该协同进化算法在可接受的时间复杂度前提下,不仅继承了传统遗传算法挖掘关联规则时无须产生规模庞大的候选项集和有效减少扫描数据库次数的优点,更弥补了其容易早熟收敛的缺陷,从而能高效地搜索出数据库中高质量的关联规则,这点在其应用于高维数据集时尤为显著。     

差分型复杂过程全局进化方法

复杂过程全局进化算法是一种具有类似分散搜索的通用框架结构,能够高效完成全局搜索的新型进化算法。在该算法的基础上,提出了差分型复杂过程全局进化算法。差分型算法采用拉丁超立方体抽样生成多样性种群,并应用“最小欧几里德距离的最大值法”产生参考集Refset2,以保证参考集的多样性。采用差分变异和交叉策略替代原算法的线性合并,兼顾算法的收敛速度和种群的多样性。应用Nelder-Mead直接搜索法进行局部搜索,防止搜索过程在局部最优点附近反复。仿真结果表明差分型复杂过程全局进化算法,具有较高的搜索效率。     

自适应合并与分裂的多种群差分进化算法

针对差分进化（DE）算法存在的早熟收敛与搜索停滞问题,提出了自适应合并与分裂的多种群差分进化算法。算法将种群划分为多个子种群,引入子种群优劣因子来评价种群的优劣性,实现种群间的自适应合并与分裂;对于种群中的各个个体,采取基于精英池学习的变异算子,结合优秀个体进行自适应学习调整,使算法达到全局搜索与局部搜索能力的平衡;在算法后期引入扰乱策略,保证算法快速收敛的同时有效地跳出局部极值点,提高算法寻优的精度。在30个标准测试函数的实验结果表明,改进算法能有效解决早熟和陷入局部最优的问题。     

减少候选项集的数据流高效用项集挖掘算法

大数据环境下高效用项集挖掘算法中过多的候选项集极大地降低了算法的时空效率,提出了一种减少候选项集的数据流高效用项集挖掘算法。首先,通过数据流中当前窗口的一次扫描建立一个全局树,并降低全局树中头表入口与节点的冗余效用值;然后,基于全局树生成候选模式,基于增长算法降低局部树的候选项集效用;最终,从候选模式中选出高效用模式。基于真实数据流的实验结果表明,本算法的时空效率与内存占用比均优于其他数据流的高效用模式挖掘算法。