第四章：序列模式4规范.pptxVIP

数据挖掘 第四章：序列模式分析 　 本章内容 4.1 序列模式的基本概念 4.2 GSP算法 4.3 PrefixSpan算法 基本要求：掌握序列模式的基本概念，掌握GSP、PrefixSpan两种典型序列模式挖掘算法 4.1 序列模式的基本概念 序列模式(sequential pattern)的概念最早是由Agrawal和Srikant 提出的，序列模式分析旨在寻找事件间在顺序上的相关性。 例子： 凡是买了喷墨打印机的顾客中，80%的人在三个月之后又买了墨盒 。 两年前购买了Ford 牌轿车的顾客，很可能在今年采取贴旧换新的购车行动。 购买了自行车的客户中，70%的客户会在两个月后购买打气筒。 典型应用 客户购买行为模式预测 Web访问模式预测 疾病诊断 自然灾害预测 DNA序列分析 4.1 序列模式的基本概念 序列模式(sequential pattern)的概念最早是由Agrawal和Srikant 提出的，序列模式分析旨在寻找事件间在顺序上的相关性。 例子： 凡是买了喷墨打印机的顾客中，80%的人在三个月之后又买了墨盒 。 两年前购买了Ford 牌轿车的顾客，很可能在今年采取贴旧换新的购车行动。 购买了自行车的客户中，70%的客户会在两个月后购买打气筒。 典型应用 E-learning中的应用 4.1 序列模式的基本概念 typhoon flood, landslide typhoon flood, landslide A series of daily news paper articles typhoon (flood, landslide) 事件中的例子 4.1 序列模式的基本概念 交易数据数据库 交易数据数据库（按顾客与时间排序） Customer Transaction Time Items Bought B. Adams June 21, 1994 5:27 pm Beer B. Adams June 22, 1994 10:34 am Brandy J. Brown June 20, 1994 10:13 am Juice, Coke J. Brown June 20, 1994 11:47 am Beer J. Brown June 21, 1994 9:22 am Wine, Water, Cider J. Mitchell June 21, 1994 3:19 pm Beer, Gin, Cider B. Moore June 20, 1994 2:32 pm Beer B. Moore June 21, 1994 6:17 pm Wine, Cider B. Moore June 22, 1994 5:03 pm Brandy F. Zappa June 20, 1994 11:02 am Brandy 4.1 序列模式的基本概念 序列数据库 序列模式 4.1 序列模式的基本概念 4.1 序列模式的基本概念 序列模式：给定一个由不同序列组成的集合，其中每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值，序列模式就是频繁子序列，即该子序列在序列集中的出现频率不低于最小支持度阈值。 4.1 序列模式的基本概念 Sequence Database Sequence Element (Transaction) Event(Item) Customer Purchase history of a given customer A set of items bought by a customer at time t Books, diary products, CDs, etc Event data History of events generated by a given sensor Events triggered by a sensor at time t Types of alarms generated by sensors Genome sequences DNA sequence of a particular species An element of the DNA sequence Bases A,T,G,C Sequence E1E2 E1E3 E2 E3E4 E2 Element (Transaction) Event (Item) 4.1 序列模式的基本概念 形式化表示： 项目集(Itemset)是各种项目组成的集合。 序列(Sequence)是不同项目集的有序排列，序列s可以表示为s = s1s2…sl，sj(1 = j = l)为项目集，也称为序列s的元素。 序列的元素(Element)可表示为(