一种挖掘压缩序列模式的有效算法

从序列数据库中挖掘频繁序列模式是数据挖掘领域的一个中心研究主题,而且该领域已经提出和研究了各种有效的序列模式挖掘算法.由于在挖掘过程中会产生大量的频繁序列模式,最近许多研究者已经不再聚焦于序列模式挖掘算法的效率,而更关注于如何让用户更容易地理解序列模式的结果集.受压缩频繁项集思想的启发,提出了一种CFSP(compressing frequent sequential patterns)算法,其可挖掘出少量有代表性的序列模式来表达全部频繁序列模式的信息,并且清除了大量的冗余序列模式.CFSP是一种two-steps的算法:在第1步,其获得了全部闭序列模式作为有代表性序列模式的候选集,与此同时还得到大多数的有代表性模式;在第2步,该算法只花费了少量的时间去发现剩余的有代表性序列模式.一个采用真实数据集与模拟数据集的实验研究也证明了CFSP算法具有高效性.     

RAKING:一种高效的不确定图K-极大频繁模式挖掘算法

由于不确定图蕴含了指数级的可能图实例,基于确定图模型的频繁图模式挖掘算法通常难以在不确定图集合上高效运行.文中提出了一种不确定图数据集上的基于随机游走的K极大频繁子模式挖掘算法.首先,将每个不确定图转换为相应的确定图并挖掘候选频繁模式;然后,将候选频繁模式恢复为不确定图并生成极大频繁模式搜索空间;最后,通过随机游走以相同概率随机地选择K个极大频繁模式.理论分析和实验结果表明文中提出的算法能够高效地获得不确定图集合的K-极大频繁模式.     

改进的频繁闭情节挖掘算法

为克服FCMMiner算法在挖掘频繁闭情节时存在的不足,基于最小且非重叠发生的支持度定义,提出一种事件序列上频繁闭情节挖掘算法FCM++。定义两种特殊的数据结构:频繁情节树(FET)、层头表(LH),采用广度优先搜索策略进行层扩展操作,扩展时将挖掘的频繁情节逐层压缩到FET和LH结点链中。通过动态维护FET及闭合性检查过程挖掘所有的频繁闭情节。实验结果表明,FCM++算法较FCMMiner算法有更高的挖掘效率,能有效地挖掘所有的频繁闭情节。     

挖掘不确定频繁子图的改进算法的研究

鉴于图结构能简单方便地描绘复杂的数据以及实际应用中图数据的获得具有不确定性,不确定频繁子图挖掘算法得到广泛的研究。目前一个典型的图挖掘算法是MUSE,但MUSE算法存在期望支持度计算消耗大、时间效率不够高等问题。针对此问题提出了一种基于划分思想混合搜索策略的不确定子图挖掘算法EDFS,它用改进过的GSpan算法进行不确定的子图数据预处理,用裁剪子图模式的搜索空间裁剪不确定子图数据,用基于划分思想的混合策略进行频繁子图的挖掘。子图同构与边存在概率的实验结果证明了EDFS算法能更高效地挖掘出不确定数据频繁子图。     

基于相邻频繁模式段的闭合序列模式挖掘算法

直接对生物序列进行频繁模式挖掘会产生很多冗余模式,闭合模式更能表达出序列的功能和结构。根据生物序列的特点,提出了基于相邻闭合频繁模式段的模式挖掘算法－JCPS。首先产生闭合相邻频繁模式段,然后对这些闭合频繁模式段进行组合,同时进行闭合检测,产生新的闭合频繁模式。通过对真实的蛋白质序列家族库的处理,证明该算法能有效处理生物序列数据。     

不确定数据频繁闭项集挖掘算法

由于不确定数据的向下封闭属性,挖掘全部频繁项集的方法会得到一个指数级的结果。为获得一个较小的合适的结果集,研究了在不确定数据上挖掘频繁闭项集,并提出了一种新的频繁闭项集挖掘算法——NA-PFCIM。该算法将项集挖掘过程看作一个概率分布函数,考虑到基于正态分布模型的方法提取的频繁项集精确度较高,而且支持大型数据库,采用了正态分布模型提取频繁项集。同时,为了减少搜索空间以及避免冗余计算,利用基于深度优先搜索的策略来获得所有的概率频繁闭项集。该算法还设计了两个剪枝策略:超集修剪和子集修剪。最后,在常用的数据集(T10I4D100K、Accidents、Mushroom、Chess)上,将提出的NA-PFCIM算法和基于泊松分布的A-PFCIM算法进行比较。实验结果表明,NA-PFCIM算法能够减少所要扩展的项集,同时减少项集频繁概率的计算,其性能优于对比算法。     

本地化差分隐私下的频繁序列模式挖掘算法PrivSPM

序列数据中可能包含大量敏感信息,因此直接对序列数据的频繁模式进行挖掘存在泄露用户隐私信息的风险。本地化差分隐私（LDP）能够抵御具有任意背景知识的攻击者,可以对敏感信息提供更全面的保护。序列数据内在序列性和高维度的特点为LDP应用于频繁序列模式挖掘带来了挑战。为解决这个问题,提出一种满足ε-LDP的top-k频繁序列模式挖掘算法PrivSPM。该算法结合填充和采样技术、自适应频率估计算法与频繁项预测技术来构造候选集;基于新域,利用基于指数机制的策略对用户数据进行扰动,并结合频率估计算法识别最终的频繁序列模式。理论分析证明了该算法满足ε-LDP。在3个真实数据集上的实验结果表明,PrivSPM算法在纳真率（TPR）和归一化累积排名（NCR）上明显高于对比算法,能有效提高挖掘结果的准确度。     

基于约束的不确定数据频繁项集挖掘算法研究

针对基于约束的不确定数据频繁项的经典挖掘算法——U-FPS算法的不足,提出了适用于基于约束的不确定数据的新算法——UC-Eclat挖掘算法。该算法不需要构建频繁模式树,而采用了数据库垂直模式求交集的方式来计算支持度的方法,提高了挖掘效率。     

GFExtractor：事件序列上有效挖掘无冗余情节规则的算法

事件序列上挖掘情节规则,旨在发现情节之间的因果关系。基于非重叠的最小发生的支持度定义及深度优先搜索策略,提出在事件序列上挖掘无冗余情节规则的GFExtractor算法。利用非生成子情节的剪枝策略,淘汰非生成子情节;利用向前、向后扩展检查,淘汰非闭情节;最终在情节生成子集Gen与频繁闭情节集FCE之间产生无冗余的情节规则。实验结果证实了算法在事件序列上挖掘无冗余情节规则的有效性。     

基于相邻模式段组合的生物序列模式挖掘算法

传统的序列模式挖掘算法应用在生物序列上有其局限性,根据生物序列的特点,提出了基于相邻频繁模式段的模式挖掘算法－JPS。首先产生相邻频繁模式段,然后对这些频繁模式段进行组合,产生新的频繁模式。通过实验分析,该方法在相似性很强的序列数据库中比传统的PrefixSpan算法效率高。通过对真实的蛋白质序列家族库的处理,证明该算法能有效处理生物序列数据。     

基于数据流频繁闭合模式的挖掘

用挖掘频繁闭合模式集代替挖掘频繁模式集是近年来提出的一个重要策略。根据数据流的特点,提出了一种基于滑动窗口的频繁闭合模式的新方法DSFC_Mine。该算法以滑动窗口中的基本窗口为更新单位,利用改进的CHARM算法计算每个基本窗口的潜在频繁闭合项集,将它们存储到一种新的数据结构中,利用该数据结构可以快速地挖掘滑动窗口中的所有频繁闭合项集。实验验证了该算法在时间上和空间上的可行性和有效性。     

基于不确定性数据的频繁闭项集挖掘算法

对于不确定性数据,传统判断项集是否频繁的方法并不能准确表达项集的频繁性,同样对于大型数据,频繁项集显得庞大和冗余。针对上述不足,在水平挖掘算法Apriori的基础上,提出一种基于不确定性数据的频繁闭项集挖掘算法UFCIM。利用置信度概率表达项集频繁的准确性,置信度越高,项集为频繁的准确性也越高,且由于频繁闭项集是频繁项集的一种无损压缩表示,因此利用压缩形式的频繁闭项集替代庞大的频繁项集。实验结果表明,该算法能够快速地挖掘出不确定性数据中的频繁闭项集,在减少项集冗余的同时保证项集的准确性和完整性。     

数据流中频繁闭合模式的挖掘

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

不确定数据频繁项集挖掘方法综述

近几年来,不确定数据广泛出现在传感器网络、Web应用等领域中。不确定数据挖掘已经成为了新的研究热点,主要包括聚类、分类、频繁项集挖掘、孤立点检测等方面,其中频繁项集挖掘是重点研究的问题之一。综述了传统的频繁项集挖掘的两类基本算法,分析了在此基础上提出的适用于不确定数据以及不确定数据流的频繁项集挖掘的方法,并探讨了今后可能的研究方向。     

一种不确定性数据频繁模式的垂直挖掘算法

由于数据的不确定性,传统频繁模式挖掘方法难以适用到不确定性数据中.针对不确定性数据的特点,把挖掘确定性数据频繁模式的经典垂直挖掘算法Eclat算法扩展到不确定性数据中,提出了UP-Eclat算法.该算法分别对Tid集和项集搜索树进行扩展:把原来只有一个id域的Tid扩展成两个域,即id域和概率域;用扩展后的Tid集代替原来的Tid集,生成扩展后的项集搜索树.扩展后的Tid集可以表示不确定性数据,然后利用扩展后的项集搜索树进行频繁模式挖掘.通过实验与分析,UP-Eclat算法可行,高效.     

一种基于Spark的不确定数据集频繁模式挖掘算法

如何在海量不确定数据集中提高频繁模式挖掘性能是目前研究的热点.传统算法大多是以期望、概率或者权重等单一指标为数据项集支持度，在大数据背景下，同时考虑概率和权重支持度的算法难以兼顾其执行效率.为此，本文提出一种基于Spark的不确定数据集频繁模式挖掘算法（UWEFP），首先，为了同时兼顾数据项的概率和权重，计算一项集的最大概率权重值并进行剪枝；然后，为了减少对数据集的多次扫描，结合Spark框架的优点，设计了一种具有FP-tree特征的新颖的UWEFP-tree结构进行模式树的构建及挖掘；最后在Spark环境下，以UCI数据集进行实验验证.实验结果表明本文的方法在保证挖掘结果的同时，提高了效率.     

MFCPLG：微阵列数据中频繁闭合模式挖掘

微阵列数据集行少列多的特征，使得传统基于列枚举空间的算法应用于其中进行频繁闭合模式挖掘时其复杂性迅速增长。基于行枚举的CARPENTER算法较好解决了该问题。但CARPENTER算法使用映射转置表(TT)来完成频繁闭合模式完全集的挖掘效率不高。该文在CARPENTER算法基础上，提出LG-tree数据结构，并基于此结构提出挖掘频繁闭合模式的新算法MFCPLG。真实数据集的实验表明，MFCPLG算法的时间性能优于CARPENTER算法。     

基于滑动窗口的数据流闭合频繁模式的挖掘

频繁闭合模式集惟一确定频繁模式完全集并且数量小得多,然而,如何挖掘滑动窗口中的频繁闭合模式集是一个很大的挑战．根据数据流的特点,提出了一种发现滑动窗口中频繁闭合模式的新方法DS_CFI．DS_CFI算法将滑动窗口分割为若干个基本窗口,以基本窗口为更新单位。利用已有的频繁闭合模式挖掘算法计算每个基本窗口的潜在频繁闭合项集,将它们及其子集存储到一种新的数据结构DSCFI_tree中,DSCFI_tree能够增量更新,利用DSCFI_tree可以快速地挖掘滑动窗口中的所有频繁闭合模式．最后,通过实验验证了这种方法的有效性．     

Efficient Mining of Frequent Closed XML Query Pattern

Previous research works have presented convincing arguments that a frequent pattern mining algorithm should not mine all frequent but only the closed ones because the latter leads to not only more compact yet complete result set but also better efficiency. Upon discovery of frequent closed XML query patterns, indexing and caching can be effectively adopted for query performance enhancement. Most of the previous algorithms for finding frequent patterns basically introduced a straightforward generate-and-test strategy. In this paper, we present SOLARIA＊, an efficient algorithm for mining frequent closed XML query patterns without candidate maintenance and costly tree-containment checking. Efficient algorithm of sequence mining is involved in discovering frequent tree-structured patterns, which aims at replacing expensive containment testing with cheap parent-child checking in sequences. SOLARIA＊ deeply prunes unrelated search space for frequent pattern enumeration by parent-child relationship constraint. By a thorough experimental study on various real-life data, we demonstrate the efficiency and scalability of SOLARIA＊ over the previous known alternative. SOLARIA＊ is also linearly scalable in terms of XML queries＇ size.