数据挖掘基本算法2课件.ppt

1、数据仓库与数据挖掘第1页，共88页。2数据仓库与数据挖掘数据仓库与数据挖掘第一章 数据仓库与数据挖掘概述第二章 数据仓库的分析第三章 数据仓库的设计与实施第四章 信息分析的基本技术第五章 数据挖掘过程第六章第六章 数据挖掘基本算法数据挖掘基本算法第七章 非结构化数据挖掘第八章 离群数据挖掘第九章 数据挖掘语言与工具的选择第十章 知识管理与知识管理系统第2页，共88页。3第六章第六章 数据挖掘基本算法数据挖掘基本算法 6.1 分类规则挖掘 6.2 预测分析与趋势分析规则预测分析与趋势分析规则 6.3 数据挖掘的关联算法 6.4 数据挖掘的聚类算法 6.5 数据挖掘的统计分析算法 6.6 数据挖掘

2、的品种优化算法 6.7 数据挖掘的进化算法第3页，共88页。46.2 预测分析与趋势分析规则预测分析与趋势分析规则 6.2.1 预言的基本方法 6.2.2 定量分析预测 6.2.3 预测的结果分析 6.2.4 趋势分析挖掘第4页，共88页。56.2.1 预言的基本方法预言的基本方法 预言（prediction）是一门掌握对象变化动态的科学，它是对对象变动趋势的预见、分析和判断，也是一种动态分析方法。预言的目的是对未来未知变量的预测，这种预测是需要时间来验证的，即必须经过一定时间后，才知道预言准确性是多少。一旦建立了表示数据中固有模式和趋势的模型，那么这个模型就可以成功地用于对未来时间的结果进行

3、预测。第5页，共88页。66.2.1 预言的基本方法预言的基本方法 预测的基本步骤：（1）确定预测目标，包括预测对象、目的、对象范围；（2）收集分析内部和外部资料；（3）数据的处理及模型的选择；（4）预测模型的分析、修正；（5）确定预测值。第6页，共88页。76.2.1 预言的基本方法预言的基本方法 预测方法一般有定性分析预测法和定量预测法。定性预测包括：集合意见法、用户意见法（对象调查法）、员工意见法、专家评估法、类推法、判断预测和目标分解法等；定量预测方法包括:情景分析法、时间序列分析法（移动平均，指数平滑，季节系数，DOX-TENKENS法）、因果分析法（线性，回归，非线性模型：含生命周

4、期法，经济计量模型，灰色系统模型，状态转移分析法，模拟法，系统模型）等。第7页，共88页。86.2.2 定量分析预测定量分析预测（1）时间序列分析法（2）回归预测（3）非线性预测（4）灰色预测模型GM(1,1)（5）组合预测第8页，共88页。9（1）时间序列分析法）时间序列分析法 时间序列分析法的原始数据要求：1）在时间上具有连续性；2）数据之间的可比性；3）可以采取交叉预测。时间序列可划为四种变化特征：趋势性（T）、季节性（S）、周期性（C）、不规则性（I）。可以利用散点图识别来变化特征。时间序列分析法一般有：简单平均、移动平均、加权移动平均、指数平滑、一元线性回归、相关比例推算。第9页，共

5、88页。10（1）时间序列分析法）时间序列分析法 时间序列定义时间序列定义从时间序列的角度来看,每个数据单元可以被抽象为一个二元组(t,o)。其中：t 为时间变量;o 为数据变量,反映数据单元的实际意义,如某种商品的销售金额、股票的价格等。由此，对于时间序列可以给出如下定义：时间序列时间序列R 是一个有限集是一个有限集(t1,o1),(t2,o2),(tn,on),满满足足ti 0)Y=AEXP(BX)，(A0)Y=AEXP(B/X)，(A0)Y=AEXP(BX2)，(A0)将以上模型进行线性处理再转化为一元回归模型。第13页，共88页。14（4）灰色预测模型）灰色预测模型 客观世界，既是物质

6、的世界又是信息的世界。它既包含大量的已知信息，也包含大量的未知信息与非确知信息。未知的或非确知的信息称为黑色信息；已知信息称为白色信息。白色系统是指一个系统的内部特征是完全已知的，即系统的信息是完全充分的。黑色系统是指一个系统的内部信息对外界来说是一无所知的，只能通过它与外界的联系来加以观测研究。既含有已知信息又含有未知的、非确知的信息的系统，称为灰色系统。第14页，共88页。15（4）灰色预测模型）灰色预测模型 在现实世界中，灰色系统是普遍存在的。灰色系统理论，是由我国著名学者邓聚龙先生于80年代初首创的一种系统科学理论。主要包括：灰色系统建模理论、灰色系统控制理论、灰色关联分析方法、灰色预

7、测方法、灰色规划方法、灰色决策方法等。灰色预测法是一种对含有不确定因素的系统进行预测的方法。灰色系统是介于白色系统和黑色系统之间的一种系统。第15页，共88页。16（4）灰色预测模型）灰色预测模型 灰色预测通过鉴别系统因素之间发展趋势的相异程度，即进行关联分析，并对原始数据进行生成处理来寻找系统变动的规律，生成有较强规律性的数据序列，然后建立相应的微分方程模型，从而预测事物未来发展趋势的状况。其用等时距观测到的反应预测对象特征的一系列数量值构造灰色预测模型，预测未来某一时刻的特征量，或达到某一特征量的时间。第16页，共88页。17（4）灰色预测模型）灰色预测模型 灰色预测的类型灰色预测的类型

8、灰色时间序列预测：用观察到的反映预测对象特征的时间序列来构造灰色预测模型，预测未来某一时刻的特征量，或达到某一特征量的时间。畸变预测：通过灰色模型预测异常值出现的时刻，预测异常值什么时候出现在特定时区内。系统预测：通过对系统行为特征指标建立一组相互关联的灰色预测模型，预测系统中众多变量间的相互协调关系的变化。拓扑预测：将原始数据作曲线，在曲线上按定值寻找该定值发生的所有时点，并以该定值为框架构成时点数列，然后建立模型预测该定值所发生的时点。第17页，共88页。18（4）灰色预测模型）灰色预测模型 为了弱化原始时间序列的随机性，在建立灰色预测模型之前，需先对原始时间序列进行数据处理，经过数据处理

9、后的时间序列即称为生成列生成列。灰色系统常用的数据处理方式有累加累加和累减累减两种。累加是将原始序列通过累加得到生成列。累加的规则累加的规则:将原始序列的第一个数据作为生成列的第一个数据，将原始序列的第二个数据加到原始序列的第一个数据上，其和作为生成列的第二个数据，将原始序列的第三个数据加到生成列的第二个数据上，其和作为生成列的第三个数据，按此规则进行下去，便可得到生成列。第18页，共88页。19（4）灰色预测模型）灰色预测模型记原始时间序列为：nXXXXX11111,.3,2,1 nXXXXX00000,.3,2,1生成列为：上标1表示一次累加，同理，可作m次累加：kimmiXkX11第19

10、页，共88页。20（4）灰色预测模型）灰色预测模型 对非负数据，累加次数越多则随机性弱化越多，累加次数足够大后，可认为时间序列已由随机序列变为非随机序列。一般随机序列的多次累加序列，大多可用指数曲线逼近。累减将原始序列前后两个数据相减得到累减生成列，累减是累加的逆运算，累减可将累加生成 列还原为非生成列，在建模中获得增量信息。一次累减的公式为：1001kXkXkX第20页，共88页。21（4）灰色预测模型）灰色预测模型 关联度关联度 关联度分析是分析系统中各因素关联程度的方法，在计算关联度之前需先计算关联系数。关联系数关联系数 设 nXXXkX0000,.,2,1 nXXXkX0000,.,2

11、,1则关联系数定义为：kXkXkXkXkXkXkXkXk00000000maxmaxmaxmaxminmin)(第21页，共88页。22（4）灰色预测模型）灰色预测模型式中：0X kXkX00为第k个点 和 0X的绝对误差；kXkX00minmin kXkX00maxmax为两级最小差；为两级最大差；称为分辨率，00.950.800.700.70 C0.350.50Y”的蕴含式；其中，的蕴含式；其中，X I，Y I，XY=，即表示满足，即表示满足X中中条件的记录也一定满足条件的记录也一定满足Y。关联规则。关联规则X=Y在交易数据库中在交易数据库中成立，具有支持度成立，具有支持度s和具有置信度和

12、具有置信度c。第42页，共88页。436.3.1 关联规则的概念及分类关联规则的概念及分类 交易数据集D中具有支持度s，即D中至少有s%的事务包含XY，描述为：support(X=Y)=P(XY)交易数据集D中具有置信度c，即D中包含X的事务至少有c%同时也包含Y，描述为：confidence(X=Y)=P(Y|X)通常称满足最小支持度和最小置信度的关联规则称为强关强关联规则联规则（strong）。一般将最小支持度记为minsup，将最小置信度记为minconf。第43页，共88页。446.3.1 关联规则的概念及分类关联规则的概念及分类 在交易数据库D中找出具有用户给定的最小支持度和最小置信

13、度的关联规则可以分解为两个子问题：1）找出存在于事务数据库中所有大项集。If 项集X的支持度support(X)minsup then X称为大项集（large item set），满足最小支持度的项集也称为频繁项集（frequent itemset）。2）利用大项集生成关联规则，对每一大项集X，若YX，Y=，并且support(Y)/support(X)minconf。第44页，共88页。456.3.1 关联规则的概念及分类关联规则的概念及分类 为了发现出有意义的关联规则，必需给定两个阈值，即最小支持度和最小置信度。最小支持度是用户规定的关联规则必需满足的最小支持度，它表示一组物品集在统计意

14、义上的需满足的最低程度，即衡量关联规则在整个数据集中的统计重要性。最小置信度是用户规定的关联规则必需满足的最小可信度，它反映了关联规则的最低可靠度，即衡量关联规则的可信程度。关联分析可用于销售配货、商品陈列设计、产品目录设计、产品定价和促销等，也可以使我们从客户的购买模式中推知他们的嗜好。第45页，共88页。466.3.1 关联规则的概念及分类关联规则的概念及分类 发现关联规则通常要经过以下三个步骤：1）连接数据，作数据准备；2）给定最小支持度和最小可信度，利用数据挖掘工具提供的算法发现关联规则；3）可视化显示、理解、评估关联规则。第46页，共88页。476.3.1 关联规则的概念及分类关联规

15、则的概念及分类 关联规则的优缺点：优点：它可以产生清晰有用的结果；它支持间接数据挖掘；可以处理变长的数据；它的计算的消耗量是可以预见的。缺点：当问题变大时，计算量增长得厉害；难以决定正确的数据；容易忽略离群数据。第47页，共88页。486.3.1 关联规则的概念及分类关联规则的概念及分类（2）关联规则的分类）关联规则的分类表6.8 关联规则的分类分类标准类 别规则中所处理的值布尔关联规则与量化关联规则规则中所涉及的数据维单维关联规则与多维关联规则规则中所涉及的抽象层单层关联规则与多层关联规则规则中的扩充最大的模式与频繁闭项集关联特性分类分析与相关分析第48页，共88页。496.3.2 简单形式

16、的关联规则算法简单形式的关联规则算法 简单形式的关联规则算法（单维、单层和布尔关联规则）主要是经典频集方法（基于Apriori的频集方法）。（1）简单形式的关联规则的核心算法）简单形式的关联规则的核心算法 是一个两阶段频集思想的方法。关联规则算法的设计可以分解为两个子问题：1）找到所有支持度大于最小支持度的项集，即频集。找到所有支持度大于最小支持度的项集，即频集。由k个数据频集称为k项频集项频集，找出所有的频集由Apriori算法实现。Apriori性质：频繁项集的所有非空子集都必须也是频繁的。性质：频繁项集的所有非空子集都必须也是频繁的。第49页，共88页。506.3.2 简单形式的关联规则

17、算法简单形式的关联规则算法2）使用第）使用第1步找到的频集产生期望的规则。步找到的频集产生期望的规则。为了生成所有频集，使用递推的方法：首先产生频繁1项集L1，然后产生频繁2项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在k次循环中，过程先产生候选k项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)连接来产生的。Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素须在交易数据库中进行验证来决定是否加入Lk，这里的验证过程是算法性能的一个瓶颈。第50页，共88页。516.3.2 简单形式的关联规则算法简单形式

18、的关联规则算法Apriori算法的核心思想算法的核心思想L1=large 1-itemsets;/发现1项频集for(k=2;Lk-1=;k+)do beginCk=apriori-gen(Lk-1,minsup);/根据k-1项频集产生新的k项候选集for all transactions tD;/遍历数据库确定每个候选集的支持频度Ct=subset(Ck,t);/事务t中包含的候选集for all candidates c Ct doc.count+;Lk=cCk|c.countminsupReturn L=;/求所有频繁项集Lk的和kkL第51页，共88页。526.3.2 简单形式的关联

19、规则算法简单形式的关联规则算法 apriori-gen函数以Lk-1作为输入参数，返回所有大k项集的集合Lk，具体实现如下：第一步：联合，将两个项连接在一起Procedure apriori-gen(Lk-1,minsup)insert into Ckselect p.item1,p.item2,p.item(k-1),q.item(k-1)from Lk-1p,Lk-1qwhere p.item1=q.item1,p.item(k-2)=q.item(k-2),p.item(k-1)购买(X,”打印机”)第58页，共88页。596.3.3 多层和多维关联规则的挖掘多层和多维关联规则的挖掘 在

20、挖掘维间关联规则和混合关联规则的时候，还要考虑不同的字段种类：种类型和数值型。对于种类型的字段，原先的算法都可以处理。对于数值型的字段可以采用以下几种方法进行处理：1）数值字段被分成一些预定义的层次结构。这些区间都是用户预先定义的，得出的规则叫做静态数量关联规则。2）数值字段根据数据的分布分成了一些布尔字段。每个布尔字段都表示一个数值字段的区间，属于其中则为1，反之为0。这种分法是动态的，得出的规则叫做布尔数量关联规则。第59页，共88页。606.3.3 多层和多维关联规则的挖掘多层和多维关联规则的挖掘3）数值字段被分成一些能体现它含义的区间。它考虑了数据之间的距离的因素，得出的规则叫做基于距

21、离的关联规则。4）直接用数值字段中的原始数据进行分析。使用一些统计的方法对数值字段的值进行分析，并且结合多层关联规则的概念，在多个层次之间进行比较从而得出一些有用的规则。得出的关联规则叫做多层数量关联规则。第60页，共88页。616.3.3 多层和多维关联规则的挖掘多层和多维关联规则的挖掘（3）关联规则价值衡量的方法）关联规则价值衡量的方法 系统客观的层面和用户主观的层面。1）系统客观层面（支持度、置信度、兴趣度、收集强度）：使用“支持度和信任度”框架可能会产生一些不正确的规则。只凭支持度和信任度阈值未必总能找出符合实际的规则。2）用户主观层面：只有用户才能决定规则的有效性、可行性。所以，应该

22、将用户的需求和系统更加紧密地结合起来。可以采用基于约束的数据挖掘方法。具体约束的内容有：数据约束、限定数据挖掘的维和层次、规则约束。第61页，共88页。626.3.4 货篮子分析存在的问题货篮子分析存在的问题（1）即使没有支持度度量统计重要性，我们一样可以采用一种直接量度来度量产品关联的统计重要性。（2）如果只考虑销售额，我们也可以定义一种金额支持度作为量度，这样的话，我们可以忽略那些销售额相对较小的关联关系，通过这种方式，我们可以发现那些出现次数稀少，但是却包含有大金额的产品。第62页，共88页。636.3.5 关联分析的其他算法关联分析的其他算法（1）发现关联分析的更好方法）发现关联分析的

23、更好方法 共同发生的概率与随机期望的值不同时，表达式“如果顾客购买了A，也可能购买B，x%的概率”的关联才最有意义。相关性结构着眼于事务数据中统计相关的数据项之间的关联，即只考虑同时发生的百分比与随机发生的百分比有显著不同的数据项。例如：面包和牛奶；可口可乐与百事可乐 期望同时发生的概率-实际同时发生的概率2/期望同时发生的概率第63页，共88页。646.3.5 关联分析的其他算法关联分析的其他算法（2）统计相关以外的信息）统计相关以外的信息1）量化相关性的一个方法就是考虑影响度，即实际或观测到的共同发生的概率被期望同时发生的概率相除的比率。影响度影响度=实际同时发生的概率实际同时发生的概率/

24、期望同时发生的概率期望同时发生的概率 如果产品相互独立，影响度近似为1，如果产品相关，则不为0。例：影响度(可口可乐+百事可乐)=0.01/25=0.0004，影响程度明显不为0，表示产品非常相关。影响度(面包+牛奶)=12.1/12=1.008，影响度十分接近1，表明产品相互独立。第64页，共88页。656.3.5 关联分析的其他算法关联分析的其他算法 2）较为直观的计量是事件A对事件B的lift值。Lift(事件事件A对事件对事件B)=(实际实际A,B同时出现的概率期望同时出现的概率期望A,B同同时出现的概率时出现的概率)/A出现的概率出现的概率 Lift是-1,1区间内的数值，当事件相互

25、独立时接近于0，事件正相关时值为正（彼此吸引），负相关时值为负（相互排斥）。例：Lift(可口可乐对百事可乐)=0.001-0.25/0.50=-0.498 这一负值意味着两种产品相互排斥。第65页，共88页。666.3.5 关联分析的其他算法关联分析的其他算法（3）理解关联）理解关联 为了采取更为精确的营销活动，应该找出为什么一些产品同时出现的概率比随机发生的更大（或更小）。混合购买倾斜法例如：橙汁和苏打水/全麦面包和土豆片 可口可乐和百事可乐/人口统计信息 婴儿食品/补钙食品第66页，共88页。676.3.5 关联分析的其他算法关联分析的其他算法（4）有效可行的市场篮子分析）有效可行的市场

26、篮子分析 1）考虑“如果顾客购买产品A，则有x%的可能购买产品B”必须谨慎。应将搜索限制在那些不同于随机发生的关联上，因为这些关联最有可能导致可行的营销决策。2）不能鲁莽地舍去支持度较低的关联。3）一旦发现有显著非随机关联的产品集合，必须进一步分析是什么导致非随机关联。第67页，共88页。686.3.6 挖掘序列模式挖掘序列模式（1）序列模式的概念及定义）序列模式的概念及定义 序列模式定义：序列模式定义：给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值。序列模式挖掘序列模式挖掘就是找出所有的频繁子序列，即该子序

27、列在序列集中的出现频率不低于用户指定的最小支持度阈值。序列模式的元素也可以不只是一个元素，它也可以是一个项集。内部元素不分排列顺序。第68页，共88页。696.3.6 挖掘序列模式挖掘序列模式 假定项集中的项由一些连续整数代替，即项集i=i1i2,im，ij（1jm）是一个项。序列s记为s(s1s2sn)，其中sj（1jn）代表的是一个项集（也称序列s的元素）。两个序列a=(a1,a2,an)和b=(b1,b2,bn)，如果存在整数i1i2,in且a1包含于bi1，a2包含于bi2，an包含于bin，即a1bi1，a2 bi2，an bin，则称序列a包含于序列b，也称序列a为序列b的子序列，

28、又称序列b包含序列a，记为a b。在一个序列集中如果序列s不包含于任何其他序列中，则序列s为最大的（maximal）。第69页，共88页。706.3.6 挖掘序列模式挖掘序列模式 序列是不同项目集的有序排列，序列s可以表示为s(s1s2sn)，sj（1jn）为项目集，也称为序列s的元素（element）。序列的元素可以表示为(x1x2xm)，xk（1km）为不同的项目。如果一个序列只有一个项目，则括号可以省略。一个序列包含的所有项目的个数称为序列的长度序列的长度。长度为l的序列记为l-序列。序列a在序列数据库S中的支持数为序列数据库S中包含a序列的序列个数，记为Support(a)，给定支持度

29、阈值，如果序列a在序列数据库中的支持数不低于，则称序列a为序列模式序列模式。第70页，共88页。716.3.6 挖掘序列模式挖掘序列模式 例6.6：设序列数据库如下所示，并设用户指定的最小支持度min-support=2。Sequence_idSequence10203040序列序列是序列是序列的子序列的子序列序列序列是长度为是长度为3的序列模式的序列模式第71页，共88页。726.3.6 挖掘序列模式挖掘序列模式 问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式。系统规定：由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部

30、的不同项目按照字典顺序排列。一个客户所有的事务可以综合地看成是一个序列，每一个事务都由相应的一个项集来表示。事务按交易时间排列就成了一个序列。我们称这样的序列为客户序列（customer sequence）。通常讲一个客户的交易按交易时间排序成T1,T2,Tn。Ti中的项集定义成itemset(Ti)。这样，这个客户的客户序列就成了这样的一个序列：。第72页，共88页。736.3.6 挖掘序列模式挖掘序列模式 如果一个序列s包含于一个客户序列中，则我们称该客户支持（support）序列s。一个具体序列的支持（support）定义为那一部分支持该序列的客户总数。给定一个客户交易组成的数据库D，挖

31、掘序列模式的问题就是在那些具有客户指定最小支持度（minimum support）的序列中找出最大序列。而每个这样的最大序列就代表了一个序列模式（sequence pattern）。第73页，共88页。746.3.6 挖掘序列模式挖掘序列模式 实现算法可以分五个具体阶段来找出所有的序列模式，分别是排序阶段、大项集阶段、转换阶段、序列阶段以及最大值阶段。序列模式分析规则挖掘的重点在于分析数据间的前后（因果）关系，可以发现客户潜在的购物模式，规则是“先购买了商品X的顾客后购买产品Y”，置信度和支持度由决策者输入。序列模式挖掘是基于时间或者其他序列的经常发生的模式。应用领域：客户购买行为模式预测、W

32、eb访问模式预测、疾病诊断、自然灾害诊断、DNA序列分析。第74页，共88页。756.3.6 挖掘序列模式挖掘序列模式 序列模式挖掘的很多参数对挖掘的结果有很大影响。1）时间序列T的持续时间，即这个时间序列的有效时间或者是用户选择的一个时间段。2）时间折叠窗口W。在一段时间内发生的几件事件可以被看作是同时发生的。3）时间间隔int，这个参数表示发现的模式的时间间隔。int=0 min_inervalintmax_interval int=c第75页，共88页。766.3.6 挖掘序列模式挖掘序列模式（2）序列模式挖掘的主要算法）序列模式挖掘的主要算法GSP算法：算法：类似于Apriori算法。

33、PrefixSpan算法：算法：采用分而治之的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘。第76页，共88页。776.3.6 挖掘序列模式挖掘序列模式 上述算法存在的主要问题：缺少时间限制缺少时间限制：用户可能需要指定序列模式的相邻元素之间的时间间隔。例如，一个序列模式可能会发现客户在购买了物品A后的第三年购买物品B。我们需要的却是给定时间间隔内用户的购买意向。事务的定义过于严格事务的定义过于严格：一个事务中包含在客户的一次购买行为中所购买的所有物品。可能需要指定一个滑动时间窗口，客户在滑动时间窗口的时间段内的所有的购买行为均作为一个事务。缺少分类层

34、次缺少分类层次：只能在项目的原始级别上进行挖掘。第77页，共88页。786.3.6 挖掘序列模式挖掘序列模式（2）序列模式挖掘的主要算法）序列模式挖掘的主要算法1）GSP算法算法扫描序列数据库，得到长度为l的序列模式L1，作为初始的种子集。扫描长度为i的种子集Li，通过连接操作和剪切操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式的支持数，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集。重复第二步，直到没有新的序列模式或新的候选序列模式产生为止。L1 C2 L2 C3 L3 C4 L4 第78页，共88页。796.3.6 挖掘序列模式挖掘序列

35、模式 产生候选序列模式主要分为两步：连接阶段：如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，则可以将s1与s2进行连接，即将s2的最后一个项目添加到s1中。剪切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除。第79页，共88页。806.3.6 挖掘序列模式挖掘序列模式 例：下图演示了如何从长度为3的序列模式产生长度为4的候选序列模式。Sequential patternsWith length 3Candidate 4-SequencesAfter JoinAfter Pruning第80页，共88

36、页。816.3.6 挖掘序列模式挖掘序列模式 候选序列模式的支持度计算：对于给定的候选序列模式集合C，扫描序列数据库，对于其中的每一条序列d，找出集合C中被d所包含的所有候选序列模式，并增加其支持度计数。GSP算法存在的主要问题：1）如果序列数据库的规模较大，则有可能会产生大量的候选序列模式；2）需要对序列数据库进行循环扫描；3）对于序列模式的长度比较长的情况，由于其对应的短的序列模式规模太大，本算法很难处理。第81页，共88页。826.3.6 挖掘序列模式挖掘序列模式2）PrefixSpan算法（基于前缀投影的序列模式挖掘算法）算法（基于前缀投影的序列模式挖掘算法）相关定义如下：前缀。设每个

37、元素中的所有项目按照字典序排列。给定序列=(a1,a2,an)，(mn)，如果21,maaa中项目的后面中的项目均在并且,1mmmmmiiaaaaamiaa则称是的前缀。第82页，共88页。836.3.6 挖掘序列模式挖掘序列模式投影。给定序列和，如果是的子序列，则关于的投影必需满足：是的前缀，是的满足上述条件的最大子序列。后缀。序列关于子序列的投影(nm)，则序列关于子序列的后缀为nmmmaaaa,1第83页，共88页。846.3.6 挖掘序列模式挖掘序列模式算法描述：扫描序列数据库，生成所有长度为l的序列模式。根据长度l的序列模式，生成相应的投影数据库。在相应的投影数据库上重复上述步骤，直

38、到在相应的投影数据库上不能产生长度为l的序列模式为止。投影数据库：设为序列数据库S中的一个序列模式，则的投影数据库为S中所有以为前缀的序列相对于的后缀，记为S|。投影数据库中的支持数：设为序列数据库S中的一个序列模式，序列以为前缀，则在投影数据库S中支持数为S|满足条件 .的序列的个数。第84页，共88页。856.3.6 挖掘序列模式挖掘序列模式 PrefixSpan算法 输入：序列数据库S及最小支持度阈值min_sup 输出：所有的序列模式 方法：调用子程序PrefixSpan()0,S)第85页，共88页。866.3.6 挖掘序列模式挖掘序列模式 子程序PrefixSpan(,L,S|)参

39、数：为一个序列模式；L为序列模式的长度；S|如果为空，则为S，否则为的投影数据库。扫描S|，找到满足下述要求的长度为1的序列模式b：b可以添加到的最后一个元素中并为序列模式 可以作为的最后一个元素并为序列模式对每个生成的序列模式b，将b添加到形成序列模式，并输出对每个,构造的投影数据库S|,并调用子程序PrefixSpan(,L+1,S|)第86页，共88页。876.3.6 挖掘序列模式挖掘序列模式PrefixSpan算法分析：PrefixSpan算法不需要产生候选序列模式，从而大大缩减了检索空间 相对于原始的序列数据库而言，投影数据库的规模不断减小 PrefixSpan算法的主要开销在于投影数据库的构造第87页，共88页。886.3.6 挖掘序列模式挖掘序列模式 PrefixSpan算法的主要改进：逐层投影逐层投影：使用隔层投影代替逐层投影，从而可以有效减小投影数据库的个数 伪投影伪投影：当序列数据库可以直接放入内存时，可以使用伪投影操作代替实际的投影数据库，从而可以有效减少构造投影数据库的开销第88页，共88页。