一种无阈值的频繁模式生成算法

在数据挖掘的关联规则挖掘算法中,传统的频繁模式挖掘算法需要用户指定项集的最小支持度。引入Top-k模式挖掘概念的改进算法虽然无需指定最小支持度,但仍需指定阈值k。针对上述问题,对传统挖掘算法进行改进,提出一种新的频繁模式挖掘算法(TNFP- growth)。该算法无需指定最小支持度或阈值,按照支持度降序排列进行模式挖掘,有序地返回频繁模式给用户。实验结果证明,该算法的执行效率更高,具有更强的伸缩性。     

面向健康体检数据的多目标Top-k频繁模式挖掘方法

为解决现有的模式挖掘方法没有充分利用体检数据中检查项的异常程度与特定疾病之间相关性的问题,提出一种面向健康体检数据的多目标Top-k频繁模式挖掘方法.首先,针对体检数据的特点,提出异常度和覆盖率两个指标,在此基础上,将Top-k频繁模式挖掘建模为一个多目标优化问题;其次,针对该问题,提出一种基于偏好的种群初始化策略和一个面向模式和项的双层更新策略,并基于此设计一种高效的进化多目标优化算法进行求解.实验结果表明,所提出方法所获得的Top-k个模式不仅能够有效地反映其与特定疾病之间的关联性,而且能够提供多样化的模式,为健康管理提供重要的参考依据.     

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

摘 要: 高效用模式挖掘被广泛应用于数据挖掘领域。为了挖掘指定数量的高效用模式,一些基于树结构和效用表结构的top-k高效用挖掘算法被提出,但前者在挖掘过程中产生了大量候选模式,后者在效用模式增长时需要进行多次比较。同时,由于在信息社会,数据量呈爆炸性增长。因此,在数据集过大的情况下,挖掘高效用模式需以大量存储空间以及计算开销为代价。为了解决这两个问题,基于MapReduce的top-k高效用模式挖掘算法（TKHUP_MaR）被提出。该算法通过两次扫描数据库,利用三次MapReduce来实现并行top-k高效用模式的挖掘。通过实验表明TKHUP_MaR 算法在并行挖掘top-k高效用模式的过程中是有效的。     

基于矩阵的数据流Top-k频繁项集挖掘算法

传统的数据挖掘算法在挖掘频繁项集时会产生大量的冗余项集,影响挖掘效率。为此,提出一种基于矩阵的数据流Top-k频繁项集挖掘算法。引入2个0-1矩阵,即事务矩阵和二项集矩阵。采用事务矩阵表示滑动窗口模型中的事务列表,通过计算每行的支持度得到二项集矩阵。利用二项集矩阵得到候选项集,将事务矩阵中对应的行做逻辑与运算,计算出候选项集的支持度,从而得到Top-k频繁项集。把挖掘的结果存入数据字典中,当用户查询时,能够按支持度降序输出Top-k频繁项集。实验结果表明,该算法在挖掘过程中能避免冗余项集的产生,在保证正确率的前提下具有较高的时间效率。     

ETARM: an efficient top-k association rule mining algorithm

Mining association rules plays an important role in data mining and knowledge discovery since it can reveal strong associations between items in databases. Nevertheless, an important problem with traditional association rule mining methods is that they can generate a huge amount of association rules depending on how parameters are set. However, users are often only interested in finding the strongest rules, and do not want to go through a large amount of rules or wait for these rules to be generated. To address those needs, algorithms have been proposed to mine the top-k association rules in databases, where users can directly set a parameter k to obtain the k most frequent rules. However, a major issue with these techniques is that they remain very costly in terms of execution time and memory. To address this issue, this paper presents a novel algorithm named ETARM (Efficient Top-k Association Rule Miner) to efficiently find the complete set of top-k association rules. The proposed algorithm integrates two novel candidate pruning properties to more effectively reduce the search space. These properties are applied during the candidate selection process to identify items that should not be used to expand a rule based on its confidence, to reduce the number of candidates. An extensive experimental evaluation on six standard benchmark datasets show that the proposed approach outperforms the state-of-the-art TopKRules algorithm both in terms of runtime and memory usage.     

基于节点集Top-k频繁模式挖掘算法

频繁模式挖掘的模式数量通常过于巨大,在实际应用中只有少量的频繁模式被使用。Top-k频繁模式挖掘通过排列模式频数限制频繁模式的数量,有效提高了算法效率。提出了TPN（Top-k-Patterns based on Nodesets）算法,该算法使用了节点集的概念,将数据压缩于Poc-tree,通过Top-k-rank表重新计算最小支持度限制生成候选模式的数量。实验通过与ATFP,Top-k-FP-growth算法比较,证明该算法有较好的效率。     

一种快速挖掘Top-k高效用模式的算法

高效用模式挖掘是数据挖掘领域的一个基础研究方向,其中关于top-k高效用模式的挖掘算法也越来越多,其中k指的是用户需要挖掘的高效用模式的个数。它们可以归纳为两类：二阶段top-k算法和一阶段top-k算法。两者的主要区别是,前者在挖掘的过程中会产生大量的候选模式,这个是影响算法性能的主要因素;后者在挖掘的过程中不产生候选模式。为了更加高效地挖掘效用值最高的k个模式,一阶段算法TKHUP被提出。该算法在进行数据挖掘的过程中主要是通过四个有效策略来减少时间和空间消耗的。通过大量的实验数据表明,TKHUP在时间性能上优于其它top-k高效用模式挖掘算法。     

Mining top-k frequent patterns over data streams sliding window

Frequent pattern mining in data streams is an important research topic in the data mining community. In previous studies, a minimum support threshold was assumed to be available for mining frequent patterns. However, setting such a threshold is typically difficult. Hence, it is more reasonable to ask users to set a bound on the result size. The present study considers mining top-k frequent patterns from data streams using a sliding window technique. A single-pass algorithm, called MSWTP, is developed for the generation of top-k frequent patterns without a threshold. In the method, the content of the transactions in the sliding window is incrementally maintained in a summary data structure, named SWTP-tree, by scanning the stream only once. To make the mining operation efficient, insignificant patterns are distinguished from others by applying the Chernoff bound. Two kinds of obsolete pattern and one kind of insignificant pattern are periodically pruned from the pattern tree. Whenever necessary, the k most frequent patterns can be selected from SWTP-tree in order of their descending frequency. The performance of the proposed technique is evaluated via simulation experiments. The results show that the proposed method is both efficient and scalable, and that it outperforms comparable algorithms.     

最大目标频繁模式挖掘算法研究

传统的频繁模式挖掘算法往往会得到成百上千的结果模式,面对繁多的频繁模式用户通常要经过“二次挖掘”才能得到有用的目标模式。怎样根据用户需求直接挖掘用户感兴趣的目标模式是该文的研究目标。文章在FP-树的基础上设计了紧缩的、非冗余的TFP-树,它能有效过滤与目标模式无关的项和事务,而仅保留与目标模式相关的信息,缩小TFP-树的大小规模。同时根据TFP-树的规律和特点,笔者设计了最大目标频繁模式挖掘算法,算法的结果模式具有以下两个特点:(1)满足用户需求的目标模式;(2)最大模式。该实验结果验证了TFP-树算法是有效的,而且显著改善了FP-树算法的性能。     

基于复合粒度计算的频繁模式挖掘研究

针对经典频繁模式挖掘算法存在的不足,提出了一种基于复合粒度计算的频繁模式挖掘算法。该算法借助复合粒度计算方法双向搜索频繁模式,即首先通过二进制的按位取反运算获得复合粒度内涵的像,然后构建复合粒度计算发现频繁模式;虽然该算法需要产生候选项,但它只需扫描一次数据库,减少了I/O开销;算法通过线性数组存储复合信息粒度减少内存使用。理论分析和实验比较表明,其效率优于经典的频繁模式挖掘算法,且内存利用率比较高。     

数据流频繁模式挖掘综述

一些先进应用如欺诈检测和趋势学习等带来了数据流频繁模式挖掘的发展。不同于静态数据,数据流挖掘面临着时空约束和项集组合爆炸等问题。对已有数据流频繁模式挖掘算法进行综述并对经典和最新算法进行分析。按照模式集合的完整程度进行分类,数据流中频繁模式分为全集模式和压缩模式。压缩模式主要包括闭合模式、最大模式、top-k模式以及三者的组合模式。不同之处是闭合模式是无损压缩的,而其他模式是有损压缩的。为了得到有趣的频繁模式,可以挖掘基于用户约束的模式。为了处理数据流中的新近事务,将算法分为基于窗口模型和基于衰减模型的方法。数据流中模式挖掘常见的还包含序列模式和高效用模式,对经典和最新算法进行介绍。最后给出了数据流模式挖掘的下一步工作。     

Sliding window based weighted maximal frequent pattern mining over data streams

As data have been accumulated more quickly in recent years, corresponding databases have also become huger, and thus, general frequent pattern mining methods have been faced with limitations that do not appropriately respond to the massive data. To overcome this problem, data mining researchers have studied methods which can conduct more efficient and immediate mining tasks by scanning databases only once. Thereafter, the sliding window model, which can perform mining operations focusing on recently accumulated parts over data streams, was proposed, and a variety of mining approaches related to this have been suggested. However, it is hard to mine all of the frequent patterns in the data stream environment since generated patterns are remarkably increased as data streams are continuously extended. Thus, methods for efficiently compressing generated patterns are needed in order to solve that problem. In addition, since not only support conditions but also weight constraints expressing items’ importance are one of the important factors in the pattern mining, we need to consider them in mining process. Motivated by these issues, we propose a novel algorithm, weighted maximal frequent pattern mining over data streams based on sliding window model (WMFP-SW) to obtain weighted maximal frequent patterns reflecting recent information over data streams. Performance experiments report that MWFP-SW outperforms previous algorithms in terms of runtime, memory usage, and scalability.     

Efficient mining of high utility pattern with considering of rarity and length

Techniques for mining rare patterns have been researched in the association rule mining area because traditional frequent pattern mining methods have to generate a large amount of unnecessary patterns in order to find rare patterns from large databases. One such technique, the multiple minimum support threshold framework was devised to extract rare patterns by using a different minimum item support threshold for each item in a database. Nevertheless, this framework cannot sufficiently reflect environments of the real world. The reason is that it does not consider weights of items, such as market prices of products and fatality rates of diseases, in its mining process. Therefore, an algorithm has been proposed to mine rare patterns with utilities exceeding a user-specified minimum utility by considering rarity and utility information of items. However, since this algorithm employs the concept of traditional high utility pattern mining, patterns’ lengths are not considered for determining utilities of the patterns. If the length of a pattern is sufficiently long, the pattern is more likely to have an enough utility to become a high utility pattern regardless of item utilities within the pattern. Therefore, the algorithm cannot guarantee that all items in a mined pattern have high utilities. In this paper, we propose a novel algorithm that effectively reduces such dependency of patterns on their lengths by considering their lengths in the mining process in order to mine more meaningful rare patterns compared to patterns mined by previous algorithms. Experimental results demonstrate that our algorithm extracts a lesser number of more meaningful patterns and consumes less computational resources compared to state-of-the-art algorithms.     

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

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

Discovery of frequent DATALOG patterns

Discovery of frequent patterns has been studied in a variety of data mining settings. In its simplest form, known from association rule mining, the task is to discover all frequent itemsets, i.e., all combinations of items that are found in a sufficient number of examples. The fundamental task of association rule and frequent set discovery has been extended in various directions, allowing more useful patterns to be discovered with special purpose algorithms. We present WARMR, a general purpose inductive logic programming algorithm that addresses frequent query discovery: a very general DATALOG formulation of the frequent pattern discovery problem.The motivation for this novel approach is twofold. First, exploratory data mining is well supported: WARMR offers the flexibility required to experiment with standard and in particular novel settings not supported by special purpose algorithms. Also, application prototypes based on WARMR can be used as benchmarks in the comparison and evaluation of new special purpose algorithms. Second, the unified representation gives insight to the blurred picture of the frequent pattern discovery domain. Within the DATALOG formulation a number of dimensions appear that relink diverged settings.We demonstrate the frequent query approach and its use on two applications, one in alarm analysis, and one in a chemical toxicology domain.     

基于频繁词集和k-Means的Web文本聚类混合算法

当前,Web文本聚类主要存在三个挑战：数据规模海量性、高雏空间处理复杂性和聚类结果的可理解性。针对上述挑战,本文提出了一个基于top-k频繁词集和k-means的混合聚类算法topHDC。该算法在生成初始聚簇时避免了高维空间向量处理,k个频繁词集对聚类结果提供了可理解的解释。topHDC避免了已有算法中聚类结果受文档长度干扰的问题。在两个公共数据集上的实验证明,topHDC算法在聚类质量和运行效率上明显优于另外两个具有代表性的聚类算法。     

挖掘数据流滑动时间窗口内Top-K频繁模式

由于数据流滑动时间窗口中流数据包含模式的支持度是动态变化的,很难给出一个合适的支持度门限来挖掘数据流滑动时间窗口内的频繁模式.在研究数据流滑动时间窗口内流数据变化特点的基础上,论文提出了一种挖掘数据流滑动时间窗口内Top-k频繁模式的方法,该方法能够在保证模式挖掘误差基础上快速删除窗口内不频繁模式信息,保留重要的模式信息,并能按照支持度降序输出Top-k频繁模式.仿真实验结果表明,该算法具有较好的效率和正确性,并优于其它同类算法.     

Efficient mining of weighted interesting patterns with a strong weight and/or support affinity

Most algorithms for frequent pattern mining use a support constraint to prune the combinatorial search space but support-based pruning is not enough. After mining datasets to obtain frequent patterns, the resulting patterns can have weak affinity. Although the minimum support can be increased, it is not effective for finding correlated patterns with increased weight and/or support affinity. Interesting measures have been proposed to detect correlated patterns but any approach does not consider both support and weight. In this paper, we present a new strategy, Weighted interesting pattern mining (WIP) in which a new measure, weight-confidence, is suggested to mine correlated patterns with the weight affinity. A weight range is used to decide weight boundaries and an h-confidence serves to identify support affinity patterns. In WIP, without additional computation cost, original h-confidence is used instead of the upper bound of h-confidence for performance improvement. WIP not only gives a balance between the two measures of weight and support, but also considers weight affinity and/or support affinity between items within patterns so more correlated patterns can be detected. To our knowledge, ours is the first work specifically to consider weight affinity between items of patterns. A comprehensive performance study shows that WIP is efficient and scalable for finding affinity patterns. Moreover, it generates fewer but more valuable patterns with the correlation. To decrease the number of thresholds, w-confidence, h-confidence and weighted support can be used selectively according to requirement of applications.     

Efficient representative pattern mining based on weight and maximality conditions

As a core area in data mining, frequent pattern (or itemset) mining has been studied for a long time. Weighted frequent pattern mining prunes unimportant patterns and maximal frequent pattern mining discovers compact frequent patterns. These approaches contribute to improving mining performance by reducing the search space. However, we need to consider both the downward closure property and patterns' subset checking process when integrating these different methods in order to prevent unintended pattern losses. Moreover, it is also essential to extract valid patterns with faster runtime and less memory consumption. For this reason, in this paper, we propose more efficient maximal weighted frequent pattern (MWFP) mining approaches based on tree and array structures. We describe how to handle these problems more efficiently, maintaining the correctness of our method. We develop two types of maximal weighted frequent mining algorithms based on weight ascending order and support descending order and compare these two algorithms to conclude which is more suitable for MWFP mining. In addition, comprehensive tests in this paper show that our algorithms are more efficient and scalable than state‐of‐the‐art algorithms, and they also have the correctness of the MWFP mining in terms of their pattern generation results.     

去冗余Top-k对比序列模式挖掘

对比序列模式可以用来表征不同类别数据集之间的差异。在生物信息、物流管理、电子商务等领域,对比序列模式有着广泛的应用。Top-k对比序列模式挖掘的目标是发现数据集中对比度最高的前k个序列模式。在Top-k对比序列模式挖掘中,可能挖掘出冗余的序列模式。目前,虽然有Top-k对比序列模式发现算法被提出,但这些算法并未考虑冗余序列模式的问题。为此,本文提出了基于广度优先生成树的去冗余Top-k对比序列模式挖掘算法BFM（breadth-first miner）。使用BFM算法可以有效地解决冗余问题,得到去冗余的Top-k对比序列模式。在BFM算法的基础上,提出了性能更好的算法PBFM（pruning breadth-first miner）。通过在真实数据集上的实验分析与对比 ,验证了本文算法的有效性。