A framework for incremental generation of closed itemsets

Association rule mining from a transaction database (TDB) requires the detection of frequently occurring patterns, called frequent itemsets (FIs), whereby the number of FIs may be potentially huge. Recent approaches for FI mining use the closed itemset paradigm to limit the mining effort to a subset of the entire FI family, the frequent closed itemsets (FCIs). We show here how FCIs can be mined incrementally yet efficiently whenever a new transaction is added to a database whose mining results are available. Our approach for mining FIs in dynamic databases relies on recent results about lattice incremental restructuring and lattice construction. The fundamentals of the incremental FCI mining task are discussed and its reduction to the problem of lattice update, via the CI family, is made explicit. The related structural results underlie two algorithms for updating the set of FCIs of a given TDB upon the insertion of a new transaction. A straightforward method searches for necessary completions throughout the entire CI family, whereas a second method exploits lattice properties to limit the search to CIs which share at least one item with the new transaction. Efficient implementations of the parsimonious method is discussed in the paper together with a set of results from a preliminary study of the method's practical performances.     

An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation

Given a finite set V, and a hypergraph H⊆2^V, the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996) 618-628] gave an incremental quasi-polynomial-time algorithm for solving the hypergraph transversal problem. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same theoretical worst-case bound, practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the original algorithm can be used to obtain a stronger bound on the running time.More generally, we consider a monotone property π over a bounded n-dimensional integral box. As an important application of the above hypergraph transversal problem, pioneered by Bioch and Ibaraki [Complexity of identification and dualization of positive Boolean functions, Inform. and Comput. 123 (1995) 50-63], we consider the problem of incrementally generating simultaneously all minimal subsets satisfying π and all maximal subsets not satisfying π, for properties given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time via a polynomial-time reduction to a generalization of the hypergraph transversal problem on integer boxes. In this paper we present an efficient implementation of this procedure, and present experimental results to evaluate our implementation for a number of interesting monotone properties π.     

基于最大频繁序列模式挖掘的App-DDoS攻击的异常检测

为了动态、准确、高效地描述用户的访问行为,实现对不同应用层分布式拒绝服务(Application-layer Distributed Denial of Service, App-DDoS)攻击行为的透明检测,该文提出基于最大频繁序列模式挖掘的ADA_MFSP(App-DDoS Detection Algorithm based on Maximal Frequent Sequential Pattern mining)检测模型。该模型在对正常Web访问序列数据库(Web Access Sequence Database, WASD)及待检测WASD进行最大频繁序列模式挖掘的基础上,引入序列比对平均异常度,联合浏览时间平均异常度、请求循环平均异常度等有效检测属性,最终实现攻击行为的异常检测。实验证明：ADA_MFSP模型不仅能有效检测各类App-DDoS攻击,且有良好的检测灵敏度。     

一种无冗余的Web日志挖掘算法

Web日志挖掘是Web数据挖掘的一个重要研究领域。Web日志挖掘通过发现Web日志中用户的访问规律和模式,可以提取出其中潜在的规律和信息,人们对这个领域的研究也日益重视。然而,传统的基于关联规则的Web日志挖掘算法都是基于所有关联规则的。这种方式往往挖掘产生大量的候选规则,而且存在大量冗余的规则。提出了一种新的无冗余的Web日志挖掘算法,该算法通过引入频繁闭项集合最小关联规则的概念,从而解决了以往基于所有关联规则挖掘算法中出现的上述问题。     

Web挖掘中基于RD_Apriori算法发现用户频繁访问模式

从Web日志数据中发现用户的频繁访问模式，可分为两步进行。首先把经过预处理后的目志数据转换为最大前向引用的集合，然后使用Apriori算法挖掘出频繁访问模式。本文针对挖掘的第二步提出了一种基于缩减数据库(Reduced Database)的RD—Apriori算法，此算法能够准确、高效地挖掘各种长度不同的频繁访问模式。     

Exploring Semantic Association Rules Between Keyword and Visual Feature Clusters for Web Image Retrieval

The semantic gap is a big challenge in image retrieval area. Previous studies in web image retrieval have mainly focused on Relevance feedback （RF） and Latent semantic indexing （LSI） to alleviate the gap. This paper proposes an approach base on Frequent itemset mining （FIM） and Association rule （AR） techniques, which explores the semantic association rule between the two modalities that are represented by keyword and visual feature clusters. The rules are obtained oftline based on the inverted file, and utilized in query process online to realize the integration of the two modalities of web im- ages. Our approach improves the retrieval performance and is scalable well, as well as satisfies the requirement of the web users with no additional interactions. The exper- iments are carried out in our web image retrieval system named VAST （VisuAl ＆ SemanTic image search）, and the results show the effectiveness of the proposed approach.     

一种基于频繁模式的时间序列分类框架

如何提取和选择时间序列的特征是时间序列分类领域两个重要的问题。该文提出MNOE(Mining Non- Overlap Episode)算法计算时间序列中的非重叠频繁模式,并将其作为时间序列特征。基于这些非重叠频繁模式,该文提出EGMAMC(Episode Generated Mixed memory Aggregation Markov Chain)模型描述时间序列。根据似然比检验原理,从理论上推导出频繁模式在时间序列中出现的次数和EGMAMC模型是否能显著描述时间序列之间的关系;根据信息增益定义,选择能显著描述时间序列的频繁模式作为时间序列特征输入分类模型。在UCI (University of California Irvine)公共数据集和实际智能楼宇数据集上的实验表明,选择频繁模式作为特征进行分类的准确率、召回率和F-Measure均优于不选择频繁模式作为特征的分类结果。高效的计算和有效的选择非重叠频繁模式作为时间序列特征有助于提高时间序列分类模型的各项评价指标。     

单维关联规则快速Apriori算法研究

文章通过Apriori和Apriori Tid算法结合生成局部频繁项集，改进了Apriori算法运行速度过慢的问题．再通过程序优化进一步提高了算法运行速度．得到了快速Apriori算法。     

基于频繁集的多层次交互式关联规则挖掘

文章研究了一种知识发现与数据挖掘中关联规则的发现方法,针对现有大型超市销售事务数据库,提出了一种新的多层次信息获得取方法。运用关联规则挖掘所产生的频繁集对数据压缩表示,并给出了按用户的实际需求交互式挖掘感兴趣关联规则的算法。该算法在挖掘速度和效率上有较大提高。     

关联规则增量式快速更新方法的研究

随着最小支持度的不同，就会产生不同的频繁项目集，而频繁项目集的发现又是一个高花费的过程。如何实现不同最小支持度下频繁项目集的更新就显得尤为重要。提出了一种新的增量更新策略，用来解决这一关联规则的高效维护问题。