快速统一挖掘超团模式和极大超团模式

超团模式是一种新型的关联模式,这种模式所包含的项目相互间具有很高的亲密度.超团模式中某个项目在事务中的出现很强地暗示了模式中其他项目也会相应地出现.极大超团模式是一组超团模式更加紧凑的表示,可被用于多种应用.挖掘这两种模式的标准算法是完全不同的.提出一种基于FP-tree(frequent pattern tree)的快速挖掘算法——混合超团模式增长(hybrid hyperclique pattern growth,简称HHCP-growth),统一了两种模式的挖掘.算法采用递归挖掘方法,并应用多种有效的剪枝策略.提出并证明几个相关命题来说明剪枝策略的有效性和算法的正确性.实验结果表明,HHCP-growth算法相对于标准的超团模式挖掘算法和极大超团模式挖掘算法都具有更高的效率,尤其对于大数据集或在低支持度条件下更为显著.     

一种基于前缀树的增量序列挖掘算法

在已有模式的基础上,该文挖掘出了新的模式,减少了挖掘原始数据库次数,指出了IncSpan+算法存在的问题,说明了基于半频繁模式的增量挖掘算法的缺陷,提出了一种增量序列模式挖掘算法。该算法构造了前缀树表示序列模式,并用广度剪枝和深度剪枝维护该前缀树的结构。实验表明,该算法具有良好的性能。     

频繁模式挖掘中的剪枝策略

本文在研究已有剪枝策略的基础上,提出一种基于堆栈的多层回退剪枝新技术,并给出一个采用该剪枝策略的最大频繁模式挖掘算法。分析与试验证明,该算法大大削减了搜索空间,效率优于已有同类算法。     

一种模糊对象的极大co-location模式挖掘算法

空间co-location模式表示的是空间对象的实例在一个相同的区域内频繁地进行空间并置。人们已经对确定和不确定数据co-location模式挖掘做了很多工作,也有很多成果,但对极大co-location模式挖掘研究较少,特别是针对模糊对象的极大co-location模式挖掘研究还未见报道。提出Mevent-tree算法来挖掘模糊对象的极大co-location模式,首先为每个对象构建空间对象树,从而得到候选模式,然后为候选模式集构建HUT树,最后在HUT树中从阶数最大的候选模式开始到阶数2为止,深度优先搜索极大co-location模式并在得到极大模式后对HUT树剪枝。接着提出两个改进算法,包括预处理阶段模糊对象的剪枝算法和在构造HUT树之前co-location候选模式的剪枝算法。最后通过大量实验验证了Mevent-tree算法和改进算法的效果和效率。     

基于事务拆分的超团挖掘算法

为发现处在低支持度下的潜在有趣模式,针对传统基于支持度策略的模式发现算法存在的问题,提出一种基于改进Relim算法的超团模式挖掘算法,将一个事务拆分为2个或多个事务,把相同事务进行压缩,并用Relim算法的思想进行超团模式挖掘。仿真实验结果表明,该算法能有效提高超团模式的挖掘效率。     

一种高效的周期团挖掘方法

周期团是在时态网络上出现时机满足特定周期要求的完全子图，周期团挖掘用于挖掘时态图中具有周期性的团。针对现有周期团挖掘方法效率低的问题，设计三种高效的剪枝策略EMP-FlagVex、EMP-FlagEdge和EMPFlagEdge+，并提出一种基于边上时间戳序列的求解方法 EMP。枚举满足要求的极大团，并对枚举出的极大团进行周期验证。验证操作是提取极大团每条边上的时间戳集合，并对集合中出现的时间点进行计数。若某个时间点出现的次数等于提取的集合个数，则将其放入新集合。在此基础上，判断新集合中的序列是否具有周期性。实验结果表明，相比基础方法 EMP，将EMP与EMP-FlagEdge+剪枝策略相结合的方法在PS、Lkml、Enron等数据集上的运行时间加快了15倍以上。相比MPC算法，基于顶点度数的EMP-FlagVex剪枝策略的挖掘效率提高约1倍，基于边上时间戳序列长度的EMP-FlagEdge剪枝策略的挖掘效率提高10倍，基于周期子序列长度的EMP-FlagEdge+剪枝策略的挖掘效率提高约30倍。     

关联规则中FP-tree的最大频繁模式非检验挖掘算法

基于FP-tree的最大频繁模式挖掘算法是目前较为高效的频繁模式挖掘算法,针对这些算法需要递归生成条件FP-tree、做超集检验等问题,在分析DMFIA-1算法的基础上,提出了最大频繁模式的非检验挖掘算法NCMFP。该算法改进了FP-tree的结构,使挖掘过程中不需要生成条件频繁模式树也不需要超集检验。算法采用的预测剪枝策略减少了挖掘的次数,采用的求取公共交集的方式保证了挖掘结果的完整性。实验结果表明在支持度相对较小情况下,NCMFP的效率是同类算法的2~5倍。     

一种有效的完全加权正负关联模式挖掘算法AWAPM_SPRMI

完全加权正负关联模式在文本挖掘、信息检索等方面具有重要的理论和应用价值.针对现有挖掘算法的不足,构建完全加权正负关联模式评价框架SPRMII(support-probability ratio-mutual information-interest),提出完全加权项集双兴趣度阈值剪枝策略,然后基于该剪枝策略提出一种新的基于SPRMII框架的完全加权正负关联模式挖掘算法AWAPM_SPRMII(all-weighted association patterns mining based on SPRMII).该算法克服了传统挖掘算法缺陷并采用新剪枝方法从完全加权数据库中挖掘有趣的频繁项集和负项集,通过项集权重维数比的简单计算和SPRMII评价框架,从这些项集中挖掘有效的完全加权正负关联规则.理论分析和实验表明,该算法有效,具有良好的扩展性,与现有经典挖掘算法比较,获得了良好的挖掘性能.     

空间极大co-location模式挖掘研究

空间co-location模式代表了一组空间特征的子集,它们的实例在空间中频繁地关联。挖掘空间co-location模式的研究已经有很多,但是针对极大co-location模式挖掘的研究非常少。提出了一种新颖的空间极大co-location模式挖掘算法。首先扫描数据集得到二阶频繁模式,然后将二阶频繁模式转换为图,再通过极大团算法求解得到空间特征极大团,最后使用二阶频繁模式的表实例验证极大团得到空间极大co-location频繁模式。实验表明,该算法能够很好地挖掘空间极大co-location频繁模式。     

序列模式增量式更新的快速算法

在原有序列模式挖掘算法基础上,提出了序列模式增量式更新的快速算法SPIU.算法充分利用原有的挖掘结果,并对候选序列集合进行有效地剪枝.测试结果表明,算法是正确和高效的,具有良好的扩放性.     

Mining maximal hyperclique pattern: A hybrid search strategy

A hyperclique pattern is a new type of association pattern that contains items which are highly affiliated with each other. Specifically, the presence of an item in one transaction strongly implies the presence of every other item that belongs to the same hyperclique pattern. In this paper, we present an algorithm for mining maximal hyperclique patterns, which specifies a more compact representation of hyperclique patterns and are desirable for many applications, such as pattern-based clustering. Our algorithm exploits key advantages of both the Depth First Search (DFS) strategy and the Breadth First Search (BFS) strategy. Indeed, we adapt the equivalence pruning method, one of the most efficient pruning methods of the DFS strategy, into the process of the BFS strategy. Our experimental results show that the performance of our algorithm can be orders of magnitude faster than standard maximal frequent pattern mining algorithms, particularly at low levels of support.     

Hyperclique pattern discovery

Existing algorithms for mining association patterns often rely on the support-based pruning strategy to prune a combinatorial search space. However, this strategy is not effective for discovering potentially interesting patterns at low levels of support. Also, it tends to generate too many spurious patterns involving items which are from different support levels and are poorly correlated. In this paper, we present a framework for mining highly-correlated association patterns called hyperclique patterns. In this framework, an objective measure called h-confidence is applied to discover hyperclique patterns. We prove that the items in a hyperclique pattern have a guaranteed level of global pairwise similarity to one another as measured by the cosine similarity (uncentered Pearson's correlation coefficient). Also, we show that the h-confidence measure satisfies a cross-support property which can help efficiently eliminate spurious patterns involving items with substantially different support levels. Indeed, this cross-support property is not limited to h-confidence and can be generalized to some other association measures. In addition, an algorithm called hyperclique miner is proposed to exploit both cross-support and anti-monotone properties of the h-confidence measure for the efficient discovery of hyperclique patterns. Finally, our experimental results show that hyperclique miner can efficiently identify hyperclique patterns, even at extremely low levels of support.

挖掘最大频繁模式的新方法

由于其内在的计算复杂性，挖掘密集型数据集的频繁模式完全集非常困难，解决方案之一是挖掘最大频繁模式集．该文在频繁模式完全集挖掘算法Opportune Project基础上，提出了挖掘最大频繁模式的新算法MOP．它采用宽度与深度优先相结合的混合搜索策略，能恰当地选择不同的支持集表示和投影方法，将闭合性剪裁和一般性剪裁相结合，并适时前窥，实现搜索与剪裁效率最优化．实验表明，MOP效率是MaxMiner的2～8倍，比MAFIA高2个数量级以上．     

数据流中基于滑动窗口的最大频繁项集挖掘算法*

挖掘数据流中最大频繁项集是从数据流中获得信息的一种有效手段,是数据流挖掘研究的热点之一。结合数据流的特点,提出了一种新的基于滑动窗口的最大频繁项集挖掘算法。该算法用位图来存储数据流中流动的数据;采用直接覆盖的方法存储和更新数据流上的数据;在深度优先搜索挖掘最大频繁项集时,除采用经典的剪枝策略外,还提出了与父等价原理相对应的子等价剪枝策略;最后将挖掘结果存储在索引链表中以提高超集检测效率,进一步减少挖掘最大频繁项集的时间。理论分析和实验结果证实了该算法在时间和空间上的有效性。     

Top-down mining of frequent closed patterns from very high dimensional data

Frequent pattern mining is an essential theme in data mining. Existing algorithms usually use a bottom-up search strategy. However, for very high dimensional data, this strategy cannot fully utilize the minimum support constraint to prune the rowset search space. In this paper, we propose a new method called top-down mining together with a novel row enumeration tree to make full use of the pruning power of the minimum support constraint. Furthermore, to efficiently check if a rowset is closed, we develop a method called the trace-based method. Based on these methods, an algorithm called TD-Close is designed for mining a complete set of frequent closed patterns. To enhance its performance further, we improve it by using new pruning strategies and new data structures that lead to a new algorithm TTD-Close. Our performance study shows that the top-down strategy is effective in cutting down search space and saving memory space, while the trace-based method facilitates the closeness-checking. As a result, the algorithm TTD-Close outperforms the bottom-up search algorithms such as Carpenter and FPclose in most cases. It also runs faster than TD-Close.     

有效的矩阵加权正负关联规则挖掘算法——MWARM-SRCCCI

针对现有加权关联规则挖掘算法不能适用于矩阵加权数据的缺陷,给出一种新的矩阵加权项集剪枝策略,构建矩阵加权正负关联模式评价框架SRCCCI,提出一种新的基于SRCCCI评价框架的矩阵加权正负关联规则挖掘算法MWARM-SRCCCI。该算法克服了现有挖掘技术的缺陷,采用新的剪枝技术和模式评价方法,挖掘有效的矩阵加权正负关联规则,避免一些无效和无趣的模式产生。以中文Web测试集CWT200g为实验数据,与现有无加权正负关联规则挖掘算法比较,MWARM-SRCCCI算法的挖掘时间减幅最大可达74.74%。理论分析和实验结果表明,MWARM-SRCCCI算法具有较好的剪枝效果,候选项集数量和挖掘时间明显减少,挖掘效率得到极大提高,其关联模式可为信息检索提供可靠的查询扩展词来源。     

MAXSeq: 一个新的最大频繁序列挖掘算法

最大频繁序列发现是数据挖掘中的一个重要分支．本文提出一种发现最大频繁序列集的算法MAXSeq，该算法通过对潜在的最大频繁序列进行选择性的扩展，直接判断其是否为最大序列，无须对候选最大序列进行维护，从而显著减小了存储开销．同时，优化策略的恰当运用对降低CPU时间起着至关重要的作用．     

垂直分布下的隐私保护关联规则挖掘

针对垂直分布下的隐私保护关联规则挖掘算法安全性不高和挖掘效率较低的问题,提出了一种隐私保护关联规则挖掘算法.算法采用一种新的点积协议,通过引入逆矩阵和随机数隐藏原始输入信息,具有较好的安全性;利用挖掘最大频繁项集来代替挖掘所有频繁项集,采用深度优先遍历策略,结合各种剪枝策略,明显加快了频繁项集的生成速度,大大减少计算代价.实验结果表明,挖掘效率得到了很大提高.