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

数据仓库与数据挖掘,数据仓库与数据挖掘,第一章数据仓库与数据挖掘概述第二章数据仓库的分析第三章数据仓库的设计与实施第四章信息分析的基本技术第五章数据挖掘过程第六章数据挖掘基本算法第七章非结构化数据挖掘第八章离群数据挖掘第九章数据挖掘语言与工具的选择第十章知识管理与知识管理系统,第六章数据挖掘基本算法,6.1分类规则挖掘6.2预测分析与趋势分析规则6.3数据挖掘的关联算法6.4数据挖掘的聚类算法6.5数据挖掘的统计分析算法6.6数据挖掘的品种优化算法6.7数据挖掘的进化算法,6.2预测分析与趋势分析规则,6.2.1预言的基本方法6.2.2定量分析预测6.2.3预测的结果分析6.2.4趋势分析挖掘,6.2.1预言的基本方法,预言（prediction）是一门掌握对象变化动态的科学，它是对对象变动趋势的预见、分析和判断，也是一种动态分析方法。预言的目的是对未来未知变量的预测，这种预测是需要时间来验证的，即必须经过一定时间后，才知道预言准确性是多少。一旦建立了表示数据中固有模式和趋势的模型，那么这个模型就可以成功地用于对未来时间的结果进行预测。,6.2.1预言的基本方法,预测的基本步骤：（1）确定预测目标，包括预测对象、目的、对象范围；（2）收集分析内部和外部资料；（3）数据的处理及模型的选择；（4）预测模型的分析、修正；（5）确定预测值。,6.2.1预言的基本方法,预测方法一般有定性分析预测法和定量预测法。定性预测包括：集合意见法、用户意见法（对象调查法）、员工意见法、专家评估法、类推法、判断预测和目标分解法等；定量预测方法包括:情景分析法、时间序列分析法（移动平均，指数平滑，季节系数，DOX-TENKENS法）、因果分析法（线性，回归，非线性模型：含生命周期法，经济计量模型，灰色系统模型，状态转移分析法，模拟法，系统模型）等。,6.2.2定量分析预测,（1）时间序列分析法（2）回归预测（3）非线性预测（4）灰色预测模型GM(1,1)（5）组合预测,（1）时间序列分析法,时间序列分析法的原始数据要求：1）在时间上具有连续性；2）数据之间的可比性；3）可以采取交叉预测。时间序列可划为四种变化特征：趋势性（T）、季节性（S）、周期性（C）、不规则性（I）。可以利用散点图识别来变化特征。时间序列分析法一般有：简单平均、移动平均、加权移动平均、指数平滑、一元线性回归、相关比例推算。,（1）时间序列分析法,时间序列定义从时间序列的角度来看,每个数据单元可以被抽象为一个二元组(t,o)。其中：t为时间变量;o为数据变量,反映数据单元的实际意义,如某种商品的销售金额、股票的价格等。由此，对于时间序列可以给出如下定义：时间序列R是一个有限集(t1,o1),(t2,o2),(tn,on),满足ti0)Y=AEXP(BX)，(A0)Y=AEXP(B/X)，(A0)Y=AEXP(BX2)，(A0)将以上模型进行线性处理再转化为一元回归模型。,（4）灰色预测模型,客观世界，既是物质的世界又是信息的世界。它既包含大量的已知信息，也包含大量的未知信息与非确知信息。未知的或非确知的信息称为黑色信息；已知信息称为白色信息。白色系统是指一个系统的内部特征是完全已知的，即系统的信息是完全充分的。黑色系统是指一个系统的内部信息对外界来说是一无所知的，只能通过它与外界的联系来加以观测研究。既含有已知信息又含有未知的、非确知的信息的系统，称为灰色系统。,（4）灰色预测模型,在现实世界中，灰色系统是普遍存在的。灰色系统理论，是由我国著名学者邓聚龙先生于80年代初首创的一种系统科学理论。主要包括：灰色系统建模理论、灰色系统控制理论、灰色关联分析方法、灰色预测方法、灰色规划方法、灰色决策方法等。灰色预测法是一种对含有不确定因素的系统进行预测的方法。灰色系统是介于白色系统和黑色系统之间的一种系统。,（4）灰色预测模型,灰色预测通过鉴别系统因素之间发展趋势的相异程度，即进行关联分析，并对原始数据进行生成处理来寻找系统变动的规律，生成有较强规律性的数据序列，然后建立相应的微分方程模型，从而预测事物未来发展趋势的状况。其用等时距观测到的反应预测对象特征的一系列数量值构造灰色预测模型，预测未来某一时刻的特征量，或达到某一特征量的时间。,（4）灰色预测模型,灰色预测的类型灰色时间序列预测：用观察到的反映预测对象特征的时间序列来构造灰色预测模型，预测未来某一时刻的特征量，或达到某一特征量的时间。畸变预测：通过灰色模型预测异常值出现的时刻，预测异常值什么时候出现在特定时区内。系统预测：通过对系统行为特征指标建立一组相互关联的灰色预测模型，预测系统中众多变量间的相互协调关系的变化。拓扑预测：将原始数据作曲线，在曲线上按定值寻找该定值发生的所有时点，并以该定值为框架构成时点数列，然后建立模型预测该定值所发生的时点。,（4）灰色预测模型,为了弱化原始时间序列的随机性，在建立灰色预测模型之前，需先对原始时间序列进行数据处理，经过数据处理后的时间序列即称为生成列。灰色系统常用的数据处理方式有累加和累减两种。累加是将原始序列通过累加得到生成列。累加的规则:将原始序列的第一个数据作为生成列的第一个数据，将原始序列的第二个数据加到原始序列的第一个数据上，其和作为生成列的第二个数据，将原始序列的第三个数据加到生成列的第二个数据上，其和作为生成列的第三个数据，按此规则进行下去，便可得到生成列。,（4）灰色预测模型,记原始时间序列为：,生成列为：,上标1表示一次累加，同理，可作m次累加：,（4）灰色预测模型,对非负数据，累加次数越多则随机性弱化越多，累加次数足够大后，可认为时间序列已由随机序列变为非随机序列。一般随机序列的多次累加序列，大多可用指数曲线逼近。累减将原始序列前后两个数据相减得到累减生成列，累减是累加的逆运算，累减可将累加生成列还原为非生成列，在建模中获得增量信息。一次累减的公式为：,（4）灰色预测模型,关联度关联度分析是分析系统中各因素关联程度的方法，在计算关联度之前需先计算关联系数。关联系数设,则关联系数定义为：,（4）灰色预测模型,式中：,为第k个点,和,的绝对误差；,为两级最小差；,为两级最大差；,称为分辨率，00.800.700.70,C0.35Y在交易数据库中成立，具有支持度s和具有置信度c。,6.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。,6.3.1关联规则的概念及分类,在交易数据库D中找出具有用户给定的最小支持度和最小置信度的关联规则可以分解为两个子问题：1）找出存在于事务数据库中所有大项集。If项集X的支持度support(X)minsupthenX称为大项集（largeitemset），满足最小支持度的项集也称为频繁项集（frequentitemset）。2）利用大项集生成关联规则，对每一大项集X，若YX，Y=，并且support(Y)/support(X)minconf。,6.3.1关联规则的概念及分类,为了发现出有意义的关联规则，必需给定两个阈值，即最小支持度和最小置信度。最小支持度是用户规定的关联规则必需满足的最小支持度，它表示一组物品集在统计意义上的需满足的最低程度，即衡量关联规则在整个数据集中的统计重要性。最小置信度是用户规定的关联规则必需满足的最小可信度，它反映了关联规则的最低可靠度，即衡量关联规则的可信程度。关联分析可用于销售配货、商品陈列设计、产品目录设计、产品定价和促销等，也可以使我们从客户的购买模式中推知他们的嗜好。,6.3.1关联规则的概念及分类,发现关联规则通常要经过以下三个步骤：1）连接数据，作数据准备；2）给定最小支持度和最小可信度，利用数据挖掘工具提供的算法发现关联规则；3）可视化显示、理解、评估关联规则。,6.3.1关联规则的概念及分类,关联规则的优缺点：优点：它可以产生清晰有用的结果；它支持间接数据挖掘；可以处理变长的数据；它的计算的消耗量是可以预见的。缺点：当问题变大时，计算量增长得厉害；难以决定正确的数据；容易忽略离群数据。,6.3.1关联规则的概念及分类,（2）关联规则的分类,表6.8关联规则的分类,6.3.2简单形式的关联规则算法,简单形式的关联规则算法（单维、单层和布尔关联规则）主要是经典频集方法（基于Apriori的频集方法）。（1）简单形式的关联规则的核心算法是一个两阶段频集思想的方法。关联规则算法的设计可以分解为两个子问题：1）找到所有支持度大于最小支持度的项集，即频集。由k个数据频集称为k项频集，找出所有的频集由Apriori算法实现。Apriori性质：频繁项集的所有非空子集都必须也是频繁的。,6.3.2简单形式的关联规则算法,2）使用第1步找到的频集产生期望的规则。为了生成所有频集，使用递推的方法：首先产生频繁1项集L1，然后产生频繁2项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在k次循环中，过程先产生候选k项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)连接来产生的。Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素须在交易数据库中进行验证来决定是否加入Lk，这里的验证过程是算法性能的一个瓶颈。,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中包含的候选集forallcandidatescCtdoc.count+;Lk=cCk|c.countminsupReturnL=;/求所有频繁项集Lk的和,6.3.2简单形式的关联规则算法,apriori-gen函数以Lk-1作为输入参数，返回所有大k项集的集合Lk，具体实现如下：第一步：联合，将两个项连接在一起Procedureapriori-gen(Lk-1,minsup)insertintoCkselectp.item1,p.item2,p.item(k-1),q.item(k-1)fromLk-1p,Lk-1qwherep.item1=q.item1,p.item(k-2)=q.item(k-2),p.item(k-1)购买(X,”打印机”),6.3.3多层和多维关联规则的挖掘,在挖掘维间关联规则和混合关联规则的时候，还要考虑不同的字段种类：种类型和数值型。对于种类型的字段，原先的算法都可以处理。对于数值型的字段可以采用以下几种方法进行处理：1）数值字段被分成一些预定义的层次结构。这些区间都是用户预先定义的，得出的规则叫做静态数量关联规则。2）数值字段根据数据的分布分成了一些布尔字段。每个布尔字段都表示一个数值字段的区间，属于其中则为1，反之为0。这种分法是动态的，得出的规则叫做布尔数量关联规则。,6.3.3多层和多维关联规则的挖掘,3）数值字段被分成一些能体现它含义的区间。它考虑了数据之间的距离的因素，得出的规则叫做基于距离的关联规则。4）直接用数值字段中的原始数据进行分析。使用一些统计的方法对数值字段的值进行分析，并且结合多层关联规则的概念，在多个层次之间进行比较从而得出一些有用的规则。得出的关联规则叫做多层数量关联规则。,6.3.3多层和多维关联规则的挖掘,（3）关联规则价值衡量的方法系统客观的层面和用户主观的层面。1）系统客观层面（支持度、置信度、兴趣度、收集强度）：使用“支持度和信任度”框架可能会产生一些不正确的规则。只凭支持度和信任度阈值未必总能找出符合实际的规则。2）用户主观层面：只有用户才能决定规则的有效性、可行性。所以，应该将用户的需求和系统更加紧密地结合起来。可以采用基于约束的数据挖掘方法。具体约束的内容有：数据约束、限定数据挖掘的维和层次、规则约束。,6.3.4货篮子分析存在的问题,（1）即使没有支持度度量统计重要性，我们一样可以采用一种直接量度来度量产品关联的统计重要性。（2）如果只考虑销售额，我们也可以定义一种金额支持度作为量度，这样的话，我们可以忽略那些销售额相对较小的关联关系，通过这种方式，我们可以发现那些出现次数稀少，但是却包含有大金额的产品。,6.3.5关联分析的其他算法,（1）发现关联分析的更好方法共同发生的概率与随机期望的值不同时，表达式“如果顾客购买了A，也可能购买B，x%的概率”的关联才最有意义。相关性结构着眼于事务数据中统计相关的数据项之间的关联，即只考虑同时发生的百分比与随机发生的百分比有显著不同的数据项。例如：面包和牛奶；可口可乐与百事可乐期望同时发生的概率-实际同时发生的概率2/期望同时发生的概率,6.3.5关联分析的其他算法,（2）统计相关以外的信息1）量化相关性的一个方法就是考虑影响度，即实际或观测到的共同发生的概率被期望同时发生的概率相除的比率。影响度=实际同时发生的概率/期望同时发生的概率如果产品相互独立，影响度近似为1，如果产品相关，则不为0。例：影响度(可口可乐+百事可乐)=0.01/25=0.0004，影响程度明显不为0，表示产品非常相关。影响度(面包+牛奶)=12.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）理解关联为了采取更为精确的营销活动，应该找出为什么一些产品同时出现的概率比随机发生的更大（或更小）。混合购买倾斜法例如：橙汁和苏打水/全麦面包和土豆片可口可乐和百事可乐/人口统计信息婴儿食品/补钙食品,6.3.5关联分析的其他算法,（4）有效可行的市场篮子分析1）考虑“如果顾客购买产品A，则有x%的可能购买产品B”必须谨慎。应将搜索限制在那些不同于随机发生的关联上，因为这些关联最有可能导致可行的营销决策。2）不能鲁莽地舍去支持度较低的关联。3）一旦发现有显著非随机关联的产品集合，必须进一步分析是什么导致非随机关联。,6.3.6挖掘序列模式,（1）序列模式的概念及定义序列模式定义：给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值。序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值。序列模式的元素也可以不只是一个元素，它也可以是一个项集。内部元素不分排列顺序。,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，即a1bi1，a2bi2，anbin，则称序列a包含于序列b，也称序列a为序列b的子序列，又称序列b包含序列a，记为ab。在一个序列集中如果序列s不包含于任何其他序列中，则序列s为最大的（maximal）。,6.3.6挖掘序列模式,序列是不同项目集的有序排列，序列s可以表示为s(s1s2sn)，sj（1jn）为项目集，也称为序列s的元素（element）。序列的元素可以表示为(x1x2xm)，xk（1km）为不同的项目。如果一个序列只有一个项目，则括号可以省略。一个序列包含的所有项目的个数称为序列的长度。长度为l的序列记为l-序列。序列a在序列数据库S中的支持数为序列数据库S中包含a序列的序列个数，记为Support(a)，给定支持度阈值，如果序列a在序列数据库中的支持数不低于，则称序列a为序列模式。,6.3.6挖掘序列模式,例6.6：设序列数据库如下所示，并设用户指定的最小支持度min-support=2。,序列是序列的子序列序列是长度为3的序列模式,6.3.6挖掘序列模式,问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式。系统规定：由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字典顺序排列。一个客户所有的事务可以综合地看成是一个序列，每一个事务都由相应的一个项集来表示。事务按交易时间排列就成了一个序列。我们称这样的序列为客户序列（customersequence）。通常讲一个客户的交易按交易时间排序成T1,T2,Tn。Ti中的项集定义成itemset(Ti)。这样，这个客户的客户序列就成了这样的一个序列：。,6.3.6挖掘序列模式,如果一个序列s包含于一个客户序列中，则我们称该客户支持（support）序列s。一个具体序列的支持（support）定义为那一部分支持该序列的客户总数。给定一个客户交易组成的数据库D，挖掘序列模式的问题就是在那些具有客户指定最小支持度（minimumsupport）的序列中找出最大序列。而每个这样的最大序列就代表了一个序列模式（sequencepattern）。,6.3.6挖掘序列模式,实现算法可以分五个具体阶段来找出所有的序列模式，分别是排序阶段、大项集阶段、转换阶段、序列阶段以及最大值阶段。序列模式分析规则挖掘的重点在于分析数据间的前后（因果）关系，可以发现客户潜在的购物模式，规则是“先购买了商品X的顾客后购买产品Y”，置信度和支持度由决策者输入。序列模式挖掘是基于时间或者其他序列的经常发生的模式。应用领域：客户购买行为模式预测、Web访问模式预测、疾病诊断、自然灾害诊断、DNA序列分析。,6.3.6挖掘序列模式,序列模式挖掘的很多参数对挖掘的结果有很大影响。1）时间序列T的持续时间，即这个时间序列的有效时间或者是用户选择的一个时间段。2）时间折叠窗口W。在一段时间内发生的几件事件可以被看作是同时发生的。3）时间间隔int，这个参数表示发现的模式的时间间隔。int=0min_inervalintmax_intervalint=c,6.3.6挖掘序列模式,（2）序列模式挖掘的主要算法GSP算法：类似于Apriori算法。PrefixSpan算法：采用分而治之的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘。,6.3.6挖掘序列模式,上述算法存在的主要问题：缺少时间限制：用户可能需要指定序列模式的相邻元素之间的时间间隔。例如，一个序列模式可能会发现客户在购买了物品A后的第三年购买物品B。我们需要的却是给定时间间隔内用户的购买意向。事务的定义过于严格：一个事务中包含在客户的一次购买行为中所购买的所有物品。可能需要指定一个滑动时间窗口，客户在滑动时间窗口的时间段内的所有的购买行为均作为一个事务。缺少分类层次：只能在项目的原始级别上进行挖掘。,6.3.6挖掘序列模式,（2）序列模式挖掘的主要算法1）GSP算法扫描序列数据库，得到长度为l的序列模式L1，作为初始的种子集。扫描长度为i的种子集Li，通过连接操作和剪切操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式的支持数，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集。重复第二步，直到没有新的序列模式或新的候选序列模式产生为止。,L1C2L2C3L3C4L4,6.3.6挖掘序列模式,产生候选序列模式主要分为两步：连接阶段：如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，则可以将s1与s2进行连接，即将s2的最后一个项目添加到s1中。剪切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除。,6.3.6挖掘序列模式,例：下图演示了如何从长度为3的序列模式产生长度为4的候选序列模式。,6.3.6挖掘序列模式,候选序列模式的支持度计算：对于给定的候选序列模式集合C，扫描序列数据库，对于其中的每一条序列d，找出集合C中被d所包含的所有候选序列模式，并增加其支持度计数。GSP算法存在的主要问题：1）如果序列数据库的规模较大，则有可能会产生大量的候选序列模式；2）需要对序列数据库进行循环扫描；3）对于序列模式的长度比较长的