數(shù)據(jù)挖掘 決策樹(shù)

1、數(shù)據(jù)挖掘決策樹(shù)算法數(shù)據(jù)挖掘決策樹(shù)算法書(shū)本DATA Mining concepts and techniques third edition 關(guān)于決策樹(shù)的描述算法Generation_decision_tree的創(chuàng)建過(guò)程如下：1、 創(chuàng)建一個(gè)節(jié)點(diǎn)N2、 IF D的元組都在同一類C中，then返回N作為葉節(jié)點(diǎn)，以類C標(biāo)記3、 IF attribute_list為空，then返回N作為葉節(jié)點(diǎn)，標(biāo)記D中的多數(shù)類4、 使用Attribute_lselection_method(D, attribute_list)找出最好的splitting_criterion5、 用splitting_criterion

2、標(biāo)記節(jié)點(diǎn)N6、 IF splitting_criterion是離散值，并且多路劃分，刪除分裂屬性7、 For splitting_criterion的每個(gè)輸出j:設(shè)Dj中D滿足輸出j的數(shù)據(jù)元組的集合，if Dj為空，加一個(gè)樹(shù)葉到節(jié)點(diǎn)N，標(biāo)記為D中的多數(shù)類，else 加一個(gè)由Generation_decision_tree(D, attribute_list)返回的節(jié)點(diǎn)到N8、 返回N在實(shí)際操作中，選取數(shù)據(jù)很重要，決策樹(shù)是分類算法，在網(wǎng)/ml/選取數(shù)據(jù)時(shí)，選擇Classification類，由于第一次做數(shù)據(jù)分析，以及對(duì)R語(yǔ)言不懂，對(duì)于數(shù)據(jù)的屬性類

3、Attributes選擇在510之間，最終數(shù)據(jù)定位在BreastTissue，Auto-Mpg，car三個(gè)數(shù)據(jù)之一在數(shù)據(jù)的導(dǎo)入過(guò)程，各種數(shù)據(jù)類型不一樣，導(dǎo)入的方式不一樣，最終各種嘗試之后，選擇導(dǎo)入text文本文檔在這個(gè)過(guò)程還是屬性跟數(shù)值對(duì)不齊，至于數(shù)據(jù)框輸入實(shí)現(xiàn)不了，Attribute有七個(gè)，但是數(shù)值有1728個(gè)手動(dòng)輸入是不可行的R語(yǔ)言實(shí)現(xiàn)過(guò)程，參照Generation_decision_tree的創(chuàng)建過(guò)程，通過(guò)先用c實(shí)現(xiàn)，再根據(jù)c結(jié)構(gòu)試探性用r構(gòu)造，期間參考了Python對(duì)于決策樹(shù)算法的實(shí)現(xiàn)過(guò)程，以及實(shí)際案例Iris的實(shí)際案例。1）數(shù)據(jù)輸入以及數(shù)據(jù)判斷是否合理,計(jì)算剛開(kāi)始類別的Info(熵)

4、2）計(jì)算訓(xùn)練集合D對(duì)特征值A(chǔ)的條件熵3）計(jì)算訓(xùn)練集合D對(duì)特征值A(chǔ)的信息增益4）根據(jù)訓(xùn)練集合生成決策樹(shù)：先根據(jù)之前的分類統(tǒng)計(jì)類別出現(xiàn)次數(shù)，然后進(jìn)行排序過(guò)D中都屬于同一類，那么樹(shù)就是單節(jié)點(diǎn)樹(shù)，如果屬性向量為空，那么將D頻數(shù)最高的類返回，計(jì)算屬性向量中各特征值對(duì)D的信息增益，選擇信息增益最大的特征值A(chǔ)g及其信息增益如果最大信息增益小于閾值e，將D中頻數(shù)最高的類別返回，否則，對(duì)Ag的每一可能值ai，依Ag=ai將D分割為若干非空子集Di，將Di中實(shí)例數(shù)最大的類作為標(biāo)記，構(gòu)建子節(jié)點(diǎn)由節(jié)點(diǎn)及其子節(jié)點(diǎn)構(gòu)成樹(shù)T，返回T，然后遞歸調(diào)用，提出已使用的屬性5）出現(xiàn)問(wèn)題，理論上可行但是在實(shí)際用的過(guò)程，return總是

5、出錯(cuò)，重復(fù)調(diào)用有問(wèn)題，還有就是在開(kāi)始用的數(shù)據(jù)包有但是不知道怎么把構(gòu)建的樹(shù)畫(huà)出來(lái)在分析這個(gè)簡(jiǎn)單數(shù)據(jù)的過(guò)程中，決策樹(shù)的構(gòu)建過(guò)程已經(jīng)掌握，用C可以實(shí)現(xiàn)構(gòu)造，但是沒(méi)有掌握R的而且指令語(yǔ)法都不熟，只能進(jìn)行少數(shù)據(jù)手動(dòng)輸入的簡(jiǎn)單分析，對(duì)于大數(shù)據(jù)數(shù)據(jù)導(dǎo)入的分析存在難度，問(wèn)題癥結(jié)所在是對(duì)R的不熟悉，對(duì)于數(shù)據(jù)的預(yù)處理，理論上掌握，手動(dòng)輸入少量數(shù)據(jù)也可以實(shí)現(xiàn)，但是對(duì)于數(shù)據(jù)大規(guī)模整體導(dǎo)入，也有點(diǎn)覺(jué)得束手無(wú)策，解決的辦法就是盡快熟練掌握R語(yǔ)言。數(shù)據(jù)挖掘技術(shù)決策樹(shù)決策樹(shù)是通過(guò)一系列規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類的過(guò)程。建決策樹(shù)，首先根據(jù)記錄字段的不同取值建立樹(shù)的分支，以及在每個(gè)分支子集中重復(fù)建立下層結(jié)點(diǎn)和分支。對(duì)于建立分支時(shí)對(duì)記錄字

6、段不同取值的選擇，采用information gain進(jìn)行屬性選擇。ID3是基于信息熵的決策樹(shù)分類算法，該算法是根據(jù)屬性集的取值選擇實(shí)例的類別。它的核心是在決策樹(shù)中各級(jí)結(jié)點(diǎn)上選屬性，用信息增益率作為屬性選擇標(biāo)準(zhǔn)，使得在每一非葉結(jié)點(diǎn)進(jìn)行測(cè)試時(shí)，能獲得關(guān)于被測(cè)試?yán)幼畲蟮念愋畔?。使用該屬性將例子集分成子集后，系統(tǒng)的熵值最小，期望該非葉結(jié)點(diǎn)到達(dá)各后代葉節(jié)點(diǎn)的平均路徑最短，我們組選用數(shù)據(jù)為是新切除的組織從乳房樣品的電阻抗測(cè)量數(shù)據(jù)集，對(duì)其構(gòu)造決策樹(shù)。首先應(yīng)當(dāng)對(duì)數(shù)據(jù)進(jìn)行分類，用information gain進(jìn)行屬性分類，我們將數(shù)據(jù)按照屬性進(jìn)行分類之后，計(jì)算此分類下的期望l(S1,S2,Sm)=-ilog

7、2(i)(i=1,m，數(shù)據(jù)集為S，m為S的分類數(shù)目, i,(|Sj|)/(|S|),計(jì)算各個(gè)屬性的熵，求由屬性劃分為子集的熵E(A)=(S1j+S2j+,+Smj)/S*I(S1j+S2j+,+Smj)，(A為屬性，具有A個(gè)不同的取值)，求出信息增益Gain(A)=l(S1,S2,Sm )-E(A)，這時(shí)候開(kāi)始選擇Gain(A)最大的也就是E(A)最小的屬性A作為根節(jié)點(diǎn)，用于劃分的屬性。對(duì)于A不同的取值對(duì)應(yīng)不同E的V個(gè)子集Ej 遞歸調(diào)用上述過(guò)程，生成A的子節(jié)點(diǎn)B1，B2,BV。決策樹(shù)任務(wù)：用weka實(shí)現(xiàn)數(shù)據(jù)預(yù)處理，用C4.5算法構(gòu)建決策樹(shù)和通過(guò)10折交叉驗(yàn)證評(píng)估模型的性能，以及模型驗(yàn)證的結(jié)果。

8、l 數(shù)據(jù)集：breast-cancer.arffl 數(shù)據(jù)預(yù)處理：（選擇分類器錯(cuò)分的樣本）點(diǎn)擊apply，可以看到樣本的數(shù)量從286減少到了72 ，l 用C4.5算法構(gòu)建的決策樹(shù)：模型性能的評(píng)估結(jié)果：l decision tree決策樹(shù)的C4.5算法：（1） 用信息增益比例的概念。一個(gè)屬性的信息增益比例用下面的公式給出：決策樹(shù)C4.5算法的偽代碼如下所示：Function C4.5(R,C,S) /建立一個(gè)決策樹(shù) /R:除目標(biāo)屬性外的所有屬性；C：目標(biāo)屬性；S：一個(gè)訓(xùn)練集 Begin If S is empty then Returm 一個(gè)值為failure的結(jié)點(diǎn)； If訓(xùn)練集S中所有的記錄的目

9、標(biāo)屬性為同一個(gè)a then Return具有值為a的結(jié)點(diǎn)； If R為空then Return一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的值為訓(xùn)練集中目標(biāo)屬性中出現(xiàn)最多的目標(biāo)屬性： /這將出現(xiàn)錯(cuò)誤，也就是說(shuō)記錄不能正確分類 For R中的每個(gè)屬性Ri do If Ri 值為連續(xù)值then Begin Al=min(Ri)； Am=max(Ri)；m值手工設(shè)置 For j=2 to m-1 do Aj=Al+j*(Al-Am)/m； 使A為Ri的值，Ri具有最大Gain(Ri,S)<=Aj,>Aj; End;D為R屬性具有最大Gain(D,S)的屬性；D的屬性值為dj | j=1, 2, , m;S的子集Sj | j=1, 2, , m各自包含屬性D的值為dj的記錄；Return根節(jié)點(diǎn)標(biāo)記為D樹(shù)和到d1, d2, ,dm的弧；C4.5(R-D, C, SI),C4.5(R-D,C,S2), ,C4.5(R-D,C,Sm);EndC4.5使用以下的標(biāo)準(zhǔn)終止樹(shù)的增長(zhǎng)：（1） 當(dāng)前節(jié)點(diǎn)的所有的訓(xùn)練集樣本屬于同一類別。（2） 每一個(gè)可能測(cè)試的潛在子樹(shù)中少于兩個(gè)的子樹(shù)有比預(yù)定義數(shù)量多的樣本。該數(shù)量的缺省值是2.（3） 找不到具有真正測(cè)試評(píng)估函數(shù)值得測(cè)試。l evaluate the model performance1. 10-fold cross-validation，用來(lái)測(cè)試精度。是