《数据挖掘基本算法》PPT课件.ppt

《《数据挖掘基本算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据挖掘基本算法》PPT课件.ppt（88页珍藏版）》请在装配图网上搜索。

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

2、法 6.2.2 定量分析预测 6.2.3 预测的结果分析 6.2.4 趋势分析挖掘,6.2.1 预言的基本方法,预言（prediction）是一门掌握对象变化动态的科学，它是对对象变动趋势的预见、分析和判断，也是一种动态分析方法。 预言的目的是对未来未知变量的预测，这种预测是需要时间来验证的，即必须经过一定时间后，才知道预言准确性是多少。 一旦建立了表示数据中固有模式和趋势的模型，那么这个模型就可以成功地用于对未来时间的结果进行预测。,6.2.1 预言的基本方法,预测的基本步骤： （1）确定预测目标，包括预测对象、目的、对象范围； （2）收集分析内部和外部资料； （3）数据的处理及模型的选择；

3、 （4）预测模型的分析、修正； （5）确定预测值。,6.2.1 预言的基本方法,预测方法一般有定性分析预测法和定量预测法。 定性预测包括：集合意见法、用户意见法（对象调查法）、员工意见法、专家评估法、类推法、判断预测和目标分解法等； 定量预测方法包括:情景分析法、时间序列分析法（移动平均，指数平滑，季节系数，DOX-TENKENS法）、因果分析法（线性，回归，非线性模型：含生命周期法，经济计量模型，灰色系统模型，状态转移分析法，模拟法，系统模型）等。,6.2.2 定量分析预测,（1）时间序列分析法 （2）回归预测 （3）非线性预测 （4）灰色预测模型GM(1,1) （5）组合预测,（1）时间序

4、列分析法,时间序列分析法的原始数据要求： 1）在时间上具有连续性； 2）数据之间的可比性； 3）可以采取交叉预测。 时间序列可划为四种变化特征：趋势性（T）、季节性（S）、周期性（C）、不规则性（I）。可以利用散点图识别来变化特征。 时间序列分析法一般有：简单平均、移动平均、加权移动平均、指数平滑、一元线性回归、相关比例推算。,（1）时间序列分析法,时间序列定义从时间序列的角度来看, 每个数据单元可以被抽象为一个二元组( t, o) 。其中：t 为时间变量; o 为数据变量, 反映数据单元的实际意义, 如某种商品的销售金额、股票的价格等。由此，对于时间序列可以给出如下定义： 时间序列R 是一个

5、有限集 ( t1 , o1 ) , ( t2 , o2 ) , , ( tn, on) , 满足ti ti + 1 ( i = 1, 2, , n - 1) 。 由时间序列组成的数据库称为时间序列数据库。针对时间序列数据库的挖掘就是时间序列数据挖掘。时间序列数据挖掘是时间序列数据库中知识挖掘的一个步骤, 它发现时间序列数据中的时态模式或模型。,（1）时间序列分析法,时间序列挖掘的任务 时间序列相似性搜索； 时间序列聚类； 时间序列分类； 时间序列相关规则提取与模式分析； 海量时间序列可视化； 时间序列预测。 典型的应用 股票预测、机电系统诊断、医学诊断、生物信息学、营销指导、运动图像分析、生产

6、过程监测等。,（2）回归预测,一元线性回归（趋势外推）：Y= a0+ a1X 多元回归(因果关系)：Y=a0+a1X1+a2X2+ +anXn 系数用最小二乘法确定系数：a0, a1,an,（3）非线性预测,Y=A+BLOG(X) Y=1/(A+BEXP(-X) Y=1/(A+BX) Y=X/(A+BX) Y=AXB，(A0) Y=AEXP(BX)，(A0) Y=AEXP(B/X) ，(A0) Y=AEXP(BX2)，(A0) 将以上模型进行线性处理再转化为一元回归模型。,（4）灰色预测模型,客观世界，既是物质的世界又是信息的世界。它既包含大量的已知信息，也包含大量的未知信息与非确知信息。 未

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

8、系统和黑色系统之间的一种系统。,（4）灰色预测模型,灰色预测通过鉴别系统因素之间发展趋势的相异程度，即进行关联分析，并对原始数据进行生成处理来寻找系统变动的规律，生成有较强规律性的数据序列，然后建立相应的微分方程模型，从而预测事物未来发展趋势的状况。其用等时距观测到的反应预测对象特征的一系列数量值构造灰色预测模型，预测未来某一时刻的特征量，或达到某一特征量的时间。,（4）灰色预测模型,灰色预测的类型 灰色时间序列预测：用观察到的反映预测对象特征的时间序列来构造灰色预测模型，预测未来某一时刻的特征量，或达到某一特征量的时间。 畸变预测：通过灰色模型预测异常值出现的时刻，预测异常值什么时候出现在特

9、定时区内。 系统预测：通过对系统行为特征指标建立一组相互关联的灰色预测模型，预测系统中众多变量间的相互协调关系的变化。 拓扑预测：将原始数据作曲线，在曲线上按定值寻找该定值发生的所有时点，并以该定值为框架构成时点数列，然后建立模型预测该定值所发生的时点。,（4）灰色预测模型,为了弱化原始时间序列的随机性，在建立灰色预测模型之前，需先对原始时间序列进行数据处理，经过数据处理后的时间序列即称为生成列。 灰色系统常用的数据处理方式有累加和累减两种。 累加是将原始序列通过累加得到生成列。 累加的规则: 将原始序列的第一个数据作为生成列的第一个数据，将原始序列的第二个数据加到原始序列的第一个数据上，其和

10、作为生成列的第二个数据，将原始序列的第三个数据加到生成列的第二个数据上，其和作为生成列的第三个数据，按此规则进行下去，便可得到生成列。,（4）灰色预测模型,记原始时间序列为：,生成列为：,上标1表示一次累加，同理，可作m次累加：,（4）灰色预测模型,对非负数据，累加次数越多则随机性弱化越多，累加次数足够大后，可认为时间序列已由随机序列变为非随机序列。 一般随机序列的多次累加序列，大多可用指数曲线逼近。 累减将原始序列前后两个数据相减得到累减生成列，累减是累加的逆运算，累减可将累加生成 列还原为非生成列，在建模中获得增量信息。 一次累减的公式为：,（4）灰色预测模型,关联度 关联度分析是分析系统

11、中各因素关联程度的方法，在计算关联度之前需先计算关联系数。 关联系数 设,则关联系数定义为：,（4）灰色预测模型,式中：,为第k个点,和,的绝对误差；,为两级最小差；,为两级最大差；,称为分辨率，01，一般取=0.5。 对单位不一，初值不同的序列，在计算相关系数前应首先进行初始化，即将该序列所有数据分别除以第一个数据。,（4）灰色预测模型,关联度,和,的关联度为：,（4）灰色预测模型,例6.5 一个计算关联度的例子 工业、农业、运输业、商业各部门的行为数据如下：,工业,农业,运输业,商业,参考序列分别为X1,X2 ，被比较序列为X3,X4，试求关联度。,（4）灰色预测模型,以X1为参考序列求关

12、联度。 第一步：初始化，即将该序列所有数据分别除以第一个数据。得到：,（4）灰色预测模型,第二步：求序列差,第三步：求两极差,（4）灰色预测模型,第四步：计算关联系数 取=0.5，有：,从而：,（4）灰色预测模型,第五步：求关联度,计算结果表明，运输业和工业的关联程度大于农业、商业和工业的关联程度。 x2为参考序列时，计算类似，这里略去。,（4）灰色预测模型,GM(1,1)模型的建立,设时间序列,有n个观察值，,通过累加生成新序列,则GM(1,1)模型相应的微分方程为：,其中：称为发展灰数；称为内生控制灰数。,（4）灰色预测模型,设 为待估参数向量，,可利用最小二乘法求解。解得：,求解微分方程

13、，即可得预测模型：,（4）灰色预测模型,模型检验 灰色预测检验一般有残差检验、关联度检验和后验差检验。 （1）残差检验,按预测模型计算,并将,累减生成,然后计算原始序列,与,的绝对误差序列及相,对误差序列。,（4）灰色预测模型,（2）关联度检验 根据前面所述关联度的计算方法算出 与原始序列 的关联系数，然后计算出关联度。根据经验，当=0.5时，关联度大于0.6便满意了。,（4）灰色预测模型,（3）后验差检验 a.计算原始序列标准差: b. 计算绝对误差序列的标准差： c. 计算方差比：,（4）灰色预测模型,d. 计算小误差概率：,令:,则：,P 0.95 0.80 0.70 0.70,C 0.

14、35 0.50 0.65 0.65,好 合格 勉强合格 不合格,（5）组合预测,采用不同合理的模型预测后，再进行回归得出组合预测模型。 预测模型选取的原则： 有关研究资料表明，以预测方法应用多少为标准进行从大到小排序是：回归分析、指数平滑、数量经济模型、专家会议、主观概率法、多变量时间序列模型、趋势外推、抽样调查、移动平均、投入产出、相关树、类推法等。 在高层次经济预测方面：数量经济模型、投入产出、回归分析、移动平均。 在低层次方面：专家会议、类推法、移动平均、主观概率法、回归分析、指数平滑。,（5）组合预测,预测的主导方向：定量预测、定性预测和计算机相结合。 预测科学的发展方向：神经网络预测

15、、基于规则的预测系统、专家预测系统、判断预测、组合预测。 模型选择的原则：适用性、数据易采集性、数据时效性、定量与定性相结合。,6.2.3 预测的结果分析,预测的结果分析要考虑到如下的因素: （1）相反的预测结果 （2）胜出裕度：最佳预测结果得分与相反的结果得分之间的差额占最佳预测结果的百分比。 （3）成本收益分析,6.2.4 趋势分析挖掘,趋势（trend）分析挖掘，该方法类似于预测分析挖掘。一个变量Y，表示某一支股票每天的收盘价，可以看作是时间t的函数，即Y=F(t)，这样的函数可以用一个时间序列的图来表示。 分析时间序列数据需要注意以下4个方面： （1）长时间的走向 T （2）周期的走向

16、与周期的变化 C （3）季节性的走向与变化 S （4）不规则的随机走向 I,第六章 数据挖掘基本算法,6.1 分类规则挖掘 6.2 预测分析与趋势分析规则 6.3 数据挖掘的关联算法 6.4 数据挖掘的聚类算法 6.5 数据挖掘的统计分析算法 6.6 数据挖掘的品种优化算法 6.7 数据挖掘的进化算法,6.3 数据挖掘的关联算法,6.3.1 关联规则的概念及分类 6.3.2 简单形式的关联规则算法（单维、单层和布尔关联规则） 6.3.3 多层和多维关联规则的挖掘 6.3.4 货篮子分析存在的问题 6.3.5 关联分析的其他算法 6.3.6 挖掘序列模式*,6.3.1 关联规则的概念及分类,（1

17、）关联规则的概念 关联规则挖掘是寻找数据项中的有趣联系，决定哪些事情将一起发生。 在数据挖掘中，关联规则就是描述这种在一个事务中物品之间同时出现的规律的知识模式。更确切地说，关联规则通过量化的数字描述物品甲的出现与物品乙的出现有多大的影响。 在实际情况下，一种更有用的关联规则是泛化关联规则。 关联规则模式属于描述模式，发现关联规则的算法属于无监督学习的方法。,6.3.1 关联规则的概念及分类,在事务数据库中发现关联规则首先是由R.Agrawal等人提出的，其形式化描述如下： 定义6.2 设I=i1,i2,i3,im是由m个不同的数据项组成的集合，其中的元素称为项（item），项的集合称为项集，

18、包含k个项的项集称为k项集。给定一个事务（交易）D，即交易数据库，其中的每一个事务（交易）T是数据项I的一个子集，即TI，T有一个唯一的标识符TID；当且仅当X T时，称交易T包含项集X；那么关联规则就形如“X=Y”的蕴含式；其中，X I，Y I，XY=，即表示满足X中条件的记录也一定满足Y。关联规则X=Y在交易数据库中成立，具有支持度s和具有置信度c。,6.3.1 关联规则的概念及分类,交易数据集D中具有支持度s，即D中至少有s%的事务包含XY，描述为： support (X=Y)=P(XY) 交易数据集D中具有置信度c，即D中包含X的事务至少有c%同时也包含Y，描述为： confidenc

19、e (X=Y)=P(Y|X) 通常称满足最小支持度和最小置信度的关联规则称为强关联规则（strong）。 一般将最小支持度记为minsup，将最小置信度记为minconf。,6.3.1 关联规则的概念及分类,在交易数据库D中找出具有用户给定的最小支持度和最小置信度的关联规则可以分解为两个子问题： 1）找出存在于事务数据库中所有大项集。If 项集X的支持度support (X) minsup then X称为大项集（large item set），满足最小支持度的项集也称为频繁项集（frequent itemset）。 2）利用大项集生成关联规则，对每一大项集X，若YX，Y=，并且support

20、 (Y)/support (X) minconf。,6.3.1 关联规则的概念及分类,为了发现出有意义的关联规则，必需给定两个阈值，即最小支持度和最小置信度。 最小支持度是用户规定的关联规则必需满足的最小支持度，它表示一组物品集在统计意义上的需满足的最低程度，即衡量关联规则在整个数据集中的统计重要性。 最小置信度是用户规定的关联规则必需满足的最小可信度，它反映了关联规则的最低可靠度，即衡量关联规则的可信程度。 关联分析可用于销售配货、商品陈列设计、产品目录设计、产品定价和促销等，也可以使我们从客户的购买模式中推知他们的嗜好。,6.3.1 关联规则的概念及分类,发现关联规则通常要经过以下三个步骤

21、： 1）连接数据，作数据准备； 2）给定最小支持度和最小可信度，利用数据挖掘工具提供的算法发现关联规则； 3）可视化显示、理解、评估关联规则。,6.3.1 关联规则的概念及分类,关联规则的优缺点： 优点： 它可以产生清晰有用的结果； 它支持间接数据挖掘； 可以处理变长的数据； 它的计算的消耗量是可以预见的。 缺点： 当问题变大时，计算量增长得厉害； 难以决定正确的数据； 容易忽略离群数据。,6.3.1 关联规则的概念及分类,（2）关联规则的分类,表6.8 关联规则的分类,6.3.2 简单形式的关联规则算法,简单形式的关联规则算法（单维、单层和布尔关联规则）主要是经典频集方法（基于Apriori

22、的频集方法）。 （1）简单形式的关联规则的核心算法 是一个两阶段频集思想的方法。 关联规则算法的设计可以分解为两个子问题： 1）找到所有支持度大于最小支持度的项集，即频集。由k个数据频集称为k项频集，找出所有的频集由Apriori算法实现。 Apriori性质：频繁项集的所有非空子集都必须也是频繁的。,6.3.2 简单形式的关联规则算法,2）使用第1步找到的频集产生期望的规则。 为了生成所有频集，使用递推的方法：首先产生频繁1项集L1，然后产生频繁2项集L2，直到有某个r值使得Lr为空，这时算法停止。 这里在k次循环中，过程先产生候选k项集的集合Ck， Ck中的每一个项集是对两个只有一个项不同

23、的属于Lk-1的频集做一个(k-2)连接来产生的。Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。 Ck中的每个元素须在交易数据库中进行验证来决定是否加入Lk ，这里的验证过程是算法性能的一个瓶颈。,6.3.2 简单形式的关联规则算法,Apriori算法的核心思想 L1=large 1-itemsets; /发现1项频集 for (k=2; Lk-1 =;k+) do begin Ck=apriori-gen (Lk-1,minsup); /根据k-1项频集产生新的k项候选集 for all transactions tD; /遍历数据库确定每个候选集的支持频度 Ct=

24、subset(Ck,t); /事务t中包含的候选集 for all candidates c Ct do c.count+; Lk=cCk | c.countminsup Return L= ;/求所有频繁项集Lk的和,6.3.2 简单形式的关联规则算法,apriori-gen函数以Lk-1作为输入参数，返回所有大k项集的集合Lk，具体实现如下： 第一步：联合，将两个项连接在一起 Procedure apriori-gen (Lk-1,minsup) insert into Ck select p.item1,p.item2,p.item(k-1),q.item(k-1) from Lk-1p

25、,Lk-1q where p.item1=q.item1,p.item(k-2)=q.item(k-2), p.item(k-1)q.item(k-1),6.3.2 简单形式的关联规则算法,第二步，剪枝（pruning），如果存在c的(k-1)子序列不包含于Lk-1中，则删除所有项集c Ck。 For all itemsets c Ck do for all (k-1) subsets s of c do if (s Lk-1) then delete from Ck,Apriori算法示例,Database TDB,1st scan,C1,L1,L2,C2,C2,2nd scan,C3,L3

26、,3rd scan,6.3.2 简单形式的关联规则算法,（2）频集算法的几种优化方法 1）基于划分的方法 2）基于hash的方法 3）基于采样的方法 4）减少交易的个数,6.3.2 简单形式的关联规则算法,（3）其他的频集挖掘方法 基于Apriori方法的缺陷及解决办法 1）可能产生大量的候选集FP-growth 2）无法对稀有信息进行分析挖掘高可信度的规则：计算特征、生成候选集、过滤候选集,6.3.3 多层和多维关联规则的挖掘,（1）多层关联规则 多层关联规则的分类：根据规则中涉及的层次，多层关联规则可以分为同层关联规则和层间关联规则。 多层关联规则的挖掘基本上可以沿用“支持度-可信度”的框

27、架。不过在支持度设置的问题上有一些要考虑的问题。 同层关联规则可以采用两种支持度策略： 1）统一的最小支持度。对于不同的层次，都使用同一个最小支持度。 2）递减的最小支持度。每个层次都有不同的最小支持度，较低层次的最小支持度相对较小。同时还可以用上层挖掘得到的信息进行一些过滤工作。 层间关联规则考虑最小支持度的时候，应根据较低层次的最小支持度来定。,6.3.3 多层和多维关联规则的挖掘,（2）多维关联规则 根据是否允许同一个维重复出现，可以细分为维间的关联规则（不允许维重复出现）和混合维关联规则（允许维在规则的左右同时出现）。 例： 年龄(X,”2030”) 购买(X,”笔记本电脑”)=购买(

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

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

30、以采用基于约束的数据挖掘方法。具体约束的内容有：数据约束、 限定数据挖掘的维和层次、规则约束。,6.3.4 货篮子分析存在的问题,（1）即使没有支持度度量统计重要性，我们一样可以采用一种直接量度来度量产品关联的统计重要性。 （2）如果只考虑销售额，我们也可以定义一种金额支持度作为量度，这样的话，我们可以忽略那些销售额相对较小的关联关系，通过这种方式，我们可以发现那些出现次数稀少，但是却包含有大金额的产品。,6.3.5 关联分析的其他算法,（1）发现关联分析的更好方法 共同发生的概率与随机期望的值不同时，表达式“如果顾客购买了A，也可能购买B，x%的概率”的关联才最有意义。 相关性结构着眼于事务

31、数据中统计相关的数据项之间的关联，即只考虑同时发生的百分比与随机发生的百分比有显著不同的数据项。例如：面包和牛奶；可口可乐与百事可乐 期望同时发生的概率-实际同时发生的概率2/期望同时发生的概率,6.3.5 关联分析的其他算法,（2）统计相关以外的信息 1）量化相关性的一个方法就是考虑影响度，即实际或观测到的共同发生的概率被期望同时发生的概率相除的比率。 影响度=实际同时发生的概率/期望同时发生的概率 如果产品相互独立，影响度近似为1，如果产品相关，则不为0。 例： 影响度(可口可乐+百事可乐)=0.01/25=0.0004，影响程度明显不为0，表示产品非常相关。 影响度(面包+牛奶)=12.

32、1/12=1.008，影响度十分接近1，表明产品相互独立。,6.3.5 关联分析的其他算法,2）较为直观的计量是事件A对事件B的lift值。 Lift(事件A对事件B)=(实际A,B同时出现的概率期望A,B同时出现的概率)/A出现的概率 Lift是-1,1区间内的数值，当事件相互独立时接近于0，事件正相关时值为正（彼此吸引），负相关时值为负（相互排斥）。 例： Lift(可口可乐对百事可乐)=0.001-0.25/0.50=-0.498 这一负值意味着两种产品相互排斥。,6.3.5 关联分析的其他算法,（3）理解关联 为了采取更为精确的营销活动，应该找出为什么一些产品同时出现的概率比随机发生的

33、更大（或更小）。 混合购买倾斜法 例如： 橙汁和苏打水/全麦面包和土豆片 可口可乐和百事可乐/人口统计信息 婴儿食品/补钙食品,6.3.5 关联分析的其他算法,（4）有效可行的市场篮子分析 1）考虑“如果顾客购买产品A，则有x%的可能购买产品B”必须谨慎。应将搜索限制在那些不同于随机发生的关联上，因为这些关联最有可能导致可行的营销决策。 2）不能鲁莽地舍去支持度较低的关联。 3）一旦发现有显著非随机关联的产品集合，必须进一步分析是什么导致非随机关联。,6.3.6 挖掘序列模式,（1）序列模式的概念及定义 序列模式定义：给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个

34、元素由不同项目组成，同时给定一个用户指定的最小支持度阈值。 序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值。 序列模式的元素也可以不只是一个元素，它也可以是一个项集。 内部元素不分排列顺序。,6.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，即a1bi

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

36、包含a序列的序列个数，记为Support(a)，给定支持度阈值，如果序列a在序列数据库中的支持数不低于，则称序列a为序列模式。,6.3.6 挖掘序列模式,例6.6：设序列数据库如下所示，并设用户指定的最小支持度min-support = 2。,序列是序列的子序列 序列是长度为3的序列模式,6.3.6 挖掘序列模式,问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式。 系统规定：由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字典顺序排列。 一个客户所有的事务可以综合地看成是一个序列，每一个事务都由相应的一个项集

37、来表示。事务按交易时间排列就成了一个序列。我们称这样的序列为客户序列（customer sequence）。通常讲一个客户的交易按交易时间排序成T1,T2,Tn。 Ti中的项集定义成itemset(Ti)。这样，这个客户的客户序列就成了这样的一个序列：。,6.3.6 挖掘序列模式,如果一个序列s包含于一个客户序列中，则我们称该客户支持（support）序列s。 一个具体序列的支持（support）定义为那一部分支持该序列的客户总数。 给定一个客户交易组成的数据库D，挖掘序列模式的问题就是在那些具有客户指定最小支持度（minimum support）的序列中找出最大序列。而每个这样的最大序列就代

38、表了一个序列模式（sequence pattern）。,6.3.6 挖掘序列模式,实现算法可以分五个具体阶段来找出所有的序列模式，分别是排序阶段、大项集阶段、转换阶段、序列阶段以及最大值阶段。 序列模式分析规则挖掘的重点在于分析数据间的前后（因果）关系，可以发现客户潜在的购物模式，规则是“先购买了商品X的顾客后购买产品Y”，置信度和支持度由决策者输入。 序列模式挖掘是基于时间或者其他序列的经常发生的模式。 应用领域：客户购买行为模式预测、Web访问模式预测、疾病诊断、自然灾害诊断、DNA序列分析。,6.3.6 挖掘序列模式,序列模式挖掘的很多参数对挖掘的结果有很大影响。 1）时间序列T的持续时

39、间，即这个时间序列的有效时间或者是用户选择的一个时间段。 2）时间折叠窗口W。在一段时间内发生的几件事件可以被看作是同时发生的。 3）时间间隔int，这个参数表示发现的模式的时间间隔。 int=0 min_inervalintmax_interval int=c,6.3.6 挖掘序列模式,（2）序列模式挖掘的主要算法 GSP算法：类似于Apriori算法。 PrefixSpan算法：采用分而治之的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘。,6.3.6 挖掘序列模式,上述算法存在的主要问题： 缺少时间限制：用户可能需要指定序列模式的相邻元素之间的时间

40、间隔。例如，一个序列模式可能会发现客户在购买了物品A后的第三年购买物品B。我们需要的却是给定时间间隔内用户的购买意向。 事务的定义过于严格：一个事务中包含在客户的一次购买行为中所购买的所有物品。可能需要指定一个滑动时间窗口，客户在滑动时间窗口的时间段内的所有的购买行为均作为一个事务。 缺少分类层次：只能在项目的原始级别上进行挖掘。,6.3.6 挖掘序列模式,（2）序列模式挖掘的主要算法 1）GSP算法 扫描序列数据库，得到长度为l的序列模式L1，作为初始的种子集。 扫描长度为i的种子集Li ，通过连接操作和剪切操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式

41、的支持数，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集。 重复第二步，直到没有新的序列模式或新的候选序列模式产生为止。,L1 C2 L2 C3 L3 C4 L4 ,6.3.6 挖掘序列模式,产生候选序列模式主要分为两步： 连接阶段：如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，则可以将s1与s2进行连接，即将s2的最后一个项目添加到s1中。 剪切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除。,6.3.6 挖掘序列模式,例：下图演示了如何从长度为3的序列模式产生长度为4的候选序列模

42、式。,6.3.6 挖掘序列模式,候选序列模式的支持度计算：对于给定的候选序列模式集合C，扫描序列数据库，对于其中的每一条序列d，找出集合C中被d所包含的所有候选序列模式，并增加其支持度计数。 GSP算法存在的主要问题： 1）如果序列数据库的规模较大，则有可能会产生大量的候选序列模式； 2）需要对序列数据库进行循环扫描； 3）对于序列模式的长度比较长的情况，由于其对应的短的序列模式规模太大，本算法很难处理。,6.3.6 挖掘序列模式,2）PrefixSpan算法（基于前缀投影的序列模式挖掘算法） 相关定义如下： 前缀。设每个元素中的所有项目按照字典序排列。给定序列 =(a1,a2,an) ， (

43、mn)，如果,则称是的前缀。,6.3.6 挖掘序列模式,投影。给定序列和，如果是的子序列，则关于的投影必需满足： 是的前缀， 是的满足上述条件的最大子序列。 后缀。序列关于子序列的投影(nm)，则序列关于子序列的后缀为,6.3.6 挖掘序列模式,算法描述： 扫描序列数据库，生成所有长度为l的序列模式。 根据长度l的序列模式，生成相应的投影数据库。 在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生长度为l的序列模式为止。 投影数据库：设为序列数据库S中的一个序列模式，则的投影数据库为S中所有以为前缀的序列相对于的后缀，记为S| 。 投影数据库中的支持数：设为序列数据库S中的一个

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