内容发布更新时间 : 2024/12/27 7:16:28星期一 下面是文章的全部内容请认真阅读。
实验一 ID3算法实现
一、实验目的
通过编程实现决策树算法，信息增益的计算、数据子集划分、决策树的构建过程。加深对相关算法的理解过程。 实验类型：验证 计划课间：4学时
二、实验内容
1、分析决策树算法的实现流程；
2、分析信息增益的计算、数据子集划分、决策树的构建过程； 3、根据算法描述编程实现算法，调试运行； 4、对所给数据集进行验算，得到分析结果。
三、实验方法
算法描述：
以代表训练样本的单个结点开始建树；
若样本都在同一个类，则该结点成为树叶，并用该类标记；
否则，算法使用信息增益作为启发信息，选择能够最好地将样本分类的属性； 对测试属性的每个已知值，创建一个分支，并据此划分样本； 算法使用同样的过程，递归形成每个划分上的样本决策树 递归划分步骤，当下列条件之一成立时停止： 给定结点的所有样本属于同一类；
没有剩余属性可以进一步划分样本，在此情况下，采用多数表决进行
四、实验步骤
1、算法实现过程中需要使用的数据结构描述： Struct
{int Attrib_Col; // 当前节点对应属性 int Value; // 对应边值 Tree_Node* Left_Node; // 子树
Tree_Node* Right_Node // 同层其他节点 Boolean IsLeaf; // 是否叶子节点 int ClassNo; // 对应分类标号 }Tree_Node;
2、整体算法流程
主程序：
InputData();
T=Build_ID3(Data,Record_No, Num_Attrib); OutputRule(T); 释放内存; 3、相关子函数： 3.1、 InputData()
{
输入属性集大小Num_Attrib; 输入样本数Num_Record;
分配内存Data[Num_Record][Num_Attrib];
输入样本数据Data[Num_Record][Num_Attrib]； 获取类别数C(从最后一列中得到); }
3.2、Build_ID3(Data,Record_No, Num_Attrib)
{
Int Class_Distribute[C];
If (Record_No==0) { return Null }
N=new tree_node();
计算Data中各类的分布情况存入Class_Distribute Temp_Num_Attrib=0;
For (i=0;i If (Data[0][i]>=0) Temp_Num_Attrib++; If Temp_Num_Attrib==0 { N->ClassNo=最多的类； N->IsLeaf=TRUE; N->Left_Node=NULL;N->Right_Node=NULL; Return N; } If Class_Distribute中仅一类的分布大于0 { N->ClassNo=该类； N->IsLeaf=TRUE; N->Left_Node=NULL;N->Right_Node=NULL; Return N; } InforGain=0;CurrentCol=-1; For i=0;i TempGain=Compute_InforGain(Data,Record_No,I,Num_Attrib); If (InforGain { InforGain=TempGain; CurrentCol=I;} } N->Attrib_Col=CurrentCol; //记录CurrentCol所对应的不同值放入DiferentValue[]； I=0;Value_No=-1; While i For (k=0;k if (DiferentValu[k]=Data[i][CurrentCol]) flag=true; if (flag==false) {Value_No++;DiferentValue[Value_No]=Data[i][CurrentCol] } I++; } SubData=以Data大小申请内存空间； For (i=0;i k=-1; for (j=0;j if (Data[j][CurrentCol]==DiferentValu[i]) {k=k++; For(int i1=0;i1 If (i1<>CurrentCol)SubData[k][i1]=Data[j][i1]; Else SubData[k][i1]=-1; } N->Attrib_Col=CurrentCol; N->Value=DiferentValu[i]; N->Isleaf=false; N->ClassNo=0; N->Left_Node=Build_ID3(SubData,k+1, Num_Attrib); N->Right_Node=new Tree_Node; N=N->Right_Node; } } 3.3、计算信息增益 Compute_InforGain(Data,Record_No, Col_No, Num_Attrib) { Int DifferentValue[MaxDifferentValue]; Int Total_DifferentValue; Int s[ClassNo][MaxDifferentValue]; s=0;// 数组清0;