决策树C4.5算法的c++实现

本程序为VS2010编写，其中源程序中包含测试数据。

#include “DecisionTree.h“

int main（int argc char* argv[]）{
	string filename = “source.txt“;
	DecisionTree dt ;
	int attr_node = 0;
	TreeNode* treeHead = nullptr;
	set readLineNum;
	vector readClumNum;
	int deep = 0;
	if （dt.pretreatment（filename readLineNum readClumNum） == 0）
	{
		dt.CreatTree（treeHead dt.getStatTree（） dt.getInfos（） readLineNum readClumNum deep）;
	}
	return 0;
}
/*
* @function CreatTree 预处理函数，负责读入数据，并生成信息矩阵和属性标记
* @param: filename 文件名
* @param: readLineNum 可使用行set
* @param: readClumNum 可用属性set
* @return int 返回函数执行状态
*/
int DecisionTree::pretreatment（string filename set& readLineNum vector& readClumNum）
{
	ifstream read（filename.c_str（））;
	string itemline = ““;
	getline（read itemline）;
	istringstream iss（itemline）;
	string attr = ““;
	while（iss >> attr）
	{
		attributes* s_attr = new attributes（）;
		s_attr->attriName = attr;
		//初始化属性名
		statTree.push_back（s_attr）;
		//初始化属性映射
		attr_clum[attr] = attriNum;
		attriNum++;
		//初始化可用属性列
		readClumNum.push_back（0）;
		s_attr = nullptr;
	}

	int i  = 0;
	//添加具体数据
	while（true）
	{
		getline（read itemline）;
		if（itemline == ““ || itemline.length（） <= 1）
		{
			break;
		}
		vector infoline;
		istringstream stream（itemline）;
		string item = ““;
		while（stream >> item）
		{
			infoline.push_back（item）;
		}

		infos.push_back（infoline）;
		readLineNum.insert（i）;
		i++;
	}
	read.close（）;
	return 0;
}

int DecisionTree::statister（vector>& infos vector& statTree 
							set& readLine vector& readClumNum）
{
	//yes的总行数
	int deciNum = 0;
	//统计每一行
	set::iterator iter_end = readLine.end（）;
	for （set::iterator line_iter = readLine.begin（）; line_iter != iter_end; ++line_iter）
	{
		bool decisLine = false;
		if （infos[*line_iter][attriNum - 1] == “yes“）
		{
			decisLine = true;
			deciNum++; //无用，因为子树的和就是他，在计算时自动就加完这个数了
		}
		//如果该列未被锁定并且为属性列，进行统计
		for （int i = 0; i < attriNum - 1; i++）
		{
			if （readClumNum[i] == 0）
			{
				std::string tempitem = infos[*line_iter][i];
				auto map_iter = statTree[i]->attriItem.find（tempitem）;
				//没有找到
				if （map_iter == （statTree[i]->attriItem）.end（））
				{
					//新建
					attrItem* attritem = new attrItem（）;
					attritem->itemNum.push_back（1）;
					decisLine ? attritem->itemNum.push_back（1） : attritem->itemNum.push_back（0）;
					attritem->itemLine.insert（*line_iter）;
					//建立属性名->item映射
					（statTree[i]->attriItem）[tempitem] = attritem;
					attritem = nullptr;
				}
				else
				{
					（map_iter->second）->itemNum[0]++;
					（map_iter->second）->itemLine.insert（*line_iter）;
					if（decisLine）
					{
						（map_iter->second）->itemNum[1]++;
					}
				}
			}
		}
	}
	return deciNum;
}

/*
* @function CreatTree 递归DFS创建并输出决策树
* @param: treeHead 为生成的决定树
* @param: statTree 为状态树，此树动态更新，但是由于是DFS对数据更新，所以不必每次新建状态树
* @param: infos 数据信息
* @param: readLine 当前在infos中所要进行

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      14314  2012-11-14 22:52  DecisionTree\DecisionTree\Debug\DecisionTree.Build.CppClean.log

     文件        454  2012-11-14 22:52  DecisionTree\DecisionTree\Debug\DecisionTree.log

     文件       8552  2012-11-14 22:23  DecisionTree\DecisionTree\DecisionTree.cpp

     文件       1473  2012-11-14 21:43  DecisionTree\DecisionTree\DecisionTree.h

     文件       4079  2012-10-13 09:45  DecisionTree\DecisionTree\DecisionTree.vcxproj

     文件       1269  2012-10-13 09:45  DecisionTree\DecisionTree\DecisionTree.vcxproj.filters

     文件        143  2012-10-12 20:54  DecisionTree\DecisionTree\DecisionTree.vcxproj.user

     文件       1690  2012-10-20 10:57  DecisionTree\DecisionTree\Release\cl.command.1.tlog

     文件      18344  2012-10-20 10:57  DecisionTree\DecisionTree\Release\CL.read.1.tlog

     文件       1402  2012-10-20 10:57  DecisionTree\DecisionTree\Release\CL.write.1.tlog

     文件        381  2012-10-20 10:57  DecisionTree\DecisionTree\Release\DecisionTree.exe.intermediate.manifest

     文件         86  2012-10-20 10:57  DecisionTree\DecisionTree\Release\DecisionTree.lastbuildstate

     文件       2414  2012-10-20 10:57  DecisionTree\DecisionTree\Release\DecisionTree.log

     文件    1150527  2012-10-20 10:57  DecisionTree\DecisionTree\Release\DecisionTree.obj

     文件       1804  2012-10-20 10:57  DecisionTree\DecisionTree\Release\link.command.1.tlog

     文件       3068  2012-10-20 10:57  DecisionTree\DecisionTree\Release\link.read.1.tlog

     文件        938  2012-10-20 10:57  DecisionTree\DecisionTree\Release\link.write.1.tlog

     文件        596  2012-10-20 10:57  DecisionTree\DecisionTree\Release\mt.command.1.tlog

     文件        878  2012-10-20 10:57  DecisionTree\DecisionTree\Release\mt.read.1.tlog

     文件        406  2012-10-20 10:57  DecisionTree\DecisionTree\Release\mt.write.1.tlog

     文件     688353  2012-10-20 10:57  DecisionTree\DecisionTree\Release\Tree.obj

     文件     397312  2012-10-20 10:57  DecisionTree\DecisionTree\Release\vc100.pdb

     文件        417  2012-11-09 11:17  DecisionTree\DecisionTree\source.txt

     文件       1579  2012-10-13 09:45  DecisionTree\DecisionTree\Tree.cpp

     文件        527  2012-10-16 19:27  DecisionTree\DecisionTree\Tree.h

     文件        903  2012-10-12 20:54  DecisionTree\DecisionTree.sln

    ..A..H.     16384  2012-11-14 19:31  DecisionTree\DecisionTree.suo

     文件   27983872  2012-11-14 21:43  DecisionTree\ipch\decisiontree-8f8fd611\decisiontree-bfb5d3ca.ipch

     文件      49152  2012-10-20 10:57  DecisionTree\Release\DecisionTree.exe

     文件     773120  2012-10-20 10:57  DecisionTree\Release\DecisionTree.pdb

............此处省略11个文件信息