决策树算法C4.5

《数据仓库与数据挖掘》

决策树算法C4.5

本组成员：

07103218王维光 07103224 郑辰 07103229刘倩 07103230宋琛

数据仓库与数据挖掘

一．背景

最早的决策时算法是由Hunt等人于1966年提出的CLS。当前最有影响的决策树算法是Quinlan于1986年提出的ID3和1993年提出的C4.5。ID3只能处理离散型描述属性，它选择信息增益最大的属性划分训练样本，其目的是进行分枝时系统的熵最小，从而提高算法的运算速度和精确度。ID3算法的主要缺陷是，用信息增益作为选择分枝属性的标准时，偏向于取值较多的属性，而在某些情况下，这类属性可能不会提供太多有价值的信息。C4.5是ID3算法的改进算法，不仅可以处理离散型描述属性，还能处理连续性描述属性。C4.5采用了信息增益比作为选择分枝属性的标准，弥补了ID3算法的不足。

决策树算法的优点如下：（1）分类精度高；（2）成的模式简单；（3）对噪声数据有很好的健壮性。因而是目前应用最为广泛的归纳推理算法之一，在数据挖掘中受到研究者的广泛关注。

二．C4.5改进的具体方面

1.ID3算法存在的缺点

（1）ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息。

（2）ID3算法只能对描述属性为离散型属性的数据集构造决策树。

2． C4.5算法做出的改进

(1)用信息增益率来选择属性

克服了用信息增益来选择属性时偏向选择值多的属性的不足。信息增益率定义为：

其中Gain(S,A)与ID3算法中的信息增益相同，而分裂信息SplitInfo(S,A)代表了按照属性A分裂样本集S的广度和均匀性。

数据仓库与数据挖掘

其中，S1到Sc是c个不同值的属性A分割S而形成的c个样本子集。 如按照属性A把S集（含30个用例）分成了10个用例和20个用例两个集合 则SplitInfo(S,A)=-1/3*log(1/3)-2/3*log(2/3) (2)可以处理连续数值型属性

C4.5既可以处理离散型描述属性，也可以处理连续性描述属性。在选择某节点上的分枝属性时，对于离散型描述属性，C4.5的处理方法与ID3相同，按照该属性本身的取值个数进行计算；对于某个连续性描述属性Ac，假设在某个结点上的数据集的样本数量为total，C4.5将作以下处理。  将该结点上的所有数据样本按照连续型描述属性的具体数值，由小到大

进行排序，得到属性值的取值序列{A1c，A2c，……Atotalc}。

 在取值序列中生成total-1个分割点。第i（0值设置为Vi=（Aic+A（i+1）c）/2,它可以将该节点上的数据集划分为两个子集。

 从total-1个分割点中选择最佳分割点。对于每一个分割点划分数据集

的方式，C4.5计算它的信息增益比，并且从中选择信息增益比最大的分割点来划分数据集。 (3)采用了一种后剪枝方法

避免树的高度无节制的增长，避免过度拟合数据， 该方法使用训练样本集本身来估计剪枝前后的误差，从而决定是否真正剪枝。方法中使用的公式如下：

其中N是实例的数量，f=E/N为观察到的误差率（其中E为N个实例中分类错误的个数），q为真实的误差率，c为置信度（C4.5算法的一个输入参数，默认值为0.25），z为对应于置信度c的标准差，其值可根据c的设定值通过查正态分布表得到。通过该公式即可计算出真实误差率q的一个置信度上限，用此上限为该节点误差率e做一个悲观的估计：

数据仓库与数据挖掘

通过判断剪枝前后e的大小，从而决定是否需要剪枝。 (4)对于缺失值的处理

在某些情况下，可供使用的数据可能缺少某些属性的值。假如〈x，c(x)〉是样本集S中的一个训练实例，但是其属性A的值A(x)未知。处理缺少属性值的一种策略是赋给它结点n所对应的训练实例中该属性的最常见值；另外一种更复杂的策略是为A的每个可能值赋予一个概率。例如，给定一个布尔属性A，如果结点n包含6个已知A=1和4个A=0的实例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，实例x的60%被分配到A=1的分支，40%被分配到另一个分支。这些片断样例（fractional examples）的目的是计算信息增益，另外，如果有第二个缺少值的属性必须被测试，这些样例可以在后继的树分支中被进一步细分。C4.5就是使用这种方法处理缺少的属性值。

3. C4.5算法的优缺点

优点：产生的分类规则易于理解，准确率较高。

缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

三．C4.5算法源代码（C++）

// C4.5_test.cpp : Defines the entry point for the console application. //

#include \"stdafx.h\" #include #include #include \"malloc.h\" #include

const int MAX = 10;

数据仓库与数据挖掘

int** iInput; int i = 0;//列数 int j = 0;//行数

void build_tree(FILE *fp, int* iSamples, int* iAttribute,int ilevel);//输出规则

int choose_attribute(int* iSamples, int* iAttribute);//通过计算信息增益率选出test_attribute

double info(double dTrue,double dFalse);//计算期望信息

double entropy(double dTrue, double dFalse, double dAll);//求熵 double splitinfo(int* list,double dAll);

int check_samples(int *iSamples);//检查samples是否都在同一个类里 int check_ordinary(int *iSamples);//检查最普通的类

int check_attribute_null(int *iAttribute);//检查attribute是否为空

void get_attributes(int *iSamples,int *iAttributeValue,int iAttribute);

int _tmain(int argc, _TCHAR* argv[]) {

FILE *fp; FILE *fp1;

char iGet; int a = 0;

int b = 0;//a,b是循环变量 int* iSamples; int* iAttribute;

fp = fopen(\"c:\\\\input.txt\ if (NULL == fp)

{

printf(\"error\\n\"); return 0; }

iGet = getc(fp);

while (('\\n' != iGet)&&(EOF != iGet)) {

if (',' == iGet) {

i++; }

数据仓库与数据挖掘

iGet = getc(fp); } i++;

iAttribute = (int *)malloc(sizeof(int)*i); for (int k = 0; kiAttribute[k] = (int)malloc(sizeof(int)); iAttribute[k] = 1; }

while (EOF != iGet)

{

if ('\\n' == iGet) {

j++; }

iGet = getc(fp); } j++;

iInput = (int **)malloc(sizeof(int*)*j); iSamples = (int *)malloc(sizeof(int)*j); for (a = 0;a < j;a++) {

iInput[a] = (int *)malloc(sizeof(int)*i); iSamples[a] = (int)malloc(sizeof(int)); iSamples[a] = a; }

a = 0;

fclose(fp);

fp=fopen(\"c:\\\\input.txt\ iGet = getc(fp); while(EOF != iGet) {

if ((',' != iGet)&&('\\n' != iGet)) {

iInput[a][b] = iGet - 48; b++; }

if (b == i) {

a++;

数据仓库与数据挖掘

b = 0; }

iGet = getc(fp); }

fp1 = fopen(\"d:\\\\output.txt\

build_tree(fp1,iSamples,iAttribute,0); fclose(fp); return 0; }

void build_tree(FILE * fp, int* iSamples, int* iAttribute,int level)// {

int iTest_Attribute = 0; int iAttributeValue[MAX]; int k = 0; int l = 0; int m = 0;

int *iSamples1;

for (k = 0; k{

iAttributeValue[k] = -1; }

if (0 == check_samples(iSamples)) {

fprintf(fp,\"result: %d\\n\ return; }

if (1 == check_attribute_null(iAttribute))

{

fprintf(fp,\"result: %d\\n\ return; }

iTest_Attribute = choose_attribute(iSamples,iAttribute); iAttribute[iTest_Attribute] = -1;

get_attributes(iSamples,iAttributeValue,iTest_Attribute);

数据仓库与数据挖掘

k = 0;

while ((-1 != iAttributeValue[k])&&(k < MAX)) {

l = 0; m = 0;

while ((-1 != iSamples[l])&&(l < j)) {

if (iInput[iSamples[l]][iTest_Attribute] == iAttributeValue[k]) {

m++; } l++; }

iSamples1 = (int *)malloc(sizeof(int)*(m+1)); l = 0; m = 0;

while ((-1 != iSamples[l])&&(l < j)) {

if (iInput[iSamples[l]][iTest_Attribute] == iAttributeValue[k]) {

iSamples1[m] = iSamples[l]; m++; } l++; }

iSamples1[m] = -1;

if (-1 == iSamples1[0]) {

fprintf(fp,\"result: %d\\n\ return; }

fprintf(fp,\"level%d: %d

= %d\\n\ build_tree(fp,iSamples1,iAttribute,level+1); k++; } }

int choose_attribute(int* iSamples, int* iAttribute) {

int iTestAttribute = -1; int k = 0;

数据仓库与数据挖掘

int l = 0; int m = 0; int n = 0;

int iTrue = 0; int iFalse = 0; int iTrue1 = 0; int iFalse1 = 0; int iDepart[MAX]; int iRecord[MAX];

double dEntropy = 0.0; double dGainratio = 0.0; double test = 0.0;

for (k = 0;kiDepart[k] = -1; iRecord[k] = 0; }

k = 0;

while ((l!=2)&&(k<(i - 1))) {

if (iAttribute[k] == -1) {

l++; } k++; }

if (l == 1)

{

for (k = 0;k<(k-1);k++) {

if (iAttribute[k] == -1) {

return iAttribute[k]; } } }

for (k = 0;k < (i-1);k++)

{

l = 0;

iTrue = 0; iFalse = 0;

数据仓库与数据挖掘

if (iAttribute[k] != -1) {

while ((-1 != iSamples[l])&&(l < j)) {

if (0 == iInput[iSamples[l]][i-1]) {

iFalse++; }

if (1 == iInput[iSamples[l]][i-1]) {

iTrue++; }

l++; }

for (n = 0;nm = 0;

while((iDepart[m]!=-1)&&(m!=MAX)) {

if (iInput[iSamples[n]][iAttribute[k]] == iDepart[m]) {

break; } m++; }

if (-1 == iDepart[m]) {

iDepart[m] = iInput[iSamples[n]][iAttribute[k]]; } }

while ((iDepart[m] != -1)&&(m!=MAX)) {

for (n = 0;nif (iInput[iSamples[n]][iAttribute[k]] == iDepart[m]) {

if (1 == iInput[iSamples[n]][i-1]) {

iTrue1++; }

if (0 == iInput[iSamples[n]][i-1]) {

iFalse1++; }

数据仓库与数据挖掘

iRecord[m]++; } }

dEntropy +=

entropy((double)iTrue1,(double)iFalse1,(double)l); iTrue1 = 0; iFalse1 = 0; m++; }

double dSplitinfo = splitinfo(iRecord,(double)l); if (-1 == iTestAttribute) {

iTestAttribute = k; dGainratio =

(info((double)iTrue,(double)iFalse)-dEntropy)/dSplitinfo; } else {

test =

(info((double)iTrue,(double)iFalse)-dEntropy)/dSplitinfo; if (dGainratio < test) {

iTestAttribute = k; dGainratio = test; } } } }

return iTestAttribute; }

double info(double dTrue,double dFalse)

{

double dInfo = 0.0; dInfo =

((dTrue/(dTrue+dFalse))*(log(dTrue/(dTrue+dFalse))/log(2.0))+(dFalse/(dTrue+dFalse))*(log(dFalse/(dTrue+dFalse))/log(2.0)))*(-1); return dInfo; }

double entropy(double dTrue, double dFalse, double dAll) {

double dEntropy = 0.0;

数据仓库与数据挖掘

dEntropy = (dTrue + dFalse)*info(dTrue,dFalse)/dAll; return dEntropy; }

double splitinfo(int* list,double dAll)

{

int k = 0;

double dSplitinfo = 0.0; while (0!=list[k]) {

dSplitinfo -=

((double)list[k]/(double)dAll)*(log((double)list[k]/(double)dAll));

k++; }

return dSplitinfo; }

int check_samples(int *iSamples) {

int k = 0; int b = 0;

while ((-1 != iSamples[k])&&(k < j-1)) {

if (iInput[k][i-1] != iInput[k+1][i-1]) {

b = 1; break; } k++; }

return b; }

int check_ordinary(int *iSamples) {

int k = 0;

int iTrue = 0; int iFalse = 0;

while ((-1 != iSamples[k])&&(k < i)) {

if (0 == iInput[iSamples[k]][i-1]) {

数据仓库与数据挖掘

iFalse++; } else {

iTrue++; } k++; }

if (iTrue >= iFalse) {

return 1; } else {

return 0; } }

int check_attribute_null(int *iAttribute) {

int k = 0;

while (k < (i-1)) {

if (-1 != iAttribute[k]) {

return 0; } k++; }

return 1; }

void get_attributes(int *iSamples,int *iAttributeValue,int iAttribute) {

int k = 0; int l = 0;

while ((-1 != iSamples[k])&&(k < j))

{

l = 0;

while (-1 != iAttributeValue[l]) {

if (iInput[iSamples[k]][iAttribute] == iAttributeValue[l]) {

数据仓库与数据挖掘

break; } l++; }

if (-1 == iAttributeValue[l]) {

iAttributeValue[l] = iInput[iSamples[k]][iAttribute]; } k++; } }