基于決策樹(shù)規(guī)則分類(lèi)算法的研究報(bào)告人：孫秀芳2010年12月15日介紹內(nèi)容研究的主要內(nèi)容數(shù)據(jù)挖掘及其分類(lèi)方法概述C4.5算法基于規(guī)則排序的決策樹(shù)分類(lèi)算法CABRR的研究

一、研究的主要內(nèi)容研究的主要內(nèi)容：從決策樹(shù)入手，從中提取決策樹(shù)規(guī)則，并通過(guò)對(duì)決策樹(shù)規(guī)則進(jìn)行有效地排序后生成分類(lèi)器，應(yīng)用于分類(lèi)預(yù)測(cè)。

二、數(shù)據(jù)挖掘及其分類(lèi)方法概述數(shù)據(jù)挖掘的理論分類(lèi)概念及算法描述分類(lèi)算法度量的方法與尺度2.1數(shù)據(jù)挖掘的理論

數(shù)據(jù)挖掘的概念：所謂數(shù)據(jù)挖掘（又稱(chēng)數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)）是指從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的海量數(shù)據(jù)中，或是大型數(shù)據(jù)庫(kù)或數(shù)據(jù)倉(cāng)庫(kù)中提取隱含的、未知的、非平凡的、有潛在應(yīng)用價(jià)值的信息或模式。數(shù)據(jù)挖掘的過(guò)程：確定挖掘目的、數(shù)據(jù)準(zhǔn)備、數(shù)據(jù)挖掘、模式評(píng)估與知識(shí)表示。數(shù)據(jù)挖掘的具體過(guò)程如下圖所示：數(shù)據(jù)源清理/集成后數(shù)據(jù)選擇/變換后數(shù)據(jù)模式提供可供挖掘的知識(shí)清理與集成選擇與變換數(shù)據(jù)挖掘評(píng)估與表示2.2分類(lèi)概念及算法描述分類(lèi)的概念：所謂分類(lèi)，就是對(duì)己知現(xiàn)存的類(lèi)別，建立類(lèi)別的描述規(guī)則分類(lèi)器，然后對(duì)未知新例的觀察值進(jìn)行判斷歸類(lèi)。下圖為分類(lèi)過(guò)程圖：訓(xùn)練集分類(lèi)模型可接受的模型預(yù)測(cè)結(jié)果通過(guò)分類(lèi)算法建立模型評(píng)估模型預(yù)測(cè)未知數(shù)據(jù)元組

典型的分類(lèi)算法:

常用的分類(lèi)方法包括：決策樹(shù)分類(lèi)、關(guān)聯(lián)分類(lèi)、神經(jīng)網(wǎng)絡(luò)、貝葉斯分類(lèi)方法等?；跊Q策樹(shù)分類(lèi)的典型算法有:ID3算法、C4.5算法、PART算法、CABRR算法等。2.3分類(lèi)算法度量的方法與尺度每種分類(lèi)方法都需要用一定的指標(biāo)來(lái)進(jìn)行評(píng)估，常用的分類(lèi)算法的比較與評(píng)估標(biāo)準(zhǔn)有如下幾個(gè)方面：

預(yù)測(cè)的準(zhǔn)確率可理解性可伸縮性速度強(qiáng)壯性

三、C4.5算法決策樹(shù)算法的基本理論決策樹(shù)的基本算法C4.5算法3.1決策策樹(shù)算法的基基本理論決策樹(shù)：是一種結(jié)構(gòu)構(gòu)，一種知識(shí)識(shí)的表達(dá)形式式，它由兩種種元素組成:節(jié)點(diǎn)和分分支。在最終終生成的決策策樹(shù)上，其中中每個(gè)內(nèi)部節(jié)節(jié)點(diǎn)表示數(shù)據(jù)據(jù)集的一個(gè)屬屬性，每個(gè)分分支代表對(duì)該該屬性的一個(gè)個(gè)測(cè)試輸出，，每個(gè)葉結(jié)點(diǎn)點(diǎn)代表劃分的的類(lèi)別，最頂頂端節(jié)點(diǎn)為根根節(jié)點(diǎn)。決策樹(shù)的生成過(guò)程：主要分成兩個(gè)個(gè)步驟:一是是生成樹(shù)，二是樹(shù)的修修剪。樹(shù)的修剪：即樹(shù)的剪枝枝，最常用的的剪枝技術(shù)有有預(yù)剪枝和后后剪枝。決策樹(shù)的工作作原理流程圖圖如下：數(shù)據(jù)源訓(xùn)練集預(yù)處理決策樹(shù)分類(lèi)算算法歸納生成決策樹(shù)分類(lèi)規(guī)則剪枝3.2決策策樹(shù)的基本算算法Generate_decision_tree//根據(jù)給定數(shù)據(jù)據(jù)集產(chǎn)生一個(gè)個(gè)決策樹(shù)輸入：訓(xùn)練樣本，各各屬性均取離離散數(shù)值，可可供歸納的候候選屬性集為:attribute_list。。輸出：決策樹(shù)。處理流程程：：（1）創(chuàng)建一個(gè)結(jié)點(diǎn)點(diǎn)；（2）若該結(jié)點(diǎn)中的的所有樣本均均為同一類(lèi)別別C，則（3）返回N作為一個(gè)葉結(jié)點(diǎn)并標(biāo)標(biāo)志為類(lèi)別C；（4）若attribute_list為空，，則（5）返返回N作為一一個(gè)葉結(jié)點(diǎn)并并標(biāo)記為該結(jié)結(jié)點(diǎn)所含樣本本中類(lèi)別個(gè)數(shù)數(shù)最多的的類(lèi)別；（6）從attribute_list選擇一一個(gè)信息增益益最大的屬性性test_attribute；；（7））并并將將結(jié)結(jié)點(diǎn)點(diǎn)N標(biāo)標(biāo)記記為為test_attribute；；（8））對(duì)于于test_attribute中的的每每一一個(gè)個(gè)已已知知取取值值ai準(zhǔn)備備劃劃分分結(jié)結(jié)點(diǎn)點(diǎn)N所包包含含的的樣樣本本集集；；（9））根根據(jù)據(jù)test_attribute=ai條件，從結(jié)結(jié)點(diǎn)N產(chǎn)生相應(yīng)的的一個(gè)分支支，以表示示該測(cè)試條條件；（10）設(shè)設(shè)si為test_attribute=ai條件所獲得的樣樣本集合；；（11）若若si為空空，則將相相應(yīng)葉結(jié)點(diǎn)點(diǎn)標(biāo)記為該該結(jié)點(diǎn)所含含樣本中類(lèi)類(lèi)別個(gè)數(shù)最最多的類(lèi)別別；（12）否否則將相應(yīng)應(yīng)葉結(jié)點(diǎn)標(biāo)標(biāo)志為Generate_decision_tree(si,attribute_list-test_attribute)返回回值；算算法C4.5算法法：是對(duì)ID3的改進(jìn)算算法。該算算法采用信信息增益率率作為對(duì)選選擇分枝屬屬性的分枝枝準(zhǔn)則，計(jì)計(jì)算各屬性性的信息增增益率，然然后選取信信息增益率率最大的屬屬性作為結(jié)結(jié)點(diǎn)，自頂頂向下生成成決策樹(shù)。對(duì)構(gòu)造C4.5決策策樹(shù)的相關(guān)關(guān)理論的描述如下:1.首先計(jì)算給給定的樣本本所需的期期望信息,設(shè)S為一個(gè)個(gè)包含s個(gè)數(shù)據(jù)樣本本的集合，，對(duì)于類(lèi)別別屬性，可可以取m個(gè)個(gè)不同的值值,對(duì)應(yīng)于m個(gè)個(gè)不同的類(lèi)類(lèi)別Ci(i{1,2,...,m})。。假設(shè)設(shè)類(lèi)類(lèi)別別Ci中的的樣樣本本個(gè)個(gè)數(shù)數(shù)為為si，，期望望信信息息為為:其中中pi是是任任意意樣樣本本屬屬于于Ci的的概概率率，，并并用用si/s估估計(jì)計(jì)。。2.接接著著計(jì)計(jì)算算當(dāng)當(dāng)前前樣樣本本集集合合所所需需要要的的信信息息嫡嫡，，設(shè)設(shè)一一個(gè)個(gè)屬屬性性A具具有有v個(gè)個(gè)不不同同的的值值{a1,a2,...,av},利利用用屬屬性性A可可以以將將集集合合S劃劃分分為為v個(gè)個(gè)子子集集{S1,S2,...,Sv}，，其其中中Sj包包含含了了S集集合合中中屬屬性性A取取aj值值的的數(shù)數(shù)據(jù)據(jù)樣樣本本，，如如果果屬屬性性A被被選選為為測(cè)測(cè)試試屬屬性性(最最好好的的分分裂裂屬屬性性)，，設(shè)設(shè)Sij為為子子集集Sj中中屬屬于于Ci類(lèi)類(lèi)別別的的樣樣本本集集，，根根據(jù)據(jù)A劃劃分分計(jì)計(jì)算算的的熵熵為為:其中中項(xiàng)項(xiàng)為第第j個(gè)個(gè)子子集集的的權(quán)權(quán)，，也也等等于于子子集集中中樣樣本本個(gè)個(gè)數(shù)數(shù)除除以以S中中的的樣樣本本總總數(shù)數(shù)。。熵值越小，，子集劃劃分的純純度越高高。而對(duì)對(duì)于子集集sj有有：其中，是子集sj中樣本屬屬于類(lèi)別別Ci的概率;然后利利用屬性性A對(duì)當(dāng)前分分支結(jié)點(diǎn)點(diǎn)進(jìn)行相相應(yīng)樣本本集合劃劃分計(jì)算算信息增增益:3.最后，求求取信息息增益率率，其表表達(dá)式為為：其中，這個(gè)Gainratio(A)值越越大，分分枝包含含的有用用信息越越多。C4.5算法的的工作流流程圖：：開(kāi)始讀取、存存儲(chǔ)類(lèi)信信息讀取屬性性信息讀取數(shù)據(jù)據(jù)庫(kù)是連續(xù)屬屬性劃分區(qū)域域存儲(chǔ)至屬屬性哈希希表中讀取訓(xùn)練練樣本有缺失數(shù)數(shù)據(jù)忽略或用用最多的的屬性值來(lái)來(lái)替代存儲(chǔ)樣本本表Ｋ次迭代代交叉驗(yàn)驗(yàn)證將數(shù)據(jù)集集劃分成成K個(gè)子子集對(duì)生成的的樹(shù)進(jìn)行行測(cè)試后后打印分分類(lèi)信息息取K-1個(gè)子集集用C4.5算算法建構(gòu)構(gòu)樹(shù)規(guī)則提取取結(jié)束YＮYN四、基于于規(guī)則排排序的決決策樹(shù)分分類(lèi)算算法CABRR的研究究CABRR算法法的產(chǎn)生生CABRR算法法基本本概念念CABRR算法法的基基本思思想及及規(guī)則則排序序算法法CABRR算法法的實(shí)實(shí)例分分析4.1CABRR算法法的產(chǎn)產(chǎn)生CABRR算法法的產(chǎn)產(chǎn)生：：用規(guī)則則構(gòu)造造分類(lèi)類(lèi)器時(shí)時(shí)，對(duì)對(duì)規(guī)則則的排排序分分為兩兩種:基于于規(guī)則則的排排序和和基于于類(lèi)的的排序序。在在使用用基于于類(lèi)的的排序序中，，一個(gè)個(gè)質(zhì)量量較差差的規(guī)規(guī)則可可能碰碰巧預(yù)預(yù)測(cè)較較高秩秩的類(lèi)類(lèi)，從從而導(dǎo)導(dǎo)致較較高質(zhì)質(zhì)量的的規(guī)則則被忽忽略。。而基基于規(guī)規(guī)則的的排序序則能能彌補(bǔ)補(bǔ)這一一點(diǎn)的的不足足，于是出出現(xiàn)了了基于于規(guī)則則的決決策樹(shù)樹(shù)分類(lèi)類(lèi)規(guī)則則算法法CABRR。?；陬?lèi)類(lèi)的排排序：：按照對(duì)對(duì)類(lèi)的的規(guī)則則的描描述長(zhǎng)長(zhǎng)度由由小到到大進(jìn)進(jìn)行排排序。?；谝?guī)規(guī)則的的排序序：結(jié)合規(guī)規(guī)則的的長(zhǎng)度度、準(zhǔn)準(zhǔn)確率率和覆覆蓋率率這三三個(gè)度度量值值進(jìn)行行排序序。4.2CABRR算法法基本本概念念規(guī)則前前件、、規(guī)則則后件件：每一個(gè)個(gè)分類(lèi)類(lèi)規(guī)則則可以以表示示為如如下形形式：：，規(guī)則則左邊邊為規(guī)規(guī)則前前件，，右邊邊為規(guī)規(guī)則后后件。。準(zhǔn)確率率:是指節(jié)節(jié)點(diǎn)中中正確確預(yù)測(cè)測(cè)的實(shí)實(shí)例與與分配配給該該節(jié)點(diǎn)點(diǎn)的實(shí)實(shí)例總總數(shù)之之比，，度量量的是是該節(jié)節(jié)點(diǎn)會(huì)會(huì)正確確預(yù)測(cè)測(cè)目標(biāo)標(biāo)值的的可能能性記記為：：覆蓋率:是指節(jié)點(diǎn)中實(shí)實(shí)例數(shù)量與構(gòu)構(gòu)造數(shù)據(jù)集中中實(shí)例總數(shù)之之比，度量的的是從構(gòu)造數(shù)數(shù)據(jù)集中分配配了多少實(shí)例例給該節(jié)點(diǎn)，，記為：其中|A|是是滿(mǎn)足規(guī)則前前件的記錄數(shù)數(shù)，|Ay|是同時(shí)時(shí)滿(mǎn)足規(guī)則前前件和后件的的記錄數(shù)，|D|是記錄錄總數(shù)。規(guī)則匹配:所謂規(guī)則匹配配，就是對(duì)于于新的對(duì)象，，在規(guī)則集中中查找匹配的的規(guī)則，如果果只有一條規(guī)規(guī)則與之完全全匹配，即各各個(gè)屬性值均均相等，則將將新對(duì)象歸至至匹配規(guī)則決決策值對(duì)應(yīng)的的類(lèi)別;如果果有多個(gè)規(guī)則則與之相匹配配，必須對(duì)所所有匹配規(guī)則則進(jìn)行排序，，然后將新對(duì)對(duì)象歸至優(yōu)先先值最高的規(guī)規(guī)則所定義的的類(lèi)別。4.3CABRR算法法的基本思想想及及規(guī)則排序算算法CABRR分分類(lèi)算法的基基本思想可用用過(guò)程圖表示示如右：數(shù)據(jù)源訓(xùn)練集C4.5算法法歸納生成未剪枝的的決策樹(shù)分類(lèi)規(guī)則規(guī)則排序構(gòu)造分類(lèi)器分類(lèi)結(jié)果分類(lèi)未知類(lèi)別數(shù)據(jù)集開(kāi)始讀取未排好序序的規(guī)則集Rules計(jì)算Rules中每條規(guī)則的長(zhǎng)度度按規(guī)則長(zhǎng)度與與準(zhǔn)確率的乘積對(duì)Rules中規(guī)則則進(jìn)行排序，乘積大大者優(yōu)先某些規(guī)則的長(zhǎng)長(zhǎng)度與準(zhǔn)確確率率的的乘乘積積是是否否相相等等某些些規(guī)規(guī)則則的的長(zhǎng)度度是是否否相相等等按規(guī)規(guī)則則長(zhǎng)長(zhǎng)度度對(duì)對(duì)這這些些規(guī)則則重重新新排排序序按覆覆蓋蓋率率對(duì)對(duì)規(guī)則則進(jìn)進(jìn)行行排排序序排好好序序的的規(guī)規(guī)則則集Rules結(jié)束束YNＹN基于于規(guī)規(guī)則則的的排排序序算算法法的的思思想想流流程程圖圖：：規(guī)則則集集排排序序后后對(duì)對(duì)測(cè)測(cè)試試數(shù)數(shù)據(jù)據(jù)集集進(jìn)進(jìn)行行分分類(lèi)類(lèi)的的流流程程圖圖：：開(kāi)始始讀取取排排好好序序的的規(guī)規(guī)則則集集Rules和測(cè)測(cè)試試數(shù)數(shù)據(jù)據(jù)集集test-data-setfor循循環(huán)環(huán)讀讀取取test-data-set中中的的對(duì)象象，，并并為為其其尋尋找找匹匹配配的的規(guī)規(guī)則則設(shè)置置一一個(gè)個(gè)Flag標(biāo)標(biāo)志志，，賦賦初初值值為為0，，如果果其其值值變變?yōu)闉?，，表表示示Rules中中有與與所所讀讀取取對(duì)對(duì)象象相相匹匹配配得得規(guī)規(guī)則則從前前往往后后掃掃描描Rules，，直到有匹匹配的規(guī)規(guī)則出現(xiàn)現(xiàn)Rules中是是否有匹配的規(guī)規(guī)則將新對(duì)象象歸至匹匹配規(guī)則則所定義的的類(lèi)別，，并使Flag=1尋找覆蓋蓋率最大大的規(guī)則則所定義的的類(lèi)別，，將新對(duì)象歸至至此類(lèi)別別中分好類(lèi)的的數(shù)據(jù)集集結(jié)束NY4.5CABRR算算法的實(shí)實(shí)例分析析接下來(lái)我我們通過(guò)過(guò)實(shí)驗(yàn)證證明使用用基于規(guī)規(guī)則排序序的CABRR算法的的有效性性。取脊椎動(dòng)動(dòng)物數(shù)據(jù)據(jù)集來(lái)做做一個(gè)實(shí)實(shí)驗(yàn)，具具體的數(shù)數(shù)據(jù)如下表（a）所示示：表（a））脊椎動(dòng)動(dòng)物數(shù)據(jù)據(jù)集從上表中中得出的的未截枝枝的決策策樹(shù)如下下圖所示示：體溫胎生水生動(dòng)物物哺乳類(lèi)（（5.0）鳥(niǎo)類(lèi)（2.0））爬行類(lèi)（（2.0）魚(yú)類(lèi)（3.0））兩棲類(lèi)（（3.0/1.0)=恒溫=冷血=是=否