序列模式挖掘算法解决方案.ppt

2001-8-15 第4章 序列模式挖掘算法 主要内容 序列模式挖掘简介 序列模式挖掘的应用背景 序列模式挖掘算法概述 GSP算法 PrefixSpan算法 Disc-all算法 支持约束的序列模式挖掘 一、序列模式挖掘简介 序列模式的概念最早是由Agrawal和Srikant 提出的。 动机：大型连锁超市的交易数据有一系列的用户事务数据库，每一条记录包括用户的ID，事务发生的时间和事务涉及的项目。如果能在其中挖掘涉及事务间关联关系的模式，即用户几次购买行为间的联系，可以采取更有针对性的营销措施。 事务数据库实例 例：一个事务数据库，一个事务代表一笔交易，一个单项代表交易的商品，单项属性中的数字记录的是商品ID 序列数据库 一般为了方便处理，需要把数据库转化为序列数据库。方法是把用户ID相同的记录合并，有时每个事务的发生时间可以忽略，仅保持事务间的偏序关系。 问题定义 项集(Itemset)是所有在序列数据库出现过的单项组成的集合 例：对一个用户购买记录的序列数据库来说，项集包含用户购买的所有商品，一种商品就是一个单项。通常每个单项有一个唯一的ID，在数据库中记录的是单项的ID。 问题定义 元素(Element)可表示为(x1x2…xm)， xk(1 = k = m)为不同的单项。元素内的单项不考虑顺序关系，一般默认按照ID的字典序排列． 在用户事务数据库里，一个事务就是一个元素。 问题定义 序列(Sequence)是不同元素(Element)的有序排列，序列s可以表示为s = s1s2…sl，sj(1 = j = l)为序列s的元素 一个序列包含的所有单项的个数称为序列的长度。长度为l的序列记为l-序列 例：一条序列(10,20)30(40,60,70)有3个元素，分别是（10 20），30，（40 60 70 ）； 3个事务的发生时间是由前到后。这条 序列是一个6-序列。 问题定义 设序列? = a1a2…an，序列? = b1b2…bm，ai 和bi都是元素。如果存在整数1 = j1 j2 … jn = m，使得a1 ? bj1，a2 ? bj2，…， an ? bjn，则称序列?为序列?的子序列，又称序列?包含序列?，记为? ? ?。 问题定义 序列?在序列数据库S中的支持度为序列数据库S中包含序列?的序列个数，记为Support(?) 给定支持度阈值?，如果序列?在序列数据库中的支持数不低于?，则称序列?为序列模式 长度为l的序列模式记为l-模式 例子：设序列数据库如下图所示，并设用户指定的最小支持度min-support = 2。 　序列模式 VS 关联规则 二、序列模式挖掘的应用背景 应用领域： 客户购买行为模式预测 Web访问模式预测 疾病诊断 自然灾害预测 DNA序列分析 应用案例3：疾病诊断 例: 通过分析大量曾患A类疾病的病人发病纪录，发现以下症状发生的序列模式：(眩晕) (两天后低烧37-38度) 如果病人具有以上症状，则有可能患A类疾病 三、序列模式挖掘算法概述 Agrawal和Srikant在提出这个问题时提出了三个算法，AprioriAll ， AprioriSome 和DynamicSome， 它们都基于Apriori框架。构成了序列模式挖掘问题的基石。随后，这个领域 的研究工作取得了大量的成果。 序列模式挖掘算法概述 类Apriori算法 基于划分的模式生长算法 基于序列比较的算法 类Apriori算法 该类算法基于Apriori理论，即序列模式的任一子序列也是序列模式。算法首先自底向上的根据较短的序列模式生成较长的候选序列模式，然后计算候选序列模式的支持度。典型的代表有GSP算法, spade算法等。 基于划分的模式生长算法 该类算法基于分治的思想，迭代的将原始数据集进行划分，减少数据规模，同时在划分的过程中动态的挖掘序列模式，并将新发现的序列模式作为新的划分元。典型的代表有FreeSpan算法和prefixSpan算法。 基于序列比较的算法 该类算法首先定义序列的大小度量，接着从小到大的枚举原始序列数据库中包含的所有k-序列，理论上所有的k-序列模式都能被找到。算法制定特定的规则加快这种枚举过程。典型的代表为Disc-all算法。 四、GSP算法 算法思想： 类似于Apriori算法，采用冗余候选模式的剪除策略和特殊的数据结构-----哈希树来实现候选模式的快速访存。