C45算法的实现.docx

C45算法的实现.docx

《C45算法的实现.docx》由会员分享，可在线阅读，更多相关《C45算法的实现.docx（10页珍藏版）》请在冰点文库上搜索。

C45算法的实现

C4.5算法的实现

一.C4.5算法介绍

C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法.

C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：

1）用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；

2）在树构造过程中进行剪枝；

3）能够完成对连续属性的离散化处理；

4）能够对不完整数据进行处理。

C4.5算法有如下优点：

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

其缺点是：

在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

二.算法实现

//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++;}}