????????決策樹(DecisionTree)學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法。算法從--組無序、無規(guī)則的事例中推理出決策樹表示形式的分類規(guī)則,決策樹也能表示為多個If-Then規(guī)則。一般在決策樹中采用“自頂向下、分而治之”的遞歸方式,將搜索空間分為若千個互不相交的子集,在決策樹的內(nèi)部節(jié)點(diǎn)(非葉子節(jié)點(diǎn))進(jìn)行屬性值的比較,并根據(jù)不同的屬性值判斷從該節(jié)點(diǎn)向下的分支,在樹的葉節(jié)點(diǎn)得到結(jié)論。
????????數(shù)據(jù)挖掘中的分類常用決策樹實(shí)現(xiàn)。到目前為止,決策樹有很多實(shí)現(xiàn)算法,例如1986年由Quinlan提出的ID3算法和1993年提出的C4.5算法,以及CART,C5.0(C4.5的商業(yè)版本),SLIQ和SPRINT等。本章將詳細(xì)講解ID 3算法和C 4.5算法的基本思想,并結(jié)合實(shí)例講解在MATLAB環(huán)境
下利用決策樹解決分類問題。
1.案例背景
1. 1 決策樹分類器概述
????????1)決策樹分類器的基本思想及其表示
????????決策樹通過把樣本實(shí)例從根節(jié)點(diǎn)排列到某個葉子節(jié)點(diǎn)來對其進(jìn)行分類。樹上的每個非葉子節(jié)點(diǎn)代表對一個屬性取值的測試，其分支就代表測試的每個結(jié)果;而樹上的每個葉子節(jié)點(diǎn)均代表一個分類的類別，樹的最高層節(jié)點(diǎn)是根節(jié)點(diǎn)。
????????簡單地說,決策樹就是一個類似流程圖的樹形結(jié)構(gòu),采用自頂向下的遞歸方式,從樹的根節(jié)點(diǎn)開始,在它的內(nèi)部節(jié)點(diǎn)上進(jìn)行屬性值的測試比較,然后按照給定實(shí)例的屬性值確定對應(yīng)的分支,最后在決策樹的葉子節(jié)點(diǎn)得到結(jié)論。這個過程在以新的節(jié)點(diǎn)為根的子樹上重復(fù)。圖28-1所示為決策樹的結(jié)構(gòu)示意圖。在圖上，每個非葉子節(jié)點(diǎn)代表訓(xùn)練集數(shù)據(jù)的輸人屬性,Attribute Value代表屬性對應(yīng)的值,葉子節(jié)點(diǎn)代表目標(biāo)類別屬性的值。圖中的“Yes”、“No”分別代表實(shí)例集中的正例和反例。
????????2)ID3算法
????????到目前為止,已經(jīng)有很多種決策樹生成算法,但在國際上最有影響力的示例學(xué)習(xí)算法首推J. R. Quinlan的ID 3(Iterative Dichotomic version 3)算法。Quinlan的首創(chuàng)性工作主要是在決策樹的學(xué)習(xí)算法中引入信息論中互信息的概念,他將其稱作信息增益(information gain),以之作為屬性選擇的標(biāo)準(zhǔn)。
????????為了精確地定義信息增益,這里先定義信息論中廣泛使用的一一個度量標(biāo)準(zhǔn)，稱為熵(entropy),它刻畫了任意樣例集的純度(purity)。如果目標(biāo)屬性具有c個不同的值,那么集合S相對于c個狀態(tài)的分類的熵定義為
????????由上式可以得到:若集合S中的所有樣本均屬于同一類,則Entropy(S)=0;若兩個類別的樣本數(shù)不相等,則Entropy(S)∈(0,1)。
????????特殊地,若集合S為布爾型集合,即集合S中的所有樣本屬于兩個不同的類別,則若兩個類別的樣本數(shù)相等,有Entropy(S)=1。 圖28-2描述了布爾型集合的熵與p;的關(guān)系。
????????引入信息增益的概念后，下面將詳細(xì)介紹ID3算法的基本流程。不妨設(shè)Examples為訓(xùn)練樣本集合,Attributelist為候選屬性集合。
????????①創(chuàng)建決策樹的根節(jié)點(diǎn)N;
????????②若所有樣本均屬于同一類別C,則返回N作為-一個葉子節(jié)點(diǎn),并標(biāo)志為C類別;
????????③若Attributelist為空,則返回N作為一一個葉子節(jié)點(diǎn),并標(biāo)志為該節(jié)點(diǎn)所含樣本中類別最多的類別;
????????④計(jì)算Attributelist中各個候選屬性的信息增益，選擇最大的信息增益對應(yīng)的屬性Attribute* ,標(biāo)記為根節(jié)點(diǎn)N;
????????⑤根據(jù)屬性Attribute*值域中的每個值V;,從根節(jié)點(diǎn)N產(chǎn)生相應(yīng)的一個分支,并記S,為Examples集合中滿足Attribute" =V,條件的樣本子集合;
????????⑥若S,為空,則將相應(yīng)的葉子節(jié)點(diǎn)標(biāo)志為Examples樣本集合中類別最多的類別;否則，將屬性Attribute*從Attribute list 中刪除,返回①,遞歸創(chuàng)建子樹。
????????3)C4.5算法
????????針對ID3算法存在的一些缺點(diǎn),許多學(xué)者包括Quinlan都做了大量的研究。C4.5算法便是ID 3算法的改進(jìn)算法,其相比于ID3改進(jìn)的地方主要有:
? ? ? ? ①用信息增益率(gainratio)來選擇屬性
????????信息增益率是用信息增益和分裂信息量(splitinformation)共同定義的,關(guān)系如下:
????????采用信息增益率作為選擇分支屬性的標(biāo)準(zhǔn),克服了ID3算法中信息增益選擇屬性時偏向選擇取值多的屬性的不足。
? ? ? ? ②樹的剪枝
????????剪枝方法是用來處理過擬合問題而提出的,一般分為先剪枝和后剪枝兩種方法。先剪枝方法通過提前停止樹的構(gòu)造,比如決定在某個節(jié)點(diǎn)不再分裂,而對樹進(jìn)行剪枝。一旦停止,該節(jié)點(diǎn)就變?yōu)槿~子節(jié)點(diǎn),該葉子節(jié)點(diǎn)可以取它所包含的子集中類別最多的類作為節(jié)點(diǎn)的類別。
????????后剪枝的基本思路是對完全成長的樹進(jìn)行剪枝,通過刪除節(jié)點(diǎn)的分支,并用葉子節(jié)點(diǎn)進(jìn)行替換,葉子節(jié)點(diǎn)一般用子集中最頻繁的類別進(jìn)行標(biāo)記。
????????C4.5算法采用的悲觀剪枝法(PessimisticPruning)是Quinlan在1987年提出的,屬于后剪枝方法的一種。它使用訓(xùn)練集生成決策樹,并用訓(xùn)練集進(jìn)行剪枝,不需要獨(dú)立的剪枝集。悲觀剪枝法的基本思路是:若使用葉子節(jié)點(diǎn)代替原來的子樹后,誤差率能夠下降，則就用該葉子節(jié)點(diǎn)代替原來的子樹。關(guān)于樹的剪枝詳盡算法,請參考本章的參考文獻(xiàn),此處不再贅述。
????????4)決策樹分類器的優(yōu)缺點(diǎn)
????????相對于其他數(shù)據(jù)挖掘算法,決策樹在以下幾個方面擁有優(yōu)勢:
????????①決策樹易于理解和實(shí)現(xiàn)。人們在通過解釋后都有能力去理解決策樹所表達(dá)的意義。
????????②對于決策樹,數(shù)據(jù)的準(zhǔn)備往往是簡單或者是不必要的。其他的技術(shù)往往要求先把數(shù)據(jù)歸一化，比如去掉多余的或者空白的屬性。
????????③能夠同時處理數(shù)據(jù)型和常規(guī)型屬性。其他的技術(shù)往往要求數(shù)據(jù)屬性單--。
????????④是一個白盒模型。如果給定一個觀察的模型,那么根據(jù)所產(chǎn)生的決策樹很容易推出相應(yīng)的邏輯表達(dá)式。
????????同時,決策樹的缺點(diǎn)也是明顯的，主要表現(xiàn)為:
????????①對于各類別樣本數(shù)量不一致的數(shù)據(jù),在決策樹當(dāng)中信息增益的結(jié)果偏向于那些具有更多數(shù)值的特征。
????????②決策樹內(nèi)部節(jié)點(diǎn)的判別具有明確性,這種明確性可能會帶來誤導(dǎo)。
1.2 問題描述
????????威斯康辛大學(xué)醫(yī)學(xué)院經(jīng)過多年的收集和整理,建立了一個乳腺腫瘤病灶組織的細(xì)胞核顯微圖像數(shù)據(jù)庫。數(shù)據(jù)庫中包含了細(xì)胞核圖像的10個量化特征(細(xì)胞核半徑、質(zhì)地、周長、面積、光滑性、緊密度、凹陷度、凹陷點(diǎn)數(shù)、對稱度、斷裂度),這些特征與腫瘤的性質(zhì)有密切的關(guān)系。因此,需要建立一個確定的模型來描述數(shù)據(jù)庫中各個量化特征與腫瘤性質(zhì)的關(guān)系,從而可以根據(jù)細(xì)胞核顯微圖像的量化特征診斷乳腺腫瘤是良性還是惡性的。
2.模型建立
2.1 設(shè)計(jì)思路
????????將乳腺腫瘤病灶組織的細(xì)胞核顯微圖像的10個量化特征作為模型的輸人，良性乳腺腫瘤和惡性乳腺腫瘤作為模型的輸出。用訓(xùn)練集數(shù)據(jù)進(jìn)行決策樹分類器的創(chuàng)建,然后對測試集數(shù)據(jù)進(jìn)行仿真測試,最后對測試結(jié)果進(jìn)行分析。
2.2 設(shè)計(jì)步驟
????????根據(jù)上述設(shè)計(jì)思路,設(shè)計(jì)步驟主要包括以下幾個部分，如圖28-3所示。
????????1)數(shù)據(jù)采集
????????數(shù)據(jù)來源于威斯康辛大學(xué)醫(yī)學(xué)院的乳腺癌數(shù)據(jù)集,共包括569個病例,其中,良性357例,惡性212例。本書隨機(jī)選取500組數(shù)據(jù)作為訓(xùn)練集,剩余69組作為測試集。每個病例的一組數(shù)據(jù)包括采樣組織中各細(xì)胞核的這10個特征量的平均值、標(biāo)準(zhǔn)差和最壞值(各特征的3個最大數(shù)據(jù)的平均值)共30個數(shù)據(jù)。數(shù)據(jù)文件中每組數(shù)據(jù)共分32個字段:第1個字段為病例編號;第2個字段為確診結(jié)果,B為良性,M為惡性;第3~12個字段是該病例腫瘤病灶組織的各細(xì)胞核顯微圖像的10個量化特征的平均值;第13~22個字段是相應(yīng)的標(biāo)準(zhǔn)差;第23~32個字段是相應(yīng)的最壞值。
????????2)決策樹分類器創(chuàng)建
????????數(shù)據(jù)采集完成后,利用MATLAB自帶的統(tǒng)計(jì)工具箱函數(shù)ClassificationTree. fit(MATLAB R2012b)或classregtree(MATLAB R2009a) ,即可基于訓(xùn)練集數(shù)據(jù)創(chuàng)建一個決策樹分類器。
????????3)仿真測試
????????決策樹分類器創(chuàng)建好后,利用MATLAB自帶的統(tǒng)計(jì)工具箱函數(shù)predict(MATLABR2012b)或eval(MATLAB R2009a),即可對測試集數(shù)據(jù)進(jìn)行仿真預(yù)測。
????????4)結(jié)果分析
????????通過對決策樹分類器的仿真結(jié)果進(jìn)行分析,可以得到誤診率(包括良性被誤診為惡性、惡性被誤診為良性),從而可以對該方法的可行性進(jìn)行評價。同時,可以與其他方法進(jìn)行比較,探討該方法的有效性。
3 決策樹分類器編程實(shí)現(xiàn)
? ? ? ? 決策樹分類器完整代碼實(shí)現(xiàn)如下：
%% 決策樹分類器在乳腺癌診斷中的應(yīng)用研究
%% 清空環(huán)境變量
clear all
clc
warning off
%% 導(dǎo)入數(shù)據(jù)
load data.mat
% 隨機(jī)產(chǎn)生訓(xùn)練集/測試集
a = randperm(569);
Train = data(a(1:500),:);
Test = data(a(501:end),:);
% 訓(xùn)練數(shù)據(jù)
P_train = Train(:,3:end);
T_train = Train(:,2);
% 測試數(shù)據(jù)
P_test = Test(:,3:end);
T_test = Test(:,2);
%% 創(chuàng)建決策樹分類器
ctree = ClassificationTree.fit(P_train,T_train);
% 查看決策樹視圖
view(ctree);
view(ctree,'mode','graph');
%% 仿真測試
T_sim = predict(ctree,P_test);
%% 結(jié)果分析
count_B = length(find(T_train == 1));
count_M = length(find(T_train == 2));
rate_B = count_B / 500;
rate_M = count_M / 500;
total_B = length(find(data(:,2) == 1));
total_M = length(find(data(:,2) == 2));
number_B = length(find(T_test == 1));
number_M = length(find(T_test == 2));
number_B_sim = length(find(T_sim == 1 & T_test == 1));
number_M_sim = length(find(T_sim == 2 & T_test == 2));
disp(['病例總數(shù)：' num2str(569)...
' 良性：' num2str(total_B)...
' 惡性：' num2str(total_M)]);
disp(['訓(xùn)練集病例總數(shù)：' num2str(500)...
' 良性：' num2str(count_B)...
' 惡性：' num2str(count_M)]);
disp(['測試集病例總數(shù)：' num2str(69)...
' 良性：' num2str(number_B)...
' 惡性：' num2str(number_M)]);
disp(['良性乳腺腫瘤確診：' num2str(number_B_sim)...
' 誤診：' num2str(number_B - number_B_sim)...
' 確診率p1=' num2str(number_B_sim/number_B*100) '%']);
disp(['惡性乳腺腫瘤確診：' num2str(number_M_sim)...
' 誤診：' num2str(number_M - number_M_sim)...
' 確診率p2=' num2str(number_M_sim/number_M*100) '%']);
%% 葉子節(jié)點(diǎn)含有的最小樣本數(shù)對決策樹性能的影響
leafs = logspace(1,2,10);
N = numel(leafs);
err = zeros(N,1);
for n = 1:N
t = ClassificationTree.fit(P_train,T_train,'crossval','on','minleaf',leafs(n));
err(n) = kfoldLoss(t);
end
plot(leafs,err);
xlabel('葉子節(jié)點(diǎn)含有的最小樣本數(shù)');
ylabel('交叉驗(yàn)證誤差');
title('葉子節(jié)點(diǎn)含有的最小樣本數(shù)對決策樹性能的影響')
%% 設(shè)置minleaf為28，產(chǎn)生優(yōu)化決策樹
OptimalTree = ClassificationTree.fit(P_train,T_train,'minleaf',28);
view(OptimalTree,'mode','graph')
% 計(jì)算優(yōu)化后決策樹的重采樣誤差和交叉驗(yàn)證誤差
resubOpt = resubLoss(OptimalTree)
lossOpt = kfoldLoss(crossval(OptimalTree))
% 計(jì)算優(yōu)化前決策樹的重采樣誤差和交叉驗(yàn)證誤差
resubDefault = resubLoss(ctree)
lossDefault = kfoldLoss(crossval(ctree))
%% 剪枝
[~,~,~,bestlevel] = cvLoss(ctree,'subtrees','all','treesize','min')
cptree = prune(ctree,'Level',bestlevel);
view(cptree,'mode','graph')
% 計(jì)算剪枝后決策樹的重采樣誤差和交叉驗(yàn)證誤差
resubPrune = resubLoss(cptree)
lossPrune = kfoldLoss(crossval(cptree))
?
?
?
病例總數(shù)：569 ?良性：357 ?惡性：212
訓(xùn)練集病例總數(shù)：500 ?良性：315 ?惡性：185
測試集病例總數(shù)：69 ?良性：42 ?惡性：27
良性乳腺腫瘤確診：41 ?誤診：1 ?確診率p1=97.619%
惡性乳腺腫瘤確診：26 ?誤診：1 ?確診率p2=96.2963%
5.案例擴(kuò)展
????????一般而言,對于一個“枝繁葉茂”的決策樹，訓(xùn)練集樣本的分類正確率通常較高。然而,并不能保證對于獨(dú)立的測試集也有近似的分類正確率。這是因?yàn)椋爸Ψ比~茂”的決策樹往往是過擬合的。相反,對于一個結(jié)構(gòu)簡單(分叉少、葉子節(jié)點(diǎn)少)的決策樹，訓(xùn)練集樣本的分類正確率并非特別高，但是可以保證測試集的分類正確率。
?文章來源地址http://www.zghlxwxcb.cn/news/detail-658068.html
?文章來源：http://www.zghlxwxcb.cn/news/detail-658068.html
?
?
到了這里，關(guān)于基于決策樹(Decision Tree)的乳腺癌診斷的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
