《数据挖掘报告》PPT课件.ppt

数据挖掘概述,陈珊珊 C,目录,一数据挖掘概念 背景 概念 典型数据挖掘系统结构 数据挖掘的对象 二数据仓库和数据挖掘的OLAP技术 关系数据 数据仓库 事务数据库 高级数据库系统和高 级 数据库应用,三数据挖掘技术 概念描述 关联分析 分类和预测 聚类分析 孤立点分析 四数据挖掘在零售业中的应用 五数据挖掘的发展趋势 六数据挖掘软件的发展,一、数据挖掘概念-原由,有价值的知识,可怕的数据,一、数据挖掘概念-原由,数据爆炸，知识贫乏,苦恼: 淹没在数据中 ; 不能制定合适的决策!,数据,知识,决策,一数据挖掘的概念,1995年，在加拿大蒙特利尔召开了第一届知识发现和数据挖掘国际学术会议，数据挖掘一词被很快流传开来。 数据挖掘(DM:Dat Mining)就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。,典型数据挖掘系统结构,图形用户界面,模式评估,数据挖掘引擎,数据库或数据 仓库服务器,数据库,数据仓库,数据清理,数据集成,过滤,知识库,数据挖掘的对象,关系数据库 数据仓库 事务数据库 高级数据库系统和高级数据库应用,二数据仓库和数据挖掘的OLAP技术,数据仓库的概念 多维数据模型 多维数据模型上的OLAP操作,数据仓库的概念,W.H.Inman: 数据仓库是一个面向主题的、集成的、时变的、非易失的数据集合，支持管理部门的决策过程。 面向主题的：数据仓库围绕一些主题，如顾客、供应商、产品和销售组织。 集成的：数据仓库将多个异种数据源，如关系数据库、一般文件和联机事务处理记录集成在一起。 时变的：数据存储从历史的角度提供信息。 非易失的：数据仓库总是物理地分离存放数据；,多维数据模型,最流行的数据仓库数据模型是多维数据模型。这种模型可以以星型模式、雪花模式、或事实星座模式形式存在。 星型模式：数据仓库包括一个事实表，一组维表。事实表包含大批数据且不含冗余。 雪花模式：雪花模式是星型模式的变种。雪花模式的维表可能是规范化形式，以便减少冗余。但是执行查询时需要更多连接操作，可能会降低浏览的性能。 事实星座模式：对于需要多个事实表共享维表的复杂应用采用事实星座模式。,Sales数据仓库的星型模式,Time维表,item维表,branch维表,location维表,Sale事实表,多维数据模型上的OLAP操作,概念分层：概念分层定义一个映射序列，将低层概念映射到更一般的高层概念。 模式分层：是数据库模式属性间的全序或偏序。可以形式地表示属性间的语义联系。如关系模式address,包含属性street,city,province-or-state和country,可用如下全序定义location模式分层结构： streetcityprovince_or_statecountry,all,canada,usa,British columbia,ontario,vancouver,victoria,toronto,ottawa,New york,buffalo,New york,IIIinois,chicago,location,all,country,Province_or_state,city,多维数据模型上的OLAP操作,集合分组分层：将给定属性或维的值组织成常量组或区间组，定义全序或偏序。 young,middle_aged,seniorall(age) 2039 young 4059 middle_aged 6089 senior 操作导出的分层：根据用户、专家或数据挖掘系统说明的操作分层。操作可能包括信息编码串的解码，由复杂数据对象提取信息和数据聚类。 例:一个e-mail地址www的URL可能包含涉及部门、学校（或公司）和国家的层次信息。可以使用解码操作来提取信息，形成概念分层。 dmbookcs.sfu.ca给出偏序 login-namedepartmentuniversitycountry,形成了e-mail地址的一个概念分层。,多维数据模型上的OLAP操作,基于规则的分层：由一组规则定义一个概念分层。 如下面的规则可将商品分类为low_profit_margin,medium_profit_margin和high_profit_margin。其中，商品x的价格差定义为x的销售价格和实际价格的差。,low_profit_margin(x)price(x,p1) cost(x,p2) (p1p2)250),多维数据模型上的OLAP操作,上卷(roll-up)：通过一个维的概念分层向上攀升或者通过维归约，在数据立方体上进行聚集。 下钻(drill-down)：通过沿维的概念分层向下或引入新的未来实现。 切片或切块：切片(slice)操作在给定的数据立方体的一个维上进行选择，导致一个子方。切块(dice)操作通过对两个或多个维执行选择，定义子方。 转轴(pivot):转动数据的视角，提供数据的替代表示。,三数据挖掘的功能,概念描述：特征化和区分 关联分析 分类和预测 聚类分析 孤立点分析 演变分析,概念描述：特征化和区分,概念描述是指用汇总的、简洁的、精确的方式描述每个类或概念。 数据特征化是目标类数据的一般特征或特征的汇总 数据区分是将目标类对象的一般特征与一个或多个对比类对象的一般特征比较,基于汇总的数据特征化,数据立方体(或OLAP)方法: ( 面向数据仓库) 面向属性的归纳方法(AOI): 面向关系数据库查询的、基于概化的、联机的数据分析处理技术。 AOI基本思想：首先使用关系数据库查询收集任务相关的数据：然后考察任务相关数据中的每个属性的不同值的个数，进行概化。概化通过属性删除或属性概化进行。,属性删除：如果初始工作关系的某个属性有大量不同的值，但（1）在此属性上没有概化操作符：在该属性没有定义概念分层），（2）它的高层概念用其他属性表示，则该属性应该从工作关系中删除。 属性概化：如果初始工作关系的某个属性有大量不同的值，并且该属性上存在概化操作符，则应该选择该概化操作符，并将它用于该属性。 属性概化阈值控制:一般情况下，数据挖掘系统有一个缺省的属性阈值，取值范围为2到8。 概化关系阈值控制：这样的阈值也可以在数据挖掘系统中预先设定，一般取值为1030。,例3-1：假定用户想描述big_university数据库中研究生的一般特征。给定属性：name,gender,major,birth_place,birth_date,residence,phone#(电话号码）和gpa(平均等级分)。 该特征的数据挖掘查询可以用数据挖掘查询语言DMQL表示如下： use big_university_db mine characteristics as “science_students” in relevance to name,gender,major,birth_place,birth_date,residence,phone#,gpa from student where status in “graduate”,转化数据挖掘查询为关系查询。 use big_university_db select name,gender,major,birth_date,residence,phone#,gpa from student where status in “M.SC.”,”M.A.”,”M.B.A”,”Ph.D”,初始工作关系：任务相关数据的集合,面向属性的归纳过程如下： 1)name:该属性存在大量不同值，并且该属性没有概化操作符，该属性被删除。 2)gender:由于gender只有两个不同值，该属性保留，并且不对其进行概化。 3)major:假定已定义了一个概念分层，允许将属性major概化到值arts&science,engineering,business还假定该属性的概化阈值设置为5，且初始关系中major有20不同值。根据属性概化控制，major沿概念分层向上攀升被概化。,4)birth_place:该属性有大量不同值，因此应当概化它。假定存在birth_place的概念分层，定义为cityprovince_or_statecountry。如果初始工作关系中country的不同值个数大于属性概化阈值，则birth_place应当删除，因为尽管存在概化操作符，概化阈值也不会满足。如果假定 country的不同值个数小于概化阈值，则birth_place应概化到birth_country. 5)birth_date:假定存在概念分层，可以将birth_date概化到age_range,并age_range的不同值数小于对应的属性概化阈值，则应当对birth_date进行概化,6)residence:假定residence被属性number,street,residence_city,residence_province_or_state和residence_country定义number和street的不同值多半很多，因为这些概念的层次相当低因此，number和street应当删除，将residence概化到residence_city. 7)phone#:与上面的属性name一样，该属性包含太多不同值，因此应当在概化中删除 8)gpa:假定存在gpa的概念分层，将等级分成数据区间，如3.75-4.0,3.5-3.75,它又按描述值excellent,very good,分组，这样，该属性可以被概化,通过面向属性归纳得到广义关系：,属性相关分析信息增益技术,前提假设：S是训练样本的集合，每个样本的类标号是已知的，每个样本是一个元组，一个属性用于确定训练样本的类例如属性status可以用于定义每个样本的类标号，或是graduate,或是undergraduate. 这里假设m个类设S包含 Si个i类样本，i=1,m.一个任意样本属于类i的可能性是 si/s,其中s是集合中S中对象的总数,给定样本分类所需的期望信息： (s1,s2,sm)=si/slog2si/s I=1 每个属性的熵： E(A)=(s1j+smj)/s*I(s1j+smj) 每个属性在该划分上获得的信息增益： Gain(A)=I(s1,s2,sm)-E(A) 具有最高信息增益的属性是给定集合中具有最高区分度的属性。,挖掘类比较,假定给定1998和1999年某公司的销售数据，希望比较这两个类。维location具有抽象层：cityprovince_or_statecountry, 每个数据类都应该概化到同一抽象层。如city层，这样比较有意义。,类比较过程： 数据收集：通过查询处理收集数据库中相关数据集，并将它划分成一个目标类和一个或多个对比类。 维相关分析：用前边介绍的信息增益法分析出强相关的维。 同步概化：概化在目标类上进行，概化到用户或专家指定的维阈值控制层，产生主目标类关系方体。对比类概念概化到与主目标类关系方体相同的层次，形成主对比类关系方体。 导出比较的表示：结果类比较描述可以用表、图、或规则的形式化可视化。,关联分析,数据库中的数据一般都存在着关联关系，也就是说，两个或多个变量的取值之间存在某种规律性。这种关联关系有简单关联和时序关联两种。 简单关联，例如；购买面包的顾客中有90%的人同时购买牛奶。 时序关联，例如：若AT&T股票连续上涨两天且DEC股票不下跌，则第三天IBM股票上涨的可能性为75%。它在简单关联中增加了时间属性。,同一次去超市，如果顾客购买牛奶，则他也购买面包的可能性有多大？ 通过了解哪些商品频繁地被顾客同时购买，这些关联规则的发现可以帮助零售商制定营销策略。,购物篮分析,在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%-40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。,啤酒与尿布,关联规则挖掘过程,挖掘过程： 1)找出所有频繁项集 2)由频繁项集产生强关联规则 由事物数据库挖掘单维布尔关联规则 Apriori算法：使用候选项集找频繁项集。 Apriori性质：频繁项集的所有非空子集都必须也是频繁的。该性质应用于算法中，由连接和剪枝来实现频繁项集的查找。,关联规则挖掘几个基本概念,项集：任务相关的数据集合：I=i1,i2,im 关联规则：AI,B I,形如的蕴涵式 支持度s:support(A B)=P(A B) 置信度c:confidence(A B)=P(B|A) 强规则：同时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf)的规则。 频繁项集：项集的出现频率是包含项集的事物数，如果项集满足最小支持度，则称它为频繁项集。,利用Apriori算法找出所有频繁项集 例：设某分店的事物数据如下,用Apriori算法寻找频繁购买的商品。,扫描D,对每个候选计数,比较候选支持度计数与最小支持度计数,C1,L1,由L1产生候选C2,扫描D,对每个候选计数,比较候选支持度计数于最小支持度,C2,C2,L2,由L2产生候选C3,扫描D,对每个候选计数,比较候选支持度计数于最小支持度,C3,C3,L3,由频繁项集产生关联规则,置信度：confidence(AB)=P(A|B) =support_count(AB)/support_count(A) 关联规则产生如下： 对于每个频繁项集l,产生l的所有非空子集。 对于每个非空子集s,如果support_count(l)/support_count(s)min_conf,则输出规则“s (l-s)”。其中，min_conf是最小置信度阈值。 例：假定数据包含频繁项集 l=I1,I2,I5,可以产生哪些关联规则？L的非空子集有I1,I2,I1,I5,I2,I5,I1,I2和I5.结果关联规则如下，每个都列出置信度。,I1I2I5,confidence=2/4=50% I1I5I2,confidence=2/2=100% I2I5I1,confidence=2/2=100% I1 I2 I5,confidence=2/6=33% I2 I1 I5,confidence=2/7=29% I5I1 I2,confidence=2/2=100% 如果最小置信度阈值为70%，则只有第2、3赫最后一个规则可以输出，因为只有这些是产生的强规则。,分类和预测,分类和预测是两种数据分析形式，可以用来提取描述重要数据类的模型或预测未来的数据趋势。分类是预测分类标号（或离散值），而预测建立连续值函数模型。 数据分类分为两步：建立模型与使用模型进行分类。为建立模型而被分析的数据元组称之为训练数据集。 使用模型之前首先评估模型的预测准确度。 预测是构造和使用模型评估无标号样本类。 数据分类有下列基本技术，如判定树归纳、贝叶斯分类和贝叶斯网络、神经网络、k-最临近分类、基于案例的推理、遗传算法、粗糙集和模糊逻辑技术。,判定树归纳分类,判定树是一个类似于流程图的树结构，其中每个内部节点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点代表类或类分布。树的最顶层节点是根结点。 一棵典型的判定树如下图所示，表示概念buys_computer,预测AllElectronics的顾客是否可能购买计算机。,Age?,Student?,yes,Credit_rating?,no,yes,yes,no,=30,3140,40,no,yes,excellent,fair,判定树归纳的基本算法是贪心算法，它以自顶向下递归的各个击破方式构造判定树。算法的基本策略如下： 树以代表训练样本的单个节点开始（步骤1） 如果样本都在同一个类，则该节点成为树叶，并用该类标记（步骤2和3） 否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好地将样本分类的属性。该属性成为该节点的“测试”或“判定”属性。在算法的这个版本中，所有的属性都是分类的，即取离散值的。连续值的属性必须离散化。 对测试属性的每个已知的值，创建一个分枝，并据此划分样本。 算法是用同样的过程，递归地形成每个划分上的样本判定树。一旦一个属性出现在一个节点上，就不必考虑该节点的任何后代上。,递归划分步骤仅当下列条件之一成立时停止： (1)给定节点的所有样本属于同一类； (2)没有剩余属性可以用来进一步划分样本。在此情况下，使用多数表决。这涉及将给定的节点转换成树叶，并用samples中的多数所在的类标记它。换一种方式，可以存放节点样本的类分布。 分枝test_attribute=ai没有样本。在这种情况下，以samples中的多数类创建一个树叶。 属性选择度量：信息增益度量选择测试属性。略。,例4.2：给定一顾客数据库数据元组训练集，类标号属性buys_computer有两个不同值（即yes,no),因此有两个不同的类， 利用判定树归纳法进行分类：,利用信息增益度量计算每个属性的信息增益，得出age具有最高增益值，因此成为判定树根节点的测试属性。判定树如下图所示： 由判定树产生分类规则：沿着由根结点到树叶节点的路径，上图的判定树可以转换成IF-THEN分类规则。提取的规则是： IF age=“40” AND credit_rating=“excellent” THEN buys_computer=“no” IF age=“40” AND credit_rating=“fair” THEN buys_computer=“yes”,age,30,3040,40,分类的其他方法,贝叶斯分类 后向传播分类 K-最临近分类 模糊集方法,预测的方法,线性回归和多元回归 线性模型Y=+X, 多元模型Y= + 1X1+ 2X2 , 回归系数用最小二乘法计算。 非线性回归 通过变量变换将非线性模型转换成线性模型。Y= + 1X+ 2X+ 3X 引入新变量X1=X,X2=X,X3=X, 转换成线性回归模型： Y= + 1X1+ 2X2+ 3X3,聚类分析,聚类就是将数据对象分组成为多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。 聚类与分类的区别：都是对数据对象的集合分析，但聚类所要划分的类是未知的。 在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。 统计方法中的聚类分析是实现聚类的一种手段，它主要研究基于几何距离的聚类分析。基于k-means(k-平均值)、k-medoids(k-中心点）和其他一些方法的聚类分析工具已经被加入到许多统计分析软件包或系统中，如SPSS、SAS.,相似度估算,区间标度变量 1.标准化度量 2.相似度计算 欧几里得距离 曼哈坦距离 明考斯基距离 二元变量、标称变量、序数型和比例标度变量 混合类型的变量,聚类分析方法分类,划分方法 层次方法 基于密度的方法 基于网格的 方法 基于模型的方法,聚类分析技术,划分方法(partitioning method):对给定的一个n个对象或元组的数据库,将数据划分为k个组,同时满足: (I)每个组至少包含一个对象; (II)每个对象必须属于且只属于一个组 比较典型的划分方法有: (1)基于质心的技术:k-平均方法 (2)基于有代表性的对象的技术:k-中心点法,K-平均算法 算法：K-平均。划分的K-平均算法基于簇中平均值。 输入：簇的数目K和包含N个对象的数据库。 输入：K个簇，使平方误差准则最小。 方法： 1)任意选择K个对象作为初始的簇中心; 2)repeat 3)根据簇中对象的平均值,将每个对象(重新)赋给最类似 的簇; 4)更新簇的平均值,即计算每个簇中对象的平均值; 5)until不再发生变化,孤立点分析,孤立点是指不符合数据的一般模型的数据对象。 孤立点本身可能非常重要，例如在欺诈探测中，孤立点可能预示着欺诈行为。在市场分析中可用于确定极低或极高收入的客户的消费行为，或在医疗分析中用于发现对多种治疗方式的不寻常反应。 孤立点分析方法有三类：统计学方法，基于距离的方法和基于偏离的方法。,演变分析,数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模尽管这可能包括时间相关数据的特征化、区分、关联、分类或聚类，这类分析的不同特点包括时间序列数据分析、序列或周期模式匹配和基于类似性的数据分析。 例如：假定你有纽约股票交易所过去十年的主要股票市场（时间序列）数据，并希望投资于高科技工业公司的股票。股票交易数据的挖掘研究可以识别整个股票市场和特定公司的股票演变规律。这种规律可以帮助预测股票市场价格的未来走向，帮助你对股票投资作出决策。,零售业中几个数据挖掘的例子,基于数据挖掘的数据仓库的设计与构造： 由于零售数据覆盖面广（包括销售、顾客、职员、货品运输、销售和服务），所以有许多设计数据仓库的方式。由于数据仓库的主要用途是支持数据分析和数据挖掘，预先的一些数据挖掘例子的结果可作为设计和开发数据仓库结构的参考依据。这涉及要决定包括哪些维和什么级别，以及为保证高质量和有效的数据挖掘应进行哪些预处理。,零售业中几个数据挖掘的例子,销售、顾客、产品、时间和地区的多维分析： 考虑到顾客的需求，产品的销售，趋势和时尚，以及日用品的质量、价格、利润和服务，零售业需要的是适时的信息。因此提供强有力的多维分析和可视化工具是十分重要的一件事情，这包括提供根据数据分析的需要构造复杂的数据立方体。,零售业中几个数据挖掘的例子,顾客保持力顾客忠诚分析： 通过顾客荣誉卡信息，可以记录下一顾客的购买序列。顾客的忠诚和购买趋势可以按系统的方式加以分析。由同一顾客在不同时期购买的商品可以分组为序列。序列模式挖掘可用于分析顾客的消费或忠诚的变化，据此对价格和商品的花样加以调整，以便留住老客户，吸引新顾客。,零售业中几个数据挖掘的例子,购买推荐和商品参照： 通过从销售记录中挖掘关联信息，可以发现购买某一品牌香水的顾客很可能购买其他一些商品。这类信息可用于形成一定的购买推荐。购买推荐可在Web、每周传单或收据上宣传，以便改进服务，帮助顾客选择商品，增加销售额。同样，诸如“本周热点商品”之类的信息或有吸引力的买卖也可以和相关信息一同发布，以达到促销的目的。,零售业中几个数据挖掘的例子,促销活动的有效性分析： 零售业经常通过广告、优惠券和各种折扣和让利的方式搞促销活动，以达到促销产品，吸引顾客的目的。认真分析促销活动的有效性，有助于提高企业利润。多维分析可满足这方面分析的要求，方法是通过比较促销期间的销售量和交易数量与促销前后的有关情况。此外，关联分析可以找出哪些商品可能随降价商品一同被购买，特别是与促销活动前后的销售相比。,五数据挖掘的发展趋势,应用的探索 可伸缩的数据挖掘方法 数据挖掘与数据库系统、数据仓库系统和Web数据库系统的集成 数据挖掘语言的标准化 可视化数据挖掘 复杂数据类型挖掘的新方法 Web挖掘 数据挖掘中的隐私保护与信息安全,六数据挖掘软件的发展,第一代数据挖掘软件,特点 支持一个或少数几个数据挖掘算法 挖掘向量数据（vector-valued data） 数据一般一次性调进内存进行处理 典型的系统如Salford Systems公司早期的CART系统() 缺陷 如果数据足够大，并且频繁的变化，这就需要利用数据库或者数据仓库技术进行管理，第一代系统显然不能满足需求。,六数据挖掘软件的发展,Robert Grossman， National Center for Data Mining University of Illinois at Chicago 的观点,第一代数据挖掘软件 CBA 新加坡国立大学。基于关联规则的分类算法，能从关系数据或者交易数据中挖掘关联规则，使用关联规则进行分类和预测,第二代数据挖掘软件,特点 与数据库管理系统（DBMS）集成