#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?
using?namespace?std;
int?Length;//訓(xùn)練集文本特征數(shù)?
int?textcnt=0;//訓(xùn)練集文本數(shù)?
int?train[800][10];//訓(xùn)練集二維數(shù)組?
int?label[800];//訓(xùn)練集標(biāo)簽數(shù)組?
int?valicnt=0;//驗證集文本數(shù)?
int?vali[500][10];//驗證集二維數(shù)組?
int?valilabel[500];//驗證集標(biāo)簽數(shù)組?
int?vali_label_result[800];//使用驗證集猜測的標(biāo)簽數(shù)組?
double?accuracy=0;//準(zhǔn)確率?
int?cnt_of_leave=0;//用訓(xùn)練集構(gòu)建的決策樹的葉子節(jié)點數(shù)目?
int?cnt_of_arriving_leaf=0;//使用決策樹時到達(dá)葉子節(jié)點的文本數(shù)?
int?cnt_of_not_arriving_leaf=0;//使用決策樹時沒有到達(dá)葉子節(jié)點的文本數(shù)?
int?cnt_of_pruned_leaves=0;
int?test[500][10];//測試集二維數(shù)組?
int?testcnt=0;//測試集樣本數(shù)?
int?test_label_result[500];//測試集使用決策樹后的預(yù)測結(jié)果?
int?test_cnt_of_arriving_leaf=0;//測試集使用決策樹時到達(dá)葉子結(jié)點?
int?test_cnt_of_not_arriving_leaf=0;//測試集使用決策樹時沒有到達(dá)葉子結(jié)點?
struct?Node{
	int?Data[1000][10];//數(shù)據(jù)集?
	int?Label[1000];//當(dāng)前數(shù)據(jù)集的標(biāo)簽數(shù)組，行數(shù)跟Data數(shù)據(jù)集一樣多?
	int?Attr[10];//共有9個特征?
	int?datasize;//共多少行數(shù)據(jù)集?
	int?attrsize;//共多少個特征?
	int?attr_chosen;//選取哪個特征向下分裂?
	int?final_label;//葉節(jié)點最后取的label（多數(shù)投票）?
	int?attr_num;//父節(jié)點分裂時這個節(jié)點的具體的特征值?
	vector?children;//子節(jié)點vector數(shù)組?
	bool?prune_or_not;//判斷是否剪枝?
};
Node?*root=new?Node;?
void?Readtext（）;
void?Readtest（）;
double?Empirical_entropy（Node?*p）//求當(dāng)前數(shù)據(jù)集的經(jīng)驗熵?HD
{
	double?HD;
	double?pos=0neg=0;
	for（int?i=0;idatasize;i++）//統(tǒng)計數(shù)據(jù)集中正標(biāo)簽和負(fù)標(biāo)簽的數(shù)目?
	{
		if（p->Label[i]==1）?pos++;
		else?neg++;
	}
	HD=-1*（pos/p->datasize）*log（pos/p->datasize）-（（neg/p->datasize）*log（neg/p->datasize））;
	return?HD;
}
double?Conditional_entropy（int?attr_indexNode?*p）//求索引位置為attr_index的特征的條件熵HDA?
{
	int?maxnum=0minnum=1000;
	for（int?i=0;idatasize;i++）{//先遍歷找出當(dāng)前特征的特征值的最小值和最大值?	
		if（p->Data[i][attr_index]Data[i][attr_index];
		if（p->Data[i][attr_index]>maxnum）?maxnum=p->Data[i][attr_index];
	}	
	double?HDA=0;
	for（int?i=minnum;i<=maxnum;i++）{//遍歷所有可能的取值?			
		double?pos=0neg=0cnt=0;
		for（int?j=0;jdatasize;j++）{//遍歷所有樣本?		
			if（p->Data[j][attr_index]==i）{//找出取值為i的所有樣本?			
				cnt++;//記錄取值為i的樣本的數(shù)量?
				if（p->Label[j]==1）?pos++;
				else?neg++;
			}
		}
		double?A=0B=0C=0;
		if（cnt!=0）{//cnt==0即沒有這個特征值時不計算，cnt!=0即存在這個特征值時計算?		
			A=（cnt/p->datasize）*-1;
			if（pos!=0）?B=pos/cnt*log（pos/cnt）;
			if（neg!=0）?C=neg/cnt*log（neg/cnt）;
			HDA+=A*（?B?+?C?）;	//累加?
		}				?	
	}
	return?HDA;
}
int?ID3（Node?*p）//用ID3從當(dāng)前節(jié)點的特征集當(dāng)中選擇一個特征來分裂?
{
	double?HD=Empirical_entropy（p）;//求當(dāng)前數(shù)據(jù)集的經(jīng)驗熵?
	double?HDA[10];
	for（int?i=0;iattrsize;i++）	
		HDA[i]=Conditional_entropy（ip）;//求第i個特征，在當(dāng)前數(shù)據(jù)集的經(jīng)驗熵?
	double?G[10]maxG=-100;
	int?max_index=0;//信息增益最大的特征的索引位置?
	for（int?i=0;iattrsize;i++）//遍歷所有特征，得到他們的信息增益?
	{
		G[i]=HD-HDA[i];
		if（G[i]>maxG）{	maxG=G[i];	max_index=i;}		
	}
	return?p->Attr[max_index];//最終返回的是這個特征而不是其索引位置?
}
double?SplitInfo（int?attr_indexNode*?p）//計算索引位置為attr_index的特征的熵?
{
	int?maxnum=0minnum=1000;
	for（int?i=0;idatasize;i++）//先遍歷找出當(dāng)前特征

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2018-04-02?16:00??決策樹代碼及數(shù)據(jù)文件\
?????文件???????15310??2018-04-02?16:00??決策樹代碼及數(shù)據(jù)文件\DecisionTree.cpp
?????文件????????6306??2017-10-26?11:06??決策樹代碼及數(shù)據(jù)文件\test.csv
?????文件???????17009??2017-10-26?11:06??決策樹代碼及數(shù)據(jù)文件\train.csv