第7章-分类

数据挖掘天津大学计算机科学与技术学院喻梅目录CONTENTS27.17.27.37.4分类概述决策树朴素贝叶斯分类惰性学习法7.57.6神经网络分类模型评估Chapter7.1分类概述47.1分类概述什么是分类？•分类就是根据以往的数据和结果对另一部分数据进行结果的预测。•模型的学习在被告知每个训练样本属于哪个类的“指导”下进行新数据使用训练数据集中得到的规则进行分类分类的基本过程：学习阶段：建立一个分类模型，描述预定数据类或概念集。分类阶段：即使用分类模型，对将来的或未知的对象进行分类。评估模型的预测准确率如果准确率可以接受，那么使用该模型来分类标签为未知的样本。数据集：•训练集、测试集、预测数据集57.1分类概述分类与预测•不同点–分类是预测类对象的分类标号（或离散值），根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据。–预测是建立连续函数值模型评估无标号样本类，或评估给定样本可能具有的属性值或值区间，即用来估计连续值或量化属性值，比如预测空缺值。•相同点–分类和预测的共同点是两者都需要构建模型，都用模型来估计未知值。预测中主要的估计方法是回归分析。67.1分类概述分类的相关知识：–1、信息熵信息熵用来衡量事件的不确定性的大小，计算公式如下：𝐼𝑛𝑓𝑜𝑟𝑥=−𝑝𝑥×𝑙𝑜𝑔2𝑝(𝑥)信息熵具有可加性，即多个期望信息，计算公式如下：𝐼𝑛𝑓𝑜𝑟𝑋=−𝑝𝑥𝑖×𝑙𝑜𝑔2𝑝(𝑥𝑖)𝑚𝑖=177.1分类概述分类的相关知识：–2、信息增益信息增益表示某一特征的信息对类标签的不确定性减少的程度。𝑔𝐷𝐴=𝐼𝑛𝑓𝑜𝑟𝐷−𝐼𝑛𝑓𝑜𝑟𝐷|𝐴其中𝐼𝑛𝑓𝑜𝑟𝐷|𝐴是在特征A给定条件下对数据集合D进行划分所需要的期望信息，它的值越小表示分区的纯度越高，计算公式如式(7-4)所示。𝐼𝑛𝑓𝑜𝑟𝐷|𝐴=|𝐷𝑗||𝐷|𝑛𝑗=1×𝐼𝑛𝑓𝑜(𝐷𝑗)(7-4)其中n是数据分区数，|𝐷𝑗|表示第j个数据分区的长度，|𝐷𝑗||𝐷|表示第j个数据分区的权重。87.1分类概述例7.1信息增益的计算表7-1是带有标记类的训练集D，训练集的列是一些特征，表中最后一列的类标号为是否提供贷款，有两个不同的取值，计算按照每个特征进行划分的信息增益。表7-1贷款申请的训练集ID学历婚否是否有车收入水平是否提供贷款123456789101112131415专科专科专科专科专科本科本科本科本科本科研究生研究生研究生研究生研究生否否是是否否否是否否否否是是否否否否是否否否是是是是是否否否中高高中中中高高很高很高很高高高很高中否否是是否否否是是是是是是是否97.1分类概述①根据公式计算信息熵𝐼𝑛𝑓𝑜𝑟𝐷。𝐼𝑛𝑓𝑜𝑟𝐷=−915×𝑙𝑜𝑔2915−615×𝑙𝑜𝑔2615=0.971②计算按照每个特征进行划分的期望信息，A代表特征“学历”，B代表特征“婚否”，C代表特征“是否有车”，E代表特征“收入水平”。𝐼𝑛𝑓𝑜𝑟𝐷|𝐴=515×−25𝑙𝑜𝑔225−35𝑙𝑜𝑔235+515×−35𝑙𝑜𝑔235−25𝑙𝑜𝑔225+515×(−45𝑙𝑜𝑔245−15𝑙𝑜𝑔215)=0.888𝐼𝑛𝑓𝑜𝑟𝐷|𝐵=𝐼𝑛𝑓𝑜𝑟𝐷|𝐵=1015×−610𝑙𝑜𝑔2610−410𝑙𝑜𝑔2410+515×−55𝑙𝑜𝑔255=0.647𝐼𝑛𝑓𝑜𝑟𝐷|𝐶=915×−69𝑙𝑜𝑔269−39𝑙𝑜𝑔239+615×−66𝑙𝑜𝑔266=0.951𝐼𝑛𝑓𝑜𝑟𝐷|𝐸=515×−45𝑙𝑜𝑔245−15𝑙𝑜𝑔215+615×−26𝑙𝑜𝑔226−46𝑙𝑜𝑔246+415×(−44𝑙𝑜𝑔244)=0.608③计算信息增益𝑔𝐷𝐴=𝐼𝑛𝑓𝑜𝑟𝐷−𝐼𝑛𝑓𝑜𝑟𝐷|𝐴=0.083𝑔𝐷𝐵=𝐼𝑛𝑓𝑜𝑟𝐷−𝐼𝑛𝑓𝑜𝑟𝐷|𝐵=0.324𝑔𝐷𝐶=𝐼𝑛𝑓𝑜𝑟𝐷−𝐼𝑛𝑓𝑜𝑟𝐷|𝐶=0.019𝑔𝐷𝐸=𝐼𝑛𝑓𝑜𝑟𝐷−𝐼𝑛𝑓𝑜𝑟𝐷|𝐸=0.363107.1分类概述分类的相关知识：–3、信息增益率信息增益率是指按照某一特征进行划分的信息增益与训练集关于这个特征的信息熵的比值。𝑔𝑟𝐷,𝐴=𝑔𝐷𝐴𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜𝑟𝐴(𝐷)其中：𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜𝑟𝐴𝐷=−|𝐷𝑗||𝐷|×𝑙𝑜𝑔2(|𝐷𝑗||𝐷|)𝑛𝑖=1117.1分类概述例7.2信息增益率的计算基于例7.1的数据，计算按照每个特征进行划分的信息增益率。解：①根据例7.1计算出的按照每个特征划分的信息增益，A代表特征“学历”，B代表特征“婚否”，C代表特征“是否有车”，E代表特征“收入水平”，计算𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜𝑟𝐴𝐷。𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜𝑟𝐴𝐷=−515×𝑙𝑜𝑔2515−515×𝑙𝑜𝑔2515−515×𝑙𝑜𝑔2515=1.585𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜𝑟𝐵𝐷=−1015×𝑙𝑜𝑔21015−515×𝑙𝑜𝑔2515=0.918𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜𝑟𝐶𝐷=−915×𝑙𝑜𝑔2915−615×𝑙𝑜𝑔2615=0.971𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜𝑟𝐸𝐷=−515×𝑙𝑜𝑔2515−615×𝑙𝑜𝑔2615−415×𝑙𝑜𝑔2415=1.566②按照公式(7-5)计算信息增益率。𝑔𝑟𝐷,𝐴=0.0831.585=0.052𝑔𝑟𝐷,𝐵=0.3240.918=0.353𝑔𝑟𝐷,𝐶=0.4200.971=0.433𝑔𝑟𝐷,𝐸=0.3631.566=0.232127.1分类概述分类的相关知识：–4、基尼系数基尼指数是度量数据分区或者训练数据的不纯度。𝐺𝑖𝑛𝑖𝐷=1−𝑝𝑖2𝑚𝑖=1其中𝑝𝑖是数据集合D中任何一个记录属于𝐶𝑖类的概率，可通过|𝐶𝑖,𝐷||𝐷|进行计算，|𝐶𝑖,𝐷|是D中属于𝐶𝑖类的集合的记录个数，|𝐷|是所有记录的个数。如果所有的记录都属于同一个类，则𝑝𝑖=1，m是分区数量。基尼指数考虑的是二元化，即将某一特征中的数值分为两个子集，然后进行划分。如果按照特征A作为数据的二元划分准则将D分成𝐷1和𝐷2，则D的基尼指数为：𝐺𝑖𝑛𝑖𝐴𝐷=|𝐷1||𝐷|Gini(𝐷1)+|𝐷2||𝐷|Gini(𝐷2)对于属性A的二元划分导致的不纯度降低为∆𝐺𝑖𝑛𝑖𝐴=𝐺𝑖𝑛𝑖𝐷−𝐺𝑖𝑛𝑖𝐴𝐷（7-9）137.1分类概述例7.3计算属性的不纯度降低值根据表7-1中的数据计算“学历”属性的基尼指数。解①使用基尼指数计算公式(7-7)计算D的不纯度：𝐺𝑖𝑛𝑖𝐷=1−9152−6152=0.48②计算属性“学历”的基尼指数。此特征有三个取值：“专科”、“本科”、“硕士”。所以划分值有三个，即三种划分集合，分别为：以“专科”划分：{专科}、{本科、研究生}。以“本科”划分：{本科}、{专科、研究生}。以“研究生”划分：{研究生}、{专科、本科}。考虑集合{研究生}、{本科，专科}，D被划分成两个部分，基于这样的划分计算基尼指数为：𝐺𝑖𝑛𝑖本科，专科、研究生𝐷=1015Gini(𝐷1)+515Gini(𝐷2)=1015×(1-(12)2−(12)2)+515×(1-(15)2−(45)2)=0.44147.1分类概述例7.3计算属性的不纯度降低值类似地可以求出属性“学历”其余子集的基尼指数：以“专科”划分的基尼指数为：𝐺𝑖𝑛𝑖本科，研究生、专科𝐷=1015Gini(𝐷1)+515Gini(𝐷2)=1015×(1-(310)2−(710)2)+515×(1-(25)2−(35)2)=0.44以“本科”划分的基尼指数为：𝐺𝑖𝑛𝑖专科，研究生、本科𝐷=1015Gini(𝐷1)+515Gini(𝐷2)=1015×(1-(25)2−(35)2)+515×(1-(25)2−(35)2)=0.48选择基尼指数最小值0.44作为属性“学历”的基尼指数，因此属性“学历”的不纯度降低值为：∆𝐺𝑖𝑛𝑖𝐴=𝐺𝑖𝑛𝑖𝐷−𝐺𝑖𝑛𝑖𝐴𝐷=0.48−0.44=0.04同样可以求出每个属性的基尼指数及不纯度降低值。157.1分类概述分类的相关知识：–5、过拟合通常，模型为了较好拟合训练数据会变得比较复杂，模型复杂的表现就是参数过多。虽然模型在训练数据上有较好的效果，但是对未知的测试数据可能结果会不好，这种现象叫做过拟合。Chapter7.2决策树决策树基本概念：决策树算法的基础是二叉树，但不是所有的决策树都是二叉树，还有可能是多叉树，如图所示。177.2决策树（1）构造决策树决策树构造过程如下。①输入数据，主要包括训练集的特征和类标号。②选取一个属性作为根节点的分裂属性进行分裂。③对于分裂的每个分支，如果已经属于同一类就不再分了，如果不是同一类，依次选取不同的特征作为分裂属性进行分裂，同时删除已经选过的分列属性。④不断的重复③，直到到达叶子节点，也就是决策树的最后一层，这时这个节点下的数据都是一类了。⑤最后得到每个叶子节点对应的类标签以及到达这个叶子节点的路径。（2）决策树的预测得到由训练数据构造的决策树以后就可以进行预测了，当待预测的数据输入决策树的时候，根据分裂属性以及分裂规则进行分裂，最后即可确定所属的类别。187.2决策树决策树算法过程设A是分裂属性，根据训练数据，A具有n个不同值{a1,a2,…,an}，选取A作为分裂属性进行分裂时有如下三种情况。①A是离散值：对A的每个值aj创建一个分支，分区Dj是D中A上取值为aj的类标号元组的子集，如图7-3（a）所示。②A是连续的：产生两个分支，分别对应于A≤split_point和Asplit_point，其中split_point是分裂点，数据集D被划分为两个分区，D1包含D中A≤split_point的类标号组成的子集，而D2包括其他元组，如图7-3（b）所示。③A是离散值且必须产生二叉树（由属性选择度量或所使用的算法指出）：结点的判定条件为“A∈SA?”，其中SA是A的分裂子集。根据A的值产生两个分支，左分支标记为yes，使得D1对应于D中满足判定条件的类标记元组的子集；右分支标记为no，使得D2对应于D中不满足判定条件的类标记元组的子集，如图7-3（c）所示。197.2决策树Aa1a2an……AA∈SA?(a)(b)(c)。图7-3属性分裂的三种情况属性分裂的三种情况ID3算法的构建方法和决策树的构建基本是一致的，不同的是分裂节点的特征选择的标准。该算法在分裂节点处将信息增益作为分裂准则进行特征选择，递归的构建决策树。ID3算法的步骤如下：①输入数据，主要包括训练集的特征和类标号。②如果所有实例都属于一个类别，则决策树是一个单结点树，否则执行③。③计算训练数据中每个特征的信息增益。④从根节点开始选择最大信息增益的特征进行分裂。依次类推，从上向下构建决策树，每次选择具有最大信息增益的特征进行分裂，选过的特征后面就不能继续进行选择使用了。⑤不断的构建决策树，至没有特征可以选择或者分裂后的所有元组属于同一类别时候停止构建。⑥决策树构建完成，进行预测。207.2决策树ID3例7.4使用ID3算法进行分类预测表7-2和表7-3为训练数据和测试数据，其中“患病与否”是类标记，使用ID3算法构建决策树然后进行分类预测。217.2决策树ID3表7-2某疾病患病情况的训练数据ID年龄吸烟史有无家族