簡單易學的機器學習算法—決策樹之ID3算法

一、決策樹分類算法概述
    決策樹算法是從數據的屬性（或者特征）出發，以屬性作為基礎，劃分不同的類。例如對于如下數據集

（數據集）
其中，第一列和第二列為屬性（特征），最后一列為類別標簽，1表示是，0表示否。決策樹算法的思想是基于屬性對數據分類，對于以上的數據我們可以得到以下的決策樹模型

（決策樹模型）
先是根據第一個屬性將一部份數據區分開，再根據第二個屬性將剩余的區分開。
    實現決策樹的算法有很多種，有ID3、C4.5和CART等算法。下面我們介紹ID3算法。
二、ID3算法的概述
    ID3算法是由Quinlan首先提出的，該算法是以信息論為基礎，以信息熵和信息增益為衡量標準，從而實現對數據的歸納分類。
    首先，ID3算法需要解決的問題是如何選擇特征作為劃分數據集的標準。在ID3算法中，選擇信息增益最大的屬性作為當前的特征對數據集分類。信息增益的概念將在下面介紹，通過不斷的選擇特征對數據集不斷劃分；
    其次，ID3算法需要解決的問題是如何判斷劃分的結束。分為兩種情況，第一種為劃分出來的類屬于同一個類，如上圖中的最左端的“非魚類”，即為數據集中的第5行和第6行數據；最右邊的“魚類”，即為數據集中的第2行和第3行數據。第二種為已經沒有屬性可供再分了。此時就結束了。
    通過迭代的方式，我們就可以得到這樣的決策樹模型。

（ID3算法基本流程）
三、劃分數據的依據
    ID3算法是以信息熵和信息增益作為衡量標準的分類算法。
1、信息熵(Entropy)
   熵的概念主要是指信息的混亂程度，變量的不確定性越大，熵的值也就越大，熵的公式可以表示為：

其中為類別在樣本s中出現的概率。
2、信息增益(Information gain)
   信息增益指的是劃分前后熵的變化，可以用下面的公式表示：

其中，a表示樣本的屬性，是屬性所有的取值集合。v是a的其中一個屬性值，sv是s中a的值為v的樣例集合。

四、實驗仿真
1、數據預處理
    我們以下面的數據為例，來實現ID3算法：

我們首先需要對數據處理，例如age屬性，我們用0表示youth，1表示middle_aged，2表示senior等等。

（將表格數據化）
2、實驗結果

（原始的數據）

（劃分1）

（劃分2）

（劃分3）

（最終的決策樹）
MATLAB代碼
主程序
[plain] view plain copy 在CODE上查看代碼片派生到我的代碼片
%% Decision Tree  
% ID3  
 
%導入數據  
%data = [1,1,1;1,1,1;1,0,0;0,1,0;0,1,0];    
 
data = [0,2,0,0,0;  
    0,2,0,1,0;  
    1,2,0,0,1;  
    2,1,0,0,1;  
    2,0,1,0,1;  
    2,0,1,1,0;  
    1,0,1,1,1;  
    0,1,0,0,0;  
    0,0,1,0,1;  
    2,1,1,0,1;  
    0,1,1,1,1;  
    1,1,0,1,1;  
    1,2,1,0,1;  
    2,1,0,1,0];  
 
% 生成決策樹  
createTree(data)；  

生成決策樹
[plain] view plain copy 在CODE上查看代碼片派生到我的代碼片
function [ output_args ] = createTree( data )  
    [m,n] = size(data);  
    disp('original data:');  
    disp(data);  
    classList = data(:,n);  
    classOne = 1;%記錄第一個類的個數  
    for i = 2:m  
        if classList(i,:) == classList(1,:)  
            classOne = classOne+1;  
        end  
    end  
      
    % 類別全相同  
    if classOne == m  
        disp('final data: ');  
        disp(data);  
        return;  
    end  
      
    % 特征全部用完  
    if n == 1  
        disp('final data: ');  
        disp(data);  
        return;  
    end  
      
    bestFeat = chooseBestFeature(data);  
    disp(['bestFeat: ', num2str(bestFeat)]);  
    featValues = unique(data(:,bestFeat));  
    numOfFeatValue = length(featValues);  
      
    for i = 1:numOfFeatValue  
        createTree(splitData(data, bestFeat, featValues(i,:)));  
        disp('-------------------------');  
    end  
end  

選擇信息增益最大的特征
[plain] view plain copy 在CODE上查看代碼片派生到我的代碼片
%% 選擇信息增益最大的特征  
function [ bestFeature ] = chooseBestFeature( data )  
    [m,n] = size(data);% 得到數據集的大小  
      
    % 統計特征的個數  
    numOfFeatures = n-1;%最后一列是類別  
    % 原始的熵  
    baseEntropy = calEntropy(data);  
      
    bestInfoGain = 0;%初始化信息增益  
    bestFeature = 0;% 初始化最佳的特征位  
      
    % 挑選最佳的特征位  
    for j = 1:numOfFeatures  
        featureTemp = unique(data(:,j));  
        numF = length(featureTemp);%屬性的個數  
        newEntropy = 0;%劃分之后的熵  
        for i = 1:numF  
            subSet = splitData(data, j, featureTemp(i,:));  
            [m_1, n_1] = size(subSet);  
            prob = m_1./m;  
            newEntropy = newEntropy + prob * calEntropy(subSet);  
        end  
          
        %計算增益  
        infoGain = baseEntropy - newEntropy;  
          
        if infoGain > bestInfoGain  
            bestInfoGain = infoGain;  
            bestFeature = j;  
        end  
    end  
end  

計算熵
[plain] view plain copy 在CODE上查看代碼片派生到我的代碼片
function [ entropy ] = calEntropy( data )  
    [m,n] = size(data);  
      
    % 得到類別的項  
    label = data(:,n);  
      
    % 處理完的label  
    label_deal = unique(label);  
      
    numLabel = length(label_deal);  
    prob = zeros(numLabel,2);  
      
    % 統計標簽  
    for i = 1:numLabel  
        prob(i,1) = label_deal(i,:);  
        for j = 1:m  
            if label(j,:) == label_deal(i,:)  
                prob(i,2) = prob(i,2)+1;  
            end  
        end  
    end  
      
    % 計算熵  
    prob(:,2) = prob(:,2)./m;  
    entropy = 0;  
    for i = 1:numLabel  
        entropy = entropy - prob(i,2) * log2(prob(i,2));  
    end  
end  

劃分數據
[plain] view plain copy 在CODE上查看代碼片派生到我的代碼片
function [ subSet ] = splitData( data, axis, value )  
    [m,n] = size(data);%得到待劃分數據的大小  
      
    subSet = data;  
    subSet(:,axis) = [];  
    k = 0;  
    for i = 1:m  
        if data(i,axis) ~= value  
            subSet(i-k,:) = [];  
            k = k+1;  
        end  
    end     
end