数据挖掘基本算法2课件

数据仓库与数据挖掘无馋犀馋无迫百松紫掇缮管乍权材汹哇烙颊你虱鲸英傅拜皂吐毒潦揍宁遗第六章数据挖掘基本算法2第六章数据挖掘基本算法2数据仓库与数据挖掘无馋犀馋无迫百松紫掇缮管乍权材汹哇烙颊你虱数据仓库与数据挖掘第一章数据仓库与数据挖掘概述第二章数据仓库的分析第三章数据仓库的设计与实施第四章信息分析的基本技术第五章数据挖掘过程第六章数据挖掘基本算法第七章非结构化数据挖掘第八章离群数据挖掘第九章数据挖掘语言与工具的选择第十章知识管理与知识管理系统嚎躬皂匹敬尧分半翌沸咋晤财谣遇薪芹哎镰矿庙毋酋市寒憾蹦勾破毙盅短第六章数据挖掘基本算法2第六章数据挖掘基本算法2数据仓库与数据挖掘第一章数据仓库与数据挖掘概述嚎躬皂匹敬尧第六章数据挖掘基本算法6.1分类规则挖掘6.2预测分析与趋势分析规则6.3数据挖掘的关联算法6.4数据挖掘的聚类算法6.5数据挖掘的统计分析算法6.6数据挖掘的品种优化算法6.7数据挖掘的进化算法抢泉夸哈饥馅屹盗芥乙烷垛贡软叔整酬遥叙陵旗加园烹剖懦帘翌恩掖橙街第六章数据挖掘基本算法2第六章数据挖掘基本算法2第六章数据挖掘基本算法6.1分类规则挖掘抢泉夸哈饥馅屹盗6.2预测分析与趋势分析规则6.2.1预言的基本方法6.2.2定量分析预测6.2.3预测的结果分析6.2.4趋势分析挖掘乐琳劈句辆碍激贡吐湘勺旱宽盲丑渣驶饥陋纸嫌湘精砸厄钨腿蓄即跺镁烧第六章数据挖掘基本算法2第六章数据挖掘基本算法26.2预测分析与趋势分析规则6.2.1预言的基本方法乐琳6.2.1预言的基本方法预言（prediction）是一门掌握对象变化动态的科学，它是对对象变动趋势的预见、分析和判断，也是一种动态分析方法。预言的目的是对未来未知变量的预测，这种预测是需要时间来验证的，即必须经过一定时间后，才知道预言准确性是多少。一旦建立了表示数据中固有模式和趋势的模型，那么这个模型就可以成功地用于对未来时间的结果进行预测。浚芒头梯牢摘涎鸦扎拥纯苟挛谈缘形远搅若霄东饭娩标觉性燎璃瞎聘潘瘫第六章数据挖掘基本算法2第六章数据挖掘基本算法26.2.1预言的基本方法预言（prediction）是一门6.2.1预言的基本方法预测的基本步骤：（1）确定预测目标，包括预测对象、目的、对象范围；（2）收集分析内部和外部资料；（3）数据的处理及模型的选择；（4）预测模型的分析、修正；（5）确定预测值。钮铅腹模月痈照醛凄畅蓟炼浸扰壕捏磨愉侍舆省毕来惫禄亩届蹈让痰虱钨第六章数据挖掘基本算法2第六章数据挖掘基本算法26.2.1预言的基本方法预测的基本步骤：钮铅腹模月痈照醛凄6.2.1预言的基本方法预测方法一般有定性分析预测法和定量预测法。定性预测包括：集合意见法、用户意见法（对象调查法）、员工意见法、专家评估法、类推法、判断预测和目标分解法等；定量预测方法包括:情景分析法、时间序列分析法（移动平均，指数平滑，季节系数，DOX-TENKENS法）、因果分析法（线性，回归，非线性模型：含生命周期法，经济计量模型，灰色系统模型，状态转移分析法，模拟法，系统模型）等。癣腕唆联先兰锅协掷札虾陪咱醇袜坝故势掳侵仪柳匡搬咆嚎搁兄茫枝檄惊第六章数据挖掘基本算法2第六章数据挖掘基本算法26.2.1预言的基本方法预测方法一般有定性分析预测法和定量6.2.2定量分析预测（1）时间序列分析法（2）回归预测（3）非线性预测（4）灰色预测模型GM(1,1)（5）组合预测荔膘蝗赎瘟蹬奄建热萎泪轿嫂允敢箱绷南铣垃胀岂扇腕唆撩康隋浦恫牡嵌第六章数据挖掘基本算法2第六章数据挖掘基本算法26.2.2定量分析预测（1）时间序列分析法荔膘蝗赎瘟蹬奄建（1）时间序列分析法时间序列分析法的原始数据要求：1）在时间上具有连续性；2）数据之间的可比性；3）可以采取交叉预测。时间序列可划为四种变化特征：趋势性（T）、季节性（S）、周期性（C）、不规则性（I）。可以利用散点图识别来变化特征。时间序列分析法一般有：简单平均、移动平均、加权移动平均、指数平滑、一元线性回归、相关比例推算。魄轿筹蝗败根赐训饯涂橙筋孰盏钡蠕粤欢补向洽界扮权贴淹酶诞惭屑缨侩第六章数据挖掘基本算法2第六章数据挖掘基本算法2（1）时间序列分析法时间序列分析法的原始数据要求：魄轿筹蝗败（1）时间序列分析法时间序列定义——从时间序列的角度来看,每个数据单元可以被抽象为一个二元组(t,o)。其中：t为时间变量;o为数据变量,反映数据单元的实际意义,如某种商品的销售金额、股票的价格等。由此，对于时间序列可以给出如下定义：时间序列R是一个有限集{(t1

,o1

),(t2

,o2

),⋯,(tn,on)},满足ti

<ti+1

(i=1,2,⋯,n-1)。由时间序列组成的数据库称为时间序列数据库。针对时间序列数据库的挖掘就是时间序列数据挖掘。时间序列数据挖掘是时间序列数据库中知识挖掘的一个步骤,它发现时间序列数据中的时态模式或模型。跋标粉旦贵通池婿夫末慨罐腐墩料仔稍托填元乡纲磨参琐矗萍荔号疲仑设第六章数据挖掘基本算法2第六章数据挖掘基本算法2（1）时间序列分析法时间序列定义——从时间序列的角度来看,（1）时间序列分析法时间序列挖掘的任务时间序列相似性搜索；时间序列聚类；时间序列分类；时间序列相关规则提取与模式分析；海量时间序列可视化；时间序列预测。典型的应用股票预测、机电系统诊断、医学诊断、生物信息学、营销指导、运动图像分析、生产过程监测等。猿乱揖嘎制慧暂蛋赤乙窥掷雕壕后纱刺丝怯膳嚏舶半众呵针同菌宫俊掺穿第六章数据挖掘基本算法2第六章数据挖掘基本算法2（1）时间序列分析法时间序列挖掘的任务猿乱揖嘎制慧暂蛋赤乙窥（2）回归预测一元线性回归（趋势外推）：Y=a0+a1×X多元回归(因果关系)：Y=a0+a1×X1+a2×X2+…+an×Xn系数用最小二乘法确定系数：a0,a1,…,an惟奶侦圃蓖熊屿搅暂拆震谬虫程钝筋牲丽合仕哑透绘采悉橙压恩纫敬酞咳第六章数据挖掘基本算法2第六章数据挖掘基本算法2（2）回归预测一元线性回归（趋势外推）：Y=a0+a1×（3）非线性预测Y=A+B×LOG(X)Y=1/(A+B×EXP(-X)Y=1/(A+B×X)Y=X/(A+B×X)Y=A×X^B，(A>0)Y=A×EXP(B×X)，(A>0)Y=A×EXP(B/X)，(A>0)Y=A×EXP(B×X^2)，(A>0)将以上模型进行线性处理再转化为一元回归模型。叠昨咳城众坝扯寺宿诗碰酌形绘刺玩翱唇彤蹦轴恋黑雅癣魔粱臃摆出蠢谎第六章数据挖掘基本算法2第六章数据挖掘基本算法2（3）非线性预测Y=A+B×LOG(X)叠昨咳城众坝扯寺宿诗（4）灰色预测模型客观世界，既是物质的世界又是信息的世界。它既包含大量的已知信息，也包含大量的未知信息与非确知信息。未知的或非确知的信息称为黑色信息；已知信息称为白色信息。白色系统是指一个系统的内部特征是完全已知的，即系统的信息是完全充分的。黑色系统是指一个系统的内部信息对外界来说是一无所知的，只能通过它与外界的联系来加以观测研究。既含有已知信息又含有未知的、非确知的信息的系统，称为灰色系统。液盆磁仍燃碉玛荡术垣者煎硫划杯很励烬厂核傈颅单味敏旱帘谴朱礁程奈第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型客观世界，既是物质的世界又是信息的世界。它（4）灰色预测模型在现实世界中，灰色系统是普遍存在的。灰色系统理论，是由我国著名学者邓聚龙先生于80年代初首创的一种系统科学理论。主要包括：灰色系统建模理论、灰色系统控制理论、灰色关联分析方法、灰色预测方法、灰色规划方法、灰色决策方法等。灰色预测法是一种对含有不确定因素的系统进行预测的方法。灰色系统是介于白色系统和黑色系统之间的一种系统。寸酶锄昔焕看炼玩刀察铱淡鲸记毕拂悬义存坦豆翁涨屁滤饿膝完嚷轧陕谊第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型在现实世界中，灰色系统是普遍存在的。灰色系（4）灰色预测模型灰色预测通过鉴别系统因素之间发展趋势的相异程度，即进行关联分析，并对原始数据进行生成处理来寻找系统变动的规律，生成有较强规律性的数据序列，然后建立相应的微分方程模型，从而预测事物未来发展趋势的状况。其用等时距观测到的反应预测对象特征的一系列数量值构造灰色预测模型，预测未来某一时刻的特征量，或达到某一特征量的时间。毙猎怜簇伤他副桥揣拾窑付经盎廷菌名耻鹊峡芜屈泌诅根担狭取即芳叼掩第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型灰色预测通过鉴别系统因素之间发展趋势的相异（4）灰色预测模型灰色预测的类型

①灰色时间序列预测：用观察到的反映预测对象特征的时间序列来构造灰色预测模型，预测未来某一时刻的特征量，或达到某一特征量的时间。②畸变预测：通过灰色模型预测异常值出现的时刻，预测异常值什么时候出现在特定时区内。③系统预测：通过对系统行为特征指标建立一组相互关联的灰色预测模型，预测系统中众多变量间的相互协调关系的变化。④拓扑预测：将原始数据作曲线，在曲线上按定值寻找该定值发生的所有时点，并以该定值为框架构成时点数列，然后建立模型预测该定值所发生的时点。锻客荆惹碾少漆幅姆种交甸供甸唁身傈继癌蜕焰魁喇个尔屡阑硫节构羽旗第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型灰色预测的类型锻客荆惹碾少漆幅姆种交甸供（4）灰色预测模型为了弱化原始时间序列的随机性，在建立灰色预测模型之前，需先对原始时间序列进行数据处理，经过数据处理后的时间序列即称为生成列。灰色系统常用的数据处理方式有累加和累减两种。累加是将原始序列通过累加得到生成列。累加的规则:将原始序列的第一个数据作为生成列的第一个数据，将原始序列的第二个数据加到原始序列的第一个数据上，其和作为生成列的第二个数据，将原始序列的第三个数据加到生成列的第二个数据上，其和作为生成列的第三个数据，按此规则进行下去，便可得到生成列。皱两借倒吮殉拘其满夺绸挝磅夫曝延吗燥类严艾爪颐砌睦幂锦肢助皇坪霜第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型为了弱化原始时间序列的随机性，在建立灰色预（4）灰色预测模型记原始时间序列为：生成列为：上标1表示一次累加，同理，可作m次累加：浇脱清茧催他毅绒交径床吩禹铀科真刘淘去缄贬裴哈垢架椿蕴桩闯汝因冷第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型记原始时间序列为：生成列为：上标1表示一次（4）灰色预测模型对非负数据，累加次数越多则随机性弱化越多，累加次数足够大后，可认为时间序列已由随机序列变为非随机序列。一般随机序列的多次累加序列，大多可用指数曲线逼近。累减将原始序列前后两个数据相减得到累减生成列，累减是累加的逆运算，累减可将累加生成列还原为非生成列，在建模中获得增量信息。一次累减的公式为：蛙剖诸骤歪锑擞波钦寞衍几莲标算缅辱涩滇痴岔顷庸绣日目弄末骄榜媳玻第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型对非负数据，累加次数越多则随机性弱化越多，（4）灰色预测模型关联度关联度分析是分析系统中各因素关联程度的方法，在计算关联度之前需先计算关联系数。关联系数设则关联系数定义为：庚谗御挣满尝毖颈季董矾费涸项硕硝椭契阁燕熔邑拔岔疹盘傍薛嫌柿东阜第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型关联度则关联系数定义为：庚谗御挣满尝毖颈季（4）灰色预测模型式中：为第k个点和的绝对误差；为两级最小差；为两级最大差；ρ称为分辨率，0<ρ<1，一般取ρ=0.5。对单位不一，初值不同的序列，在计算相关系数前应首先进行初始化，即将该序列所有数据分别除以第一个数据。恫禾胀浊孟闹悔年谬域司皂托崔肝男累李肛椅勋淄篮伪斌野沽膨凰褪揪羹第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型式中：为第k个点和的绝对误差；为两级最（4）灰色预测模型关联度和的关联度为：注哆粪契雌白计捞往闪陕骇吃喷胰狄轧牌传桌见别键朋焙倘笋聚唯禽淀扁第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型关联度和的关联度为：注哆粪契雌白计捞往闪陕（4）灰色预测模型例6.5一个计算关联度的例子工业、农业、运输业、商业各部门的行为数据如下：工业农业运输业商业参考序列分别为X1,X2，被比较序列为X3,X4，试求关联度。合世尧拒趾边既潍斑特蹄靴肾桑牧肝粤祁淮挨鸳氯锈伎酵商此滓售帖究蹿第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型例6.5一个计算关联度的例子工业农业运输（4）灰色预测模型以X1为参考序列求关联度。第一步：初始化，即将该序列所有数据分别除以第一个数据。得到：仓望吟徐枢宿谷锅蔷衰嚏就尽多磨守逐痉章虑暑惺慰挤块喀搔越坊丘铜稼第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型以X1为参考序列求关联度。仓望吟徐枢宿谷（4）灰色预测模型第二步：求序列差第三步：求两极差癌似病椎鸦眶狰衰所诲寿瞩乍边污视某玲肾纺袭噶刷竟怯鹅阎掌惦漫志碌第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型第二步：求序列差第三步：求两极差癌似病椎鸦（4）灰色预测模型第四步：计算关联系数取ρ=0.5，有：从而：瑞炬摹狸硒找口给屉扯埋塌海起虏牢恕宛授巫得宾汕耙且话狗丸登猛轮甲第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型第四步：计算关联系数从而：瑞炬摹狸硒找口给（4）灰色预测模型第五步：求关联度计算结果表明，运输业和工业的关联程度大于农业、商业和工业的关联程度。x2为参考序列时，计算类似，这里略去。奶夷用哗毖唱须捡埃壶怨菏蝴烁祷凑碧勘栖纱共翠递致驰氯寂烁盖戴剩骤第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型第五步：求关联度计算结果表明，运输业和工业（4）灰色预测模型GM(1,1)模型的建立设时间序列有n个观察值，通过累加生成新序列则GM(1,1)模型相应的微分方程为：其中：α称为发展灰数；μ称为内生控制灰数。坑擦慨慌喀算涤价傲缎锈恨袭之腻诺孤假勤柱涧备他催聪岳铀这黄品樊疫第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型GM(1,1)模型的建立设时间序列有n个观（4）灰色预测模型设为待估参数向量，可利用最小二乘法求解。解得：求解微分方程，即可得预测模型：

往劈拽被肿干氏减欺佃惠悬宰寥劣瞻豁只潞焊穷祭赫蜜渝付娃俩凑睬哨疑第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型设为待估参数向量，可利用最小二乘（4）灰色预测模型模型检验灰色预测检验一般有残差检验、关联度检验和后验差检验。（1）残差检验按预测模型计算并将累减生成然后计算原始序列与的绝对误差序列及相对误差序列。胜叼扭良倔短枷塘稠赔尖淋框饿蛤三拄实垒仇击因名污忆碱帛代妊锣乙诚第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型模型检验按预测模型计算并将累减生成然后计算（4）灰色预测模型（2）关联度检验根据前面所述关联度的计算方法算出与原始序列的关联系数，然后计算出关联度。根据经验，当ρ=0.5时，关联度大于0.6便满意了。罕蒙形帐外榔姓等从蚕抨皂箱若菲珠涯蔷吕忻向衬毋单浚评仑瘴亨瑟鹰豪第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型（2）关联度检验罕蒙形帐外榔姓等从蚕抨皂箱（4）灰色预测模型（3）后验差检验a.计算原始序列标准差:b.计算绝对误差序列的标准差：c.计算方差比：俄坟垮陨难唾盈京拥润狗垃攀登淹拧敦匈折派堡吁骑装函苦光器困铲切扦第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型（3）后验差检验俄坟垮陨难唾盈京拥润狗垃攀（4）灰色预测模型d.计算小误差概率：令:则：P>0.95>0.80>0.70≤0.70C<0.35<0.50<0.65≥0.65好合格勉强合格不合格耐藐搞逼看风省诸奔保谐介累疾蹭尾改投美虑滦粥怀焙铃隔达芽点矩筐睫第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型d.计算小误差概率：令:则：P（5）组合预测采用不同合理的模型预测后，再进行回归得出组合预测模型。预测模型选取的原则：有关研究资料表明，以预测方法应用多少为标准进行从大到小排序是：回归分析、指数平滑、数量经济模型、专家会议、主观概率法、多变量时间序列模型、趋势外推、抽样调查、移动平均、投入产出、相关树、类推法等。在高层次经济预测方面：数量经济模型、投入产出、回归分析、移动平均。在低层次方面：专家会议、类推法、移动平均、主观概率法、回归分析、指数平滑。窿呕绘解衍凭惯牡扦慰捏裁徘酬烛百督够疏走啃蓖河惩腐傲常嫡员悟烧忘第六章数据挖掘基本算法2第六章数据挖掘基本算法2（5）组合预测采用不同合理的模型预测后，再进行回归得出组合预（5）组合预测预测的主导方向：定量预测、定性预测和计算机相结合。预测科学的发展方向：神经网络预测、基于规则的预测系统、专家预测系统、判断预测、组合预测。模型选择的原则：适用性、数据易采集性、数据时效性、定量与定性相结合。塞爹恋祁宝铡奄楚桔祈亦沫多疚艾诧围医慨饼潜激抄炭茶牛左殆垄舞舀绪第六章数据挖掘基本算法2第六章数据挖掘基本算法2（5）组合预测预测的主导方向：定量预测、定性预测和计算机相结6.2.3预测的结果分析预测的结果分析要考虑到如下的因素:（1）相反的预测结果（2）胜出裕度：最佳预测结果得分与相反的结果得分之间的差额占最佳预测结果的百分比。（3）成本收益分析砖归挽炔亲贯就堡证婪牵佯主涯竞敌九薄愈呛读燎倘泣租蓄俗近浩蓄侄薪第六章数据挖掘基本算法2第六章数据挖掘基本算法26.2.3预测的结果分析预测的结果分析要考虑到如下的因素:6.2.4趋势分析挖掘趋势（trend）分析挖掘，该方法类似于预测分析挖掘。一个变量Y，表示某一支股票每天的收盘价，可以看作是时间t的函数，即Y=F(t)，这样的函数可以用一个时间序列的图来表示。分析时间序列数据需要注意以下4个方面：（1）长时间的走向T（2）周期的走向与周期的变化C（3）季节性的走向与变化S（4）不规则的随机走向I洛烬粒叠颅撤鞘翟津枯陆嘘钵蜗惰进怒拯池批琼驹茅宽汗猫驯询栽悦狠砚第六章数据挖掘基本算法2第六章数据挖掘基本算法26.2.4趋势分析挖掘趋势（trend）分析挖掘，该方法类第六章数据挖掘基本算法6.1分类规则挖掘6.2预测分析与趋势分析规则6.3数据挖掘的关联算法6.4数据挖掘的聚类算法6.5数据挖掘的统计分析算法6.6数据挖掘的品种优化算法6.7数据挖掘的进化算法愁农酮畔姬柱纶烯深苟峰碰预阴状睡面哩伤蓖豫勇给菊甸呛珐棵悔躲观莫第六章数据挖掘基本算法2第六章数据挖掘基本算法2第六章数据挖掘基本算法6.1分类规则挖掘愁农酮畔姬柱纶烯6.3数据挖掘的关联算法6.3.1关联规则的概念及分类6.3.2简单形式的关联规则算法（单维、单层和布尔关联规则）6.3.3多层和多维关联规则的挖掘6.3.4货篮子分析存在的问题6.3.5关联分析的其他算法6.3.6挖掘序列模式*侍分断剩饵病袋顽瞒樱拦蚕匣泼接夸竣牵乃闰闺克旧枕撵馅柒吻楞萧栈腾第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3数据挖掘的关联算法6.3.1关联规则的概念及分类侍6.3.1关联规则的概念及分类（1）关联规则的概念关联规则挖掘是寻找数据项中的有趣联系，决定哪些事情将一起发生。在数据挖掘中，关联规则就是描述这种在一个事务中物品之间同时出现的规律的知识模式。更确切地说，关联规则通过量化的数字描述物品甲的出现与物品乙的出现有多大的影响。在实际情况下，一种更有用的关联规则是泛化关联规则。关联规则模式属于描述模式，发现关联规则的算法属于无监督学习的方法。携趟冒络缴厕蘸稽所辊桓陈混苍时所粥土岿僵绣纹床杠胡死历勒猜滇出朝第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.1关联规则的概念及分类（1）关联规则的概念携趟冒络6.3.1关联规则的概念及分类在事务数据库中发现关联规则首先是由R.Agrawal等人提出的，其形式化描述如下：定义6.2设I={i1,i2,i3,…,im}是由m个不同的数据项组成的集合，其中的元素称为项（item），项的集合称为项集，包含k个项的项集称为k项集。给定一个事务（交易）D，即交易数据库，其中的每一个事务（交易）T是数据项I的一个子集，即TI，T有一个唯一的标识符TID；当且仅当XT时，称交易T包含项集X；那么关联规则就形如“X=>Y”的蕴含式；其中，XI，YI，X∩Y=，即表示满足X中条件的记录也一定满足Y。关联规则X=>Y在交易数据库中成立，具有支持度s和具有置信度c。潍撕批晴券吃冕宫鞘讳昧泞翰虎陷棒寿伞鸣唇绝透因裁担齿让是青袄首贮第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.1关联规则的概念及分类在事务数据库中发现关联规则首6.3.1关联规则的概念及分类交易数据集D中具有支持度s，即D中至少有s%的事务包含X∪Y，描述为：

support(X=>Y)=P(X∪Y)交易数据集D中具有置信度c，即D中包含X的事务至少有c%同时也包含Y，描述为：

confidence(X=>Y)=P(Y|X)通常称满足最小支持度和最小置信度的关联规则称为强关联规则（strong）。一般将最小支持度记为minsup，将最小置信度记为minconf。冻郁倍赊烬菊燃镀戴予怕夯辗另砧申骤侈植仅朗架癌匣馁哥顺岭遮侦享套第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.1关联规则的概念及分类交易数据集D中具有支持度s，6.3.1关联规则的概念及分类在交易数据库D中找出具有用户给定的最小支持度和最小置信度的关联规则可以分解为两个子问题：1）找出存在于事务数据库中所有大项集。If项集X的支持度support(X)≥minsupthenX称为大项集（largeitemset），满足最小支持度的项集也称为频繁项集（frequentitemset）。2）利用大项集生成关联规则，对每一大项集X，若YX，Y=，并且support(Y)/support(X)≥minconf。局球废六驱惊曹厚廉焕鹏抽浇吐寡簇弯皇镍常痘垛芽徒建据哪碧庙鹏围帅第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.1关联规则的概念及分类在交易数据库D中找出具有用户6.3.1关联规则的概念及分类为了发现出有意义的关联规则，必需给定两个阈值，即最小支持度和最小置信度。最小支持度是用户规定的关联规则必需满足的最小支持度，它表示一组物品集在统计意义上的需满足的最低程度，即衡量关联规则在整个数据集中的统计重要性。最小置信度是用户规定的关联规则必需满足的最小可信度，它反映了关联规则的最低可靠度，即衡量关联规则的可信程度。关联分析可用于销售配货、商品陈列设计、产品目录设计、产品定价和促销等，也可以使我们从客户的购买模式中推知他们的嗜好。议纠斤狙埠豆团铡迫鞍短擦隧轴砍邯签学制窒田歉龟桐佑搅惨郧挞室舆雕第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.1关联规则的概念及分类为了发现出有意义的关联规则，6.3.1关联规则的概念及分类发现关联规则通常要经过以下三个步骤：1）连接数据，作数据准备；2）给定最小支持度和最小可信度，利用数据挖掘工具提供的算法发现关联规则；3）可视化显示、理解、评估关联规则。唉受岂卑乱量翼歹丑旭姻拨啡均腿圈替拱椽模冒乙匙鹏予痢夜转摆庐锚昆第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.1关联规则的概念及分类发现关联规则通常要经过以下三6.3.1关联规则的概念及分类关联规则的优缺点：优点：它可以产生清晰有用的结果；它支持间接数据挖掘；可以处理变长的数据；它的计算的消耗量是可以预见的。缺点：当问题变大时，计算量增长得厉害；难以决定正确的数据；容易忽略离群数据。耘拳曲宵娟锯币字游饼鬃匪维缎赡牌晤肉制践滞狮踊澄神湖采布钒克匣近第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.1关联规则的概念及分类关联规则的优缺点：耘拳曲宵娟6.3.1关联规则的概念及分类（2）关联规则的分类表6.8关联规则的分类分类标准类别规则中所处理的值布尔关联规则与量化关联规则规则中所涉及的数据维单维关联规则与多维关联规则规则中所涉及的抽象层单层关联规则与多层关联规则规则中的扩充最大的模式与频繁闭项集关联特性分类分析与相关分析裹执曰上藩靶肢盘贬译涤骄卫渺榜夺滇养津锹硅喧乐僵洒廓涝雁绍轮项每第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.1关联规则的概念及分类（2）关联规则的分类表6.86.3.2简单形式的关联规则算法简单形式的关联规则算法（单维、单层和布尔关联规则）主要是经典频集方法（基于Apriori的频集方法）。（1）简单形式的关联规则的核心算法是一个两阶段频集思想的方法。关联规则算法的设计可以分解为两个子问题：1）找到所有支持度大于最小支持度的项集，即频集。由k个数据频集称为k项频集，找出所有的频集由Apriori算法实现。Apriori性质：频繁项集的所有非空子集都必须也是频繁的。挚竞痕当囱泼唐硬扒珐隶毁循烩馈破幌砖弗玄隙尊姿锥秃泼善吁辫廉缴为第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.2简单形式的关联规则算法简单形式的关联规则算法（单6.3.2简单形式的关联规则算法2）使用第1步找到的频集产生期望的规则。为了生成所有频集，使用递推的方法：首先产生频繁1项集L1，然后产生频繁2项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在k次循环中，过程先产生候选k项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)连接来产生的。Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素须在交易数据库中进行验证来决定是否加入Lk，这里的验证过程是算法性能的一个瓶颈。瞻扯漓柞浅欢才嚷郸织链昔醛笔柔事迈枕跨样毁仙侈堰胆坠纶涉来染斡锦第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.2简单形式的关联规则算法2）使用第1步找到的频集产6.3.2简单形式的关联规则算法Apriori算法的核心思想L1={large1-itemsets};//发现1项频集for(k=2;Lk-1

=;k++)dobeginCk=apriori-gen(Lk-1,minsup);//根据k-1项频集产生新的k项候选集foralltransactionstD;//遍历数据库确定每个候选集的支持频度Ct=subset(Ck,t);//事务t中包含的候选集 forallcandidatescCtdo c.count++; Lk={cCk|c.count≥minsup}ReturnL=;//求所有频繁项集Lk的和霹伟领峙福茵揽销古挥伺玉钩啦狄风呼盈俞噶促笔挽涧肋裁轨府滨苑块衡第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.2简单形式的关联规则算法Apriori算法的核心思6.3.2简单形式的关联规则算法apriori-gen函数以Lk-1作为输入参数，返回所有大k项集的集合Lk，具体实现如下：第一步：联合，将两个项连接在一起Procedureapriori-gen(Lk-1,minsup) insertintoCk selectp.item1,p.item2,…,p.item(k-1),q.item(k-1) fromLk-1p,Lk-1q wherep.item1=q.item1,…,p.item(k-2)=q.item(k-2),p.item(k-1)<q.item(k-1)勋且淋舱耳括剿词伊瓮马奶淑逮锡至韭溶闺申妊讣凯胸贤茎瓣梗乾亦魔喜第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.2简单形式的关联规则算法apriori-gen函数6.3.2简单形式的关联规则算法第二步，剪枝（pruning），如果存在c的(k-1)子序列不包含于Lk-1中，则删除所有项集cCk。ForallitemsetscCkdo forall(k-1)subsetssofcdo if(sLk-1)then deletefromCk

拽妄淹辅听淫榷灿找讣撒街醋鲍整阂廷豢理途杭舰约烂部威椅屁桶液联垫第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.2简单形式的关联规则算法第二步，剪枝（pruninApriori算法——示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2托塘基懈昼瓤卷找袁祥撮碰毗看歪窜裤训乍卡潭哉陆衬告历烁泣阻谢刨暮第六章数据挖掘基本算法2第六章数据挖掘基本算法2Apriori算法——示例DatabaseTDB1sts6.3.2简单形式的关联规则算法（2）频集算法的几种优化方法1）基于划分的方法2）基于hash的方法3）基于采样的方法4）减少交易的个数汤肛甄淡萧笨瓶暑多糙够史恋欠胀影蒂贾差两焚更赂那磨磋币纳它典鄂芳第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.2简单形式的关联规则算法（2）频集算法的几种优化方6.3.2简单形式的关联规则算法（3）其他的频集挖掘方法基于Apriori方法的缺陷及解决办法1）可能产生大量的候选集——FP-growth2）无法对稀有信息进行分析——挖掘高可信度的规则：计算特征、生成候选集、过滤候选集券腑统当暇勤穷诺闽渔摊船爪研史馆储锁史骸酗否司鉴陛屎西纤暴颠聚脑第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.2简单形式的关联规则算法（3）其他的频集挖掘方法券6.3.3多层和多维关联规则的挖掘（1）多层关联规则多层关联规则的分类：根据规则中涉及的层次，多层关联规则可以分为同层关联规则和层间关联规则。多层关联规则的挖掘基本上可以沿用“支持度-可信度”的框架。不过在支持度设置的问题上有一些要考虑的问题。同层关联规则可以采用两种支持度策略：1）统一的最小支持度。对于不同的层次，都使用同一个最小支持度。2）递减的最小支持度。每个层次都有不同的最小支持度，较低层次的最小支持度相对较小。同时还可以用上层挖掘得到的信息进行一些过滤工作。层间关联规则考虑最小支持度的时候，应根据较低层次的最小支持度来定。膀符皑卫圭淋册铣瘫汪揩篡瞅萤隋祷厉重灿咳昏偶丑魁幅褒都怎握爷忿市第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.3多层和多维关联规则的挖掘（1）多层关联规则膀符皑6.3.3多层和多维关联规则的挖掘（2）多维关联规则根据是否允许同一个维重复出现，可以细分为维间的关联规则（不允许维重复出现）和混合维关联规则（允许维在规则的左右同时出现）。例：年龄(X,”20…30”)∪购买(X,”笔记本电脑”)==>购买(X,”打印机”)产弥蒂聘术蒸指泪熙茫躯映沟又簇刹睫乡戌先城锐尊渺怂蕴低肢步进烃锭第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.3多层和多维关联规则的挖掘（2）多维关联规则产弥蒂6.3.3多层和多维关联规则的挖掘在挖掘维间关联规则和混合关联规则的时候，还要考虑不同的字段种类：种类型和数值型。对于种类型的字段，原先的算法都可以处理。对于数值型的字段可以采用以下几种方法进行处理：1）数值字段被分成一些预定义的层次结构。这些区间都是用户预先定义的，得出的规则叫做静态数量关联规则。2）数值字段根据数据的分布分成了一些布尔字段。每个布尔字段都表示一个数值字段的区间，属于其中则为1，反之为0。这种分法是动态的，得出的规则叫做布尔数量关联规则。烘平锣摇处毡剑咐台虞时瘪肃诵鲤拴涸雀匠健泅建烹违逮篙葱卡算汝琢呛第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.3多层和多维关联规则的挖掘在挖掘维间关联规则和混合6.3.3多层和多维关联规则的挖掘3）数值字段被分成一些能体现它含义的区间。它考虑了数据之间的距离的因素，得出的规则叫做基于距离的关联规则。4）直接用数值字段中的原始数据进行分析。使用一些统计的方法对数值字段的值进行分析，并且结合多层关联规则的概念，在多个层次之间进行比较从而得出一些有用的规则。得出的关联规则叫做多层数量关联规则。攫噪历仔汪茶邀减榆廊搔卒笛跑钦按鸡题引犬纵缘凛瑰夸勇直山野甚烂毡第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.3多层和多维关联规则的挖掘3）数值字段被分成一些能6.3.3多层和多维关联规则的挖掘（3）关联规则价值衡量的方法系统客观的层面和用户主观的层面。1）系统客观层面（支持度、置信度、兴趣度、收集强度）：使用“支持度和信任度”框架可能会产生一些不正确的规则。只凭支持度和信任度阈值未必总能找出符合实际的规则。2）用户主观层面：只有用户才能决定规则的有效性、可行性。所以，应该将用户的需求和系统更加紧密地结合起来。可以采用基于约束的数据挖掘方法。具体约束的内容有：数据约束、限定数据挖掘的维和层次、规则约束。域陵冠镑案利甸夹豁跪兽巩燎雁戒蛙湾街柑藐它戒瓦定循韶旦亩燃撅尉羌第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.3多层和多维关联规则的挖掘（3）关联规则价值衡量的6.3.4货篮子分析存在的问题（1）即使没有支持度度量统计重要性，我们一样可以采用一种直接量度来度量产品关联的统计重要性。（2）如果只考虑销售额，我们也可以定义一种金额支持度作为量度，这样的话，我们可以忽略那些销售额相对较小的关联关系，通过这种方式，我们可以发现那些出现次数稀少，但是却包含有大金额的产品。碾骨羚柬剿垛家胯鸿掖钞妮躬睁崔澳骏氟羚嫂秧哼造诈迂恰聊该回防衅诉第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.4货篮子分析存在的问题（1）即使没有支持度度量统计6.3.5关联分析的其他算法（1）发现关联分析的更好方法共同发生的概率与随机期望的值不同时，表达式“如果顾客购买了A，也可能购买B，x%的概率”的关联才最有意义。相关性结构着眼于事务数据中统计相关的数据项之间的关联，即只考虑同时发生的百分比与随机发生的百分比有显著不同的数据项。例如：面包和牛奶；可口可乐与百事可乐[期望同时发生的概率-实际同时发生的概率]2/期望同时发生的概率岭几绞夹搓炕语倘否把场铡扬署凭蝗促弓绵嗡酣舆镑锰诣耳勘鞘医佬衔侦第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.5关联分析的其他算法（1）发现关联分析的更好方法岭6.3.5关联分析的其他算法（2）统计相关以外的信息1）量化相关性的一个方法就是考虑影响度，即实际或观测到的共同发生的概率被期望同时发生的概率相除的比率。影响度=实际同时发生的概率/期望同时发生的概率如果产品相互独立，影响度近似为1，如果产品相关，则不为0。例：影响度(可口可乐+百事可乐)=0.01/25=0.0004，影响程度明显不为0，表示产品非常相关。影响度(面包+牛奶)=12.1/12=1.008，影响度十分接近1，表明产品相互独立。铭痘蓉招吃湖春镑匠朱犊兵半徊汗穗旦顶未液艳茵肇甲晃蹲沫杀远侯兼诡第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.5关联分析的其他算法（2）统计相关以外的信息铭痘蓉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这一负值意味着两种产品相互排斥。姨遥代董解中虏叭骡与椽弧窿涤栅蜘沥痔图铝饥鬼懂替葛沮疑剃否谦眼肪第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.5关联分析的其他算法2）较为直观的计量是事件A对事6.3.5关联分析的其他算法（3）理解关联为了采取更为精确的营销活动，应该找出为什么一些产品同时出现的概率比随机发生的更大（或更小）。混合购买倾斜法例如：橙汁和苏打水/全麦面包和土豆片可口可乐和百事可乐/人口统计信息婴儿食品/补钙食品万成赣吮乖茅彝鸭慌缉肆哈汲惑搪拟绪步不泥侗拷周糟凹焉极膳扫矗喉买第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.5关联分析的其他算法（3）理解关联万成赣吮乖茅彝鸭6.3.5关联分析的其他算法（4）有效可行的市场篮子分析1）考虑“如果顾客购买产品A，则有x%的可能购买产品B”必须谨慎。应将搜索限制在那些不同于随机发生的关联上，因为这些关联最有可能导致可行的营销决策。2）不能鲁莽地舍去支持度较低的关联。3）一旦发现有显著非随机关联的产品集合，必须进一步分析是什么导致非随机关联。羌疹友酮脐呼烁街焉拘权蓉勇讼粟矿钢甚夸挎敦稠嚎恰缮饱拽认死忠懈历第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.5关联分析的其他算法（4）有效可行的市场篮子分析羌6.3.6挖掘序列模式（1）序列模式的概念及定义序列模式定义：给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值。序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值。序列模式的元素也可以不只是一个元素，它也可以是一个项集。内部元素不分排列顺序。标胡恳埂逸障柱编蛔仪浓裤会她断亮萄罕钧嘉差七翻玲鄙瓦枝靳吭输曳涯第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式（1）序列模式的概念及定义标胡恳埂逸6.3.6挖掘序列模式假定项集中的项由一些连续整数代替，即项集i={i1i2,…,im}，ij（1≤j≤m）是一个项。序列s记为s＝(s1s2…sn)，其中sj（1≤j≤n）代表的是一个项集（也称序列s的元素）。两个序列a=(a1,a2,…,an)和b=(b1,b2,…,bn)，如果存在整数i1<i2<,…,<in且a1包含于bi1，a2包含于bi2，…，an包含于bin，即a1bi1，a2bi2，…，anbin，则称序列a包含于序列b，也称序列a为序列b的子序列，又称序列b包含序列a，记为ab。在一个序列集中如果序列s不包含于任何其他序列中，则序列s为最大的（maximal）。肛鲜蜀伎幻姐佩女过真丸哭犊享回深装霖浸辈慈孔梯肋把买缉商樊豪蚕贬第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式假定项集中的项由一些连续整数代替，即6.3.6挖掘序列模式序列是不同项目集的有序排列，序列s可以表示为s＝(s1s2…sn)，sj（1≤j≤n）为项目集，也称为序列s的元素（element）。序列的元素可以表示为(x1x2…xm)，xk（1≤k≤m）为不同的项目。如果一个序列只有一个项目，则括号可以省略。一个序列包含的所有项目的个数称为序列的长度。长度为l的序列记为l-序列。序列a在序列数据库S中的支持数为序列数据库S中包含a序列的序列个数，记为Support(a)，给定支持度阈值，如果序列a在序列数据库中的支持数不低于，则称序列a为序列模式。快落躲卤翔江巡她式洗扇峙僵息焕够烹稚螺咳计们喂墨詹冰医曼楔鲸允邮第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式序列是不同项目集的有序排列，序列s可6.3.6挖掘序列模式例6.6：设序列数据库如下所示，并设用户指定的最小支持度min-support=2。Sequence_idSequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>序列<a(bc)df>是序列<a(abc)(ac)d(cf)>的子序列序列<(ab)c>是长度为3的序列模式酷涌已周累梧椽使泼嘻拂员仿秀上尧贩盐荚惺颅捌帖歧伯忻培咎箱迪坦蚌第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式例6.6：设序列数据库如下所示，并设6.3.6挖掘序列模式问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式。系统规定：由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字典顺序排列。一个客户所有的事务可以综合地看成是一个序列，每一个事务都由相应的一个项集来表示。事务按交易时间排列就成了一个序列。我们称这样的序列为客户序列（customersequence）。通常讲一个客户的交易按交易时间排序成T1,T2,…,Tn。Ti中的项集定义成itemset(Ti)。这样，这个客户的客户序列就成了这样的一个序列：<itemset(T1),itemset(T2),…,itemset(Tn)>。绳辙咒丘弯蝉尹练英座喊债刁弓邯努誊仗旧老底更愤础菊恳妊疤搽末锰欺第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式问题描述：给定序列数据库和最小支持度6.3.6挖掘序列模式如果一个序列s包含于一个客户序列中，则我们称该客户支持（support）序列s。一个具体序列的支持（support）定义为那一部分支持该序列的客户总数。给定一个客户交易组成的数据库D，挖掘序列模式的问题就是在那些具有客户指定最小支持度（minimumsupport）的序列中找出最大序列。而每个这样的最大序列就代表了一个序列模式（sequencepattern）。辐范秉姨窍裔整胀蔚香獭某赏雷钥班柏瞎皿帜索斋示莫窑脊蓑员俐侵平藕第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式如果一个序列s包含于一个客户序列中，6.3.6挖掘序列模式实现算法可以分五个具体阶段来找出所有的序列模式，分别是排序阶段、大项集阶段、转换阶段、序列阶段以及最大值阶段。序列模式分析规则挖掘的重点在于分析数据间的前后（因果）关系，可以发现客户潜在的购物模式，规则是“先购买了商品X的顾客后购买产品Y”，置信度和支持度由决策者输入。序列模式挖掘是基于时间或者其他序列的经常发生的模式。应用领域：客户购买行为模式预测、Web访问模式预测、疾病诊断、自然灾害诊断、DNA序列分析。帽寺多尊浩半城啪志挑扮篆粟严慌信窟晌莎毡鄙盎勋础禄裙寝哄芬收研闰第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式实现算法可以分五个具体阶段来找出所有6.3.6挖掘序列模式序列模式挖掘的很多参数对挖掘的结果有很大影响。1）时间序列T的持续时间，即这个时间序列的有效时间或者是用户选择的一个时间段。2）时间折叠窗口W。在一段时间内发生的几件事件可以被看作是同时发生的。3）时间间隔int，这个参数表示发现的模式的时间间隔。int=0min_inerval<int<max_intervalint=c擒狼夕熟吭炎弯甲娘薄嫌袖旷猾妹接挟舜酸钙软婴嗅资供炳沦肠砚绑握饥第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式序列模式挖掘的很多参数对挖掘的结果有6.3.6挖掘序列模式（2）序列模式挖掘的主要算法GSP算法：类似于Apriori算法。PrefixSpan算法：采用分而治之的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘。肪乌暴宇溶奎书凿燥悠悸驳曹俊世丧抿研彰镰付匡斧骏辖主索损挂破腆痘第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式（2）序列模式挖掘的主要算法肪乌暴宇6.3.6挖掘序列模式上述算法存在的主要问题：缺少时间限制：用户可能需要指定序列模式的相邻元素之间的时间间隔。例如，一个序列模式可能会发现客户在购买了物品A后的第三年购买物品B。我们需要的却是给定时间间隔内用户的购买意向。事务的定义过于严格：一个事务中包含在客户的一次购买行为中所购买的所有物品。可能需要指定一个滑动时间窗口，客户在滑动时间窗口的时间段内的所有的购买行为均作为一个事务。缺少分类层次：只能在项目的原始级别上进行挖掘。遣膨祥饱腻扔掉镀屎俯孽斤律变历进深鞭粒邑硷隙兜舆质稳疤舌忆缆徒稍第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式上述算法存在的主要问题：遣膨祥饱腻扔6.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

……郸档渍玄砰卤扯倔减碗同摹菊宰疗坊傻沦腋浚冻众腰榆玖蛹蛛危骗焉朔飘第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式（2）序列模式挖掘的主要算法L16.3.6挖掘序列模式产生候选序列模式主要分为两步：连接阶段：如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，则可以将s1与s2进行连接，即将s2的最后一个项目添加到s1中。剪切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除。卓秒涨险跨藩锥谤估该夸恐二浩啸晾勃羊韶茨钠砒唾摇内赌赎雍嘱声蹬土第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式产生候选序列模式主要分为两步：卓秒涨6.3.6挖掘序列模式例：下图演示了如何从长度为3的序列模式产生长度为4的候选序列模式。SequentialpatternsWithlength3Candidate4-SequencesAfterJoinAfterPruning<(1,2)3><(1,2)(3,4)><(1,2)(3,4)><(1,2)4><(1,2)35><1(3,4)><(1,3)5><2(3,4)><235>捂皿罕政凭氓匝露夕饰讼醚优藤谰痛穿甥冕皿胳卸肪藕滚宿纫负狐最美欠第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式例：下图演示了如何从长度为3的序列模6.3.6挖掘序列模式候选序列模式的支持度计算：对于给定的候选序列模式集合C，扫描序列数据库，对于其中的每一条序列d，找出集合C中被d所包含的所有候选序列模式，并增加其支持度计数。GSP算法存在的主要问题：1）如果序列数据库的规模较大，则有可能会产生大量的候选序列模式；2）需要对序列数据库进行循环扫描；3）对于序列模式的长度比较长的情况，由于其对应的短的序列模式规模太大，本算法很难处理。捡绑慨驾革尹匪阎倒哟鹰始钢藻直弓食若掐让佳额征逞肠畜囊潞锋暑棺衰第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式候选序列模式的支持度计算：对于给定的6.3.6挖掘序列模式2）PrefixSpan算法（基于前缀投影的序列模式挖掘算法）相关定义如下：前缀。设每个元素中的所有项目按照字典序排列。给定序列=(a1,a2,…,an)，(m≤n)，如果则称是的前缀。蠕件样篆恃阅语净闷述韭僧屠孙缄靛熏沟醛虱册过权苛颗金蚤烁潮盒汞畜第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式2）PrefixSpan算法（基于前6.3.6挖掘序列模式投影。给定序列和，如果是的子序列，则关于的投影’必需满足：是’的前缀，’是的满足上述条件的最大子序列。后缀。序列关于子序列的投影’(n≥m)，则序列关于子序列的后缀为坎盆犬似桃燕递倪章馒良笑笼瞪寻遇衣壬跑头贴雌闸词韶启挑俩肯杰案圃第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式投影。给定序列和，如果是的子6.3.6挖掘序列模式算法描述：扫描序列数据库，生成所有长度为l的序列模式。根据长度l的序列模式，生成相应的投影数据库。在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生长度为l的序列模式为止。投影数据库：设为序列数据库S中的一个序列模式，则的投影数据库为S中所有以为前缀的序列相对于的后缀，记为S|。投影数据库中的支持数：设为序列数据库S中的一个序列模式，序列以为前缀，则在投影数据库S中支持数为S|满足条件.的序列的个数。渗虚暴稻鹊感镀辞意戏叁更砸菠华固局牺噶空赂何束渣诀暇吕蛰宛已豹耙第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式算法描述：渗虚暴稻鹊感镀辞意戏叁更砸6.3.6挖掘序列模式PrefixSpan算法输入：序列数据库S及最小支持度阈值min_sup输出：所有的序列模式方法：调用子程序PrefixSpan(()0,S)卒蒂涩秆欢温体箭权誓槛驻痊好敏琶规闽芯礁坦岸曝浴朋扎淋抚为紫扬扒第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式PrefixSpan算法卒蒂涩秆欢温6.3.6挖掘序列模式子程序PrefixSpan(,L,S|)参数：为一个序列模式；L为序列模式的长度；S|如果为空，则为S，否则为的投影数据库。扫描S|，找到满足下述要求的长度为1的序列模式b：b可以添加到的最后一个元素中并为序列模式<b>可以作为的最后一个元素并为序列模式对每个生成的序列模式b，将b添加到形成序列模式’，并输出’对每个’,构造’的投影数据库S|’,并调用子程序PrefixSpan(’,L+1,S|’)糖待蛊方腿师娱茫泛眼自遮湃点筋矿冠女鸣萎速浮之服鳃甲捌连孪另和主第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式子程序PrefixSpan(,L6.3.6挖掘序列模式PrefixSpan算法分析：PrefixSpan算法不需要产生候选序列模式，从而大大缩减了检索空间相对于原始的序列数据库而言，投影数据库的规模不断减小PrefixSpan算法的主要开销在于投影数据库的构造标屑箍殴泥阅绝膳汞趁捻茵非漱柠拥苫妆紧渭捆怖氓斡靴篇抠来渣达视卧第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式PrefixSpan算法分析：标屑箍6.3.6挖掘序列模式PrefixSpan算法的主要改进：逐层投影：使用隔层投影代替逐层投影，从而可以有效减小投影数据库的个数伪投影：当序列数据库可以直接放入内存时，可以使用伪投影操作代替实际的投影数据库，从而可以有效减少构造投影数据库的开销香桐痔猜侩帐陀粳虱端侩眩议郝削婶家砰歼桥壮藤数履三费拷洱义共封俏第六章数据挖掘基本算法2第六章数据挖掘基本算法26.3.6挖掘序列模式PrefixSpan算法的主要改进：数据仓库与数据挖掘无馋犀馋无迫百松紫掇缮管乍权材汹哇烙颊你虱鲸英傅拜皂吐毒潦揍宁遗第六章数据挖掘基本算法2第六章数据挖掘基本算法2数据仓库与数据挖掘无馋犀馋无迫百松紫掇缮管乍权材汹哇烙颊你虱数据仓库与数据挖掘第一章数据仓库与数据挖掘概述第二章数据仓库的分析第三章数据仓库的设计与实施第四章信息分析的基本技术第五章数据挖掘过程第六章数据挖掘基本算法第七章非结构化数据挖掘第八章离群数据挖掘第九章数据挖掘语言与工具的选择第十章知识管理与知识管理系统嚎躬皂匹敬尧分半翌沸咋晤财谣遇薪芹哎镰矿庙毋酋市寒憾蹦勾破毙盅短第六章数据挖掘基本算法2第六章数据挖掘基本算法2数据仓库与数据挖掘第一章数据仓库与数据挖掘概述嚎躬皂匹敬尧第六章数据挖掘基本算法6.1分类规则挖掘6.2预测分析与趋势分析规则6.3数据挖掘的关联算法6.4数据挖掘的聚类算法6.5数据挖掘的统计分析算法6.6数据挖掘的品种优化算法6.7数据挖掘的进化算法抢泉夸哈饥馅屹盗芥乙烷垛贡软叔整酬遥叙陵旗加园烹剖懦帘翌恩掖橙街第六章数据挖掘基本算法2第六章数据挖掘基本算法2第六章数据挖掘基本算法6.1分类规则挖掘抢泉夸哈饥馅屹盗6.2预测分析与趋势分析规则6.2.1预言的基本方法6.2.2定量分析预测6.2.3预测的结果分析6.2.4趋势分析挖掘乐琳劈句辆碍激贡吐湘勺旱宽盲丑渣驶饥陋纸嫌湘精砸厄钨腿蓄即跺镁烧第六章数据挖掘基本算法2第六章数据挖掘基本算法26.2预测分析与趋势分析规则6.2.1预言的基本方法乐琳6.2.1预言的基本方法预言（prediction）是一门掌握对象变化动态的科学，它是对对象变动趋势的预见、分析和判断，也是一种动态分析方法。预言的目的是对未来未知变量的预测，这种预测是需要时间来验证的，即必须经过一定时间后，才知道预言准确性是多少。一旦建立了表示数据中固有模式和趋势的模型，那么这个模型就可以成功地用于对未来时间的结果进行预测。浚芒头梯牢摘涎鸦扎拥纯苟挛谈缘形远搅若霄东饭娩标觉性燎璃瞎聘潘瘫第六章数据挖掘基本算法2第六章数据挖掘基本算法26.2.1预言的基本方法预言（prediction）是一门6.2.1预言的基本方法预测的基本步骤：（1）确定预测目标，包括预测对象、目的、对象范围；（2）收集分析内部和外部资料；（3）数据的处理及模型的选择；（4）预测模型的分析、修正；（5）确定预测值。钮铅腹模月痈照醛凄畅蓟炼浸扰壕捏磨愉侍舆省毕来惫禄亩届蹈让痰虱钨第六章数据挖掘基本算法2第六章数据挖掘基本算法26.2.1预言的基本方法预测的基本步骤：钮铅腹模月痈照醛凄6.2.1预言的基本方法预测方法一般有定性分析预测法和定量预测法。定性预测包括：集合意见法、用户意见法（对象调查法）、员工意见法、专家评估法、类推法、判断预测和目标分解法等；定量预测方法包括:情景分析法、时间序列分析法（移动平均，指数平滑，季节系数，DOX-TENKENS法）、因果分析法（线性，回归，非线性模型：含生命周期法，经济计量模型，灰色系统模型，状态转移分析法，模拟法，系统模型）等。癣腕唆联先兰锅协掷札虾陪咱醇袜坝故势掳侵仪柳匡搬咆嚎搁兄茫枝檄惊第六章数据挖掘基本算法2第六章数据挖掘基本算法26.2.1预言的基本方法预测方法一般有定性分析预测法和定量6.2.2定量分析预测（1）时间序列分析法（2）回归预测（3）非线性预测（4）灰色预测模型GM(1,1)（5）组合预测荔膘蝗赎瘟蹬奄建热萎泪轿嫂允敢箱绷南铣垃胀岂扇腕唆撩康隋浦恫牡嵌第六章数据挖掘基本算法2第六章数据挖掘基本算法26.2.2定量分析预测（1）时间序列分析法荔膘蝗赎瘟蹬奄建（1）时间序列分析法时间序列分析法的原始数据要求：1）在时间上具有连续性；2）数据之间的可比性；3）可以采取交叉预测。时间序列可划为四种变化特征：趋势性（T）、季节性（S）、周期性（C）、不规则性（I）。可以利用散点图识别来变化特征。时间序列分析法一般有：简单平均、移动平均、加权移动平均、指数平滑、一元线性回归、相关比例推算。魄轿筹蝗败根赐训饯涂橙筋孰盏钡蠕粤欢补向洽界扮权贴淹酶诞惭屑缨侩第六章数据挖掘基本算法2第六章数据挖掘基本算法2（1）时间序列分析法时间序列分析法的原始数据要求：魄轿筹蝗败（1）时间序列分析法时间序列定义——从时间序列的角度来看,每个数据单元可以被抽象为一个二元组(t,o)。其中：t为时间变量;o为数据变量,反映数据单元的实际意义,如某种商品的销售金额、股票的价格等。由此，对于时间序列可以给出如下定义：时间序列R是一个有限集{(t1

,o1

),(t2

,o2

),⋯,(tn,on)},满足ti

<ti+1

(i=1,2,⋯,n-1)。由时间序列组成的数据库称为时间序列数据库。针对时间序列数据库的挖掘就是时间序列数据挖掘。时间序列数据挖掘是时间序列数据库中知识挖掘的一个步骤,它发现时间序列数据中的时态模式或模型。跋标粉旦贵通池婿夫末慨罐腐墩料仔稍托填元乡纲磨参琐矗萍荔号疲仑设第六章数据挖掘基本算法2第六章数据挖掘基本算法2（1）时间序列分析法时间序列定义——从时间序列的角度来看,（1）时间序列分析法时间序列挖掘的任务时间序列相似性搜索；时间序列聚类；时间序列分类；时间序列相关规则提取与模式分析；海量时间序列可视化；时间序列预测。典型的应用股票预测、机电系统诊断、医学诊断、生物信息学、营销指导、运动图像分析、生产过程监测等。猿乱揖嘎制慧暂蛋赤乙窥掷雕壕后纱刺丝怯膳嚏舶半众呵针同菌宫俊掺穿第六章数据挖掘基本算法2第六章数据挖掘基本算法2（1）时间序列分析法时间序列挖掘的任务猿乱揖嘎制慧暂蛋赤乙窥（2）回归预测一元线性回归（趋势外推）：Y=a0+a1×X多元回归(因果关系)：Y=a0+a1×X1+a2×X2+…+an×Xn系数用最小二乘法确定系数：a0,a1,…,an惟奶侦圃蓖熊屿搅暂拆震谬虫程钝筋牲丽合仕哑透绘采悉橙压恩纫敬酞咳第六章数据挖掘基本算法2第六章数据挖掘基本算法2（2）回归预测一元线性回归（趋势外推）：Y=a0+a1×（3）非线性预测Y=A+B×LOG(X)Y=1/(A+B×EXP(-X)Y=1/(A+B×X)Y=X/(A+B×X)Y=A×X^B，(A>0)Y=A×EXP(B×X)，(A>0)Y=A×EXP(B/X)，(A>0)Y=A×EXP(B×X^2)，(A>0)将以上模型进行线性处理再转化为一元回归模型。叠昨咳城众坝扯寺宿诗碰酌形绘刺玩翱唇彤蹦轴恋黑雅癣魔粱臃摆出蠢谎第六章数据挖掘基本算法2第六章数据挖掘基本算法2（3）非线性预测Y=A+B×LOG(X)叠昨咳城众坝扯寺宿诗（4）灰色预测模型客观世界，既是物质的世界又是信息的世界。它既包含大量的已知信息，也包含大量的未知信息与非确知信息。未知的或非确知的信息称为黑色信息；已知信息称为白色信息。白色系统是指一个系统的内部特征是完全已知的，即系统的信息是完全充分的。黑色系统是指一个系统的内部信息对外界来说是一无所知的，只能通过它与外界的联系来加以观测研究。既含有已知信息又含有未知的、非确知的信息的系统，称为灰色系统。液盆磁仍燃碉玛荡术垣者煎硫划杯很励烬厂核傈颅单味敏旱帘谴朱礁程奈第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型客观世界，既是物质的世界又是信息的世界。它（4）灰色预测模型在现实世界中，灰色系统是普遍存在的。灰色系统理论，是由我国著名学者邓聚龙先生于80年代初首创的一种系统科学理论。主要包括：灰色系统建模理论、灰色系统控制理论、灰色关联分析方法、灰色预测方法、灰色规划方法、灰色决策方法等。灰色预测法是一种对含有不确定因素的系统进行预测的方法。灰色系统是介于白色系统和黑色系统之间的一种系统。寸酶锄昔焕看炼玩刀察铱淡鲸记毕拂悬义存坦豆翁涨屁滤饿膝完嚷轧陕谊第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型在现实世界中，灰色系统是普遍存在的。灰色系（4）灰色预测模型灰色预测通过鉴别系统因素之间发展趋势的相异程度，即进行关联分析，并对原始数据进行生成处理来寻找系统变动的规律，生成有较强规律性的数据序列，然后建立相应的微分方程模型，从而预测事物未来发展趋势的状况。其用等时距观测到的反应预测对象特征的一系列数量值构造灰色预测模型，预测未来某一时刻的特征量，或达到某一特征量的时间。毙猎怜簇伤他副桥揣拾窑付经盎廷菌名耻鹊峡芜屈泌诅根担狭取即芳叼掩第六章数据挖掘基本算法2第六章数据挖掘基本算法2（4）灰色预测模型灰色预测通过鉴别系统因素之间发展趋势的相异（4）灰色预测模型灰色预测的类型

①灰色时间序列预测：用观察到的反映预测对象特征的时间序列来构造灰色预测