分类_分类算法 - CSDN
精华内容
参与话题
  • 这一篇博客将介绍机器学习中另一个重要的任务——分类(classification),即找一个函数判断输入数据所属的类别,可以是二类别问题(是/不是),也可以是多类别问题(在多个类别中判断输入数据具体属于哪一个类别)...

    这一篇博客将介绍机器学习中另一个重要的任务——分类(classification),即找一个函数判断输入数据所属的类别,可以是二类别问题(是/不是),也可以是多类别问题(在多个类别中判断输入数据具体属于哪一个类别)。与回归问题(regression)相比,分类问题的输出不再是连续值,而是离散值,用来指定其属于哪个类别。分类问题在现实中应用非常广泛,比如垃圾邮件识别,手写数字识别,人脸识别,语音识别等。

    思考

    首先思考一个问题,能不能用回归问题的解法去求解分类问题呢?
    以二分类问题为例,对于类别1,我们假设其目标值为1,对于类别2,假设其目标值为-1。在回归问题中,我们需要找到一个函数,使得函数的预测值尽可能的接近目标值。如下图所示,为了方便可视化,假设每个样本只用两维特征表示。
    在这里插入图片描述

    上图中,蓝色的点目标值是1,代表类别1;红色的点目标值是-1,代表类别2。现在需要找到一个函数对这些点进行拟合,如图中绿线所代表的函数b+w1x1+w2x2=0b+w_1x_1+w_2x_2=0。对于一个样本点,如果其对应的函数值大于0,则认为其属于类别1,反之属于类别2。这么做看起来好像也是可以的,但现在我们考虑另外一种情况,如下图所示
    在这里插入图片描述

    此时,在类别1中加入了右下角这些点,如果仍然采用绿色那条线所代表的函数进行预测,这些新加入进来的点的误差将特别的大,为了缓解由此带来的误差,绿色的线将往右下角偏移,以此减少误差。但这么做明显是不符合常理的,误差虽然减少了,但也带来了更严重的分类类别错误问题。**造成这个问题的本质是损失函数定义的不恰当,回归问题种将损失函数定位为误差函数是因为回归的目标是尽可能拟合样本点,但分类问题的目标是尽可能将样本点分类到正确的类别中,仍然使用误差函数作为损失函数显然是不合适的。**会闹出这样的笑话:对于那些类别明显的点,回归问题求解的惩罚反而更加严重。另外对于多分类问题种,我们给每个类别指定一个对应的目标值,在机器看来这些目标值之间是有联系的,比如:类别1目标值指定为1,类别2目标值指定为2,类别3目标值指定为3……计算机在寻找样本之间的关系时,会默认类别2和类别3要比类别1和类别3更加有关联,因为3和2更加靠近。

    分类问题

    分类问题的求解过程同样可以分为三个步骤:
    1、确定一个模型f(x)f(x),输入样本数据xx,输出其类别;
    2、定义损失函数L(f)L(f),一个最简单的想法是计数分类错误的次数,L(f)=nδ(f(xn)y^n)L(f)=\sum_{n} \delta(f(x^n)\ne \hat{y}^n)
    3、找出使损失函数最小的那个最优函数。
    上面的做法中,我们寻找到的最优函数直接计算出了p(cx)p(c|x),即给出了样本xx属于每个类别cc的概率,这是一种解法。我们将其称作判别式(discrimination)方法,因为我们直接对样本所属类别进行了判断,相应的模型称作判别式模型。这一篇博客我们换一个角度思考,从另一个方向解决分类问题。下面以最简单的二分类为例,样本可以根据其类别标签被自然分为两类,那为什么我们不分别对每一类进行研究呢?是否可以发现每一类样本的特性呢?结合我们的研究目标:建模p(cx)p(c|x),借助概率论条件概率的知识,我们对其进行下转换:
    p(cx)=p(c,x)p(x)(1) p(c|x)=\frac{p(c,x)}{p(x)} \tag 1

    此时还需要求解联合概率分布p(c,x)p(c,x),基于贝叶斯定理,p(cx)p(c|x)可写为
    p(cx)=p(xc)p(c)p(x)(2) p(c|x)=\frac{p(x|c)p(c)}{p(x)} \tag 2

    对给定样本xxp(x)p(x)与类别无关,因此我们需要考虑的只剩下p(xc)p(x|c)p(c)p(c),惊讶的是,这两个分布不正是每一类样本的特性吗?因此下面就需要对这两个分布进行研究。
    p(c)p(c)是类先验(prior)概率,即在未知其他条件下对事件发生概率的表示,这个值是通过以往经验和分析(历史数据)得到的结果。根据大数定律,当训练样本中包含充足的独立同分布样本时,p(c)p(c)可通过各类样本的出现频率进行估计;与类先验概率相对应的是类后验(posterior)概率p(cx)p(c|x),即我们要建模的目标,表示在已知条件xx下事件发生的概率。
    p(xc)p(x|c)是类条件(class-conditional)概率,即在某个特定类别下,样本xx的发生概率。它是涉及关于样本xx所有属性的联合概率,如果xxdd个属性且取值均为二值,那么样本空间大小将是2d2^d,现实中训练样本的大小往往远小于这个值,因此通过频率估算p(xc)p(x|c)显然是不可行的,因为“未被观测到”不等于“出现概率为0”。

    高斯分布

    通常我们假定类条件概率p(xc)p(x|c)符合某种确定的概率分布,训练样本都是从这个分布中随机采样得到的,“未被采样到的点”也对应有一个发生概率。某种确定的概率分布通常被假设为高斯分布(Gaussian Distribution),现在我们需要做的就是根据训练样本确定高斯分布的参数。多元高斯分布的概率密度函数如下:
    fμ,Σ(x)=1(2π)k/21Σ1/2exp{12(xμ)TΣ1(xμ)} f_{\mu,\Sigma}(x)=\frac{1}{(2\pi)^{k/2}}\frac{1}{|\Sigma|^{1/2}}exp\{-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)\}

    其中kkxx的维数,μ\mu是均值向量,Σ\Sigma是协方差矩阵,μ\mu决定了分布的最高点,Σ\Sigma决定了分布的形状,二维高斯分布概率密度函数如下:
    在这里插入图片描述

    下面两幅图分别展示了μ\mu不同,Σ\Sigma相同,和μ\mu相同,Σ\Sigma不同的分布对比。
    在这里插入图片描述
    在这里插入图片描述

    极大似然估计

    任何一个高斯分布都能采样出我们的训练样本,但是不同的分布采样出训练样本的可能性(likelihood)是不一样的,对给定μ\muΣ\Sigma采样出训练样本的likelihood可以写作:
    L(μ,Σ)=xDcpμ,Σ(x) L(\mu,\Sigma)=\prod_{x\in D_c}p_{\mu,\Sigma}(x)

    DcD_c表示训练样本中属于类别cc的样本数目。最大化上面的似然函数,找出的μ\muΣ\Sigma就是最佳参数。
    μ,Σ=argmaxμ,ΣL(μ,Σ) \mu^*,\Sigma^*=arg \max_{\mu,\Sigma}L(\mu,\Sigma)

    该方法称为最大似然估计(Maximum Likelihood Estimation,MLE),参数μ\muΣ\Sigma的最大似然估计为
    μ=1DcxDcxΣ=1DcxDc(xμ)(xμ)T \mu^*=\frac{1}{|D_c|}\sum_{x\in D_c}x \\ \Sigma^*=\frac{1}{|D_c|}\sum_{x\in D_c}(x-\mu^*)(x-\mu^*)^T

    也就是说,最佳μ\mu^*是样本均值,协方差矩阵是(xμ)(xμ)T(x-\mu^*)(x-\mu^*)^T的均值,这显然是一个符合直觉的结果。现在我们已经计算出每个类别的p(c)p(c)p(xc)p(x|c),就可以选择p(c)p(xc)p(c)p(x|c)较大的那个类别作为xx的类别。
    在实际应用中,对于不同的类别分别给予不同的μ\muΣ\Sigma是比较少见的,尤其是Σ\Sigma的大小是特征的平方,分别给予不同的参数将使得模型参数太多,容易过拟合,所以通常给予不同分布相同的Σ\Sigma,此时似然函数如下:
    L(μ1,μ2,Σ)=xDc1pμ1,Σ(x)xDc2pμ2,Σ(x) L(\mu^1,\mu^2,\Sigma)=\prod_{x\in D_{c_1}}p_{\mu^1,\Sigma}(x)\prod_{x\in D_{c_2}}p_{\mu^2,\Sigma}(x)

    μ1\mu^1μ2\mu^2的值不变,依旧是每一类样本的均值。Σ\Sigma的值稍有变化,等于每一类样本的Σ\Sigma的加权平均
    Σ=Dc1DΣ1+Dc2DΣ2 \Sigma=\frac{D_{c_1}}{D}\Sigma^1+\frac{D_{c_2}}{D}\Sigma^2

    朴素贝叶斯分类器

    上面的计算中,我们将大部分的精力都放在了求解类条件概率p(xc)p(x|c)上,因为p(xc)p(x|c)是关于所有属性的联合概率,难以从样本中直接估计得到。一个大胆的假设是认为描述样本的所有属性是相互独立的,因此p(xc)p(x|c)可以拆解成
    p(xc)=p(x1c)p(x2c)p(xnc)=i=1np(xic) p(x|c)=p(x_1|c)p(x_2|c)\cdots p(x_n|c)=\prod_{i=1}^np(x_i|c)

    其中,nn是属性数目,xix_i是第ii个属性。同样可以假设每一维属性上的概率分布仍然服从高斯分布,此时的高斯分布是一个一维高斯分布,Σ\Sigma对应一个实值,组成协方差矩阵也只在对角线位置有值,进一步减少了参数数目,得到了更简单的模型。这样的模型被称作朴素贝叶斯分类器(naive Bayes classifier,NB)。
    最后,对于样本分布不一定要选择高斯分布,例如如果是二值分布,我们可以假设符合伯努利分布,具体应用中要根据样本特点具体而定,但显示生活中确实有很多分布符合高斯分布。

    总结

    这一篇博客中,我们从另一个角度介绍了求解分类问题的一类新模型,与判别式模型直接建模p(cx)p(c|x)不同,这类模型首先对每一类别样本求解p(c)p(c)p(xc)p(x|c),然后再计算p(cx)p(c|x),我们将这一类模型称作生成式模型(generative models)。因为求解出p(c)p(c)p(xc)p(x|c)后,我们也就求出了联合概率p(x,c)p(x,c),也就求出了p(x)=p(x,c1)+p(x,c2)+p(x)=p(x,c_1)+p(x,c_2)+\cdots,有了p(x)我们就能采样生成每一个样本xx,所以被称为生成式模型。

    参考文献

    李宏毅机器学习2017秋

    展开全文
  • 常见分类方法

    万次阅读 2018-08-07 08:58:46
    本文只对几种常见的分类方法做简单介绍,详细的讲解和算法网上有很多资源,文中会给出推荐链接。 Content 1. 决策树分类(链接:http://blog.csdn.net/github_36299736/article/details/52749999) 2. 基于规则...

    本文只对几种常见的分类方法做简单介绍,详细的讲解和算法网上有很多资源,文中会给出推荐链接。

    Content

    1.      决策树分类(链接:http://blog.csdn.net/github_36299736/article/details/52749999

    2.      基于规则分类

    3.      最邻近分类(K-NN)

    4.      朴素贝叶斯分类器

    5.      人工神经网络

    6.      支持向量机(SVM)

     

    1. 基于规则的分类器

    简单来说,基于规则的分类器就是使用一组“if… then …”的组合来进行分类的技术。通常用R =( r1˅ r2 ˅ … ˅ rk)来表示,其中 ri 就是分类的规则。

    以上图为例,r1  类就可以用如下规则判断:

            If (胎生 = 否 & 飞行动物 = 是)then (类别 = 鸟类)

    度量分类规则的质量可以用覆盖率(coverage)和准确率(accuracy)。覆盖率就是满足规则的记录数占总记录数的比例,准确率就是使用该规则正确分类的比例。

    基于规则分类还有以下两个重要的规则:

            互斥规则(Mutually Exclusive Rule)和穷举规则(Exhaustive Rule)

    互斥规则:规则集中不存在两条规则被同一条记录触发。简单说就是保证同一条记录不会同时属于两个类别。

    穷举规则:对于属性值的任一组合,R中都存在一条规则加以覆盖。即每一条记录都保证能以其中一种规则加以分类。

    这两个性质就可以保证每条记录被且仅被一条规则覆盖。但是实际情况下,分类器可能无法满足这两条性质。对于不能穷举的规则集,我们可以通过设定一个默认规则来覆盖不能被分类的记录。对于不互斥的规则集,我们可以通过建立优先级或者为规则加权等方式来解决。

     

    2. 最邻近分类器

    最邻近分类器是一种简单且常用的分类器。也就是我们常说的K-NN分类算法。它的原理非常简单,即根据与测试数据最近的K个点的类别,采用多数表决方案来确定该测试数据的分类

    以上图为例,1-最邻近(图a)中可以看到与测试数据最近的一个点为负,所以该测试点被指派到负类。2-最邻近(图b)中,与测试数据最近的两点为一正一负,可以随机选择其中一个类别。3-最邻近(图c)中,最近的三个点为两正一负,根据多数表决方案,该点被指派为正。

    从上述例子中就可以看到该算法中k值的选取非常关键。K值太小,结果容易受到数据中噪声的影响从而产生过拟合。K值太大,容易导致误分类,因为结果可能会受到距离测试数据点非常远的数据的影响。(如下图)

    算法描述如下:

    也可以对不同距离的数据点进行加权,从而提高分类的准确率。

     

    3. 朴素贝叶斯分类器

    了解朴素贝叶斯分类,首先要知道贝叶斯定理,也就是我们比较熟悉的条件概率。参考:http://blog.csdn.net/github_36299736/article/details/52800394

    朴素贝叶斯分类器的工作原理就是计算测试数据被分给各个类别的条件概率(后验概率),并将该记录指派给概率最大的分类。

    让我们用之前在决策树分类中使用过的例子来分析:

    假定一个测试数据,该测试数据的属性集可以表示为:X= {有房=否,婚姻状况=已婚,年收入=120k},我们需要将该数据分类到两个类别之一,即 Y = {拖欠贷款=是,拖欠贷款=否}。那么我们需要做的就是分别计算两种分类情况下的后验概率 P (Y|X) 。 P1 = P (拖欠贷款 = 是|X) 和P2 = P (拖欠贷款 = 否|X) ,如果P1 >P2,则记录分类为拖欠贷款 = 是,反之分类为拖欠贷款 = 否。

    朴素贝叶斯分类器更通常的表示方法:给定类标号 y,朴素贝叶斯分类器在估计条件概率时假设属性之间条件独立,若每个属性集(数据)包含d个属性X = { X1,X2,…,Xd } ,那么每个类Y的后验概率计算公式为:

    由于P(X)是固定值,因此只要找出分子最大的类就可以了。

    对于连续属性的条件概率,可以用以下两种方法来估计它的类条件概率:

    1.      把连续的属性离散化,然后用相应区间来替代连续的属性值;

    2.      假设连续变量服从某种概率分布(例如:高斯分布),然后使用训练数据估计分布的参数。

     

    4. 人工神经网络(ANN)

    类似于人脑由神经元及轴突构成的结构,人工神经网络由相互连接的结点和有向链构成。最简单的ANN模型是感知器(perceptron)。

    以上图为例,b即为一个感知器,其中,x1, x2, x3 分别为三个输入结点,在本例中表示三个输入的布尔值,还有一个输出结点。结点通常叫做神经元或单元。感知器中,每个输入结点都通过一个加权链连接到输出结点。加权链就像神经元间连接的强度,训练一个感知器模型就相当于不断调整链的权值,直到能拟合训练数据的输入输出关系为止

    感知器对输入加权求和,再减去偏置因子 t,然后考察得到的结果,得到输出值 ŷ。

    上图中分类依据为如果三个输入值中至少两个0,y取-1,至少有两个1时,y取1. 它的感知器的输出计算公式如下:

    更通用的数学表达方式是:

    其中,w1, w2, …, wd 是输入链的权值,x1, x2, …, xd 是输入属性值。

    还可以写成更简洁的形式:

    其中,w0 = -t,x0 = 1. w · x 是权值向量 w 和输入属性向量 x 的点积。

     

    多层人工神经网络

    多层神经网络相比于感知器要复杂得多,首先,网络的输入层和输出层之间可能包含多个隐藏层,隐藏层中包含隐藏结点。这种结构就叫做多层神经网络。感知器就是一个单层的神经网络

    除此之外,网络还可以使用其他激活函数(如S型函数,双曲线正切函数,符号函数等)使得隐藏结点和输出结点的输出值和输入参数呈非线性关系。

    直观上,我们可以把每个隐藏结点看成一个感知器,而每个感知器可以构造出一个超平面用于分类。如下图a中所构造的两个超平面。

    ANN学习算法的目标函数是找出一组权值w,使得误差平方和最小:

     

    对于激活函数是线性函数的情况,可以将ŷ =w · x 带入上式将其变成参数的二次函数,就可以找出全局最小解。当输出是参数的非线性函数的时候,可以采用梯度下降法来优化。

    关于神经网络的更多内容,我推荐这一篇文章,来自知乎专栏,作者:YJango,链接:https://zhuanlan.zhihu.com/p/22888385

     

    5. 支持向量机(SVM)

    SVM是现在倍受关注的分类技术,可以很好地适用于高维数据。它的特点是,使用训练实例的一个子集来表示决策边界,该子集就是支持向量。那么为什么把一个决策边界叫做“向量”呢?首先从最大边缘超平面这个概念开始了解。

    假设这是一个数据集,其中包含两类数据,分别用方块和圆来表示。非常直观地看到,我们很容易在两组数据之间找到无限个超平面(本例中是一条直线),使得不同类的数据分别在这个超平面的两侧。

    但是,有一些超平面的选择在测试未知数据时的效果可能并不好,比如下图中的红色线:

    可以看到,只要测试数据稍稍偏离一点,就容易导致分类错误。因此,我们要在这无数条分界线中找到一条最优解,使它到两边的边距最大。(如下图)

    如果将这些数据点放在坐标系中,边缘的点可以以向量的形式来表示:

     

    其中,用红色圈起来的数据点就是support vector,这也就是SVM这个算法名称的由来。

    关于支持向量机,有一系列非常好的博客可以参考,作者:pluskid,链接:http://blog.pluskid.org/?page_id=683

     

    其实常用分类方法还有很多,例如AdaBoost,以及不同分类方法的组合。本文只是参考书中内容对几种常见分类算法做了入门级介绍,可以根据实际的学习和工作需要做深入研究并择优使用。 感谢阅读。

     

    参考:《数据挖掘导论》第五章 分类:其他技术

    展开全文
  • 数据挖掘——分类

    万次阅读 2018-10-12 08:46:20
    分类 基本概念 分类:一种数据分析形式,它提取刻画重要数据类的模型。这种模型叫分类器,进而预测分类的(离散的、无序的)类标号。 相关概念解释 训练集:由数据库元组和与它们相关联的类标号组成。 ...

    分类

    基本概念
    分类:一种数据分析形式,它提取刻画重要数据类的模型。这种模型叫分类器,进而预测分类的(离散的、无序的)类标号

    预测问题
    分类两个阶段
    相关概念解释

    • 训练集:由数据库元组和与它们相关联的类标号组成。
    • 元组X用n维属性向量x=(x1,x2,x3……xn)表示,分别描述元组在n维数据库中的n个属性值的集合。
    • 每个元组都可预先定义为一个,由一个称为类标号属性的数据库属性确定。
    • 类标号属性:是离散的无序的。它是分类的(标称的。标称属性的值仅仅只是不同的名字,以区分不同对象)。因为每个值充当一个类别或类。
    • 数据元组也称为:样本、记录、实例、对象、数据点。
    • 属性值也称:变量、特征、字段、维。
    • 属性的数量称为维度
    • 由训练集所得到的学习模型:可用分类规则决策树数学公式的形式表示。

    第一步 建立模型(可看作学习一个函数y=f(x),它可预测给定元组X的类标号y。)
    在这里插入图片描述
    第二步 检验模型并用于新的分类(由检验集评估分类器的准确率,再应用于新的数据进行分类)
    在这里插入图片描述
    如上图分类的预测任务,首先通过已有的数据集(训练集)进行训练学习,得到一个目标函数(学习模型或分类规则),再通过检验集的数据对该模型的准确度评估,若通过评估,则该规则应用于新的数据元组分类。

    • 分类器在给定检验集上的准确率是指分类器正确分类的检验元组所占的百分比。通过每个检验元组的类标号与学习模型对该元组的类预测进行比较。

    • 监督学习 (用于分类)
      即分类器的学习,是在已知每个训练元组的类别的“监督下”进行的。
    • 无监督学习(用于聚类)
      每个训练元组的类标号未知,并且学习的类的个数和集合也可能是事先未知的。

    在这里插入图片描述

    1. 什么是决策树?
    2. 类似于流程图的树结构
    3. 每个内部节点表示在一个属性上的测试
    4. 每个分枝代表一个测试输出
    5. 每个树叶节点存放一个类编号

    决策树:Buys_computer
    在这里插入图片描述

    1. 决策树是如何分类的?
      给定一个类标号未知的元组X,在决策树上测试元组的属性值,跟踪一条由根到叶节点的路径,叶节点存放该元组的类预测。
    2. 决策树的生成由两个阶段组成
      决策树构建
      1.) 使用属性选择度量来选择属性,使元组能最好的划分为不同的类。
      2.) 递归的通过选定属性,来划分样本(必须是离散值)。
      树剪枝
      1.) 决策树建立时,许多分枝反映的是训练数据中的噪声和离群点点,树剪枝试图识别并剪去这种分枝,以提高对未知数据分类的准确性。
    3. 决策树的基本算法
      在这里插入图片描述
      算法主要步骤:
    • 以训练样本的单个节点N开始;
    • 如果样本都在同一类,则该节点成为树叶,并用该类标记。
    • 否则,算法调用Attribute_selection_method(属性选择度量),选择能够最好的将样本分类的属性,确定“分裂准则”,指出“分裂点”或“分裂子集”;
    • 对测试属性每个已知的值,创建一个分支,并以此划分元组;
    • 算法使用同样的过程,递归的形成每个划分上的元组决策树。一旦一个属性出现在一个节点上,就在该节点的子节点上删除;

    递归划分步骤停止的条件

    • 情形(1):划分D(在N节点提供)的所有元组属于同一类
    • 情形(2):当前属性集为空,或所有样本在所有属性上取值相同,无法划分。
    • 情形(3):没有剩余的样本。
    • 给定分支没有元组,则以D中多数类创建一个树叶

    注:整个决策树建立的关键是:属性选择的度量,也是算法的核心


    1. 属性选择度量(分裂准则)

    问题: 如何选择元组的属性进行优先建树,使得将所有训练元组能最好的划分??(也即使决策树简单)。
    eg. 女生约会是否见男生。eg. 明天是否打球案例。
    在这里插入图片描述
    理想的划分是,使每个划分都是“纯”的,即落在给定划分内的元组都属于同一类。
    2. 常用的属性选择度量

    • 信息增益
    • 增益率
    • Gini指数

    3. 使用符号如下:
    设数据分区D为标记类元组的训练集,类标号属性具有m个不同值,定义了m个不同类Ci(i=1,2,3…,m),设Ci, D 是D中Ci类元组的集合,|D|和|Ci, D|分别是D和Ci, D中元组的个数。

    信息增益

    ID3算法使用信息增益作为属性选择度量。它是基于香农的信息论,对信息进行度量的方法。(可参考信息论的文章xxx)。
    设节点N存放分区D的元组,选择具有最高信息增益的属性作为节点N的分裂属性。该属性使最终的结果分区中对元组分类所需要的信息量最小。这种方法使得对一个元组进行分类的测试数目最小,并确保找到一颗简单的树。

    对D中元组分类所需要的期望信息由下式计算:

    其中,Pi是D中任意元组属于类Ci的非零概率,用|Ci, D|/|D|估计。用到信息论里面的自信息量公式,表示事件x发生前,事件发生的不确定性,或事件发生后,所得到信息量。在这里插入图片描述
    Info(D)是对D中所有元组分类所需要的期望信息(平均信息量)。也称为D的熵。是随机变量平均不确定度的度量,同时它也代表了消除随机变量不确定度所需获得的信息量。

    若我们对属性A进行划分元组D,其中A具有v个不同值{a1,a2,a3…,av},若A是离散值,则对应有v个输出,可以用属性A将D划分为v个分区或子集{D1,D2,D3,…Dv},Dj包含D中的元组,它们的属性值都为aj。为了得到准确分类,还需要多少信息量?由下式计算:
    在这里插入图片描述
    在这里插入图片描述
    是第j个分区的权重。在这里插入图片描述
    是基于按A划分对D的元组分类所需要的期望信息。

    信息增益:原来的信息需求与新的信息需求(对A划分后)之间的差。
    Gain(A)=Info(D)-InfoA(D),即对A划分后所获得的信息量。所以选择最高信息增益Gain(A)的属性A作为节点N的分裂属性。等价于在“能做最佳分类”的属性A上划分,使得完成剩余元组的划分所需要的信息量最小。

    例题:
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 分类算法总结

    万次阅读 多人点赞 2010-01-17 19:59:00
    2.4.1 主要分类方法介绍解决分类问题的方法很多[40-42] ,单一的分类方法主要包括:决策树、贝叶斯、人工神经网络、K-近邻、支持向量机和基于关联规则的分类等;另外还有用于组合单一分类方法的集成学习算法,如...

    目前看到的比较全面的分类算法,总结的还不错.
    2.4.1 主要分类方法介绍解决分类问题的方法很多[40-42] ,单一的分类方法主要包括:决策树、贝叶斯、人工神经网络、K-近邻、支持向量机和基于关联规则的分类等;另外还有用于组合单一分类方法的集成学习算法,如Bagging和Boosting等。
    (1)决策树
    决策树是用于分类和预测的主要技术之一,决策树学习是以实例为基础的归纳学习算法,它着眼于从一组无次序、无规则的实例中推理出以决策树表示的分类规则。构造决策树的目的是找出属性和类别间的关系,用它来预测将来未知类别的记录的类别。它采用自顶向下的递归方式,在决策树的内部节点进行属性的比较,并根据不同属性值判断从该节点向下的分支,在决策树的叶节点得到结论。
    主要的决策树算法有ID3、C4.5(C5.0)、CART、PUBLIC、SLIQ和SPRINT算法等。它们在选择测试属性采用的技术、生成的决策树的结构、剪枝的方法以及时刻,能否处理大数据集等方面都有各自的不同之处。
    (2)贝叶斯
    贝叶斯(Bayes)分类算法是一类利用概率统计知识进行分类的算法,如朴素贝叶斯(Naive Bayes)算法。这些算法主要利用Bayes定理来预测一个未知类别的样本属于各个类别的可能性,选择其中可能性最大的一个类别作为该样本的最终类别。由于贝叶斯定理的成立本身需要一个很强的条件独立性假设前提,而此假设在实际情况中经常是不成立的,因而其分类准确性就会下降。为此就出现了许多降低独立性假设的贝叶斯分类算法,如TAN(Tree Augmented Na?ve Bayes)算法,它是在贝叶斯网络结构的基础上增加属性对之间的关联来实现的。
    (3)人工神经网络
    人工神经网络(Artificial Neural Networks,ANN)是一种应用类似于大脑神经突触联接的结构进行信息处理的数学模型。在这种模型中,大量的节点(或称”神经元”,或”单元”)之间相互联接构成网络,即”神经网络”,以达到处理信息的目的。神经网络通常需要进行训练,训练的过程就是网络进行学习的过程。训练改变了网络节点的连接权的值使其具有分类的功能,经过训练的网络就可用于对象的识别。
    目前,神经网络已有上百种不同的模型,常见的有BP网络、径向基RBF网络、Hopfield网络、随机神经网络(Boltzmann机)、竞争神经网络(Hamming网络,自组织映射网络)等。但是当前的神经网络仍普遍存在收敛速度慢、计算量大、训练时间长和不可解释等缺点。
    (4)k-近邻
    k-近邻(kNN,k-Nearest Neighbors)算法是一种基于实例的分类方法。该方法就是找出与未知样本x距离最近的k个训练样本,看这k个样本中多数属于哪一类,就把x归为那一类。k-近邻方法是一种懒惰学习方法,它存放样本,直到需要分类时才进行分类,如果样本集比较复杂,可能会导致很大的计算开销,因此无法应用到实时性很强的场合。
    (5)支持向量机
    支持向量机(SVM,Support Vector Machine)是Vapnik根据统计学习理论提出的一种新的学习方法[43] ,它的最大特点是根据结构风险最小化准则,以最大化分类间隔构造最优分类超平面来提高学习机的泛化能力,较好地解决了非线性、高维数、局部极小点等问题。对于分类问题,支持向量机算法根据区域中的样本计算该区域的决策曲面,由此确定该区域中未知样本的类别。
    (6)基于关联规则的分类
    关联规则挖掘是数据挖掘中一个重要的研究领域。近年来,对于如何将关联规则挖掘用于分类问题,学者们进行了广泛的研究。关联分类方法挖掘形如condset→C的规则,其中condset是项(或属性-值对)的集合,而C是类标号,这种形式的规则称为类关联规则(class association rules,CARS)。关联分类方法一般由两步组成:第一步用关联规则挖掘算法从训练数据集中挖掘出所有满足指定支持度和置信度的类关联规则;第二步使用启发式方法从挖掘出的类关联规则中挑选出一组高质量的规则用于分类。属于关联分类的算法主要包括CBA[44] ,ADT[45] ,CMAR[46] 等。
    (7)集成学习(Ensemble Learning)
    实际应用的复杂性和数据的多样性往往使得单一的分类方法不够有效。因此,学者们对多种分类方法的融合即集成学习进行了广泛的研究。集成学习已成为国际机器学习界的研究热点,并被称为当前机器学习四个主要研究方向之一。
    集成学习是一种机器学习范式,它试图通过连续调用单个的学习算法,获得不同的基学习器,然后根据规则组合这些学习器来解决同一个问题,可以显著的提高学习系统的泛化能力。组合多个基学习器主要采用(加权)投票的方法,常见的算法有装袋[47] (Bagging),提升/推进[48, 49] (Boosting)等。
    有关分类器的集成学习见图2-5。集成学习由于采用了投票平均的方法组合多个分类器,所以有可能减少单个分类器的误差,获得对问题空间模型更加准确的表示,从而提高分类器的分类准确度。
    图2-5:分类器的集成学习
    以上简单介绍了各种主要的分类方法,应该说其都有各自不同的特点及优缺点。对于数据库负载的自动识别,应该选择哪种方法呢?用来比较和评估分类方法的标准[50] 主要有:(1)预测的准确率。模型正确地预测新样本的类标号的能力;(2)计算速度。包括构造模型以及使用模型进行分类的时间;(3)强壮性。模型对噪声数据或空缺值数据正确预测的能力;(4)可伸缩性。对于数据量很大的数据集,有效构造模型的能力;(5)模型描述的简洁性和可解释性。模型描述愈简洁、愈容易理解,则愈受欢迎。
    zz from http://hi.baidu.com/gf271828/blog/item/38df3df172e150c10b46e06d.html

    展开全文
  • 分类(classification)与回归(regression)的关系

    万次阅读 多人点赞 2018-10-15 15:17:19
    分类模型和回归模型本质一样,分类模型是将回归模型的输出离散化。 举几个例子: 1. Logistic Regression 和 Linear Regression: Linear Regression: 输出一个标量 wx+b,这个值是连续值,所以可以用来处理回归...
  • 文本分类过程概述

    千次阅读 2019-01-09 19:15:11
    传统的文本分类过程通常包括训练模块和分类模块如下图所示:一般来讲文本分类过程包括预处理、文本表示、特征降维、训练分类器和分类性能评估。  文本分类过程图 1、文本分类预处理  由于计算机很难直接处...
  • 分类和回归的区别

    千次阅读 2019-04-04 09:23:39
    分类和回归的区别在于输出变量的类型。 定量输出称为回归,或者说是连续变量预测; 定性输出称为分类,或者说是离散变量预测。 输入变量与输出变量均为变量序列的预测问题为标注问题 举个例子: 预测明天的气温是...
  • 回归问题和分类问题

    千次阅读 2019-08-30 18:08:13
    参考博客1:分类与回归区别是什么?(知乎) 参考博客2:回归和分类区别,及模型的选择 参考博客3:回归(regression)与分类(classification)的区别 1、回归问题通常是用来预测一个值,如预测房价、未来的天气情况...
  • 编程语言分类

    万次阅读 2019-01-23 10:05:13
    1. 桌面程序:Java、C++、C#、VB、C均可。 2. 网站服务器端开发:JSP(Java语法)...4. 智能手机程序:安卓使用Java,iPhone使用Objective-C 5. 底层、工具开发:C、C++ 6. 多功能脚本程序:Python、Perl、Ruby等等 ...
  • Python实现简单分类

    千次阅读 2018-09-22 09:22:45
    文章目录@[toc]第一步,导入我们需要的python库第二步,获取训练数据并解析坐标第三步,随机化数据第四步、生成分界线斜率第五步、处理测试数据第六步、输出展示分类结果输入数据完整代码 今天重新开始学习机器学习...
  • 机器学习——几种分类算法的汇总

    千次阅读 2019-06-25 01:03:45
    https://www.cnblogs.com/Zhi-Z/p/8912396.html
  • 分类评价指标 准确率(Accuracy) 评价分类问题的性能指标一般是分类准确率,即对于给定的数据,分类正确的样本数占总样本数的比例。 注意:准确率这一指标在Unbalanced数据集上的表现很差,因为如果我们的正负...
  • 分类,聚类及其回归的区别

    万次阅读 多人点赞 2020-04-10 16:06:02
    from:...由上图我们可以看到,机器学习分为四大块,分别是classification (分类),regression (回归),clustering (聚类),dimensionality reduction (降维...
  • arcgis中的重分类

    万次阅读 2018-05-12 16:28:03
    分类:就是对原有栅格像元值重新分类从而得到一组新值并输出。重分类工具包括重分类、查找表、分割、使用表和ASCII文件重分类等重分类的原因:1、新值替代(例如,水库面积的变化,土地利用类型的变化);2、将值...
  • CSDN分类专栏操作演示

    万次阅读 多人点赞 2019-08-26 17:37:43
    博客专栏与文章分类合并为分类专栏,同时新增二级分类功能。新创建的分类专栏不能超过50个(包含二级),标签不能超过3个。 之前创建超过数量的分类专栏不会自动合并,暂时先保持不变。 新分类专栏管理页面如下,...
  • 任何的分类问题

    万次阅读 2020-03-20 10:06:58
    任何的分类问题 都是找到共同点,加以群分 一定存在某个分类法则可以群分两个事物 任何的数据都可通过某种变换得到这个分类法则的编码 深度编码可以让数据适合任何的分类法则 , 深度学习来说就是 通过卷积进行深度...
  • 分类问题的基本思路是“拆解法”,将多分类任务拆为若干个二分类任务求解。经典的拆分策略有三种:一对多、一对其余和多对多。 二、拆分方法 1、 将个类别两两配对,形成个二分类任务。在测试阶段,新样本被...
  • 今天修改了论文封皮里面的国内图书分类号和国际图书分类号,关于这些,简单记录一下吧,希望对于之后同样需要的人提供一点帮助 国内图书分类号相对来数比较容易填写,最简单的方法就是找到跟你内容相似的论文看他们...
  • 数据挖掘十大经典算法(7) AdaBoost

    万次阅读 热门讨论 2009-05-01 14:35:00
    Adaboost是一种迭代算法,其核心思想是针对同一个训练集训练不同的分类器(弱分类器),然后把这些弱分类器集合起来,构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的,它根据每次训练集之...
  • 中图分类号和UDC查询

    万次阅读 2017-10-20 08:59:01
    中图分类号: http://www.ztflh.com/ UDC: http://www.udcc.org/udcsummary/php/index.php?lang=chi
1 2 3 4 5 ... 20
收藏数 1,475,215
精华内容 590,086
关键字:

分类