1、1第十一讲第十一讲 分类方法分类方法本讲讲授目标：本讲讲授目标：1. 分类的基本概念分类的基本概念2. 决策树方法决策树方法 3. 决策树方法的评价决策树方法的评价 2一. 分类的基本概念分类的基本概念 数据分类（数据分类（data classfication）是数据挖）是数据挖掘的主要内容之一，主要是通过分析训练掘的主要内容之一，主要是通过分析训练数据样本，产生关于类别的精确描述。这数据样本，产生关于类别的精确描述。这种类别通常由分类规则组成，可以用来对种类别通常由分类规则组成，可以用来对未来的数据进行分类和预测。未来的数据进行分类和预测。 3数据分类过程数据分类过程第第1步：建立一个模型，
2、描述给定的数据类集步：建立一个模型，描述给定的数据类集或概念集（简称训练集）。或概念集（简称训练集）。 通过分析由属性描述的数据库元组来构造模型。通过分析由属性描述的数据库元组来构造模型。用于建立模型的元组集称为训练数据集，其中用于建立模型的元组集称为训练数据集，其中每个元组称为训练样本。如果训练样本的类别每个元组称为训练样本。如果训练样本的类别是未知的，则称为无指导的学习（聚类）。学是未知的，则称为无指导的学习（聚类）。学习模型可用分类规则、决策树和数学公式的形习模型可用分类规则、决策树和数学公式的形式给出。式给出。第第2步：使用模型对数据进行分类。包括评估步：使用模型对数据进行分类。包括评
3、估模型的分类准确性以及对类标号未知的模型的分类准确性以及对类标号未知的元组按模型进行分类。元组按模型进行分类。4数据分类过程数据分类过程训练数据训练数据分类算法分类算法分类规则分类规则(a) 学习学习分类规则分类规则新数据新数据测试数据测试数据(b) 分类分类5常用的分类规则挖掘方法常用的分类规则挖掘方法 分类规则的挖掘通常有以下几种方法分类规则的挖掘通常有以下几种方法 决策树方法决策树方法 贝叶斯方法贝叶斯方法 人工神经网络方法人工神经网络方法 约略集方法约略集方法 遗传算法遗传算法典型的分类规则挖掘算法有：典型的分类规则挖掘算法有： ID3 C4.5 DBlearn等等 6分类方法的评估标
4、准分类方法的评估标准 准确率：模型正确预测新数据类标号的能力。准确率：模型正确预测新数据类标号的能力。 速度：产生和使用模型花费的时间。速度：产生和使用模型花费的时间。 健壮性：有噪声数据或空缺值数据时模型正确健壮性：有噪声数据或空缺值数据时模型正确分类或预测的能力。分类或预测的能力。 伸缩性：对于给定的大量数据，有效地构造模伸缩性：对于给定的大量数据，有效地构造模型的能力。型的能力。 可解释性：学习模型提供的理解和观察的层次。可解释性：学习模型提供的理解和观察的层次。7二. 决策树方法决策树方法 决策树（决策树（Decision Tree）又称为判定树，是运用）又称为判定树，是运用于分类的一
5、种树结构。其中的每个内部结点于分类的一种树结构。其中的每个内部结点（internal node）代表对某个属性的一次测试，）代表对某个属性的一次测试，每条边代表一个测试结果，叶结点（每条边代表一个测试结果，叶结点（leaf）代表）代表某个类（某个类（class）或者类的分布（）或者类的分布（class distribution），最上面的结点是根结点。），最上面的结点是根结点。 决策树提供了一种展示类似在什么条件下会得到决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。什么值这类规则的方法。 决策树的基本组成部分：决策结点、分支和叶结决策树的基本组成部分：决策结点、分支和叶结点。
6、点。8下图给出了一个商业上使用的决策树的例子。它表示了一个下图给出了一个商业上使用的决策树的例子。它表示了一个关心电子产品的用户是否会购买关心电子产品的用户是否会购买PC（buys_computer）的）的知识，用它可以预测某条记录（某个人）的购买意向。知识，用它可以预测某条记录（某个人）的购买意向。 Age? Credit_rating? student? yes no yes yes no 40 3040 yes no fair excellent 每个内部结点（方形框）代表对某个属性的一次检测。每个叶结点每个内部结点（方形框）代表对某个属性的一次检测。每个叶结点（椭圆框）代表一个类：（椭
7、圆框）代表一个类：buys_computers=yes 或者或者 buys_computers=no在这个例子中，样本向量为：在这个例子中，样本向量为： （age, student, credit_rating; buys_computers）被决策数据的格式为被决策数据的格式为:（age, student, credit_rating）输入新的被决策的记录，可以预测该记录隶属于哪个类。输入新的被决策的记录，可以预测该记录隶属于哪个类。9ID3算法算法 ID3算法的基本思想描述如下：算法的基本思想描述如下：step 1任意选取一个属性作为决策树的根结点，任意选取一个属性作为决策树的根结点，然后
8、就这个属性所有的取值创建树的分支；然后就这个属性所有的取值创建树的分支；step 2用这棵树来对训练数据集进行分类，如果用这棵树来对训练数据集进行分类，如果一个叶结点的所有实例都属于同一类，则以该类一个叶结点的所有实例都属于同一类，则以该类为标记标识此叶结点；如果所有的叶结点都有类为标记标识此叶结点；如果所有的叶结点都有类标记，则算法终止；标记，则算法终止；step 3否则，选取一个从该结点到根路径中没有否则，选取一个从该结点到根路径中没有出现过的属性为标记标识该结点，然后就这个属出现过的属性为标记标识该结点，然后就这个属性所有的取值继续创建树的分支；重复算法步骤性所有的取值继续创建树的分支；
9、重复算法步骤step 2； 10属性选择度量属性选择度量 ID3算法在树的每个结点上以信息增量算法在树的每个结点上以信息增量（information gain）作为度量来选择测）作为度量来选择测试属性。这种度量称为属性选择度量或分试属性。这种度量称为属性选择度量或分裂的优良性度量。裂的优良性度量。 选择具有最高信息增益（或最大熵压缩）选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。该属性的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需要的信使得对结果划分中的样本分类所需要的信息量最小，并确保找到一棵简单的（但不息量最小，并确保找到一棵简单的（但不一定是最简单
10、的）决策树。一定是最简单的）决策树。 11Information Gain 信息量（信息量（Information）设设S是有是有s个训练样本数据的集合，类标号个训练样本数据的集合，类标号属性具有属性具有m个不同值，定义个不同值，定义m个不同类个不同类Ci（i=1,2,m），），si是类是类Ci中的样本数，则对中的样本数，则对一个给定的训练样本分类所需要的信息量为：一个给定的训练样本分类所需要的信息量为：其中其中pi是任意样本属于是任意样本属于Ci的概率，可用的概率，可用si/s来来估计。估计。 熵（熵（Entropy） 设属性设属性A具有具有k个不同值个不同值a1,a2,ak，则可用属性，则
11、可用属性A将将S划分为划分为k个子集个子集S1,S2,Sk，Sj中包含的样中包含的样本在属性本在属性A上具有值上具有值aj。如果选择。如果选择A作为测试属性，作为测试属性，则这些子集对应于由包含集合则这些子集对应于由包含集合S的结点生长出来的结点生长出来的分枝。设的分枝。设sij是子集是子集Sj中类中类Ci的样本数，则按照的样本数，则按照A划分成子集的熵为：划分成子集的熵为： 信息增益（信息增益（Information Gain），表示系统由于分），表示系统由于分类获得的信息量。由系统熵的减少值定量描述。类获得的信息量。由系统熵的减少值定量描述。用属性用属性A分类后的信息增益为：分类后的信息增
12、益为：Gain(A) = I (s1, s2, , sm) E(A)12Information Gain13例子 顾客数据库训练数据集如下表所示顾客数据库训练数据集如下表所示 C1：yes C2: noS1=9 S2=5I(S1,S2)=-9/14*log(9/14)-5/14*log(5/14)=0.94计算计算age属性的信息熵：属性的信息熵：age:40S11=2 S21=3 I(S11,s21)=0.971S12=4 S22=0 I(S12,S22)=0S13=3 S23=2 I(S13,S23)=0.971E(age)=5/14*I(S11,S21)+4/14*I(S12,S22)+
13、5/14*I(S13,S23) = 0.694Gain(age)=I(s1,s2)- E(age) =0.24614 所有属性的熵： Gain（age）=0.246Gain（income）= 0.029 Gain（student）= 0.151 Gain（credit _rating）=0.048 由于属性由于属性age在所有属性中具有最高的信在所有属性中具有最高的信息增益，因此它被选择为测试属性。创建息增益，因此它被选择为测试属性。创建一个以一个以age为标记的结点，并对每一个属性为标记的结点，并对每一个属性值引出一个分枝。落在分枝值引出一个分枝。落在分枝age=“3140”的样本都属于同一
14、类的样本都属于同一类“yes” ,该分枝的端该分枝的端点应该创建一个叶结点。点应该创建一个叶结点。 15age40 3140 16剪枝剪枝 剪枝常常利用统计学方法，去掉最不可靠、剪枝常常利用统计学方法，去掉最不可靠、可能是噪音的一些枝条。剪枝方法主要有可能是噪音的一些枝条。剪枝方法主要有两类：同步修剪和迟滞修剪。两类：同步修剪和迟滞修剪。17由决策树提取分类规则由决策树提取分类规则 从根结点到叶结点的每一条路径创建一条分类规则，路径从根结点到叶结点的每一条路径创建一条分类规则，路径上的每一个上的每一个“属性值属性值”对为规则的前件（即对为规则的前件（即IF部分）的部分）的一个合取项，叶结点为规
15、则的后件（即一个合取项，叶结点为规则的后件（即THEN部分）。部分）。 例例对于对于buys_computer的决策树可提取以下分类规的决策树可提取以下分类规则：则：IF age=30AND studentno THEN buys_computernoIF age40AND credit _ratingexcellent THEN buys_computernoIF age40AND credit _ratingfair THEN buys_computeryes18三. 决策树方法的评价决策树方法的评价 决策树有如下优点：决策树有如下优点：（1）速度快：计算量相对较小，且容易转化成分）速度快
16、：计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的谓词。例如，分裂条件就能够唯一确定一条分类的谓词。例如，沿着结点沿着结点Age-Credit Rating-no走下来就能得走下来就能得到一条谓词：到一条谓词：if there is a person (age40) and (credit rating is excellent) then he will not buy a computer.（2）准确性高：挖掘出的分类规则准确性高，便）准确性高：挖掘出的分类规则准确性高，便于理解。于理解。 1
17、9三. 决策树方法的评价决策树方法的评价 一般决策树的劣势：一般决策树的劣势：（1）缺乏伸缩性：由于进行深度优先搜索，所以）缺乏伸缩性：由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集。一个算法受内存大小限制，难于处理大训练集。一个例子：在例子：在Irvine机器学习知识库中，最大可以允机器学习知识库中，最大可以允许的数据集仅仅为许的数据集仅仅为700KB，2000条记录。而现代条记录。而现代的数据仓库动辄存储几个的数据仓库动辄存储几个G-Bytes的海量数据。的海量数据。用以前的方法是显然不行的。用以前的方法是显然不行的。（2）为了处理大数据集或连续量的种种改进算法）为了处理大数据集或连续量的种种改进算法（离散化、取样）不仅增加了分类算法的额外开（离散化、取样）不仅增加了分类算法的额外开销，而且降低了分类的准确性。销，而且降低了分类的准确性。
