Finding hot query patterns over an XQuery stream

Caching query results is one efficient approach to improving the performance of XML management systems. This entails the discovery of frequent XML queries issued by users. In this paper, we model user queries as a stream of XML query pattern trees and mine the frequent query patterns over the query stream. To facilitate the one-pass mining process, we devise a novel data structure called DTS to summarize the pattern trees seen so far. By grouping the incoming pattern trees into batches, we can dynamically mark the active portion of the current batch in DTS and limit the enumeration of candidate trees to only the currently active pattern trees. We also design another summary data structure called ECTree that provides for the incremental computation of the frequent tree patterns over the query stream. Based on the above two constructs, we present two mining algorithms called XQSMinerI and XQSMinerII. XQSMinerI is fast, but it tends to overestimate, while XQSMinerII adopts a filter-and-refine approach to minimize the amount of overestimation. Experimental results show that the proposed methods are both efficient and scalable and require only small memory footprints.Received: 17 October 2003, Accepted: 16 April 2004, Published online: 14 September 2004Edited by: J. Gehrke and J. Hellerstein.     

基于递推式右路径扩展的XML频繁模式树挖掘

在分析现有的频繁模式树挖掘的经典算法FREQT和FreqtTree基础上,提出一种新的基于递推式右路径扩展的XML频繁模式树挖掘算法。该算法采用最右路径扩展的思想,利用递推式的候选节点集更新技术来压缩候选节点集,产生数量较少的候选模式,并且在计算候选模式树的支持数时,采用增量式技术,提高算法效率。从理论上证明该算法的正确性,并对通过具体实验验证算法的高效性。     

Bottom-up discovery of frequent rooted unordered subtrees

In the past decade, XML has emerged as the standard language for information exchanging over the Internet. Due to its tree-structure paradigm, XML is superior for its capability of storing, querying, and manipulating complex data. Therefore, discovering frequent tree patterns over tree-structured data has become an interesting topic for XML data management. In this paper, we propose a tree mining algorithm, named BUXMiner, for finding a special class of frequent trees, called rooted unordered trees, from a tree-structured database. BUXMiner employs an efficient bottom-up approach to enumerate all candidate trees over a compact global tree guide and computes the frequent trees based on the tree guide. In addition to BUXMiner, we also propose a mining approach called BUMXMiner to discover the maximal frequent rooted unordered trees. We compare BUXMiner with previous tree-structure mining algorithms, namely XQPMinerTID and FastXMiner, which were also proposed to discover rooted unordered trees. The experimental results show that our algorithm outperforms XQPMinerTID and FastXMiner in terms of efficiency. The performance results from real-world applications also indicate the usefulness of our proposed tree mining algorithms in a variety of web applications, such as analysis of web page access patterns and mining frequent XML query patterns for caching.     

Looking into the seeds of time: Discovering temporal patterns in large transaction sets

This paper studies the problem of mining frequent itemsets along with their temporal patterns from large transaction sets. A model is proposed in which users define a large set of temporal patterns that are interesting or meaningful to them. A temporal pattern defines the set of time points where the user expects a discovered itemset to be frequent. The model is general in that (i) no constraints are placed on the interesting patterns given by the users, and (ii) two measures—inclusiveness and exclusiveness—are used to capture how well the temporal patterns match the time points given by the discovered itemsets. Intuitively, these measures indicate to what extent a discovered itemset is frequent at time points included in a temporal pattern p, but not at time points not in p. Using these two measures, one is able to model many temporal data mining problems appeared in the literature, as well as those that have not been studied. By exploiting the relationship within and between itemset space and pattern space simultaneously, a series of pruning techniques are developed to speed up the mining process. Experiments show that these pruning techniques allow one to obtain performance benefits up to 100 times over a direct extension of non-temporal data mining algorithms.     

结合用户兴趣的微博信息传播模式挖掘*

由于信息传播模型是社区挖掘、社区影响力研究的基础,文中提出结合用户兴趣的信息传播模型,设计基于频繁子树的信息传播微观模式挖掘方法.首先,基于微博社交网络图表示及用户多标签建模,将微观信息传播模式转换为频繁子树挖掘问题.然后,针对微博社交网络图单节点多标签特性,设计多标签节点树的频繁子树挖掘算法(MLTreeMiner).最后,结合主题提取方法,使用MLTreeMiner挖掘信息传播模式.在人工数据集上的实验表明,MLtreeMiner能高效地对多标签节点树进行频繁子树挖掘.针对新浪微博真实数据的实验也验证方法的有效性.     

Mining top?k frequent patterns without minimum support threshold

Finding frequent patterns play an important role in mining association rules, sequences, episodes, Web log mining and many other interesting relationships among data. Frequent pattern mining methods often produce a huge number of frequent itemsets that is not feasible for effective usage. The number of highly correlated patterns is usually very small and may even be one. Most of the existing frequent pattern mining techniques often require the setting of many input parameters and may involve multiple passes over the database. Minimum support is the widely used parameter in frequent pattern mining to discover statistically significant patterns. Specifying appropriate minimum support is a challenging task for a data analyst as the choice of minimum support value is somewhat arbitrary. Generally, it is required to repeatedly execute an algorithm, heuristically tuning the value of minimum support over a wide range, until the desired result is obtained, certainly, a very time-consuming process. Setting up an inappropriate minimum support may also cause an algorithm to fail in finding the true patterns. We present a novel method to efficiently retrieve top few maximal frequent patterns in order of significance without use of the minimum support parameter. Instead, we are only required to specify a more human understandable parameter, namely the desired number itemsets k. Our technique requires only a single pass over the database and generation of length two itemsets. The association ratio graph is proposed as a compact structure containing concise information, which is created in time quadratic to the size of the database. Algorithms are described for using this graph structure to discover top-most and top-k maximal frequent itemsets without minimum support threshold. To effectively achieve this, the method employs construction of an all path source-to-destination tree to discover all maximal cycles in the graph. The results can be ranked in decreasing order of significance. Results are presented demonstrating the performance advantages to be gained from the use of this approach.     

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

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

Mining rooted ordered trees under subtree homeomorphism

Mining frequent tree patterns has many applications in different areas such as XML data, bioinformatics and World Wide Web. The crucial step in frequent pattern mining is frequency counting, which involves a matching operator to find occurrences (instances) of a tree pattern in a given collection of trees. A widely used matching operator for tree-structured data is subtree homeomorphism, where an edge in the tree pattern is mapped onto an ancestor-descendant relationship in the given tree. Tree patterns that are frequent under subtree homeomorphism are usually called embedded patterns. In this paper, we present an efficient algorithm for subtree homeomorphism with application to frequent pattern mining. We propose a compact data-structure, called occ, which stores only information about the rightmost paths of occurrences and hence can encode and represent several occurrences of a tree pattern. We then define efficient join operations on the occ data-structure, which help us count occurrences of tree patterns according to occurrences of their proper subtrees. Based on the proposed subtree homeomorphism method, we develop an effective pattern mining algorithm, called TPMiner. We evaluate the efficiency of TPMiner on several real-world and synthetic datasets. Our extensive experiments confirm that TPMiner always outperforms well-known existing algorithms, and in several cases the improvement with respect to existing algorithms is significant.     

一种基于F-矩阵的最大频繁项目集快速挖掘算法

最大频繁项目集挖掘是多种数据挖掘应用研究的一个重要方面,最大频繁项目集的快速挖掘算法研究是当前研究的热点。传统的最大频繁项目集挖掘算法要多遍扫描数据库并产生大量的候选项目集。为此,该文提出了基于F-矩阵的最大频繁项目集快速挖掘算法FMMFIBFM,FMMFIBFM采用FP-tree的存储结构,仅须扫描数据库两遍且不产生候选频繁项目集,有效地提高了频繁项目集的挖掘效率。实验结果表明,FMMFIBFM算法是有效可行的。     

数据挖掘技术在互联网时代的应用

广泛地从Web获取信息是信息时代的一个重要特征,借助数据挖掘的知识,从Web日志中发现用户的访问模式,可以帮助管理站点,更好地满足用户的要求,本文介绍了从原始的日志数据中发现用户访问模式的方法,提出了数据预处理的方法和一种新的用于挖掘的数据结构－序列访问树SAT,以及基于此结构的挖掘算法。     

一种挖掘频繁闭项集的深度优先算法

频繁闭项集挖掘是许多数据挖掘应用中的重要问题。为减少候选项集数量和降低支持度计算的开销,提出一种新的深度优先搜索频繁闭项集(DFFCI)的算法。将改进的压缩频繁模式树(CFP-Tree)表示的数据集信息投影到划分矩阵,使用二进制向量逻辑运算计算支持度,简化了计算过程,减少了时间开销;采用基于支持度预计算技术的全局2-项剪枝和局部扩展剪枝,有效削减了搜索空间。实验结果表明该算法的性能优于其他主流深度优先算法。     

Optimal constraint-based decision tree induction from itemset lattices

In this article we show that there is a strong connection between decision tree learning and local pattern mining. This connection allows us to solve the computationally hard problem of finding optimal decision trees in a wide range of applications by post-processing a set of patterns: we use local patterns to construct a global model. We exploit the connection between constraints in pattern mining and constraints in decision tree induction to develop a framework for categorizing decision tree mining constraints. This framework allows us to determine which model constraints can be pushed deeply into the pattern mining process, and allows us to improve the state-of-the-art of optimal decision tree induction.     

基于有序FP-tree的最大长度频繁项集挖掘算法

频繁项集的挖掘受到大量候选频繁项集和较高计算花费的限制,只挖掘最大长度频繁项集已满足很多应用。提出一种基于有序FP-tree结构挖掘最大长度频繁项集的算法。即对有序FP-tree的头表进行改造,增加一个max-level域,记录该项在有序FP-tree中的最大高度。挖掘时仅对max-level 大于等于已有最大长度频繁项集长度的项进行遍历,不产生条件模式基,无需递归构造条件FP-tree,且计算出最大长度频繁项集的支持度。实验结果表明该算法挖掘效率高、速度快。     

快速挖掘全局频繁项目集

分布式环境中，全局频繁项目集的挖掘是数据挖掘中最重要的研究课题之一．传统的全局频繁项目集挖掘算法采用Apriori算法框架，须多遍扫描数据库并产生大量的候选项目集，且通过传送局部频繁项目集求全局频繁项目集的网络通信代价高．为此，提出了一种分布数据库的全局频繁项目集快速挖掘算法——FMAGF.FMAGF算法采用传送条件频繁模式树或条件模式基来挖掘全局频繁项目集，可有效地减小网络通信量，提高全局频繁项目集挖掘效率．理论分析和实验结果表明提出的算法是有效可行的．     

基于Web日志文件的关联规则挖掘模块的实现

在对Web应用挖掘的基本步骤作系统性研究的基础上,设计了一个基于Web日志文件的关联规则挖掘模块。该系统应能够对用户访问Web时服务器方留下的访问记录进行挖掘,从中得出用户的访问模式和访问兴趣。为了识别用户浏览模式,实现了利用关联规则挖掘算法Apriori对Web应用挖掘过程中预处理阶段所产生的用户会话文件进行挖掘的模块,该模块针对用户选定的若干页面产生满足最小支持度和最小置信度的页面之间的强关联规则,并以文本的形式显示挖掘的结果。     

一种基于频繁模式树的约束最大频繁项目集挖掘及其更新算法

目前已提出了许多快速的关联规则挖掘算法,实际上用户只关心部分关联规则,如他们仅想 知道包含指定项目的规则.当这些约束被用于数据预处理或将它结合到数据挖掘算法中去时 ,可以显著减少算法的执行时间.为此,考虑了一类包含或不包含某些项目的布尔表达式约 束条件,提出了一种快速的基于FP-tree的约束最大频繁项目集挖掘算法CMFIMA,并对其更 新问题进行了研究,提出了一种增量式更新约束最大频繁项目集挖掘算法CMFIUA.     

A constraint-based querying system for exploratory pattern discovery

In this article we present ConQueSt, a constraint-based querying system able to support the intrinsically exploratory (i.e., human-guided, interactive and iterative) nature of pattern discovery. Following the inductive database vision, our framework provides users with an expressive constraint-based query language, which allows the discovery process to be effectively driven toward potentially interesting patterns. Such constraints are also exploited to reduce the cost of pattern mining computation. ConQueSt is a comprehensive mining system that can access real-world relational databases from which to extract data. Through the interaction with a friendly graphical user interface (GUI), the user can define complex mining queries by means of few clicks. After a pre-processing step, mining queries are answered by an efficient and robust pattern mining engine which entails the state-of-the-art of data and search space reduction techniques. Resulting patterns are then presented to the user in a pattern browsing window, and possibly stored back in the underlying database as relations.     

频繁模式挖掘的约束算法

在频繁模式挖掘过程中能够动态改变约束的算法比较少.提出了一种基于约束的频繁模式挖掘算法MCFP.MCFP首先按照约束的性质来建立频繁模式树,并且只需扫描一遍数据库,然后建立每个项的条件树,挖掘以该项为前缀的最大频繁模式,并用最大模式树来存储,最后根据最大模式来找出所有支持度明确的频繁模式.MCFP算法允许用户在挖掘频繁模式过程中动态地改变约束.实验表明,该算法与iCFP算法相比是很有效的.     

A weighted common structure based clustering technique for XML documents

XML has recently become very popular as a means of representing semistructured data and as a standard for data exchange over the Web, because of its varied applicability in numerous applications. Therefore, XML documents constitute an important data mining domain. In this paper, we propose a new method of XML document clustering by a global criterion function, considering the weight of common structures. Our approach initially extracts representative structures of frequent patterns from schemaless XML documents using a sequential pattern mining algorithm. Then, we perform clustering of an XML document by the weight of common structures, without a measure of pairwise similarity, assuming that an XML document is a transaction and frequent structures extracted from documents are items of the transaction. We conducted experiments to compare our method with previous methods. The experimental results show the effectiveness of our approach.     

An integrated,generic approach to pattern mining: data mining template library

Frequent pattern mining (FPM) is an important data mining paradigm to extract informative patterns like itemsets, sequences, trees, and graphs. However, no practical framework for integrating the FPM tasks has been attempted. In this paper, we describe the design and implementation of the Data Mining Template Library (DMTL) for FPM. DMTL utilizes a generic data mining approach, where all aspects of mining are controlled via a set of properties. It uses a novel pattern property hierarchy to define and mine different pattern types. This property hierarchy can be thought of as a systematic characterization of the pattern space, i.e., a meta-pattern specification that allows the analyst to specify new pattern types, by extending this hierarchy. Furthermore, in DMTL all aspects of mining are controlled by a set of different mining properties. For example, the kind of mining approach to use, the kind of data types and formats to mine over, the kind of back-end storage manager to use, are all specified as a list of properties. This provides tremendous flexibility to customize the toolkit for various applications. Flexibility of the toolkit is exemplified by the ease with which support for a new pattern can be added. Experiments on synthetic and public dataset are conducted to demonstrate the scalability provided by the persistent back-end in the library. DMTL been publicly released as open-source software (), and has been downloaded by numerous researchers from all over the world.