对比保序模式挖掘算法

针对现有的对比序列模式挖掘方法主要针对字符序列数据集且难以应用于时间序列数据集的问题，提出一种对比保序模式挖掘（COPM）算法。首先，在候选模式生成阶段，采用模式融合策略减少候选模式数；其次在模式支持度计算阶段，利用子模式的匹配结果计算超模式的支持度；最后，设计了动态最小支持度阈值的剪枝策略，以进一步有效地剪枝候选模式。实验结果表明，在6个真实的时间序列数据集上，在内存消耗方面，COPM算法至少比COPM-o(COPM-original)算法降低52.1%，比COPM-e(COPM-enumeration)算法低36.8%，比COPM-p(COPM-prune)算法降低63.6%；同时在运行时间方面，COPM算法至少比COPM-o算法降低30.3%，比COPM-e算法降低8.8%，比COPM-p算法降低41.2%。因此，在算法性能方面，COPM算法优于COPM-o、COPM-e和COPM-p算法。实验结果验证了COPM算法可以有效挖掘对比保序模式，发现不同类别的时间序列数据集间的差异。     

具有周期间隙约束的负序列模式挖掘

间隙约束的序列模式挖掘是一种特殊形式的序列模式挖掘方法，该方法能够揭示一定间隔下的频繁出现(发生)的子序列。但当前间隙约束的序列模式挖掘方法只关注正序列模式的挖掘，忽略了事件中的缺失行为。为解决该问题，探索了周期间隙约束的负序列模式(Negative Sequential Pattern with Periodic Gap Constraints, NSPG)挖掘方法，该方法能够更灵活地反映元素与元素之间的关系。为高效求解NSPG挖掘问题，提出了NSPG-INtree(Incomplete Nettrees)算法，该算法主要包括两个步骤：候选模式生成和支持度计算。在候选模式生成方面，为了减少候选模式的数量，该算法采用模式连接策略；在支持度计算方面，为了提高模式支持度计算效率并减少空间消耗，该算法采用不完整网树结构计算模式支持度。实验结果表明，NSPG-INtree算法不仅具有较高的挖掘效率，而且能同时挖掘间隙约束的正序列模式和负序列模式。与其他间隙约束的序列模式挖掘算法相比，NSPG-INtree能够多发现209%～352%的模式；与不同策略的对比算法相比，NSPG-INtree能够缩...     

基于图结构的候选序列生成算法

先生成候选序列再判断候选序列是否为频繁序列，最后获得频繁序列是序列数据挖掘中基于候选序列挖掘算法的一般结构，如Apriori类算法，GSP算法，SPADE算法等。因此，研究候选序列生成算法具有普遍意义。本文首先研究了序列数据集(序列数据库)与图结构间的关系，证明了一个序列是频繁序列的必要条件是该序列对应于一个完全子图。以此为基础提出了基于图结构的候选序列生成算法，文中给出了算法正确性证明。在T25110D10K和T25120D100K数据集上的挖掘实验表明在本文提出的候选序列生成算法上进行挖掘比用Apriori算法进行挖掘的效率更高。     

基于DBP的TOp-k高效用项集挖掘算法

针对Top-k高效用项集挖掘算法在挖掘过程中忽略内存管理的问题,提出基于DBP的Top-k高效用项集挖掘算法TKBPH(Top-k buffer pool high utility itemsets mining),采用数据缓冲池(DBP)结构存储效用链表,并由索引链表记录效用链表在DBP的位置.数据缓冲池根据挖掘过程情况在数据缓冲池尾部动态插入和删除效用链表,通过索引链表直接读取效用链表避免项集搜索时频繁的比较操作,有效减少内存空间和运行时间消耗.不同类型数据集上的实验结果表明,TKBPH算法在挖掘过程中执行速度更快、内存消耗更少.     

基于数据索引结构的跨级高效用项集挖掘算法

针对现有的跨级高效用项集挖掘（HUIM）算法非常耗时且占用大量内存的问题，提出一种基于数据索引结构的跨级高效用项集挖掘算法（DISCH）。首先，为了高效存储和快速检索到搜索空间中的所有项集，拓展带有分类信息和索引信息的效用链表为数据索引结构（DIS）；然后，为了提高内存利用率，对不满足条件的效用链表所占的内存进行回收再分配；最后，在构建效用链表时使用提前结束策略，以减少效用链表的产生。基于真实零售数据集和合成数据集进行的实验结果表明，与CLH-Miner(Cross-Level High utility itemsets Miner)算法相比，DISCH在运行时间上平均降低了77.6%，同时在内存消耗上平均降低了73.3%，可见该算法能高效完成跨级高效用项集的搜索，并且降低算法的内存消耗。     

基于列表结构的加权可擦除项集挖掘算法

可擦除项集挖掘是从大规模产品数据库中挖掘出低利润项集,以解决厂商财务危机的方法。传统挖掘方法只处理静态产品数据库,在提取可擦除项集时忽略项本身的权值。为解决现有可擦除项集挖掘算法考虑条件单一、效率低下的问题,提出一种有效的在增量数据集上挖掘加权可擦除项集的算法WELI。该算法综合考虑了数据不断积累和项具有不同重要性的因素,采用简洁的列表结构减少内存消耗,利用权重条件进行项集修剪,并结合包含索引和差集思想简化增益的计算过程,以实现高效的增量挖掘操作。实验表明：就运行时间和内存消耗而言,该算法在稠密数据集和稀疏数据集上均具有良好的实验效果,就可伸缩性而言,该算法也优于以往算法。     

基于二级索引结构无候选项闭合序列模式挖掘算法

针对CloSpan算法分两个阶段挖掘闭合序列模式中第一阶段需要保持候选序列且未充分利用项的位置信息、存在对数据库重复扫描和计算大小的不足,提出了posCloSpan算法。算法通过对二级索引结构进行检索实现向前剪枝,避免数据库重复扫描以及对超序索引表、子序索引表的检测,实现非闭合序列的修剪,无须保存候选序列。实验结果证明,算法在处理较长序列以及存在大量重复投影数据库的数据源时,有效降低了时间上的开销。     

基于多效用阈值的分布式高效用序列模式挖掘

针对序列模式的高效用模式挖掘过程中搜索空间大、计算复杂度高的问题,提出一种基于多效用阈值的分布式高效用序列模式挖掘算法。采用数组结构保存模式的效用信息,解决效用矩阵导致的内存消耗大的缺点。设计1-项集与2-项集的深度剪枝策略,深入地缩小候选模式的搜索空间,减少搜索时间成本与缓存成本。提出挖掘算法的分布式实现方案,通过并行处理进一步降低模式挖掘的时间。基于中等规模与大规模的序列数据集分别进行实验,实验结果表明,该算法有效减少了候选模式的数量,降低了挖掘的时间成本与存储成本,对于大数据集表现出较好的可扩展能力与稳定性。     

减少候选项集的数据流高效用项集挖掘算法

大数据环境下高效用项集挖掘算法中过多的候选项集极大地降低了算法的时空效率,提出了一种减少候选项集的数据流高效用项集挖掘算法。首先,通过数据流中当前窗口的一次扫描建立一个全局树,并降低全局树中头表入口与节点的冗余效用值;然后,基于全局树生成候选模式,基于增长算法降低局部树的候选项集效用;最终,从候选模式中选出高效用模式。基于真实数据流的实验结果表明,本算法的时空效率与内存占用比均优于其他数据流的高效用模式挖掘算法。     

一种基于倒排索引树的增量更新关联挖掘算法

增量更新关联规则挖掘主要解决事务数据库中交易记录不断更新和最小支持度发生变化时关联规则的维护问题。针对目前诸多增量更新关联规则挖掘算法存在效率低、计算成本高、规则难以维护等问题,提出一种基于倒排索引树的增量更新关联挖掘算法。该算法有效地将倒排索引技术与树型结构相结合,使得交易数据库中的数据不断更新和最小支持度随应用环境不同而不断改变时,以实现无需扫描原始交易数据库和不产生候选项集的情况下生成频繁项集。实验结果表明,该算法只需占用较小的存储空间、且检索项集的效率较高,能高效地解决增量更新关联规则难以维护的问题。     

基于优化上界的高平均效用项集垂直挖掘算法

高平均效用项集挖掘是当前研究的热点之一。针对高平均效用项集挖掘算法产生大量无意义的候选项集,而导致高内存消耗和运行时间长的问题,提出了dMHAUI算法。首先定义了集成矩阵Q,并提出了4种基于垂直数据库表示的紧凑平均效用上界及3种有效的修剪策略;将高平均效用项集挖掘所需的信息存储于IDUL结构树,利用改进的diffset技术快速计算项集的平均效用和上界;最后通过递归调用搜索函数得到高平均效用项集。与EHAUPM算法和MHAI算法进行仿真比较,结果表明,dMHAUI算法在运行时间、连接比较次数和可扩展性等方面都有较优的性能。     

基于密度约束和间隙约束的对比模式挖掘

对比模式挖掘是序列模式挖掘的一个重要分支,带有密度约束的对比模式有助于生物学家发现生物序列中的特殊因子的分布情况。为此,文中提出了MPDG (Mining distinguishing sequence Patterns based on Density and Gap constraint) 算法,该算法应用网树结构挖掘满足密度约束和间隙约束的对比模式,在仅需扫描一遍序列库的情况下,该算法可计算当前模式的所有超模式的支持度,从而提高挖掘效率。最后,在真实蛋白质数据集上进行实验,实验结果验证了MPDG算法的有效性。     

自动粒度选择的半结构化页面信息抽取

半结构化页面的数据记录间存在结构相似性,在先序遍历DOM树生成的标记序列中表现为重复出现的模式,可利用后缀树进行挖掘。由于标记序列可以在块粒度和文本粒度两个级别上展现,而不同粒度下产生的最佳抽取模式在抽取效果方面又表现出不确定性,因此提出一种自动粒度选择的半结构化页面信息抽取方法。算法从后缀树获取的重复模式中选取最大重复和串联重复构成候选模式集,通过特征参数确定两个粒度各自的最佳模式集,最后引入抽取结果规则度参数并进行综合评价,以确定抽取模式完成半结构化页面数据记录的自动抽取。     

基于Top-k的高效用模式挖掘算法

通过用户设定阈值获取高效用模式的算法效率较低且挖掘结果不一定满足用户需求。针对这一问题,基于EFIM算法提出一种高效用Top-k模式挖掘算法。由用户指定高效用模式个数来代替人为阈值设定。采用基于扩展效用和剩余效用的双重剪枝策略,有效控制模式的增长。在数据库投影过程中,应用事务排序及合并策略减少运行时间和内存消耗。实验结果表明,该算法在运行时间和内存消耗上具有较大优势,尤其适用于密集型数据集的高效用模式挖掘。     

基于R-list的Top-K高效用项集挖掘算法

针对现有的一阶段Top-K高效用项集挖掘算法挖掘过程中阈值提升慢,迭代时生成大量候选项集造成内存占用过多等问题,提出一种基于重用链表(R-list)的Top-K高效用挖掘算法RHUM。使用一种新的数据结构R-list来存储并快速访问项集信息,无需第2次扫描数据库进行项集挖掘。该算法重用内存以保存候选集信息,结合改进的RSD阈值提升策略对数据进行预处理,期间采用更严格的剪枝参数在递归搜索的过程中同时计算多个项集的效用来缩小搜索空间。在不同类型数据集中的实验结果表明:RHUM算法在内存效率方面均优于其他一阶段算法,且在K值变化时能保持稳定。     

改进的频繁项集挖掘算法及其应用研究

频繁模式增长(FP-growth)算法是挖掘频繁项集的经典算法,解决了挖掘频繁项集时需多次扫描数据库且产生大量候选项集的问题,但大多数基于FP-growth思想的算法在生成频繁项集时存在过程复杂、占用空间多的问题。为此,提出一种基于前序完全构造链表(PF-List)的频繁项集挖掘算法(PFLFIM)。该算法使用PF-List表示项集,通过简单比较和连接两个PF-List挖掘频繁项集,避免复杂的连接操作;使用包含索引、提前停止交集和父子等价策略对搜索空间进行优化,减少空间占用。通过实验验证,相比于FIN算法和negFIN算法,该算法在运行时间和内存占用方面具有更好的性能。将该算法应用于高校人力资源管理系统中进行关联规则挖掘,寻找影响人才发展的因素,为高校人才引进和选拔提供决策支持。     

基于差分隐私的频繁序列模式挖掘算法

针对当数据集含有敏感信息时,直接发布频繁序列模式本身及其支持度计数都有可能泄露用户隐私信息的问题,提出一种满足差分隐私（DP）的频繁序列模式挖掘（DP-FSM）算法。该算法利用向下封闭性质生成候选序列模式集,基于智能截断方法从候选模式中挑选出频繁的序列模式,最后采用几何机制对所选出模式的真实支持度添加噪声进行扰动。另外,为了提高挖掘结果的可用性,设计了一个阈值修正的策略来减小挖掘过程中的截断误差和传播误差。理论分析证明了该算法满足ε-差分隐私。实验结果表明了该算法在拒真率（FNR）和相对支持度误差（RSE）两个指标上明显低于对比算法PFS²,有效地提高了挖掘结果的准确度。     

基于改进的AprioriAll算法的Web序列模式挖掘研究

为了减少AprioriAll算法挖掘过程中候选序列的生成以及对序列数据库的扫描次数,提高算法的挖掘效率,提出了一种基于改进的AprioriAll算法的Web序列模式挖掘方法.首先对数据进行预处理,然后利用经过改进的AprioriAll算法进行模式挖掘.算法的改进主要有两点:一个通过改变候选序列的连接方式来减少候选序列的产生;二是通过减少不必要的数据库扫描操作来提高算法的效率.通过实验验证了改进后算法在Web序列模式挖掘过程中的高效性和正确性.     

无重复投影数据库扫描的序列模式挖掘算法

序列模式挖掘在Web点击流分析、自然灾害预测、DNA和蛋白质序列模式发现等领域有着广泛应用.基于频繁模式增长的PrefixSpan是目前性能最好的序列模式挖掘算法之一.然而在密数据集和长序列模式挖掘过程中会出现大量的重复投影数据库,使得这类算法性能下降.算法SPMDS通过对投影数据库的伪投影做单项杂凑函数,如MD5等,检查是否存在重复的投影数据库,避免大量重复数据库的扫描,并采用一些必要条件简化投影数据库的搜索,进而提高算法的性能.实验和分析都表明SPMDS性能优于PrefixSpan.     

一种基于大项集重用的序列模式挖掘算法

在重新定义序列模式的长度、增加了序列模式的挖掘粒度的基础上，提出一种基于大项集重用的序列模式挖掘算法HVSM．该算法采用垂直位图法表示数据库，先横向扩展项集，将挖掘出的所有大项集组成一大序列项集，再纵向扩展序列，将每个一大序列项集作为“集成块”，在挖掘k大序列时重用大项集．并以兄弟节点为种子生成候选大序列，利用1st—TID对支持度进行计数．实验表明，对于大规模事务数据库，该算法有效地提高了挖掘效率．