数据仓库和数据挖掘决策树

分类

分类是数据挖掘中重要的任务分类的目的是学会一个分类器（分类函数或模型），该分类器能把待分类的数据映射到给定的类别中。分类可用于预测。从利用历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行类预测。分类具有广泛的应用，例如医疗诊断、信用卡系统的信用分级、图像模式识别等。分类器的构造依据的方法很广泛：统计方法：包括贝叶斯法和非参数法等。机器学习方法：包括决策树法和规则归纳法。神经网络方法。其他，如粗糙集等。分类方法的类型从使用的主要技术上看，可以把分类方法归结为四种类型：基于距离的分类方法决策树分类方法贝叶斯分类方法规则归纳方法。本章将择选一些有代表性的方法和算法来介绍分类方法。分类问题的描述定义1给定一个数据库D={t1，t2，…，tn}和一组类C={C1，…，Cm}，分类问题是去确定一个映射f:DC，使得每个元组ti被分配到一个类中。一个类Cj包含映射到该类中的所有元组，即Cj={ti|f(ti)=Cj，1≤i≤n，而且ti

D}。例如，把学生的百分制分数分成A、B、C、D、F五类，就是一个分类问题：D是包含百分制分数在内的学生信息，C={A、B、C、D、F}。解决分类问题的关键是构造一个合适的分类器：从数据库到一组类别集的映射。一般地，这些类是被预先定义的、非交叠的。数据分类的两个步骤1．建立一个模型，描述预定的数据类集或概念集数据元组也称作样本、实例或对象。为建立模型而被分析的数据元组形成训练数据集。训练数据集中的单个元组称作训练样本，由于提供了每个训练样本的类标号，因此也称作有指导的学习。通过分析训练数据集来构造分类模型，可用分类规则、决策树或数学公式等形式提供。2．使用模型进行分类首先评估模型（分类法）的预测准确率。如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行分类。分类:定义分类任务就是通过学习得到一个目标函数f，把每个属性集x映射到一个预先定义的类标号y。分类模型可以用于以下目的：描述性建模——作为解释性工具，用于区分不同类对象。例如，根据动物的某些特性分为哺乳类、爬行类、鸟类、鱼类和两栖类预测性建模——用于预测未知记录的类标号。当给定未知记录的属性集上的值时，它自动地赋予未知样本类标号。表1脊椎动物的数据集名字体温表皮胎生水生动物飞行动物有腿冬眠类标号人类蟒蛇鲑鱼鲸鱼青蛙巨蜥蝙蝠鸽子猫豹纹鲨海龟企鹅豪猪鳗蝾螈恒温冷血冷血恒温冷血冷血恒温恒温恒温冷血冷血恒温恒温冷血冷血毛发鳞片鳞片毛发无鳞片毛发羽毛软毛鳞片鳞片羽毛刚毛鳞片无是否否是否否是否是是否否是否否否否是是半否否否否是半半否是半否否否否否否是是否否否否否否否是否否否是是是是是否是是是否是否是否否是否是否否否否否是否是哺乳类爬行类鱼类哺乳类两栖类爬行类哺乳类鸟类哺乳类鱼类爬行类鸟类哺乳类鱼类两栖类未知类标号的动物的预测名字体温表皮胎生水生动物飞行动物有腿冬眠类标号毒蜥冷血鳞片否否否是是？输入属性集x分类模型输出类标号y解决分类问题的一般方法分类技术是一种根据输入数据集建立分类模型的系统方法包括决策树分类法、基于规则的分类法、神经网络、支持向量机和贝叶斯分类法。这些技术都是用一种学习算法确定分类模型，该模型能很好的拟合输入数据中的类标号和属性集之间的联系。并能预测为之样本的标号。举例说明分类任务应用模型l归纳推论

学习模型模型Tid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

Tid

有房者

婚姻状况2

年收入

拖欠贷款

11

否

单身l

55K

?

12

是

已婚

80K

?

13

是

离异

110K

?

14

否

单身

95K

?

15

否

已婚

67K

?

10

学习算法决策树的例子有房婚姻状况年收入是否否否是没有已婚单身,离婚<80K>80K极快的属性训练数据模型:决策树Tid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

决策树的例子婚姻状况有房年收入是否否否是没有已婚单身,离异<80K>80KTid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

举例说明分类任务应用模型l归纳推论

学习模型模型Tid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

Tid

有房者

婚姻状况2

年收入

拖欠贷款

11

否

单身l

55K

?

12

是

已婚

80K

?

13

是

离异

110K

?

14

否

单身

95K

?

15

否

已婚

67K

?

10

学习算法申请模型到测试数据有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根申请模型到测试数据有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根申请模型到测试数据有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根申请模型到测试数据有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根申请模型到测试数据有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根申请模型到测试数据有房婚姻年收入是否否否是否已婚单身、离婚<80K>80K测试数据开始从树.的根举例说明分类任务应用模型l归纳推论

学习模型模型Tid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

Tid

有房者

婚姻状况2

年收入

拖欠贷款

11

否

单身l

55K

?

12

是

已婚

80K

?

13

是

离异

110K

?

14

否

单身

95K

?

15

否

已婚

67K

?

10

学习算法分类模型的评估分类模型的评估是根据检验记录准确率来评估的。例如：fij实际标号为i但被预测为j类的记录数。因此被分类模型正确的预测的样本总数为（f11+f00），而被错误预测的样本数为（f10

+f01）。类=1类=0类=1f11f10类=0f01f00准确率==差错率==决策树的创建方法常用的有ID3、C4.5、CART方法归纳起来如下：设Dt是与结点t相关联的训练记录集，而y={y1,y2,…,yc}是类标号。算法如下:1、如果Dt中所有记录都属于同一个类，则t是叶结点。2、如果Dt中包含属于多个类的记录，则选择一个测试条件，将记录划分为较小的子集。对于测试条件的每个输出，创建子女节点。Dt?Tid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

决策树算法拖欠贷款？有房否否是否有房否是No婚姻否是单身,离婚已婚年收入否<80K>=80K有房否YesNo婚姻否是单身,离婚已婚Tid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

决策树归纳的设计问题决策树归纳的学习算法必须解决两个问题：1、如何分裂训练记录？

树的增长过程每个递归都必须选择一个属性测试条件，将记录划分成较小的子集。为了实现这个步骤，算法必须提供不同类型的属性的测试条件，并提供评估每种测试条件的客观度量。2、如何停止分裂过程？需要有结束条件，一种树的生长过程。可能的策略是，直到所有的记录都属于同一各类，或所有记录都有相同的属性值。但可以使用其它标准提前终止树的生长过程。如何到规定测试条件?依靠属性类型标称属性序数属性连续属性1、标称属性二元切分多路切分婚姻单身,离婚已婚婚姻单身离婚已婚婚姻单身,离婚已婚离婚单身离婚序数属性也可以产生二元和多路划分，只要不违背序数值的有序性就可以对序数属性进行分组。多路-切分:使用一样多分割同样地清楚的价值.二元-切分:分到二个子集.

需要到查找最佳的分割2、序数属性Size小中大Size{中,

大}{小}Size{小,中}{大}或Size{小,大}{中}或3、连续属性测试条件可以使具有二元输出的比较测试（a<v）或（a>=v）,也可以是vi<=a<vi+1（i=1,…,k)年收入>80K?YesNo年收入?(i)二元(ii)多元<10K[10K,25K)[25K,50K)[50K,80K)>80K选择最佳划分的度量划分的策略.确定如何划分记录如何得到规定属性测试条件?如何确定最好的划分?确定终止的条件选择最佳划分的度量哪个测试条件是最好的?性别?C0:6C1:4C0:4C1:6C0:1C1:3C0:8C1:0C0:1C1:7车型?C0:1C1:0C0:1C1:0C0:0C1:1顾客ID?...男女家用运动豪华c1c10c20C0:0C1:1...c11选择最佳划分的度量选择最佳划分的度量是根据划分后子女节点不纯性的程度。不纯的程度越低，类分布越倾斜。例如，类分布为（1，0）的节点具有0不纯性，而均匀分布的节点(0.5,0.5)具有最高的不纯性。非-同类的,最高的不存度同类的,不纯度为0C0:10C1:0不纯性的度量Gini指标熵错误其中c是类的个数，p（i|t）表示给定结点t中属于类i的记录所占的比例。不纯性的度量:GINI节点N1计数类=00类=16节点N1计数类=01类=15节点N1计数类=03类=13二元分类问题不纯性度量之间的比较加权GINI指标

为了确定测试条件的效果，需要比较父结点（划分前）的不纯程度和子女结点（划分后）的不纯程度，它们的差越大，测试条件的效果越好。信息增益△是一种可以用来确定划分效果的标准

其中I()是给定结点的不纯性度量，N是父结点的记录总数，k是属性值的个数，N（Vi）是与子女节点vi相关的记录个数。二元属性的划分：

计算信息增益B?是没有节点N1节点N2Gini(N1)

=1–(5/7)2–(2/7)2

=0.408Gini(N2)

=1–(1/5)2–(4/5)2

=0.32Gini(孩子)

=7/12*0.408+

5/12*0.32

=0.371△=0.5-0.371=0.129多路划分加权Gini指标对于多路划分，需要计算每个属性值的Gini指标Gini({家用})=0.375Gini({运动})=0Gini({豪华})=0.219△=0.5-0.163=0.337△=0.5-0.468=0.032△=0.5-0.167=0.333连续属性的划分:Gini指标的计算Tid

有房者

婚姻状况

年收入

拖欠贷款

1

是

单身

125K

否

2

否

已婚

100K

否

3

否

单身

70K

否

4

是

已婚

120K

否

5

否

离异

95K

是

6

否

已婚

60K

否

7

是

离异

220K

否

8

否

单身

85K

是

9

否

已婚

75K

否

10

否

单身

90K

是

10

连续属性的划分:Gini指标的计算划分点排序值

一种算法为，从两个相邻的已排序属性之中选择中间值作为候选划分点分别计算每个划分点的Gini指标，产生最小Gini指标的点极为最佳划分点。共11个划分点第二种方法为，仅考虑位于具有不同类标号的两个相邻记录之间的候选划分点,只考虑两个划分点。决策树的剪枝基本的决策树构造算法没有考虑噪声，因此生成的决策树完全与训练例子拟合。在有噪声情况下，将导致过分拟合（Overfitting），即对训练数据的完全拟合反而使对现实数据的分类预测性能下降。现实世界的数据一般不可能是完美的，是可能缺值的（MissingValues）；数据是不完整的；含有噪声甚至是错误的。目的：消除决策树的过适应(OverFitting)问题实质：消除训练集中的异常和噪声两种方法：先剪枝法(Public算法)：提前停止树的构造后剪枝法(Sprint算法)：树完全生长后剪枝决策树剪枝算法1、先剪枝法(Public算法)：在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。2、后剪枝法（Post-Pruning）：是一种拟合+化简（fitting-and-simplifying）的两阶段方法。首先生成与训练数据完全拟合的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用到一个测试数据集合（TuningSet或AdjustingSet），如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子；否则停机。理论上讲，后剪枝好于先剪枝，但计算复杂度大。剪枝过程中一般要涉及一些统计参数或阈值（如停机阈值）。要防止过分剪枝（Over-Pruning）带来的副作用。基于距离的分类算法的思路定义2给定一个数据库D={t1，t2，…，tn}和一组类C={C1，…，Cm}。假定每个元组包括一些数值型的属性值：ti={ti1，ti2，…，tik}，每个类也包含数值性属性值：Cj={Cj1，Cj2，…，Cjk}，则分类问题是要分配每个ti到满足如下条件的类Cj：sim(ti，Cj)>=sim(ti，Cl)，Cl∈C，Cl≠Cj，其中sim(ti，Cj)被称为相似性。在实际的计算中往往用距离来表征，距离越近，相似性越大，距离越远，相似性越小。距离的计算方法有多种，最常用的是通过计算每个类的中心来完成。基于距离的分类算法的一般性描述算法1通过对每个元组和各个类的中心来比较，从而可以找出他的最近的类中心，得到确定的类别标记。算法1基于距离的分类算法输入：每个类的中心C1，…，Cm；待分类的元组t。输出：输出类别c。（1）dist=∞；//距离初始化（2）FORi:=1tomDO（3） IFdis(ci，t)<distTHENBEGIN（4） c←i；（5） dist←dist(ci，t)；（6） END.基于距离的分类方法的直观解释（a）类定义（b）待分类样例（c）分类结果K-近邻分类算法K-近邻分类算法（KNearestNeighbors，简称KNN）通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的K个训练数据，K个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类别。算法2K-近邻分类算法输入：训练数据T；近邻数目K；待分类的元组t。输出：输出类别c。（1）N=；（2）FOReachd∈TDOBEGIN（3）IF|N|≤KTHEN（4）N=N∪{d}；（5）ELSE（6） IF

u∈Nsuchthatsim(t，u)〈sim(t，d)THEN

BEGIN（7） N=N-{u}；（8） N=N∪{d}；（9） END（10）END（11）c=classtowhichthemostu∈N.

KNN的例子序号姓名 性别身高

类别 1Kristina 女1.6 矮2Jim 男2 高 3Maggie 女1.9 中等 4Martha 女1.88 中等 5Stephanie女1.7 矮 6Bob 男1.85 中等 7Kathy 女1.6 矮 8Dave 男1.7 矮 9Worth 男2.2 高 10Steven 男2.1 高 11Debbie 女1.8 中等 12Todd 男1.95 中等 13Kim 女1.9 中等 14Amy 女1.8 中等 15Wynette