第一章课程设计的目的及要求

1.1课程设计目标

 《面向对象编程课程设计》是必修的实践性教学环节之一，是学习了《程序设计基础》和《面向对象程序设计》课程之后的综合性实验课程，是对这两门课程所学知识所进行的一次全面的综合训练。通过学生完成所要求的设计项目，使学生系统掌握面向对象程序设计的基本理念、基本语法、实现方法、设计特性以及编程思想，综合培养学生利用所学的编程知识解决复杂工程问题的能力。学生根据设计要求首先进行需求分析、制定总体方案、设计程序架构、功能及类层次结构图，然后完成算法设计、程序开发、程序调试、程序优化和程序发布，最后撰写课程设计报告并提交程序代码清单。课程设计具体目标如下：

 课程目标1. 能够针对设计题目，通过调研或者查找资料，进行初步需求分析和系统总体设计的能力。

 课程目标2.能够利用面向对象程序设计的思想完成系统的设计并编程实现。

 课程目标3.能够根据设计工作量和人员特点进行合理分工。小组人员配合默契，能够互相交流，能够完成个人承担的任务，并且整个项目能够按时完成和保证质量。

 课程目标4.能够对设计的内容进行表述，并回答老师和同学提出的问题。

 课程目标5.能够绘制类图和流程图，具有按照软件工程思路撰写完整的课程设计报告。

 课程目标6. 能够对设计过程进行总结，能够意识到不足，并具有改进的意识。

1.2课程设计实验环境

 硬件要求：能运行Windows 操作系统的微机系统。

 软件要求：后端、底层使用Visual Studio2019,或其他C++语言应用程序的开发软件。前端使用vs.net ,QT等开发工具设计图形化的界面。

1.3课程设计的预备知识

 C++程序设计基础、面向对象的程序设计：熟悉C++语言的基本知识与编程思想，会使用Visual Studio的功能对程序进行开发、调试与编译。

1.4课程设计要求

 1.学习决策树相关知识，学习周志华《机器学习》相关章节。

 2.根据题目要求构建完整且自洽的算法并运行，编写出符合要求的程序。

 3.积极上机编写调试源程序，增强自学能力、编程能力、调试能力与心态调整能力。

 4.积极与其他组员认真沟通交流。协调工作、合理分配工作任务，开展高效的多人协同开发工作，增强合作能力。

 5.认真准备演示、答辩，认真书写课程设计说明报告。

 6.服从指导教师安排，确保能按时完成课程设计的相关任务。

第二章课程设计的内容

2.1c++语言程序设计——《利用决策树方法判定西瓜质量》课题内容

2.1.1问题描述

 以下数据集是经过确认的西瓜属性，请根据这些信息，利用决策树方法判定另外一批西瓜的质量。

2.1.2 功能要求

 1.学习有关决策树的相关知识

 2.构建每个属性的信息增益，并写入到文件Gain.txt中

 3.绘制决策树，保存成文件, Decision_tree.jpg

 4.利用随机算法生成不少于5W条的数据集，写入文件data.csv 中

 5.利用决策树进行判定，判定结果写入到result.csv中，并记录判定所花费的绝对时间

2.2问题分析

2.2.1 引入

 决策树是机器学习的一种常见方法。机器学习，就是指我们从给定的训练数据集中，构建一个模型。之后，利用这个模型，对新的未知数据集进行分类。这是一个构建抽象模型并回归具体事物的过程。而决策树是一种常用的抽象模型。它是基于树结构进行构建的。

 例如，我们如何决定明天出不出去玩？我们能根据多年的经验构建出一套对天气的认知，而这构建认知的过程就可以类比“机器学习”。我们根据这一套经验，先夜观天象，如果天有异象，则明天不出去；如果天气晴朗，则进一步判断：天气预报说明天温度是多少……这是一个先根据前置条件而选择分支，后进入分支做进一步决断的过程，直到找到最终的结果，这就是决策树的模型。

2.2.2相关概念

 本文对相关文献中涉及的概念进行了简化处理。

 叶结点：表示决策判定的结果值。

 根结点：决策树的第一步判定的属性值，可导出表示结果的叶结点或下一步判定属性值的内部节点。

 内部结点：表示中间步骤中判定属性值的结点。与根结点相同，可导出表示结果的叶结点或下一步判定属性值的内部节点。

 训练数据集：包括了若干项属性值与一项结果值，用作构建决策树的参数。

 待测数据集：包括了若干项属性值的数据集。可以通过决策树导出其结果值。

2.2.3 基本理论

 以下给出了决策树学习基本流程，简化但牺牲了一定严谨性。比起周志华老师的《机器学习》原文，这里作简化的原因包括但不限于：训练集样本容量较小、训练集样本没有缺失值、决策树深度较小，无需进行预剪枝与后剪枝。因此经过最多2次分类后，每个西瓜的好坏都是非常明确的。在此可以将几个递归返回的情形进行统一。

方法TreeGenerate(训练数据集D)

1.生成结点node;

2.If(数据集的结果值全相同，为C）

3. 将该node标记为C类叶结点 return；

4.End if

5.从数据集中选择最优划分属性值

6.for 对的每一个值()do

7. 为node生成一个分支，令表示D在上取值为的样本子集

8. if （为空）

9. 将该分支节点标记为叶结点，其判定结果值标记为D中结果值最多的值

10. return；

11. else

12. 以TreeGenerate()为分支结点，并剔除属性

2.3 后端程序设计

2.3.1 架构

 由于本课题侧重于算法构建而非对象、类的关联与架构，所以本程序架构相对简单，由main.cpp,TreeNode.cpp,TreeNode.h三份文档组成。所构建的类有且只有一个：TreeNode类

 main.cpp涉及了简单的输入输出、生成随机数据、调用生成决策树与利用决策树进行判断的函数，以便将后续工作顺利交接给前端。

 TreeNode.h写了TreeNode类属性与函数的声明，TreeNode.cpp写了各个函数的具体实现。这些函数主要分为两类：一类是计算工具，计算、信息熵、信息增益、连续值间断点、判断该集合的数据是否在判定结果值上相同。这些函数代码由队友完成。另一类函数即为构建决策树与利用决策树判断所涉及的核心算法与理论。这一部分代码由我完成。在下文中，我将具体阐述这些算法的具体实现。

2.3.2类的属性

 TreeNode类是树的结点，有13个属性。

 Continuouspoint为double类数组，长度为2，因为数据集中有且只有2个连续属性：密度、含糖率。在每次计算信息增益时，会将密度属性的划分点写入  Continuouspoint[0],将含糖率的划分点写入Continuouspoint[1]。

 isContinuous为bool类，用以判断该中间结点是否按照连续值来划分。

 breakingpoint为double类，若该中间结点按照连续值划分，即(TreeNode.isContinuous)，则该属性给出了划分点，该划分点由属性Continuouspoint取得。若该中间结点不按连续值划分，则该值无意义，默认值为0.

indexOfAttribute为int类，用以记录中间结点或根结点以哪个属性进行划分。

rem_wat为double类的二维数组，remaining watermelons，长度为18*10.该数组记录了剩下的未分的数据集。

 sizeOfWatermelons为int类，用以记录剩下未分的数据集的数据个数。

 isLeafNode为bool类，判断该节点是否为叶结点。

 isGood为bool类。若该结点为叶结点，则可通过isGood类知道该西瓜是否为好瓜，得到决策判定的结果值。若该结点不是叶节点，则该属性值无意义。

 entD为double类，储存了该结点所带数据集的初始信息熵。

 rem_att为int类数组，长度为10。指代remaining attributes,用于记录剩下的还未分完的属性的集合。

 attSize为int类，attribute size，用于记录剩下还未分完的属性的个数。

 childTree为TreeNode类vector，若该结点是根结点或中间结点，则该vector记录了子树的位置。若该结点为叶结点，则该vector的长度为0且无意义。

 attribute_size为静态int数组，储存了每项属性最多有几项取值。其中，编号的取值数记为-1，色泽、根蒂、敲声、纹理、脐部这五项属性都有3种取值，触感属性有2种取值。密度、含糖率为连续值，取值数量记为-1.

 言而简之，每个结点都记录了rem_wat，entD，Continuouspoint，sizeOfWatermelons，attSize，rem_att，isLeafNode，childTree。中间结点与根结点还有属性isContinuous，breakingpoint，indexOfAttribute。叶结点还有属性判断西瓜好坏isGood。

2.3.3类的函数

 在本文，我将侧重于介绍由我构建的函数。

 有两个构造函数。一个构造函数的参数为空，将各个属性初始化并置为0.另一个构造函数有4个参数，依次为：剩下的训练数据集、剩下的数据的个数、剩下的未划分的属性的集合、剩下的属性的个数。这个构造函数能够将这四个参数代入属性值、将所有其他属性值初始化为0，并计算初始的信息熵。

 deleteatt函数英文全名为delete attribute。在将大训练数据集按某个属性值分为多个小训练数据集后，调用该函数剔除该属性值，以便在子结点按另外的数据进行进一步的细分。

 generate_childNode函数为这个结点生成子结点。其流程根据2.2.3中提及的TreeGenerate，参数为rem_wat和sizeOfWatermelons，即训练数据集。利用这个函数，我们便能实现对决策树的构建。这个构建决策树的过程对于连续值的划分点进行了特化处理：在计算信息增益的过程中就确定了该结点该属性的划分点。由于前6个属性均为离散值，第7和第8项属性为连续值，为了简化代码，就不用attribute_size判断是否为连续值，而是直接分为两种情况：划分属性在1~6中间、划分属性在第7或第8项。若该属性为连续值，childNode[0]，childNode[1]分别储存了小于、大于划分点时子树的位置。若该属性是离散值，则childNode[i]储存了该离散值取i时子树的位置。需要说明的是，在前端的输入输出工作中，我们已经将离散值的具体文字转化为0/1/2等数字。

 judgeByTree函数遍历决策树并判断未知西瓜的好坏。该函数的逻辑如下：若该结点为叶结点，则该叶结点存储的isGood属性表示了该西瓜的好坏属性，完成判断。若该结点不是叶节点而是中间结点或根结点，则该结点的indexOfAttribute存储了该结点分类依据的属性，childNode[i]是根据该属性分类构建出的子树，并将西瓜数据交给子树判断。用这种方法递归，最终可以找到叶结点并判断该西瓜的好坏。这是一种前序遍历的逻辑。

2.3.4main函数的流程

 这里只涉及后端构建的main函数，而不涉及融合前端后的main函数流程。

 第一步，从watermelon.csv文件中读取数据，这些数据是原始的训练数据集，保存在data[17][10]这个double类数组中。而这个文件已经将离散值的文字处理成了0/1/2等数字。

 第二步，对这数据集的每列属性计算信息一次增益，并输出。

 第三步，将剩余未划分的属性rem_att[8]初始化，包括了全部8个属性。

 第四步，构建TreeNode类对象mytree，将data和rem_att作为参数，构建出决策树。

 第五步，随机生成50000个西瓜数据，这些西瓜的数据不包括西瓜本身好坏这一属性。创建double类的行指针，即double (*ListData)[10]。由于栈区内存不能同时存放50000条数据，我们将这50000条数据存放到堆区，以便进行进一步处理。

 第六步，开始计时。

 第七步，利用决策树对这50000条数据进行判断，得出西瓜的好坏。

 第八步，输出这50000条数据。

 第九步，结束计时，并输出第五步和第八步中间所经历的绝对时间。

 第十步，释放堆区内存，结束程序运行。

 另外还有一个独立的步骤：用easyx将决策树绘制并输出。这一步是在已经预知结果的情况下对该结果进行输出，而非根据第四步在系统内存中构建出的决策树来输出。

2.3.5头文件说明

 本文只说明后端所使用的的头文件，对前端运用QT等开发工具所使用的头文件不作涉及，对绘图所导入的库也不作涉及。

 为了防止TreeNode.h与TreeNode.cpp这两份文档被多次编译，加入#pragma once语句。

 Vector为stl库中的一个类模板，vector可以理解为自由伸缩长度的数组，用于记录子结点的地址。

 time.h头文件提供了计时功能。

 Random头文件提供了生成随机数据的功能。

 Fstream，iostream，math.h，iomanip，cstring，stdlib.h等头文件保证了程序各个功能的正常运行。

2.4后端程序设计的图像化

2.4.1 UML类图

2.4.2 决策树构建的流程图

2.4.3利用决策树进行判断的流程图

2.5 程序运行结果

2.5.1信息增益

 构建每个属性的信息增益，并写入gain.txt中

 如图所示，我们可以得知第一轮划分中每种属性的信息增益：

Gain(D,色泽)=0.109 Gain(D,根蒂)=0.143

Gain(D,敲声)=0.141 Gain(D,纹理)=0.381

Gain(D,脐部)=0.289 Gain(D,触感)=0.006

Gain(D,密度)=0.262 Gain(D,含糖率)=0.349

2.5.2决策树

(注：应为密度≤ 0.3815 \le 0.3815≤0.3815)

2.5.3随机数据

2.5.4判断数据并输出