c45dt.cpp

这是一个改进的C4.5决策数算法C++类

	    if ( ! Values ) return;

	    IndentToBuffer(Sh, Tab);

	    if ( Values == 1 )
	    {
			sprintf(buffer,"%s = %s:", AttName[Att], AttValName[Att][Last]);
			strcat(sShowTree,buffer);
			break;
	    }

	    sprintf(buffer,"%s in {", AttName[Att]);
		strcat(sShowTree,buffer);
	    FirstValue = DTTrue;
	    Skip = TextWidth = strlen(AttName[Att]) + 5;

	    ForEach(Pv, 1, MaxAttVal[Att])
	    {
			if ( In(Pv, T->Subset[v]) )
			{
				if ( ! FirstValue &&
				 TextWidth + strlen(AttValName[Att][Pv]) + 11 > Width )
				{
		  			IndentToBuffer(Sh, Tab);
					ForEach(i, 1, Skip) 
					{
						sprintf(buffer,"%c",' ');
						strcat(sShowTree,buffer);
					}

					TextWidth = Skip;
					FirstValue = DTTrue;
				}

				sprintf(buffer,"%s%c", AttValName[Att][Pv], Pv == Last ? '}' : ',');
				strcat(sShowTree,buffer);
				TextWidth += strlen(AttValName[Att][Pv]) + 1;
				FirstValue = DTFalse;
			}
	    }
	    sprintf(buffer,"%c",':');
		strcat(sShowTree,buffer);
		break;
    }

	//有待进一步分析
    ShowToBuffer(T->Branch[v], Sh+1);//显示分支的下一层，递归调用
	//Show(T, Sh+1);//显示分支的下一层，递归调用
}


/*************************************************************************/
/*									 */
/*	Display the tree T with offset Sh				 */
/*									 */
/*************************************************************************/

void C45DT::Show(Tree T,short Sh)
{
    DiscrValue v, MaxV;

    if ( T->NodeType )//非叶节点
    {
	/*  See whether separate subtree needed  */

		if ( T != Nil && Sh && Sh * TabSize + MaxLine(T) > Width )//分支超过显示宽度
		{
			if ( Subtree < 99 )
			{
				Subdef[++Subtree] = T;
				printf("[S%d]", Subtree);//用子树代替
			}
			else
			{
				printf("[S??]");//子树太多
			}
		}
		else//未超过宽度
		{
			MaxV = T->Forks;

			/*  Print simple cases first */

			ForEach(v, 1, MaxV)
			{
				if ( ! T->Branch[v]->NodeType )//如果下层分支为叶节点
				{
					ShowBranch(Sh, T, v);
				}
			}

			/*  Print subtrees  */

			ForEach(v, 1, MaxV)
			{
				if ( T->Branch[v]->NodeType )//非叶节点
				{
					ShowBranch(Sh, T, v);
				}
			}
		}
    }
    else//叶节点
    {
		printf(" %s (%.1f", ClassName[T->Leaf], T->Items);
		if ( T->Errors > 0 ) printf("/%.1f", T->Errors);
		printf(")");
    }
}

/*************************************************************************/
/*									 */
/*	Print show tree T with offset Sh to file				 */
/*	by wuxing, 2003,4,21								 */
/*									 */
/*************************************************************************/

void    C45DT::ShowToFile(Tree T,short Sh)
{
    DiscrValue v, MaxV;

    if ( T->NodeType )//非叶节点
    {
	/*  See whether separate subtree needed  */

		if ( T != Nil && Sh && Sh * TabSize + MaxLine(T) > Width )//分支超过显示宽度
		{
			if ( Subtree < 99 )
			{
				Subdef[++Subtree] = T;
				fprintf(TRf,"[S%d]", Subtree);//用子树代替
			}
			else
			{
				fprintf(TRf,"%s","[S??]");//子树太多
			}
		}
		else//未超过宽度
		{
			MaxV = T->Forks;

			/*  Print simple cases first */

			ForEach(v, 1, MaxV)
			{
				if ( ! T->Branch[v]->NodeType )//如果下层分支为叶节点
				{
					ShowBranchToFile(Sh, T, v);
				}
			}

			/*  Print subtrees  */

			ForEach(v, 1, MaxV)
			{
				if ( T->Branch[v]->NodeType )//非叶节点
				{
					ShowBranchToFile(Sh, T, v);
				}
			}
		}
    }
    else//叶节点
    {
		fprintf(TRf," %s (%.1f", ClassName[T->Leaf], T->Items);
		if ( T->Errors > 0 ) fprintf(TRf,"/%.1f", T->Errors);
		fprintf(TRf,"%s",")");
    }
}

void C45DT::ShowToBuffer(Tree T,short Sh)
{
    DiscrValue v, MaxV;
	char buffer[100];

    if ( T->NodeType )//非叶节点
    {
	/*  See whether separate subtree needed  */

		if ( T != Nil && Sh && Sh * TabSize + MaxLine(T) > Width )//分支超过显示宽度
		{
			if ( Subtree < 99 )
			{
				Subdef[++Subtree] = T;
				sprintf(buffer,"[S%d]", Subtree);//用子树代替
				strcat(sShowTree,buffer);
			}
			else
			{
				sprintf(buffer,"%s","[S??]");//子树太多
				strcat(sShowTree,buffer);
			}
		}
		else//未超过宽度
		{
			MaxV = T->Forks;

			/*  Print simple cases first */

			ForEach(v, 1, MaxV)
			{
				if ( ! T->Branch[v]->NodeType )//如果下层分支为叶节点
				{
					ShowBranchToBuffer(Sh, T, v);
				}
			}

			/*  Print subtrees  */

			ForEach(v, 1, MaxV)
			{
				if ( T->Branch[v]->NodeType )//非叶节点
				{
					ShowBranchToBuffer(Sh, T, v);
				}
			}
		}
    }
    else//叶节点
    {
		sprintf(buffer," %s (%.1f", ClassName[T->Leaf], T->Items);
		strcat(sShowTree,buffer);
		if ( T->Errors > 0 ) 
		{
			sprintf(buffer,"/%.1f", T->Errors);
			strcat(sShowTree,buffer);
		}
		sprintf(buffer,"%s",")");
		strcat(sShowTree,buffer);
    }
}

/*************************************************************************/
/*									 */
/*	Display entire decision tree T					 */
/*									 */
/*************************************************************************/

void C45DT::PrintTree(Tree T)
{
    short s;

    Subtree=0;
    printf("Decision Tree:\n");
    Show(T, 0);//显示整个树，按照深度优先
    printf("\n");

    ForEach(s, 1, Subtree)
    {
		printf("\n\nSubtree [S%d]\n", s);
		Show(Subdef[s], 0);//分别显示子树
		printf("\n");
    }
    printf("\n");
}


/*************************************************************************/
/*									 */
/*	Print show decision tree T  to file				 */
/*	by wuxing, 2003,4,21								 */
/*									 */
/*************************************************************************/

void C45DT::PrintTreeToFile(Tree T)
{
    short s;

    Subtree=0;
    fprintf(TRf,"%s","Decision Tree:\n");
    ShowToFile(T, 0);//显示整个树，按照深度优先
    fprintf(TRf,"%s","\n");

    ForEach(s, 1, Subtree)
    {
		fprintf(TRf,"\n\nSubtree [S%d]\n", s);
		ShowToFile(Subdef[s], 0);//分别显示子树
		fprintf(TRf,"%s","\n");
    }
    fprintf(TRf,"%s","\n");
}

void C45DT::PrintTreeToBuffer(Tree T)
{
    short s;
	char buffer[100];

    Subtree=0;
    sprintf(buffer,"%s","决策树:\n");
	strcat(sShowTree,buffer);
    ShowToBuffer(T, 0);//显示整个树，按照深度优先
    sprintf(buffer,"%s","\n");
	strcat(sShowTree,buffer);

    ForEach(s, 1, Subtree)
    {
		sprintf(buffer,"\n\n子树 [S%d]\n", s);
		strcat(sShowTree,buffer);
		ShowToBuffer(Subdef[s], 0);//分别显示子树
		sprintf(buffer,"%s","\n");
		strcat(sShowTree,buffer);
    }
    sprintf(buffer,"%s","\n");
	strcat(sShowTree,buffer);
}
/*************************************************************************/
/*									 */
/*	Find the maximum single line size for non-leaf subtree St.	 */
/*	The line format is						 */
/*			<attribute> <> X.xx:[ <class (<Items>)], or	 */
/*			<attribute> = <DVal>:[ <class> (<Items>)]	 */
/*									 */
/*************************************************************************/

short C45DT::MaxLine(Tree St)
{
    Attribute a;
    DiscrValue v, MaxV, Next;
    short Ll, MaxLl=0;

    a = St->Tested;

    MaxV = St->Forks;
    ForEach(v, 1, MaxV)
    {
		Ll = ( St->NodeType == 2 ? 4 : strlen(AttValName[a][v]) ) + 1;

		/*  Find the appropriate branch  */

        Next = v;

		if ( ! St->Branch[Next]->NodeType )//分支下为叶节点则
		{
			Ll += strlen(ClassName[St->Branch[Next]->Leaf]) + 6;
		}
		MaxLl = Max(MaxLl, Ll);
    }

    return strlen(AttName[a]) + 4 + MaxLl;
}

/*************************************************************************/
/*								   	 */
/*	Indent Sh columns					  	 */
/*								  	 */
/*************************************************************************/

void C45DT::Indent(short Sh,char *Mark)
{
    printf("\n");
    while ( Sh-- ) printf("%s", Mark);
}

/*************************************************************************/
/*								   	 */
/*	Indent Sh columns in file					  	 */
/*								  	 */
/*************************************************************************/

void C45DT::IndentToFile(short Sh,char *Mark)
{
    fprintf(TRf,"%s","\n");
    while ( Sh-- ) fprintf(TRf,"%s", Mark);
}

void C45DT::IndentToBuffer(short Sh,char *Mark)
{
    char buffer[100];

	sprintf(buffer,"%s","\n");
	strcat(sShowTree,buffer);
    while ( Sh-- ) 
	{
		sprintf(buffer,"%s", Mark);
		strcat(sShowTree,buffer);
	}
}

/*************************************************************************/
/*									 */
/*	Save entire decision tree T in file with extension Extension	 */
/*	顺序存入								 */
/*************************************************************************/

void C45DT::SaveTree(Tree T,C45_String Extension)
{
    static char *LastExt="";
	
	if (!TRf) LastExt="";//added by wuxing,2004/10/13

    if ( strcmp(LastExt, Extension) )
    {
		LastExt = Extension;

		if ( TRf ) fclose(TRf);//关闭已打开的文件指针

		strcpy(Fn, FileName);
		strcat(Fn, Extension);
		if ( ! ( TRf = fopen(Fn, "w") ) )
			Quinlan_Error(0, Fn, " for writing");

	}		
    putc('\n', TRf);
    OutTree(T);
	fclose(TRf);

//    SaveDiscreteNames();
}


/*************************************************************************/
/*									 */
/*	Save show decision tree T in file with extension Extension	 */
/*  by wuxing ,2003,4,21*/
/*	存树形结构								 */
/*************************************************************************/

void C45DT::SaveTreeToFile(Tree T,C45_String Extension)
{
    static char *LastExt="";

	if (!TRf) LastExt="";//added by wuxing,2004/10/13

    if ( strcmp(LastExt, Extension) )
    {
		LastExt = Extension;

		if ( TRf ) fclose(TRf);//关闭已打开的文件指针

		strcpy(Fn, FileName);
		strcat(Fn, Extension);
		if ( ! ( TRf = fopen(Fn, "w") ) )
		{
			Quinlan_Error(0, Fn, " for writing");
			return;
		}
    }
	
    putc('\n', TRf);
	PrintHeaderToFile("decision tree generator");
    PrintTreeToFile(T);
	if ( TRf ) fclose(TRf);//关闭已打开的文件指针
  
}

void C45DT::SaveTreeToBuffer(Tree T)
{	
	PrintHeaderToBuffer("决策树自学习器");
    PrintTreeToBuffer(T);
}

/*************************************************************************/
/*									 */
/*	Save tree T as txt					 */
/*	modified by wuxing 2003/9/2								 */
/*************************************************************************/

void C45DT::OutTree(Tree T)
{
    DiscrValue v;
    int Bytes,i;
	
    fprintf(TRf,"%d,",T->NodeType);
	fprintf(TRf,"%d,",T->Leaf);
    fprintf(TRf,"%f,",T->Items);
	fprintf(TRf,"%f,",T->Errors); 
    for(i=0;i<MaxClass+1;i++)
		fprintf(TRf,"%f,",T->ClassDist[i]); 

    if ( T->NodeType )
    {
		fprintf(TRf,"%d,",T->Tested); 
		fprintf(TRf,"%d,",T->Forks); 
	
		switch ( T->NodeType )
		{
			case BrDiscr:
				break;

			case ThreshContin:
				fprintf(TRf,"%f,",T->Cut);
				fprintf(TRf,"%f,",T->Lower);
				fprintf(TRf,"%f,",T->Upper);
				break;

			case BrSubset:
				Bytes = (MaxAttVal[T->Tested]>>3) + 1;
				ForEach(v, 1, T->Forks)
				{
					fprintf(TRf,"%s,",T->Subset[v]);
				}
				break;
		}

		ForEach(v, 1, T->Forks)
		{
			OutTree(T->Branch[v]);
		}
	}
}

/*************************************************************************/
/*									 */
/*	Save tree T into Buffer					 */
/*	modified by wuxing 2003/9/19								 */
/*************************************************************************/

void C45DT::OutTreeToBuffer(Tree T)
{
    DiscrValue v;
    int Bytes,i;
	
	fTreeSwap[iTreeArray]=(float)T->NodeType;iTreeArray++;
	fTreeSwap[iTreeArray]=(float)T->Leaf;iTreeArray++;
	fTreeSwap[iTreeArray]=T->Items;iTreeArray++;
	fTreeSwap[iTreeArray]=T->Errors;iTreeArray++;
    for(i=0;i<MaxClass+1;i++)
	{
		fTreeSwap[iTreeArray]=T->ClassDist[i];
		iTreeArray++;
	}

    if ( T->NodeType )
    {
		fTreeSwap[iTreeArray]=(float)T->Tested;iTreeArray++;
		fTreeSwap[iTreeArray]=(float)T->Forks;iTreeArray++;