Mining frequent closed rooted trees

Many knowledge representation mechanisms are based on tree-like structures, thus symbolizing the fact that certain pieces of information are related in one sense or another. There exists a well-studied process of closure-based data mining in the itemset framework: we consider the extension of this process into trees. We focus mostly on the case where labels on the nodes are nonexistent or unreliable, and discuss algorithms for closure-based mining that only rely on the root of the tree and the link structure. We provide a notion of intersection that leads to a deeper understanding of the notion of support-based closure, in terms of an actual closure operator. We describe combinatorial characterizations and some properties of ordered trees, discuss their applicability to unordered trees, and rely on them to design efficient algorithms for mining frequent closed subtrees both in the ordered and the unordered settings. Empirical validations and comparisons with alternative algorithms are provided.     

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.     

Mining frequent closed patterns in pointset databases

In this paper, we proposed an efficient algorithm, called PCP-Miner (Pointset Closed Pattern Miner), for mining frequent closed patterns from a pointset database, where a pointset contains a set of points. Our proposed algorithm consists of two phases. First, we find all frequent patterns of length two in the database. Second, for each pattern found in the first phase, we recursively generate frequent closed patterns by a frequent pattern tree in a depth-first search manner. Since the PCP-Miner does not generate unnecessary candidates, it is more efficient and scalable than the modified Apriori, SASMiner and MaxGeo. The experimental results show that the PCP-Miner algorithm outperforms the comparing algorithms by more than one order of magnitude.     

基于不确定数据的可能频繁闭序列模式挖掘

; 对于不确定数据的频繁序列模式挖掘,会导致可能频繁模式数量的指数级出现,其中有些无用的挖掘结果,引起频繁序列的冗余。针对上述不足, 提出了可能频繁闭序列模式(pfcsp)的定义, 以及一种基于不确定数据的可能频繁闭序列挖掘算法U-FCSM。此算法中,基于一种元组不确定数据模型,计算序列的可能频繁性,应用BIDE算法的闭序列思想判断可能频繁序列是否是可能频繁闭序列模式。为了减少搜索空间与避免冗余的计算,应用了几个剪枝与边界技术。U-FCSM算法的有效性与效率通过大量的实验得以表明。     

Incremental mining of weighted maximal frequent itemsets from dynamic databases

Frequent itemset mining allows us to find hidden, important information from large databases. Moreover, processing incremental databases in the itemset mining area has become more essential because a huge amount of data has been accumulated continually in a variety of application fields and users want to obtain mining results from such incremental data in more efficient ways. One of the major problems in incremental itemset mining is that the corresponding mining results can be very large-scale according to threshold settings and data volumes. In addition, it is considerably hard to analyze all of them and find meaningful information. Furthermore, not all of the mining results become actually important information. In this paper, to solve these problems, we propose an algorithm for mining weighted maximal frequent itemsets from incremental databases. By scanning a given incremental database only once, the proposed algorithm can not only conduct its mining operations suitable for the incremental environment but also extract a smaller number of important itemsets compared to previous approaches. The proposed method also has an effect on expert and intelligent systems since it can automatically provide more meaningful pattern results reflecting characteristics of given incremental databases and threshold settings, which can help users analyze the given data more easily. Our comprehensive experimental results show that the proposed algorithm is more efficient and scalable than previous state-of-the-art algorithms.     

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.     

挖掘数据库中的负频繁模式

传统的关联规则挖掘研究事务中所包含的项与项之间的关联性,而负关联规则挖掘不仅要考虑事务中包含的项,还要考虑事务中不包含的项。给出了完全负关联规则的定义,提出一种基于树的算法Free-PNP,通过此算法挖掘数据库中的负频繁模式,继而得到所要挖掘的完全负关联规则。通过实验验证了算法的有效性。     

Mining frequent trajectory patterns in spatial-temporal databases

In this paper, we propose an efficient graph-based mining (GBM) algorithm for mining the frequent trajectory patterns in a spatial-temporal database. The proposed method comprises two phases. First, we scan the database once to generate a mapping graph and trajectory information lists (TI-lists). Then, we traverse the mapping graph in a depth-first search manner to mine all frequent trajectory patterns in the database. By using the mapping graph and TI-lists, the GBM algorithm can localize support counting and pattern extension in a small number of TI-lists. Moreover, it utilizes the adjacency property to reduce the search space. Therefore, our proposed method can efficiently mine the frequent trajectory patterns in the database. The experimental results show that it outperforms the Apriori-based and PrefixSpan-based methods by more than one order of magnitude.     

最大模糊频繁模式挖掘算法

针对有效模式挖掘的组合爆炸及挖掘结果信息如何有效表达的问题,提出了一种基于“核心-牵引”结构的修剪候选模式和考虑项目不确定性的最大模糊模式挖掘算法（MFFP-Tree）。首先,综合分析项目的模糊性,提出模糊支持度,分析项目在事务数据集中的模糊权重,依据模糊修剪策略修剪候选项集;其次,仅扫描数据集一次,就能成功构建模糊模式挖掘树,依据模糊剪枝策略减少模式提取的开销,采用FFP-array阵列结构使得搜索方式更精简,从而进一步降低时空开销。根据基准数据集的实验结果,与最大模式挖掘算法PADS和FPMax^*对比分析,MFFP-Tree挖掘出的最大模糊模式能够更准确地反映项目与项目之间的关系;算法的时间复杂度能减半甚至低1个数量级;算法的空间复杂度降低1~2个数量级。     

Efficient mining of maximal frequent itemsets from databases on a cluster of workstations

In this paper, we propose two parallel algorithms for mining maximal frequent itemsets from databases. A frequent itemset is maximal if none of its supersets is frequent. One parallel algorithm is named distributed max-miner (DMM), and it requires very low communication and synchronization overhead in distributed computing systems. DMM has the local mining phase and the global mining phase. During the local mining phase, each node mines the local database to discover the local maximal frequent itemsets, then they form a set of maximal candidate itemsets for the top-down search in the subsequent global mining phase. A new prefix tree data structure is developed to facilitate the storage and counting of the global candidate itemsets of different sizes. This global mining phase using the prefix tree can work with any local mining algorithm. Another parallel algorithm, named parallel max-miner (PMM), is a parallel version of the sequential max-miner algorithm (Proc of ACM SIGMOD Int Conf on Management of Data, 1998, pp 85–93). Most of existing mining algorithms discover the frequent k-itemsets on the kth pass over the databases, and then generate the candidate (k + 1)-itemsets for the next pass. Compared to those level-wise algorithms, PMM looks ahead at each pass and prunes more candidate itemsets by checking the frequencies of their supersets. Both DMM and PMM were implemented on a cluster of workstations, and their performance was evaluated for various cases. They demonstrate very good performance and scalability even when there are large maximal frequent itemsets (i.e., long patterns) in databases.

基于频繁项集挖掘最大频繁项集和频繁闭项集

提出了基于频繁项集的最大频繁项集（BFI-DMFI）和频繁闭项集挖掘算法（BFI-DCFI）。BFI-DMFI算法通过逐个检测频繁项集在其集合中是否存在超集确定该项集是不是最大频繁项集;BFI-DCFI算法则是通过挖掘所有支持度相等的频繁项集中的最大频繁项集组合生成频繁闭项集。该类算法的提出,为关联规则的精简提供了一种新的解决方法。     

Mining closed patterns in multi-sequence time-series databases

In this paper, we propose an efficient algorithm, called CMP-Miner, to mine closed patterns in a time-series database where each record in the database, also called a transaction, contains multiple time-series sequences. Our proposed algorithm consists of three phases. First, we transform each time-series sequence in a transaction into a symbolic sequence. Second, we scan the transformed database to find frequent patterns of length one. Third, for each frequent pattern found in the second phase, we recursively enumerate frequent patterns by a frequent pattern tree in a depth-first search manner. During the process of enumeration, we apply several efficient pruning strategies to remove frequent but non-closed patterns. Thus, the CMP-Miner algorithm can efficiently mine the closed patterns from a time-series database. The experimental results show that our proposed algorithm outperforms the modified Apriori and BIDE algorithms.     

在单向FP-tree上挖掘频繁闭项集

频繁闭项集提供了频繁项集的一种完整的、最小表示。针对稠密数据集,提出一种基于单向FP-tree的频繁闭项集挖掘算法Unid_FP-FCI。该算法在挖掘过程中只生成被约束子树,而它是一种虚拟的树结构,在原有的单向FP-tree基础上用三个很小的数组来表示,因而避免了以往算法需递归构造条件FP-tree来计算频繁闭项集的弊端,极大地降低了内存空间和时间开销,提高了挖掘效率。     

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

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

最小组合法挖掘最大频繁集*

提出了与apriori和FP-tree两类算法完全不同的高效挖掘最大频繁集的算法,即最小组合算法MCA.该算法不产生候选频繁集,能大大减少计算量的开销.在此算法的研究中提出了另一个子课题,即重复数列中最小组合算法研究.     

用有序FP-tree挖掘最大频繁项集

提出了完全前缀路径和有序FP-tree的概念,给出根据数据项所在的层建立有序FP-tree的方法,利用有序FP-tree表示数据.提出用有序FP-tree中的完全前缀路径进行最大频繁项集挖掘的算法——MFIM算法,该算法利用有序FP-tree中的完全前缀路径对挖掘算法进行优化.实验结果表明,该算法对于浓密数据集中挖掘长模式具有较好的性能.     

基于图论的最大频繁项集挖掘

利用有向项集图来存储事务数据库中有关频繁项集的信息,提出了有向项集图的三叉链表式存储结构和基于有向项集图的最大频繁项集挖掘算法.它不仅实现了事务数据库的一次扫描,减少了I/O代价,而且可以同时解决好稀疏数据库和稠密数据库的最大频繁项集挖掘问题.     

Mining lossless closed frequent patterns with weight constraints

Frequent pattern mining is one of main concerns in data mining tasks. In frequent pattern mining, closed frequent pattern mining and weighted frequent pattern mining are two main approaches to reduce the search space. Although many related studies have been suggested, no mining algorithm considers both paradigms. Even if closed frequent pattern mining represents exactly the same knowledge and weighted frequent pattern mining provides a way to discover more important patterns, the incorporation of closed frequent pattern mining and weight frequent pattern mining may loss information. Based on our analysis of joining orders, we propose closed weighted frequent pattern mining, and present how to discover succinct but lossless closed frequent pattern with weight constraints. To our knowledge, ours is the first work specifically to consider both constraints. An extensive performance study shows that our algorithm outperforms previous algorithms. In addition, it is efficient and scalable.     

Mining frequent patterns in image databases with 9D-SPA representation

In this paper, we propose a novel algorithm, called 9DSPA-Miner, to mine frequent patterns from an image database, where every image is represented by the 9D-SPA representation. Our proposed method consists of three phases. First, we scan the database once and create an index structure. Next, the index structure is scanned to find all frequent patterns of length two. Finally, we use the frequent k-patterns (k ? 2) to generate candidate (k + 1)-patterns and check if the support of each candidate generated is not less than the user-specified minimum support threshold by using the index structure. Then, the steps in the third phase are repeated until no more frequent patterns can be found. Since the 9DSPA-Miner algorithm uses the characteristics of the 9D-SPA representation to prune most of impossible candidates, the experiment results demonstrate that it is more efficient and scalable than the modified Apriori method.