摘 要：本實驗的目的是學習和掌握分類回歸樹算法。CART提供一種通用的樹生長框架，它可以實例化為各種各樣不同的判定樹。CART算法采用一種二分遞歸分割的技術，將當前的樣本集分為兩個子樣本集，使得生成的決策樹的每個非葉子節點都有兩個分支。因此，CART算法生成的決策樹是結構簡潔的二叉樹。在MATLAB平臺上編寫程序，較好地實現了非剪枝完全二叉樹的創建、應用以及近似剪枝操作，同時把算法推廣到多叉樹。
##一、技術論述
**1.非度量方法**
在之前研究的多種模式分類算法中，經常會使用到樣本或向量之間距離度量(distance metric)的方法。最典型的是最近鄰分類器，距離的概念是這個分類方法的根本思想所在。在神經網絡中，如果兩個輸入向量足夠相似，則它們的輸出也很相似。總的來說，大多數的模式識別方法在研究這類問題中，由于特征向量是實數數據，因此自然擁有距離的概念。
而在現實世界中，另外一類酚類問題中使用的是“語義數據”(nominal data)，又稱為“標稱數據”或“名義數據”。這些數據往往是離散的，其中沒有任何相似性的概念，甚至沒有次序的關系。以下給出一個簡單的例子：
試用牙齒的信息對魚和海洋哺乳動物分類。一些魚的牙齒細小而精致（如巨大的須鯨），這種牙齒用于在海里篩濾出微小的浮游生物來吃；另一些有成排的牙齒（如鯊魚）；一些海洋動物，如海象，有很長的牙齒；而另外一些，如魷魚，則根本沒有牙齒。這里并沒有一個清楚的概念來表示關于牙齒的相似性或距離度量，打個比方，須鯨和海象的牙齒之間并不比鯊魚和魷魚之間更相似。本實驗的目的是將以往以實向量形式表示的模式，轉變成以非度量(nonmetric)的語義屬性來表示的模式。
**2.判定樹**
利用一系列的查詢回答來判斷和分類某模式是一種很自然和直觀的做法。有一個問題的提法依賴于前一個問題的回答。這種“問卷表”方式的做法對非度量數據特別有效，因為回答問題時的是“是/否”、“真/假”、“屬性值”等并不涉及任何距離測度概念。這些實際問題可以用有向的判定樹(decision tree)的形式表示。從結構上看，一棵樹的第一個節點又稱為根節點，存在于最上方，與其他節點通過分支實現有序的相連。繼續上述的構造過程，知道沒有后續的葉節點為止，下圖給出了一個判定樹的實例。
從根節點開始，對模式的某一屬性的取值提問。與根節點相連的不同分支，對應這個屬性的不同取值，根據不同的結果轉向響應的后續子節點。這里需要注意的是樹的各分支之間必須是互斥的，且各分支覆蓋了整個可能的取值空間。
在把當前到達的節點視為新的根節點，做同樣的分支判斷。不斷繼續這一過程直至到達葉節點。每個葉節點都擁有一個相應的類別標記，測試樣本被標記為它所到達的葉節點的類別標記。
決策樹算法相比其他分類器（如神經網絡）的優點之一是，樹中所體現的語義信息，容易直接用邏輯表達式表示出。而樹分類器的另外一個有點是分類速度快。這是因為樹提供了一種很自然的嵌入人類專家的先驗知識的機制，在實際中，當問題較為簡單且訓練樣本較少的情況下，這類專家知識往往十分有效。
**3.分類和回歸樹(CART)算法**
綜合以上概念，這里討論一個問題，即基于訓練樣本構造或“生成一棵判定樹”的問題。假設一個訓練樣本集D，該訓練集擁有類別標記，同時確定了一個用于判定模式的屬性集。對于一棵判定樹，其任務是把訓練樣本逐步劃分成越來越小的子集，一個理想的情況是每個子集中所有的樣本均擁有同種類別標記，樹的分類操作也到此結束，這類子集稱為“純”的子集。而一般情況下子集中的類別標記并不唯一，這時需要執行一個操作，要么接受當前有“缺陷”的判決結果，停止繼續分類；要么另外選取一個屬性進一步生長該樹，這一過程是一種遞歸結構的樹的生長過程。
若從數據結構的角度來看，數據表示在每個節點上，要么該節點已經是葉節點（自身已擁有明確的類別標記），要么利用另一種屬性，繼續分裂出子節點。分類和回歸樹是僅有的一種通用的樹生長算法。CART提供一種通用的框架，使用者可以將其實例化為各種不同的判定樹。
**3.1 CART算法的分支數目**
節點處的一次判別稱為一個分支，它將訓練樣本劃分成子集。根節點處的分支對應于全部訓練樣本，氣候每一次判決都是一次子集劃分過程。一般情況下，節點的分支數目由樹的設計者確定，并且在一棵樹上可能有不同的值。從一個節點中分出去的分支數目有時稱為節點的分支率(branching ratio)，這里用B表示。這里需要說明一個事實，即每個判別都可以用二值判別表示出來。由于二叉樹具有普適性，而且構造比較方便，因此被廣泛采用。
**3.2 CART算法中查詢的選取與節點不純度**
在決策樹的設計過程中，一個重點是考慮在每個節點處應該選出測試或查詢哪一個屬性。我們知道對于數值數據，用判定樹的方法得到的分類邊界存在著較為自宏觀的幾何解釋；而對于非數值數據，在節點處作查詢進而劃分數據的過程并沒有直接的幾何解釋。
構造樹的過程的一個基本原則是簡單。我們期望獲得的判定樹簡單緊湊，只有很少的節點。本著這一目標，應試圖尋找這樣一個查詢T，它能使后繼節點數據盡可能的“純”。這里需要定義“不純度”的指標。用i(N)表示節點N的“不純度”，當節點上的模式數據均來自同一類別時，令i(N)=0；若類別標記均勻分布時，i(N)應當比較大。一種最流行的測量稱為“熵不純度”(entropy impurity)，又稱為信息量不純度(information impurity)：
其中P(ωj)是節點N處屬于ωj類模式樣本數占總樣本數的頻度。根據熵的特性，如果所有模式的樣本都來自同一類別，則不純度為零，否則則大于零。當且僅當所有類別以等概率出現時，熵值取最大值。以下給出另外幾種常用的不純度定義：
“平方不純度”，根據當節點樣本均來自單一類別時不純度為0的思想，用以下多項式定義不純度，該值與兩類分布的總體分布方差有關：
“Gini不純度”，用于多類分類問題的方差不純度（也是當節點N的類別標記任意選取時對應的誤差率）：
當類別標記等概率時“Gini不純度”指標的峰度特性比“熵不純度”要好。
“誤分類不純度”，用于衡量節點N處訓練樣本分類誤差的最小概率：
該指標在之前討論過的不純度指標中當等概率標記時具有最好的峰值特性。然而由于存在不連續的導數值，因而在連續參數空間搜索最大值時會出現問題。
當給定一種不純度計算方法，另一個關鍵問題是：對于一棵樹，目前已生長到節點N，要求對該節點作屬性查詢T，應該如何選擇待查詢值s？一種思路是選擇那個能夠使不純度下降最快的那個查詢，不純度的下降公式可寫為：
其中N_L和N_R分別表示左右子節點，i(N_L)和i(N_R)是相應的不純度。P_L是當查詢T被采納時，樹由N生長到N_L的概率。若采用熵不純度指標，則不純度的下降差就是本次查詢所能提供的信息增益。由于二叉樹的每次查詢僅僅給出是/否的回答，所以每次分支所引起的熵不純度的下降差不會超過1位。
##二、實驗步驟
訓練數據：
編寫一個生成二叉分類樹的通用程序，并使用上表中的數據來訓練該樹，訓練過程中使用熵不純度進行分支。通過過程中的判決條件，使用treeplot函數畫出決策二叉樹，如下圖所示。
用上述程序訓練好的非剪枝完全樹，分類下列模式：?
{A,E,I,L,N},{D,E,J,K,N},{B,F,J,K,M},{C,D,J,L,N}
用上述程序訓練好的非剪枝完全樹，選擇其中的一對葉節點進行剪枝，使剪枝后樹的熵不純度的增量盡可能小。
##三、實驗結果
使用未剪枝的樹進行分類：
使用剪枝后的樹進行分類：
**四、MATLAB代碼**
主函數：
~~~
clear all; clc; close all;
%% 數據預處理
% 訓練樣本
w1 = ['AEHKM'; 'BEILM'; 'AGILN'; 'BGHKM'; 'AGILM'];
w2 = ['BFILM'; 'BFJLN'; 'BEILN'; 'CGJKN'; 'CGJLM'; 'DGJKM'; 'BDILM'];
w3 = ['DEHKN'; 'AEHKN'; 'DEHLN'; 'DFJLN'; 'AFHKN'; 'DEJLM'; 'CFJLM'; 'DFHLM'];
w = [w1; w2; w3];
C = [ones(5,1); 2*ones(7,1); 3*ones(8,1)]; % 分類標簽
% 數據范圍
Region = ['AD'; 'EG'; 'HJ'; 'KL'; 'MN'];
%測試樣本
T1 = 'AEILN';
T2 = 'DEJKN';
T3 = 'BFJKM';
T4 = 'CDJLM';
%字符串矩陣 數據轉化為 相應的自然數矩陣，方便后續處理
w = w + 0; % w=abs(w)
Region = abs(Region);
global Tree;
global Flag;
%% 非剪枝完全樹
%建立一二叉樹并用樣本進行訓練
Tree = CART_MakeBinaryTree(w, C, Region)
p=[0 1 2 3 4 4 3 2 8 9 10 10 9 8 1 15 15];
treeplot(p)%畫出二叉樹
%使用該分類樹
W1 = CART_UseBinaryTree(Tree,T1)
W2 = CART_UseBinaryTree(Tree,T2)
W3 = CART_UseBinaryTree(Tree,T3)
W4 = CART_UseBinaryTree(Tree,T4)
%% B 剪枝
W1=CART_PruningBinaryTree(Tree,T1)
W2=CART_PruningBinaryTree(Tree,T2)
W3=CART_PruningBinaryTree(Tree,T3)
W4=CART_PruningBinaryTree(Tree,T4)
%% 多叉樹分類
%AnyTree=CART_MakeAnyTree(w, C, Region)
%MultiTree=CART_MakeMultiTree(w, C, Region)
~~~
~~~
function Tree = CART_MakeBinarySortTree(Train_Samples, TrainingTargets, Region)
% 基于 熵不純度 遞歸地實現 非剪枝完全二叉樹
% 輸入變量：
% Train_Samples：n個d維訓練樣本，為(n * d)的矩陣
% TrainingTargets：對應的類別屬性，為(n * 1)的矩陣
% Region：特征向量維度順序下上限，為(d * 2)的矩陣（特征值取離散的自然數區間，左小右大）
% 輸出變量：一個基本樹形節點 Tree
% 基本樹形節點結構
% 一：標簽（記錄當前節點判定所用的維度，表葉子時為空）；
% 二：閾值（記錄當前所用維度判定之閾值，葉子節點時表類別）；
% 三：左枝（小于等于閾值的待分目標 歸于此，表葉子時為空）
% 四：右枝（大于閾值的 歸于此，表葉子時為空）
[n,Dim] = size(Train_Samples);
[t,m] = size(Region);
if Dim ~= t || m ~= 2
disp('參數錯誤，請檢查');
return;
end
%檢查類別屬性是否只有一個屬性，若是則當前為葉節點，否則需要繼續分
if ( length(unique(TrainingTargets)) == 1)
Tree.Label = [];
Tree.Value = TrainingTargets(1);
% 無左右子節點
Tree.Right = [];
Tree.Left = [];
Tree.Num = n;
return;
end
% 如果兩個樣本 為兩類 直接設置為左右葉子
% 差異最大維度做為查詢項目
% 單獨處理此類情況，做為一種優化方法應對 后面提到的缺陷
if length(TrainingTargets) == 2
[m,p] = max(abs(Train_Samples(1,:) -Train_Samples(2,:)));
Tree.Label = p;
Tree.Value = ((Train_Samples(1,p) +Train_Samples(2,p))/2);
Tree.Num = n;
BranchRight.Right = [];
BranchRight.Left = [];
BranchRight.Label = [];
BranchRight.Num =1;
BranchLeft.Right = [];
BranchLeft.Left = [];
BranchLeft.Label = [];
BranchLeft.Num =1;
if Train_Samples(1,p) > Tree.Value
BranchRight.Value = TrainingTargets(1);
BranchLeft.Value = TrainingTargets(2);
else
BranchRight.Value = TrainingTargets(2);
BranchLeft.Value = TrainingTargets(1);
end
Tree.Right = BranchRight;
Tree.Left = BranchLeft;
return;
end
%確定節點的標簽（當前節點判定所用的維度），熵不純度下降落差最大的維度當選
%依次計算各個維度當選之后所造成的不純度之和
%每個維度中可選值中 最大值代表本維度
Dvp=zeros(Dim,2); %記錄每個維度中最大的不純度及相應的閾值
for k=1:Dim
EI=-20*ones(Region(k,2)-Region(k,1)+1,1);
Iei=0;
for m = Region(k,1):Region(k,2)
Iei =Iei +1;
%計算臨時分類結果 去右邊的記為 1
CpI = Train_Samples(:,k) > m;
SumCpI = sum(CpI);
if SumCpI == n || SumCpI == 0 %分到一邊去了，不妥，直接考察下一個
continue;
end
CpI = [not(CpI),CpI];
EIt = zeros(2,1);
%統計預計 新分到左右兩枝的類別及相應的比率，然后得出熵不純度
for j = 1:2
Cpt = TrainingTargets(CpI(:, j));
if ( length(unique(Cpt)) == 1) %應對 hist() 在處理同一元素時所存在的異常問題
Pw = 0;
else
Pw = hist(Cpt,unique(Cpt));
Pw=Pw/length(Cpt); % 被分到該類的比率
Pw=Pw.*log2(Pw);
end
EIt(j) = sum(Pw);
end
Pr = length(Cpt)/n;
EI(Iei) = EIt(1) *(1-Pr) + EIt(2) *Pr;
end
[maxEI, p] = max(EI);
NmaxEI = sum(EI == maxEI);
if NmaxEI > 1 %如果最大值有多個，取中間那一個, 稍微改進了默認地只取第一個最大值的缺陷
t = find(EI == maxEI);
p = round(NmaxEI /2);
p = t(p);
end
Dvp(k,1) = maxEI;
Dvp(k,2) = Region(k,1) +p -1;
end
%更新節點標簽和閾值
[maxDv, p] = max(Dvp(:,1));
NmaxDv = sum(Dvp(:,1) == maxDv);
if NmaxDv > 1 %如果最大值有多個，采用取值范圍較小的那一個維度屬性, 稍微改進了默認地只取第一個最大值的缺陷
t = find(Dvp(:,1) == maxDv);
[D,p] = min(Region(t,2) -Region(t,1));
p = t(p);
end
Tree.Label = p;
Tree.Value = Dvp(p,2);
%將訓練樣本分成兩類，對左右子節點分別形成二叉樹，需要進行遞歸調用
CprI = Train_Samples(:,p) > Dvp(p,2);
CplI = not(CprI);
Tree.Num = n;
Tree.Right = CART_MakeBinarySortTree(Train_Samples(CprI,:), TrainingTargets(CprI), Region);
Tree.Left = CART_MakeBinarySortTree(Train_Samples(CplI,:), TrainingTargets(CplI), Region);
~~~
~~~
% 針對 由函數 CART_MakeBinaryTree()生成的二叉樹 Tree，給出 Test 類屬 W
function W = CART_UseBinarySortTree(tree, testSamples)
% 當前節點不存在左右子結點時，判定為葉節點并返回其類別屬性
if isempty(tree.Right) && isempty(tree.Left)
W = tree.Value;
return;
end
% 非葉節點的判決過程
if testSamples(tree.Label) > tree.Value
W = CART_UseBinarySortTree(tree.Right,testSamples);
else
W = CART_UseBinarySortTree(tree.Left,testSamples);
end
~~~
~~~
function W = CART_PruningBinarySortTree(tree, Samples)
% 針對 由函數 CART_MakeBinaryTree()生成的二叉樹 Tree，按樣本 Samples 遍歷Tree
%如果 發現有與葉子共父節點的長枝條，并且其數量不多于葉子中的樣本數，則將其父節點設為葉子，類別屬性取多數
%由于程序編寫上一時間沒能用Matlab語言實現對二叉樹的修改，所以沒有真實地修剪樹，但是起到的修剪之后的效果,
%遇到葉子時，就可以返回其類別屬性
TempLift=tree.Left;
TempRight=tree.Right;
LeftEmpty =isempty(TempLift.Right) && isempty(TempLift.Left);
RightEmpty=isempty(TempRight.Right) && isempty(TempRight.Left);
if LeftEmpty && RightEmpty %遇到掛有 兩葉子節點，執行剪枝，擇多歸類
if TempLift.Num > TempRight.Num
W=TempLift.Value;
else
W=TempRight.Value;
end
return;
elseif LeftEmpty || RightEmpty %遇到掛有 一個葉子 和 一個子父節點，比較，擇多歸類
if LeftEmpty && (TempLift.Num > TempRight.Num /3)
W=TempLift.Value;
return;
elseif RightEmpty && (TempRight.Num > TempLift.Num /3)
W=TempRight.Value;
return;
end
end
if Samples(tree.Label) > tree.Value
if RightEmpty
W = tree.Right.Value;
return;
else
W = CART_PruningBinarySortTree(tree.Right,Samples);
end
else
if LeftEmpty
W = tree.Left.Value;
return;
else
W = CART_PruningBinarySortTree(tree.Left,Samples);
end
end
~~~
參考書籍：Richard O. Duda, Peter E. Hart, David G. Stork 著《模式分類》
