- Visual C++数字图像模式识别典型案例详解
- 冯伟兴 梁洪 王臣业编著
- 3029字
- 2025-03-16 03:50:25
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;
}