决策树算法在商标分类中的应用

人工智能原理姓名：成军学好：510061813论文题目：决策树算法在商标分类中的应用中文摘要：决策树一般都是自上而下的来生成的。每个决策或事件（即自然状态）都可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形很像一棵树的枝干。本文将使用决策树算法对给定的商标进行分类。其中有三大类商标数据，每大类使用五分之三的数据进行训练，使用五分之二的数据进行测试。我们应用Java和MySQl数据库进行测试。用c4.5算法构造决策树。最终对数据进行准确率计算。关键词：决策树分类商标测试Title:DecisiontreealgorithmoftheapplicationfortrademarkclassificationAbstract:Thedecisiontreeiscommonlytop-downtogenerate.Eachdecisionorevents(namelynaturalstate)arelikelytoelicittwoormoreevents,leadtodifferentresults,putthisdecisionbranchlosergraphicsislikeatreebranches.Thisarticlewillusethedecisiontreealgorithmforgiventhetrademarkofclassification.Therearethreekindsoftrademarkdata,eachofthegroupsusingthreefifthsofthedatatotrain,usetwofifthsoftheexperimentaldata.WeuseJavaandMySQLdatabasetesting.Usec4.5decisiontreealgorithm'sconstruction.Finally,calculatethedataaccuracy.Keywords:Decisiontreeclassificationbrandtest引言：机器学习一般分为3种类型：有监督的、无监督的以及强化学习【1】。有监督学习问题涉及从它的输入和输出的实例中学习一个函数。对于完全可观察的环境，智能体总能够观察到它的行动所带来的影响，因此有监督学习是可行的，否则会困难一些。无监督学习问题涉及在未提供明确的输出值的情况下，学习输入的模式。纯粹的无监督学习智能体无法学习要做什么，因为它没有信息说明什么能构成正确的行动或者所期望的状态。强化学习问题，是三类问题中最普遍的一个。强化学习是从强化物（起加强作用的事物）中进行学习，而不是根据教师所说的应该做什么进行学习。正文：决策树方法是挖掘分类规则的有效方法，通常包括两个部分：①树的生成，开始时所有的数据都在根节点，然后根据设定的标准选择测试属性，用不同的测试属性递归进行数据分割。②树的修剪，就是除去一些可能是噪音或异常的数据。基于信息熵的ID3算法、C4．5算法都能有效地生成决策树，建决策树的关键在于建立分支时对记录字段不同取值的选择。选择不同的字段值使划分出来的记录子集不同影响决策树生长的快慢及决策树的结构，从而可寻找到规则信息的优劣。可见，决策树算法的技术难点就是选择一个好的分支取值。利用好的取值产生分支可加快决策树的生长，更重要是产生好结构的决策树，并可得到较好的规则信息。相反，若根据一个差的取值产生分支，不但减慢决策树的生长速度，而且使产生的决策树分支过细、结构差，从而难以发现有用的规则信息。随着训练样本集中样本个数的不断增多(即样本集规模不断扩大)，训练样本集在主存中换进换出就耗费了大量的时间，严重影响了算法效率。因此使算法能有效处理大规模的训练样本集已成为决策树算法研究的一个重要问题，也是目前国内对决策树算法研究的热点。本文利用决策树C4.5算法来解决图像的分类问题。现在我们引用下c4.5算法的实例【2】。C4.5算法是构造决策树分类规则的一种算法，它是ID3算法的扩展。ID3算法只能处理离散型的描述性属性而C4.5算法还能够处理描述属性取值为连续型的情况。选取节点的标准是最大信息增益率，具体的算法步骤如下:Stepl：数据源进行数据预处理，将连续型的属性变量进行离散化处理形成决策树的训练集(如果连续取值的属性则忽略);(1)根据原始数据，找到该连续型属性的最小取值a0大取值an+1;(2)在区间[a，b]插人n数值等分为n+l个小区间;(3)分别以ai,i=1,2,⋯,n。为分段点，将区间[a0,an+1]划分为两个子区间:[a0,aj]，[(ai+1,an+1)]对应该连续型的属性变量的两类取值，有n种划分方式;Step2:计算每个属性的信息增益和信息增益率;(1)计算属性A的信息增益Gain(A)信息增益Gain(A)的计算和ID3算法中的完全一致;(2)计算属性A的信息增益率Gain一Ratio(A)Gain一Ratio(A)=Gain(A)/I(A)对于取值连续的属性而言，分别计算以ai(i=1,2,…,n)为分割点，对应分类的信息增益率，选择最大信息增益率对应的ai，作为该属性分类的分割点。选择信息增益率最大的属性，作为当前的属性节点，得到决策树的根节点。Step3:根节点属性每一个可能的取值对应一个子集，对样本子集递归地执行以上Step2过程，直到划分的每个子集中的观测数据在分类属性上取值都相同，生成决策树。Step4:根据构造的决策树提取分类规则，对新的数据集进行分类。类似算法的主要思想都是，逐步找出能够为各个层次的分类提供最大信息量的变量，由此可以确定决策树从根到枝，再从枝到叶的结构。决策树生成的过程也就是对训练数据集迸行分类的过程。现在分析给出的商标，建立数据库。并建立表：其中id是主键。属性包括：circle、rectangle、triangle、connect、object。分别是圆、长方形、三角形、组合行、所属分类。接着用3/5的数据作为训练集，2/5的数据集作为测试集。对所有商标进行定义属性，并保存到数据库中。如下：由于数据量比较大，这里就不全部列出，接着用sql语句对数据查询，比如要查询从id1—id100中circle属性都是1的个数是多少：Selectsum(circle)FrombrandWhereid101andid0andcircle=1接着根据c4.5算法计算得到：GainRaticircle(A)=0.23212131GainRatiRectange(A)=6.44123121GainRatitriangle(A)=2.91892837GainRatioconnect(A)=5.32412321结论：根据c4.5算法，增益率高的作为分界点，则我们可以得到决策树的结构：R=0R=1C=1C=0最后对训练集和测试测试集进行准确率计算：在数据库中使用查询：Select*FrombrandWhererectangle=0andobject=2用球的值除以测试集的60，就是正确率。最终的结果是：类第一类第二类第三类正确率71.76%78.65%86.6%训练集接着用同样的方法对测试集进行测试，得：类第一类第二类第三类正确率58.65%63.21%70.65%参考文献：【1】姜哲，金奕江等.人工智能—一种现代方法（第二版）[M]人民邮电出版社，2010（8）。【2】盛文，杨江平，柳健。一种基于纹理元灰度模式统计的图像纹理分析方法。[J]，电子学报2000(4)。【3】罗森林，辛子英，冯磊。基于C4.5的敏感图像检测方法。[J]北京理工大学学2006（5）。RectangleconnectObject2Object1Object3