tree.cpp

自主式决策树学习的程序源码

// Tree.cpp: implementation of the CTree class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "dstl.h"
#include "Tree.h"
#include "Statistic.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////



CTree::CTree()
{

}

CTree::~CTree()
{

}
extern int leaveCount;
extern int nodeCount;
extern CString strRuletable;
extern int AttNumber;
extern CDatabase * pDb;
extern int recCount;
////////////////////////////////////

void CTree::CreatTree(TreeNode *ptn)
{   
	
//最大正确率大于父结点的整体确定性，作为叶结点
	if (ptn->ParNode!=NULL && ptn->LeaveCer>ptn->ParNode->CerRatio)
	{
		ptn->ChiCount=0;
		ptn->ChiNode=NULL;
		//ptn->nodeList=NULL;
		//rules(ptn);
		ptn->AttCount=AttNumber+3;//只是为了标识为第一类叶结点，用于书的删除
		reduceRules(ptn);
		leaveCount++;
		
			
	}
	else  //else1
//不满足条件则继续分裂
    {
		CStatistic mysta;
		CPtrList * AttList=new CPtrList[ptn->AttCount];//CPtrList数组，每条件属性一个
	
		//选择分裂属性
		int index=mysta.SelSplit(ptn->AttArray,ptn->AttCount,AttList,ptn->strWh);
	    ptn->nodeList=&AttList[index];
		//计算整体确定性
		int sum1=0;
		int sum2=0;
		int ChiCount=AttList[index].GetCount();
		ValNode * tempNode;
		for (int i=0;i<ChiCount;i++)
		{
			tempNode=(ValNode*)AttList[index].GetAt(AttList[index].FindIndex(i));
			sum1+=tempNode->ValMaxNum;
			sum2+=tempNode->ValTotalNum;
			
		}
		float wholeCer=(float)sum1/sum2;
		//////
		if(ptn->ParNode!=NULL && wholeCer<=ptn->LeaveCer)
//继续分裂所得整体确定性并不大于该结点作为叶结点的确定程度，所以把该结点作叶结点
			                                
		{
			ptn->ChiCount=0;
			ptn->ChiNode=NULL;
            
			
			//rules(ptn->ParNode);
			reduceRules(ptn);
			leaveCount++;
			
		
		}
		else   //else2
		{
			
			ptn->CerRatio=wholeCer;//整体确定性
			ptn->SplitAtt=ptn->AttArray[index];//分裂属性
			ptn->ChiCount=ChiCount;//孩子个数
			ptn->ChiNode=new TreeNode*[ptn->ChiCount];//分配孩子指针
			for(int j=0;j<ptn->ChiCount;j++)
			{
				ptn->ChiNode[j]=new TreeNode;//分配孩子空间
				ptn->ChiNode[j]->ParNode=ptn;//给孩子找父亲
				ptn->ChiNode[j]->AttCount=ptn->AttCount-1;//孩子结点的当前条件属性个数
				
				tempNode=(ValNode*)AttList[index].GetAt(AttList[index].FindIndex(j));
				ptn->ChiNode[j]->SplitVal=tempNode->ValueName;//父分裂属性的取值
				CString str;
				if (ptn->strWh.IsEmpty())
				{
				     str=ptn->SplitAtt
			                 +" = "+"'"+ptn->ChiNode[j]->SplitVal+"'";//where字句，去定当前的记录集
				}
				else
				{
					str=ptn->strWh+ " and "+ptn->SplitAtt
			                 +" = "+"'"+ptn->ChiNode[j]->SplitVal+"'";//where字句，去定当前的记录集
				}
				ptn->ChiNode[j]->strWh=str;
				ptn->ChiNode[j]->ClassName=tempNode->ValueClass;//如果作为叶结点时的决策分类名
				ptn->ChiNode[j]->LeaveCer=tempNode->CerVote;//如果作为叶结点是的正确率
				ptn->ChiNode[j]->supRatio=(float)tempNode->ValMaxNum/recCount;//支持度
				int iSize=ptn->AttCount;
				char * arrAttTemp=new char[iSize];
				arrSub(ptn->AttArray,ptn->AttCount+1,arrAttTemp,ptn->SplitAtt[0]);
				ptn->ChiNode[j]->AttArray=arrAttTemp;//包括决策属性
				
			
				CreatTree(ptn->ChiNode[j]);
			}//end for
		}//end else2
	}//end else1
}
////////////////////////////////////////////////////////////////////////////
//删除树节点
void CTree::delTreeNode(TreeNode *ptn)
{
	delete [] ptn->AttArray;//删除分配给此节点的字符串指针
	delete ptn;//删除本结点
	
}
/////////////////////////////////////////////////////////////////////////////
//释放PtrList链表
void CTree::FreeList(CPtrList * list)
{

		if (list->IsEmpty())
		return;
	    int k=list->GetCount();
        ValNode * p;
	    for(int j=0;j<k;j++)
		{
		   p=(ValNode*)list->GetHead();
		   list->RemoveHead();
           delete p;
		}
	
}
///////////////////////////////////////////////////////////////////////////////
void CTree::arrSub(char * sArr,int size,char *dArr, char ch)
//参数说明（原数组，原数组长度，目的数组，删除的元素）
{
	int k=0;
	for(int i=0;i<size;i++)
	{
		if(sArr[i]!=ch)
		{
			dArr[k]=sArr[i];
			k++;
		}
	}
}
///////////////////////////////////////////////////////////////////////
//用于测试时输出规则集
void CTree::rules(TreeNode *ptn)
{
	CString str="class = "+ptn->ClassName+";"+"确定性＝";
	CString strRule="";
	strRule.Format(str+"%2f" ,ptn->LeaveCer);   
	TreeNode *p;
	while(ptn->ParNode!=NULL)
	{
		p=ptn->ParNode;
		strRule=p->SplitAtt+"="+ptn->SplitVal+";"+strRule;
		ptn=p;
	}
	AfxMessageBox(strRule);
}

///////////////////////////////////////////////////////////////////////////
//生成规则集
void CTree::reduceRules(TreeNode *ptn)
{
	CString strCmd,strCmd1,strCmd2;
	float fCer=ptn->LeaveCer;//确定性
	float fSup=ptn->supRatio;//支持度
	CString strClassName="ClassName";//决策类列
	CString classname=ptn->ClassName;
	strCmd="insert "+strRuletable;
	TreeNode *p;
	while(ptn->ParNode!=NULL)
	{
		p=ptn->ParNode;
		strCmd1=strCmd1+p->SplitAtt+",";
		strCmd2=strCmd2+"'"+ptn->SplitVal+"'"+",";
		ptn=p;
	}
	strCmd1="("+strCmd1+strClassName+",certainty,"+"support"+")";
	
	CString str=strCmd2;
	strCmd2.Format("values("+str+"'"+classname+"','"+"%2f"+"'"+",%2f"+")",fCer,fSup);
	strCmd=strCmd+" "+strCmd1+" "+strCmd2;
	//AfxMessageBox(strCmd);
	pDb->ExecuteSQL(strCmd);

/*
	CRecordset rst(pDb);//声明规则集数据集
	CString strSQL;
	strSQL="select * from "+strRuletable;
	//if(!rst.IsOpen())
	//{
	rst.Open(CRecordset::dynaset,strSQL);
	//}
	//else

*/
  }
/////////////////////////////////////////////////////////////////////////////
//删除树
void CTree::delTree(TreeNode *ptn)
{
	
	int iCh=ptn->ChiCount;
	for(int i=0;i<iCh;i++)
	{
		delTree(ptn->ChiNode[i]);
		
	}
	//CString str;
	//str=ptn->ClassName+","+ptn->SplitVal;
	//AfxMessageBox(str);
	if(ptn->AttCount<AttNumber)//因为第一类叶结点不含有链，
	{
		FreeList(ptn->nodeList);
	}
	delTreeNode(ptn);
	nodeCount++;
	
	
}