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

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

一种高效用项集并行挖掘算法

由于能反映用户的偏好,可以弥补传统频繁项集挖掘仅由支持度来衡量项集重要性的不足,高效用项集正在成为当前数据挖掘研究的热点。为使高效用项集挖掘更好地适应数据规模不断增大的实际需求,提出了一种高效用项集的并行挖掘算法PHUI-Mine。提出了记录挖掘高效用项集信息的DHUI-树结构,描述了DHUI-树的构造方法,论证了DHUI-树的动态剪枝策略。在此基础上,给出了高效用项集挖掘的并行算法描述。实验结果表明,PHUI-Mine算法具有较高的挖掘效率及较低的存储开销。     

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

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

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

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

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

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

基于滑动窗口模型的数据流闭合高效用项集挖掘

从数据流中挖掘高效用项集是一项具有挑战性的任务,因为传入的数据必须在时间和存储内存约束下进行实时处理数据流挖掘通常会产生大量冗余的项集,为了减少这些无用的项集数量且保证无损压缩,需要挖掘闭合项集,它可以比全集高效用项集的集合小几个数量级.为了解决以上问题,提出一种基于滑动窗口模型的数据流闭合高效用项集挖掘(closed high utility itemsets mining over data stream based on sliding window model,CHUI_DS)算法.在 CHUI DS 中设计了 一种新的效用列表结构,该结构在提升批次插入和删除的速度方面非常有效此外,应用修剪策略来改进闭合项集挖掘过程,消除潜在的低效用候选对象.对真实数据集和合成数据集进行的广泛实验评估显示了该算法的效率以及可行性就速度而言,它优于先前提出的主要以批处理模式运行的算法.且它适用于不同大小的滑动窗口,在事务数量等方面具有较强的扩展性.     

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

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

基于马尔可夫优化的高效用项集挖掘算法

基于树型和链表结构的高效用项集挖掘（HUIM）算法通常需要指数量级的搜索空间，而基于进化类型的挖掘算法未能充分考虑变量间的相互作用，因此提出一种基于马尔可夫优化的HUIM算法（HUIM-MOA）。首先，采用位图矩阵表示数据库和使用期望向量编码，以实现对数据库的快速扫描和效用值的高效计算；其次，通过计算优势个体间的互信息估计马尔可夫网络（MN）结构，并根据它们的局部特性使用吉布斯采样以产生新的种群；最后，为防止算法过快陷入局部最优和减少高效用项集的缺失，分别采用种群多样性保持策略和精英策略。在真实数据集上的实验结果表明，相较于次优的基于粒子群优化（PSO）的生物启发式HUI框架（Bio-HUIF-PSO）算法，在给定较大最小阈值的情况下，HUIM-MOA可以找到全部的高效用项集（HUI），收敛速度平均提升12.5%，挖掘HUI数平均提高2.85个百分点，运行时间平均减少14.6%。HUIM-MOA较进化型HUIM算法有更强的搜索性能，能有效减少搜索时间和提高搜索质量。     

基于效用表的快速高平均效用挖掘算法

高效用项集挖掘在数据挖掘领域中受到了广泛的关注,但是高效用项集挖掘并没有考虑项集长度对效用值的影响,所以高平均效用项集挖掘被提出;而目前的一些高平均效用项集挖掘算法需要耗费大量的时间才能挖掘出有效的高平均效用项集。针对此问题,给出了一个高平均效用项集挖掘的改进算法——FHAUI。FHAUI算法将效用信息保存到效用列表中,通过效用列表的比较来挖掘出所有的高平均效用值,同时FHAUI算法还采用了一个二维矩阵来有效减少二项效用值的连接比较次数。最后将FHAUI算法在多个经典的数据集上测试。实验结果表明,FHAUI算法在效用列表的连接比较次数上有了极大的降低,同时其时间性能也有非常大提高。     

基于模式增长的高效用序列模式挖掘算法

高效用序列模式挖掘是数据挖掘领域的一项重要内容, 在生物信息学、消费行为分析等方面具有重要的应用.与传统基于频繁项模式挖掘方法不同, 高效用序列模式挖掘不仅考虑项集的内外效用, 更突出项集的时间序列含义, 计算复杂度较高.尽管已经有一定数量的算法被提出应用于解决该类问题, 挖掘算法的时空效率依然成为该领域的主要研究热点问题.鉴于此, 本文提出一个基于模式增长的高效用序列模式挖掘算法HUSP-FP.依据高效用序列项集必须满足事务效用闭包属性要求, 算法首先在去除无用项后建立全局树, 进而采用模式增长方法从全局树上获取全部高效用序列模式, 避免产生候选项集. 在实验环节与目前效率较好的HUSP-Miner、USPAN、HUS-Span三类算法进行了时空计算对比, 实验结果表明本文给出算法在较小阈值下仍能有效挖掘到相关序列模式, 并且在计算时间和空间使用效率两方面取得了较大的提高.     

高激励项集的挖掘研究

基于支持度的关联规则只能找出所有的频繁集,无法找到那些非频繁但效用很高的项集;基于效用的关联规则致力于发现所有高效用项集,无法找到效用不高但支持度与效用的积很大的项集。为克服支持度与效用的不足,提出了一种新的项集重要性的度量方法（即激励）及一种自下而上的挖掘高激励项集的算法HM-Two-Phase-Miner。激励集成了支持度与效用的优点,能同时表达项集的语义特性与统计特性。HM-Two-Phase-Miner利用事务权重激励向下封闭特性进行减枝,有效提高了算法的性能。     

Mining itemset utilities from transaction databases

The rationale behind mining frequent itemsets is that only itemsets with high frequency are of interest to users. However, the practical usefulness of frequent itemsets is limited by the significance of the discovered itemsets. A frequent itemset only reflects the statistical correlation between items, and it does not reflect the semantic significance of the items. In this paper, we propose a utility based itemset mining approach to overcome this limitation. The proposed approach permits users to quantify their preferences concerning the usefulness of itemsets using utility values. The usefulness of an itemset is characterized as a utility constraint. That is, an itemset is interesting to the user only if it satisfies a given utility constraint. We show that the pruning strategies used in previous itemset mining approaches cannot be applied to utility constraints. In response, we identify several mathematical properties of utility constraints. Then, two novel pruning strategies are designed. Two algorithms for utility based itemset mining are developed by incorporating these pruning strategies. The algorithms are evaluated by applying them to synthetic and real world databases. Experimental results show that the proposed algorithms are effective on the databases tested.     

Mining itemset utilities from transaction databases

The rationale behind mining frequent itemsets is that only itemsets with high frequency are of interest to users. However, the practical usefulness of frequent itemsets is limited by the significance of the discovered itemsets. A frequent itemset only reflects the statistical correlation between items, and it does not reflect the semantic significance of the items. In this paper, we propose a utility based itemset mining approach to overcome this limitation. The proposed approach permits users to quantify their preferences concerning the usefulness of itemsets using utility values. The usefulness of an itemset is characterized as a utility constraint. That is, an itemset is interesting to the user only if it satisfies a given utility constraint. We show that the pruning strategies used in previous itemset mining approaches cannot be applied to utility constraints. In response, we identify several mathematical properties of utility constraints. Then, two novel pruning strategies are designed. Two algorithms for utility based itemset mining are developed by incorporating these pruning strategies. The algorithms are evaluated by applying them to synthetic and real world databases. Experimental results show that the proposed algorithms are effective on the databases tested.     

DiffNodesets: An efficient structure for fast mining frequent itemsets

Mining frequent itemsets is an essential problem in data mining and plays an important role in many data mining applications. In recent years, some itemset representations based on node sets have been proposed, which have shown to be very efficient for mining frequent itemsets. In this paper, we propose DiffNodeset, a novel and more efficient itemset representation, for mining frequent itemsets. Based on the DiffNodeset structure, we present an efficient algorithm, named dFIN, to mining frequent itemsets. To achieve high efficiency, dFIN finds frequent itemsets using a set-enumeration tree with a hybrid search strategy and directly enumerates frequent itemsets without candidate generation under some case. For evaluating the performance of dFIN, we have conduct extensive experiments to compare it against with existing leading algorithms on a variety of real and synthetic datasets. The experimental results show that dFIN is significantly faster than these leading algorithms.     

CLS-Miner: efficient and effective closed high-utility itemset mining

High-utility itemset mining (HUIM) is a popular data mining task with applications in numerous domains. However, traditional HUIM algorithms often produce a very large set of high-utility itemsets (HUIs). As a result, analyzing HUIs can be very time consuming for users. Moreover, a large set of HUIs also makes HUIM algorithms less efficient in terms of execution time and memory consumption. To address this problem, closed high-utility itemsets (CHUIs), concise and lossless representations of all HUIs, were proposed recently. Although mining CHUIs is useful and desirable, it remains a computationally expensive task. This is because current algorithms often generate a huge number of candidate itemsets and are unable to prune the search space effectively. In this paper, we address these issues by proposing a novel algorithm called CLS-Miner. The proposed algorithm utilizes the utility-list structure to directly compute the utilities of itemsets without producing candidates. It also introduces three novel strategies to reduce the search space, namely chain-estimated utility co-occurrence pruning, lower branch pruning, and pruning by coverage. Moreover, an effective method for checking whether an itemset is a subset of another itemset is introduced to further reduce the time required for discovering CHUIs. To evaluate the performance of the proposed algorithm and its novel strategies, extensive experiments have been conducted on six benchmark datasets having various characteristics. Results show that the proposed strategies are highly efficient and effective, that the proposed CLS-Miner algorithmoutperforms the current state-ofthe- art CHUD and CHUI-Miner algorithms, and that CLSMiner scales linearly.     

最大频繁项目集的快速更新

挖掘最大频繁项目集是多种数据挖掘应用中的关键问题．为克服基于Apriori的最大频繁项目集挖掘算法存在的不足,DMFIA采用FP-tree存储结构及自顶向下的搜索策略,有效地提高了最大频繁项目集的挖掘效率．但对于频繁项目多而最大频繁项目集维数相对较小的情况,DMFIA要经过多层搜索且在每一层产生大量的候选项目集,因而影响算法的执行效率．为此,该文提出了DMFIA的改进算法IDMFIA(the Improved algorithm of DMFIA)．IDMFIA采用自顶向下和自底向上双向搜索策略,可尽早修剪掉较短最大频繁项目集的超集和较长最大频繁项目集的子集．另外,该文还提出最大频繁项目集更新算法FUMFIA(Fast Updating Maximum Frequent Itemsets Algorithm),该算法充分利用已建立的FP-tree和已挖掘的最大频繁项目集,可对已挖掘的最大频繁项目集进行高效维护．实验结果表明,IDMFIA和FUMFIA可有效提高最大频繁项目集的挖掘和更新效率．     

快速挖掘全局最大频繁项目集

挖掘最大频繁项目集是多种数据挖掘应用中的关键问题.现行可用的最大频繁项目集挖掘算法大多基于单机环境,针对分布式环境下的全局最大频繁项目集挖掘尚不多见.若将基于单机环境的最大频繁项目集挖掘算法运用于分布式环境,或运用分布式环境下的全局频繁项目集挖掘算法来挖掘全局最大频繁项目集,均会产生大量的候选频繁项目集,且网络通信代价高.为此,提出了快速挖掘全局最大频繁项目集算法FMGMFI(fast mining global maximum frequent itemsets),该算法采用FP-tree存储结构,可方便地从各局部FP-tree的相关路径中得到项目集的频度,同时采用自顶向下和自底向上的双向搜索策略,可有效地降低网络通信代价.实验结果表明,FMGMF算法是有效、可行的.