【机器学习】决策树算法（ID3算法及C4.5算法）的理解和应用

1.信息熵： 度量一个属性的信息量
$S代表训练样本集合，p代表预测结果在总样本的占比的集合\\ 公式：Entropy(S) = -\sum_{i=1}^n{p_i}log_2p_i\\ 总样本数：5\\正样本数（满意）：3 \\ 负样本数（不满意）：2\\ 实例计算：Entropy(S) = -\frac{3}{5}\cdot log_2(\frac{3}{5})-\frac{2}{5}\cdot log_2(\frac{2}{5})$
2.条件熵： 表示在已知属性X的情况下它的属性类别Y的不确定性（需要求所有属性的条件熵）
$公式：Entropy(X|Y)=-\sum_{i=1}^np_ilog_2p_i (p_i=p(X=X_i))$

求身高的条件熵
$属性类别数 X_1(175)=1\\ 属性类别数 X_2(178)=2\\ 属性类别数 X_3(180)=2\\ X1=1(满意)\\ X2=1(满意)+1(不满意)\\ X3=1(满意)+1(不满意)\\ Entropy(X1)=-\frac{1}{1}log_2(\frac{1}{1})-\frac{0}{1}log_2(\frac{0}{1})\\ Entropy(X2)=-\frac{1}{2}log_2(\frac{1}{2})-\frac{1}{2}log_2(\frac{1}{2})\\ Entropy(X3)=-\frac{1}{2}log_2(\frac{1}{2})-\frac{1}{2}log_2(\frac{1}{2})\\ Entropy(身高)=\frac{1}{5}Entropy(X1)+\frac{2}{5}Entropy(X2)+\frac{2}{5}Entropy(X3)$
求年龄的条件熵
$属性类别数X1(偏大)=3\\ 属性类别数X2(偏小)=2\\ X1=2(不满意)+1(满意)\\ X2=2(满意)\\ Entropy(X1)=-\frac{1}{3}log_2\frac{1}{3}-\frac{2}{3}log_2\frac{2}{3}\\ Entropy(X2)=-\frac{2}{2}log_2\frac{2}{2}-\frac{0}{2}log_2\frac{0}{2}\\ Entropy(年龄)=\frac{3}{5}Entropy(X1)+\frac{2}{5}Entropy(X2)$
求是否有房的条件熵
$属性类别数X1(有)=2\\ 属性类别数X2(无)=3\\ X1=2(满意)\\ X2=1(满意)+2(不满意)\\ Entropy(X1)=-\frac{2}{2}log_2\frac{2}{2}-\frac{0}{2}log_2\frac{0}{2}\\ Entropy(X2)=-\frac{1}{3}log_2\frac{1}{3}-\frac{2}{3}log_2\frac{2}{3}\\ Entropy(是否有房)=\frac{2}{5}Entropy(X1)+\frac{3}{5}Entropy(X2)$
求工作单位的条件熵
$属性类别数X1(企业)=3\\ 属性类别数X2(*)=2\\ X1=2(满意)+1(不满意)\\ X2=1(满意)+1(不满意)\\ Entropy(X1)=-\frac{2}{3}log_2\frac{2}{3}-\frac{1}{3}log_2\frac{1}{3}\\ Entropy(X2)=-\frac{1}{2}log_2\frac{1}{2}-\frac{1}{2}log_2\frac{1}{2}\\ Entropy(工作单位)=\frac{3}{5}Entropy(X1)+\frac{2}{5}Entropy(X2)$

**3.信息增益：**信息熵与条件熵的差
$Gain(X|Y)=Entropy(S)-Entropy(X|Y)\\ Gain(身高)=Entropy(S)-Entropy(身高)\\ Gain(年龄)=Entropy(S)-Entropy(年龄)\\ Gain(是否有房)=Entropy(S)-Entropy(是否有房)\\ Gain(工作单位)=Entropy(S)-Entropy(工作单位)$

1.1.3 算法过程

在求出各属性的信息增益后，将属性增益最大的属性做为决策树的根结点。然后至上向下递归建树。这里简单的距离介绍确定第一个根结点后的步骤。

比如信息增益最大的属性为年龄，它有两个属性类别（即决策树的两个分支）

属性类别为“偏大”时（即分支为“偏大”）

身高	年龄	是否有房	工作单位	满意程度
175	偏大	有	企业	满意
178	偏大	无	企业	不满意
180	偏大	无	*	不满意

属性类别为“偏小”时（即分支为“偏小”）

身高	年龄	是否有房	工作单位	满意程度
178	偏小	无	*	满意
180	偏小	有	企业	满意

在此基础上在通过1.1.2中的基本概念求出各属性的信息增益，求出最大的信息增益在确定为根结点。
这里假设偏大分支下信息增益最大的属性是身高，偏小分支下信息增益最大的属性是工作单位。（如图）
【机器学习】决策树算法（ID3算法及C4.5算法）的理解和应用

1.2 C4.5算法

1.2.1 算法核心

在信息增益的基础上引入分裂率的概念，从而决定决策树根结点的因素变成了信息增益率。

1.2.2 基础概念

分裂率：
$引用上述例子来计算属性为身高时的分裂率：\\ 属性类别X_1(175)=1\\ 属性类别X_2(178)=2\\ 属性类别X_3(180)=2\\ split=-\frac{1}{5}log_2\frac{1}{5}-\frac{2}{5}log_2\frac{2}{5}-\frac{2}{5}log_2\frac{2}{5}$
信息增益率：
$信息增益率等于信息增益除以分裂率\\ Gain.ratio=\frac{Gain}{split}$
其余概念与ID3算法相同。

1.2.3 算法过程

除了判断根结点属性的依据是信息增益率之外，其余过程与ID3算法相同。

2.决策树分类实战

2.1 C++实现ID3算法和C4.5算法

功能菜单：
【机器学习】决策树算法（ID3算法及C4.5算法）的理解和应用
数据集：

数据集可以自己制作，这里我是用网上常用的数据（偷个懒），但制作时注意进行预处理操作。

附上代码（在VS下操作）：

除了功能6需要配置环境，其余均可直接复制使用。

头文件(pch.h)：


//#define PCH_H
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
using namespace std;

#define ROW 14
#define COL 5
#define log2 0.69314718055//这里指log以e为底的loge(2)的定义，方便后面使用换底公式

//定义决策树结点，这里运用的是兄弟-孩子双叉链表
typedef struct TNode
{
	char data[20];
	char weight[20];
	TNode* firstchild, * nextsibling;
}*tree;

//定义训练样本链表的结点
typedef struct LNode
{
	char  OutLook[20];
	char  Temperature[20];
	char  Humidity[20];
	char  Wind[20];
	char  PlayTennis[20];

	LNode* next;
}*link;

//定义属性链表的结点
typedef struct AttrNode
{
	char   attributes[15];//属性
	int	   attr_Num;//属性的个数

	AttrNode* next;
}*Attributes;

//定义属性类别
const char* OutLook_kind[3] = { "Sunny","OverCast","Rain" };
const char* Temperature_kind[3] = { "Hot","Mild","Cool" };
const char* Humidity_kind[2] = { "High","Normal" };
const char* Wind_kind[2] = { "Weak","Strong" };

//广义表表示决策树
void treelists(tree T);//不带分支
void treelists1(tree T, int& i);//带分支

//构建决策树的基本函数
void InitAttr(Attributes& attr_link, const char* Attributes_kind[], int Attr_kind[]);//构造属性链表
void InitLink(link& L, const char* Examples[][COL]);//构造训练样本链表
void PN_Num(link L, int& positve, int& negative);//计算正负样本

//ID3算法构建决策树
double Gain(int positive, int negative, const char* atrribute, link L, Attributes attr_L);//计算信息增益
void ID3(tree& T, link L, link Target_Attr, Attributes attr);//ID3算法构建决策树

//C4.5算法构建决策树
double Gain_Ratio(int positive, int negative, const char* atrribute, link L, Attributes attr_L);//计算信息增益率
void C4_5(tree& T, link L, link Target_Attr, Attributes attr);//C4.5算法构建决策树

//展示训练样本
void show(const char* Examples[][COL]);//终端展示
void show_txt(link LL, const char* Attributes_kind[], const char* Examples[][COL]);//打印有关样本数据

//测试数据
void Test(tree T, char train[4][20], char max[20], stack <char*>& a);//输出分类类别
void route(tree T, char train[4][20]);//输出测试数据在决策树中的遍历路径

//可视化决策树
void graphic1(tree T);//可视化ID3算法构建的决策树
void graphic2(tree T);//可视化C4.5算法构建的决策树

//基本函数(备用)
int TreeHeight(tree T);//求树的高度
void InOrderTraverse1(tree T);//先序遍历

主控文件(decision_tree.cpp)：



#include "pch.h"
#include <iostream>

const char* Examples[ROW][COL] = {
	//"OverCast","Cool","High","Strong","No",
	//"Rain","Hot","Normal","Strong","Yes",
	"Sunny","Hot","High","Weak","No",
	"Sunny","Hot","High","Strong","No",
	"OverCast","Hot","High","Weak","Yes",
	"Rain","Mild","High","Weak","Yes",
	"Rain","Cool","Normal","Weak","Yes",
	"Rain","Cool","Normal","Strong","No",
	"OverCast","Cool","Normal","Strong","Yes",
	"Sunny","Mild","High","Weak","No",
	"Sunny","Cool","Normal","Weak","Yes",
	"Rain","Mild","Normal","Weak","Yes",
	"Sunny","Mild","Normal","Strong","Yes",
	"OverCast","Mild","Normal","Strong","Yes",
	"OverCast","Hot","Normal","Weak","Yes",
	"Rain","Mild","High","Strong","No"
};
const char* Attributes_kind[4] = { "OutLook","Temperature","Humidity","Wind" };
int	   Attr_kind[4] = { 3,3,2,2 };

int main()
{



	//char* kind[COL - 1];
	link LL, p;
	Attributes attr_L, q;

	tree T, T_C;

	T = new TNode;
	T->firstchild = T->nextsibling = NULL;
	strcpy_s(T->weight, "");
	strcpy_s(T->data, "");

	T_C = new TNode;
	T_C->firstchild = T_C->nextsibling = NULL;
	strcpy_s(T_C->weight, "");
	strcpy_s(T_C->data, "");

	attr_L = new AttrNode;
	attr_L->next = NULL;

	LL = new LNode;
	LL->next = NULL;

	int choice;
	printf("					该系统通过决策树预测在何种天气下适合出门打球\n");
	printf("				$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");
	printf("				按键1：导入训练样本，显示训练数据\n");
	printf("				按键2：构建决策树,并展示信息增益信息\n");
	printf("				按键3：通过广义表来展示训练出来的决策树\n");
	printf("				按键4：输入测试数据展示该数据在决策树中的遍历路径，并输出分类结果\n");
	printf("				按键5：改进算法，优越性展示\n");
	printf("				按键6：可视化决策树(该程序使用会直接释放内存)，建议关闭程序时使用\n");
	printf("				按键0: 退出系统\n");
	printf("				$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");

	cout << "选择操作：";
	cin >> choice;
	while (choice != 0)
	{
		switch (choice)
		{
		case 1:
		{
		InitLink(LL, Examples);
		printf("成功导入样本数据\n\n");
		show(Examples);
		int choice1;
		printf("是否将训练样本信息进行打印(按键1:是;其他按键:否):");
		cin >> choice1;

		if (choice1 == 1)
		{
			if (LL->next != NULL)
			{
				show_txt(LL, Attributes_kind, Examples);
				printf("操作成功，请到相应目录找寻文件!\n");
			}
			else
				printf("训练样本链表未建立，建立后可呈现正负样本数!\n");
		}
		break;
		}
		case 2:
			if (LL->next != NULL)
			{
				InitAttr(attr_L, Attributes_kind, Attr_kind);
				ID3(T, LL, NULL, attr_L);
				if (T)
					printf("成功构建决策树！\n\n");
				else
					printf("决策树为空\n\n");
			}
			else
				printf("未导入训练样本，无法构建决策树！！！\n");
			break;
		case 3:
			if (T->firstchild != NULL)
			{
				int n;
				printf("是否展现树的分支权值（属性类别）(按键1.是;按键2.否):");
				cin >> n;
				if (n == 1)
				{
					printf("说明：{}内为分支权值（属性类别）\n");
					int i = 0;
					treelists1(T,i);
				}
				else  if (n == 2)
					treelists(T);
				else
					printf("操作错误!!!\n");
				cout << endl << endl;
			}
			if (T->firstchild == NULL)
				printf("决策树未构建!!!\n");
			break;
		case 4:
		{
			if (T->firstchild != NULL)
			{
				char train[COL - 1][20];
				cout << endl;
				int g = 0;
				printf("预测在某天气下是否出门打球\n");
				printf("仔细阅读输入数据规范要求\n");
				printf("----------------------------------------\n");
				cout << "四种属性:" << "OutLook" << ',' << "Temperature" << ',' << "Humidity" << ',' << "Wind" << endl;
				cout << "OutLook属性类别为:" << "Sunny" << ',' << "OverCast" << ',' << "Rain" << endl;
				cout << "Temperature属性类别为:" << "Hot" << ',' << "Mild" << ',' << "Cool" << endl;
				cout << "Humidity属性类别为:" << "High" << ',' << "Normal" << endl;
				cout << "Wind属性类别为:" << "Weak" << ',' << "Strong" << endl;
				printf("----------------------------------------\n");
				printf("请输入OutLook的属性类别：");
				cin >> train[0];
				if (!(strcmp(train[0], "Sunny") == 0 || strcmp(train[0], "OverCast") == 0 || strcmp(train[0], "Rain") == 0))
				{
					printf("操作错误，待输入完全后，请重新操作！！！\n");
					g++;
				}
				printf("请输入Temprature的属性类别：");
				cin >> train[1];
				if (!(strcmp(train[1], "Hot") == 0 || strcmp(train[1], "Mild") == 0 || strcmp(train[1], "Cool") == 0))
				{
					printf("操作错误，待输入完全后，请重新操作！！！\n");
					g++;
				}
				printf("请输入Humidity的属性类别：");
				cin >> train[2];
				if (!(strcmp(train[2], "High") == 0 || strcmp(train[2], "Normal") == 0))
				{
					printf("操作错误，待输入完全后，请重新操作！！！\n");
					g++;
				}
				printf("请输入Wind的属性类别：");
				cin >> train[3];
				if (!(strcmp(train[3], "Weak") == 0 || strcmp(train[3], "Strong") == 0))
				{
					printf("操作错误，待输入完全后，请重新操作！！！\n");
					g++;
				}

				if (g == 0)
				{
					stack<char*> a;
					//int g = 0;
					Test(T, train, T->data, a);
					//cout<<g<<' '<<a.size()<<endl;
					//cout << a.top() << endl;
					if (strcmp(a.top(), "Yes") == 0 || strcmp(a.top(), "No") == 0)
					{
						printf("预测结果(PlayTennis)：");

						if (strcmp(a.top(), "Yes") == 0)
							printf("可以出门打球！\n");
						else
							if (strcmp(a.top(), "No") == 0)
								printf("唉，不能出门打球了。。。\n");

						printf("输出测试数据在ID3算法构建出的决策树下经过的路径:");
						printf("%s", T->data);
						route(T->firstchild, train);
						cout << endl;
						printf("是否比较在C4.5算法下测试数据经过在决策树中经过的路径(按键1:是；其他按键:否):");
						int choice1;
						cin >> choice1;
						if (choice1 == 1)
						{
							if (T_C->firstchild != NULL)
							{
								printf("输出测试数据在C4.5算法构建出的决策树下经过的路径:");
								printf("%s", T_C->data);
								route(T_C->firstchild, train);
							}
							else
								printf("还未通过C4.5算法建立决策树，请选择按键5优化算法构建决策树!!!\n");
						}
						cout << endl;
					}
				}
				else
				{
					printf("重要的事说三遍：操作失误，请重新操作！！！\n");
				}
			}
			else
				printf("决策树未构建!\n");

			break;
		}

		case 5:
		{
			if (LL->next == NULL)
				printf("训练样本未导入!\n");
			else
			{
			printf("通过C4.5算法构建决策树，优化于ID3算法\n");
			C4_5(T_C, LL, NULL, attr_L);
			if (T_C)
				printf("成功构建决策树！\n\n");
			else
				printf("决策树为空\n\n");
			printf("以广义表形式展现决策树:\n");
			if (T_C != NULL)
			{
				printf("不带分支:");
				treelists(T_C);
				cout << endl;
				printf("带分支:");
				int i = 0;
				treelists1(T_C,i);
				cout << endl << endl;
			}
			if (T_C == NULL)
				printf("决策树未构建!!!\n");
			}
			break;
		}
		case 6:
		{
			int choice1;
			printf("决策树可视化（按键1:ID3算法构建的决策树;按键2：C4.5算法构建的决策树）:");
			cin >> choice1;
			if (choice1 == 1)
			{
				if (T->firstchild != NULL)
					graphic1(T);
				else
					printf("树未构建!\n");
			}
				
			else if (choice1 == 2)
			{
				if (T_C->firstchild != NULL)
					graphic2(T_C);
				else
					printf("树未构建!\n");
			}
			else
				printf("操作错误!\n");
			break;
		}
		default:printf("操作失误!\n"); break;


		}
		cout << "选择操作：";
		cin >> choice;
	}
	printf("谢谢使用！！！\n");
	cout << endl;
	return 0;
}

功能模块文件(pch.cpp)：

#include "pch.h"


//以广义表的形式输出树
void treelists(tree T)
{
	tree p;
	if (T == NULL)
		return;
	cout << T->data;//输出根结点
	p = T->firstchild;
	if (p)
	{
		cout << "(";//层次加'('
		treelists(p);//层次递归
		p = p->nextsibling;
		while (p)
		{
			cout << ',';//层内加','
			treelists(p);//层内递归
			p = p->nextsibling;
		}
		cout << ")";
	}

}

void treelists1(tree T,int &i)
{
	tree p;
	if (!T)
		return;
	if(i!=0)
	cout << "{" << T->weight << "}";

	i++;
	cout << T->data;

	p = T->firstchild;
	if (p)
	{
		cout << "(";
		while (p)
		{
			treelists1(p,i);
			p = p->nextsibling;
			if(p)
			cout << ',';
		}
		cout << ")";
	}
}

//建立属性链表（参数：待构建链表，属性种类，属性种类数）
void InitAttr(Attributes& attr_link, const char* Attributes_kind[], int Attr_kind[])
{
	Attributes p;
	for (int i = 0; i < COL - 1; i++)
	{
		p = new AttrNode;//结点初始化
		p->next = NULL;

		strcpy_s(p->attributes, Attributes_kind[i]);
		p->attr_Num = Attr_kind[i];

		//头插法（后面部分验证代码需要注意）
		p->next = attr_link->next;
		attr_link->next = p;
	}
}

//建立训练样本链表（参数待训练的样本，给定的样本数据）
void InitLink(link& LL, const char* Examples[][COL])
{
	link p;

	for (int i = 0; i < ROW; i++)
	{
		//结点初始化
		p = new LNode;
		p->next = NULL;

		strcpy_s(p->OutLook, Examples[i][COL - 5]);
		strcpy_s(p->Temperature, Examples[i][COL - 4]);
		strcpy_s(p->Humidity, Examples[i][COL - 3]);
		strcpy_s(p->Wind, Examples[i][COL - 2]);
		strcpy_s(p->PlayTennis, Examples[i][COL - 1]);

		//头插法
		p->next = LL->next;
		LL->next = p;
	}
}


//寻找正负样本 
void PN_Num(link L, int& positve, int& negative)
{
	positve = 0;
	negative = 0;
	link p;

	//找最终分类结果
	p = L->next;
	while (p)
	{
		if (strcmp(p->PlayTennis, "No") == 0)
			negative++;
		else if (strcmp(p->PlayTennis, "Yes") == 0)
			positve++;

		p = p->next;
	}
}


//计算信息增益（重点）
//参数：正样本数，负样本数，待计算属性，训练样本链表，属性链表
double Gain(int positive, int negative, const char* atrribute, link L, Attributes attr_L)
{
	int atrr_kinds;//每个属性的类别数
	int attr_th = 0;//第几个属性（这里是根据属性链表的顺序，由于是头插法构建，故顺序与插入顺序颠倒），仅用以验证

	Attributes p = attr_L->next;
	link q = L->next;

	//确定该属性的类别数
	while (p)
	{
		if (strcmp(p->attributes, atrribute) == 0)
		{
			atrr_kinds = p->attr_Num;//获得其属性类别数
			break;
		}
		p = p->next;
		attr_th++;
	}
	//printf("attr_th:%d,atrr_kinds:%d\n", attr_th, atrr_kinds);

	double entropy, gain = 0;

	//信息熵的计算（公式：entropy = -p1*log2(p1) - p2*log2(p2)）
	double p1 = 1.0 * positive / (positive + negative);//正样本占总样本的比例
	double p2 = 1.0 * negative / (positive + negative);//负样本占总样本的比例
	entropy = -p1 * log(p1) / log2 - p2 * log(p2) / log2;//公式计算,这里用到数学公式中换底公式的小技巧
	gain = entropy;


	//定义一个3*atrr_kinds的数组，目的为了存储该属性类别下的一系列信息，来计算条件熵
	int** kinds = new int* [3];//c++中定义二维数组的方法
	for (int j = 0; j < 3; j++)
	{
		kinds[j] = new int[atrr_kinds];
		//printf("%d\n",kinds[j]);
		//printf("kinds[%d]=%d\n",j,kinds[j]);
	}

	//初始化
	for (int j = 0; j < 3; j++)
	{
		for (int i = 0; i < atrr_kinds; i++)
		{
			kinds[j][i] = 0;
		}
	}

	/*初始化效果（以OutLook为例）：
			Sunny		OverCast	Rain
	总：	0			0			0
	正：	0			0			0
	负：	0			0			0

	  进行统计后效果（以OutLook为例）：
			Sunny		OverCast	Rain
	总：	5			4			5
	正：	2			4			3
	负：	3			0			2
	*/

	//Gain函数的目的是为了求某一个属性的信息增益（故需要在训练样本中找出该属性的条件熵）
	//将定义的二维数组填满信息
	while (q)
	{
		if (strcmp("OutLook", atrribute) == 0)
		{
			for (int i = 0; i < atrr_kinds; i++)//计算属性类别的信息（样本占比数，正样本数，负样本数）
			{
				if (strcmp(q->OutLook, OutLook_kind[i]) == 0)
				{
					kinds[0][i]++;//计算样本占比数

					if (strcmp(q->PlayTennis, "Yes") == 0)
						kinds[1][i]++;//计算正样本数
					else
						kinds[2][i]++;//计算负样本数
				}
			}
		}
		else if (strcmp("Temperature", atrribute) == 0)
		{
			for (int i = 0; i < atrr_kinds; i++)
			{
				if (strcmp(q->Temperature, Temperature_kind[i]) == 0)
				{
					kinds[0][i]++;

					if (strcmp(q->PlayTennis, "Yes") == 0)
						kinds[1][i]++;
					else
						kinds[2][i]++;
				}
			}
		}
		else if (strcmp("Humidity", atrribute) == 0)
		{
			for (int i = 0; i < atrr_kinds; i++)
			{
				if (strcmp(q->Humidity, Humidity_kind[i]) == 0)
				{
					kinds[0][i]++;

					if (strcmp(q->PlayTennis, "Yes") == 0)
						kinds[1][i]++;// 
					else
						kinds[2][i]++;
				}
			}
		}
		else if (strcmp("Wind", atrribute) == 0)
		{
			for (int i = 0; i < atrr_kinds; i++)
			{
				if (strcmp(q->Wind, Wind_kind[i]) == 0)
				{
					kinds[0][i]++;

					if (strcmp(q->PlayTennis, "Yes") == 0)
						kinds[1][i]++;
					else
						kinds[2][i]++;
				}
			}
		}
		q = q->next;
	}

	//计算信息增益，定义一个atrr_kinds的数组（目的存储entropy()如上注释）
	double* gain_kind = new double[atrr_kinds];

	/*
	条件熵公式的计算（需要）：每个属性类别的正负样本及其占比，类别之间的占比
	以OotLook为例：
	entropy(S)= -2/5 * log2(2/5) - 3/5 * log2(3/5)
	entropy(O)= -4/4 * log2(4/4) - 0/4 * log2(0/4)=0
	entropy(R)= -3/5 * log2(3/5) - 2/5 * log2(2/5)
	entropy(SOR)= 5/14entropy(S) + 4/14entropy(O) + 5/14entropy(R)
	gain = entropy(信息熵) - entropy(SOR)
	*/

	//上方公式计算
	for (int j = 0; j < atrr_kinds; j++)
	{
		if (kinds[0][j] != 0 && kinds[1][j] != 0 && kinds[2][j] != 0)
		{
			p1 = 1.0 * kinds[1][j] / kinds[0][j];
			p2 = 1.0 * kinds[2][j] / kinds[0][j];

			gain_kind[j] = -p1 * log(p1) / log2 - p2 * log(p2) / log2;//换底公式
			gain = gain - (1.0 * kinds[0][j] / (positive + negative)) * gain_kind[j];
		}
		else
			gain_kind[j] = 0;//通过上方注释可得出该结论
	}
	return gain;
}


//ID3算法中需要及时清空子属性链和子训练样本链
void FreeLink(link& Link)
{
	link p, q;
	p = Link->next;
	while (p)
	{
		q = p;
		p = p->next;
		delete(q);
	}
	Link->next = NULL;
}



//通过ID3算法构建决策树
//参数：树（待构建），训练样本链表，目标链（为了表示当属性链为空时的普遍情况，以防万一），属性链
void ID3(tree& T, link L, link Target_Attr, Attributes attr)
{
	//定义p,p1是为了构建attr_chilid的辅助，max是为了找到最大增益的属性
	Attributes p, max, attr_child, p1;

	//定义q和q1是为了构建link_child的辅助
	link q, link_child, q1;

	//定义r是为了构建新的结点以构树
	//定义tree_p的目的是为了当我们构建完每一层的第一个结点后需要改变操作对象（由T到T->firstchild）
	tree r, tree_p;

	//计算总训练样本中的正负样本
	int positive = 0, negative = 0;
	PN_Num(L, positive, negative);

	//初始化两个子集合（两个子集合是构建树的关键）
	attr_child = new AttrNode;
	attr_child->next = NULL;

	link_child = new LNode;
	link_child->next = NULL;

	if (positive == 0)//全是反例
	{
		strcpy_s(T->data, "No");
	}
	else if (negative == 0)//全是正例
	{
		strcpy_s(T->data, "Yes");
	}

	p = attr->next; //属性链表
	double gain, g = 0;

	if (p)
	{
		//建立属性子链表
		while (p)
		{
			//计算所有属性中哪个属性的信息增益最大，做为决策树的根结点
			gain = Gain(positive, negative, p->attributes, L, attr);
			cout << p->attributes << "的信息增益为：" << gain << endl;
			if (gain > g)
			{
				g = gain;
				max = p;
			}
			p = p->next;
		}
		strcpy_s(T->data, max->attributes);//增加决策树的节点

		cout << "信息增益最大的属性：max->attributes = " << max->attributes << endl << endl;

		//创建属性子链表（树的每一层只需要创建一次属性子链表）
		p = attr->next;
		while (p)
		{
			if (strcmp(p->attributes, max->attributes) != 0)//属性链中不为信息最大增益的属性进行链表构建
			{
				//初始化
				p1 = new AttrNode;
				p1->next = NULL;
				strcpy_s(p1->attributes, p->attributes);
				p1->attr_Num = p->attr_Num;
				//头插法
				p1->next = attr_child->next;
				attr_child->next = p1;
			}
			p = p->next;
		}

		//由于我们已经得到信息增益最大的点，我们就需要构建其分支（即属性类别，也可理解为权重）
		//而我们构建决策树的方式是利用兄弟孩子链表进行构建，因此构建第一步需要找到所有层的第一个结点（孩子结点）
		if (strcmp("OutLook", max->attributes) == 0)
		{
			//结点初始化
			r = new TNode;
			r->firstchild = r->nextsibling = NULL;
			//为结点的分支赋值（属性类别）
			strcpy_s(r->weight, OutLook_kind[0]);
			T->firstchild = r;

			//建立样本子链表（目的找第一个孩子结点）
			q = L->next;
			while (q)
			{
				//将q->OutLook为“Sunny”的数据进行链表建立
				if (strcmp(q->OutLook, OutLook_kind[0]) == 0)
				{
					q1 = new LNode;
					strcpy_s(q1->OutLook, q->OutLook);
					strcpy_s(q1->Humidity, q->Humidity);
					strcpy_s(q1->Temperature, q->Temperature);
					strcpy_s(q1->Wind, q->Wind);
					strcpy_s(q1->PlayTennis, q->PlayTennis);
					q1->next = NULL;

					q1->next = link_child->next;
					link_child->next = q1;
				}
				q = q->next;
			}
		}
		else if (strcmp("Temperature", max->attributes) == 0)
		{
			r = new TNode;
			r->firstchild = r->nextsibling = NULL;
			strcpy_s(r->weight, Temperature_kind[0]);
			T->firstchild = r;
			q = L->next;
			while (q)
			{
				if (strcmp(q->Temperature, Temperature_kind[0]) == 0)
				{
					q1 = new LNode;
					strcpy_s(q1->OutLook, q->OutLook);
					strcpy_s(q1->Humidity, q->Humidity);
					strcpy_s(q1->Temperature, q->Temperature);
					strcpy_s(q1->Wind, q->Wind);
					strcpy_s(q1->PlayTennis, q->PlayTennis);
					q1->next = NULL;

					q1->next = link_child->next;
					link_child->next = q1;
				}
				q = q->next;
			}
		}
		else if (strcmp("Humidity", max->attributes) == 0)
		{
			r = new TNode;
			r->firstchild = r->nextsibling = NULL;
			strcpy_s(r->weight, Humidity_kind[0]);
			T->firstchild = r;
			q = L->next;
			while (q)
			{
				if (strcmp(q->Humidity, Humidity_kind[0]) == 0)
				{
					q1 = new LNode;
					strcpy_s(q1->OutLook, q->OutLook);
					strcpy_s(q1->Humidity, q->Humidity);
					strcpy_s(q1->Temperature, q->Temperature);
					strcpy_s(q1->Wind, q->Wind);
					strcpy_s(q1->PlayTennis, q->PlayTennis);
					q1->next = NULL;

					q1->next = link_child->next;
					link_child->next = q1;
				}
				q = q->next;
			}
		}
		else if (strcmp("Wind", max->attributes) == 0)
		{
			r = new TNode;
			r->firstchild = r->nextsibling = NULL;
			strcpy_s(r->weight, Wind_kind[0]);

			T->firstchild = r;
			q = L->next;
			while (q)
			{
				if (strcmp(q->Wind, Wind_kind[0]) == 0)
				{
					q1 = new LNode;
					strcpy_s(q1->OutLook, q->OutLook);
					strcpy_s(q1->Humidity, q->Humidity);
					strcpy_s(q1->Temperature, q->Temperature);
					strcpy_s(q1->Wind, q->Wind);
					strcpy_s(q1->PlayTennis, q->PlayTennis);
					q1->next = NULL;

					q1->next = link_child->next;
					link_child->next = q1;
				}
				q = q->next;
			}
		}

		//上述过程，分别建立了属性子链表和训练样本子链表
		int p = 0, n = 0;
		PN_Num(link_child, p, n);//在子训练样本中找正负样本
		if (p != 0 && n != 0)
		{
			//递归（建立每一层的第一个节点，T->firstchild是重点）
			ID3(T->firstchild, link_child, Target_Attr, attr_child);
			FreeLink(link_child);//因为link_child会一直不一样，所以占用的空间要及时清空
		}
		else if (p == 0)//当样本都为负样本时
		{
			strcpy_s(T->firstchild->data, "No");
			FreeLink(link_child);
		}
		else if (n == 0)//当样本都为正样本时
		{
			strcpy_s(T->firstchild->data, "Yes");
			FreeLink(link_child);
		}

		/*
		（假设）样本例子（按建立第一个结点后的效果）：
		LookOut
		   |
		Humidity — Temperature — Wind
		*/

		//建立每一层上的其他节点
		//因为我们构建决策树是利用
		tree_p = T->firstchild;//由于我们在上面的操作中已经将每层的第一个结点构建完成，所以现在的操作目标应该从每层的第一个子节点的兄弟结点来操作

		for (int i = 1; i < max->attr_Num; i++)//注意这里的下标从1开始，因为我们已经建立了每层的第一个结点
		{
			//每层的max是固定的，但是分支（weight）是不一样的，因此对应的link_child也不一样
			//需要区分出是哪一种属性
			if (strcmp("OutLook", max->attributes) == 0)
			{
				r = new TNode;
				r->firstchild = r->nextsibling = NULL;
				strcpy_s(r->weight, OutLook_kind[i]);//这里是决策树分支的赋值
				tree_p->nextsibling = r;//对每层的兄弟结点进行操作

				q = L->next;
				while (q)
				{
					if (strcmp(q->OutLook, OutLook_kind[i]) == 0)
					{
						q1 = new LNode;
						strcpy_s(q1->OutLook, q->OutLook);
						strcpy_s(q1->Humidity, q->Humidity);
						strcpy_s(q1->Temperature, q->Temperature);
						strcpy_s(q1->Wind, q->Wind);
						strcpy_s(q1->PlayTennis, q->PlayTennis);
						q1->next = NULL;

						q1->next = link_child->next;
						link_child->next = q1;
					}
					q = q->next;
				}
			}
			else if (strcmp("Temperature", max->attributes) == 0)
			{
				r = new TNode;
				r->firstchild = r->nextsibling = NULL;
				strcpy_s(r->weight, Temperature_kind[i]);
				tree_p->nextsibling = r;
				q = L->next;
				while (q)
				{
					if (strcmp(q->Temperature, Temperature_kind[i]) == 0)
					{
						q1 = new LNode;
						strcpy_s(q1->OutLook, q->OutLook);
						strcpy_s(q1->Humidity, q->Humidity);
						strcpy_s(q1->Temperature, q->Temperature);
						strcpy_s(q1->Wind, q->Wind);
						strcpy_s(q1->PlayTennis, q->PlayTennis);
						q1->next = NULL;

						q1->next = link_child->next;
						link_child->next = q1;
					}
					q = q->next;
				}

			}
			else if (strcmp("Humidity", max->attributes) == 0)
			{
				r = new TNode;
				r->firstchild = r->nextsibling = NULL;
				strcpy_s(r->weight, Humidity_kind[i]);
				tree_p->nextsibling = r;
				q = L->next;
				while (q)
				{
					if (strcmp(q->Humidity, Humidity_kind[i]) == 0)
					{
						q1 = new LNode;
						strcpy_s(q1->OutLook, q->OutLook);
						strcpy_s(q1->Humidity, q->Humidity);
						strcpy_s(q1->Temperature, q->Temperature);
						strcpy_s(q1->Wind, q->Wind);
						strcpy_s(q1->PlayTennis, q->PlayTennis);
						q1->next = NULL;

						q1->next = link_child->next;
						link_child->next = q1;
					}
					q = q->next;
				}
			}
			else if (strcmp("Wind", max->attributes) == 0)
			{
				r = new TNode;
				r->firstchild = r->nextsibling = NULL;
				strcpy_s(r->weight, Wind_kind[i]);
				tree_p->nextsibling = r;
				q = L->next;
				while (q)
				{
					if (strcmp(q->Wind, Wind_kind[i]) == 0)
					{
						q1 = new LNode;
						strcpy_s(q1->OutLook, q->OutLook);
						strcpy_s(q1->Humidity, q->Humidity);
						strcpy_s(q1->Temperature, q->Temperature);
						strcpy_s(q1->Wind, q->Wind);
						strcpy_s(q1->PlayTennis, q->PlayTennis);
						q1->next = NULL;

						q1->next = link_child->next;
						link_child->next = q1;
					}
					q = q->next;
				}
			}

			//通过正负样本和训练样本子链表，属性子链表的关系，递归建树
			int p = 0, n = 0;
			PN_Num(link_child, p, n);
			if (p != 0 && n != 0)
			{
				//这里操作对象是兄弟结点
				ID3(tree_p->nextsibling, link_child, Target_Attr, attr_child);
				FreeLink(link_child);
			}
			else if (p == 0)
			{
				strcpy_s(tree_p->nextsibling->data, "No");
				FreeLink(link_child);
			}
			else if (n == 0)
			{
				strcpy_s(tree_p->nextsibling->data, "Yes");
				FreeLink(link_child);
			}

			tree_p = tree_p->nextsibling;//建立所有的孩子结点
		}//建立决策树结束
	}
	else
	{
		q = L->next;
		strcpy_s(T->data, q->PlayTennis);
		//这个地方要赋以训练样本Example中最普遍的Target_attributes的值
	}
}

void show(const char* Examples[][COL])
{
	int i, j;
	printf("OutLook         Temperature     Humidity        Wind            PlayTennis\n");
	printf("--------------------------------------------------------------------------\n");
	for (i = 0; i < ROW; i++)
	{
		if (strcmp(Examples[i][0], "OverCast") == 0)
			printf("%s        ", Examples[i][0]);
		else
			printf("%s\t\t", Examples[i][0]);
		printf("%s\t\t%s\t\t%s\t\t%s\n", Examples[i][1], Examples[i][2], Examples[i][3], Examples[i][4]);
	}
}

//测试，输出分类类别
void Test(tree T, char train[4][20], char max[20], stack <char*>& a)
{
	tree p;
	//g++;
	//queue<char*> a;
	if (T == NULL)
		return;
	if (strcmp(T->data, max) == 0)//根结点没有分支
		p = T->firstchild;
	else
		p = T;
	//cout << T->data << endl;
	a.push(T->data);
	int j, fig = 0;
	int i = 0;
	if (p != NULL)
	{

		for (j = 0; j < 4; j++)
		{
			if (strcmp(train[j], p->weight) == 0)
				fig++;
		}
		if (fig != 0)
		{
			p = p->firstchild;
			//cout << T->data << "----->";
			Test(p, train, max, a);
		}
		else
		{
			p = p->nextsibling;
			//cout << T->data << "----->";
			Test(p, train, max, a);
		}
		//cout << T->data << endl;

	}
}

//输出决策树经过路径
void route(tree T, char train[4][20])
{
	tree p;
	if (T == NULL)
		return;
	p = T;
	int j, fig = 0;
	int i = 0;
	if (p != NULL)
	{

		for (j = 0; j < 4; j++)
		{
			if (strcmp(train[j], p->weight) == 0)
				fig++;
		}
		if (fig != 0)
		{
			if (strcmp(T->data, "Yes") == 0 || strcmp(T->data, "No") == 0)
			{
				cout << "---" << '(' << T->weight << ')' << "--->" << T->data;
				p = p->firstchild;
			}
			if (strcmp(T->data, "Yes") != 0 && strcmp(T->data, "No") != 0)
			{
				p = p->firstchild;
				cout << "---" << '(' << T->weight << ')' << "--->" << T->data;
			}
			route(p, train);
		}
		else
		{
			p = p->nextsibling;
			//cout << "---" << '(' << T->weight << ')' << "--->" << T->data;
			route(p, train);
		}
	}
}


void InOrderTraverse1(tree T)
{
	//先序遍历
	if (T)
	{
		InOrderTraverse1(T->firstchild);
		InOrderTraverse1(T->nextsibling);
		cout << T->data << ' ';
	}
}

int TreeHeight(tree T)
{
	tree p;
	int h, maxh = 0;
	if (!T)
		return 0;
	else
	{
		p = T->firstchild;
		while (p)
		{
			h = TreeHeight(p);
			if (maxh < h)
				maxh = h;
			p = p->nextsibling;
		}
		return (maxh + 1);
	}
}


double Gain_Ratio(int positive, int negative, const char* atrribute, link L, Attributes attr_L)
{
	int atrr_kinds;//每个属性的类别数
	int attr_th = 0;//第几个属性（这里是根据属性链表的顺序，由于是头插法构建，故顺序与插入顺序颠倒），仅用以验证

	Attributes p = attr_L->next;
	link q = L->next;

	//确定该属性的类别数
	while (p)
	{
		if (strcmp(p->attributes, atrribute) == 0)
		{
			atrr_kinds = p->attr_Num;
			break;
		}
		p = p->next;
		attr_th++;
	}
	//printf("attr_th:%d,atrr_kinds:%d\n", attr_th, atrr_kinds);

	double entropy, gain = 0;

	//信息熵的计算（公式：entropy = -p1*log2(p1) - p2*log2(p2)）
	double p1 = 1.0 * positive / (positive + negative);//正样本占总样本的比例
	double p2 = 1.0 * negative / (positive + negative);//负样本占总样本的比例
	entropy = -p1 * log(p1) / log2 - p2 * log(p2) / log2;//公式计算,这里用到数学公式中换底公式的小技巧
	gain = entropy;


	//定义一个3*atrr_kinds的数组，目的为了存储该属性类别下的一系列信息，来计算条件熵
	int** kinds = new int* [3];//c++中定义二维数组的方法
	for (int j = 0; j < 3; j++)
	{
		kinds[j] = new int[atrr_kinds];
		//printf("%d\n",kinds[j]);
		//printf("kinds[%d]=%d\n",j,kinds[j]);
	}

	//初始化
	for (int j = 0; j < 3; j++)
	{
		for (int i = 0; i < atrr_kinds; i++)
		{
			kinds[j][i] = 0;
		}
	}

	/*初始化效果（以OutLook为例）：
			Sunny		OverCast	Rain
	总：	0			0			0
	正：	0			0			0
	负：	0			0			0

	  进行统计后效果（以OutLook为例）：
			Sunny		OverCast	Rain
	总：	5			4			5
	正：	2			4			3
	负：	3			0			2
	*/

	//Gain函数的目的是为了求某一个属性的信息增益（故需要在训练样本中找出该属性的条件熵）
	//将定义的二维数组填满信息
	while (q)
	{
		if (strcmp("OutLook", atrribute) == 0)
		{
			for (int i = 0; i < atrr_kinds; i++)//计算属性类别的信息（样本占比数，正样本数，负样本数）
			{
				if (strcmp(q->OutLook, OutLook_kind[i]) == 0)
				{
					kinds[0][i]++;//计算样本占比数

					if (strcmp(q->PlayTennis, "Yes") == 0)
						kinds[1][i]++;//计算正样本数
					else
						kinds[2][i]++;//计算负样本数
				}
			}
		}
		else if (strcmp("Temperature", atrribute) == 0)
		{
			for (int i = 0; i < atrr_kinds; i++)
			{
				if (strcmp(q->Temperature, Temperature_kind[i]) == 0)
				{
					kinds[0][i]++;

					if (strcmp(q->PlayTennis, "Yes") == 0)
						kinds[1][i]++;
					else
						kinds[2][i]++;
				}
			}
		}
		else if (strcmp("Humidity", atrribute) == 0)
		{
			for (int i = 0; i < atrr_kinds; i++)
			{
				if (strcmp(q->Humidity, Humidity_kind[i]) == 0)
				{
					kinds[0][i]++;

					if (strcmp(q->PlayTennis, "Yes") == 0)
						kinds[1][i]++;// 
					else
						kinds[2][i]++;
				}
			}
		}
		else if (strcmp("Wind", atrribute) == 0)
		{
			for (int i = 0; i < atrr_kinds; i++)
			{
				if (strcmp(q->Wind, Wind_kind[i]) == 0)
				{
					kinds[0][i]++;

					if (strcmp(q->PlayTennis, "Yes") == 0)
						kinds[1][i]++;
					else
						kinds[2][i]++;
				}
			}
		}
		q = q->next;
	}

	//计算信息增益，定义一个atrr_kinds的数组（目的存储entropy()如上注释）
	double* gain_kind = new double[atrr_kinds];

	/*
	条件熵公式的计算（需要）：每个属性类别的正负样本及其占比，类别之间的占比
	以OotLook为例：
	entropy(S)= -2/5 * log2(2/5) - 3/5 * log2(3/5)
	entropy(O)= -4/4 * log2(4/4) - 0/4 * log2(0/4)=0
	entropy(R)= -3/5 * log2(3/5) - 2/5 * log2(2/5)
	entropy(SOR)= 5/14entropy(S) + 4/14entropy(O) + 5/14entropy(R)
	gain = entropy(信息熵) - entropy(SOR)
	*/

	//上方公式计算
	for (int j = 0; j < atrr_kinds; j++)
	{
		if (kinds[0][j] != 0 && kinds[1][j] != 0 && kinds[2][j] != 0)
		{
			p1 = 1.0 * kinds[1][j] / kinds[0][j];
			p2 = 1.0 * kinds[2][j] / kinds[0][j];

			gain_kind[j] = -p1 * log(p1) / log2 - p2 * log(p2) / log2;//换底公式
			gain = gain - (1.0 * kinds[0][j] / (positive + negative)) * gain_kind[j];
		}
		else
			gain_kind[j] = 0;//通过上方注释可得出该结论
	}

	//计算该属性的不同类别在总样本中的占比，计算分裂率
	double* split_kind = new double[atrr_kinds];//计算分裂率
	int* split_th = new int[atrr_kinds];//存储该属性类别在样本中的数量
	//初始化
	for (int i = 0; i < atrr_kinds; i++)
		split_th[i] = 0;

	q = L->next;
	while (q)
	{
		if (strcmp("OutLook", atrribute) == 0)
		{
			for (int i = 0; i < atrr_kinds; i++)
			{
				if (strcmp(q->OutLook, OutLook_kind[i]) == 0)
					split_th[i]++;
			}
		}
		else if (strcmp("Temperature", atrribute) == 0)
		{
			for (int i = 0; i < atrr_kinds; i++)
			{
				if (strcmp(q->Temperature, Temperature_kind[i]) == 0)
					split_th[i]++;
			}
		}
		else if (strcmp("Humidity", atrribute) == 0)
		{
			for (int i = 0; i < atrr_kinds; i++)
			{
				if (strcmp(q->Humidity, Humidity_kind[i]) == 0)
					split_th[i]++;
			}
		}
		else if (strcmp("Wind", atrribute) == 0)
		{
			for (int i = 0; i < atrr_kinds; i++)
			{
				if (strcmp(q->Wind, Wind_kind[i]) == 0)
					split_th[i]++;
			}
		}
		q = q->next;
	}

	/*
	以OutLook为例：
	Sunny	OverCast	Rain
	5		4			5
	split_kind[0] = -5/14 * log2(5/14)
	split_kind[1] = -4/14 * log2(4/14)
	split_kind[2] = -5/14 * log2(5/14)
	split = split_kind[0] + split_kind[1] +split_kind[2]
	gain_ratio = gain/spilit
	*/

	//cout << "该属性的信息增益为" << gain << endl;

	double num;
	double split = 0;

	/*
	for (int i = 0; i < atrr_kinds; i++)
	{
		cout << split_th[i] << endl;
	}*/
	

	for (int i = 0; i < atrr_kinds; i++)
	{
		if (split_th[i] != 0 )
		{
			num = 1.0 * split_th[i] / (positive + negative);
			if (num != 2)
				split_kind[i] = -1 * num * log(num) / log2;
			if (num == 2)
				split_kind[i] = 0;
		}
		else
			split_kind[i] = 0;

		split += split_kind[i];
	}
	//cout << split <<','<<split_kind[0]<<','<<split_kind[1]<<','<<split_kind[2]<< endl;
	double gain_ratio;

	if (gain != 0)
		gain_ratio = gain / split;
	else
		gain_ratio = 0;

	return gain_ratio;
}





void C4_5(tree& T, link L, link Target_Attr, Attributes attr)
{
	//定义p,p1是为了构建attr_chilid的辅助，max是为了找到最大增益的属性
	Attributes p, max, attr_child, p1;

	//定义q和q1是为了构建link_child的辅助
	link q, link_child, q1;

	//定义r是为了构建新的结点以构树
	//定义tree_p的目的是为了当我们构建完每一层的第一个结点后需要改变操作对象（由T到T->firstchild）
	tree r, tree_p;

	//计算总训练样本中的正负样本
	int positive = 0, negative = 0;
	PN_Num(L, positive, negative);

	//初始化两个子集合（两个子集合是构建树的关键）
	attr_child = new AttrNode;
	attr_child->next = NULL;

	link_child = new LNode;
	link_child->next = NULL;

	if (positive == 0)//全是反例
	{
		strcpy_s(T->data, "No");
	}
	else if (negative == 0)//全是正例
	{
		strcpy_s(T->data, "Yes");
	}

	p = attr->next; //属性链表
	double gain, g = 0;

	if (p)
	{
		//建立属性子链表
		while (p)
		{
			//计算所有属性中哪个属性的信息增益最大，做为决策树的根结点
			gain = Gain_Ratio(positive, negative, p->attributes, L, attr);
			cout << p->attributes << "的信息增益率为：" << gain << endl;
			if (gain > g)
			{
				g = gain;
				max = p;
			}
			p = p->next;
		}
		strcpy_s(T->data, max->attributes);//增加决策树的节点

		cout << "信息增益率最大的属性：max->attributes = " << max->attributes << endl << endl;

		//创建属性子链表（树的每一层只需要创建一次属性子链表）
		p = attr->next;
		while (p)
		{
			if (strcmp(p->attributes, max->attributes) != 0)//属性链中不为信息最大增益的属性进行链表构建
			{
				//初始化
				p1 = new AttrNode;
				p1->next = NULL;
				strcpy_s(p1->attributes, p->attributes);
				p1->attr_Num = p->attr_Num;
				//头插法
				p1->next = attr_child->next;
				attr_child->next = p1;
			}
			p = p->next;
		}

		//由于我们已经得到信息增益最大的点，我们就需要构建其分支（即属性类别，也可理解为权重）
		//而我们构建决策树的方式是利用兄弟孩子链表进行构建，因此构建第一步需要找到所有层的第一个结点（孩子结点）
		if (strcmp("OutLook", max->attributes) == 0)
		{
			//结点初始化
			r = new TNode;
			r->firstchild = r->nextsibling = NULL;
			//为结点的分支赋值（属性类别）
			strcpy_s(r->weight, OutLook_kind[0]);
			T->firstchild = r;

			//建立样本子链表（目的找第一个孩子结点）
			q = L->next;
			while (q)
			{
				//将q->OutLook为“Sunny”的数据进行链表建立
				if (strcmp(q->OutLook, OutLook_kind[0]) == 0)
				{
					q1 = new LNode;
					strcpy_s(q1->OutLook, q->OutLook);
					strcpy_s(q1->Humidity, q->Humidity);
					strcpy_s(q1->Temperature, q->Temperature);
					strcpy_s(q1->Wind, q->Wind);
					strcpy_s(q1->PlayTennis, q->PlayTennis);
					q1->next = NULL;

					q1->next = link_child->next;
					link_child->next = q1;
				}
				q = q->next;
			}
		}
		else if (strcmp("Temperature", max->attributes) == 0)
		{
			r = new TNode;
			r->firstchild = r->nextsibling = NULL;
			strcpy_s(r->weight, Temperature_kind[0]);
			T->firstchild = r;
			q = L->next;
			while (q)
			{
				if (strcmp(q->Temperature, Temperature_kind[0]) == 0)
				{
					q1 = new LNode;
					strcpy_s(q1->OutLook, q->OutLook);
					strcpy_s(q1->Humidity, q->Humidity);
					strcpy_s(q1->Temperature, q->Temperature);
					strcpy_s(q1->Wind, q->Wind);
					strcpy_s(q1->PlayTennis, q->PlayTennis);
					q1->next = NULL;

					q1->next = link_child->next;
					link_child->next = q1;
				}
				q = q->next;
			}
		}
		else if (strcmp("Humidity", max->attributes) == 0)
		{
			r = new TNode;
			r->firstchild = r->nextsibling = NULL;
			strcpy_s(r->weight, Humidity_kind[0]);
			T->firstchild = r;
			q = L->next;
			while (q)
			{
				if (strcmp(q->Humidity, Humidity_kind[0]) == 0)
				{
					q1 = new LNode;
					strcpy_s(q1->OutLook, q->OutLook);
					strcpy_s(q1->Humidity, q->Humidity);
					strcpy_s(q1->Temperature, q->Temperature);
					strcpy_s(q1->Wind, q->Wind);
					strcpy_s(q1->PlayTennis, q->PlayTennis);
					q1->next = NULL;

					q1->next = link_child->next;
					link_child->next = q1;
				}
				q = q->next;
			}
		}
		else if (strcmp("Wind", max->attributes) == 0)
		{
			r = new TNode;
			r->firstchild = r->nextsibling = NULL;
			strcpy_s(r->weight, Wind_kind[0]);

			T->firstchild = r;
			q = L->next;
			while (q)
			{
				if (strcmp(q->Wind, Wind_kind[0]) == 0)
				{
					q1 = new LNode;
					strcpy_s(q1->OutLook, q->OutLook);
					strcpy_s(q1->Humidity, q->Humidity);
					strcpy_s(q1->Temperature, q->Temperature);
					strcpy_s(q1->Wind, q->Wind);
					strcpy_s(q1->PlayTennis, q->PlayTennis);
					q1->next = NULL;

					q1->next = link_child->next;
					link_child->next = q1;
				}
				q = q->next;
			}
		}

		//上述过程，分别建立了属性子链表和训练样本子链表
		int p = 0, n = 0;
		PN_Num(link_child, p, n);//在子训练样本中找正负样本
		if (p != 0 && n != 0)
		{
			//递归（建立每一层的第一个节点，T->firstchild是重点）
			C4_5(T->firstchild, link_child, Target_Attr, attr_child);
			FreeLink(link_child);//因为link_child会一直不一样，所以占用的空间要及时清空
		}
		else if (p == 0)//当样本都为负样本时
		{
			strcpy_s(T->firstchild->data, "No");
			FreeLink(link_child);
		}
		else if (n == 0)//当样本都为正样本时
		{
			strcpy_s(T->firstchild->data, "Yes");
			FreeLink(link_child);
		}

		/*
		（假设）样本例子（按建立第一个结点后的效果）：
		LookOut
		   |
		Humidity — Temperature — Wind
		*/

		//建立每一层上的其他节点
		//因为我们构建决策树是利用
		tree_p = T->firstchild;//由于我们在上面的操作中已经将每层的第一个结点构建完成，所以现在的操作目标应该从每层的第一个子节点的兄弟结点来操作

		for (int i = 1; i < max->attr_Num; i++)//注意这里的下标从1开始，因为我们已经建立了每层的第一个结点
		{
			//每层的max是固定的，但是分支（weight）是不一样的，因此对应的link_child也不一样
			//需要区分出是哪一种属性
			if (strcmp("OutLook", max->attributes) == 0)
			{
				r = new TNode;
				r->firstchild = r->nextsibling = NULL;
				strcpy_s(r->weight, OutLook_kind[i]);//这里是决策树分支的赋值
				tree_p->nextsibling = r;//对每层的兄弟结点进行操作

				q = L->next;
				while (q)
				{
					if (strcmp(q->OutLook, OutLook_kind[i]) == 0)
					{
						q1 = new LNode;
						strcpy_s(q1->OutLook, q->OutLook);
						strcpy_s(q1->Humidity, q->Humidity);
						strcpy_s(q1->Temperature, q->Temperature);
						strcpy_s(q1->Wind, q->Wind);
						strcpy_s(q1->PlayTennis, q->PlayTennis);
						q1->next = NULL;

						q1->next = link_child->next;
						link_child->next = q1;
					}
					q = q->next;
				}
			}
			else if (strcmp("Temperature", max->attributes) == 0)
			{
				r = new TNode;
				r->firstchild = r->nextsibling = NULL;
				strcpy_s(r->weight, Temperature_kind[i]);
				tree_p->nextsibling = r;
				q = L->next;
				while (q)
				{
					if (strcmp(q->Temperature, Temperature_kind[i]) == 0)
					{
						q1 = new LNode;
						strcpy_s(q1->OutLook, q->OutLook);
						strcpy_s(q1->Humidity, q->Humidity);
						strcpy_s(q1->Temperature, q->Temperature);
						strcpy_s(q1->Wind, q->Wind);
						strcpy_s(q1->PlayTennis, q->PlayTennis);
						q1->next = NULL;

						q1->next = link_child->next;
						link_child->next = q1;
					}
					q = q->next;
				}

			}
			else if (strcmp("Humidity", max->attributes) == 0)
			{
				r = new TNode;
				r->firstchild = r->nextsibling = NULL;
				strcpy_s(r->weight, Humidity_kind[i]);
				tree_p->nextsibling = r;
				q = L->next;
				while (q)
				{
					if (strcmp(q->Humidity, Humidity_kind[i]) == 0)
					{
						q1 = new LNode;
						strcpy_s(q1->OutLook, q->OutLook);
						strcpy_s(q1->Humidity, q->Humidity);
						strcpy_s(q1->Temperature, q->Temperature);
						strcpy_s(q1->Wind, q->Wind);
						strcpy_s(q1->PlayTennis, q->PlayTennis);
						q1->next = NULL;

						q1->next = link_child->next;
						link_child->next = q1;
					}
					q = q->next;
				}
			}
			else if (strcmp("Wind", max->attributes) == 0)
			{
				r = new TNode;
				r->firstchild = r->nextsibling = NULL;
				strcpy_s(r->weight, Wind_kind[i]);
				tree_p->nextsibling = r;
				q = L->next;
				while (q)
				{
					if (strcmp(q->Wind, Wind_kind[i]) == 0)
					{
						q1 = new LNode;
						strcpy_s(q1->OutLook, q->OutLook);
						strcpy_s(q1->Humidity, q->Humidity);
						strcpy_s(q1->Temperature, q->Temperature);
						strcpy_s(q1->Wind, q->Wind);
						strcpy_s(q1->PlayTennis, q->PlayTennis);
						q1->next = NULL;

						q1->next = link_child->next;
						link_child->next = q1;
					}
					q = q->next;
				}
			}

			//通过正负样本和训练样本子链表，属性子链表的关系，递归建树
			int p = 0, n = 0;
			PN_Num(link_child, p, n);
			if (p != 0 && n != 0)
			{
				//这里操作对象是兄弟结点
				C4_5(tree_p->nextsibling, link_child, Target_Attr, attr_child);
				FreeLink(link_child);
			}
			else if (p == 0)
			{
				strcpy_s(tree_p->nextsibling->data, "No");
				FreeLink(link_child);
			}
			else if (n == 0)
			{
				strcpy_s(tree_p->nextsibling->data, "Yes");
				FreeLink(link_child);
			}

			tree_p = tree_p->nextsibling;//建立所有的孩子结点
		}//建立决策树结束
	}
	else
	{
		q = L->next;
		strcpy_s(T->data, q->PlayTennis);
		//这个地方要赋以训练样本Example中最普遍的Target_attributes的值
	}
}

void show_txt(link LL, const char* Attributes_kind[], const char* Examples[][COL])
{
	FILE* fp;
	if ((fp = fopen("train.txt", "w+")) == NULL)
	{
		printf("File open error!\n");
		exit(0);
	}
	fprintf(fp, "%s: %s	%s	%s\n", Attributes_kind[0], OutLook_kind[0], OutLook_kind[1], OutLook_kind[2]);
	fprintf(fp, "%s: %s	%s	%s\n", Attributes_kind[1], Temperature_kind[0], Temperature_kind[1], Temperature_kind[2]);
	fprintf(fp, "%s: %s	%s\n", Attributes_kind[2], Humidity_kind[0], Humidity_kind[1]);
	fprintf(fp, "%s: %s	%s\n", Attributes_kind[3], Wind_kind[0], Wind_kind[1]);
	fprintf(fp, "\n\n");

	fprintf(fp, "%s		%s          %s	               %s	               PlayTennis\n", Attributes_kind[0], Attributes_kind[1], Attributes_kind[2], Attributes_kind[3]);
	for (int i = 0; i < ROW; i++)
	{
		fprintf(fp, "%s		", Examples[i][0]);
		fprintf(fp, "%s		", Examples[i][1]);
		fprintf(fp, "%s		", Examples[i][2]);
		fprintf(fp, "%s		", Examples[i][3]);
		fprintf(fp, "%s\n", Examples[i][4]);
	}
	fprintf(fp, "\n\n");

	int positive = 0, negative = 0;
	PN_Num(LL, positive, negative);
	fprintf(fp, "正样本:%d;负样本:%d\n", positive, negative);

	if (fclose(fp)) {
		printf("Can not close the file!\n");
		exit(0);
	}
}

//graphic工具，所想即所得
void graphic1(tree T)
{
	FILE* stream1;
	freopen_s(&stream1,"graph1.dot", "w+", stdout);
	if (stdout == NULL)
	{
		printf("File open error!\n");
		exit(0);
	}
	cout << "digraph G{" << endl;
	cout << T->data << "->" << T->firstchild->data << '[' << "label=" << '"' << T->firstchild->weight << '"' << ']' << ';' << endl;
	cout << T->firstchild->data << "->" << T->firstchild->firstchild->data << '1' << '[' << "label=" << '"' << T->firstchild->firstchild->weight << '"' << ']' << ';' << endl;
	cout << T->firstchild->data << "->" << T->firstchild->firstchild->nextsibling->data << '1' << '[' << "label=" << '"' << T->firstchild->firstchild->nextsibling->weight << '"' << ']' << ';' << endl;
	cout << T->data << "->" << T->firstchild->nextsibling->data  << '2' << '[' << "label=" << '"' << T->firstchild->nextsibling->weight << '"' << ']' << ';' << endl;
	cout << T->data << "->" << T->firstchild->nextsibling->nextsibling->data << '[' << "label=" << '"' << T->firstchild->nextsibling->nextsibling->weight << '"' << ']' << ';' << endl; 
	cout << T->firstchild->nextsibling->nextsibling->data<<"->"<<T->firstchild->nextsibling->nextsibling->firstchild->data << '[' << "label=" << '"' << T->firstchild->nextsibling->nextsibling->firstchild->weight << '"' << ']' << ';' << endl;
	cout << T->firstchild->nextsibling->nextsibling->data << "->" << T->firstchild->nextsibling->nextsibling->firstchild->nextsibling->data << '[' << "label=" << '"' << T->firstchild->nextsibling->nextsibling->firstchild->nextsibling->weight << '"' << ']' << ';' << endl;
	cout << "}" << endl;
	//fclose(stdout);
	if (fclose(stdout))
	{
		printf("Can not close the file!\n");
		exit(0);
	}
	system("dot -Tpng graph1.dot -o sample1.png");
}


void graphic2(tree T)
{
	FILE* stream1;
	freopen_s(&stream1, "graph2.dot", "w+", stdout);
	if (stdout == NULL)
	{
		printf("File open error!\n");
		exit(0);
	}
	cout << "digraph G{" << endl;

	cout << T->data << "->" << T->firstchild->data <<'1'<< '[' << "label=" << '"' << T->firstchild->weight << '"' << ']' << ';' << endl;
	cout << T->data << "->" << T->firstchild->nextsibling->data<<'1'  << '[' << "label=" << '"' << T->firstchild->nextsibling->weight << '"' << ']' << ';' << endl;
	cout<<T->firstchild->data<<'1'<<"->"<<T->firstchild->firstchild->data<<'1' << '[' << "label=" << '"' << T->firstchild->firstchild->weight << '"' << ']' << ';' << endl;
	cout<<T->firstchild->data<<'1'<<"->"<<T->firstchild->firstchild->nextsibling->data<<'1' << '[' << "label=" << '"' << T->firstchild->firstchild->nextsibling->weight << '"' << ']' << ';' << endl;
	cout<<T->firstchild->data<<'1'<<"->"<<T->firstchild->firstchild->nextsibling->nextsibling->data<<'2'<< '[' << "label=" << '"' << T->firstchild->firstchild->nextsibling->nextsibling->weight << '"' << ']' << ';' << endl;
	cout<<T->firstchild->firstchild->nextsibling->nextsibling->data<<'2'<<"->"<<T->firstchild->firstchild->nextsibling->nextsibling->firstchild->data <<'2'<< '[' << "label=" << '"' << T->firstchild->firstchild->nextsibling->nextsibling->firstchild->weight << '"' << ']' << ';' << endl;
	cout<<T->firstchild->firstchild->nextsibling->nextsibling->data<<'2'<<"->"<<T->firstchild->firstchild->nextsibling->nextsibling->firstchild->nextsibling->data<<'2' << '[' << "label=" << '"' << T->firstchild->firstchild->nextsibling->nextsibling->firstchild->nextsibling->weight << '"' << ']' << ';' << endl;
	cout<<T->firstchild->nextsibling->data<<'1'<<"->"<<T->firstchild->nextsibling->firstchild->data<<'3' << '[' << "label=" << '"' << T->firstchild->nextsibling->firstchild->weight << '"' << ']' << ';' << endl;
	cout<<T->firstchild->nextsibling->data<<'1'<<"->"<<T->firstchild->nextsibling->firstchild->nextsibling->data <<'2'<< '[' << "label=" << '"' << T->firstchild->nextsibling->firstchild->nextsibling->weight << '"' << ']' << ';' << endl;
	cout<<T->firstchild->nextsibling->firstchild->nextsibling->data<<'2'<<"->"<<T->firstchild->nextsibling->firstchild->nextsibling->firstchild->data <<'4'<< '[' << "label=" << '"' << T->firstchild->nextsibling->firstchild->nextsibling->firstchild->weight << '"' << ']' << ';' << endl;
	cout<<T->firstchild->nextsibling->firstchild->nextsibling->data<<'2'<<"->"<<T->firstchild->nextsibling->firstchild->nextsibling->firstchild->nextsibling->data <<'5'<< '[' << "label=" << '"' << T->firstchild->nextsibling->firstchild->nextsibling->firstchild->nextsibling->weight << '"' << ']' << ';' << endl;
	cout<<T->firstchild->nextsibling->firstchild->nextsibling->data<<'2'<<"->"<<T->firstchild->nextsibling->firstchild->nextsibling->firstchild->nextsibling->nextsibling->data<<'4' << '[' << "label=" << '"' << T->firstchild->nextsibling->firstchild->nextsibling->firstchild->nextsibling->nextsibling->weight << '"' << ']' << ';' << endl;

	cout << "}" << endl;

	//fclose(stdout);
	if (fclose(stdout))
	{
		printf("Can not close the file!\n");
		exit(0);
	}
	system("dot -Tpng graph2.dot -o sample2.png");
}

2.1.1 安装Graphviz（可视化决策树）

DOT语言是用来描述图形的一种语言，而Graphviz则是用来处理这种语言的工具，适用于树结构的可视化。
该地址下下载graphviz-2.38.msi
https://graphviz.gitlab.io/_pages/Download/Download_windows.html
下载后会出现
【机器学习】决策树算法（ID3算法及C4.5算法）的理解和应用
然后一直点next，直到出现安装路径时，它会给你默认安装路径（这里个人建议放在你自己熟悉的路径下，方便后面配置环境变量）
安装后

环境变量配置：
搜索—>编辑系统环境变量—>高级—>环境变量—>系统变量中找到path—>添加安装路径加上bin
【机器学习】决策树算法（ID3算法及C4.5算法）的理解和应用
有的电脑需要重启一下，使得环境变量生效。
bin文件下标注的gvedit可以直接调用该工具

dot语言可参考：https://blog.csdn.net/STILLxjy/article/details/86004519

注意： 该工具在c++环境下不够友好，基本每次运行只能调用一次。

2.2 Python下实现CART算法

1.安装Graphviz（如上）
2.pip install graphviz
3.pip install pydotplus

数据集（配置适合你的隐形眼镜）
【机器学习】决策树算法（ID3算法及C4.5算法）的理解和应用

# -*- coding: UTF-8 -*-
from sklearn.preprocessing import LabelEncoder, OneHotEncoder
from sklearn.externals.six import StringIO
from sklearn import tree
import pandas as pd
import numpy as np
import pydotplus
import os


if __name__ == '__main__':
    os.environ["PATH"] += os.pathsep + 'E:/Graphviz-2.38/bin' #若环境配置不成功，则直接代码调用环境，E:/Graphviz-2.38/bin为我的安装路径
    with open('D:/desktop/experience/lenses1.txt', 'r') as fr:                                        #加载文件
        lenses = [inst.strip().split('\t') for inst in fr.readlines()]     #处理文件
        #print(lenses)
    lenses_target = []                                                        #提取每组数据的类别，保存在列表里
    for each in lenses:
        #print(each[-1])
        lenses_target.append(each[-1])
    #print(lenses_target)

    lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']            #特征标签       
    lenses_list = []                                                        #保存lenses数据的临时列表
    lenses_dict = {}                                                        #保存lenses数据的字典，用于生成pandas
    for each_label in lensesLabels:                                            #提取信息，生成字典
        for each in lenses:
            lenses_list.append(each[lensesLabels.index(each_label)])
        lenses_dict[each_label] = lenses_list
        lenses_list = []
    #print(lenses_dict)                                                        #打印字典信息
    lenses_pd = pd.DataFrame(lenses_dict)                                    #生成pandas.DataFrame
    print(lenses_pd)                                                        #打印pandas.DataFrame
    le = LabelEncoder()                                                        #创建LabelEncoder()对象，用于序列化           
    for col in lenses_pd.columns:                                            #序列化
        lenses_pd[col] = le.fit_transform(lenses_pd[col])
    print(lenses_pd)                                                        #打印编码信息

    clf = tree.DecisionTreeClassifier(max_depth = 4)                        #创建DecisionTreeClassifier()类
    clf = clf.fit(lenses_pd.values.tolist(), lenses_target)                    #使用数据，构建决策树
    dot_data = StringIO()
    tree.export_graphviz(clf, out_file = dot_data,                            #绘制决策树
                        feature_names = lenses_pd.keys(),
                        class_names = clf.classes_,
                        filled=True, rounded=True,
                        special_characters=True)
    graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
    graph.write_pdf("tree1.pdf")                                                #保存绘制好的决策树，以PDF的形式存储。

决策树可视化：
【机器学习】决策树算法（ID3算法及C4.5算法）的理解和应用

相关标签：决策树算法机器学习

上一篇： CodeForces 1150C Prefix Sum Primes

下一篇：洛谷 3620 [APIO2007]数据备份贪心

【机器学习】决策树算法（ID3算法及C4.5算法）的理解和应用

文章目录