《最新序列模式挖掘PPT课件.ppt》由会员分享，可在线阅读，更多相关《最新序列模式挖掘PPT课件.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、序列模式挖掘内容概要 基本概念基本概念 类类AprioriApriori生成候选算法生成候选算法2001-8-152思考思考:是否属于是否属于?注意注意:并不属于并不属于,反之亦然反之亦然因为后者代表项目因为后者代表项目3 3及及5,5,是购买一个之后购买另是购买一个之后购买另外一个，而前者是代表两个一起购买外一个，而前者是代表两个一起购买 基本概念基本概念2001-8-159序列序列 在序列数据库在序列数据库S中的中的支持数支持数为序列数据库为序列数据库S中中包含序列包含序列 的序列个数，记为的序列个数，记为Support()给定支持度阈值给定支持度阈值，如果序列，如果序列 在序列数据库中的
2、次在序列数据库中的次数不低于数不低于，则称序列，则称序列 为为序列模式序列模式长度为长度为l的序列模式记为的序列模式记为l-模式模式基本概念基本概念2001-8-1510例子例子3：设序列数据库如下图所示，并设用户指定的最小支持：设序列数据库如下图所示，并设用户指定的最小支持度度min-support=2。Sequence_idSequence10203040l序列序列是否是否的子序列的子序列?基本概念基本概念-是是序列序列是长度为是长度为3的的序列模式序列模式(10,30)2001-8-1511例子例子4:对于开始的对于开始的数据表数据表，可以得到它的客户序列如下，可以得到它的客户序列如下客
3、户标识客户序列12345基本概念基本概念2001-8-1512l设最小支持度为设最小支持度为25%，即最小支持计数，即最小支持计数（5x25%=1.25，取上整为，取上整为2）l可以看出两个序列可以看出两个序列满足最小满足最小支持度支持度l不满足最小支持度的序列之一是不满足最小支持度的序列之一是基本概念基本概念2001-8-15132.应用领域：应用领域：客户购买行为模式预测客户购买行为模式预测Web访问模式预测访问模式预测疾病诊断疾病诊断自然灾害预测自然灾害预测DNA序列分析序列分析故障诊断系统故障诊断系统基本概念基本概念2001-8-1514应用案例1：客户购买行为模式分析lB2CB2C电
4、子商务网站可以根据客户购买纪录来分析客电子商务网站可以根据客户购买纪录来分析客户购买行为模式，从而进行有针对性的营销策略。户购买行为模式，从而进行有针对性的营销策略。IDUser transaction sequence1.23.4.图书交易网站将用户购物纪录整合成用户购物序列集合得到用户购物行为序列模式相关商品推荐：如果用户购买了书籍“UML语言”,则推荐“Visio2003实用技巧”2001-8-1515应用案例2：Web访问模式分析l大型网站的网站地图大型网站的网站地图(site(site map)map)往往具有复杂的拓扑结构。往往具有复杂的拓扑结构。用户访问序列模式的挖掘有助用户访问
5、序列模式的挖掘有助于改进网站地图的拓扑结构。于改进网站地图的拓扑结构。比如用户经常访问网页比如用户经常访问网页web1web1然然后访问后访问web2,web2,而在网站地图中二而在网站地图中二者距离较远，就有必要调整网者距离较远，就有必要调整网站地图，缩短它们的距离，甚站地图，缩短它们的距离，甚至直接增加一条链接。至直接增加一条链接。Index 网站入口web1web22001-8-1516应用案例3：疾病诊断 医疗领域的专家系统可以作为疾病诊断医疗领域的专家系统可以作为疾病诊断的辅助决策手段。的辅助决策手段。对应特定的疾病，众多该类病人的对应特定的疾病，众多该类病人的症状症状按时间顺序被记
6、录按时间顺序被记录。自动分析该纪录可以发现。自动分析该纪录可以发现对应此类疾病对应此类疾病普适的症状模式普适的症状模式。每种疾病和对应的一系列症状模式被每种疾病和对应的一系列症状模式被加入加入到知识库后到知识库后，专家系统就可以依此来辅助人类，专家系统就可以依此来辅助人类专家进行疾病诊断。专家进行疾病诊断。2001-8-1517应用案例3：疾病诊断例例:通过分析大量曾患通过分析大量曾患A A类疾病的病人发病类疾病的病人发病纪录，发现以下症状发生的序列模式：纪录，发现以下症状发生的序列模式：()如果病人具有以上症状，则有可能患如果病人具有以上症状，则有可能患A A类疾类疾病病2001-8-151
7、8应用案例4：查询扩展l查询扩展是搜索领域一个重要的问题。用户提交的查询扩展是搜索领域一个重要的问题。用户提交的查询往往不能完全反映其信息需求。一些研究工作查询往往不能完全反映其信息需求。一些研究工作尝试用用户的查询序列模式来辅助原始查询，其主尝试用用户的查询序列模式来辅助原始查询，其主要思想是：要思想是：1 1）挖掘用户的查询序列模式挖掘用户的查询序列模式2 2）用这些序列模式构造查询词关系图）用这些序列模式构造查询词关系图3 3）找到每个极大全连通图作为一个）找到每个极大全连通图作为一个”概念概念”4)4)对于一个查询，和它同处于一个对于一个查询，和它同处于一个”概念概念”的查询可以作为查
8、的查询可以作为查询扩展的选项询扩展的选项2001-8-1519应用案例4：查询扩展l给定一组查询模式：给定一组查询模式：(,)查询关系图如上图：查询关系图如上图：丰田雷诺宝马汽车概念1：汽车品牌概念2：汽车2001-8-15203.问题描述：问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式序列数据库中所有的序列模式4.系统规定：系统规定：由于同一个元素中的项目之间排列没有顺序，为了表达的唯一由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目性，我们将同一个元素内
9、部的不同项目按照字典顺序排列按照字典顺序排列基本概念基本概念2001-8-1521 二、序列模式挖掘算法二、序列模式挖掘算法 1 1、序列模式挖掘的、序列模式挖掘的、序列模式挖掘的、序列模式挖掘的5 5个阶段个阶段个阶段个阶段排序阶段排序阶段排序阶段排序阶段 发现频繁项集阶段发现频繁项集阶段发现频繁项集阶段发现频繁项集阶段 转换阶段转换阶段转换阶段转换阶段 序列阶段序列阶段序列阶段序列阶段 最大阶段最大阶段最大阶段最大阶段 2001-8-1522(1)排序阶段排序阶段l利用利用客户标识客户标识customer-id作作为主关键字为主关键字以及以及事务发生事务发生时间时间transaction-
10、time作为次关键字作为次关键字对数据库对数据库D排序排序l该步骤将原始的该步骤将原始的事务数据库事务数据库转换成客户转换成客户序列的数据库序列的数据库序列模式挖掘算法序列模式挖掘算法-排序排序2001-8-1523交易发生的时间交易发生的时间客户标识客户标识购买项购买项June 1004June 1204June 1504June 2004June 2504June 2504June 2504June 3004June 3004July 25042522431144A，BHCD，F，GCC，E，GCHD，GH2001-8-1524客户标识交易时间交易时间购买项购买项11June 2504Ju
11、ne 3004CH222June 1004June 1504June 2004A,BCD,F,G3June 2504C,E,G444June 2504June 3004July 2504CD,GH5June 1204H由由客户标识客户标识及及交易发生的时间交易发生的时间为关键字所排序的数据库为关键字所排序的数据库排序阶段排序阶段2001-8-1525客户客户号号客户序列客户序列12345客户序列描述数据库客户序列描述数据库频繁项频繁项集集映射映射(C)(D)(G)(D,G)(H)12345频繁项集分别是频繁项集分别是(C)、(D)、(G)、(D,G)和和(H)(2)(2)发现频繁项集阶段发现频
12、繁项集阶段2001-8-1526客户标识客户标识原始客户序列原始客户序列转换后客户序列转换后客户序列映射后序列映射后序列12345转换后的数据库（客户序列）转换后的数据库（客户序列）(3)(3)转换阶段转换阶段2001-8-1527需要将每一个顾客序列转换成一个替换的代表需要将每一个顾客序列转换成一个替换的代表l在一个已经转换的客户序列中，每一个事务被在一个已经转换的客户序列中，每一个事务被包含包含于该事物中的所有频繁项目集于该事物中的所有频繁项目集来替换来替换l如果一个序列不包含任何如果一个序列不包含任何频繁频繁项目集，则在已经转项目集，则在已经转换的序列中就不应该保留这项事务换的序列中就不
13、应该保留这项事务转换规则转换规则2001-8-1528 AprioriAllAprioriAll,AprioriSomeAprioriSome算法算法 FreeSpanFreeSpan，PrefixSpanPrefixSpan算法算法(4)(4)(4)(4)序列阶段序列阶段序列阶段序列阶段 (5)(5)(5)(5)最大阶段最大阶段最大阶段最大阶段2.核心算法核心算法2001-8-1529序列阶段算法l给出的算法分为两个系列：给出的算法分为两个系列：count-all和和count-somel通用结构是遍历数据多遍，在每一遍都利用一个频通用结构是遍历数据多遍，在每一遍都利用一个频繁序列的种子集合
14、作为开始，利用种子集合来产生繁序列的种子集合作为开始，利用种子集合来产生新的潜在频繁序列，称作候选序列新的潜在频繁序列，称作候选序列(CandidateSequence)2001-8-1530两个系列lcount-allAprioriAll算法算法lcount-someAprioriSome算法和算法和DynamicSome算算法法2001-8-1531类类Apriori算法算法-AprioriAll算法l在每一遍中都利用前一遍的频繁序列产生候选序列，在每一遍中都利用前一遍的频繁序列产生候选序列，然后在完成遍历整个数据库后测试它们的支持度。然后在完成遍历整个数据库后测试它们的支持度。l遍历结束
15、时，候选者的支持度用来确定频繁序列。遍历结束时，候选者的支持度用来确定频繁序列。l在第一遍在第一遍,输出用来初始化输出用来初始化1序列模式的集合序列模式的集合2001-8-1532AprioriAll候选序列的产生候选序列的产生(1)(1)首先进行首先进行 L Lk-1k-1 与与 L Lk-1k-1 的连接运算的连接运算比如比如与与连接成为连接成为要注意的是要注意的是和和是两个序列是两个序列(2)(2)其次进行修剪其次进行修剪对于一个连接过后的序列，如果它的任意一个子列不在对于一个连接过后的序列，如果它的任意一个子列不在L Lk-1k-1 中，那么删除该序列，这个过程称为修剪中，那么删除该序
16、列，这个过程称为修剪2001-8-1533产生候选序列示例产生候选序列示例序列序列支持度支持度连接结果连接结果22322修剪后得到最后结果修剪后得到最后结果2001-8-1534应用应用AprioriAll算法例子（一）算法例子（一）例：如下给出一个数据库（转换阶段已经完成），最小支持度例：如下给出一个数据库（转换阶段已经完成），最小支持度是是40%40%，如下为客户序列，如下为客户序列2001-8-1535应用应用AprioriAll算法例子（二）算法例子（二）序列序列支持度支持度424421序列模式序列模式2001-8-1536应用应用AprioriAll算法例子（三）算法例子（三）序列序
17、列支持度支持度24222001-8-1537应用应用AprioriAll算法例子算法例子(四四)序列序列支持度支持度223223序列模式序列模式2001-8-1538应用应用AprioriAll算法例子（五）算法例子（五）序列序列支持度支持度24序列模式序列模式至此算法结束，得到结果最大序列至此算法结束，得到结果最大序列2001-8-1539 类类类类AprioriApriori算法有以下缺点：算法有以下缺点：算法有以下缺点：算法有以下缺点：l l有可能生成庞大众多的候选序列有可能生成庞大众多的候选序列有可能生成庞大众多的候选序列有可能生成庞大众多的候选序列l l多遍扫描数据库多遍扫描数据库多
18、遍扫描数据库多遍扫描数据库l l不易发生长度较大的序列模式不易发生长度较大的序列模式不易发生长度较大的序列模式不易发生长度较大的序列模式,序列模式越长，序列模式越长，序列模式越长，序列模式越长，所需要生成的序列就越多所需要生成的序列就越多所需要生成的序列就越多所需要生成的序列就越多。2001-8-1540序列模式 VS 关联规则 问题问题序列模式挖掘序列模式挖掘 关联规则挖掘关联规则挖掘数据集数据集序列数据库序列数据库事务数据库事务数据库关注点关注点单项间在同一单项间在同一事务内以及事事务内以及事务间的关系务间的关系单项间在同一单项间在同一事务内的关系事务内的关系2001-8-1541Pref
19、ixSpan算法算法l相关定义相关定义前缀前缀：设每个元素中的所有项目按照字典序排列。给定：设每个元素中的所有项目按照字典序排列。给定序列序列 =e，=e(m(m n)n)，如果如果e ei i =e ei i (i(i m-1 m-1)，e em m e em m，并且并且(e em m-e em m)中的项目均在中的项目均在e em m中项目的后面，中项目的后面，则称则称 是是 的前的前缀缀2001-8-1542投影投影：给定序列：给定序列 和和 ，如果，如果 是是 的子序列，则的子序列，则 关关于于 的投影的投影 必须满足：必须满足：是是 的前缀，的前缀，是是 的满足的满足上述条件的最大
20、子序列上述条件的最大子序列后缀后缀：序列序列 关于子序列关于子序列 =的投影的投影为为 =(n=m)，则序列，则序列 关于子序列关于子序列 的后缀为的后缀为，其中其中em”=(em-em)2001-8-1543三、PrefixSpan算法l例子：例子：a(ab)a(abc)2001-8-1544三、PrefixSpan算法l算法描述：算法描述：扫描序列数据库，生成所有长度为扫描序列数据库，生成所有长度为1的序列模式的序列模式根据长度为根据长度为1的序列模式，生成相应的投影数据库的序列模式，生成相应的投影数据库在相应的投影数据库上重复上述步骤，直到在相应在相应的投影数据库上重复上述步骤，直到在相
21、应的投影数据库上不能产生长度为的投影数据库上不能产生长度为1的序列模式为止的序列模式为止SS1SmS11 S1n Sm1 Smp 2001-8-1545三、PrefixSpan算法l扫描序列数据库扫描序列数据库S，产生长度为，产生长度为1的序列模式有：的序列模式有：:4,:4,:4,:3,:3,:3l序列模式的全集必然可以分为分别以序列模式的全集必然可以分为分别以，和和为前缀的序列模式的集合，构造不同为前缀的序列模式的集合，构造不同前缀所对应的投影数据库，结果如下页图所示前缀所对应的投影数据库，结果如下页图所示l分别对不同的投影数据库重复上述过程，直到没有新分别对不同的投影数据库重复上述过程，
22、直到没有新的长度为的长度为1的序列模式产生为止的序列模式产生为止Sequence_idSequence102030402001-8-1546三、PrefixSpan算法PrefixProject Database Sequence_idSequence102030402001-8-1547三、PrefixSpan算法l定义定义1.投影数据库投影数据库：设：设 为序列数据库为序列数据库S中的一个序列模式，则中的一个序列模式，则 的投影数据库为的投影数据库为S中所有以中所有以 为前缀的序列相对于为前缀的序列相对于 的后缀，记为的后缀，记为S|l定义定义2.投影数据库中的支持数投影数据库中的支持数：
23、设设 为序列数据库为序列数据库S中的一个序列中的一个序列模式，序列模式，序列 以以 为前缀，则为前缀，则 在在 的投影数据库的投影数据库S|中的支持数为中的支持数为S|中满足条件中满足条件 .的序列的序列 的个数的个数2001-8-1548三、PrefixSpan算法lPrefixSpan算法算法输入：序列数据库输入：序列数据库S及最小支持度阈值及最小支持度阈值min_sup输出：所有的序列模式输出：所有的序列模式方法：调用子程序方法：调用子程序PrefixSpan(,0,S)2001-8-1549三、PrefixSpan算法l子程序子程序PrefixSpan(,L,S|)参数：参数：.一个序
24、列模式一个序列模式 L.序列模式序列模式 的长度的长度 S|.如果如果 为空，则为为空，则为S，否则为否则为 的投影数据库的投影数据库扫描扫描S|，找到满足下述要求的长度为找到满足下述要求的长度为1的序列模式的序列模式b：b可以添加到可以添加到 的最后一个元素中并为序列模式的最后一个元素中并为序列模式可以作为可以作为 的最后一个元素并为序列模式的最后一个元素并为序列模式对每个生成的序列模式对每个生成的序列模式b，将，将b添加到添加到 形成序列模形成序列模式式，并输出，并输出 对每个对每个,构造构造 的投影数据库的投影数据库S|,并并调用子程序调用子程序PrefixSpan(,L+1,S|)20
25、01-8-1550三、PrefixSpan算法lPrefixSpan算法分析：算法分析：PrefixSpan算法不需要产生候选序列模式，从而大算法不需要产生候选序列模式，从而大大缩减了检索空间大缩减了检索空间相对于原始的序列数据库而言，投影数据库的规模相对于原始的序列数据库而言，投影数据库的规模不断减小不断减小PrefixSpan算法的主要开销在于投影数据库的构造算法的主要开销在于投影数据库的构造2001-8-1551三、PrefixSpan算法lPrefixSpan算法的主要改进：算法的主要改进：逐层投影逐层投影：使用隔层投影代替逐层投影，从而可以：使用隔层投影代替逐层投影，从而可以有效减小
26、投影数据库的个数有效减小投影数据库的个数伪投影伪投影：当序列数据库可以直接放入内存时，可以：当序列数据库可以直接放入内存时，可以使用伪投影操作代替实际的投影数据库，从而可以使用伪投影操作代替实际的投影数据库，从而可以有效减少构造投影数据库的开销有效减少构造投影数据库的开销2001-8-1552三、PrefixSpan算法l隔层投影的例子：隔层投影的例子：扫描序列数据库，产生所有长度为扫描序列数据库，产生所有长度为1的序列模式的序列模式再次扫描序列数据库，构造如下图所示的下三角矩阵，得到所有再次扫描序列数据库，构造如下图所示的下三角矩阵，得到所有长度为长度为2的序列模式的序列模式构造长度为构造长
27、度为2的序列模式所对应的扫描数据库，然后对每个投影数的序列模式所对应的扫描数据库，然后对每个投影数据库，重复上面的操作，直到没有新的序列模式产生为止据库，重复上面的操作，直到没有新的序列模式产生为止Sequence_idSequence10203040a2b(4,2,2)1c(4,2,1)(3,3,2)3d(2,1,1)(2,2,0)(1,3,0)0e(1,2,1)(1,2,0)(1,2,0)(1,1,0)0f(2,1,1)(2,2,0)(1,2,1)(1,1,1)(2,0,1)1abcdef2001-8-1553三、PrefixSpan算法l伪投影：当数据库可以直接放入内层时，并不需要构伪投
28、影：当数据库可以直接放入内层时，并不需要构造所有的序列模式对应的投影数据库，我们可以使用造所有的序列模式对应的投影数据库，我们可以使用指向数据库中序列的指针及其偏移量作为伪投影指向数据库中序列的指针及其偏移量作为伪投影l例子：假设上述序列数据库可以放入内层，在构造例子：假设上述序列数据库可以放入内层，在构造a投投影数据库时，序列影数据库时，序列 S1=所对应的伪投所对应的伪投影为：一个指向影为：一个指向S1的指针，指针偏移设定为的指针，指针偏移设定为2。同样的，。同样的，序列序列S1的的投影数据库对应的伪投影为：一个指向投影数据库对应的伪投影为：一个指向S1的指针，指针偏移设定为的指针，指针偏
29、移设定为42001-8-1554l上述算法存在的主要问题：上述算法存在的主要问题：缺少时间限制缺少时间限制：用户可能需要指定序列模式的相邻：用户可能需要指定序列模式的相邻元素之间的时间间隔。例如，一个序列模式可能会元素之间的时间间隔。例如，一个序列模式可能会发现客户在购买了物品发现客户在购买了物品A后的第三年购买物品后的第三年购买物品B。我我们需要的却是给定时间间隔内用户的购买意向们需要的却是给定时间间隔内用户的购买意向事务的定义过于严格事务的定义过于严格：一个事务中包含在客户的一：一个事务中包含在客户的一次购买行为中所购买的所有物品。可能需要指定一次购买行为中所购买的所有物品。可能需要指定一个滑动时间窗口，客户在滑动时间窗口的时间段内个滑动时间窗口，客户在滑动时间窗口的时间段内的所有的购买行为均作为一个事务的所有的购买行为均作为一个事务缺少分类层次缺少分类层次：只能在项目的原始级别上进行挖掘：只能在项目的原始级别上进行挖掘2001-8-1555结束语结束语谢谢大家聆听！谢谢大家聆听！56