一种基于不确定数据的高效剪枝挖掘算法

剪枝策略(pruning mechanisms)是频繁模式挖掘算法常用方法之一,通过该策略可以快速克服工业生产中可能发生的金融危机,从而最大限度地提高制造业的生产能力.现有的剪枝策略算法仅考虑每个产品的利润信息,不考虑产品的权重,所以效率低下.提出了一种新的剪枝挖掘算法.通过基于低估值的约束和组件权重的挖掘索引器进行的有效剪枝挖掘,不但考虑了利润信息,而且考虑了权重信息.实验表明,该方法能节省大量的运行时间,大幅提高挖掘效率.     

基于DSCFCI_tree的带项目约束的数据流频繁闭合模式挖掘算法

根据数据流的特点,提出了一种挖掘约束频繁闭合项集的算法,该算法将数据流分段,用DSCFCI_tree动态存储潜在约束频繁闭合项集,对每一批到来的数据流,首先建立局部DSCFCI_tree,进而对全局DSCFCI_tree进行有效更新并剪枝,从而有效地挖掘整个数据流中的约束频繁闭合模式.实验表明,该算法具有很好的时间和空间效率.     

树形频繁模式的挖掘及可视化技术研究

频繁项集的挖掘不仅仅是关联规则挖掘的基础,而且在序列模式、聚类、多维模式等数据挖掘任务中扮演重要角色.本文在给出一个基于数据垂直分布的频繁项集挖掘算法HBMFP的基础上,论述了利用MFC中的树视图控件(CTreeCtrl)将频繁项集树形可视化,并讨论了基于该频繁模式树的3种约束频繁项集查询的方法.     

一种用户频繁移动模式并行挖掘算法

针对用户的日常移动轨迹进行挖掘,可以有效地发现隐藏在用户生活中频繁出现的移动规律,即用户频繁移动模式,提出了一种基于PrefixSpan算法的用户频繁移动模式并行挖掘算法PASFORM.该算法利用了新的剪枝策略,缩小了搜索空间;引入了时间约束,挖掘出的频繁移动模式带有时间属性;使用前缀树存储频繁移动模式,缩小了存储空间;采用了并行化方法,适用于海量时空数据的挖掘.实验结果表明,该方法能够快速有效地挖掘出用户频繁移动模式.     

在有噪音的环境中挖掘序列模式精简基

提出在匹配度模型下频繁序列模式精简基的概念,精简基由相对于一系列匹配度阈值的最大序列模式组成,它是频繁序列模式的一个子集,可以用它来估计任一频繁序列模式的匹配度,并能将误差控制在确定范围内.还开发了一个从有噪音的序列数据库中挖掘这种序列模式精简基的算法,该算法采用了一种不需要保留候选序列模式的方法来检查最大序列模式,采用的剪枝技术也比以前的算法更有效率.实验结果显示计算频繁序列模式精简基是很有前途的.     

基于约束的序列模式关联规则挖掘算法

约束关联规则是数据挖掘的一个主要方向,可以根据用户给定的约束条件针对性的挖掘.目前大多数的研究都集中在约束频繁项集挖掘方面,很少进行序列模式的约束关联挖掘.本文把序列模式和约束进行结合,提出一种基于约束的序列模式关联规则挖掘算法.它同时处理两类约束:反单调性约束和单调性约束.可以根据约束条件挖掘数据间的因果关联关系.通过实验验证,该算法在运行效率上达到了较好效果.     

DMBIT：一种有效的序列模式挖掘算法

大量候选序列模式支持度的计算所带来的时间消耗是序列模式挖掘主要问题之一,为此提出了一种有效的序列模式挖掘算法:DMBIT(Data Mining Bitmap),该算法根据位索引表和Seq-list表的结构,采用渐进的事件扩展,事务扩展方法,通过有效的剪枝策略和"与"逻辑运算操作进一步缩小了频繁序列的搜索范围,同时通过序列列表ListX的生成加快了相应候选项支持度的计算,算法分析和实验结果表明,在大数据集环境下的DMBIT算法性能优越,能够明显加速数据库中最大频繁序列的生成.     

DMGSP:一种快速分布式全局序列模式挖掘算法

为了解决分布式环境下挖掘全局序列模式常产生过多候选序列,加大网络通信代价问题,提出了一种基于分布式环境下的快速挖掘全局序列模式算法--DMGSP.该算法将分布式环境下的各站点得到的局部序列模式压缩到一种语法序列树上, 避免了重复的序列前缀传输. 采用合并树中结点序列规则和项序扩展策略,对非频繁序列进行剪枝,有效地约简了候选序列,减少了网络传输量,从而快速生成全局序列模式.算法分析和实验结果表明,在大数据集环境下的DMGSP算法性能优越,能够有效地挖掘全局序列模式.     

一种基于规则表达式约束的序列模式增量式挖掘算法

序列模式挖掘是数据挖掘中的研究热点之一。在挖掘过程中需要用户的参与日益显得重要。为了提高挖掘过程中的交互性，本文提出了一个基于规则表达式约束的序列模式增量式挖掘算法RE_IncUp。该算法首先利用约束对已经挖掘出的频繁序列模式进行预处理，缩小了搜索范围；然后采用模式扩展方法把规则表达式约束和增量挖掘过程融为一体，并且采用先修剪后计算支持度的方法进一步缩小了搜索范围，降低了支持度的计算量。该算法允许用户不断改变约束条件，实现交互式挖掘而且可将挖掘的目标仅仅聚焦到用户感兴趣的模式上。实验表明该算法对序列模式的维护和满足用户的需求都是十分有效的。     

频繁序列模式更新算法

在分析了频繁序列模式更新算法关键技术的基础上，提出了一种快速的增量式更新频繁序列模式挖掘算法FUFSPA，该算法将充分利用先前挖掘过程中所产生的信息来减少本次挖掘过程中的时闻开销．另外，针对频繁序列模式挖掘中支持数计算的复杂性，提出了一种基于二进制形式的支持数计算方法，该方法只需进行一些“或”逻辑运算操作，将该方法用于序列模式挖掘中支持度（数）的计算，可以进一步提高算法的执行效率．实验结果表明算法FUFSPA是可行和有效的．     

一种基于序列挖掘的分类系统框架

为了有效地对序列数据进行分类，提出了一种集成分类挖掘和序列模式挖掘技术的分类系统框架(SPACS)．先采用一套约束和裁减策略，为每个分类挖掘频繁序列模式，并将其转换为分类序列规则(CSR)；再利用平均CSR匹配置信度和一个规则匹配算法构建有效的序列数据分类器．SPACS不需要在提取序列的特征后采用传统方法进行分类，可以直接利用从序列数据中提取出的频繁序列进行分类．实验结果表明，对于序列类型的数据的分类，SPACS比传统的决策树和关联分类方法具有更高的分类精度．     

基于SAT和BDD的频繁序列挖掘技术

【目的】研究模式挖掘领域中的频繁序列挖掘技术,由于序列模式挖掘存在指数级的搜索空间,且传统的SAT求解算法无法高效求解大规模数据集的缺点,因此研究符号表示和操作技术,用来避免冗余计算。【方法】提出基于SAT的频繁序列挖掘的符号OBDD算法,基于深度优先算法的思想,首先将频繁序列挖掘问题构建为SAT模型,其次对变量进行排序并将约束子句分类后分别描述为OBDD,利用OBDD的"与"操作得到满足SAT的所有频繁序列模式。【结果】实例结果表明,该方法准确可行。【结论】该方法能有效缩减搜索空间,提高求解效率。     

基于频繁模式矩阵的改进挖掘算法研究

提出了对基于频繁模式矩阵Fp-array的挖掘的改进算法。首先对各项的投影矩阵预处理划分成若干同维矩阵,并根据同维矩阵的权值对剩余未搜索项进行预先判断,进而对搜索最大频繁项目集进行有效剪枝,减少了搜索范围。经过实验和算法分析,证明了改进算法具有明显的优越性。     

Incremental frequent tree-structured pattern mining from semi-structured data

The paper studies the problem of incremental pattern mining from semi-structrued data. When a new dataset is added into the original dataset, it is difficult for existing pattern mining algorithms to incrementally update the mined results. To solve the problem, an incremental pattern mining algorithm based on the rightmost expansion technique is proposed here to improve the mining performance by utilizing the original mining results and information obtained in the previous mining process. To improve the efficiency, the algorithm adopts a pruning technique by using the frequent pattern expansion forest obtained in mining processes. Comparative experiments with different volume of initial datasets, incremental datasets and different minimum support thresholds demonstrate that the algorithm has a great improvement in the efficiency compared with that of non-incremental pattern mining algorithm.     

基于频繁活动序列挖掘的过程改进机会分析

为了指导质量管理过程的持续改进，提出了基于图结构的工作流频繁活动序列模式的挖掘方法．采用基于Apriori方法的频繁活动序列挖掘算法，认为k-频繁图集中，当一个图减去其中的一个源顶点后，如果所得到的图与另一个图减去其中的一个沉顶点后的图相同时，可以连接生成一个（k＋1）-候选频繁图，从而减少了传统Apriori算法迭代过程中生成的冗余候选频繁图的数目．文中以某飞机制造公司的质量外审意见处理流程为例，对改进Apriori算法的应用效果进行了验证，结果表明，该方法能够有效地挖掘出历史过程实例集中所蕴含的频繁活动执行序列，辅助企业可从过程组成的角度来寻找质量管理过程的改进机会．     

Mining Maximal Frequent Patterns in a Unidirectional FP-tree

Becausemining complete set of frequent patterns from dense database could be impractical, an interesting alternative has been proposed recently. Instead of mining the complete set of frequent patterns, the new model only finds out the maximal frequent patterns, which can generate all frequent patterns. FP-growth algorithm is one of the most efficient frequent-pattern mining methods published so far. However,because FP-tree and conditional FP-trees must be two-way traversable, a great deal memory is needed in process of mining. This paper proposes an efficient algorithm Unid_FP-Max for mining maximal frequent patterns based on unidirectional FP-tree. Because of generation method of unidirectional FP-tree and conditional unidirectional FP-trees, the algorithm reduces the space consumption to the fullest extent. With the development of two techniques：single path pruning and header table pruning which can cut down many conditional unidirectional FP-trees generated recursively in mining process, Unid_ FP-Max further lowers the expense of time and space.     

基于序列挖掘的分等级搜索可持续进化算法

讨论了最大频繁序列模式和公平竞争层次模型(HFC),设计了最大频繁序列模式的挖掘算法(MFSPMA),把MFSPMA同HFC结合起来,提出了基于序列挖掘技术的分等级搜索可持续进化算法(SEAHSM).该进化算法设置多个不同层次的种群为不同适应度水平的个体提供生存空间,采用最大频繁子模式挖掘算法挖掘种群中的优良基因,并将具有优良基因模块的新个体注入到不同适应度水平的种群,从而实现遗传信息的稳定继承,有效避免优良基因的丢失.实验结果表明:SEAHSM在维持遗传信息稳定性、避免早熟收敛、提高搜索精度等方面表现良好.     

快速频繁序列模式挖掘算法

为解决从数据库中挖掘长模式可能遇到较高的计算复杂度问题, 提出一种新的算法FFSPAN. 传统上, 要判断一个序列是否频繁, 需要在原数据库中判断整个序列是否频繁; 而算法FFSPAN是通过在序列数据库中寻找一个频繁项或一个频繁项集来代替寻找一个完整的频繁序列, 而且FFSPAN算法每次扫描的数据库都是迅速减小的, 这使得算法在挖掘的序列模式越长时越有效. 在标准测试数据集上的实验结果表明, FFSPAN算法非常有效.     

基于频繁模式树的正负项目集挖掘

传统的基于支持度—置信度框架的关联规则挖掘方法可能会产生大量不相关的、甚至是误导的关联规则,同时也不能区分正负关联规则。在充分考虑用户感兴趣模式的基础上,采用一阶谓词逻辑作为用户感兴趣的背景知识表示技术,提出了一种基于背景知识的包含正负项目集的频繁模式树,给出了针对正负项目集的约束频繁模式树的构造算法NCFP-Construct,从而提高了关联规则挖掘的效率和针对性,实验结果显示该方法是有效的。     

基于投影数据库的序列模式挖掘增量式更新算法

针对序列模式挖掘中的增量挖掘问题,提出一种序列模式更新算法ISPBP.算法引入序列数据库结构来存储从原始数据库中挖掘出的所有项、最大频繁模式以及它们的支持数,采用间接拼接方法,只需处理增量数据库,避免了对更新后数据库的重新计算.对于因增量数据库新产生的频繁模式,利用了在增量数据库中出现的频繁项集来减小投影数据库,进一步提高了算法的效率.理论分析和实验表明,算法是有效可行的,并且增量数据库越大,算法在效率上的优越性越明显,算法ISPBP优于传统增量式更新算法.