- Visual C++數字圖像模式識別典型案例詳解
- 馮偉興 梁洪 王臣業編著
- 3029字
- 2018-12-31 19:38:57
2.2.3 決策樹
分類是數據挖掘中很重要的任務，決策樹是模式識別中求解分類問題時的一種非常有效的方法。
1.決策樹的基本概念及算法
（1）基本概念
決策樹，又稱多級分類器，在對數據進行決策分類時利用樹的結構記錄數據并進行分類。決策樹方法包含兩個基本步驟：構建樹和將樹應用于數據庫。目前，大多數研究都集中在如何有效地構建樹，而應用過程則很簡單。
一棵決策樹由一系列結點和分支組成，父結點和子結點之間形成分支，父結點代表著決策過程中所考慮的屬性，并根據屬性的不同取值建立決策樹的各個分支；隨后遞歸地構造每個子結點的子樹。一棵決策樹的內部結點是屬性或屬性的集合，葉結點是所要學習劃分的類，內部結點的屬性稱為測試屬性。在通過訓練實例集的訓練產生一棵決策樹后，該決策樹可以根據屬性值對一個未知實例集進行分類。使用決策樹對實例進行分類的時候，由樹根開始向下搜索直至到達某個葉結點，此葉結點代表的類即為該對象所處的類。
決策樹學習采用自頂向下的遞歸方式，在決策樹的內部結點進行屬性值的比較并根據不同的屬性值判斷從該結點向下的分支，在決策樹的葉結點得到結論。所以從根結點到葉結點的一條路徑就對應著一條析取規則，整個決策樹就對應著一組析取表達式規則。決策樹生成算法分為兩個步驟：一是樹的生成，開始時所有數據都在根結點，然后遞歸地進行數據劃分，從而生成樹；二是樹的修剪，就是去掉一些可能是噪音或者異常的數據。決策樹停止分割的條件有兩個：一是一個結點上的數據都屬于同一個類別；二是沒有屬性可以再用于對數據進行分割。
決策樹的示意圖如圖2-10所示（n表示結點，t表示終點）。
圖2-10 決策樹示意圖
（2）ID3算法
決策樹算法的研究是數據挖掘中一個非常活躍的研究領域。基于信息熵的ID3算法，是由Quinlan在1986年提出的，該算法是目前公認最早和最有影響的決策樹方法。
ID3算法的核心思想是，在決策樹各層分支結點上選擇屬性時，用信息增益（information gain）作為屬性的選擇標準，使得在每一非葉子結點進行測試時，能獲得關于被測例子最大的類別信息，使用該屬性將樣本集劃分成子集后，系統的信息熵值最小，期望該非葉子結點到達各后代葉子結點的平均路徑最短，生成的決策樹平均深度較小。該算法的具體過程為：選擇當前樣本集中具有最大信息增益值的屬性作為測試屬性；樣本集的劃分則依據測試屬性的取值進行，測試屬性有多少不同取值就將樣本集劃分為多少子樣本集；決策樹上相應于該樣本集的結點長出新的葉子結點。
用來量化信息的概念稱為熵（entropy）。熵是數據集中的不確定性、突發性或隨機性的程度的度量。熵的值介于0和1之間，當所有的概率相等時達到最大值。它的具體定義如下：
設S是s個樣本的集合，假定類標號屬性有m個不同值，定義m個不同類Ci（i=1,2,…,m）。設Si是Ci中樣本數。對一個給定的樣本分類所需的熵為
式中，Pi =Si/s。
設屬性A有v個不同值（a1,a2,…,av）。可以用屬性A將S劃分為v個子集{S1,S2,…,Sv}，其中Si中樣本在屬性A上具有值ai。如果A選作測試屬性，則這些子集對應于由包含集合s的結點生長出來的分枝。設Sij是子集Sj中類Ci的樣本數，則根據由A劃分成子集的熵或期望信息由下式給出：1 2 1 2 1 , , ,( ) ( , , , ) v j j mj j j mj i S S SEA IS S S= s=∑……（2-124
式中，項
j充當第j個子集的權，并且等于子集（即A值為ai）中的樣本個數除以S中的樣本總數。熵值越小，子集劃分的純度越高。對于給定的子集Sj
式中，
是Sj中的樣本屬于類Cj的概率。
選擇A作為分裂屬性獲得的信息增益為
信息增益是ID3算法增長樹的每一步中選取最佳屬性的變量標準。
2.決策樹的設計
根據決策樹算法，首先由給定數據集產生一棵決策樹，即Generate_decision_tree；當輸入訓練樣本samples時，各屬性均取離散數值，建立候選屬性集合attribute_list；然后輸出決策樹。
具體的步驟如下：
（a）創建結點N；
（b）如果samples都在同一個類C，則返回N作為葉子結點，以類C標記；
（c）如果attribute_list為空，則返回N作為葉子結點，標記為samples中最普通的類；
（d）選擇attribute_list中具有最高信息增益的屬性test_ attribute；
（e）標記結點N為test_attribute；
（f）對每一個test_attribute中的已知值ai，由結點N長出一個條件為test_attribute=ai的分支；
（g）設si是samples中test_attribute=ai的樣本的集合；
（h）如果 si為空，則加上一個葉子結點，標記為samples中最普通的類；否則加上一個由Generate_decision_tree(si,sttribute_list-test_attribute)返回的結點。
該算法是一個貪心算法，采用自上而下、分而治之的遞歸方式來構造一棵決策樹。遞歸操作的停止條件是：一個結點的所有樣本均為同一類別。若無屬性可用于劃分當前樣本集，則利用投票原則將當前結點強制為葉子結點，并標記為當前結點所含樣本集中類別個數最多的類別。沒有樣本滿足test_attribute=ai；則創建一個葉子結點并將其標記為當前結點所含樣本集中類別個數最多的類別。
ID3通過不斷地循環處理，逐步求精決策樹，直至找到一棵完全正確的決策樹，并自頂向下歸納形成了一組類似if…then的規則。
ID3算法具有如下的優缺點：
·優點：算法基礎理論清晰，計算時間是實例個數、特征個數和結點個數之積的線性函數；搜索空間是完全的假設空間，目標函數必在搜索空間中，不存在無解的危險；全盤使用訓練數據，而不是像候選剪除算法那樣一個個地考慮訓練例，這樣做可以利用全部訓練例的統計性質進行決策，從而抵抗噪聲。
·缺點：傾向于選擇取值較多的屬性，但取值較多的屬性并不都是最重要的屬性；搜索無回溯，可能會收斂于局部最優解而丟失全局最優解，因為它是一種自頂向下的貪心算法，逐個地考慮訓練例；只能處理具有離散值的屬性，對連續值屬性無能為力；沒有考慮訓練集中的缺值問題；是一種單變量決策樹算法，表達復雜概念時非常困難。
3.決策樹的C語言實現
決策樹算法的C語言實現代碼如代碼2-7所示。
代碼2-7決策樹算法的代碼
enum UINT { INACTIVE, OFF, ON };
#define LN_2 0.693147180559945309417
#define entropy(x) (x > 0 ? x ＊ log(x) / LN_2 : 0.0)
typedef struct node {
unsigned int idx;
double threshold;
struct node ＊on;
struct node ＊off;
struct node ＊parent;
} NODE;
typedef struct ne_struct {
double ne;
UINT status;
} NEGENTROPY;
typedef struct matrix {
unsigned int width;
unsigned int height;
double ＊＊data;
} MATRIX;
MATRIX ＊build_matrix (unsigned int width, unsigned int height)
{
MATRIX ＊_matrix;
unsigned int i;
_matrix = (MATRIX＊) malloc (sizeof (MATRIX));
if (!_matrix)
err_exit (__FILE__, __LINE__);
_matrix->width = width;
_matrix->height = height;
_matrix->data = (double ＊＊) malloc (height ＊ sizeof (double ＊));
if (_matrix->data == NULL)
err_exit(__FILE__, __LINE__);
for (i=0; i<height; i++)
{
_matrix->data[i] = (double ＊) malloc (width ＊ sizeof(double));
if (_matrix->data[i] == NULL)
err_exit(__FILE__, __LINE__);
}
return _matrix;
}
void err_exit (char ＊ file, unsigned int line)
{
printf("\n Fatal error in file %s, line %u", file, line);
exit(0);
}
void file_size (char ＊file_name, unsigned int ＊width, unsigned int ＊height)
{
FILE ＊f;
unsigned int buf_size = 0xFF, _width = 0;
char ＊buffer, ＊ptr;
＊width = ＊height = 0;
buffer = (char ＊) malloc (buf_size ＊ sizeof (char));
if (buffer == NULL)
err_exit (__FILE__, __LINE__);
f = fopen(file_name, "r");
if (f == NULL)
{
printf("\n File not found : %s\n", file_name);
err_exit (__FILE__, __LINE__);
}
if (fgets(buffer, buf_size, f) != NULL)
{
++＊height;
ptr = strtok (buffer, " ,");
while (ptr != NULL)
{
++＊width;
ptr = strtok (NULL, " ,");
}
}
while (!feof(f))
{
if (fgets(buffer, buf_size, f) != NULL)
{
if (strlen(buffer) > strlen("\n")) /＊ if line is more than a NL char ＊/
{
++＊height;
_width = 0;
ptr = strtok (buffer, " ,");
while (ptr != NULL)
{
++_width;
ptr = strtok (NULL, " ,");
}
if (＊width != _width)
{
printf("\n Number of entries in file %s did not agree", file_name);
err_exit (__FILE__, __LINE__);
}
}
}
}
free (buffer);
}
void free_matrix (MATRIX ＊_matrix)
{
unsigned int i;
for (i=0; i<_matrix->height; i++)
free (_matrix->data[i]);
free (_matrix->data);
free (_matrix);
}
void free_tags (char ＊＊ varname, unsigned int width)
{
unsigned int i;
for (i=0; i<width; i++)
free(varname[i]);
free (varname);
}
void free_tree ( NODE ＊node )
{
if (node == NULL)
return;
else
{
free_tree (node->on);
free_tree (node->off);
free(node);
}
}
NEGENTROPY negentropy (double ＊＊data, unsigned int n_samples, NODE ＊local,
unsigned int target)
{
NEGENTROPY ret_val;
NODE ＊_node, ＊_parent;
UINT on_ctr, off_ctr, p1, p2, i, _match;
double p_on, p_off, negentropy_on, negentropy_off;
on_ctr = off_ctr = p1 = p2 = 0;
for (i=0; i<n_samples; i++)
{
_match = 1;
_node = local;
while (_node->parent != NULL)
{
_parent = _node->parent;
if (_node == _parent->on)
{
if (data[i][_parent->idx] < _parent->threshold)
_match = 0;
}
else
if (_node == _parent->off)
{
if (data[i][_parent->idx] >= _parent->threshold)
_match = 0;
}
_node = _parent;
}
if (_match)
{
if (data[i][local->idx] >= local->threshold)
{
on_ctr++;
if (data[i][target] >= 0.5)
p1++;
}
else
{
off_ctr++;
if (data[i][target] >= 0.5)
p2++;
}
}
}
if (on_ctr > 0)
{
p_on = (REAL) p1 / (REAL) on_ctr;
p_off = 1- p_on;
negentropy_on = -entropy (p_on) - entropy (p_off);
}
else
negentropy_on = 0.0;
if (off_ctr > 0)
{
p_on = (REAL) p2 / (REAL) off_ctr;
p_off = 1- p_on;
negentropy_off = -entropy (p_on) - entropy (p_off);
}
else
negentropy_off = 0.0;
ret_val.ne = (negentropy_on ＊ on_ctr + negentropy_off ＊ off_ctr);
ret_val.ne /= (on_ctr + off_ctr);
if ((p1 == on_ctr) && (p2 == off_ctr))
ret_val.status = ON;
else if ((p1 == 0) && (p2 == 0))
ret_val.status = OFF;
else
ret_val.status = INACTIVE;
return ret_val;
}
NODE＊ ID3 ( MATRIX ＊matrix, NODE＊ parent, unsigned int target, UINT state)
//基于Quinlan 的 ID3 算法，建立一棵決策樹
{
NEGENTROPY negentropy_struct;
NODE ＊node;
unsigned int n_vars = matrix->width, n_samples = matrix->height, i, j, split;
double ＊＊data = matrix->data;
double best_threshold, min_negentropy, _negentropy;
//為結點分配內存
node = (NODE＊) malloc (sizeof(NODE));
if (!node)
err_exit (__FILE__, __LINE__);
//建立決策樹的連接
node->parent = parent;
if (parent != NULL)
{
if (state == ON)
parent->on = node;
else
if (state == OFF)
parent->off = node;
}
min_negentropy = 1.0;
for (i=0; i<n_vars; i++)
{
for (j=0; j<n_samples; j++)
{
if (i != target)
{
node->idx = i;
node->threshold = data[j][i];
negentropy_struct = negentropy (data, n_samples, node, target);
_negentropy = negentropy_struct.ne;
if (_negentropy < min_negentropy)
{
min_negentropy = _negentropy;
split = i;
best_threshold = data[j][i];
}
}
}
}
/保存最高信息增益的屬性
inode->idx = split;
inode->threshold = best_threshold;
iif (negentropy_struct.status != INACTIVE)
i{
inode->on = node->off = NULL;
inode->idx = negentropy_struct.status;
i}
ielse
i{
inode->on = ID3 (matrix, node, target, ON);
inode->off = ID3 (matrix, node, target, OFF);
}
return node;
}