基于多尺度的时序数据部分周期模式增量挖掘

针对动态时序数据部分周期模式挖掘过程存在的计算复杂度过高和扩展性差等问题,提出了一种结合多尺度理论的时间序列部分周期模式挖掘算法(MSI-PPPGrowth),所提算法充分利用了时序数据客观存在的时间多尺度特性,将多尺度理论引入时序数据的部分周期模式挖掘过程。首先,将尺度划分后的原始数据以及增量时序数据作为更细粒度的基准尺度数据集进行独立挖掘;然后,利用不同尺度数据间的相关性实现尺度转换,以间接获取动态更新后的数据集对应的全局频繁模式,从而避免了原始数据集的重复扫描和树结构的不断调整。其中,基于克里金法并考虑时序周期性设计了一个新的频繁缺失计数估计模型(PJK-EstimateCount),以有效估计在尺度转换过程中的缺失项支持度计数。实验结果表明,MSI-PPPGrowth具有良好的可扩展性和实时性,尤其是对于稠密数据集,其性能优势更为突出。

IncLOF:动态环境下局部异常的增量挖掘算法

异常检测是数据挖掘领域研究的最基本的问题之一 ,它在欺诈甄别、贷款审批、气象预报、客户分类等方面有广泛的应用 以前的异常检测算法只适应于静态环境 ,在数据更新时需要进行重新计算 在基于密度的局部异常检测算法LOF的基础上 ,提出一种在动态环境下局部异常挖掘的增量算法IncLOF ,当数据库中的数据更新时 ,只对受到影响的点进行重新计算 ,这样可以大大提高异常的挖掘速度 实验表明 ,在动态环境下IncLOF的运行时间远远小于LOF的运行时间 ,并且用户定义的邻域中的最小对象个数与记录数之比越小 。

Web数据挖掘中的增量挖掘

为了高效及时地处理频繁新增的数据,在Web挖掘中引入增量挖掘的方法,并给出了一个Web关联规则增量挖掘的有效算法。

改进的并行关联规则增量挖掘算法

针对大数据环境下基于Can树(canonical order tree)的增量关联规则算法存在树结构空间占用过大、频繁模式挖掘效率不佳以及MapReduce集群并行化性能不足等问题,提出了一种基于粗糙集和归并剪枝方法改进的并行关联规则增量挖掘算法MR-PARIRM(MapReduce-based parallel association rules incremental mining algorithm using rough set and merge pruning)。首先,设计了一种基于粗糙集的相似项合并策略RS-SIM(rough set based similar item merge)对数据集的相似项进行合并处理,并根据合并后的数据进行Can树构造,从而降低树结构的空间占用;其次,提出了一种归并剪枝策略MPS(merge pruning strategy)对树结构中的传播路径进行修剪合并,通过压缩频繁模式搜索空间来加快频繁项挖掘;最后,通过动态调度策略DSS(dynamic scheduling strategy)对异构式MapReduce集群中的计算任务进行动态调度,实现了负载均衡,有效提升了集群的并行化运算能力。最终的实验仿真结果表明,MR-PARIRM在大数据环境下具有相对较好的性能表现,适用于对大规模数据进行并行化处理。

基于信息熵与遗传算法的并行关联规则增量挖掘算法

针对大数据环境下基于Can树的增量关联规则算法存在树结构空间占用过大、支持度阈值无法动态设置以及Map与Reduce阶段数据传输耗时等问题,提出了一种基于信息熵和遗传算法的并行关联规则增量挖掘算法MR-PARIMIEG。首先,该算法设计基于信息熵的相似项合并策略(SIM-IE)来合并相似数据项,并根据合并后的数据集进行Can树构造,从而减少树结构的空间占用;其次,提出基于遗传算法的DST-GA策略获取大数据环境下相对最优的动态支持度阈值,根据此阈值进行频繁项集挖掘,避免了冗余的频繁模式挖掘导致的时间消耗;最后,在MapReduce并行化运算过程中使用并行LZO数据压缩算法对Map端输出数据进行压缩,从而减少传输的数据规模,最终提升算法的运行速度。实验仿真结果表明,MR-PARIMIEG在大数据环境下进行频繁项集挖掘时具有较好的性能表现,适用于对较大规模的数据集进行并行化处理。

NPSP:一种高效的序列模式增量挖掘算法

提出了一种称为"异构树"的数据结构,采用一套编号规则对异构树的分支进行编号,使具有相同编号的分支代表相同的候选序列,编号不同的分支代表不同的候选序列,极大地简化了候选集计数过程.在此基础上提出了具有增量挖掘功能的序列模式高效挖掘算法NPSP,并从理论分析和实验两方面证明了其挖掘结果集的完备性和算法的高效性.

PFPonCanTree:一种基于MapReduce的并行频繁模式增量挖掘算法

频繁模式挖掘是最重要的数据挖掘任务之一,传统的频繁模式挖掘算法是以"批处理"方式执行的,即一次性对所有数据进行挖掘,无法满足不断增长的大数据挖掘的需要。MapReduce是一种流行的并行计算模式,在并行数据挖掘领域已得到了广泛的应用。将传统频繁模式增量挖掘算法CanTree向MapReduce计算模型进行了迁移,实现了并行的频繁模式增量挖掘。实验结果表明,提出的算法实现了较好的负载均衡,执行效率有明显提升。

基于扩展自然序树的概化关联规则增量挖掘方法

概化关联规则挖掘作为数据挖掘领域一个重要的拓展性研究课题,首先提出了一种概化扩展自然序树(generalized extended canonical-order tree,GECT)结构及其增量挖掘算法GECT-IM.该算法对原始分类事务数据库只扫描一次,就可以将所有交易信息映射至一棵压缩格式的GECT,然后通过对更新交易数据集扫描得到更新数据集中各项集的计数,结合相关性质及运算就可以发现大部分更新后的概化频繁项集;其次,针对GECT规模较大以及GECT-IM 算法仍然可能需要遍历初始GECT树的局限,在界定数据库更新和重构概念的基础上,基于一种可量化度量的准最小支持度阈值,提出了一种改进的准频繁概化扩展自然序树(pre-large generalized extended canonical-order tree,PGECT)结构及其增量挖掘算法PGECT-IM.由于有效避免了对初始GECT进行遍历的情形,从而进一步提升了概化关联规则增量挖掘效率.实验证明,提出的概化关联规则增量挖掘算法 GECT-IM 及其优化算法PGECT-IM,比现有增量挖掘算法具有更高的挖掘效率和更好的扩展性.

InClosPan:大型数据库中闭序列模式的增量挖掘

许多现实数据库都以增量形式增长,不希望在每次更新了数据库之后,又重新挖掘完整数据库,增量算法成为必需。研究了当初始数据库中增加了新的事务或增加了新的顾客时,增量挖掘闭序列模式的问题。给出了一个新的频繁闭序列模式增量挖掘算法InClosPan,该算法利用已得到的结果进行增量挖掘,减少了重新挖掘数据库的费用。

基于HFUFP-tree的增量挖掘算法研究

增量挖掘算法通常需要重复扫描原始数据库,现实中数据库大多很庞大且以增量形式增长,重新扫描数据库在挖掘过程中必然花费极高的成本。因此,研究一种不用重复扫描原始数据库的增量挖掘算法显得十分必要。提出一种新的算法,该算法以FUFP-tree(Fast Updated FP-tree)为基础,基于趋频项集和小项集来修改FUFP-tree结构,建立一种新的在逻辑上有层次的HFUFP-tree(Hierarchical Fast Updated FP-tree)结构,该结构能将所有的交易记录压缩在一棵树中,在数据更新后不要任何重新扫描或重建树状结构,便能快速地挖掘关联规则。

基于事务线索树的一次扫描关联规则增量挖掘算法

首先将事务数据库压缩存储到一棵事务线索树(TT-tree)的结点上,并建立这些结点的索引表,然后寻找结点索引表的最后结点到根结点的全部路径,这些路径及路径的交集包含了用于挖掘关联规则的频繁集.该算法只需扫描事务数据库一次,由于采用了逆向搜索TT-tree的方法,搜索的时间开销非常少.该算法可以挖掘中短模式的海量数据,具有很好的伸缩性,同时该算法具有增量挖掘的功能.通过大量的实验数据进行比较,该算法的速度约是Apriori算法的10倍.

面向电子商务的增量挖掘算法

对商务信息挖掘理论进行了研究,给出了电子商务运作模式的定义、性质、定理及相关证明;提出了一种用于跟踪电子商务活动的数据模型,在模型中定义了网页监控点与商务指标之间的“点-集”映射关系,建立了商务网站的访问事件、网页中事先设定的监控点,以及商务工作流程之间的联系;根据这些研究结果对关联规则挖掘算法中的发现和剪枝过程进行改进,设计了面向电子商务的增量挖掘算法,并在第三方物流信息系统中实现。实践表明,该算法在频繁变化的数据集中的挖掘效率大大高于传统的非增量挖掘算法,基于智能Agent技术的商务信息挖掘模型有效地提高了电子商务的实时跟踪与分析能力。

一种存在全局站点的分布式增量挖掘算法

随着互联网技术的快速发展与普及,尤其是Web2.0时代的来临,网络数据量与日俱增.对新增数据进行挖掘成为数据挖掘领域研究的热点之一.基于存在全局站点的分布式数据挖掘思想,提出了一种存在全局站点的分布式增量挖掘算法.首先对局部站点的增量数据进行全局挖掘,有效减少了局部站点对原有数据的扫描次数;然后在全局站点采用新的剪枝策略,极大地降低了产生的候选集数量;最后通过实例验证了所给算法切实可行,并具有较好的挖掘效率.

基于项目位置索引的序贯模式增量挖掘方法

通过前缀序列的引入 ,将搜索空间划分为若干个子空间 ,利用模式增量技术对序贯模式进行有效搜索 ,并提出了项目位置索引的概念 ,即将原始序列数据库信息转换到项目位置索引 (IPI)中 ,从而在搜索序贯模式时避免了复杂的多维候选序列的测试 ,仅需对各前缀序列对应的扩展的项目位置索引库(IPIDBs)做简单的序列数目累加操作 ,将复杂的高维序贯模式搜索问题巧妙地转换为一维频繁项目的搜索 ,降低了算法复杂度 。

基于Mapreduce与关联分类挖掘的海量数据分类增量挖掘方法研究

海量数据的增量数据不断出现,须对已挖掘出的结果进行增量更新,而已有增量挖掘方法并不适合海量数据的增量挖掘。针对这个问题,将Map Reduce与关联分类挖掘相结合,提出基于Mapreduce与关联分类挖掘的海量数据分类增量挖掘方法。

基于模式分解树的增量挖掘

数据挖掘具有广泛的应用,频繁模式发现是关联规则挖掘问题的重要组成部分。频繁模式的增量挖掘是一个挑战性的任务,已有的几种基于Apriori思想的方法,具有代价太高的弱点。本文提出了一个基于模式分解树,不需要扫描原数据库的增量挖掘算法。通过合理地组织候选项索引,可以取得较高的效率。

一种改进的增量挖掘算法

Pre-FUFP算法基于次频繁项的概念有效处理了频繁模式树的更新,但当有次频繁项变成频繁项时,需要判定原数据库中哪些事务包含该数据项。为此,通过引入次频繁项对应原事务标识符的索引确定需要处理原数据库的事务,减少这一过程所消耗的时间,并用基于压缩FP-tree和矩阵技术代替原始FP-growth挖掘出频繁模式。实验证明该算法在时间效率上较Pre-FUFP有大幅度提高。

流程增量挖掘中的模型更新方法

正确发现流程实际运作情况对工作流管理有着重要的意义。流程挖掘抽取系统日志信息,挖掘流程的真实运作模型。目前很多该方面的研究,着重于从一份日志中挖掘出工作流模型。然而,这些挖掘方法只关注日志信息,忽略了流程设计者的先验知识。而且,日志所包含信息量较大,进行一次挖掘耗费较大。因此,希望能结合已有工作流模型及新增日志信息,更新工作流模型。已有研究给出对模型及日志的增量挖掘算法。但是,业务流程会随着时间推移变更,可能已有的任务被取消了,因此在新增的一段日志中该任务没被记录。但由于该任务曾经在已有日志中记录下来,故应用已有挖掘算法或增量挖掘算法,在更新模型中,该任务也会被挖掘出来。提出了一种增量挖掘模型更新的改进算法。通过流程设计者的先验知识及统计任务出现的频率,判断该任务是否被取消。最后给出一个实验,验证算法的可行性。

一种具有增量挖掘功能的Web点击流聚类算法

分析了典型的聚类算法及其适用范围,针对其处理Web点击流数据的不足,提出了一种用于Web点击流的增量挖掘的聚类算法WCSCluster,给出了相关定义及存储结构,并用实例说明了算法的运行过程.最后对比同类算法给出实验结果.实验结果表明该算法具有良好的性能,能够发现更优的簇.

状态转移模式的三支增量挖掘

针对动态多元时间序列(MTS)上的状态转移模式(STAP)挖掘问题,提出一种准确高效的三支增量挖掘算法(3IU-STAP)。该算法根据原始数据、已有频繁STAP和增量数据构造出候选模式,使用频繁阈值将其划分至正域、负域以及边界域。仅边界域中的候选模式需要延迟决策,即通过扫描数据集来判断其是否频繁。准确性方面,设计了增量数据补齐技术,获得候选模式实际出现次数。效率方面,使用了向下封闭性质来控制候选模式数量,尽可能减少对数据的扫描。在4个真实数据集上的实验结果表明,与非增量方法相比,3IU-STAP可以得到准确结果,同时显著提高效率。