基于二维数组的序列模式挖掘方法研究

本文介绍了两种主要的序列模式挖掘方法,在已有二进制算法的基础上提出了一种基于二维数组与二进制形式的频繁序列的计算方法.该方法通过二维数组实现事务数据库的存储,利用 "或"、"与"、"异或"等逻辑运算计算序列的支持度计数和确定频繁序列模式,减少了数据库的扫描次数,降低了算法实现的难度,提高了挖掘效率,具有较好的创新性和理论价值.     

频繁序列模式更新算法

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

一种改进的关联规则挖掘算法

从大型事务数据库中发现关联规则是数据挖掘中的一个重要课题,其核心问题是挖掘频繁项集.经典Apriori算法是有效的挖掘频繁项目集的算法.在分析Apriori算法的基础上,提出了一种利用二维数组来代替算法中的哈希树的方法,可以迅速产生二阶频繁项目集,改善了Apriori算法的效率瓶颈,大大提高了算法的执行效率.     

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

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

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

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

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

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

基于向量的频繁项集挖掘算法研究

针对Apriori算法寻找频繁项集时,需要多次扫描事务数据库和可能产生大量候选项集的问题,提出了一种向量和数组相结合的频繁项集挖掘算法。该算法不仅实现了只扫描事务数据库一次,而且避免了模式匹配,减少了无价值的候选项集的产生。通过与已有算法的比较,验证了本文算法具有较高的挖掘效率,而且数据库的项数越多,此算法的挖掘效果越明显。     

序列模式的一种挖掘算法

序列模式挖掘是数据挖掘中最重要的研究课题之一。基于记录数据库频繁集中各元素CtiD表的基础上,提出了序列模式挖掘的一种算法ISP。该算法考虑了项目集与序列之间的关系,利用时序连接法,采用不同的构造法,构造出相对应的候选集,从而计算出频繁集。由于算法ISP能够利用中间的挖掘结果,故提高了挖掘过程的效率。     

基于投影位置的序列模式挖掘算法

针对PrefixSpan算法在产生频繁序列模式(特别是挖掘密数据集和长序列模式)时会产生大量的投影数据库,使得算法性能下降的问题,提出一种基于投影位置的序列模式挖掘(PSPM)算法.该算法利用Apriori性质舍弃对非频繁项存储,节省了存储空间和扫描不可能出现序列的挖掘时间;在递归挖掘过程中,利用投影位置表直接定位投影序列位置进行挖掘局部频繁项,避免了构造投影数据库,从而提高执行效率.实验结果表明:与PrefixSpan(with pseudo-pro)算法相比,PSPM具有更好的执行效率和可伸缩性.     

一种面向物流数据分析的路径序列挖掘算法ImGSP

为了有效地挖掘物流管理系统中的物流频繁路径序列模式,提出了一种针对物流数据分析的路径序列挖掘算法ImGSP算法.ImGSP算法通过对原始路径数据库筛选,选出路径序列长度大于或等于候选序列长度的路径序列,有针对性地产生过度候选序列,来约减候选序列.实验结果表明:ImGSP算法能够有效地减少候选序列数量,生成频繁路径序列模式,进而产生物流中有用的规则.该方法不仅缩小了扫描数据库的规模,而且减少了生成频繁序列的候选序列集合.     

CSE算法:利用对频繁序列扩展来进行序列模式挖掘

序列模式挖掘是在多个有序事件序列中查找出现频率大于某个阈值的序列模式的数据挖掘方法 ,自从1995年序列模式挖掘的概念被提出以来 ,人们不断地对序列模式挖掘算法进行研究和改进 .本文介绍了一种新的序列模式挖掘方法—CSE算法及其具体实现方法 ,并对该算法性能做了初步的评价 .     

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

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

基于区间编码挖掘邻近序列模式

提出一种快速挖掘邻近序列模式的RCSP算法。该算法只需扫描一次数据库,且通过建立前序链接编码树,借助结点的区间编码,可以在常数时间内确定序列在树中的不同映射片段之间的祖孙关系,实现序列支持数的快速计算,不必额外创建中间树,直接在树上进行挖掘,就能得到所有邻近序列模式。实验表明RCSP算法具有较好的性能。     

A New Hybrid Algorithm for Association Rule Mining

HA (hashing array), a new algorithm, for mining frequent itemsets of large database is proposed. It employs a structure hash array, ItemArray ( ) to store the information of database and then uses it instead of database in later iteration. By this improvement, only twice scanning of the whole database is necessary, thereby the computational cost can be reduced significantly. To overcome the performance bottleneck of frequent 2-itemsets mining, a modified algorithm of HA, DHA (direct-addressing hashing and array) is proposed, which combines HA with direct-addressing hashing technique. The new hybrid algorithm, DHA, not only overcomes the performance bottleneck but also inherits the advantages of HA. Extensive simulations are conducted in this paper to evaluate the performance of the proposed new algorithm, and the results prove the new algorithm is more efficient and reasonable.     

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

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

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

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

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

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