《数据挖掘》由会员分享，可在线阅读，更多相关《数据挖掘（91页珍藏版）》请在金锄头文库上搜索。
1、中山大学硕士论文 序列模式挖掘算法研究中山大学硕士学位论文序列模式挖掘算法研究Research on Sequential Pattern Mining Algorithms专业名称：计算机软件与理论学位申请人：贺桂娇导师姓名及职称：印鉴教授答辩委员会主席（签名）：_答辩委员会委员（签名）：_ _ _ _ 中山大学信息与科学技术学院贰零零柒年拾月IV论文题目：序列模式挖掘算法研究专业：计算机软件与理论硕士生：贺桂娇指导老师：印鉴教授摘 要关联规则是数据挖掘中比较活跃的研究方向之一，它反映了大量数据中项目之间有趣的关联或联系，一个比较经典例子就是“90%的客户在购买面包和黄油的同时也购买了牛奶”
2、，数据库中的每个项目以平等一致的方式来处理。而加权关联规则则考虑了各个项目的不同的关注度，从一定程度上提高了传统关联规则的兴趣度。序列模式是在关联模型中增加了时间属性，把数据之间的关联性与时间联系起来，寻找的事务之间在时间上的先后次序关系，预测将来可能出现的值的分布。目前，对序列模式挖掘算法的研究很多，主要集中在如何提高算法的时间效率和减少空间上的开销。但在庞大的交易数据库里，这些算法很容易产生几百、几千个序列模式，如果每个序列都要实验一遍，代价太高了且让人无所适从，如何从事务数据库中找出商家更感兴趣的精简的“黄金”序列就成了当务之急。因此本文在序列模式的基础上提出了偏爱度，并结合加权的概念，
3、提出了FSPAM算法，经原型验证，该算法挖掘出的序列模式更精简且更有效。其次、序列模式的经典算法的主要思想都是最开始从数据库中找到所有长度为1的频繁序列，由此产生长度为2的频繁序列集，接着得到长度为3的频繁序列集，如此反复直到数据库不再发现频繁序列为止。象这样重复扫描数据库，造成系统沉重的负担而导致效率不佳。本文利用邻接矩阵来记录事物数据库中2-项频繁项集，进而生成需要的频繁模式。可以大大减少扫描数据库的次数，使系统的性能得到改善。关键字：关联规则，加权，偏爱度，序列模式Title:Research on Sequential Pattern Mining AlgorithmsMarjor:C
4、omputer Software and TheoryName:He GuijiaoSupervisor:Yin Jian ProfessorAbstractAssociation rule is one of the prevailing study orientations in data mining，which reflects interesting correlation or link among numerous data items. One typical example is that 90% customers purchase milk while purchasin
5、g bread and butter, each item in the database is dealt with in the same way . Yet in weight association rule, highlight degree of each item is considered, and interest in traditional association rule is improved to some extent. Frequent sequential patterns add property of time to association model ,
6、 integrate time with correlation between data., seek after the time sequence of events and forecast the distribution of values .At present, studies on frequent sequential pattern mining calculation mainly focus on how to improve time efficiency and how to minimize space occupying. But this calculati
7、ng may produce hundreds or even thousands of frequent sequential patterns from numerous database, if each of them needs to be tested, it will cost too much .So it is essential to seek the golden sequence which customers are most interested in. Therefore Preference based on Frequent sequential patter
8、ns is referred to in this thesis .Combined with the concept of weight , FSPAM calculation is put forward. Through primary test , frequent sequential pattern out of this calculation is more concise and more effective.Secondly ,the main thoughts about classic calculation of frequent sequential pattern
9、s begin by finding all the frequent sequences with 1 length, resulting in frequent sequence group with 2 lengths, then with 3 lengths and so on and on ,until no more sequence can be found in the database . So repeated scans on database burden the system, which results in low efficiency. In this thes
10、is, adjacent arrays are used to record database frequent item-sets, further to produce frequency mode, to reduce database scans and improve the performance of the system.Key words：Association Rule, weight ,Frequent Sequential Pattern Mining, Frequent itemsets目 录摘 要IAbstractII目 录III第1章 绪论51.1 论文的研究背景
11、51.2 论文选题的意义61.3 序列模式挖掘的国内外研究现状61.4 本文的主要研究内容71.5 本文的结构安排81.6 本章小结8第2章 数据挖掘与关联规则挖掘92.1 数据挖掘概述92.2 序列模式挖掘概述122.3 关联规则152.4 加权关联规则252.5 本章小结30第3章 序列挖掘模式及相关算法313.1 序列模式挖掘的概念与描述313.2 序列模式挖掘基本步骤：333.3 序列模式一般算法353.4 本章小结43第4章 基于邻接矩阵的加权偏爱序列444.1 序列模式改进算法的提出444.2 问题的描述454.3 有向邻接矩阵的引入474.4 加权偏爱支持度概念484.5 基于邻
12、接矩阵的FSPAM算法。494.6 序列模式改进算法FSPAM挖掘步骤534.7 FSPAM挖掘算法示例说明544.8 算法的特点及性能分析57第5章 算法原型及结果分析605.1 背景介绍605.2 开发前的准备：615.3数据预处理615.4 实现方法645.5 结果分析665.6 本章小结66第6章 结论与展望686.1 本文结论686.2 存在的问题以及进一步研究方向686.3 未来研究展望69参考文献71附录 本文算法autoFSPAM原型代码73致 谢89论文原创性声明90学位论文使用授权声明90中山大学硕士论文 序列模式挖掘算法研究第1章 绪论1.1 论文的研究背景 在20世纪9
13、0年代，随着计算机应用的普及，信息技术得以快速发展，并在各个行业中逐渐被广泛应用，为企业竞争态势构成了不可忽视的影响。一方面，由于数据库管理系统的广泛应用，各个领域每时每刻都在产生大量的数据。根据一项研究显示，全世界的数据量每二十个月就会番一番1，在这些海量的数据中，往往蕴含有丰富的、对企业有指导意义的知识。另一方面，由于计算机硬件价格的逐渐下降、信息技术的普及化、数据存储、处理以及传输已成为任何企业都可以负担的投资，企业很难单靠传统的信息管理方式如简单的数据录入、查询、统计等事务性处理过程建立起竞争优势2。企业急需一种能从海量数据中发现潜在知识的“工具”，以解决“数据爆炸与知识贫乏”的矛盾。
14、而对以上的挑战，数据挖掘和知识发现技术应运而生，并得到蓬勃的发展3，越来越显示出其强大的生命力。数据挖掘是从大量的、不完全的、有噪音的、模糊的、随机的实际数据中，提取隐含在当中人们不知道的潜在有用的信息和知识的过程4。它的一个重要的应用是关联规则的发现。关联规则发现是在数据库中寻找数据对象间的关联模式5，例如，“在购买面包和黄油的顾客中，90%的人同时也购买了牛奶。”就是一种关联模式，早期主要用于零售业交易数据分析，以进行物品更合理的摆放，最终提高销售量。因此，该方法有时也直接称为“货篮分析”。序列模式是从关联规则中演变而来，序列模式发现是在数据库中寻找基于一段时间区间的关联模式6，例如，“在某一时间购买个人电脑的所有顾客中，60%会在 3 个月内购买应用软件。”就是一序列模式。序列模式同关联模式非常相似，区别在于序列模式表述的是基于时间的关系，而不是关于数据对象间的关系。在实际应用中，多数数据集中的数据都带有时
