第八章 数据开采课件

一、

知识发现与数据挖掘二、决策树方法（分类方法）三、聚类方法四、关联分析方法第八章数据挖掘本章内容

第八章数据开采(1)80年在美国召开了第一届国际机器学习研讨会；(2)89年8月于美国底特律市召开的第一届KDD国际学术会议；(3)95年在加拿大召开了第一届知识发现和数据挖掘国际学术会议；(4)我国于87年召开了第一届全国机器学习研讨会。第八章数据挖掘一、

知识发现与数据挖掘1.1知识发现和数据挖掘的兴起第八章数据开采

知识发现（KDD）被认为是从数据中发现有用知识的整个过程。数据挖掘（DM）被认为是KDD过程中的一个特定步骤，它用专门算法从数据中抽取模式（patterns）。

KDD过程定义（Fayyad，Piatetsky-Shapiror，andSmyth1996）：

从大量数据中提取出可信的、新颖的、有用的并能被人理解的模式的高级处理过程。“模式”可以看成是知识的雏形，经过验证、完善后形成知识。第八章数据挖掘一、

知识发现与数据挖掘1.2知识发现和数据挖掘概念第八章数据开采KDD过程数据源数据数据集成目标数据预处理后数据转换数据模式知识数据选择预处理数据挖掘数据转换结果表达和解释数据准备数据挖掘结果表达和解释第八章数据挖掘一、

知识发现与数据挖掘1.2知识发现和数据挖掘概念第八章数据开采若两个或多个数据项的取值之间重复出现且概率很高时，它就存在某种关联，可以建立起这些数据项的关联规则。一个相关规则的形式为：A1∧A2…∧Ai→B1∧B2…∧Bj。如果B1,B2,Bj出现，那么A1,A2,Ai一定出现，这表明A1,A2,Ai与B1,B2,Bj有某种关联第八章数据挖掘一、

知识发现与数据挖掘1.3数据挖掘任务关联分析数据挖掘任务主要有：关联分析、聚类、概念描述

、偏差检测、预测。第八章数据开采

数据库中的数据可以划分为一系列有意义的子集，即类。在同一类别中，个体之间的距离较小，而不同类别上的个体之间的距离偏大。第八章数据挖掘一、

知识发现与数据挖掘1.3数据挖掘任务聚类分析第八章数据开采对数据库中一类对象的内涵进行描述，以概括这个类的有关特征。概念描述是对数据库的整体信息有全面概括，从数据库中归纳抽象的信息。类的内涵描述有两种：（1）特征描述：对类中对象的共同特点进行描述（2）辨别性描述：对两个或多个类之间的区别描述产生辨别性描述的方法有：(1)决策树方法：ID3，IBLE等(2)神经网络方法(3)遗传算法第八章数据挖掘一、

知识发现与数据挖掘1.3数据挖掘任务

概念描述第八章数据开采数据库中的数据存在很多异常情况，从数据分析中发现这些异常情况也是很重要的，以引起人们对它更多的注意。偏差检测的数据模式有极值点、断点、拐点、零点和边界等不同的偏差对象。第八章数据挖掘一、

知识发现与数据挖掘1.3数据挖掘任务偏差检测

预测是利用历史数据找出变化规律，建立模型，并用此模型来预测未来数据的种类，特征等。预测第八章数据开采第八章数据挖掘2.1基本概念决策树方法着眼于从一组无次序、无规则的示例中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部结点（非叶结点）进行属性值的比较，并根据不同的属性值决定从此结点向下的分支，直到叶结点才得到结论。叶结点的条件：结点内所有示例属于同类。内部结点用作分支判断的属性称为测试属性。

——怎么选择测试属性？二、

决策树方法（分类分析）分类规则：从树根到叶结点的一条路径对应着一条合取规则。第八章数据开采第八章数据挖掘2.2CLS（ConceptLearningSystem）方法二、

决策树方法（分类分析）工作过程：首先找出最有判别力的因素，把数据分成两个子集，每个子集又选择最有判别力的因素进行划分，一直进行到所有子集仅包含同一类型的数据为止，最后得到一棵决策树，可以用来对新的样例进行分类。

没有明确选择测试属性的标准Quinlan在1979年引进了信息论中的互信息，作为特征判别能力的度量。——ID3方法第八章数据开采第八章数据挖掘2.3信息论原理源信息宿信息信道干预源信息是客观系统本身固有的信息。宿信息是接受系统所呈现的信息。信息熵（先验熵）、条件熵（后验熵）、互信息互信息=信息熵-条件熵三者关系：二、

决策树方法（分类分析）第八章数据开采条件熵：H（U/V）=-∑P(vj)∑P(ui/vj)logP(ui/vj)第八章数据挖掘2.3信息论原理源U宿V信道P(V/U)u1,u2,…,urv1,v2,…,vq信道模型:计算：信息熵：H（U）=-∑P（ui）logP（ui）irrijqP(U)=(P(u1),P(u2),…,P(ur))给定：P(V/U)=P(v1/u1)P(v2/u1)…P(vq/u1)P(v1/u2)P(v2/u2)…P(vq/u2)P(v1/ur)P(v2/ur)…P(vq/ur)传输概率二、

决策树方法（分类分析）第八章数据开采第八章数据挖掘2.4ID3算法主算法：训练集PE，NE取子集建窗口窗口PE’，NE’生成决策树测试PE，NE存在错判的PE’’，NE’’？扩展窗口PE’=PE’+PE’’NE’=NE’+NE’’YN结束二、

决策树方法（分类分析）第八章数据开采第八章数据挖掘2.4ID3算法建树算法：（1）对当前集合，计算各特征的互信息；（2）选择互信息最大的特征AK；（3）根据特征AK的取值把当前集合分为若干个子集；（4）对既含正例又含反例的子集，递归调用建树算法；（5）对只含正例或反例的子集，对应分支标上P或N，返回调用处。二、

决策树方法（分类分析）优缺点：第八章数据开采第八章数据挖掘2.4ID3算法示例：二、

决策树方法（分类分析）1晴热高无风N2晴热高有风N3多云热高无风P4雨适中高无风P5雨冷正常无风P6雨冷正常有风N7多云冷正常有风P8晴适中高无风N9晴冷正常无风P10雨适中正常无风P11晴适中正常有风P12多云适中高有风P13多云热正常无风P14雨适中高有风N天气气温湿度风P（u1）=9/14u1代表正例Pu2代表反例P（u2）=5/14A1=天气取值

v1=晴，v2=多云，v3=雨第八章数据开采第八章数据挖掘2.4ID3算法示例：NPNP天气湿度风高正常有风无风多云P晴

雨二、

决策树方法（分类分析）第八章数据开采第八章数据挖掘2.5ID3应用示例

示例：用决策树方法挖掘保险业务（医疗保险）数据中的投资风险规则设医疗保险数据库由个人信息表、单位信息表、一定时间内（月）索赔单据表等数据表组成，各表信息如下：保险号姓名性别出生日期单位编号年薪投保日期张女670121305423000970901刘男541123200115508970402李男43082520457086970623……个人信息表：二、

决策树方法（分类分析）第八章数据开采第八章数据挖掘2.5ID3应用示例

编号单位名称类别投保日期3054XX房产公司企业9709012001XX公交公司企业9704022045XX工业大学事业970623…………单位信息表：月索赔单据表：单号营业员保险号索赔金额索赔日期000121王300970901000101刘158970902000340刘208970923二、

决策树方法（分类分析）第八章数据开采第八章数据挖掘2.5ID3应用示例

数据挖掘工作的几个步骤：1）数据整理保险号年龄性别单位类别年薪索赔次数是否索赔63女企业230006Y33男企业155080N55男事业70863Y2）数据分析：索赔次数可以去掉。3）数据挖掘：

年龄分段；年薪分段。

ID3建树4）挖掘结果解释：二、

决策树方法（分类分析）第八章数据开采第八章数据挖掘2.5ID3应用示例

数据离散化（分段）

无指导离散化：等间隔离散、等频度离散有指导离散化：基于信息熵的离散化等基于信息熵的离散化基本原理：给定一样本集S，如果用边界T将S划分为S1和S2两部分，则划分后的熵为：H（S，T）=H（S1）+H（S2）|S1||S||S2||S|选取使H（S，T）取值最小的边界T进行划分。二、

决策树方法（分类分析）第八章数据开采第八章数据挖掘2.6IBLE算法基本思想2.7IBLE算法为了克服ID3的缺点，而设计的。用信道容量代替互信息作为特征判别力的度量结点是一组特征，而不只一个特征决策规则树规则2规则3规则1u1u1u1u2u2u2二、

决策树方法（分类分析）第八章数据开采第八章数据挖掘2.7IBLE算法决策规则树中非叶结点均为规则。规则形式为:

特征:A1，A2，...，.Am

权值:W1，W2，...，.Wm

标准值:V1，V2，...，.Vm

阈值:Sp，Sn该规则可形式描述为：（1）sum:=0；（2）对i:=1到m作：若Ai=Vi，则sum:=sum+wi；（3）若sum

sn，则该例为N类；（4）若sum

sp，则该例为P类；（5）若sn<sum<sp，则该例暂不能判，转下一条规则判别。其中sum表示权和。二、

决策树方法（分类分析）第八章数据开采第八章数据挖掘决策规则树结点IBLE算法组成部分：预处理，建规则算法，建决策树算法，类判定算法PENE建规则测试PEPPENPEMNEPNENNEM二、

决策树方法（分类分析）第八章数据开采第八章数据挖掘3.1聚类将集合分组成为由类似的对象组成的多个类的过程被称为聚类。主要的聚类方法：划分方法、层次方法、基于密度方法、基于网格的方法、基于模型的方法。三、

聚类分析与分类的区别：不依赖预先定义的类和带类标识的训练实例。聚类属于无指导学习，而分类是指导性的学习。第八章数据开采第八章数据挖掘3.2划分法算法思想：对N个对象的数据集，构建数据的K个划分，每个划分表示一个聚簇，并且K<=N。即，它将数据划分为K个组，同时满足如下的要求：

每个组至少包含一个对象；每个对象必须属于且只属于一个组。三、

聚类分析目前较流行的两个划分方法是：K-平均算法：每个簇用该簇中所有对象的平均值来表示；K-中心算法：每个簇用最接近簇中心的那个对象来表示。第八章数据开采第八章数据挖掘3.2划分法三、

聚类分析K-平均算法：输入：簇的数目K和包含N个对象的数据集输出：K个簇，使平方误差准则最小方法：任意选择K个对象作为初始的簇中心；repeat

根据对象与各簇中心的距离，将每个对象赋给最近的簇；更新簇的平均值，即计算每个簇的中心；3.Until平方误差准则函数收敛第八章数据开采第八章数据挖掘3.2划分法三、

聚类分析K-平均算法：簇是否不再变化结束NY任意选定K个初始的簇中心将每个对象分配给最临近的簇更新簇平均值缺陷：

不适合发现非凸面形状的簇；不适合发现大小相差很大的簇；对噪声和孤立点数据敏感。算法复杂度：O（nkt）第八章数据开采第八章数据挖掘3.2划分法三、

聚类分析K-中心算法：方法：任意选择K个对象作为初始的簇中心；repeat将每个对象赋给最临近的簇；随机地选择一个非中心点对象，并计算迭代后的总代价；如果总代价小于0，迭代成功，形成新的K个中心点集合；3.until不再发生变化优点：对噪声和孤立点不敏感缺陷：计算代价高第八章数据开采第八章数据挖掘3.3层次法三、

聚类分析算法思想：首先将每个对象作为一簇，然后这些原子簇为越来越大的簇，直到所有的对象都在一个簇中。CURE(ClusteringUsingREpresentatives)CURE思想：用固定数目的代表点来表示一个簇。每个簇的代表点通过这种方式产生：首先选择类中分散的点，然后根据一个特定的收缩因子向类中心“收缩”。在算法的每一步，有最近距离的代表点对（每个点来自一个不同的类）的两个类被合并。第八章数据开采第八章数据挖掘3.3层次法三、

聚类分析优点：每个类有多于一个的代表点使得CURE可以适宜非球形的几何形状。类的收缩可以有助于控制孤立点的影响。因此，CURE对孤立点的处理更加健壮，而且能够识别非球形和大小变化较大的类。

CURE(ClusteringUsingREpresentatives)划分法聚类结果第八章数据开采第八章数据挖掘3.3层次法三、

聚类分析代表点的产生与收缩：CURE第八章数据开采第八章数据挖掘3.4基于密度的方法——DBSCAN三、

聚类分析算法思想：算法将具有足够高密度的区域划分为簇，并可以在带有“噪声”的数据库中发现任意形状的聚类。它定义簇为密度相连的点的最大集合。有关定义：核心对象：如果一个对象的EPS邻域至少包含了MinPts个对象，则称该对象为核心对象。直接密度可达：给定一个对象集合D，如果p在q的EPS邻域内，而q是一个核心对象，则称p从对象q出发是直接密度可达的。密度可达：如果存在一个对象链p1,p2,…,pn,p1=q,pn=p,对pi∈D，（1≤i≤n），pi+1是从pi关于EPS和MinPts直接密度可达的，则对象p是从对象q关于EPS和MinPts密度可达的。密度相连：如果对象集合D中存在一个对象o，使得对象p、q是从o关于EPS和MinPts密度可达的，那么对象p，q是关于EPS和MinPts密度相连的。

第八章数据开采第八章数据挖掘3.4基于密度的方法——DBSCAN三、

聚类分析基于密度的簇：基于密度可达性的最大的密度相连对象的集合

DBSCAN的原理如下：检查数据库中每个点的EPS邻域，如果一个点p的EPS邻域包含多于MinPts个点，则创建一个以p为核心的新簇。然后，反复寻找从核心对象直接密度可达的对象，这个过程还涉及一些密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。第八章数据开采第八章数据挖掘3.4基于密度的方法——DBSCAN三、

聚类分析参数设置接受用户给定的EPS和MinPts的设置值查找核心对象根据EPS和MinPts的设置值，扫描数据库，找出所有核心对象，建立初始簇群簇的扩展与合并根据直接密度可达性扩展和合并簇筛除噪声把不属于任何簇的对象标识为噪声第八章数据开采第八章数据挖掘四、

关联分析4.1基本概念设I={i1