决策树算法C45.docx
- 文档编号:2138715
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:18
- 大小:70.51KB
决策树算法C45.docx
《决策树算法C45.docx》由会员分享,可在线阅读,更多相关《决策树算法C45.docx(18页珍藏版)》请在冰点文库上搜索。
决策树算法C45
《数据仓库与数据挖掘》
决策树算法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
●从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%被分配到另一个分支。
这些片断样例(fractionalexamples)的目的是计算信息增益,另外,如果有第二个缺少值的属性必须被测试,这些样例可以在后继的树分支中被进一步细分。
C4.5就是使用这种方法处理缺少的属性值。
3. C4.5算法的优缺点
优点:
产生的分类规则易于理解,准确率较高。
缺点:
在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。
此外,C4.5只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。
三.C4.5算法源代码(C++)
//C4.5_test.cpp:
Definestheentrypointfortheconsoleapplication.
//
#include"stdafx.h"
#include
#include
#include"malloc.h"
#include
constintMAX=10;
int**iInput;
inti=0;//列数
intj=0;//行数
voidbuild_tree(FILE*fp,int*iSamples,int*iAttribute,intilevel);//输出规则
intchoose_attribute(int*iSamples,int*iAttribute);//通过计算信息增益率选出test_attribute
doubleinfo(doubledTrue,doubledFalse);//计算期望信息
doubleentropy(doubledTrue,doubledFalse,doubledAll);//求熵
doublesplitinfo(int*list,doubledAll);
intcheck_samples(int*iSamples);//检查samples是否都在同一个类里
intcheck_ordinary(int*iSamples);//检查最普通的类
intcheck_attribute_null(int*iAttribute);//检查attribute是否为空
voidget_attributes(int*iSamples,int*iAttributeValue,intiAttribute);
int_tmain(intargc,_TCHAR*argv[])
{
FILE*fp;
FILE*fp1;
chariGet;
inta=0;
intb=0;//a,b是循环变量
int*iSamples;
int*iAttribute;
fp=fopen("c:
\\input.txt","r");
if(NULL==fp)
{
printf("error\n");
return0;
}
iGet=getc(fp);
while(('\n'!
=iGet)&&(EOF!
=iGet))
{
if(','==iGet)
{
i++;
}
iGet=getc(fp);
}
i++;
iAttribute=(int*)malloc(sizeof(int)*i);
for(intk=0;k
{
iAttribute[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 { 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","r"); 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","w"); build_tree(fp1,iSamples,iAttribute,0); fclose(fp); return0; } voidbuild_tree(FILE*fp,int*iSamples,int*iAttribute,intlevel)// { intiTest_Attribute=0; intiAttributeValue[MAX]; intk=0; intl=0; intm=0; int*iSamples1; for(k=0;k { iAttributeValue[k]=-1; } if(0==check_samples(iSamples)) { fprintf(fp,"result: %d\n",iInput[iSamples[0]][i-1]); return; } if(1==check_attribute_null(iAttribute)) { fprintf(fp,"result: %d\n",check_ordinary(iSamples)); return; } iTest_Attribute=choose_attribute(iSamples,iAttribute); iAttribute[iTest_Attribute]=-1; get_attributes(iSamples,iAttributeValue,iTest_Attribute); k=0; while((-1! =iAttributeValue[k])&&(k { l=0; m=0; while((-1! =iSamples[l])&&(l { 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 { 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",check_ordinary(iSamples)); return; } fprintf(fp,"level%d: %d=%d\n",level,iTest_Attribute,iAttributeValue[k]); build_tree(fp,iSamples1,iAttribute,level+1); k++; } } intchoose_attribute(int*iSamples,int*iAttribute) { intiTestAttribute=-1; intk=0; intl=0; intm=0; intn=0; intiTrue=0; intiFalse=0; intiTrue1=0; intiFalse1=0; intiDepart[MAX]; intiRecord[MAX]; doubledEntropy=0.0; doubledGainratio=0.0; doubletest=0.0; for(k=0;k { iDepart[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) { returniAttribute[k]; } } } for(k=0;k<(i-1);k++) { l=0; iTrue=0; iFalse=0; if(iAttribute[k]! =-1) { while((-1! =iSamples[l])&&(l { if(0==iInput[iSamples[l]][i-1]) { iFalse++; } if(1==iInput[iSamples[l]][i-1]) { iTrue++; } l++; } for(n=0;n { m=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;n { if(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++; } doubledSplitinfo=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 { iTestAttribute=k; dGainratio=test; } } } } returniTestAttribute; } doubleinfo(doubledTrue,doubledFalse) { doubledInfo=0.0; dInfo=((dTrue/(dTrue+dFalse))*(log(dTrue/(dTrue+dFalse))/log(2.0))+(dFalse/(dTrue+dFalse))*(log(dFalse/(dTrue+dFalse))/log(2.0)))*(-1); returndInfo; } doubleentropy(doubledTrue,doubledFalse,doubledAll) { doubledEntropy=0.0; dEntropy=(dTrue+dFalse)*info(dTrue,dFalse)/dAll; returndEntropy; } doublesplitinfo(int*list,doubledAll) { intk=0; doubledSplitinfo=0.0; while(0! =list[k]) { dSplitinfo-=((double)list[k]/(double)dAll)*(log((double)list[k]/(double)dAll)); k++; } returndSplitinfo; } intcheck_samples(int*iSamples) { intk=0; intb=0; while((-1! =iSamples[k])&&(k { if(iInput[k][i-1]! =iInput[k+1][i-1]) { b=1; break; } k++; } returnb; } intcheck_ordinary(int*iSamples) { intk=0; intiTrue=0; intiFalse=0; while((-1! =iSamples[k])&&(k { if(0==iInput[iSamples[k]][i-1]) { iFalse++; } else { iTrue++; } k++; } if(iTrue>=iFalse) { return1; } else { return0; } } intcheck_attribute_null(int*iAttribute) { intk=0; while(k<(i-1)) { if(-1! =iAttribute[k]) { return0; } k++; } return1; } voidget_attributes(int*iSamples,int*iAttributeValue,intiAttribute) { intk=0; intl=0; while((-1! =iSamples[k])&&(k { 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++; } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 决策树 算法 C45
![提示](https://static.bingdoc.com/images/bang_tan.gif)