数据挖掘技术 赵卫东博士 复旦大学软件学院 wdzhao@fudan.edu.cn
1 数据挖掘技术 赵卫东 博士 复旦大学软件学院 wdzhao@fudan.edu.cn
且导理 D document for Review June 8. 2001 4.27 am 分类和预测 Mining your own business in banking using Intelligent Miner for Data What are banking business issues w to address them through mining algorithms 2
2 分类和预测
分类 ■对离散数据的分类称为分类,对数值数据的分类称为预测。 分类要解决的问题是为一个事件或对象归类,即确定一个 特定的对象属于哪一类。分类函数或分类模型(分类器) 分类模型是通过那些已知历史数据训练出来的。 这里用于建立模型的数据称为训练集,通常是已经掌握的历 史数据。 在训练集中每个对象都赋予一个类别的标记,不同的类别具 有不同的标记 分类就是通过分析训练集(决策表)中的数据,为每个类 别做岀准确的描述或建立分析模型或挖掘岀分类规则,然 后用这个分类规则对其它数据对象进行分类。 3
3 分类 ◼ 对离散数据的分类称为分类，对数值数据的分类称为预测。 ◼ 分类要解决的问题是为一个事件或对象归类，即确定一个 特定的对象属于哪一类。分类函数或分类模型(分类器) ◼ 分类模型是通过那些已知历史数据训练出来的。 ◼ 这里用于建立模型的数据称为训练集，通常是已经掌握的历 史数据。 ◼ 在训练集中每个对象都赋予一个类别的标记，不同的类别具 有不同的标记。 ◼ 分类就是通过分析训练集（决策表）中的数据，为每个类 别做出准确的描述或建立分析模型或挖掘出分类规则，然 后用这个分类规则对其它数据对象进行分类
决策树 新数据 判定树分类算法 分类 训练集 决策树 对数据进行分析 对未来迎行预题 对将要采取的 把客户,事 企业数 商业活动和业务系统 4
4 决策树 判定树分类算法 output 训练集 决策树 input 新数据 分类
使用决策树进行分类 决策树 个树形的结构 内部节点上选用一个属性进行分割 每个分叉都是分割的一个部分 叶子节点表示一个分类 决策树生成算法分成两个步骤 树的生成 开始,数据都在根节点 递归的进行数据分片 ■树的修剪:去掉一些可能是噪音或者异常的数据 决策树使用:对未知数据进行分割 ■按照决策树上采用的分割属性逐层往下,直到叶子节点
5 使用决策树进行分类 ◼ 决策树 ◼ 一个树形的结构 ◼ 内部节点上选用一个属性进行分割 ◼ 每个分叉都是分割的一个部分 ◼ 叶子节点表示一个分类 ◼ 决策树生成算法分成两个步骤 ◼ 树的生成 ◼ 开始，数据都在根节点 ◼ 递归的进行数据分片 ◼ 树的修剪：去掉一些可能是噪音或者异常的数据 ◼ 决策树使用: 对未知数据进行分割 ◼ 按照决策树上采用的分割属性逐层往下，直到叶子节点
决策树算法 基本算法(贪心算法) 自上而下分而治之的方法 开始时所有的实例都在根节点 属性都是分类型(如果是连续的,将其离散化) 所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规则或者一个统计的度量(如信息增 停止分割的条件 一个节点上的实例都属于同一个类别; ■没有属性可以再用于对数据进行分割
6 决策树算法 ◼ 基本算法（贪心算法） ◼ 自上而下分而治之的方法 ◼ 开始时所有的实例都在根节点 ◼ 属性都是分类型 (如果是连续的，将其离散化) ◼ 所有记录用所选属性递归的进行分割 ◼ 属性的选择是基于一个启发式规则或者一个统计的度量 (如信息增 益) ◼ 停止分割的条件 ◼ 一个节点上的实例都属于同一个类别； ◼ 没有属性可以再用于对数据进行分割
属性选择的统计度量 ■信息增益— information gain(ID3/C5.0) 所有属性假设都是分类型字段 ■经过修改之后可以适用于数值型字段 ■信息增益率(C4.5) 基尼指数— Gini index( IBM Intelligent Miner) 能够适用于分类和数值字段 Ⅹ检验 CHAID) 其他
7 属性选择的统计度量 ◼ 信息增益—Information gain (ID3/C5.0) ◼ 所有属性假设都是分类型字段 ◼ 经过修改之后可以适用于数值型字段 ◼ 信息增益率（C4.5) ◼ 基尼指数—Gini index (IBM Intelligent Miner) ◼ 能够适用于分类和数值字段 ◼ χ 2检验(CHAID) ◼ 其他
信息增益(ID3) 任意样本分类的期望信息: I(1s…Sm)=-ΣPilg2(p)(=1.m) 其中,数据集为S,m为S的分类数目,PS C为某分类标号,P为任意样本属于C的概率,s为分 类Ci上的样本数 由A划分为子集的熵: E(A)=∑(|1j|+…+|sm)/|s*I(S1j, A为属性,具有V个不同的取值 信息增益:Gain(A)=I(s1,S2…m)-E(A)
8 信息增益(ID3) ◼ 任意样本分类的期望信息： ◼ I(s1,s2,……,sm)=－∑Pi log2(pi) (i=1..m) ◼ 其中，数据集为S，m为S的分类数目， Pi ◼ Ci为某分类标号，Pi为任意样本属于Ci的概率， si为分 类Ci上的样本数 ◼ 由A划分为子集的熵： ◼ E(A)= ∑j(|s1j|+ ……+|smj|)/|s| * I(s1j， ……，smj) ◼ A为属性，具有V个不同的取值 ◼ 信息增益：Gain(A)= I(s1,s2,……,sm) － E(A) | | | | S Si
训练集 age income student credit_rating buys_ computer 40 OW yesfair yes >40 low yes excellent no 31.40|ow yes excellent yes 40 medium fair yes 40 medium no excellent no
9 训练集 age income student credit_rating buys_computer 40 medium n o fair yes >40 low yes fair yes >40 low yes excellent n o 31…40 low yes excellent yes 40 medium yes fair yes 40 medium n o excellent n o
使用信息增益进行属性选择 Class p: buys_computer =yes e(age) 1(2,3)又 Class n: buys_computer ="no q(40) 5 I(p,n)=I(9,5)=0.940 (3,2)=0.9 0.694 Compute the entropy for age Hence Gain(age)=/(p, n)-e(age) age pi (p,n) 40 320.971 Gain(income)=0.029 Gain(student)=0.151 Gain(credit rating)=0.048
10 使用信息增益进行属性选择 Class P: buys_computer = “yes” Class N: buys_computer = “no” I(p, n) = I(9, 5) =0.940 Compute the entropy for age: Hence Similarly age pi ni I(pi , ni ) 40 3 2 0.971 (3,2) 0.971 14 5 (4,0) 14 4 (2,3) 14 5 ( ) + = = + I E age I I ( _ ) 0.048 ( ) 0.151 ( ) 0.029 = = = Gain credit rating Gain student Gain income Gain(age) = I( p,n) − E(age) 0.694