朴素贝叶斯分类算法

第3章分类与回归3.1概述3.2决策树分类方法3.3贝叶斯分类方法3.4K-最近邻分类方法3.5神经网络分类方法3.6支持向量机3.7组合学习方法3.8不平衡数据分类问题3.9分类模型的评价3.10回归方法3.1概述分类的定义分类是数据挖掘中的一种主要分析手段分类的任务是对数据集进行学习并构造一个拥有预测功能的分类模型，用于预测未知样本的类标号，如：根据电子邮件的标题和内容检查出垃圾邮件根据核磁共振的结果区分肿瘤是恶性还是良性的根据星系的形状对它们进行分类划分出交易是合法或欺诈将新闻分类金融、天气、娱乐体育等分类与回归的区别分类和回归都有预测的功能，但是：分类预测的输出为离散或标称的属性；回归预测的输出为连续属性值；分类与回归的例子：预测未来某银行客户会流失或不流失，这是分类任务；预测某商场未来一年的总营业额，这是回归任务。分类的步骤分类的过程描述如下：1)首先将数据集划分为2部分：训练集和测试集。2)第一步：对训练集学习，构建分类模型。模型可以是决策树或分类规则等形式。3)第二步：用建好的分类模型对测试集分类评估该分类模型的分类准确度及其它性能。4)最后，使用分类准确度高的分类模型对类标号未知的未来样本数据进行分类。分类与聚类的区别分类因为使用了类标号属性，属于有监督的学习方法聚类，事先没有使用任何类标号信息，属于无监督的学习方法分类的应用目前分类与回归方法已被广泛应用于各行各业，如：股票预测信用评估医疗诊断市场营销图像分类等……数据挖掘中分类算法归类分类模型的学习方法大体上主要有以下几类基于决策树的分类方法贝叶斯分类方法K-最近邻分类方法神经网络方法支持向量机方法集成学习方法……回归分析回归分析可以对预测变量和响应变量之间的联系建模。在数据挖掘环境下，预测变量是描述样本的感兴趣的属性，一般预测变量的值是已知的，响应变量的值是我们要预测的。当响应变量和所有预测变量都是连续值时，回归分析是一个好的选择。回归分析包括：线性回归、非线性回归以及逻辑回归等。3.2决策树分类方法3.2.1决策树的基本概念3.2.1决策树的基本概念决策树(DecisionTree)是一种树型结构，包括：决策节点(内部节点)、分支和叶节点三个部分。其中：决策节点代表某个测试，通常对应于待分类对象的某个属性，在该属性上的不同测试结果对应一个分支。叶节点存放某个类标号值，表示一种可能的分类结果。分支表示某个决策节点的不同取值。决策树可以用来对未知样本进行分类，分类过程如下：从决策树的根节点开始，从上往下沿着某个分支往下搜索，直到叶结点，以叶结点的类标号值作为该未知样本所属类标号。典型决策树决策树分类例题演示1某银行训练数据下表，请利用决策树分类方法预测类标号未知的新样本{“是”,“5000~10000”,“2”,“是”,？}，其类标号属性为流失或不流失.是否定期存款数月业务频率是否投资是否流失否10000~200005~10不是不流失否5000~1000010是不流失否20000~300002不是流失……………首先，建立决策树存款数10000~20000不流失5000流失5000~10000月业务频率2~5220000~3000030000不流失不流失流失不流失流失=0然后，使用决策树对未知新样本分类：存款数10000~20000不流失5000流失5000~10000月业务频率2~5220000~3000030000不流失不流失流失不流失流失=0未知样本：{“是”,“5000~10000”,“2”,“是”,？}决策树分类例题演示2Tid有房者婚姻状态年收入拖欠贷款1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10训练数据集决策树模型有房者婚姻状态年收入YESNONONOYesNoMarriedSingle,Divorced80K80K应用模型测试数据有房者婚姻状态年收入YESNONONOYesNoMarriedSingle,Divorced80K80K有房者婚姻状态年收入拖欠房款NoMarried80K?10测试数据Startfromtherootoftree.有房者婚姻状态年收入YESNONONOYesNoMarriedSingle,Divorced80K80K有房者婚姻状态年收入拖欠房款NoMarried80K?10测试数据应用模型测试数据有房者婚姻状态年收入YESNONONOYesNoMarriedSingle,Divorced80K80K应用模型测试数据有房者婚姻状态年收入拖欠房款NoMarried80K?10测试数据有房者婚姻状态年收入YESNONONOYesNoMarriedSingle,Divorced80K80K应用模型测试数据有房者婚姻状态年收入拖欠房款NoMarried80K?10测试数据有房者婚姻状态年收入YESNONONOYesNoMarriedSingle,Divorced80K80K应用模型测试数据有房者婚姻状态年收入拖欠房款NoMarried80K?10测试数据有房者婚姻状态年收入YESNONONOYesNoMarriedSingle,Divorced80K80K分配拖欠房款属性为：“No”应用模型测试数据有房者婚姻状态年收入拖欠房款NoMarried80K?10测试数据3.2.2决策树的构建决策树在构建过程中需重点解决2个问题：(1)如何选择合适的属性作为决策树的节点去划分训练样本；(2)如何在适当位置停止划分过程，从而得到大小合适的决策树。1.决策树的属性选择虽然可以采用任何一个属性对数据集进行划分，但最后形成的决策树会差异很大。需要寻找合适的属性选择方法。属性选择是决策树算法中重要的步骤，常见的属性选择标准包括信息增益(informationgain)和Gini系数。信息增益是决策树常用的分枝准则,在树的每个结点上选择具有最高信息增益的属性作为当前结点的划分属性。Gini系数是一种不纯度函数，用来度量数据集的数据关于类的纯度。2.获得大小合适的树决策树学习的目的是希望生成能够揭示数据集结构并且预测能力强的一棵树，在树完全生长的时候有可能预测能力反而降低，为此通常需要获得大小合适的树。一般来说有两种获取方法:一种为定义树的停止生长条件,常见条件包括最小划分实例数、划分阈值和最大树深度等。另一种方法是对完全生长决策树进行剪枝，方法是对决策树的子树进行评估，若去掉该子树后整个决策树表现更好，则该子树将被剪枝。3.决策树构建的经典算法Hunt算法是许多经典决策树算法如ID3、C4.5的基础Hunt算法对决策树的建立过程描述如下，假定Dt是与结点t相关联的训练记录集，C={C1,C2,…,Cm}是类标号，Hunt算法的递归定义如下：(1)如果Dt中所有记录都属于同一个类Ci(1≤i≤m),那么t是叶结点，用类标号Ci进行标记。(2)如果Dt包含属于多个类的记录,则选择一个属性测试条件，将记录划分为更小的子集。对于测试条件的每个输出，创建一个子女节点，并根据测试结果将Dt中的记录分布到子女节点中，然后对每个子女节点递归调用该算法。3.2.3ID3分类算法DI3分类算法概述ID3分类算法由Quinlan于1986年提出它使用信息增益(informationgain)作为属性的选择标准。首先检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一个类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。基本概念与ID3分类算法相关的基本概念包括：信息熵信息增益信息熵熵(entropy,也称信息熵)用来度量一个属性的信息量。假定S为训练集，S的目标属性C具有m个可能的类标号值，C={C1,C2,…,Cm}，假定训练集S中，Ci在所有样本中出现的频率为(i=1,2,3,…,m)，则该训练集S所包含的信息熵定义为：熵越小表示样本对目标属性的分布越纯，反之熵越大表示样本对目标属性分布越混乱。miiimpppppEntropySEntropy1221log),...,,()(信息熵例题演示考虑数据集weather如下,求weather数据集关于目标属性playball的熵。outlooktemperaturehumiditywindplayballsunnyhothighweaknosunnyhothighstrongnoovercasthothighweakyesrainmildhighweakyesraincoolnormalweakyesraincoolnormalstrongnoovercastcoolnormalstrongyessunnymildhighweaknosunnycoolnormalweakyesrainmildnormalweakyessunnymildnormalstrongyesovercastmildhighstrongyesovercasthotnormalweakyesrainmildhighstrongno信息熵例题演示(续)解答：令weather数据集为S，其中有14个样本,目标属性playball有2个值{C1=yes,C2=no}。14个样本的分布为：9个样本的类标号取值为yes，5个样本的类标号取值为No。C1=yes在所有样本S中出现的概率为9/14，C2=no在所有样本S中出现的概率为5/14。因此数据集S的熵为：94.0145log145149log149)145,149()(22EntropySEntropy信息增益信息增益是划分前样本数据集的不纯程度(熵)和划分后样本数据集的不纯程度(熵)的差值。假设划分前样本数据集为S,并用属性A来划分样本集S，则按属性A划分S的信息增益Gain(S,A)为样本集S的熵减去按属性A划分S后的样本子集的熵：按属性A划分S后的样本子集的熵定义如下：假定属性A有k个不同的取值，从而将S划分为k个样本子集{S1,S2,…,Sk}，则按属性A划分S后的样本子集的信息熵为:其中|Si|(i,=1,2,…k)为样本子集Si中包含的样本数，|S|为样本集S中包含的样本数。信息增益越大，说明使用属性A划分后的样本子集越纯，越有利于分类。)()(),(SEntropySEntropyASGainAkiiiASEntropySSSEntropy1)(||||)(信息增益例题演示以数据集weather为例，设该数据集为S，假定用属性wind来划分S，求S对属性wind的信息增益。outlooktemperaturehumiditywindplayballsunnyhothighweaknosunnyhothighstrongnoovercasthothighweakyesrainmildhighweakyesraincoolnormalweakyesraincoolnormalstrongnoovercastcoolnormalstrongyessunnymildhighweaknosunnycoolnormalweakyesrainmildnormalweakyessunnymildnormalstrongyesovercastmildhighstrongyesovercasthotnormalweakyesrainmildhighstrongno信息增益例题演示(续)解答：(1)首先由前例计算得到数据集S的熵值为0.94；