第八章 数据开采1.ppt

1、一、 知识发现与数据挖掘 二、 基于信息论的数据挖掘方法 三、 基于信息熵的规则组合,第八章 数据挖掘,本章内容,(1) 80年在美国召开了第一届国际机器学习研讨会； (2) 89年8月于美国底特律市召开的第一届KDD国 际学术会议； (3) 95年在加拿大召开了第一届知识发现和数据挖掘国际学术会议； (4) 我国于87年召开了第一届全国机器学习研讨会。,第八章 数据挖掘,一、 知识发现与数据挖掘,1.1 知识发现和数据挖掘的兴起,知识发现（KDD）被认为是从数据中发现有用知识的整个过程。数据挖掘（DM）被认为是KDD过程中的一个特定步骤，它用专门算法从数据中抽取模式（patterns）。 K

2、DD过程定义（Fayyad，Piatetsky-Shapiror， and Smyth 1996）： 从大量数据中提取出可信的、新颖的、有用的并能被人理解的模式的高级处理过程。 “模式”可以看成是知识的雏形，经过验证、完善后形成知识。,第八章 数据挖掘,一、 知识发现与数据挖掘,1.2 知识发现和数据挖掘概念,KDD过程,第八章 数据挖掘,一、 知识发现与数据挖掘,1.2 知识发现和数据挖掘概念,若两个或多个数据项的取值之间重复出现且概率很高时，它就存在某种关联，可以建立起这些数据项的关联规则。 一个相关规则的形式为： A1A2AiB1B2Bj。 如果B1,B2,Bj出现，那么A1,A2,Ai

3、一定出现，这表明A1,A2,Ai 与 B1,B2,Bj有某种关联,第八章 数据挖掘,一、 知识发现与数据挖掘,1.3 数据挖掘任务,关联分析,数据挖掘任务主要有：关联分析、聚类、概念描述 、偏差检测、预测。,数据库中的数据可以划分为一系列有意义的子集，即类。 在同一类别中，个体之间的距离较小，而不同类别上的个体之间的距离偏大。,第八章 数据挖掘,一、 知识发现与数据挖掘,1.3 数据挖掘任务,聚类分析,对数据库中一类对象的内涵进行描述，以概括这个类的有关特征。概念描述是对数据库的整体信息有全面概括，从数据库中归纳抽象的信息。 类的内涵描述有两种： （1）特征描述：对类中对象的共同特点进行描述

4、（2）辨别性描述：对两个或多个类之间的区别描述 产生辨别性描述的方法有： (1)决策树方法：ID3，IBLE等 (2)神经网络方法 (3)遗传算法,第八章 数据挖掘,一、 知识发现与数据挖掘,1.3 数据挖掘任务,概念描述,数据库中的数据存在很多异常情况，从数据分析中发现这些异常情况也是很重要的，以引起人们对它更多的注意。 偏差检测的数据模式有极值点、断点、拐点、零点和边界等不同的偏差对象。,第八章 数据挖掘,一、 知识发现与数据挖掘,1.3 数据挖掘任务,偏差检测,预测是利用历史数据找出变化规律，建立模型，并用此模型来预测未来数据的种类，特征等。,预测,第八章 数据挖掘,2.1 ID3方法,

5、二、 基于信息论的数据挖掘方法,工作过程：,首先找出数据集合中最有判别力的属性，把数据分成若干个子集，针对每个子集又选择最有判别力的因素进行划分，直到子集中所有元素属于同一类型为止。,属性判别力的度量互信息,工作结果：生成一棵决策树,第八章 数据挖掘,2.2 信息论原理,二、 基于信息论的数据挖掘方法,源信息是客观系统本身固有的信息。,宿信息是接受系统所呈现的信息。,信息熵（先验熵）、条件熵（后验熵）、互信息,互信息 = 信息熵 - 条件熵,三者关系：,第八章 数据挖掘,2.2 信息论原理,二、 基于信息论的数据挖掘方法,信道模型:,计算：,信息熵：H（U）= -P（ui）log P（ui）,

6、i,r,r,q,第八章 数据挖掘,2.3 ID3算法,二、 基于信息论的数据挖掘方法,主算法：,训练集PE，NE,取子集 建窗口,窗口 PE，NE,生成决策树,测试PE，NE,存在错判的 PE，NE？,扩展窗口 PE= PE + PE NE= NE+ NE ,Y,N,结束,第八章 数据挖掘,2.3 ID3算法,二、 基于信息论的数据挖掘方法,建树算法：,（1）对当前集合，计算各特征的互信息； （2）选择互信息最大的特征AK； （3）根据特征AK的取值把当前集合分为若干个子集； （4）对既含正例又含反例的子集，递归调用建树算法； （5）对只含正例或反例的子集，对应分支标上P或N，返回调用处。,第

7、八章 数据挖掘,2.3 ID3算法,二、 基于信息论的数据挖掘方法,优缺点：,示例：,第八章 数据挖掘,提问：,二、 基于信息论的数据挖掘方法,1、ID3方法的工作过程？,2、建树算法？,第八章 数据挖掘,二、 基于信息论的数据挖掘方法,2.4 应用示例,示例：用决策树方法挖掘保险业务（医疗保险）数据中的投资风险规则,设医疗保险数据库由个人信息表、单位信息表、一定时间内（月）索赔单据表等数据表组成，各表信息如下：,个人信息表：,第八章 数据挖掘,二、 基于信息论的数据挖掘方法,2.4 应用示例,单位信息表：,月索赔单据表：,第八章 数据挖掘,二、 基于信息论的数据挖掘方法,2.4 应用示例,数

8、据挖掘工作的几个步骤：,1）数据整理,2）数据分析：索赔次数可以去掉。,3）数据挖掘：,年龄分段；年薪分段。 ID3建树,4）挖掘结果解释：,第八章 数据挖掘,二、 基于信息论的数据挖掘方法,2.4 应用示例,数据离散化（分段）,无指导离散化：等间隔离散、等频度离散 有指导离散化：基于信息熵的离散化等,第八章 数据挖掘,3.1 基本思想,三、 基于信息论的示例学习方法（IBLE）,3.2 IBLE算法,为了克服ID3的缺点，而设计的。 用信道容量代替互信息作为特征判别力的度量 结点是一组特征，而不只一个特征,决策规则树,规则2,规则3,规则1,u1,u1,u1,u2,u2,u2,第八章 数据挖

9、掘,三、 基于信息论的示例学习方法（IBLE）,决策规则树结点,IBLE算法组成部分：预处理，建规则算法，建决策树算法，类判定算法,PE,NE,建 规 则,测 试,PEP,PEN,PEM,NEP,NEN,NEM,第八章 数据挖掘,4.1 问题的提出,四、 基于信息熵的规则组合,对数据库R（X，Y），从中挖出规则集 XY。如果又有一批新数据加入到数据库中，假设对这批新数据进行挖掘得出规则集：XY。如何将这些规则集组合起来?,数据挖掘过程得后处理,4.2 规则熵,H（ XY ）= -P（ xy ）log P（ xy ）,其中： 规则 xy 规则集 XY,规则熵规则集平均不确定性的度量,第八章 数据挖掘,4.3 利用规则熵进行规则组合,四、 基于信息熵的规则组合,将两规则集 XY、XY进行组合时，若组合规则集的规则熵最小，则这种组合方法为最佳。,4.4 示例,R1,R2,第八章 数据挖掘,四、 基于信息熵的规则组合,4.4 示例,R（合并）,规则1可以