一种分布式序列模式挖掘算法

针对分布式环境下的序列模式挖掘问题,提出了一种分布式序列模式挖掘(DSPM)算法。DSPM以PrefixSpan算法为基础,使用抽样检测技术平衡了任务负载,将挖掘任务分解后分配到多台计算机上以多进程、多线程并行执行。另外采用了伪投影技术来降低生成投影数据库的开销。实验结果表明,DSPM算法能够快速有效地挖掘分布式环境下的全局序列模式。     

动态划分序列模式挖掘算法

在对海量数据进行序列模式挖掘时,由于产生的候选序列数量大并且需要反复遍历数据库,会带来存储受限及时效性问题.为此,基于无共享分布式环境,提出一种动态划分序列模式挖掘算法DPSPM.通过分布数据降低数据库扫描的规模,降低I、O开销,使用分派函数指定选举节点,降低通信开销,设计动态列表存储候选序列,降低内存开销,多个子过程异步运行,提高算法的执行效能.实验结果表明,DPSPM算法在较小支持度情况下对中大型数据库有较好的搜索效率.     

基于Map Reduce的序列模式挖掘算法

传统数据挖掘算法在处理海量数据集时计算能力有限。为解决该问题,提出一种基于Map Reduce的分布式序列模式挖掘算法MR-PrefixSpan。在PrefixSpan算法的基础上,对模式挖掘任务进行分割,利用Map函数处理由不同前缀得到的序列模式,并行构造投影数据库,从而提高挖掘效率及简化搜索空间。采用Reduce函数对中间结果进行规约,得到全局序列模式。在Hadoop集群上的实验结果表明,MR-PrefixSpan能减少数据库扫描时间,具有较高的并行加速比和较好的可扩展性。     

基于层次空间聚类的表语义汇总算法

频繁模式挖掘可以发现数据中频繁出现的模式,是关联规则挖掘的重要步骤。并行频繁模式算法将其应用到并行环境中,以对海量数据进行挖掘。在Apache软件基金会的Mahout项目实现的基础上,对计数和排序阶段以及算法的执行顺序提出了新的优化策略。优化后的设计将计数信息存储在分布式协调系统上,充分地利用了分布式协调系统的高可用性、适宜存储元数据信息的特点。该设计减小了小文件在分布式文件系统(HDFS)上的开销,同时保留了其优点,还能使计数过程和排序过程并行执行,减小了计算节点的内存开销。对比了文件系统I/O的开销,并分析了实现设计中的难点,为未来的工作打下了基础。     

基于分布式协调系统的并行频繁模式增长算法的优化

频繁模式挖掘可以发现数据中频繁出现的模式,是关联规则挖掘的重要步骤。并行频繁模式算法将其应用到并行环境中,以对海量数据进行挖掘。在Apachc软件基金会的Mahout项目实现的基础上,对计数和排序阶段以及算法的执行顺序提出了新的优化策略。优化后的设计将计数信息存储在分布式协调系统上,充分地利用了分布式协调系统的高可用性、适宜存储元数据信息的特点。该设计减小了小文件在分布式文件系统(HDFS)上的开销,同时保留了其优点,还能使计数过程和排序过程并行执行,减小了计算节点的内存开销。对比了文件系统I/O的开销,并分析了实现设计中的难点,为未来的工作打下了基础。     

分布式图计算框架混合计算模式的研究

分析了分布式图计算框架的同步和异步计算模式在调度开销和收敛速度上存在的优点与不足.同步计算模式调度开销小,但是收敛较慢;而异步计算模式收敛较快,但调度开销大.基于上述发现,提出一种混合计算模式,能够在分布式环境下有效地结合同步与异步计算模式的优点克服各自不足,以获得最优性能.混合计算模式采用"同步控制流"以降低分布式环境下的调度开销,同时采用"异步数据流"使计算过程使用较新的数据以加快收敛速度.基于多个典型图算法和真实大规模图的评测显示,混合计算模式的性能是原有同步计算模式的1.2倍到2.4倍,计算量平均减少30%;相对于异步计算模式通过减少调度开销,整体性能可以提升至其2.3倍到4.6倍.     

云计算环境下支持复杂查询的多维数据索引机制

针对云计算环境下分布式存储系统的数据索引不支持复杂查询的问题,提出了一种多维数据索引机制M-Index,采用金字塔技术(pyramid-technique)将数据的多维元数据描述成一维索引,在此基础上首次提出前缀二叉树(prefix binary tree,PBT)的概念,通过提取一维索引和PBT有效节点的前缀作为数据在存储系统中的主键.数据根据主键和一致性Hash机制发布到存储节点组成的覆盖网络.设计了基于M-Index的数据查询算法,将复杂查询请求转换成一维查询键值,有效支持多维查询和区间查询等复杂查询模式.理论分析和实验表明,M-Index在复杂查询模式下具有良好的查询效率和负载均衡.     

一种基于GPU集群的深度优先并行算法设计与实现

深度优先搜索算法在GPU集群中大型图上的简单执行,会导致线程间的负载不平衡和无法合并内存访问的情况,这使得算法的性能较低.为了明显提高算法在单个GPU和多个GPU环境下的性能,在处理数据之前通过采取一系列有效的操作来进行重新编排.提出了构造线程和数据之间映射的新技术,通过利用前缀求和及二分查找操作来达到完美的负载平衡.为了降低通信开销,对DFS各分支中需要进行交换的边集执行修剪操作.实验结果表明,算法在单个GPU上可以尽可能地实现最佳的并行性,在多GPU环境下可以最小化通信开销.在一个GPU集群中,它可以对合有数十亿节点的图有效地执行分布式DFS.     

基于差分隐私的轨迹模式挖掘算法

针对现有基于差分隐私的频繁轨迹模式挖掘算法全局敏感度过高、挖掘结果可用性较低的问题,提出一种基于前缀序列格和轨迹截断的差分隐私下频繁轨迹模式挖掘算法--LTPM。该算法首先利用自适应的方法获得最优截断长度,然后采用一种动态规划的策略对原始数据库进行截断处理,在此基础上,利用等价关系构建前缀序列格,并挖掘频繁轨迹模式。理论分析表明LTPM算法满足ε-差分隐私;实验结果表明,LTPM算法的准确率（TPR）和平均相对误差（ARE）明显优于N-gram和Prefix算法,能有效提高挖掘结果的可用性。     

基于Spark的并行频繁模式挖掘算法

在大数据环境下Apriori频繁模式挖掘算法在数据处理过程具有预先设定最小阈值、时间复杂度高等缺陷, 为此采用多阶段挖掘策略实现并行化频繁模式挖掘算法PTFP-Apriori。首先将预处理数据以模式树的形式存储,通过最为频繁的[k]个模式得到最优阈值。然后根据该值删除预期不能成长为频繁的模式以降低计算规模,并利用弹性分布式数据集RDD完成统计项集支持度计数、候选项集生成的工作。实验分析表明相比于传统的频繁模式挖掘算法,该算法具有更高的效率以及可扩展性。     

基于CTID序列模式的一种改进算法

提高序列模式挖掘算法效率的关键在于减少发现频繁序列的时间。文中基于CTID概念提出了一种改进的频繁序列模式挖掘算法——SPM，它充分利用频繁项集和中间挖掘结果，得到更多有效的序列模式，并简化了剪枝步骤，从而提高了算法效率。实验证明该算法可行。     

基于关联规则的分布式通信网告警相关性研究

描述了基于数据挖掘的通信网告警相关性分析.在分布式数据库中直接运用序列算法效率很低,因为这需要大量的额外通信.为此提出了一种有效的分布式关联规则挖掘算法--EDMA,它通过局部剪枝与全局剪枝来最小化候选项集数目和通信量.在局部站点上运用先进的压缩关联矩阵CMatrix统计局部项集支持数.此外还利用项目剪枝与交易剪枝共同来减少扫描时间.最后仿真验证了EDMA比其他经典分布式算法有更高的运算效率、更低的通信开销以及更好的可扩展性.     

CLAP: Collaborative pattern mining for distributed information systems

The purpose of data mining from distributed information systems is usually threefold: (1) identifying locally significant patterns in individual databases; (2) discovering emerging significant patterns after unifying distributed databases in a single view; and (3) finding patterns which follow special relationships across different data collections. While existing research has significantly advanced the techniques for mining local and global patterns (the first two goals), very little attempt has been made to discover patterns across distributed databases (the third goal). Moreover, no framework currently exists to support the mining of all three types of patterns. This paper proposes solutions to discover patterns from distributed databases. More specifically, we consider pattern mining as a query process where the purpose is to discover patterns from distributed databases with patterns' relationships satisfying user specified query constraints. We argue that existing self-contained mining frameworks are neither efficient, nor feasible to fulfill the objective, mainly because their pattern pruning is single-database oriented. To solve the problem, we advocate a cross-database pruning concept and propose a collaborative pattern (CLAP) mining framework with cross-database pruning mechanisms for distributed pattern mining. In CLAP, distributed databases collaboratively exchange pattern information between sites so that each site can leverage information from other sites to gain cross-database pruning. Experimental results show that CLAP fits a niche position, and demonstrate that CLAP not only outperforms its other peers with significant runtime performance gains, but also helps find patterns incapable of being discovered by others.     

去冗余Top-k对比序列模式挖掘

对比序列模式可以用来表征不同类别数据集之间的差异。在生物信息、物流管理、电子商务等领域,对比序列模式有着广泛的应用。Top-k对比序列模式挖掘的目标是发现数据集中对比度最高的前k个序列模式。在Top-k对比序列模式挖掘中,可能挖掘出冗余的序列模式。目前,虽然有Top-k对比序列模式发现算法被提出,但这些算法并未考虑冗余序列模式的问题。为此,本文提出了基于广度优先生成树的去冗余Top-k对比序列模式挖掘算法BFM（breadth-first miner）。使用BFM算法可以有效地解决冗余问题,得到去冗余的Top-k对比序列模式。在BFM算法的基础上,提出了性能更好的算法PBFM（pruning breadth-first miner）。通过在真实数据集上的实验分析与对比 ,验证了本文算法的有效性。     

Sequential Pattern Mining in Multi-Databases via Multiple Alignment

To efficiently find global patterns from a multi-database, information in each local database must first be mined and summarized at the local level. Then only the summarized information is forwarded to the global mining process. However, conventional sequential pattern mining methods based on support cannot summarize the local information and is ineffective for global pattern mining from multiple data sources. In this paper, we present an alternative local mining approach for finding sequential patterns in the local databases of a multi-database. We propose the theme of approximate sequential pattern mining roughly defined as identifying patterns approximately shared by many sequences. Approximate sequential patterns can effectively summerize and represent the local databases by identifying the underlying trends in the data. We present a novel algorithm, ApproxMAP, to mine approximate sequential patterns, called consensus patterns, from large sequence databases in two steps. First, sequences are clustered by similarity. Then, consensus patterns are mined directly from each cluster through multiple alignment. We conduct an extensive and systematic performance study over synthetic and real data. The results demonstrate that ApproxMAP is effective and scalable in mining large sequences databases with long patterns. Hence, ApproxMAP can efficiently summarize a local database and reduce the cost for global mining. Furthremore, we present an elegant and uniform model to identify both high vote sequential patterns and exceptional sequential patterns from the collection of these consensus patterns from each local databases.     

一种有效的并行序列模式挖掘算法

为解决共享存储的并行计算环境下挖掘序列模式时存在的处理器负载不平衡及缺少有效剪枝策略的问题,提出采用动态任务分配的办法来平衡处理器之间的工作负载,利用并行局部剪枝技术消除投影数据库的重复生成与计算以提高挖掘效率。设计一种基于共享存储SMP系统的并行序列模式挖掘算法PFSPAN。算法分析和实验结果表明,PFSPAN能够有效地挖掘序列模式。     

基于ACV约束的序列模式挖掘算法

针对变值数据环境下的序列模式挖掘问题进行研究,提出一种针对变值数据的约束(ACV约束),用于表达用户在变值数据环境下对序列模式聚集特征的要求。在此基础上,提出一种基于ACV约束的序列模式挖掘算法,利用ACV约束的性质有效削减搜索空间。在用IBM数据生成器产生的序列数据以及真实数据上的实验结果表明,该算法能够有效利用ACV约束对无用的候选序列模式进行剪枝,减少冗余的搜索空间并提高挖掘效率。     

基于最右扩展枚举的半结构化数据最大模式挖掘方法研究

本文以标记有序树作为半结构化数据的数据模型 ,研究了半结构化数据的树状最大频繁模式挖掘问题 .已有挖掘算法通常挖掘所有频繁模式 ,其中很多模式为其它模式的子模式 ,针对该问题 ,设计实现了一种最大模式挖掘算法 .该算法采用最右扩展枚举方法无重复枚举所有候选模式 ,利用频繁模式扩展森林实现高效剪枝扩展和挖掘频繁叶模式 ,通过计算频繁叶模式间的包含关系挖掘树状最大频繁模式 .试验结果表明该算法具有良好性能     

基于BIDE的多核并行闭合序列模式挖掘

基于经典的BIDE算法,提出一种多核并行闭合序列模式挖掘算法——MT_BIDE。该算法在频繁序列扩展判断前进行剪枝,在扩展过程中动态调整频繁序列及其伪投影数据集,平衡不同线程间挖掘闭合序列模式的计算量差异。实验结果表明,该算法具有较高的运行效率和加速比。