bigtree.cpp

该代码是数据挖掘里面的决策树算法 利用ID3理论

	///信息熵计算完毕,开始生成决策树

	maxValue=0.0;
	int INDEX=0;//保存为参考属性是第几个属性
	for(aNum=0;aNum<sizeof(pNAME)/4;aNum++)
	{
		if(maxValue<Entropy[aNum])
		{
			INDEX=aNum;
			maxValue=Entropy[aNum];
		}
	};
	
	//申请动态行链表数组,保存新的分类
	//cout<<"正在创建动态链表数组,请稍候.............."<<endl;
	Point *pnHead=new Point[classNum[INDEX]];
	Point *pnRear=new Point[classNum[INDEX]];
	char *VALUE=new char[classNum[INDEX]];
	for(aNum=0;aNum<classNum[INDEX];aNum++)
	{
		pnHead[aNum].Next=NULL;
		pnRear[aNum]=pnHead[aNum];
		VALUE[aNum]=NULL;
	}

	ClassLink *clTemp=new ClassLink;
	clTemp=&clHead[INDEX];
	aNum=0;
	while(clTemp->Next!=NULL)
	{
		clTemp=clTemp->Next;
		VALUE[aNum++]=clTemp->aValue;
	}

	//cout<<classNum[INDEX]<<"=="<<INDEX<<endl;
	//根据分类开始创建新的链表
	pRear=pHead;
	while(pRear->Next!=NULL)
	{
		Attribute *aRear=new Attribute;
		Attribute *aTemp=new Attribute;
		pRear=pRear->Next;
		aRear=&pRear->Value;
		iTemp=0;
		while(aRear->Next!=NULL)
		{//查找属性所在列位置
			aRear=aRear->Next;
			aTemp=aRear;
			if(iTemp==INDEX)
			{
				aTemp->usedTag=true;//用于添加时保存
				break;
			}
			iTemp++;
		};
		iTemp=0;
		for(aNum=0;aNum<classNum[INDEX];aNum++)
		{//查找类链表
			if(VALUE[aNum]==aRear->Value)
			{
				iTemp=aNum;
				//break;
			};
		}
		Point *pnTemp=new Point;
		pnTemp=&pnRear[iTemp];
		while(pnTemp->Next!=NULL)//将指针移到最后
		{
			pnTemp=pnTemp->Next;
		}
		//OutLine(pRear);
		//cout<<"Value: "<<VALUE[iTemp]<<"    加入类位:"<<iTemp<<endl;
		Point *pnt=new Point;
		pnt->Value=pRear->Value;
		pnt->Next=NULL;
		pnTemp->Next=pnt;
		pnTemp=pnt;
		//Out(&pnRear[iTemp]);
		//OutLine(pnTemp);
	};
	
	/*cout<<endl<<"---------------------------------------------------"<<endl;
	for(aNum=0;aNum<classNum[INDEX];aNum++)
	{
		Point *ptRear=&pnRear[aNum];
		iTemp=0;
		cout<<"类位:"<<aNum<<endl;
		Out(ptRear);
		cout<<"---------------------------------------------------"<<endl;
	};
	*/


	/*for(aNum=0;aNum<sizeof(pNAME)/4;aNum++)
	{
		ClassLink *clTemp=new ClassLink;
		clTemp=&clHead[INDEX];
		while(clTemp->Next!=NULL)
		{
			clTemp=clTemp->Next;
			cout<<"属性:"<<clTemp->aValue<<" 值: "<<clTemp->Total<<"\t"<<endl;
			ClassLink *clbTemp=new ClassLink;
			clbTemp=clTemp;
			while(clbTemp->Brother!=NULL)
			{
				clbTemp=clbTemp->Brother;
				cout<<"  A="<<clbTemp->aValue<<"\tV="<<clbTemp->Total<<"\t";
			};
			cout<<endl;
		};
		cout<<"--------------------------------------------------------"<<endl;
	};*/

	
	Node *gnHead=new Node,*gnRear=new Node;
	gnHead->Brother=NULL;
	gnHead->Next=NULL;
	gnRear=gnHead;
	clTemp=&clHead[INDEX];
	//查找只有一个分类的点
	while(clTemp->Next!=NULL)
	{
		clTemp=clTemp->Next;
		ClassLink *clbTemp=new ClassLink;
		clbTemp=clTemp;
		int num=0;
		while(clbTemp->Brother!=NULL)
		{
			clbTemp=clbTemp->Brother;
			num++;
		};
		if(num==1)//只有一个分类
		{
			//cout<<"位置:"<<aNum<<"  "<<clbTemp->aValue<<"="<<clbTemp->Total<<"只有一个分类!"<<endl;
			Node *nt=new Node;
			nt->Brother=NULL;
			nt->Next=NULL;
			nt->Name=aName;
			nt->Value=clbTemp->aValue;
			gnRear->Next=nt;
			gnRear=nt;
			//cout<<gnHead[aNum].Name<<"="<<gnHead[aNum].Value<<endl;
		};
	};

	gnRear=gnHead;
	while(gnRear->Next!=NULL)
	{
		gnRear=gnRear->Next;
		//cout<<gnRear->Name<<"="<<gnRear->Value<<endl;
	}

	//cout<<"----------------------------"<<endl<<endl;

	Node *nTemp=new Node,*nTRear=new Node;
	nTemp->Brother=NULL;
	nTemp->Next=NULL;
	nTemp->Name=pNAME[INDEX];//保存列名
	nTRear=nTemp;
	clTemp=&clHead[INDEX];
	aNum=0;
	gnRear=gnHead;//只有一个属性的类链表
	//cout<<"类总数:"<<classNum[INDEX]<<endl;
	while(clTemp->Next!=NULL)//读取每一属性分类
	{
		clTemp=clTemp->Next;
		Node *nbTemp=new Node,*nt=NULL;
		Point *ptRear=&pnRear[aNum];
		nbTemp->Brother=NULL;
		nbTemp->Next=NULL;
		nbTemp->Value=clTemp->aValue;
		nTRear->Brother=nbTemp;
		nTRear=nbTemp;
		nt=FormTree(nTRear,ptRear,aName);
		if(nt==NULL)
		{
			gnRear=gnRear->Next;//根据类位置的变化同时移位
			//cout<<gnRear->Name<<"="<<gnRear->Value<<endl;
			Node *gt=new Node;
			gt->Name=gnRear->Name;
			gt->Value=gnRear->Value;
			gt->Brother=NULL;
			gt->Next=NULL;
			nTRear->Next=gt;
			//cout<<"加入!"<<endl;
		}
		aNum++;
	};

	nTRear=nTemp;
	Node *nbTemp=new Node;
	nbTemp=nTRear;
	aNum=0;
	while(nbTemp->Brother!=NULL)
	{
		nbTemp=nbTemp->Brother;
		//cout<<nbTemp->Value<<endl;
		aNum++;
	};

	nHead->Next=nTemp;
	return nHead;
};

void GetNode(Node *nHead)
{
	Node *nRear=nHead;
	int i=0,b=0;
	nRear=nHead;
	while(nRear->Next!=NULL)
	{
		nRear=nRear->Next;
		Node *nTemp=new Node;
		nTemp=nRear;
		cout<<" Name:   "<<nTemp->Name<<"\tAttri:  "<<nTemp->Value<<endl;
		i=0;
		while(nTemp->Brother!=NULL)
		{
			nTemp=nTemp->Brother;
			cout<<" Attri_"<<i++<<": "<<nTemp->Value<<"\t";;
			GetNode(nTemp);
		}
		nodeLay++;
		//cout<<endl;
	};
	return;
};

void FindData(Node *nHead,Point *pHead,char *aName)//根据树判断一点的分类
{//走的路已经正确
	Node *nRear=nHead;
	nRear=nHead;
	while(nRear->Next!=NULL)
	{
		nRear=nRear->Next;
		Node *nTemp=new Node;
		Attribute *aTemp=new Attribute;
		nTemp=nRear;
		//cout<<"Name:   "<<nTemp->Name<<"\tAttri:  "<<nTemp->Value<<endl;
		if(nTemp->Name==aName)
		{
			//cout<<"nodeName:"<<nTemp->Name<<"\tgoldName:  "<<aName<<endl;
			//cout<<"Attr:    "<<nTemp->Value<<endl;
			aTemp=&pHead->Value;
			while(aTemp->Next!=NULL)
			{
				aTemp=aTemp->Next;
				if(aTemp->usedTag)
					continue;
				if(aTemp->Name==aName)
				{
					aTemp->Value=nTemp->Value;
					/*if(aTemp->Value==nTemp->Value)
					{
						Right++;
						//cout<<"\tLine:"<<Total<<"\tNode Attribute:"<<nTemp->Value<<"√"<<endl;
					}
					else
					{
						Wrong++;
						//cout<<"\tLine:"<<Total<<"\tNode Attribute::"<<nTemp->Value<<"×"<<"\tReality:"<<aTemp->Value<<endl;
						//cout<<"发现一个失误..........."<<endl<<endl;
						//system("pause");
					}*/
					aTemp->usedTag=true;
					break;
				};
			}
		};
		aTemp=&pHead->Value;
		while(aTemp->Next!=NULL)
		{
			aTemp=aTemp->Next;
			if(aTemp->usedTag)
				continue;
			if(aTemp->Name==nTemp->Name)
			{
				while(nTemp->Brother!=NULL)
				{
					nTemp=nTemp->Brother;
					if(nTemp->Value==aTemp->Value)
					{
						FindData(nTemp,pHead,aName);
						aTemp->usedTag=true;
					};
				}
			}
		};
	};
	return;
};

int main(int argc, char* argv[])
{
	Point *pHead=new Point,*pRear=new Point;
	Point *pHead2=new Point,*pRear2=new Point;
	Node *nHead=new Node,*nRear=new Node;
	int i=0;
	nHead->Brother=NULL;
	nHead->Next=NULL;
	nRear=nHead;
	pHead->Next=NULL;
	pRear=pHead;
	pHead2->Next=NULL;
	pRear2=pHead2;

	
	cout<<" 读取训练数据,请稍候.............."<<endl;
	ifstream in(fileName);
	char line[80],*word,*seq=",\n\t";
	while(!in.eof())
	{
		in.getline(line,80,'\n');
		word=strtok(line,seq);
		Attribute *aHead=new Attribute,*aRear=new Attribute;
		aHead->Next=NULL;
		aRear=aHead;
		i=0;
		while(word)
		{
			Attribute *aTemp=new Attribute;
			aTemp->Value=*word;
			aTemp->Name=pNAME[i++];
			aTemp->usedTag=false;
			aTemp->Next=NULL;
			aRear->Next=aTemp;
			aRear=aTemp;
			word=strtok(NULL,seq);
		};
		aRear=aHead;
		Point *pTemp=new Point;
		pTemp->Value=*aRear;
		pTemp->Next=NULL;
		pRear->Next=pTemp;
		pRear=pTemp;
	};
	in.close();
	cout<<" 读取完毕,开始计算,请稍候.............."<<endl;	
	pRear=pHead;
	FormTree(nRear,pRear,pNAME[doIndex-1]);
	cout<<" 决策树已经生成,正确读取决策树结果,请稍候.............."<<endl;
	nRear=nHead;
	GetNode(nRear);
	nRear=nHead;

	//---------------------------------------------------------------------
	cout<<" 读取目标数据,请稍候.............."<<endl;
	ifstream in2(fileName2);
	//char line[80],*word,*seq=",\n\t";
	while(!in2.eof())
	{
		in2.getline(line,80,'\n');
		word=strtok(line,seq);
		Attribute *aHead=new Attribute,*aRear=new Attribute;
		aHead->Next=NULL;
		aRear=aHead;
		i=0;
		while(word)
		{
			Attribute *aTemp=new Attribute;
			aTemp->Value=*word;
			aTemp->Name=pNAME[i++];
			aTemp->usedTag=false;
			aTemp->Next=NULL;
			aRear->Next=aTemp;
			aRear=aTemp;
			word=strtok(NULL,seq);
		};
		aRear=aHead;
		Point *pTemp=new Point;
		pTemp->Value=*aRear;
		pTemp->Next=NULL;
		pRear2->Next=pTemp;
		pRear2=pTemp;
	};
	in2.close();
	cout<<" 读取完毕,按任意键开始计算"<<endl;	
	//---------------------------------------------------------------------
	system("pause");
	Point *pTemp=new Point;
	pRear2=pHead2;
	//cout<<"训练数据:"<<endl;
	//Out(pRear);
	//cout<<"测试数据:"<<endl;
	//Out(pRear2);
	Point *pnt=new Point;
	pnt=pRear2;
	cout<<" 开始判断,请稍候.............."<<endl;
	while(pRear2->Next!=NULL)
	{
		pRear2=pRear2->Next;
		Total++;
		pTemp=pRear2;
		FindData(nRear,pTemp,pNAME[doIndex-1]);
		//OutLine(pTemp);
		//cout<<"-----------------------------------------------------"<<endl;
	}
	//double rRate=0.0,wRate=0.0;
	//rRate=(double)Right/Total;
	//wRate=(double)Wrong/Total;
	//cout<<" 总数:"<<Total<<"\t正确量:"<<Right<<"\t失误量:"<<Wrong<<endl;
	//cout<<" 正确率:"<<rRate*100<<"%\t失误率:"<<wRate*100<<"%"<<endl;
	cout<<"运行效果:"<<endl;
	Out(pnt);
	
	return 0;
}