決策樹算法在商標(biāo)分類中的應(yīng)用

1、人工智能原理姓名：成軍學(xué)好：510061813論文題目：決策樹算法在商標(biāo)分類中的應(yīng)用中文摘要：決策樹一般都是自上而下的來生成的。每個(gè)決策或事件（即自然狀態(tài)）都可能引出兩個(gè)或多個(gè)事件，導(dǎo)致不同的結(jié)果，把這種決策分支畫成圖形很像一棵樹的枝干。本文將使用決策樹算法對(duì)給定的商標(biāo)進(jìn)行分類。其中有三大類商標(biāo)數(shù)據(jù)，每大類使用五分之三的數(shù)據(jù)進(jìn)行訓(xùn)練，使用五分之二的數(shù)據(jù)進(jìn)行測(cè)試。我們應(yīng)用Java和MySQl數(shù)據(jù)庫進(jìn)行測(cè)試。用c4.5算法構(gòu)造決策樹。最終對(duì)數(shù)據(jù)進(jìn)行準(zhǔn)確率計(jì)算。關(guān)鍵詞： 決策樹 分類 商標(biāo) 測(cè)試Title: Decision tree algorithm of the application for

2、 trademark classification Abstract: The decision tree is commonly top-down to generate. Each decision or events (namely natural state) are likely to elicit two or more events, lead to different results, put this decision branch loser graphics is like a tree branches. This article will use the decisi

3、on tree algorithm for given the trademark of classification. There are three kinds of trademark data, each of the groups using three fifths of the data to train, use two fifths of the experimental data. We use Java and MySQL database testing. Use c4.5 decision tree algorithms construction. Finally,

4、calculate the data accuracy. Keywords: Decision tree classification brand test引言：機(jī)器學(xué)習(xí)一般分為3種類型：有監(jiān)督的、無監(jiān)督的以及強(qiáng)化學(xué)習(xí)【1】。有監(jiān)督學(xué)習(xí)問題涉及從它的輸入和輸出的實(shí)例中學(xué)習(xí)一個(gè)函數(shù)。對(duì)于完全可觀察的環(huán)境，智能體總能夠觀察到它的行動(dòng)所帶來的影響，因此有監(jiān)督學(xué)習(xí)是可行的，否則會(huì)困難一些。 無監(jiān)督學(xué)習(xí)問題涉及在未提供明確的輸出值的情況下，學(xué)習(xí)輸入的模式。純粹的無監(jiān)督學(xué)習(xí)智能體無法學(xué)習(xí)要做什么，因?yàn)樗鼪]有信息說明什么能構(gòu)成正確的行動(dòng)或者所期望的狀態(tài)。 強(qiáng)化學(xué)習(xí)問題，是三類問題中最普遍的一個(gè)。強(qiáng)化學(xué)習(xí)是從

5、強(qiáng)化物（起加強(qiáng)作用的事物）中進(jìn)行學(xué)習(xí)，而不是根據(jù)教師所說的應(yīng)該做什么進(jìn)行學(xué)習(xí)。正文：決策樹方法是挖掘分類規(guī)則的有效方法，通常包括兩個(gè)部分：樹的生成，開始時(shí)所有的數(shù)據(jù)都在根節(jié)點(diǎn)，然后根據(jù)設(shè)定的標(biāo)準(zhǔn)選擇測(cè)試屬性，用不同的測(cè)試屬性遞歸進(jìn)行數(shù)據(jù)分割。樹的修剪，就是除去一些可能是噪音或異常的數(shù)據(jù)?；谛畔㈧氐腎D3算法、C45算法都能有效地生成決策樹，建決策樹的關(guān)鍵在于建立分支時(shí)對(duì)記錄字段不同取值的選擇。選擇不同的字段值使劃分出來的記錄子集不同影響決策樹生長的快慢及決策樹的結(jié)構(gòu)，從而可尋找到規(guī)則信息的優(yōu)劣。可見，決策樹算法的技術(shù)難點(diǎn)就是選擇一個(gè)好的分支取值。利用好的取值產(chǎn)生分支可加快決策樹的生長，更重要

6、是產(chǎn)生好結(jié)構(gòu)的決策樹，并可得到較好的規(guī)則信息。相反，若根據(jù)一個(gè)差的取值產(chǎn)生分支，不但減慢決策樹的生長速度，而且使產(chǎn)生的決策樹分支過細(xì)、結(jié)構(gòu)差，從而難以發(fā)現(xiàn)有用的規(guī)則信息。隨著訓(xùn)練樣本集中樣本個(gè)數(shù)的不斷增多(即樣本集規(guī)模不斷擴(kuò)大)，訓(xùn)練樣本集在主存中換進(jìn)換出就耗費(fèi)了大量的時(shí)間，嚴(yán)重影響了算法效率。因此使算法能有效處理大規(guī)模的訓(xùn)練樣本集已成為決策樹算法研究的一個(gè)重要問題，也是目前國內(nèi)對(duì)決策樹算法研究的熱點(diǎn)。本文利用決策樹C4.5算法來解決圖像的分類問題。現(xiàn)在我們引用下c4.5算法的實(shí)例【2】。C4 .5 算法是構(gòu)造決策樹分類規(guī)則的一種算法，它是ID3算法的擴(kuò)展。ID3算法只能處理離散型的描述性屬性

7、而C4.5算法還能夠處理描述屬性取值為連續(xù)型的情況。選取節(jié)點(diǎn)的標(biāo)準(zhǔn)是最大信息增益率，具體的算法步驟如下:Stepl：數(shù)據(jù)源進(jìn)行數(shù)據(jù)預(yù)處理，將連續(xù)型的屬性變量進(jìn)行離散化處理形成決策樹的訓(xùn)練集(如果連續(xù)取值的屬性則忽略);(1)根據(jù)原始數(shù)據(jù)，找到該連續(xù)型屬性的最小取值a0大取值an+1;(2) 在 區(qū) 間a ，b插人n數(shù)值等分為n+l個(gè)小區(qū)間;(3 )分別以ai ,i=1,2, ,n。為分段點(diǎn)，將區(qū)間a0,an+1劃分為兩個(gè)子區(qū)間: a0,aj， (ai+1,an+1)對(duì)應(yīng)該連續(xù)型的屬性變量的兩類取值，有n種劃分方式;Ste p2 :計(jì)算每個(gè)屬性的信息增益和信息增益率;(1 )計(jì)算屬性A的信息增益

8、Gain(A)信息增益 Gain(A)的計(jì)算和ID3算法中的完全一致;(2 )計(jì) 算 屬性A的信息增益率Gain一Ratio( A)Gain一Ratio(A)=Gain(A)/I(A )對(duì)于取值連續(xù)的屬性而言，分別計(jì)算以ai(i=1,2,n)為分割點(diǎn)，對(duì)應(yīng)分類的信息增益率，選擇最大信息增益率對(duì)應(yīng)的ai，作為該屬性分類的分割點(diǎn)。選擇信息 增益率最大的屬性，作為當(dāng)前的屬性節(jié)點(diǎn)，得到?jīng)Q策樹的根節(jié)點(diǎn)。Step3:根節(jié)點(diǎn)屬性每一個(gè)可能的取值對(duì)應(yīng)一個(gè)子集，對(duì)樣本子集遞歸地執(zhí)行以上Step2過程，直到劃分的每個(gè)子集中的觀測(cè)數(shù)據(jù)在分類屬性上取值都相同，生成決策樹。Step4:根據(jù)構(gòu)造的決策樹提取分類規(guī)則，對(duì)新

9、的數(shù)據(jù)集進(jìn)行分類。類似算法的主要思想都是，逐步找出能夠?yàn)楦鱾€(gè)層次的分類提供最大信息量的變量，由此可以確定決策樹從根到枝，再從枝到葉的結(jié)構(gòu)。決策樹生成的過程也就是對(duì)訓(xùn)練數(shù)據(jù)集迸行分類的過程?，F(xiàn)在分析給出的商標(biāo)，建立數(shù)據(jù)庫。并建立表：其中id是主鍵。屬性包括：circle、rectangle、triangle、connect、object。分別是圓、長方形、三角形、組合行、所屬分類。接著用3/5的數(shù)據(jù)作為訓(xùn)練集，2/5的數(shù)據(jù)集作為測(cè)試集。對(duì)所有商標(biāo)進(jìn)行定義屬性，并保存到數(shù)據(jù)庫中。如下：由于數(shù)據(jù)量比較大，這里就不全部列出，接著用sql語句對(duì)數(shù)據(jù)查詢，比如要查詢從id1id100中circle屬性都是

10、1的個(gè)數(shù)是多少：Select sum(circle)From brandWhere id0 and circle=1接著根據(jù)c4.5算法計(jì)算得到：GainRati circle(A)= 0.23212131GainRati Rectange(A)= 6.44123121GainRati triangle(A)= 2.91892837GainRatioconnect(A)=5.32412321結(jié)論：根據(jù)c4.5算法，增益率高的作為分界點(diǎn)，則我們可以得到?jīng)Q策樹的結(jié)構(gòu)：Rectangle R=0 R=1Object2connect C=1 C=0Object3Object1最后對(duì)訓(xùn)練集和測(cè)試測(cè)試集進(jìn)行準(zhǔn)確率計(jì)算：在數(shù)據(jù)庫中使用查詢：Select *From brandWhere rectangle=0 and object=2用球的值除以測(cè)試集的60，就是正確率。最終的結(jié)果是：類第一類第二類第三類正確率71.76%78.65%86.6%訓(xùn)練集接著用同樣的方法對(duì)測(cè)試集進(jìn)行測(cè)試，得：類第一類第二類第三類正