基于BCU-Tree与字典的高效用挖掘快速脱敏算法

针对隐私保护效用挖掘(PPUM)中脱敏时间长、计算复杂度高,以及算法副作用大等问题,提出一种基于BCU-Tree和字典(BCUTD)的高效用挖掘快速脱敏算法。该算法提出了一种新的树结构BCU-Tree来存储敏感项信息,基于按位运算符编码模型降低树的构建时间并减小搜索空间。采用字典表存储树结构中的所有节点,修改敏感项时只需访问字典表,最终达到数据库脱敏目的。在4个不同的数据集上进行的实验中,BCUTD算法在脱敏时间和副作用上的表现要明显优于经典的优先隐藏高效用项(HHUIF)算法、最大敏感效用-最大项效用(MSU-MAU)算法和使用树与表结构的快速扰动(FPUTT)算法。实验结果表明,BCUTD算法能够有效减少脱敏时间,降低算法副作用以及计算复杂度。

高效用挖掘算法在处方数据中的应用

为保障和提高医疗服务,药品应具备对应的说明书。近几年来,药品问题一直是社会关注的焦点,药费贵、"大处方"、回扣药等不良现象变得越来越普遍,对患者住院治疗的用药评价研究就凸显出其重要性。高效用挖掘是指从交易清单数据库中发现那些具有高价值或者高兴趣度的项集。笔者拟采用高效用挖掘算法对处方进行自动检测,从中发现具有高药价、不合理用药的处方。实验采用两类慢性疾病真实处方数据,结果表明该算法可以有效发现满足特定兴趣度的不合理用药。

基于滑动窗口含负项的高效用模式挖掘

针对传统高效用模式挖掘均未考虑项的效用值为负,以及对流数据处理的时效性问题,提出一种基于滑动窗口的高效用挖掘算法HUPN_SW。利用一种新定义的滑动窗口正负效用列表PNSWU-List,维护挖掘最近批次高效用模式集所需的所有信息,实现有效的逐批次挖掘,避免重复的数据库扫描,在不产生候选效用模式集的情况下,直接挖掘出高效用模式,使HUPN_SW有效适应于动态流数据。实验结果表明,HUPN_SW算法在运行时间和可扩展性方面有良好表现。

面向安防系统的高效用语义轨迹模式挖掘

在安防系统中,将大量目标轨迹先转化为语义轨迹后再进行频繁模式挖掘,有助于分析目标行为模式、识别危险源及增强安防系统内部防控。针对现有频繁模式挖掘方法未考虑目标停留点的效用差异问题,提出一种高效用语义轨迹模式挖掘算法。综合停留点兴趣度、目标停留时间以及目标语义轨迹支持度这3个参数定义语义轨迹效用值,采用蚁群算法挖掘高效用语义轨迹模式。利用精英蚂蚁策略改进蚂蚁种群的迭代方式,通过轮盘赌选择法优化蚂蚁对于下一个节点的选择策略,运用无效用编码向量剪枝策略提高算法执行效率。在Chess、Mushroom、Foodmart、Retail等4个公开数据集以及某安防系统的RFID定位数据集上的实验结果表明,相比于HUIM-ACS算法,该算法挖掘的高效用语义轨迹模式数量增加了10%~15%,运行时间减少了7%~12%。

基于多效用阈值的分布式高效用序列模式挖掘

针对序列模式的高效用模式挖掘过程中搜索空间大、计算复杂度高的问题,提出一种基于多效用阈值的分布式高效用序列模式挖掘算法。采用数组结构保存模式的效用信息,解决效用矩阵导致的内存消耗大的缺点。设计1-项集与2-项集的深度剪枝策略,深入地缩小候选模式的搜索空间,减少搜索时间成本与缓存成本。提出挖掘算法的分布式实现方案,通过并行处理进一步降低模式挖掘的时间。基于中等规模与大规模的序列数据集分别进行实验,实验结果表明,该算法有效减少了候选模式的数量,降低了挖掘的时间成本与存储成本,对于大数据集表现出较好的可扩展能力与稳定性。

基于聚类划分的高效用模式并行挖掘算法

针对在大规模数据库中挖掘高效用模式产生大量基于内存的效用模式树,从而导致内存空间占用较大以及丢失一些高效用项集的问题,提出在Hadoop分布式计算平台下的基于聚类划分的高效用模式并行挖掘算法PUCP。首先,采用聚类的方法把数据库中相似的事务划分为若干数据子集;然后,把若干划分好的数据子集分配到Hadoop平台的各个节点中构造效用模式树;最后,把各个节点中相同项的条件模式基分配到同一个节点中进行挖掘,以减少各个节点交叉操作的次数。通过实验结果和理论分析表明:PUCP算法在不影响挖掘结果可靠性的前提下,与主流串行高效用模式挖掘——效用模式增长挖掘算法(UP-Growth)和现有的并行高效用模式挖掘算法PHUI-Growth相比,挖掘效率分别提高了61.2%和16.6%;并且使用了Hadoop计算平台,能有效缓解挖掘大规模数据的内存压力。

空间高效用Co-location模式挖掘技术初探

空间Co-location模式是一个空间特征集,集合中各个特征的实例在邻近区域内频繁并发出现.在经典的频繁模式挖掘研究中,最近的突破之一是将效用概念作为新的兴趣度量,它允许事务中同一个项可以有多个实例出现且不同的项可以具有不同价值.本文将效用概念引入到空间Co-location模式挖掘中,定义了模式效用、模式效用率等概念,提出一种基础算法挖掘空间高效用Co-location模式.接着定义了扩展模式效用,并根据它的反单调性提出一种剪枝策略:完全剪枝算法,加快了空间高效用Co-location模式的产生.最后通过大量实验来说明完全剪枝算法的效果和效率.

含负项的高效用序列模式挖掘算法

高效用模式挖掘在现实中有广泛的应用,也是数据挖掘研究的热点.数据库中的事务在以序列形式存在的情况下,又引申出高效用序列模式挖掘问题.序列模式的搜索空间比一般模式的大,所以计算复杂度比高效用模式挖掘大.目前对高效用序列模式算法研究比较少,且都没有考虑序列数据库中项的外部效用值为负的情况.面对含负项的外部效用值,首次提出了含负项的高效用序列模式挖掘算法EHUSN,该算法提出1-2-UM和2-2-UM结构模型,结合效用信息列表能快速剪枝非候选序列,从而使挖掘算法在时空效率上的得到提升.

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

由于数据规模的快速增长,高效用序列模式挖掘算法效率严重下降.针对这种情况,提出基于Map Reduce的高效用序列模式挖掘算法Hus Ma R.算法基于Map Reduce框架,使用效用矩阵高效地生成候选项;使用随机映射策略均衡计算资源;使用基于领域的剪枝策略来防止组合爆炸.实验结果表明,在大规模数据集下,算法取得了较高的并行效率.

高效用模式挖掘关键技术综述

通过分析有关高效用模式挖掘(high utility pattern mining,HUPM)最先进的方法,对其进行全面和结构化的概述。首先,通过介绍HUPM的相关概念、公式并给出应用示例,对HUPM有更深一步的理解;针对用于挖掘不同类型HUPM的最常见和最先进的关键技术进行分类,包括基于Apriori、基于树、基于列表、基于映射、基于垂直/水平数据格式、基于索引等方法。针对现有关键技术的用途和优缺点进行了全面概述,由于静态数据难以满足实际需要,总结了在数据流上应用的HUPM方法,主要包括基于增量方法、基于滑动窗口模型方法、基于时间衰减模型方法、基于地标模型方法等。最后,给出了现有技术的不足和改进方向,并且有针对性地提出了新的研究方法。

一种改进的流数据上的高效用模式挖掘算法

为了快速地从无限的流数据中挖掘出高效用模式,基于已有算法HUM-UT提出一种流数据上的高效用模式挖掘算法——IHUM-UT(Improved High Utility Mining based on Utility Tree)算法.IHUM-UT算法通过压缩HUM-UT算法的头表大小,使其只包含滑动窗口中关注的数据,减少挖掘时所要遍历的数据量,达到提高时间效率的目的.结合两个数据集,调节最小效用阈值、批大小和窗口大小,对两个算法进行对比实验,实验结果表明,IHUM-UT算法得到的高效用模式集与HUM-UT算法完全一致,在时间效率上有较大提升,这种提升在关注数据量较少、不同数据项个数较多的情况下更为突出.

基于滑动窗口的含负项高效用模式挖掘方法

现有的面向数据流的高效用模式挖掘方法局限性之一在于假定数据都带有正的效用值,且在挖掘过程中使用效用列表会消耗大量的时间和内存。为了解决以上问题,首次提出在数据流中挖掘含负项的高效用模式挖掘算法,在算法中设计了一种新颖的列表索引结构(list index structure,LIS),LIS包括数据段和索引段,依据索引段中的索引值以及项集中的正负效用值,在滑动窗口中可快速访问或更新数据段并及时剪枝,有效挖掘含负项的高效用模式,以此来提升算法的时空性能。进行了广泛的实验评估来验证算法的效率,实验结果表明,提出算法在内存消耗及运行时间方面均表现出良好的性能。

基于优化上界的高平均效用项集垂直挖掘算法

高平均效用项集挖掘是当前研究的热点之一。针对高平均效用项集挖掘算法产生大量无意义的候选项集,而导致高内存消耗和运行时间长的问题,提出了dMHAUI算法。首先定义了集成矩阵Q,并提出了4种基于垂直数据库表示的紧凑平均效用上界及3种有效的修剪策略;将高平均效用项集挖掘所需的信息存储于IDUL结构树,利用改进的diffset技术快速计算项集的平均效用和上界;最后通过递归调用搜索函数得到高平均效用项集。与EHAUPM算法和MHAI算法进行仿真比较,结果表明,dMHAUI算法在运行时间、连接比较次数和可扩展性等方面都有较优的性能。

基于窗口内投影的闭合高效用模式挖掘

提出了一种快速且有效的数据流高效用模式挖掘算法EFIM_Closed_DS.算法基于窗口内投影技术,在每个窗口中使用数据库投影技术以及事务合并方法有效地减少了数据库扫描的代价。使用高效的剪枝技术和有效的闭合项集检测方法能够剪枝大量低效用项集以及非闭合项集。大量实验结果显示,提出的算法比之前最先进的算法在内存和时间上都更为有效。

数据流频繁模式挖掘综述

一些先进应用如欺诈检测和趋势学习等带来了数据流频繁模式挖掘的发展。不同于静态数据,数据流挖掘面临着时空约束和项集组合爆炸等问题。对已有数据流频繁模式挖掘算法进行综述并对经典和最新算法进行分析。按照模式集合的完整程度进行分类,数据流中频繁模式分为全集模式和压缩模式。压缩模式主要包括闭合模式、最大模式、top-k模式以及三者的组合模式。不同之处是闭合模式是无损压缩的,而其他模式是有损压缩的。为了得到有趣的频繁模式,可以挖掘基于用户约束的模式。为了处理数据流中的新近事务,将算法分为基于窗口模型和基于衰减模型的方法。数据流中模式挖掘常见的还包含序列模式和高效用模式,对经典和最新算法进行介绍。最后给出了数据流模式挖掘的下一步工作。