目錄
一、初識決策樹
二、理論基礎
三、ID3算法
四、問題實作
五、運作結果分析
六、References
一、初識決策樹
決策樹（ Decision Tree ）又稱為判定樹，是對資料進行分類的一種樹結構，并通過分類達到預測的目的。決策樹分為分類樹和回歸樹兩種，分類樹是對離散變量做決策樹，回歸樹是對連續變量做決策樹。構造決策樹是采用自上而下的遞歸構造方法。
決策樹構造的結果是一棵二叉或多叉樹，它的輸入是一組帶有類别标記的訓練資料。決策樹中的每個内部結點代表對某個屬性的一次測試，每條邊代表一個測試結果，葉結點代表某個類或者類的分布，最上面的結點是根結點。二叉樹的非葉結點一般表示為一個邏輯判斷，如形為 （a = b） 的邏輯判斷，其中 a 是屬性，b 是該屬性的某個屬性值；樹的邊是邏輯判斷的分支結果；樹的葉結點都是類别标記。多叉樹的内部結點是屬性，邊是該屬性的所有取值，有幾個屬性值，就有幾條邊。
決策樹的分類過程也就是決策樹分類模型（簡稱決策樹）的生成過程，如下圖所示。從圖中可知決策樹分類的建立過程與用決策樹分類模型進行預測的過程實際上是一種歸納-演繹過程。其中，由已分類資料得到決策樹分類模型的過程稱歸納過程，用決策樹分類模型對未分類資料進行分類的過程稱為演繹過程。需要強調的是：由訓練集得到分類模型必須經過測試集測試達到一定要求才能用于預測。
二、理論基礎
1.資訊量：衡量資訊多少的實體量。
若機率很大，人們事先已有所估計，則該消息資訊量很小；若機率很小，人們感到很突然，則該消息所含資訊量很大。
資訊量的定義：若一個消息x出現的機率為p，則這一消息所含的資訊量為
n=2時，機關為bit；n=e時，機關為nat；n=10時，機關為hart。一般計算中n常取2。
例：抛一枚均勻硬币，出現正面和反面的資訊量是多少？
解：出現正反面機率均為0.5，則
2.資訊熵
信源含有的資訊量是信源發出的所有可能消息的平均不确定性，香農把信源所含有的資訊量稱為資訊熵，是指每個屬性所含資訊量的統計平均值，即所有可能發生事件所帶來的的資訊量的期望。資訊論中一個離散型随機變量X的熵定義如下：
資訊熵的定義也可表示為：
n為訓練集X類别數，如子集結果類别為正面、反面，則n為2。
例：抛一枚均勻硬币的資訊熵是多少？
解：
（注：ID3算法中會為每一個類别計算資訊熵，具有最小資訊熵的類别在本次疊代中用來劃分資料集X。）
3.條件自資訊量
在事件
出現的條件下，随機事件
發生的條件機率為
，則它的條件自資訊量定義為條件機率對數的負值：
4.條件熵
條件熵的定義是：在Y給定條件下，X的條件機率分布的熵對Y的數學期望。
在給定
條件下，
的條件自資訊量為
，X集合的條件熵為：
在給定Y（即各個
）條件下，X集合的條件熵為：
注意：條件熵中Y也是一個變量，意思是在一個變量Y的條件下（變量Y的每個值都會取），另一個變量X熵對Y的期望。條件熵不是指在給定某個數（某個變量為某個值）的情況下，另一個變量的熵是多少，變量的不确定性是多少，而是整體X變量的不确定度或期望！
5.資訊增益
資訊增益描述了一個特征帶來的資訊量的多少，往往用于特征選擇。一個特征往往會使一個随機變量Y的資訊量減少，減少的部分就是資訊增益。
資訊增益 = 資訊熵 - 條件熵
是表示集合X被屬性Y分類之前和之後熵的差異。即：集合X原來的熵和已知屬性Y之後的熵之差。表示屬性Y被固定前後集合X的不确定性降低了多少。
（注：ID3算法中會為每一個類别計算資訊熵，具有最大資訊增益的類别在本次疊代中用來劃分資料集X。）
三、ID3算法
ID3 (Iterative Dichotomiser 3) 是由Quinlan提出的分類預測算法，用來給一個資料集建立決策樹。該算法以資訊論為基礎，以資訊熵和資訊增益為衡量标準，進而實作對資料的歸納分類。ID3算法計算每個屬性的資訊增益，并選取具有最高增益的屬性作為給定集合的測試屬性。對被選取的測試屬性建立一個節點，并以該節點的屬性标記，對該屬性的每個值建立一個分支以此劃分樣本。
算法流程[References 2]：
四、問題實作
問題描述：給定上述天氣資料，将資料劃分為訓練集和測試集（最後四行），設計算法使用測試集測試構造的決策樹，然後使用測試集資料進行預測，看是否适合打網球一欄是否能夠正确對應。
程式設計思想（ID3）：每次從資料集中根據最大資訊增益選取一個最好特征，将資料進行劃分，每次劃分都會消耗一個特征，使得特征越來越少，當所有資料集都是同一類，或者消耗完所有特征時，劃分結束。其中資訊熵和資訊增益使用前面理論基礎部分的公式。
說明：為了區分最後兩列的取值，使觀察更友善，我将最後一列中“是”替換為“适合”，“否”替換為“不适合”。
C++實作：代碼修改自References[4]
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
#include <math.h>
using namespace std;
#define N 10
#define feature 4
vector< vector<string> > X;
string x[N][feature+1] =
{
{"晴", "熱", "高", "否", "不适合"},
{"晴", "熱", "高", "是", "不适合"},
{"陰", "熱", "高", "否", "适合"},
{"雨", "溫", "高", "否", "适合"},
{"雨", "涼爽", "中", "否", "适合"},
{"雨", "涼爽", "中", "是", "不适合"},
{"陰", "涼爽", "中", "是", "适合"},
{"晴", "溫", "高", "否", "不适合"},
{"晴", "涼爽", "中", "否", "适合"},
{"雨", "溫", "中", "否", "适合"},
// {"晴", "溫", "中", "是", "适合"},
// {"陰", "溫", "高", "是", "适合"},
// {"陰", "熱", "中", "否", "适合"},
// {"雨", "溫", "高", "是", "不适合"}
};
//四個特征的名稱，比如天氣取值有三個：晴，陰，雨
string attribute[] = {"天氣", "溫度", "濕度", "是否有風"};
vector<string> attributes;
//建立資料集
void createDataset() {
//建立資料集
X = vector< vector<string> >(N, vector<string>(feature+1));
int i, j;
for(i=0; i<N; i++) {
for(int j=0; j<feature+1; j++) {
X[i][j] = x[i][j];
}
}
//建立特征
for(i=0; i<feature; i++)
attributes.push_back(attribute[i]);
}
//計算給定資料集的香農熵
double calcShanno(const vector< vector<string> > &data) {
int n = data.size();
map<string, int> classCounts;
int i;
int label = data[0].size() - 1;
//初始為0
for(i=0; i<n; i++)
classCounts[ data[i][label] ] = 0;
//每當出現一次，+1
for(i=0; i<data.size(); i++)
classCounts[ data[i][label] ] += 1;
//計算香農熵
double shanno = 0;
map<string, int>::iterator it;
for(it = classCounts.begin(); it != classCounts.end(); it++) {
double prob = (double)(it->second) / (double)n;
shanno -= prob * ( log(prob) / log(2) );
}
return shanno;
}
//按照給定特征劃分資料集，劃分後的資料集中不包含給定特征，即新的資料集的次元少了一個
//axis ：特征下标
//value：特征值
vector< vector<string> > splitDataSet(const vector< vector<string> > data, int axis, string value) {
vector< vector<string> > result;
for(int i=0; i<data.size(); i++) {
if(data[i][axis] == value) {
//将“目前特征”這個次元去掉
vector<string> removed(data[i].begin(), data[i].begin()+axis);
removed.insert(removed.end(), data[i].begin()+axis+1, data[i].end());
result.push_back(removed);
}
}
return result;
}
//建立特征清單
vector<string> createFeatureList(const vector< vector<string> > &data, int axis) {
int n = data.size();
vector<string>featureList; //特征的所有取值
set<string> s;
for(int j=0; j<n; j++) //尋找該特征的所有可能取值
s.insert(data[j][axis]);
set<string>::iterator it;
for(it = s.begin(); it != s.end(); it++) {
featureList.push_back(*it);
}
return featureList;
}
//選擇最好的資料集劃分方式
int chooseBestFeatureToSplit(const vector< vector<string> > &data) {
int n = data[0].size() - 1;
double bestEntropy = calcShanno(data); //初始香農熵
double bestInfoGain = 0; //最大的資訊增益
int bestFeature = 0; //最好的特征
//所有特征
for(int i=0; i<n; i++) {
double newEntropy = 0;
//該特征的所有可能取值
vector<string> featureList = createFeatureList(data, i);
for(int j=0; j<featureList.size(); j++) {
vector< vector<string> > subData = splitDataSet(data, i, featureList[j]);
double prob = (double)subData.size() / (double)data.size();
newEntropy += prob * calcShanno(subData);
}
//資訊增益，即熵的減少，或資料無序度的減少
double infoGain = bestEntropy - newEntropy;
if(infoGain > bestInfoGain) {
bestInfoGain = infoGain;
bestFeature = i;
}
}
return bestFeature;
}
//傳回出現次數最多的分類名稱
//如果資料集已處理了所有屬性，但類标簽依然不是唯一的，采用多數表決的方法定義葉子節點的分類
string majorityCnt(vector<string> &classList) {
int n = classList.size();
map<string, int> classCount;
int i;
for(i=0; i<n; i++)
classCount[classList[i]] = 0;
for(i=0; i<n; i++)
classCount[classList[i]] += 1;
int maxCnt = 0;
map<string, int>::iterator it;
string result = "";
for(it = classCount.begin(); it != classCount.end(); it++) {
if(it->second > maxCnt) {
maxCnt = it->second;
result = it->first;
}
}
return result;
}
struct Node {
string attribute;
string val;
bool isLeaf;
vector<Node*> childs;
Node() {
val = "";
attribute = "";
isLeaf = false;
}
};
Node *root = NULL;
//遞歸建構決策樹
Node* createTree(Node *root, const vector< vector<string> > &data, vector<string> &attribute) {
if(root == NULL)
root = new Node();
vector<string> classList;
set<string> classList1;
int i, j;
int label = data[0].size() - 1;
int n = data.size();
for(i=0; i<n; i++) {
classList.push_back(data[i][label]);
classList1.insert(data[i][label]);
}
//如果所有執行個體都屬于同一類，停止劃分
if(classList1.size() == 1) {
if(classList[0] == "适合")
root->attribute = "适合";
else
root->attribute = "不适合";
root->isLeaf = true;
return root;
}
//周遊完所有特征，傳回出現次數最多的類别
if(data[0].size() == 1) {
root->attribute = majorityCnt(classList);
return root;
}
int bestFeatureIndex = chooseBestFeatureToSplit(data);
//得到屬性的所有可能值
vector<string> featureList = createFeatureList(data, bestFeatureIndex);
string bestFeature = attribute[bestFeatureIndex];
//記錄要劃分的屬性
root->attribute = bestFeature;
//對于目前屬性的每個可能值，建立新的分支
for(i=0; i<featureList.size(); i++) {
vector<string> subAttribute;
for(j=0; j<attribute.size(); j++) {
if(bestFeature != attribute[j])
subAttribute.push_back(attribute[j]);
}
Node *newNode = new Node();
newNode->val = featureList[i];//記錄屬性的取值
createTree(newNode, splitDataSet(data, bestFeatureIndex, featureList[i]), subAttribute);
root->childs.push_back(newNode);
}
return root;
}
//列印
void print(Node *root, int depth) {
int i;
for(i=0; i<depth; i++)
cout << "\t";
if(root->val != "") {
cout << root->val << endl;
for(i=0; i<depth+1; i++)
cout << "\t";
}
cout << root->attribute << endl;
vector<Node*>::iterator it;
for(it = root->childs.begin(); it != root->childs.end(); it++) {
print(*it, depth+1);
}
}
//預測x
string classify(Node *root, vector<string> &attribute, string *test) {
string firstFeature = root->attribute;
int firstFeatureIndex;
int i;
//找到根節點是第幾個特征
for(i=0; i<feature; i++) {
if(firstFeature == attribute[i]) {
firstFeatureIndex = i;
break;
}
}
if(root->isLeaf) //如果是葉子節點，直接輸出結果
return root->attribute;
for(i=0; i<root->childs.size(); i++) {
if(test[firstFeatureIndex] == root->childs[i]->val) {
return classify(root->childs[i], attribute, test);
}
}
}
//釋放節點
void freeNode(Node *root) {
if(root == NULL)
return;
vector<Node*>::iterator it;
for(it=root->childs.begin(); it != root->childs.end(); it++)
freeNode(*it);
delete root;
}
int main() {
createDataset();
root = createTree(root, X, attributes);
print(root, 0);
string test[] = {"晴", "溫", "中", "是"};
int i;
cout << endl << "屬性：";
for(i=0; i<feature; i++)
cout << attributes[i] << "\t";
cout << endl << "例子：";
for(i=0; i<feature; i++)
cout << test[i] << "\t";
cout << endl << "預測：";
cout << classify(root, attributes, test) << endl;
freeNode(root);
return 0;
}
五、運作結果分析
1.根據實作代碼列印出根據訓練集歸納反演出的決策樹如下圖：
整理出較為規整的基于ID3算法的決策樹如下圖：
2. 輸入測試集資料可得到以下預測結果
分析上述結果可知，測試集中第一條資料的預測結果與原表不符，說明決策樹的預測結果存在誤差，原因是訓練集太小，需要更多資料加入訓練。
經過測試集資料的添加後完善了決策樹，得到新的決策樹如下圖。最終的決策樹更加完善，有效降低了預測的錯誤率。
六、References
[1] https://blog.csdn.net/yijichangkong/article/details/47260847
[2] https://wenku.baidu.com/view/7aa9fbd776eeaeaad1f3305d.html
[3] http://www.dzsc.com/data/2011-8-29/95580.html
[4]https://blog.csdn.net/u012319493/article/details/53112577