论文总字数：23820字

目 录

1 绪论 1

1.1 序列模式挖掘的概念 1

1.2 序列模式挖掘的研究现状 1

1.3 研究目的及意义 2

1.4 研究内容 2

2 典型的top-k算法 3

2.1 top-k序列模式 3

2.2 TSP和TKS算法 3

2.2.1 TSP算法 3

2.2.2 TKS算法 3

2.2.3 性能分析 4

3 基于兴趣度的序列模式挖掘算法 4

3.1 OPUS算法 4

3.1.1 OPUS算法介绍 4

3.1.2 算法描述 5

3.1.3 算法的复杂度 8

3.2 SkOPUS算法 9

3.2.1 基本定义 9

3.2.2 序列模式预期支持度的定义 9

3.2.3 SkOPUS算法介绍 11

3.2.4 上界值 12

3.2.5 SkOPUS算法的流程图 12

3.3 改进后的SkOPUS算法 17

3.3.1 改进方法 17

3.3.2 算法实现 17

4 实验与结果分析 18

4.1 数据集 18

4.2 实验与结果分析 19

5 总结与展望 22

5.1 总结 22

5.2 展望 23

参考文献 23

致谢 25

基于兴趣度的序列模式挖掘算法的研究

杨雅婕

，China

Abstract:Extracting interesting patterns from massive data is the core task of data mining. Sequential pattern mining is an important research content of data mining and has been widely used in many fields in recent years. Traditional pattern mining often uses frequency as a criterion for whether the pattern is interesting. If a pattern frequently appears in the database, the pattern is considered to be interesting. However, because the frequency of many patterns can be simply interpreted as contingency in real data, the frequency can not be a good representation of interestingness metrics. When dealing with a sequence database, this problem becomes more pronounced due to the repeatability of itemsets in the sequence. To solve this problem, the text studies an algorithm that can effectively identify the k most interesting sequential patterns in the sequence database. Using leverage as an interestingness measure , it measures the interestingness degree of the sequential pattern. At the same time, the branch-and-bound OPUS algorithm is extended in sequence, all possible candidate sequences are traversed, effective pruning strategies are used to improve the efficiency of algorithm execution, and top-k most interesting sequence patterns are extracted. Finally, the effectiveness of the proposed algorithm is verified by experiments.

Key words:data mining; pattern mining; sequential data; exact discovery; interestingness measures

1 绪论

1.1 序列模式挖掘的概念

数据挖掘主要是利用某些特定的知识发现算法，在一定的运算效率限制下，从海量数据中挖掘出有潜在利用价值的知识模式。在数据挖掘领域中，序列模式挖掘是其中一个有重大应用价值的研究分支，一般是指发现相对时间或者其他顺序出现的高频率子序列。序列模式挖掘是由Agrawal and Srikant（1995）^[1]针对超市中购物篮数据的分析提出，之后便逐渐成为频繁模式挖掘领域中的一个重要分支^[2,3]，当初序列模式概念的提出是为了发现某一段时间内的客户购买规律，根据数据挖掘中关联规则挖掘的方法，通过分析消费者的购买序列，在其中带有交易时间属性的交易序列数据中找到频繁项目序列，即是我们要挖掘的频繁序列，也称之为序列模式。序列模式挖掘是数据挖掘的一个分支，它和传统的关联规则挖掘的不同之处是：序列模式挖掘针对的目标数据都是带有时间属性的序列数据，这种数据在日常生活中是很常见的，比如信用卡消费序列、城市交通数据序列、大型超市客户的购物序列等等，这些都是序列模式挖掘分析的目标数据，都有重大的商业价值^[4]。

总的来说，序列模式挖掘的问题可以描述如下：给定一个序列的集合，其中每个序列都由时间（或元素）的列表组成，而每个时间都由一个项集组成，给定由用户制定的最小支持度阈值，序列模式需要挖掘找出的频繁子序列，即，在序列集合中出现频率不小于的子序列^[4]。

1.2 序列模式挖掘的研究现状

序列模式挖掘是数据挖掘的一个重要研究领域，其目的是从序列数据库中发现频繁子序列作为模式。序列模式挖掘在Web日志分析、交易数据分析、顾客购买行为的分析、天气预报等领域具有广泛的应用前景。

剩余内容已隐藏，请支付后下载全文，论文总字数：23820字