数据挖掘概述课件

数据挖掘概述

陈珊珊数据挖掘概述陈珊珊目录一．数据挖掘概念

背景概念典型数据挖掘系统结构数据挖掘的对象二．数据仓库和数据挖掘的OLAP技术

关系数据数据仓库事务数据库高级数据库系统和高级数据库应用

三．数据挖掘技术概念描述关联分析分类和预测聚类分析孤立点分析四．数据挖掘在零售业中的应用五．数据挖掘的发展趋势六．数据挖掘软件的发展目录一．数据挖掘概念三．数据挖掘技术一、数据挖掘概念----原由数据挖掘数据库越来越大有价值的知识可怕的数据一、数据挖掘概念----原由数据挖掘数据库越来越大有价值的知一、数据挖掘概念----原由数据爆炸，知识贫乏

苦恼:淹没在数据中;不能制定合适的决策!数据知识决策模式趋势事实关系模型关联规则序列目标市场资金分配贸易选择在哪儿做广告销售的地理位置金融经济政府POS.人口统计生命周期一、数据挖掘概念----原由数据爆炸，知识贫乏苦恼:淹没一．数据挖掘的概念

1995年，在加拿大蒙特利尔召开了第一届知识发现和数据挖掘国际学术会议，数据挖掘一词被很快流传开来。

数据挖掘(DM:DatMining)就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。

一．数据挖掘的概念

1995年，在加拿大蒙特利尔召开了第一届典型数据挖掘系统结构图形用户界面模式评估数据挖掘引擎数据库或数据仓库服务器数据库数据仓库数据清理数据集成过滤知识库典型数据挖掘系统结构图形用户界面模式评估数据挖掘引擎数据库数数据挖掘的对象关系数据库数据仓库事务数据库高级数据库系统和高级数据库应用数据挖掘的对象关系数据库二．数据仓库和数据挖掘的OLAP技术数据仓库的概念多维数据模型多维数据模型上的OLAP操作二．数据仓库和数据挖掘的OLAP技术数据仓库的概念数据仓库的概念W.H.Inman:数据仓库是一个面向主题的、集成的、时变的、非易失的数据集合，支持管理部门的决策过程。面向主题的：数据仓库围绕一些主题，如顾客、供应商、产品和销售组织。集成的：数据仓库将多个异种数据源，如关系数据库、一般文件和联机事务处理记录集成在一起。时变的：数据存储从历史的角度提供信息。非易失的：数据仓库总是物理地分离存放数据；数据仓库的概念W.H.Inman:数据仓库是一个面向主题的多维数据模型最流行的数据仓库数据模型是多维数据模型。这种模型可以以星型模式、雪花模式、或事实星座模式形式存在。星型模式：数据仓库包括一个事实表，一组维表。事实表包含大批数据且不含冗余。雪花模式：雪花模式是星型模式的变种。雪花模式的维表可能是规范化形式，以便减少冗余。但是执行查询时需要更多连接操作，可能会降低浏览的性能。事实星座模式：对于需要多个事实表共享维表的复杂应用采用事实星座模式。多维数据模型最流行的数据仓库数据模型是多维数据模型。这种模型Time_keyItem_keyBranch_keyLocation_keyDollars_soldUnits_soldTime_keyDayDay_of_the_weekMonthQuarterYearItem_keyItem_namebrandtypeSupplier_typeBranch_keyBranch_nameBranch_typeLocation_keyStreetCityProvince_or_statecountrySales数据仓库的星型模式Time维表item维表branch维表location维表Sale事实表Time_keyItem_keyBranch_keyLoca多维数据模型上的OLAP操作概念分层：概念分层定义一个映射序列，将低层概念映射到更一般的高层概念。模式分层：是数据库模式属性间的全序或偏序。可以形式地表示属性间的语义联系。如关系模式address,包含属性street,city,province-or-state和country,可用如下全序定义location模式分层结构：

street<city<province_or_state<country

多维数据模型上的OLAP操作概念分层：概念分层定义一个映射序allcanadausaBritishcolumbiaontariovancouvervictoriatorontoottawaNewyorkbuffaloNewyorkIIIinois chicagolocationallcountryProvince_or_statecityallcanadausaBritishcolumbiaon多维数据模型上的OLAP操作集合分组分层：将给定属性或维的值组织成常量组或区间组，定义全序或偏序。

{young,middle_aged,senior}all(age){20…39}young{40…59}middle_aged{60…89}senior操作导出的分层：根据用户、专家或数据挖掘系统说明的操作分层。操作可能包括信息编码串的解码，由复杂数据对象提取信息和数据聚类。例:一个e-mail地址www的URL可能包含涉及部门、学校（或公司）和国家的层次信息。可以使用解码操作来提取信息，形成概念分层。

dmbook@cs.sfu.ca给出偏序

login-name<department<university<country,形成了e-mail地址的一个概念分层。多维数据模型上的OLAP操作集合分组分层：将给定属性或维的值多维数据模型上的OLAP操作基于规则的分层：由一组规则定义一个概念分层。如下面的规则可将商品分类为low_profit_margin,medium_profit_margin和high_profit_margin。其中，商品x的价格差定义为x的销售价格和实际价格的差。多维数据模型上的OLAP操作基于规则的分层：由一组规则定义一low_profit_margin(x)price(x,p1)cost(x,p2)

((p1－p2)<50)medium_profit_margin(x)price(x,p1)cost(x,p2)

((p1－p2)50)((p1－p2)250)high_profit_margin(x)price(x,p1)cost(x,p2)

((p1－p2)>250)low_profit_margin(x)price(x,p多维数据模型上的OLAP操作上卷(roll-up)：通过一个维的概念分层向上攀升或者通过维归约，在数据立方体上进行聚集。下钻(drill-down)：通过沿维的概念分层向下或引入新的未来实现。切片或切块：切片(slice)操作在给定的数据立方体的一个维上进行选择，导致一个子方。切块(dice)操作通过对两个或多个维执行选择，定义子方。转轴(pivot):转动数据的视角，提供数据的替代表示。多维数据模型上的OLAP操作上卷(roll-up)：通过一个三．数据挖掘的功能概念描述：特征化和区分关联分析分类和预测聚类分析孤立点分析演变分析三．数据挖掘的功能概念描述：特征化和区分概念描述：特征化和区分概念描述是指用汇总的、简洁的、精确的方式描述每个类或概念。数据特征化是目标类数据的一般特征或特征的汇总．数据区分是将目标类对象的一般特征与一个或多个对比类对象的一般特征比较．概念描述：特征化和区分概念描述是指用汇总的、简洁的、精确的方基于汇总的数据特征化数据立方体(或OLAP)方法:(面向数据仓库)

面向属性的归纳方法(AOI):面向关系数据库查询的、基于概化的、联机的数据分析处理技术。AOI基本思想：首先使用关系数据库查询收集任务相关的数据：然后考察任务相关数据中的每个属性的不同值的个数，进行概化。概化通过属性删除或属性概化进行。

基于汇总的数据特征化数据立方体(或OLAP)方法:(面向属性删除：如果初始工作关系的某个属性有大量不同的值，但（1）在此属性上没有概化操作符：在该属性没有定义概念分层），（2）它的高层概念用其他属性表示，则该属性应该从工作关系中删除。属性概化：如果初始工作关系的某个属性有大量不同的值，并且该属性上存在概化操作符，则应该选择该概化操作符，并将它用于该属性。属性概化阈值控制:一般情况下，数据挖掘系统有一个缺省的属性阈值，取值范围为2到8。概化关系阈值控制：这样的阈值也可以在数据挖掘系统中预先设定，一般取值为10~30。属性删除：如果初始工作关系的某个属性有大量不同的值，但（1）例3-1：假定用户想描述big_university数据库中研究生的一般特征。给定属性：name,gender,major,birth_place,birth_date,residence,phone#(电话号码）和gpa(平均等级分)。该特征的数据挖掘查询可以用数据挖掘查询语言DMQL表示如下：

usebig_university_dbminecharacteristicsas“science_students”inrelevancetoname,gender,major,birth_place,birth_date,residence,phone#,gpafromstudentwherestatusin“graduate”例3-1：假定用户想描述big_university数据库中转化数据挖掘查询为关系查询。

usebig_university_dbselectname,gender,major,birth_date,residence,phone#,gpafromstudentwherestatusin{“M.SC.”,”M.A.”,”M.B.A”,”Ph.D”}转化数据挖掘查询为关系查询。初始工作关系：任务相关数据的集合namegendermajorBirth_placeBirth_dateresidencePhone#gpajimMCSVancouver,BC,Canda8-12-763511MainSt.,Richmond687-45983.67scottMCSMontreal,Que,Canada28-7-75345lstAve.,Richmond253-91063.70leeFphysicsSeattle,WA,USA25-8-70125AustinAve.,Burnaby420-52323.83…………初始工作关系：任务相关数据的集合namegendermajo面向属性的归纳过程如下：

1)name:该属性存在大量不同值，并且该属性没有概化操作符，该属性被删除。

2)gender:由于gender只有两个不同值，该属性保留，并且不对其进行概化。

3)major:假定已定义了一个概念分层，允许将属性major概化到值{arts&science,engineering,business}还假定该属性的概化阈值设置为5，且初始关系中major有20不同值。根据属性概化控制，major沿概念分层向上攀升被概化。

面向属性的归纳过程如下：4)birth_place:该属性有大量不同值，因此应当概化它。假定存在birth_place的概念分层，定义为city<province_or_state<country。如果初始工作关系中country的不同值个数大于属性概化阈值，则birth_place应当删除，因为尽管存在概化操作符，概化阈值也不会满足。如果假定

country的不同值个数小于概化阈值，则birth_place应概化到birth_country.

．．．．．．5)birth_date:假定存在概念分层，可以将birth_date概化到age_range,并age_range的不同值数小于对应的属性概化阈值，则应当对birth_date进行概化．4)birth_place:该属性有大量不同值，因此应当概化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,verygood,…}分组，这样，该属性可以被概化．6)residence:假定residence被属性numb通过面向属性归纳得到广义关系：gendermajorBirth_countryAge_rangeResidence_citygpacountMScienceCanda20…25RichmondVery_good16FScienceforeign25…30Burnabyexcellent22…………………gendermajorBirth_countryAge_ra属性相关分析－信息增益技术前提假设：S是训练样本的集合，每个样本的类标号是已知的，每个样本是一个元组，一个属性用于确定训练样本的类．例如属性status可以用于定义每个样本的类标号，或是graduate,或是undergraduate.

这里假设m个类．设S包含Si个Ｃi类样本，i=1,…,m.一个任意样本属于类Ｃi的可能性是

si/s,其中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具有抽象层：city<province_or_state<country,

每个数据类都应该概化到同一抽象层。如city层，这样比较有意义。挖掘类比较假定给定1998和1999年某公司的销售数据，希望类比较过程：数据收集：通过查询处理收集数据库中相关数据集，并将它划分成一个目标类和一个或多个对比类。维相关分析：用前边介绍的信息增益法分析出强相关的维。同步概化：概化在目标类上进行，概化到用户或专家指定的维阈值控制层，产生主目标类关系／方体。对比类概念概化到与主目标类关系／方体相同的层次，形成主对比类关系／方体。导出比较的表示：结果类比较描述可以用表、图、或规则的形式化可视化。类比较过程：关联分析数据库中的数据一般都存在着关联关系，也就是说，两个或多个变量的取值之间存在某种规律性。这种关联关系有简单关联和时序关联两种。简单关联，例如；购买面包的顾客中有90%的人同时购买牛奶。时序关联，例如：若AT&T股票连续上涨两天且DEC股票不下跌，则第三天IBM股票上涨的可能性为75%。它在简单关联中增加了时间属性。关联分析数据库中的数据一般都存在着关联关系，也就是说，两个或同一次去超市，如果顾客购买牛奶，则他也购买面包的可能性有多大？通过了解哪些商品频繁地被顾客同时购买，这些关联规则的发现可以帮助零售商制定营销策略。购物篮分析同一次去超市，如果顾客购买牛奶，则他也购买面包的可能性有多大

在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%-40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。

啤酒与尿布在美国，一些年轻的父亲下班后经常要到超市去买婴儿关联规则挖掘过程挖掘过程：

1)找出所有频繁项集

2)由频繁项集产生强关联规则由事物数据库挖掘单维布尔关联规则Apriori算法：使用候选项集找频繁项集。

Apriori性质：频繁项集的所有非空子集都必须也是频繁的。该性质应用于算法中，由连接和剪枝来实现频繁项集的查找。

关联规则挖掘过程挖掘过程：关联规则挖掘几个基本概念项集：任务相关的数据集合：I={i1,i2,…im}关联规则：AI,BI,形如ＡＢ的蕴涵式支持度s:support(AB)=P(AB)置信度c:confidence(AB)=P(B|A)强规则：同时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf)的规则。频繁项集：项集的出现频率是包含项集的事物数，如果项集满足最小支持度，则称它为频繁项集。关联规则挖掘几个基本概念项集：任务相关的数据集合：I={i1利用Apriori算法找出所有频繁项集例：设某分店的事物数据如下,用Apriori算法寻找频繁购买的商品。TID项ID的列表T100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I3利用Apriori算法找出所有频繁项集TID项ID的列表T1项集支持度计数{I1}6{I2}7{I3}6{I4}2{I5}2扫描D,对每个候选计数比较候选支持度计数与最小支持度计数项集支持度计数{I1}6{I2}7{I3}6{I4}2{I5}2C1L1项集支持度计数{I1}6{I2}7{I3}6{I4}2{I5项集{I1,I2}{I1,I3}{I1,I4}{I1,I5}{I2,I3}{I2,I4}{I2,I5}{I3,I4}{I3,I5}{I4,I5}由L1产生候选C2扫描D,对每个候选计数项集支持度计数{I1,I2}4{I1,I3}4{I1,I4}1{I1,I5}2{I2,I3}4{I2,I4}2{I2,I5}2{I3,I4}0{I3,I5}1{I4,I5}0项集支持度计数{I1,I2}4{I1,I3}4{I1,I5}2{I2,I3}4{I2,I4}2{I2,I5}2比较候选支持度计数于最小支持度C2C2L2项集{I1,I2}{I1,I3}{I1,I4}{I1,I5}项集{I1,I2,I3}{I1,I2,I5}由L2产生候选C3项集支持度计数{I1,I2,I3}2{I1,I2,I5}2项集支持度计数{I1,I2,I3}2{I1,I2,I5}2扫描D,对每个候选计数比较候选支持度计数于最小支持度C3C3L3项集{I1,I2,I3}{I1,I2,I5}由L2产生候选C由频繁项集产生关联规则置信度：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}.结果关联规则如下，每个都列出置信度。

由频繁项集产生关联规则置信度：confidence(AB)I1I2I5,confidence=2/4=50%I1I5I2,confidence=2/2=100%I2I5I1,confidence=2/2=100%I1I2I5,confidence=2/6=33%I2I1I5,confidence=2/7=29%

I5I1I2,confidence=2/2=100%

如果最小置信度阈值为70%，则只有第2、3赫最后一个规则可以输出，因为只有这些是产生的强规则。I1I2I5,confidence=2/4=5分类和预测分类和预测是两种数据分析形式，可以用来提取描述重要数据类的模型或预测未来的数据趋势。分类是预测分类标号（或离散值），而预测建立连续值函数模型。数据分类分为两步：建立模型与使用模型进行分类。为建立模型而被分析的数据元组称之为训练数据集。使用模型之前首先评估模型的预测准确度。预测是构造和使用模型评估无标号样本类。数据分类有下列基本技术，如判定树归纳、贝叶斯分类和贝叶斯网络、神经网络、k-最临近分类、基于案例的推理、遗传算法、粗糙集和模糊逻辑技术。分类和预测分类和预测是两种数据分析形式，可以用来提取描述重要判定树归纳分类判定树是一个类似于流程图的树结构，其中每个内部节点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点代表类或类分布。树的最顶层节点是根结点。一棵典型的判定树如下图所示，表示概念buys_computer,预测AllElectronics的顾客是否可能购买计算机。

Age?Student?yesCredit_rating?noyesyesno<=3031…40>40noyesexcellentfair判定树归纳分类判定树是一个类似于流程图的树结构，其中每个内部判定树归纳的基本算法是贪心算法，它以自顶向下递归的各个击破方式构造判定树。算法的基本策略如下：树以代表训练样本的单个节点开始（步骤1）如果样本都在同一个类，则该节点成为树叶，并用该类标记（步骤2和3）否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好地将样本分类的属性。该属性成为该节点的“测试”或“判定”属性。在算法的这个版本中，所有的属性都是分类的，即取离散值的。连续值的属性必须离散化。对测试属性的每个已知的值，创建一个分枝，并据此划分样本。算法是用同样的过程，递归地形成每个划分上的样本判定树。一旦一个属性出现在一个节点上，就不必考虑该节点的任何后代上。判定树归纳的基本算法是贪心算法，它以自顶向下递归的各个击破方递归划分步骤仅当下列条件之一成立时停止：

(1)给定节点的所有样本属于同一类；

(2)没有剩余属性可以用来进一步划分样本。在此情况下，使用多数表决。这涉及将给定的节点转换成树叶，并用samples中的多数所在的类标记它。换一种方式，可以存放节点样本的类分布。分枝test_attribute=ai没有样本。在这种情况下，以samples中的多数类创建一个树叶。属性选择度量：信息增益度量选择测试属性。略。递归划分步骤仅当下列条件之一成立时停止：

例4.2：给定一顾客数据库数据元组训练集，类标号属性buys_computer有两个不同值（即{yes,no}),因此有两个不同的类，利用判定树归纳法进行分类：RIDageincomestudentCredit_ratingClass:buy_computer1<=30highNofairNo2<=30highNoexcellentNo331…40highNofairYes4>40mediumNofairYes5>40lowYesfairYes6>40lowYesexcellentNo731…40lowYesexcellentYes8<=30mediumNofairNo9<=30lowYesfairYes10>40mediumYesfairYes11<=30mediumYesexcellentYes1231…40mediumNoexcellentYes1331…40highYesfairYes14>40mediumNoexcellentNo例4.2：给定一顾客数据库数据元组训练集，类标号属性利用信息增益度量计算每个属性的信息增益，得出age具有最高增益值，因此成为判定树根节点的测试属性。判定树如下图所示：由判定树产生分类规则：沿着由根结点到树叶节点的路径，上图的判定树可以转换成IF-THEN分类规则。提取的规则是：

IFage=“<=30”ANDstudent=“no”THENbuys_computer=“no”IFage=“<=30”ANDstudent=“yes”THENbuys_computer=“yes”IFage=“31…40”THENbuys_computer=“yes”IFage=“>40”ANDcredit_rating=“excellent”THENbuys_computer=“no”IFage=“>40”ANDcredit_rating=“fair”THENbuys_computer=“yes”

利用信息增益度量计算每个属性的信息增益，得出age具有最高增

ageincomestudentCredit_ratingclasshighNofairNohighNoexcellentNomediumNofairNolowYesfairYesmediumYesexcellentYesincomestudentCredit_ratingclassmediumnofairyeslowyesfairyeslowyesexcellentnomediumYesfairYesmediumnoexcellentnoincomestudentCredit_ratingclasshighNofairyeslowyesexcellentyesmediumNoexcellentyeshighYesfairyes<3030…40>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.相似度计算欧几里得距离曼哈坦距离明考斯基距离二元变量、标称变量、序数型和比例标度变量混合类型的变量相似度估算区间标度变量聚类分析方法分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法聚类分析方法分类划分方法聚类分析技术划分方法(partitioningmethod):对给定的一个n个对象或元组的数据库,将数据划分为k个组,同时满足:(I)每个组至少包含一个对象;(II)每个对象必须属于且只属于一个组比较典型的划分方法有:(1)基于质心的技术:k-平均方法

(2)基于有代表性的对象的技术:k-中心点法聚类分析技术划分方法(partitioningmethodK-平均算法算法：K-平均。划分的K-平均算法基于簇中平均值。输入：簇的数目K和包含N个对象的数据库。输入：K个簇，使平方误差准则最小。方法：

1)任意选择K个对象作为初始的簇中心;2)repeat3)根据簇中对象的平均值,将每个对象(重新)赋给最类似的簇;4)更新簇的平均值,即计算每个簇中对象的平均值;5)until不再发生变化K-平均算法孤立点分析孤立点是指不符合数据的一般模型的数据对象。孤立点本身可能非常重要，例如在欺诈探测中，孤立点可能预示着欺诈行为。在市场分析中可用于确定极低或极高收入的客户的消费行为，或在医疗分析中用于发现对多种治疗方式的不寻常反应。孤立点分析方法有三类：统计学方法，基于距离的方法和基于偏离的方法。孤立点分析孤立点是指不符合数据的一般模型的数据对象。演变分析数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模．尽管这可能包括时间相关数据的特征化、区分、关联、分类或聚类，这类分析的不同特点包括时间序列数据分析、序列或周期模式匹配和基于类似性的数据分析。例如：假定你有纽约股票交易所过去十年的主要股票市场（时间序列）数据，并希望投资于高科技工业公司的股票。股票交易数据的挖掘研究可以识别整个股票市场和特定公司的股票演变规律。这种规律可以帮助预测股票市场价格的未来走向，帮助你对股票投资作出决策。演变分析数据演变分析描述行为随时间变化的对象的规律或趋势，并零售业中几个数据挖掘的例子基于数据挖掘的数据仓库的设计与构造：由于零售数据覆盖面广（包括销售、顾客、职员、货品运输、销售和服务），所以有许多设计数据仓库的方式。由于数据仓库的主要用途是支持数据分析和数据挖掘，预先的一些数据挖掘例子的结果可作为设计和开发数据仓库结构的参考依据。这涉及要决定包括哪些维和什么级别，以及为保证高质量和有效的数据挖掘应进行哪些预处理。零售业中几个数据挖掘的例子基于数据挖掘的数据仓库的设计与构造零售业中几个数据挖掘的例子销售、顾客、产品、时间和地区的多维分析：

考虑到顾客的需求，产品的销售，趋势和时尚，以及日用品的质量、价格、利润和服务，零售业需要的是适时的信息。因此提供强有力的多维分析和可视化工具是十分重要的一件事情，这包括提供根据数据分析的需要构造复杂的数据立方体。零售业中几个数据挖掘的例子销售、顾客、产品、时间和地区的多维零售业中几个数据挖掘的例子顾客保持力—顾客忠诚分析：通过顾客荣誉卡信息，可以记录下一顾客的购买序列。顾客的忠诚和购买趋势可以按系统的方式加以分析。由同一顾客在不同时期购买的商品可以分组为序列。序列模式挖掘可用于分析顾客的消费或忠诚的变化，据此对价格和商品的花样加以调整，以便留住老客户，吸引新顾客。零售业中几个数据挖掘的例子顾客保持力—顾客忠诚分析：零售业中几个数据挖掘的例子购买推荐和商品参照：通过从销售记录中挖掘关联信息，可以发现购买某一品牌香水的顾客很可能购买其他一些商品。这类信息可用于形成一定的购买推荐。购买推荐可在Web、每周传单或收据上宣传，以便改进服务，帮助顾客选择商品，增加销售额。同样，诸如“本周热点商品”之类的信息或有吸引力的买卖也可以和相关信息一同发布，以达到促销的目的。零售业中几个数据挖掘的例子购买推荐和商品参照：零售业中几个数据挖掘的例子促销活动的有效性分析：

零售业经常通过广告、优惠券和各种折扣和让利的方式搞促销活动，以达到促销产品，吸引顾客的目的。认真分析促销活动的有效性，有助于提高企业利润。多维分析可满足这方面分析的要求，方法是通过比较促销期间的销售量和交易数量与促销前后的有关情况。此外，关联分析可以找出哪些商品可能随降价商品一同被购买，特别是与促销活动前后的销售相比。零售业中几个数据挖掘的例子促销活动的有效性分析：五．数据挖掘的发展趋势应用的探索可伸缩的数据挖掘方法数据挖掘与数据库系统、数据仓库系统和Web数据库系统的集成数据挖掘语言的标准化可视化数据挖掘复杂数据类型挖掘的新方法Web挖掘数据挖掘中的隐私保护与信息安全五．数据挖掘的发展趋势应用的探索六．数据挖掘软件的发展第一代数据挖掘软件特点支持一个或少数几个数据挖掘算法

挖掘向量数据（vector-valueddata）

数据一般一次性调进内存进行处理

典型的系统如SalfordSystems公司早期的CART系统()

缺陷如果数据足够大，并且频繁的变化，这就需要利用数据库或者数据仓库技术进行管理，第一代系统显然不能满足需求。六．数据挖掘软件的发展第一代数据挖掘软件特点六．数据挖掘软件的发展代特征数据挖掘算法集成分布计算模型数据模型第一代作为一个独立的应用支持一个或者多个算法独立的系统单个机器向量数据第二代和数据库以及数据仓库集成多个算法：能够挖掘一次不能放进内存的数据数据管理系统，包括数据库和数据仓库同质、局部区域的计算机群集有些系统支持对象,文本和连续的媒体数据第三代和预言模型系统集成

多个算法数据管理和预言模型系统intranet/extranet网络计算支持半结构化数据和web数据第四代和移动数据/各种计算设备的数据联合

多个算法数据管理、预言模型、移动系统移动和各种计算设备普遍存在的计算模型RobertGrossman，NationalCenterforDataMiningUniversityofIllinoisatChicago的观点六．数据挖掘软件的发展代特征数据挖掘算法集成分布计算模型数据第一代数据挖掘软件CBA新加坡国立大学。基于关联规则的分类算法，能从关系数据或者交易数据中挖掘关联规则，使用关联规则进行分类和预测第一代数据挖掘软件CBA第二代数据挖掘软件特点与数据库管理系统（DBMS）集成

支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性

能够挖掘大数据集、以及更复杂的数据集

通过支持数据挖掘模式（dataminingschema）和数据挖掘查询语言增加系统的灵活性

典型的系统如DBMiner，能通过DMQL挖掘语言进行挖掘操作缺陷只注重模型的生成，如何和预言模型系统集成导致了第三代数据挖掘系统的开发第二代数据挖掘软件特点第二代数据挖掘软件DBMiner第二代数据挖掘软件DBMiner第二代软件SASEnterpriseMiner第二代软件SASEnterpriseMiner第三代数据挖掘软件特点和预言模型系统之间能够无缝的集成，使得由数据挖掘软件产生的模型的变化能够及时反映到预言模型系统中

由数据挖掘软件产生的预言模型能够自动地被操作型系统吸收，从而与操作型系统中的预言模型相联合提供决策支持的功能

能够挖掘网络环境下（Internet/Extranet）的分布式和高度异质的数据，并且能够有效地和操作型系统集成

缺陷不能支持移动环境第三代数据挖掘软件特点第三代软件SPSSClementine以PMML的格式提供与预言模型系统的接口第三代软件SPSSClementine以PMML的格第四代数据挖掘软件特点目前移动计算越发显得重要，将数据挖掘和移动计算相结合是当前的一个研究领域。

第四代软件能够挖掘嵌入式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据第四代数据挖掘原型或商业系统尚未见报导，PKDD2001上Kargupta发表了一篇在移动环境下挖掘决策树的论文，Kargupta是马里兰巴尔的摩州立大学（UniversityofMarylandBaltimoreCounty）正在研制的CAREER数据挖掘项目的负责人，该项目研究期限是2001年4月到2006年4月，目的是开发挖掘分布式和异质数据（Ubiquitous设备）的第四代数据挖掘系统。

第四代数据挖掘软件特点第一代系统与第二代相比因为不具有和数据管理系统之间有效的接口，所以在数据预处理方面有一定缺陷

第三、四代系统强调预言模型的使用和在操作型环境的部署

第二代系统提供数据管理系统和数据挖掘系统之间的有效接口

第三代系统另外还提供数据挖掘系统和预言模型系统之间的有效的接口

目前，随着新的挖掘算法的研究和开发，第一代数据挖掘系统仍然会出现，第二代系统是商业软件的主流，部分第二代系统开发商开始研制相应的第三代数据挖掘系统，比如IBMIntelligentScoreService。第四代数据挖掘原型或商业系统尚未见报导

第一代系统与第二代相比因为不具有和数据管理系统之间有效的接口六.数据挖掘软件的发展数据挖掘软件发展的三个阶段独立的数据挖掘软件横向的数据挖掘工具集纵向的数据挖掘解决方案GregoryPiatetsky-Shapiro的观点六.数据挖掘软件的发展数据挖掘软件发展的三个阶段Gregor谢谢大家！谢谢大家！数据挖掘概述

陈珊珊数据挖掘概述陈珊珊目录一．数据挖掘概念

背景概念典型数据挖掘系统结构数据挖掘的对象二．数据仓库和数据挖掘的OLAP技术

关系数据数据仓库事务数据库高级数据库系统和高级数据库应用

三．数据挖掘技术概念描述关联分析分类和预测聚类分析孤立点分析四．数据挖掘在零售业中的应用五．数据挖掘的发展趋势六．数据挖掘软件的发展目录一．数据挖掘概念三．数据挖掘技术一、数据挖掘概念----原由数据挖掘数据库越来越大有价值的知识可怕的数据一、数据挖掘概念----原由数据挖掘数据库越来越大有价值的知一、数据挖掘概念----原由数据爆炸，知识贫乏

苦恼:淹没在数据中;不能制定合适的决策!数据知识决策模式趋势事实关系模型关联规则序列目标市场资金分配贸易选择在哪儿做广告销售的地理位置金融经济政府POS.人口统计生命周期一、数据挖掘概念----原由数据爆炸，知识贫乏苦恼:淹没一．数据挖掘的概念

1995年，在加拿大蒙特利尔召开了第一届知识发现和数据挖掘国际学术会议，数据挖掘一词被很快流传开来。

数据挖掘(DM:DatMining)就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。

一．数据挖掘的概念

1995年，在加拿大蒙特利尔召开了第一届典型数据挖掘系统结构图形用户界面模式评估数据挖掘引擎数据库或数据仓库服务器数据库数据仓库数据清理数据集成过滤知识库典型数据挖掘系统结构图形用户界面模式评估数据挖掘引擎数据库数数据挖掘的对象关系数据库数据仓库事务数据库高级数据库系统和高级数据库应用数据挖掘的对象关系数据库二．数据仓库和数据挖掘的OLAP技术数据仓库的概念多维数据模型多维数据模型上的OLAP操作二．数据仓库和数据挖掘的OLAP技术数据仓库的概念数据仓库的概念W.H.Inman:数据仓库是一个面向主题的、集成的、时变的、非易失的数据集合，支持管理部门的决策过程。面向主题的：数据仓库围绕一些主题，如顾客、供应商、产品和销售组织。集成的：数据仓库将多个异种数据源，如关系数据库、一般文件和联机事务处理记录集成在一起。时变的：数据存储从历史的角度提供信息。非易失的：数据仓库总是物理地分离存放数据；数据仓库的概念W.H.Inman:数据仓库是一个面向主题的多维数据模型最流行的数据仓库数据模型是多维数据模型。这种模型可以以星型模式、雪花模式、或事实星座模式形式存在。星型模式：数据仓库包括一个事实表，一组维表。事实表包含大批数据且不含冗余。雪花模式：雪花模式是星型模式的变种。雪花模式的维表可能是规范化形式，以便减少冗余。但是执行查询时需要更多连接操作，可能会降低浏览的性能。事实星座模式：对于需要多个事实表共享维表的复杂应用采用事实星座模式。多维数据模型最流行的数据仓库数据模型是多维数据模型。这种模型Time_keyItem_keyBranch_keyLocation_keyDollars_soldUnits_soldTime_keyDayDay_of_the_weekMonthQuarterYearItem_keyItem_namebrandtypeSupplier_typeBranch_keyBranch_nameBranch_typeLocation_keyStreetCityProvince_or_statecountrySales数据仓库的星型模式Time维表item维表branch维表location维表Sale事实表Time_keyItem_keyBranch_keyLoca多维数据模型上的OLAP操作概念分层：概念分层定义一个映射序列，将低层概念映射到更一般的高层概念。模式分层：是数据库模式属性间的全序或偏序。可以形式地表示属性间的语义联系。如关系模式address,包含属性street,city,province-or-state和country,可用如下全序定义location模式分层结构：

street<city<province_or_state<country

多维数据模型上的OLAP操作概念分层：概念分层定义一个映射序allcanadausaBritishcolumbiaontariovancouvervictoriatorontoottawaNewyorkbuffaloNewyorkIIIinois chicagolocationallcountryProvince_or_statecityallcanadausaBritishcolumbiaon多维数据模型上的OLAP操作集合分组分层：将给定属性或维的值组织成常量组或区间组，定义全序或偏序。

{young,middle_aged,senior}all(age){20…39}young{40…59}middle_aged{60…89}senior操作导出的分层：根据用户、专家或数据挖掘系统说明的操作分层。操作可能包括信息编码串的解码，由复杂数据对象提取信息和数据聚类。例:一个e-mail地址www的URL可能包含涉及部门、学校（或公司）和国家的层次信息。可以使用解码操作来提取信息，形成概念分层。

dmbook@cs.sfu.ca给出偏序

login-name<department<university<country,形成了e-mail地址的一个概念分层。多维数据模型上的OLAP操作集合分组分层：将给定属性或维的值多维数据模型上的OLAP操作基于规则的分层：由一组规则定义一个概念分层。如下面的规则可将商品分类为low_profit_margin,medium_profit_margin和high_profit_margin。其中，商品x的价格差定义为x的销售价格和实际价格的差。多维数据模型上的OLAP操作基于规则的分层：由一组规则定义一low_profit_margin(x)price(x,p1)cost(x,p2)

((p1－p2)<50)medium_profit_margin(x)price(x,p1)cost(x,p2)

((p1－p2)50)((p1－p2)250)high_profit_margin(x)price(x,p1)cost(x,p2)

((p1－p2)>250)low_profit_margin(x)price(x,p多维数据模型上的OLAP操作上卷(roll-up)：通过一个维的概念分层向上攀升或者通过维归约，在数据立方体上进行聚集。下钻(drill-down)：通过沿维的概念分层向下或引入新的未来实现。切片或切块：切片(slice)操作在给定的数据立方体的一个维上进行选择，导致一个子方。切块(dice)操作通过对两个或多个维执行选择，定义子方。转轴(pivot):转动数据的视角，提供数据的替代表示。多维数据模型上的OLAP操作上卷(roll-up)：通过一个三．数据挖掘的功能概念描述：特征化和区分关联分析分类和预测聚类分析孤立点分析演变分析三．数据挖掘的功能概念描述：特征化和区分概念描述：特征化和区分概念描述是指用汇总的、简洁的、精确的方式描述每个类或概念。数据特征化是目标类数据的一般特征或特征的汇总．数据区分是将目标类对象的一般特征与一个或多个对比类对象的一般特征比较．概念描述：特征化和区分概念描述是指用汇总的、简洁的、精确的方基于汇总的数据特征化数据立方体(或OLAP)方法:(面向数据仓库)

面向属性的归纳方法(AOI):面向关系数据库查询的、基于概化的、联机的数据分析处理技术。AOI基本思想：首先使用关系数据库查询收集任务相关的数据：然后考察任务相关数据中的每个属性的不同值的个数，进行概化。概化通过属性删除或属性概化进行。

基于汇总的数据特征化数据立方体(或OLAP)方法:(面向属性删除：如果初始工作关系的某个属性有大量不同的值，但（1）在此属性上没有概化操作符：在该属性没有定义概念分层），（2）它的高层概念用其他属性表示，则该属性应该从工作关系中删除。属性概化：如果初始工作关系的某个属性有大量不同的值，并且该属性上存在概化操作符，则应该选择该概化操作符，并将它用于该属性。属性概化阈值控制:一般情况下，数据挖掘系统有一个缺省的属性阈值，取值范围为2到8。概化关系阈值控制：这样的阈值也可以在数据挖掘系统中预先设定，一般取值为10~30。属性删除：如果初始工作关系的某个属性有大量不同的值，但（1）例3-1：假定用户想描述big_university数据库中研究生的一般特征。给定属性：name,gender,major,birth_place,birth_date,residence,phone#(电话号码）和gpa(平均等级分)。该特征的数据挖掘查询可以用数据挖掘查询语言DMQL表示如下：

usebig_university_dbminecharacteristicsas“science_students”inrelevancetoname,gender,major,birth_place,birth_date,residence,phone#,gpafromstudentwherestatusin“graduate”例3-1：假定用户想描述big_university数据库中转化数据挖掘查询为关系查询。

usebig_university_dbselectname,gender,major,birth_date,residence,phone#,gpafromstudentwherestatusin{“M.SC.”,”M.A.”,”M.B.A”,”Ph.D”}转化数据挖掘查询为关系查询。初始工作关系：任务相关数据的集合namegendermajorBirth_placeBirth_dateresidencePhone#gpajimMCSVancouver,BC,Canda8-12-763511MainSt.,Richmond687-45983.67scottMCSMontreal,Que,Canada28-7-75345lstAve.,Richmond253-91063.70leeFphysicsSeattle,WA,USA25-8-70125AustinAve.,Burnaby420-52323.83…………初始工作关系：任务相关数据的集合namegendermajo面向属性的归纳过程如下：

1)name:该属性存在大量不同值，并且该属性没有概化操作符，该属性被删除。

2)gender:由于gender只有两个不同值，该属性保留，并且不对其进行概化。

3)major:假定已定义了一个概念分层，允许将属性major概化到值{arts&science,engineering,business}还假定该属性的概化阈值设置为5，且初始关系中major有20不同值。根据属性概化控制，major沿概念分层向上攀升被概化。

面向属性的归纳过程如下：4)birth_place:该属性有大量不同值，因此应当概化它。假定存在birth_place的概念分层，定义为city<province_or_state<country。如果初始工作关系中country的不同值个数大于属性概化阈值，则birth_place应当删除，因为尽管存在概化操作符，概化阈值也不会满足。如果假定

country的不同值个数小于概化阈值，则birth_place应概化到birth_country.

．．．．．．5)birth_date:假定存在概念分层，可以将birth_date概化到age_range,并age_range的不同值数小于对应的属性概化阈值，则应当对birth_date进行概化．4)birth_place:该属性有大量不同值，因此应当概化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,verygood,…}分组，这样，该属性可以被概化．6)residence:假定residence被属性numb通过面向属性归纳得到广义关系：gendermajorBirth_countryAge_rangeResidence_citygpacountMScienceCanda20…25RichmondVery_good16FScienceforeign25…30Burnabyexcellent22…………………gendermajorBirth_countryAge_ra属性相关分析－信息增益技术前提假设：S是训练样本的集合，每个样本的类标号是已知的，每个样本是一个元组，一个属性用于确定训练样本的类．例如属性status可以用于定义每个样本的类标号，或是graduate,或是undergraduate.

这里假设m个类．设S包含Si个Ｃi类样本，i=1,…,m.一个任意样本属于类Ｃi的可能性是

si/s,其中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具有抽象层：city<province_or_state<country,

每个数据类都应该概化到同一抽象层。如city层，这样比较有意义。挖掘类比较假定给定1998和1999年某公司的销售数据，希望类比较过程：数据收集：通过查询处理收集数据库中相关数据集，并将它划分成一个目标类和一个或多个对比类。维相关分析：用前边介绍的信息增益法分析出强相关的维。同步概化：概化在目标类上进行，概化到用户或专家指定的维阈值控制层，产生主目标类关系／方体。对比类概念概化到与主目标类关系／方体相同的层次，形成主对比类关系／方体。导出比较的表示：结果类比较描述可以用表、图、或规则的形式化可视化。类比较过程：关联分析数据库中的数据一般都存在着关联关系，也就是说，两个或多个变量的取值之间存在某种规律性。这种关联关系有简单关联和时序关联两种。简单关联，例如；购买面包的顾客中有90%的人同时购买牛奶。时序关联，例如：若AT&T股票连续上涨两天且DEC股票不下跌，则第三天IBM股票上涨的可能性为75%。它在简单关联中增加了时间属性。关联分析数据库中的数据一般都存在着关联关系，也就是说，两个或同一次去超市，如果顾客购买牛奶，则他也购买面包的可能性有多大？通过了解哪些商品频繁地被顾客同时购买，这些关联规则的发现可以帮助零售商制定营销策略。购物篮分析同一次去超市，如果顾客购买牛奶，则他也购买面包的可能性有多大

在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%-40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。

啤酒与尿布在美国，一些年轻的父亲下班后经常要到超市去买婴儿关联规则挖掘过程挖掘过程：

1)找出所有频繁项集

2)由频繁项集产生强关联规则由事物数据库挖掘单维布尔关联规则Apriori算法：使用候选项集找频繁项集。

Apriori性质：频繁项集的所有非空子集都必须也是频繁的。该性质应用于算法中，由连接和剪枝来实现频繁项集的查找。

关联规则挖掘过程挖掘过程：关联规则挖掘几个基本概念项集：任务相关的数据集合：I={i1,i2,…im}关联规则：AI,BI,形如ＡＢ的蕴涵式支持度s:support(AB)=P(AB)置信度c:confidence(AB)=P(B|A)强规则：同时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf)的规则。频繁项集：项集的出现频率是包含项集的事物数，如果项集满足最小支持度，则称它为频繁项集。关联规则挖掘几个基本概念项集：任务相关的数据集合：I={i1利用Apriori算法找出所有频繁项集例：设某分店的事物数据如下,用Apriori算法寻找频繁购买的商品。TID项ID的列表T100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I3利用Apriori算法找出所有频繁项集TID项ID的列表T1项集支持度计数{I1}6{I2}7{I3}6{I4}2{I5}2扫描D,对每个候选计数比较候选支持度计数与最小支持度计数项集支持度计数{I1}6{I2}7{I3}6{I4}2{I5}2C1L1项集支持度计数{I1}6{I2}7{I3}6{I4}2{I5项集{I1,I2}{I1,I3}{I1,I4}{I1,I5}{I2,I3}{I2,I4}{I2,I5}{I3,I4}{I3,I5}{I4,I5}由L1产生候选C2扫描D,对每个候选计数项集支持度计数{I1,I2}4{I1,I3}4{I1,I4}1{I1,I5}2{I2,I3}4{I2,I4}2{I2,I5}2{I3,I4}0{I3,I5}1{I4,I5}0项集支持度计数{I1,I2}4{I1,I3}4{I1,I5}2{I2,I3}4{I2,I4}2{I2,I5}2比较候选支持度计数于最小支持度C2C2L2项集{I1,I2}{I1,I3}{I1,I4}{I1,I5}项集{I1,I2,I3}{I1,I2,I5}由L2产生候选C3项集支持度计数{I1,I2,I3}2{I1,I2,I5}2项集支持度计数{I1,I2,I3}2{I1,I2,I5}2扫描D,对每个候选计数比较候选支持度计数于最小支持度C3C3L3项集{I1,I2,I3}{I1,I2,I5}由L2产生候选C由频繁项集产生关联规则置信度：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}.结果关联规则如下，每个都列出置信度。

由频繁项集产生关联规则置信度：confidence(AB)I1I2I5,confidence=2/4=50%