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

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

基于均值约束满足度剪枝策略的高效序列模式挖掘算法

为了减少无用候选序列的生成,并使挖掘得到的序列模式符合用户要求,约束条件下的频繁序列模式挖掘已成为数据挖掘领域的一个新的重要研究方向.作为强约束形式的一种,均值约束目前仍然是基于约束的频繁序列模式挖掘的一个困难问题,其主要原因在于很难利用均值约束来进行序列模式挖掘中的剪枝.为此,提出了一种基于均值约束满足度剪枝策略,并且以前缀增长方法为基础设计了一个有效的频繁序列模式挖掘算法.通过分析并实验验证了该算法的时间效率和剪枝性能,结果表明,该方法是有效的.     

基于前缀树的数据流频繁模式挖掘算法

针对数据流的无限性和流动性特点,提出了一种基于前缀树的数据流频繁模式挖掘算法(Prefix-stream).该算法将对数倾斜时间窗口划分为若干个子窗口,以子窗口为单位,利用提出的数据结构Prefix-tree进行挖掘,在整个数据流的频繁模式挖掘中,使得频繁模式挖掘和更新能在Prefix-tree中同时进行.该算法应用对数倾斜时间窗口逐步降低历史事务的权重,从而区分最近事务与历史事务.实验结果表明Prefix-stream具有较高的效率与较好的可扩展性.     

基于有序FP树和二维列表的频繁模式挖掘算法

关联法是数据挖掘算法中一种重要的技术,FP-Growth算法是当前最有效的关联法则挖掘算法,主要针对传统的FP-Growth算法当前的一些不足进行改进,提出了一种新的挖掘算法OFP树挖掘算法.一是采用了有序FP树代替传统的FP树,减少存储空间的使用,二是采用二维列表记录项的频繁度,省去为寻找第一次条件模式基而遍历FP树的过程.实验结果表明该算法优于传统FPGrowth算法.     

一种快速频繁模式挖掘算法

频繁模式挖掘是数据挖掘领域中一个重要的研究方向,目前已有很多算法被用于挖掘频繁模式.本文在研究FP-growth算法的基础上,提出一种新的频繁模式挖掘算法——QFP算法.首先对每一个频繁项建立一棵QFP树,进而根据设定的条件对每棵树进行挖掘,直到找出符合条件的频繁模式.实验证明该算法能够减少条件子树的生成数量,降低对内存空间的依赖和CPU的计算时间,从而提高关联规则挖掘的效率.     

基于FP_tree的最大频繁模式挖掘算法的改进

基于条件模式树的最大频繁模式挖掘算法在挖掘过程中将扫描事务数据库两次,且产生了大量的候选项目集,产生最大频繁模式过程中比较次数较多,总体效率较低.提出改进后的最大频繁模式挖掘策略,利用二维表保存事务出现项目的情况,通过最大频繁模式的相关性质减少了挖掘的项数及产生的频繁模式集,减少比较的次数.     

全向传感器网络中基于虚拟力的三维覆盖增强算法

针对全向传感器网络中的三维覆盖增强问题,简单的把二维覆盖增强算法扩展到三维空间,会存在覆盖性能不稳定、能耗大等缺陷,提出了一种基于虚拟力的三维覆盖增强算法.该算法通过传感器之间的节点斥力和节点引力以及传感器与目标区域边界之间的边界斥力来确保传感器的均匀分布,并使用覆盖因子来消除传感器的无效移动.仿真结果表明,所提算法不仅具有较好的收敛性,还能够显著地提高无线传感器网络的覆盖率.     

事务模式树分层挖掘算法及其应用

从事务数据、时间序列数据等数据库中挖掘频繁模式已在数据挖掘领域中得到了广泛地研究．针对目前已有的Apriori算法和频繁模式增长算法在时间和空间等方面的复杂性和低效性，提出了一种新的数据结构——事务模式树，用来存放待挖掘的事务信息，同时给出一种基于该数据结构的挖掘算法——事务模式树分层挖掘算法．最后，把该算法应用于保险业务．结果表明,该算法简单高效，值得推广.     

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

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

基因表达数据的频繁闭合模式挖掘新算法

基因表达数据集与传统事务数据集相比呈现出新的特征,由于其项目数远远大于事务数,使得大量现有的基于项目枚举的频繁闭合模式挖掘算法不再适用.为此提出一种频繁闭合模式挖掘新算法TPclose,使用TP-树(tidset-prefix tree)保存项目的事务集信息.该算法将频繁闭合模式挖掘问题转换成频繁闭合事务集挖掘问题,采取自顶向下分而治之的事务搜索策略,并组合了高效的修剪技术和有效的优化技术.实验表明,TPclose算法普遍快于自底向上事务搜索算法RERⅡ,最高达2个数量级以上.     

基于双向十字链表的频繁项集挖掘

有效地进行频繁项挖掘一直以来都是数据挖掘任务中最为重要的组成部分。已有的大部分频繁项挖掘算法在数据项多及支持度低的情况下,算法的效率急剧下降。为了有效地解决此类问题,提出了一种采用双向十字链表结构的频繁项挖掘算法(two-way crossed list for frequent itemsets mining,TCLFI)。极大地降低了搜索空间,加快了频繁项的筛选过程,减少了所需保存的数据项个数,从而降低了时间复杂度,提高了频繁项的挖掘效率。实验通过真实数据集和合成数据集验证了算法的有效性和扩展性。     

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.     

一种基于聚合链的改进FP-Growth算法

提出了一种基于聚合链挖掘频繁模式的改进FP-growth算法.该算法引入聚合链的单链表结构,改进了FP树结构.改进后的FP树是单向的,每个结点只保留指向父结点的指针,节省了树空间;相同项的不同节点的路径信息压缩进聚合链中,避免了生成节点链和条件模式库.用Agrawa方法生成实验数据进行分析,实验结果验证了该算法在时间上的优势.     

频繁序列模式挖掘算法

为解决从数据库中挖掘长模式和支持度较低时可能遇到计算复杂度较高的问题,提出一种新的算法--EFSPAN(Effective Frequent Sequential PAtterN mining algorithm).算法采用了深度优先挖掘策略,并将基于前缀序列格的深度优先遍历与两种高效的剪枝策略相结合.实验结果表明:新算法在模式较长和支持度较低时,能使搜索空间中60%以上的节点免被搜索;从而大大缩小了搜索空间,降低了序列模式挖掘算法的计算复杂度.     

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

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

半结构化文档数据流的快速频繁模式挖掘

为了提高半结构化文档数据流的挖掘效率,对原有挖掘算法StreamT进行了改进,提出了一种半结构化文档数据流的快速频繁模式挖掘算法--FStreamT.该算法针对利用集合存储候选频繁模式效率较低的缺点,采用枚举树存储候选频繁模式,可以有效地提高对候选频繁模式集合进行查找和更新的效率,同时利用频繁模式的单调性和枚举树的特点减小了维护负边界的搜索空间,从而提高了整个算法的效率.理论分析和实验结果表明,算法FStreamT与算法StreamT相比具有较高的效率,是有效可行的.     

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

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

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

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

数据流时间窗口中闭频繁项集的在线挖掘

在数据流闭频繁项集挖掘过程中,常忽略历史模式对挖掘结果的影响,并采用一种结构来标记闭频繁项集的类型,导致算法的效率不高.为此提出一种挖掘数据流时间窗口中闭频繁项集的方法NEWT-moment.该方法能在单遍扫描数据流事务的条件下完整地记录模式信息.同时,NEWT-moment提出的剪枝方法能很好地降低滑动窗口树F-tr...