基于決策樹規(guī)則分類算法的研究(12-15)ppt課件

1、基于決策樹規(guī)那么分類算法的研討報(bào)告人：孫秀芳2021年12月15日.引見內(nèi)容研討的主要內(nèi)容數(shù)據(jù)發(fā)掘及其分類方法概述C4.5算法基于規(guī)那么排序的決策樹分類算法CABRR的研討. 一、研討的主要內(nèi)容 研討的主要內(nèi)容：從決策樹入手，從中提取決策樹規(guī)那么，并經(jīng)過對決策樹規(guī)那么進(jìn)展有效地排序后生成分類器，運(yùn)用于分類預(yù)測。. 二、數(shù)據(jù)發(fā)掘及其分類方法概述數(shù)據(jù)發(fā)掘的實(shí)際分類概念及算法描畫分類算法度量的方法與尺度.2.1 數(shù)據(jù)發(fā)掘的實(shí)際數(shù)據(jù)發(fā)掘的概念：所謂數(shù)據(jù)發(fā)掘又稱數(shù)據(jù)庫中的知識發(fā)現(xiàn)是指從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的海量數(shù)據(jù)中，或是大型數(shù)據(jù)庫或數(shù)據(jù)倉庫中提取隱含的、未知的、非平凡的、有潛在運(yùn)用

2、價(jià)值的信息或方式。數(shù)據(jù)發(fā)掘的過程：確定發(fā)掘目的、數(shù)據(jù)預(yù)備、數(shù)據(jù)發(fā)掘、方式評價(jià)與知識表示。. 數(shù)據(jù)發(fā)掘的詳細(xì)過程如以下圖所示：數(shù)據(jù)源 清理/集成后數(shù)據(jù)選擇/變換后數(shù)據(jù)模式提供可供發(fā)掘的知識清理與集成選擇與變換數(shù)據(jù)發(fā)掘評價(jià)與表示.2.2 分類概念及算法描畫分類的概念：所謂分類，就是對己知現(xiàn)存的類別，建立類別的描畫規(guī)那么分類器，然后對未知新例的察看值進(jìn)展判別歸類。以下圖為分類過程圖：訓(xùn)練集分類模型可接受的模型預(yù)測結(jié)果經(jīng)過分類算法建立模型評價(jià)模型預(yù)測未知數(shù)據(jù)元組. 典型的分類算法: 常用的分類方法包括：決策樹分類、關(guān)聯(lián)分類、神經(jīng)網(wǎng)絡(luò)、貝葉斯分類方法等。 基于決策樹分類的典型算法有:ID3算法、C4.5

3、算法、PART算法、CABRR算法等。.2.3 分類算法度量的方法與尺度每種分類方法都需求用一定的目的來進(jìn)展評價(jià)，常用的分類算法的比較與評價(jià)規(guī)范有如下幾個(gè)方面： 預(yù)測的準(zhǔn)確率 可了解性 可伸縮性 速度 強(qiáng)健性 . 三、C4.5算法決策樹算法的根本實(shí)際決策樹的根本算法C4.5算法.3.1 決策樹算法的根本實(shí)際決策樹：是一種構(gòu)造，一種知識的表達(dá)方式，它由兩種元素組成:節(jié)點(diǎn)和分支。在最終生成的決策樹上，其中每個(gè)內(nèi)部節(jié)點(diǎn)表示數(shù)據(jù)集的一個(gè)屬性，每個(gè)分支代表對該屬性的一個(gè)測試輸出，每個(gè)葉結(jié)點(diǎn)代表劃分的類別，最頂端節(jié)點(diǎn)為根節(jié)點(diǎn)。決策樹的生成過程：主要分成兩個(gè)步驟:一是生成樹，二是樹的修剪。樹的修剪：即樹的剪

4、枝，最常用的剪枝技術(shù)有預(yù)剪枝和后剪枝。. 決策樹的任務(wù)原理流程圖如下：數(shù)據(jù)源訓(xùn)練集預(yù)處置決策樹分類算法歸納生成決策樹分類規(guī)那么剪枝.3.2 決策樹的根本算法Generate_decision_tree/根據(jù)給定數(shù)據(jù)集產(chǎn)生一個(gè)決策樹輸入：訓(xùn)練樣本，各屬性均取離散數(shù)值，可供歸納的候選屬性集為:attribute_list。輸出：決策樹。處置流程程：1創(chuàng)建一個(gè)結(jié)點(diǎn)；2假設(shè)該結(jié)點(diǎn)中的一切樣本均為同一類別C，那么3 前往N作為一 個(gè)葉結(jié)點(diǎn)并標(biāo)志為類別C；4假設(shè)attribute_list為空，那么5 前往N作為一個(gè)葉結(jié)點(diǎn)并標(biāo)志為該結(jié)點(diǎn)所含樣本中類別個(gè) 數(shù)最多的類別；6從attribute_list選擇一

5、個(gè)信息增益最大的屬性test_attribute；. 7并將結(jié)點(diǎn)N標(biāo)志為test_attribute；8對于test_attribute中的每一個(gè)知取值ai預(yù)備劃分結(jié)點(diǎn)N所包含的樣本集；9根據(jù)test_attribute=ai條件，從結(jié)點(diǎn)N產(chǎn)生相應(yīng)的一個(gè)分支，以表示該測試條件；10設(shè)si為test_attribute=ai條件所獲得的樣本集合；11假設(shè)si為空，那么將相應(yīng)葉結(jié)點(diǎn)標(biāo)志為該結(jié)點(diǎn)所含樣本中類別個(gè)數(shù)最多的類別；12否那么將相應(yīng)葉結(jié)點(diǎn)標(biāo)志為Generate_decision_tree(si,attribute_list-test_attribute)前往值；. 3.3 C4.5算法C4.

6、5算法：是對ID3的改良算法。該算法采用信息增益率作為對選擇分枝屬性的分枝準(zhǔn)那么，計(jì)算各屬性的信息增益率，然后選取信息增益率最大的屬性作為結(jié)點(diǎn)，自頂向下生成決策樹。. 對構(gòu)造C4.5決策樹的相關(guān)實(shí)際的描畫如下:1.首先計(jì)算給定的樣本所需的期望信息,設(shè)S為一個(gè)包含s個(gè)數(shù)據(jù)樣本的集合，對于類別屬性，可以取m個(gè)不同的值,對應(yīng)于m個(gè)不同的類別Ci ( i 1,2,.,m)。假設(shè)類別Ci中的樣本個(gè)數(shù)為si，期望信息為: 其中pi是恣意樣本屬于Ci的概率，并用si/s估計(jì) 。 2.接著計(jì)算當(dāng)前樣本集合所需求的信息嫡，設(shè)一個(gè)屬性A具有v個(gè)不同的值a1,a2,.,av,利用屬性A可以將集合S劃分為v個(gè)子集S1

7、,S2,.,Sv，其中Sj包含了S集合中屬性A取aj值的數(shù)據(jù)樣本，假設(shè)屬性A被選為測試屬性(最好的分裂屬性)，設(shè)Sij為子集Sj中屬于Ci類別的樣本集，根據(jù)A劃分計(jì)算的熵為: . 其中項(xiàng) 為第j個(gè)子集的權(quán)，也等于子集中樣本個(gè)數(shù)除以S中的樣本總數(shù)。熵值越小，子集劃分的純度越高。而對于子集sj有： 其中， 是子集sj中樣本屬于類別Ci的概率;然后利用屬性A對當(dāng)前分支結(jié)點(diǎn)進(jìn)展相應(yīng)樣本集合劃分計(jì)算信息增益:. 3. 最后，求取信息增益率，其表達(dá)式為： 其中， 這個(gè)Gainratio(A)值越大，分枝包含的有用信息越多。. C4.5算法的任務(wù)流程圖：開場讀取、存儲類信息讀取屬性信息讀取數(shù)據(jù)庫是延續(xù)屬性劃

8、分區(qū)域存儲至屬性哈希表中讀取訓(xùn)練樣本有缺失數(shù)據(jù)忽略或用最多的屬性值來替代存儲樣本表次迭代交叉驗(yàn)證將數(shù)據(jù)集劃分成K個(gè)子集對生成的樹進(jìn)展測試后打印分類信息取K-1個(gè)子集用C4.5算法建構(gòu)樹規(guī)那么提取終了YYN.四、基于規(guī)那么排序的決策樹分類算法CABRR的研討CABRR算法的產(chǎn)生 CABRR算法根本概念CABRR算法的根本思想及規(guī)那么排序算法CABRR算法的實(shí)例分析.4.1 CABRR算法的產(chǎn)生CABRR算法的產(chǎn)生：用規(guī)那么構(gòu)造分類器時(shí)，對規(guī)那么的排序分為兩種:基于規(guī)那么的排序和基于類的排序。在運(yùn)用基于類的排序中，一個(gè)質(zhì)量較差的規(guī)那么能夠碰巧預(yù)測較高秩的類，從而導(dǎo)致較高質(zhì)量的規(guī)那么被忽略。而基于規(guī)

9、那么的排序那么能彌補(bǔ)這一點(diǎn)的缺乏，于是出現(xiàn)了基于規(guī)那么的決策樹分類規(guī)那么算法CABRR?；陬惖呐判颍喊凑諏︻惖囊?guī)那么的描畫長度由小到大進(jìn)展排序?；谝?guī)那么的排序：結(jié)合規(guī)那么的長度、準(zhǔn)確率和覆蓋率這三個(gè)度量值進(jìn)展排序。. 4.2 CABRR算法根本概念規(guī)那么前件、規(guī)那么后件：每一個(gè)分類規(guī)那么可以表示為如下方式： ，規(guī)那么左邊為規(guī)那么前件，右邊為規(guī)那么后件。準(zhǔn)確率:是指節(jié)點(diǎn)中正確預(yù)測的實(shí)例與分配給該節(jié)點(diǎn)的實(shí)例總數(shù)之比，度量的是該節(jié)點(diǎn)會正確預(yù)測目的值的能夠性記為：覆蓋率:是指節(jié)點(diǎn)中實(shí)例數(shù)量與構(gòu)造數(shù)據(jù)集中實(shí)例總數(shù)之比，度量的是從構(gòu)造數(shù)據(jù)集中分配了多少實(shí)例給該節(jié)點(diǎn)，記為： 其中|A|是滿足規(guī)那么前件的

10、記錄數(shù)，|A y|是同時(shí)滿足規(guī)那么前件和后件的記錄數(shù)，|D|是記錄總數(shù)。. 規(guī)那么匹配:所謂規(guī)那么匹配，就是對于新的對象，在規(guī)那么集中查找匹配的規(guī)那么，假設(shè)只需一條規(guī)那么與之完全匹配，即各個(gè)屬性值均相等，那么將新對象歸至匹配規(guī)那么決策值對應(yīng)的類別;假設(shè)有多個(gè)規(guī)那么與之相匹配，必需對一切匹配規(guī)那么進(jìn)展排序，然后將新對象歸至優(yōu)先值最高的規(guī)那么所定義的類別。. 4.3 CABRR算法的根本思想 及規(guī)那么排序算法CABRR分類算法的根本思想可用過程圖表示如右：數(shù)據(jù)源訓(xùn)練集C4.5算法歸納生成未剪枝的決策樹分類規(guī)那么規(guī)那么排序構(gòu)造分類器分類結(jié)果分類未知類別數(shù)據(jù)集.開場讀取未排好序的規(guī)那么集Rules計(jì)算

11、Rules中每條規(guī)那么的長度按規(guī)那么長度與準(zhǔn)確率的乘積對Rules中規(guī)那么進(jìn)展排序，乘積大者優(yōu)先某些規(guī)那么的長度與準(zhǔn)確率的乘積能否相等某些規(guī)那么的長度能否相等按規(guī)那么長度對這些規(guī)那么重新排序按覆蓋率對規(guī)那么進(jìn)展排序排好序的規(guī)那么集Rules終了YNN 基于規(guī)那么的排序算法的思想流程圖：.規(guī)那么集排序后對測試數(shù)據(jù)集進(jìn)展分類的流程圖：開場讀取排好序的規(guī)那么集Rules和測試數(shù)據(jù)集test-data-setfor循環(huán)讀取test-data-set中的對象，并為其尋覓匹配的規(guī)那么 設(shè)置一個(gè)Flag標(biāo)志，賦初值為0，假設(shè)其值變?yōu)?，表示Rules中有與所讀取對象相匹配得規(guī)那么 從前往后掃描Rules，直

12、到有匹配的規(guī)那么出現(xiàn)Rules中能否有匹配的規(guī)那么將新對象歸至匹配規(guī)那么所定義的類別，并使Flag=1尋覓覆蓋率最大的規(guī)那么所定義的類別，將新對象歸至此類別中分好類的數(shù)據(jù)集終了NY. 4.5 CABRR算法的實(shí)例分析 接下來我們經(jīng)過實(shí)驗(yàn)證明運(yùn)用基于規(guī)那么排序的CABRR算法的有效性。 取脊椎動(dòng)物數(shù)據(jù)集來做一個(gè)實(shí)驗(yàn)，詳細(xì)的數(shù)據(jù)如下表a所示：. 表a脊椎動(dòng)物數(shù)據(jù)集名字體溫表皮覆蓋胎生水生動(dòng)物飛行動(dòng)物有腿冬眠類標(biāo)號人類恒溫毛發(fā)是否否是否哺乳類蟒蛇冷血鱗片否否否否是爬行類鮭魚冷血鱗片否是否否否魚類鯨恒溫毛發(fā)是是否否否哺乳類青蛙冷血無否半否是是兩棲類巨蜥冷血鱗片否否否是否爬行類蝙蝠恒溫毛發(fā)是否是是是哺乳

13、類鴿子恒溫羽毛否否是是否鳥類貓恒溫軟毛是否否是否哺乳類虹鱂冷血鱗片是是否否否魚類美洲鱷冷血鱗片否半否是否爬行類企鵝恒溫羽毛否半否是否鳥類豪豬恒溫剛毛是否否是是哺乳類鰻鱺冷血鱗片否是否否否魚類蠑螈冷血無否半否是是兩棲類. 從上表中得出的未截枝的決策樹如以下圖所示：體溫胎生水生動(dòng)物哺乳類5.0鳥類2.0爬行類2.0魚類3.0兩棲類3.0/1.0)=恒溫=冷血=是=否=否=是=半. 對規(guī)那么進(jìn)展截枝后，得到的規(guī)那么如以下圖所示：. 詳細(xì)的規(guī)那么信息如以下圖所示：然后分別用基于規(guī)那么的排序算法和基于類的排序算法對規(guī)那么進(jìn)展排序，排序后的規(guī)那么按優(yōu)先順序從高到低排序后分別如下表b、c所示： . 表b基于

14、規(guī)那么進(jìn)展排序后的規(guī)那么列表 表c基于類進(jìn)展排序后的規(guī)那么列表 ruleclassconfsuplength體溫=冷血 AND 水生動(dòng)物=否爬行類50.00%22體溫=恒溫 AND 胎生=否鳥類50.00%22胎生=是哺乳類61.20%61水生動(dòng)物=是魚類45.30%21Default class: 兩棲類 ruleclassconfsuplength胎生=是哺乳類61.20%61水生動(dòng)物=是魚類45.30%21體溫=冷血 AND 水生動(dòng)物=否爬行類50.00%22體溫=恒溫 AND 胎生=否鳥類50.00%22Default class: 兩棲類. 用表b和表c的規(guī)那么構(gòu)造分類器，分別對表a

15、中的數(shù)據(jù)進(jìn)展預(yù)測分類，得出的分類結(jié)果如表d和表e所示：. 表d用基于規(guī)那么排序后的分類器進(jìn)展預(yù)測分類的結(jié)果名字體溫表皮覆蓋胎生水生動(dòng)物飛行動(dòng)物有腿冬眠類標(biāo)號類排序分類人類恒溫毛發(fā)是否否是否哺乳類哺乳類蟒蛇冷血鱗片否否否否是爬行類爬行類鮭魚冷血鱗片否是否否否魚類魚類鯨恒溫毛發(fā)是是否否否哺乳類哺乳類青蛙冷血無否半否是是兩棲類兩棲類巨蜥冷血鱗片否否否是否爬行類爬行類蝙蝠恒溫毛發(fā)是否是是是哺乳類哺乳類鴿子恒溫羽毛否否是是否鳥類鳥類貓恒溫軟毛是否否是否哺乳類哺乳類虹鱂冷血鱗片是是否否否魚類魚類美洲鱷冷血鱗片否半否是否爬行類兩棲類企鵝恒溫羽毛否半否是否鳥類鳥類豪豬恒溫剛毛是否否是是哺乳類哺乳類鰻鱺冷血鱗片否是否否否魚類魚類蠑螈冷血無否半否是是兩棲類兩棲類. 表e用基于類排序后的分類器進(jìn)展預(yù)測分類的結(jié)果名字體溫表皮覆蓋胎生水生動(dòng)物飛行動(dòng)物有腿冬眠類標(biāo)號類排序分類人類恒溫毛發(fā)是否否是否哺乳類哺乳類蟒蛇冷血鱗片否否否否是爬行類爬行類鮭魚冷血鱗片否是否否否魚類魚類鯨恒溫毛發(fā)是是否否否哺乳類哺乳類青蛙冷血無否半否是是兩棲類兩棲類巨蜥冷血鱗片否否否是否爬行類爬行類蝙蝠恒溫毛發(fā)是否是是是哺乳類哺乳類鴿子恒溫羽毛否