1、序 列报告人:熊 赟内容概要基本概念其他类 Apriori生成候选算法相似性搜索FreeSpan算法 ,PrefixSpan算法 第 6章 序 列 6.1 基本概念6.2 原 理6.3 核心算法6.4 其 他n 序列是不同项集的有序排列。 n 定义 1(序列 ): I= i1i2 im 是项集, ik(1,其中 sj( 1是另一个序列 S 的子序列,满足下面条件:对于每一个 j, 1的集合, sid为序列标识号,如果序列 T是 S的子序列(即 TS) 称元组 包含序列 T; 则序列 T在序列数据库 D中的支持度是数据库中包含 T的元组数,即 supportD(T) |DTS |记作suppor
2、t( T) 。 序列支持度n 定义 4(频繁序列模式):给定正整数 为支持度阈值,如果数据库中最少有 个元组包含序列S, 即 support( S) =, 则称序列 S为序列数据库 D中的一个(频繁)序列模式。n 长度为 l 的序列模式称为 l 模式。 n 序列模式挖掘的任务就是找出数据库中所有的序列模式挖掘的任务就是找出数据库中所有的序列模式,即那些在序列集合中出现频率超过序列模式,即那些在序列集合中出现频率超过最小支持度(用户指定最小支持度阈值)的子最小支持度(用户指定最小支持度阈值)的子序列。序列。频繁序列模式定义定义 5: (序列关联规则)对于给定(序列关联规则)对于给定的项集的项集 I= i1i2 im 以及序列以及序列 S,T,形如形如 ST的表达式称为序列关联规则的表达式称为序列关联规则。 序列关联规则置信度支持度序列关联规则序列关联规则 ST的支持度是支持序列 S和 T的顾客数占总顾客数之比。序列关联规则 ST的置信度记为( ),是支持序列 S和 T的顾客数与仅支持 S的顾客数之比。 序列模式挖掘阶段序列模式挖掘阶段 排序阶段排序阶段 发现频繁项集阶段发现频繁项集阶段 转换阶段转换阶段 序列阶段序列阶段 最大阶段最大阶段