Mining sequential patterns across multiple sequence databases

In this paper, given a set of sequence databases across multiple domains, we aim at mining multi-domain sequential patterns, where a multi-domain sequential pattern is a sequence of events whose occurrence time is within a pre-defined time window. We first propose algorithm Naive in which multiple sequence databases are joined as one sequence database for utilizing traditional sequential pattern mining algorithms (e.g., PrefixSpan). Due to the nature of join operations, algorithm Naive is costly and is developed for comparison purposes. Thus, we propose two algorithms without any join operations for mining multi-domain sequential patterns. Explicitly, algorithm IndividualMine derives sequential patterns in each domain and then iteratively combines sequential patterns among sequence databases of multiple domains to derive candidate multi-domain sequential patterns. However, not all sequential patterns mined in the sequence database of each domain are able to form multi-domain sequential patterns. To avoid the mining cost incurred in algorithm IndividualMine, algorithm PropagatedMine is developed. Algorithm PropagatedMine first performs one sequential pattern mining from one sequence database. In light of sequential patterns mined, algorithm PropagatedMine propagates sequential patterns mined to other sequence databases. Furthermore, sequential patterns mined are represented as a lattice structure for further reducing the number of sequential patterns to be propagated. In addition, we develop some mechanisms to allow some empty sets in multi-domain sequential patterns. Performance of the proposed algorithms is comparatively analyzed and sensitivity analysis is conducted. Experimental results show that by exploring propagation and lattice structures, algorithm PropagatedMine outperforms algorithm IndividualMine in terms of efficiency (i.e., the execution time).     

Analyzing Sequential Patterns in Retail Databases

Finding correlated sequential patterns in large sequence databases is one of the essential tasks in data mining since a huge number of sequential patterns are usually mined, but it is hard to find sequential patterns with the correlation. According to the requirement of real applications, the needed data analysis should be different. In previous mining approaches, after mining the sequential patterns, sequential patterns with the weak affinity are found even with a high minimum support. In this paper, a new framework is suggested for mining weighted support affinity patterns in which an objective measure, sequential ws-confidence is developed to detect correlated sequential patterns with weighted support affinity patterns. To efficiently prune the weak affinity patterns, it is proved that ws-confidence measure satisfies the anti-monotone and cross weighted support properties which can be applied to eliminate sequential patterns with dissimilar weighted support levels. Based on the framework, a weighted support affinity pattern mining algorithm （WSMiner） is suggested. The performance study shows that WSMiner is efficient and scalable for mining weighted support affinity patterns.     

OSAF-tree--可迭代的移动序列模式挖掘及增量更新方法

移动通信技术和无限定位技术的发展积累了海量的、动态增长的时空数据．利用数据挖掘技术从移动用户的时空行为轨迹当中挖掘用户移动序列模式,在移动通信、交通管理、基于位置服务等领域有着广泛的应用前景．由于移动环境网络资源珍贵、数据量大的特点,传统的序列模式挖掘方法在效率上很难满足需求．OSAF-tree算法基于投影的概念,只需要对数据库进行一遍扫描,就可以很好地处理移动序列模式的挖掘及其增量更新和迭代挖掘问题,这是一个非常高效的算法．与已有的方法相比,OSAF-tree算法在性能和I/O代价等方面都具有明显的优势．     

基于SPAM-FPT的WebLog访问序列模式挖掘

WebLog访问序列模式挖掘将数据挖掘中的序列模式技术应用于Web服务器上的日志文件，以此来改善Web的信息服务，而在对海量的数据挖掘时，系统资源开销很大。该文结合SPAM、PrefixSpan的思想，提出一个新的算法——SPAM-FPT，该算法通过建立First_Positon_Table，避免了SPAM中的“与操作”、“连接操作”以及PrefixSpan中大量的“投影数据库”的建立，可以快捷地挖掘数据库中所有“频繁子序列”。     

多维概念格与多维序列模式的增量挖掘

多维序列模式挖掘旨在将一个或多个背景维度信息中发现的关联模式与有序事务序列中发现的序列模式有机结合,从而为用户提供信息内容更加丰富、更具有直接应用价值的多维序列模式.目前虽有一些挖掘多维序列模式的工作,但其关联模式与序列模式的发现过程是基于不同的数据结构分开进行的.提出一种新的概念格结构——多维概念格,它是对概念格的延伸与泛化,其内涵更加丰富,不仅具有多个有序的任务内涵,而且具有多个无序的背景内涵.设计实现了基于该结构的增量式多维序列模式挖掘算法,该算法使用统一的数据模型实现关联模式与序列模式的高效同步挖掘.在合成数据集上的实验结果验证了算法的有效性.同时,算法在实际的银行数据集上的应用效果也说明了算法的实用性.     

Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach

Mining frequent patterns in transaction databases, time-series databases, and many other kinds of databases has been studied popularly in data mining research. Most of the previous studies adopt an Apriori-like candidate set generation-and-test approach. However, candidate set generation is still costly, especially when there exist a large number of patterns and/or long patterns.In this study, we propose a novel frequent-pattern tree (FP-tree) structure, which is an extended prefix-tree structure for storing compressed, crucial information about frequent patterns, and develop an efficient FP-tree-based mining method, FP-growth, for mining the complete set of frequent patterns by pattern fragment growth. Efficiency of mining is achieved with three techniques: (1) a large database is compressed into a condensed, smaller data structure, FP-tree which avoids costly, repeated database scans, (2) our FP-tree-based mining adopts a pattern-fragment growth method to avoid the costly generation of a large number of candidate sets, and (3) a partitioning-based, divide-and-conquer method is used to decompose the mining task into a set of smaller tasks for mining confined patterns in conditional databases, which dramatically reduces the search space. Our performance study shows that the FP-growth method is efficient and scalable for mining both long and short frequent patterns, and is about an order of magnitude faster than the Apriori algorithm and also faster than some recently reported new frequent-pattern mining methods.     

带通配符和One-Off条件的序列模式挖掘

很多应用领域产生大量的序列数据。如何从这些序列数据中挖掘具有重要价值的模式,已成为序列模式挖掘研究的主要任务。研究这样一个问题：给定序列S、支持度阈值和间隔约束,从序列S中挖掘所有出现次数不小于给定支持度阈值的频繁序列模式,并且要求模式中任意两个相邻元素在序列中的出现位置满足用户定义的间隔约束。设计了一种有效的带有通配符的模式挖掘算法One-Off Mining,模式在序列中的出现满足One-Off条件,即模式的任意两次出现都不共享序列中同一位置的字符。在生物DNA序列上的实验结果表明,One-Off Mining比相关的序列模式挖掘算法具有更好的时间性能和完备性。     

TSP: Mining top-k closed sequential patterns

Sequential pattern mining has been studied extensively in the data mining community. Most previous studies require the specification of a min_support threshold for mining a complete set of sequential patterns satisfying the threshold. However, in practice, it is difficult for users to provide an appropriate min_support threshold. To overcome this difficulty, we propose an alternative mining task: mining top-k frequent closed sequential patterns of length no less than min_, where k is the desired number of closed sequential patterns to be mined and min_ is the minimal length of each pattern. We mine the set of closed patterns because it is a compact representation of the complete set of frequent patterns. An efficient algorithm, called TSP, is developed for mining such patterns without min_support. Starting at (absolute) min_support=1, the algorithm makes use of the length constraint and the properties of top-k closed sequential patterns to perform dynamic support raising and projected database pruning. Our extensive performance study shows that TSP has high performance. In most cases, it outperforms the efficient closed sequential pattern-mining algorithm, CloSpan, even when the latter is running with the best tuned min_support threshold. Thus, we conclude that, for sequential pattern mining, mining top-k frequent closed sequential patterns without min_support is more preferable than the traditional min_support-based mining.     

From sequential pattern mining to structured pattern mining: A pattern-growth approach

Sequential pattern mining is an important data mining problem with broad applications. However,it is also a challenging problem since the mining may have to generate or examine a combinatorially explosivenumber of intermediate subsequences. Recent studies have developed two major classes of sequential patternmining methods: (1) a candidate generation-and-test approach, represented by (i) GSP, a horizontal format-basedsequential pattern mining method, and (ii) SPADE, a vertical format-based method; and (2) a pattern-growthmethod, represented by PrefixSpan and its further extensions, such as gSpan for mining structured patterns. In this study, we perform a systematic introduction and presentation of the pattern-growth methodologyand study its principles and extensions. We first introduce two interesting pattern-growth algorithms, FreeSpanand PrefixSpan, for efficient sequential pattern mining. Then we introduce gSpan for mining structured patternsusing the same methodology. Their relative performance in l     

使用序列模式精简基挖掘序列模式

传统的序列模式挖掘方法在挖掘由短的频繁序列模式组成的数据库时有良好的性能．但在挖掘长的序列模式或支持度阈值很低时，这些方法可能遇到固有的困难，因为产生的频繁序列模式的数量经常太大．在许多情况下，用户可能只需要那些覆盖许多短模式的长模式．此外，在很多应用中，只要得到产生的频繁序列模式的近似支持度就已足够，而不需要它们的精确支持度．介绍了能将误差控制在确定范围内的频繁序列模式精简基的概念，并开发了一个挖掘这种序列模式精简基的算法．实验结果显示计算频繁序列模式精简基是很有前途的．     

Web日志序列模式挖掘

从Ｗｅｂ日志中挖掘出的序列模式可以用于改善Ｗｅｂ信息服务。本文分析了Ｗｅｂ日志序列列模式挖掘过程中的一些难点及相应的解决方案,并在此基础上设计了一个Ｗｅｂ日志序列模式挖掘工具ＳＰＭｉｎｅｒ。     

Enhancing quality of knowledge synthesized from multi-database mining

Multi-database mining using local pattern analysis could be considered as an approximate method of mining multiple large databases. Thus, it might be required to enhance the quality of knowledge synthesized from multiple databases. Also, many decision-making applications are directly based on the available local patterns in different databases. The quality of synthesized knowledge/decision based on local patterns in different databases could be enhanced by incorporating more local patterns in the knowledge synthesizing/processing activities. Thus, the available local patterns play a crucial role in building efficient multi-database mining applications. We represent patterns in condensed form by employing a coding called ACP coding. It allows us to consider more local patterns by lowering further the user inputs, like minimum support and minimum confidence. The proposed coding enables more local patterns participate in the knowledge synthesizing/processing activities and thus, the quality of synthesized knowledge based on local patterns in different databases gets enhanced significantly at a given pattern synthesizing algorithm and computing resource.     

一种基于序列末项位置信息的序列模式挖掘算法

针对PrefixSpan算法中反复扫描投影数据库寻找局部频繁项并重复构造挖掘大量重复投影数据库的不足,提出一种基于序列末项位置信息的序列模式挖掘算法SPM-LIPT。通过连接2-序列位置信息表(LIPT)找到序列模式的下一项,实现序列模式增长,避免对投影数据库反复扫描;同时通过检查相同末项序列首位置信息表(SLIFPT)进行前向剪枝;消除大量重复投影的构建。最后通过实验证明了算法的有效性。     

CLAP: Collaborative pattern mining for distributed information systems

The purpose of data mining from distributed information systems is usually threefold: (1) identifying locally significant patterns in individual databases; (2) discovering emerging significant patterns after unifying distributed databases in a single view; and (3) finding patterns which follow special relationships across different data collections. While existing research has significantly advanced the techniques for mining local and global patterns (the first two goals), very little attempt has been made to discover patterns across distributed databases (the third goal). Moreover, no framework currently exists to support the mining of all three types of patterns. This paper proposes solutions to discover patterns from distributed databases. More specifically, we consider pattern mining as a query process where the purpose is to discover patterns from distributed databases with patterns' relationships satisfying user specified query constraints. We argue that existing self-contained mining frameworks are neither efficient, nor feasible to fulfill the objective, mainly because their pattern pruning is single-database oriented. To solve the problem, we advocate a cross-database pruning concept and propose a collaborative pattern (CLAP) mining framework with cross-database pruning mechanisms for distributed pattern mining. In CLAP, distributed databases collaboratively exchange pattern information between sites so that each site can leverage information from other sites to gain cross-database pruning. Experimental results show that CLAP fits a niche position, and demonstrate that CLAP not only outperforms its other peers with significant runtime performance gains, but also helps find patterns incapable of being discovered by others.     

Mining globally interesting patterns from multiple databases using kernel estimation

When extracting knowledge (or patterns) from multiple databases, the data from different databases might be too large in volume to be merged into one database for centralized mining on one computer, the local information sources might be hidden from a global decision maker due to privacy concerns, and different local databases may have different contribution to the global pattern. Dealing with multiple databases is essentially different from mining from a single database. In multi-database mining, the global patterns must be obtained by carefully analyzing the local patterns from individual databases. In this paper, we propose a nonlinear method, named KEMGP (kernel estimation for mining global patterns), to tackle this problem, which adopts kernel estimation to synthesizing local patterns for global patterns. We also adopt a method to divide all the data in different databases according to attribute dimensionality, which reduces the total space complexity. We test our algorithm on a customer management system, where the application is to obtain all globally interesting patterns by analyzing the individual databases. The experimental results show that our method is efficient.     

分布式序列模式发现算法的研究

提出算法FDMSP(fast distributed mining of sequential patterns),以解决分布式环境下的序列模式挖掘问题.首先对分布式环境下序列模式的性质进行了分析.算法采用前缀投影技术划分模式搜索空间,利用序列模式前缀指定选举站点统计序列的全局支持计数,利用局部约减、选举约减、计数约减等方法减少候选序列数,同时将算法分为3个子过程异步运行,使得算法具有较低的I/O开销、内存开销和通信开销,从而高效地生成全局序列模式.实验结果显示,在具有海量数据的局域网环境中,FDMSP算法的性能优于将数据集中后采用GSP算法68.5%～99.5%,并且FDMSP算法具有良好的可伸缩性.     

带有间隔约束的多序列模式挖掘

研究这样一个问题：给定多序列、支持度阈值和间隔约束,从多序列中挖掘所有出现次数不小于支持度阈值的频繁序列模式,这里要求模式中任意两个相邻元素在序列中的出现都要满足用户自定义的间隔约束,并且模式在序列中的出现要满足one-off条件。在解决该问题上,已有算法M-OneOffMine在计算模式的支持度时,只考虑模式的每个字符在序列中的首次出现,导致计算的模式支持度远小于其真实支持度,以致许多频繁的模式没有被挖掘出来。为此,设计了一个有效的带有间隔约束的多序列模式挖掘算法--MMSP算法：首先,通过采用二维表保存模式的候选位置;然后,根据候选位置采用最左最优的思想选择匹配位置。通过生物DNA序列进行实验,多序列中元素序列数目不变而序列长度变化时,MMSP挖掘出的频繁模式总数是同类算法M-OneOffMine的3.23倍;在元素序列个数变化时,MMSP挖掘出的频繁模式个数平均是M-OneOffMine的4.11倍;这两种情况下MMSP都有更好的时间性能。在模式长度变化时,MMSP挖掘出的频繁模式个数分别平均是M-OneOffMine的2.21倍和MPP的5.24倍。同时还验证了M-OneOffMine挖掘到的模式是MMSP挖掘到的频繁的子集。实验结果表明,MMSP算法不仅可以挖掘到更多的频繁模式,而且时间花费更少,更适合于实际的应用。     

序列模式图及其构造算法

序列模式挖掘是数据挖掘的一个重要分支。在序列事务及有关信息处理中有着广泛的应用,目前已有许多序列模式模型及相应的挖掘算法，该文在对序列模式挖掘问题及挖掘算法进行分析的基础上。定义了一种称为序列模式图的序列模式框架。用于表示序列模式挖掘过程发现的所有序列模式，序列模式图是由离散状态的序列集到统一的图结构的桥梁，可以将序列模式挖掘结果统一到序列模式图中来，基于序列模式图进行研究可发现某些结构化的新知识，称之为后序列模式挖掘，文中还给出了序列模式图的有关性质及构造算法。     

一种挖掘压缩序列模式的有效算法

从序列数据库中挖掘频繁序列模式是数据挖掘领域的一个中心研究主题,而且该领域已经提出和研究了各种有效的序列模式挖掘算法.由于在挖掘过程中会产生大量的频繁序列模式,最近许多研究者已经不再聚焦于序列模式挖掘算法的效率,而更关注于如何让用户更容易地理解序列模式的结果集.受压缩频繁项集思想的启发,提出了一种CFSP(compressing frequent sequential patterns)算法,其可挖掘出少量有代表性的序列模式来表达全部频繁序列模式的信息,并且清除了大量的冗余序列模式.CFSP是一种two-steps的算法:在第1步,其获得了全部闭序列模式作为有代表性序列模式的候选集,与此同时还得到大多数的有代表性模式;在第2步,该算法只花费了少量的时间去发现剩余的有代表性序列模式.一个采用真实数据集与模拟数据集的实验研究也证明了CFSP算法具有高效性.     

一种基于聚类的多数据库分类方法设计

多数据库挖掘最常用的方法是先将多数据库进行分类,然后对每个类进行单独挖掘,最后将各个类中的模式进行集成得到全局模式。这些数据库分类方法都只是针对事务数据库而设计,用两个数据库中共同项集的比例来衡量这两个数据库的相似度,以此来进行数据库分类。本文提出一种基于聚类的数据库分类方法,可以对任何类型的数据库进行分类。