监督学习

监督学习2012.04.05outline•基本概念•决策树推理•评估分类器•规则推理•基于关联规则的分类•朴素贝叶斯分类•支持向量机•K-近邻学习•分类器的集成基本概念•监督学习（分类/归纳学习）•训练数据集和测试数据集•分类精准度•学习过程决策树推理•决策树决策节点叶子节点（类标）可信度(conf)：x/y支持度（sup):x/D关联规则决策树推理•学习算法分治策略:递归的对训练数据进行分隔。终止条件决策树推理•混杂复杂度混杂度函数熵（Entropy）信息增益（InformationGain）决策树推理熵（Entropy）决策树推理信息增益决策树推理•处理连续属性二元分割分割阈值（信息增益最大化）例如：属性Ai{v1,v2,v3,……,vr},其中元素以生序排列vi和vi+1间的所有阈值在划分效果上是一样的{V1,V2,V3,……,Vi}{Vi+1,Vi+2,……,Vr}在属性Ai上，有r-1种可能的分割，逐一进行评价。从几何角度看一棵完全基于连续属性构建的决策树代表了数据空间的一个划分.例如:决策树推理•其他一些问题过度拟合(overfitting)一个决策树算法递归地划分数据，直到不纯净度为0或没有其他属性了。这个过程肯能会得到深度很大的树，其中很多叶子节点只覆盖很少数目的训练实例。这样的学习结果是意义不大的，决策树不能很好的泛化到所有数据上。剪枝(TreePruning)预剪枝：提早结束树的构建过程。后剪枝：树构建完毕之后再剪枝。规则剪枝：将决策树转换为规则集合后，通过删去某些条件使得规则变短和变少。决策树推理评估分类器•分类精准度•评估方法Holdout集合：划分数据集D的方法随机采样按时间先后（数据集是不断积累的）多次随机采样交叉验证数据集合较小评估分类器•查准率、查全率、F-score和平衡点正例类别（PositiveClass）和负例类别(NegativeClass)P=R规则推理•序列化覆盖训练样例规则1规则2规则3规则推理算法1（有序化的规则，OrderedRules）不预先定义好学习哪个类的规则，不同的类的规则在最终决策列表中次序可能是交叉混合的。在这个算法中，规则在决策列表中的次序非常重要。规则推理算法2（有序化的类，OrderedClasses）学习完一个类的所有规则，然后去学习另外一个类的规则。在最终的决策列表中，同一个类的所有规则是放在一起的。每一个类中规则的次序不再重要，但是决策表中类的次序非常重要。规则推理•规则学习：Learn-One-Rule函数规则推理Learn-One-Rule-2growRule()函数R:av1,……,avkclassR+:av1,……,avk,avk+1classR+的评估函数的信息增益标准：p0和n0分别是R所涵盖的正例和负例的个数，p1和n1分别是R+所涵盖的正例和负例的个数PruneRule()函数对一个规则进行修剪时，对BestRule中的所有条件的所有子集，我们删除最大化以下函数的子集：p和n分别是当前规则和修剪后规则所涵盖的PrunePos中的样例的数目规则推理•Separate-and-Conquer与Divide-and-Conquer的对比规则推理在每一步中，评估所有的属性-值对（条件），然后选择一个。在每一步中，决策树评估所有的属性，然后选择一个属性把数据非为m个不相交的子集，其中m是被选中的属性的不同值的数目。决策树学习在一步中，Divide-and-Conquer策略产生m条规则，而Separate-and-Conquer只产生一条规则。基于关联规则的分类•使用类关联规则进行分类•使用类关联规则作为分类属性•使用古典的关联规则分类基于关联规则的分类•使用类关联规则进行分类1.决策树和规则推理系统没有minsup和minconf的限制2.CAR的挖掘不能使用连续的属性,但是决策树和规则推理却可以.基于关联规则的分类类关联规则的挖掘规则剪枝（消除冗余）多个不同的最低支持度数据集里的类分布可能很不均匀，假设D：C(Y和N)，99%Y，1%Nifminsup=1.5%,挖掘不到类N的规则ifminsup=0.2%,挖掘到大量N的规则对于不同的类，赋予不同的最低支持度minsupi，使用全局最低支持度t_minsup:类Ci在数据集里的实例数目基于关联规则的分类参数选择（最低支持度、最低可信度）数据格式（事务数据格式）使用规则构建分类器使用最强的类规则（对于每一个实例，算法找到覆盖这个实例的最强规则）选择规则的一个子集进行分类（与序列化覆盖算法类似）CARSDLDL中的规则是基于S中各个规则的排序，另外L中应该包含一个默认类基于关联规则的分类•使用类关联规则作为分类属性关联规则作为分类属性对原始数据集进行增强，然后使用传统的分类器（决策树或朴素贝叶斯分类器）。•使用古典的关联规则分类在推荐系统中广泛应用，推荐系统本质上是一个分类预测系统。使用古典关联规则的最大的好处是：规则的右侧可以使任何的商品。而传统的分类算法中，只能针对一组预定义好的类别。朴素贝叶斯分类给定一个测试样例d后估计它的后验概率：𝑃𝑟𝐶=𝑐𝑗𝑑数据集D中,令𝐴1,𝐴2,……,𝐴|𝐴|为用离散值表示的属性集合，令C为具有|C|个不同值的类别属性，即𝑐1,𝑐2,……,𝑐|𝑐|。预测值就是类别𝑐𝑗使得最大。根据贝叶斯准则，可表示为朴素贝叶斯分类条件独立性假设：设所有属性都是条件独立于类别C=𝑐𝑗。……Mi是Ai可能取值的总数朴素贝叶斯文本分类•概率框架用于文本分类的朴素贝叶斯学习方法是在一个概率生成模型上推导的。模型假设每一个文档由一个参数化概率分布生成，这个分布是由一些隐藏参数决定的。生成模型主要基于两个假设：1.数据（文档）由一个混合模型生成。2.混合模型的每一个成分和类别一一对应。朴素贝叶斯文本分类令K为混合模型中的成分参数，并且第j个分布的参数为。令为所有成分参数的集合。混合模型生成一篇文档的过程：1.根据混合权重选择一个混合成分（类别）；2.根据对应的混合成分生成文档di,由分布决定，更准确的说是由决定的。文档di由混合模型生成的概率可以全概率展开在所有的混合成分上。朴素贝叶斯文本分类•朴素贝叶斯模型朴素贝叶斯分类将每篇文档看作一“袋子”的词。生成模型做了一下假设：1.文档中的词都是独立于语境生成的。2.单词被生成的概率是与它在文档中的位置无关的。每个文档遵循单词的多项式分布,作了与文档长度相同次数的独立实验.单词从给定的词典中提取。给定类别后一篇文档的生成概率：其中𝑁𝑡𝑖是出现在𝑑𝑖中的次数，并且多项式分布朴素贝叶斯文本分类参数估计：分类：支持向量机支持向量机是一个线性的学习系统，可以用于两类的分类问题。令训练集合D为，其中是一个r维的输入向量，𝑦𝑖是它的类标记输出值，并且𝑦𝑖取{-1，1}。为了构造一个分类器，支持向量机寻找一个线性函数：如果，那么𝑥𝑖被赋予正类，否则赋予负类。本质上支持向量机就是在寻找一个超平面：这个超平面能够区分正类和负类的样例，被称为决策边界或是决策面。支持向量机•线性支持向量机：可分的情况中w为超平面法向量。最大化正例和负例之间的边距。令𝑑+（或𝑑−)为分割超平面离正例或（负例）的最近距离。支持向量机𝑥𝑖到超平面的垂直欧式距离是，𝑥𝑠为超平面上一点；同理所以，决策边界在𝐻+和𝐻−之间一半的地方。支持向量机寻找最大边距的分割超平面，这是一个优化问题。最大化边距等价于最小化并且满足支持向量机完整的学习问题就是解决下列约束最小化问题目标函数:支持向量机•线性支持向量机：数据不可分的情况数据线性可分得情况是一种理想情况。实际上，训练数据是有噪声的，也就是说因为某些原因存在着误差。允许数据中的误差，放松边距约束，引入松弛变量在目标函数中为误差加入惩罚项，将目标函数改为：其中C=0，是一个事先指定的参数。经常使用K=1的情况。支持向量机新的优化问题是：为拉格朗日乘子支持向量机•非线性支持向量机：核方法将原始的数据变换到另一个空间（通常是更高维的空间），这样在变换后的空间中可以使用线性决策边界分割正例和负例。支持向量机总结：支持向量机是一个线性学习系统，用最大边距决策边界来分割正例和负例。非线性的决策边界可以用原始数据向更高维的特征空间变换得到。因为学习算法和核函数是相互独立的，所以核函数可以单独地使用。局限：1.支持向量机仅仅在实数范围内有效。2.支持向量机只允许二类分类。3.支持向量机产生的超平面很难被认知和理解。K-近邻学习迫切学习方法：在测试之前学习得到了数据对应的模型。惰性学习方法：学习过程仅仅在测试样例需要分类时发生。算法KNN（D,d,k）1.计算d和D中所有样例的距离；2.选择D中离d最近的k个样本，记为P；3.将P中最经常出现的类别赋予d。K近邻算法最关键的部分是距离（相似度）函数。对于关系型数据，经常使用欧式距离。对于文本数据，余弦相似度很常用。分类器的集成•Bagging训练：生成K个样本集合，每个样本集合都是有放回的从D中随机抽取得到。对每个样本集合都构造一个分类器，将得到K个分类器。所有的分类器由同样的学习算法得到。测试：对每个测试样例进行分类，由K个分类投票决定。占多数的类别就是测试样例的类别。•Boosting训练：生成一系列的分类器，每一个分类器都依赖于之前的一个，为了减少分类器的错误，之前分类器错分的样本会被赋予更高的权重。测试：对每一个测试样例，整合这一系列的分类器的所有结果，就可以给出最终的结果。