机器学习期末报告算法实验.doc

机器学习期末报告（一）决策树一、决策树简介决策树是一种用来表示人们为了做出某个决策而进行的一系列判断过程的树形图。决策树方法的基本思想是：利用训练集数据自动地构造决策树，然后根据这个决策树对任意实例进行判定。决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树方法最早产生于上世纪60年代，到70年代末。由J Ross Quinlan提出了ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。决策树算法构造决策树来发现数据中蕴涵的分类规则如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步，决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。第二步，决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数扼集（称为测试数据集）中的数据校验决策树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除二、决策树的工作原理决策树一般都是自上而下的来生成的。选择分割的方法有多种，但是目的都是一致的，即对目标类尝试进行最佳的分割。从根节点到叶子节点都有一条路径，这条路径就是一条“规则”。决策树可以是二叉的，也可以是多叉的。对每个节点的衡量：1) 通过该节点的记录数；2) 如果是叶子节点的话，分类的路径；3) 对叶子节点正确分类的比例。有些规则的效果可以比其他的一些规则要好。YYYYNNNNw1Tx0 w4Tx0 w3Tx0 w2Tx0 二叉决策树框图三、决策树算法 决策树的典型算法有ID3，C4.5，CART等。国际权威的学术组织，数据挖掘国际会议ICDM （the IEEE International Conference on Data Mining）在2006年12月评选出了数据挖掘领域的十大经典算法中，C4.5算法排名第一。C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法。C4.5算法产生的分类规则易于理解，准确率较高。不过在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，在实际应用中因而会导致算法的低效。决策树算法的优点如下：（1）分类精度高；（2）生成的模式简单；（3）对噪声数据有很好的健壮性。因而是目前应用最为广泛的归纳推理算法之一，在数据挖掘中受到研究者的广泛关注。1. ID3算法ID3算法是一个众所周之的决策树算法，该算法是澳大利亚悉尼大学的Ross Quinlan于1986年提出，也是国际上最早、最有影响力的决策树算法，其他的许多算法如C4.5、CART算法等都是在ID3算法基础上的改进。在ID3算法中，决策节点属性的选择运用了信息论中的熵概念作为启发式函数。在这种属性选择方法中，选择具有最大信息增益（information gain）的属性作为当前划分节点。通过这种方式选择的节点属性可以保证决策树具有最小的分枝数量，使得到的决策树冗余最小。公式1：设数据划分D为类标记的元组的训练集。假定类标号属性具有M个不同值，定义m个不同的类Ci（I1，2，m），Ci,D是Ci类的元组的集合。和分别表示D和Ci,D中元组的个数。对D中的元组分类所需的期望信息由下式给出：公式2：假设属性A具有v个不同的离散属性值，可使用属性A把数据集D划分成v个子集D1, D2，Dv。设子集Dj中全部的记录数在A上具有相同的值aj。基于按A划分对D的元组分类所需要的期望信息由下式给出：公式3：信息增益定义为原来的信息需求（基于类比例）与新的信息需求（对A划分之后得到的）之间的差，即 Gain(A)=Info（D）-InfoA（D）ID3算法大概的流程就是在属性集A中寻找信息增益值最大的属性，作为根节点，按照根节点属性的取值将样本集合分成几个子集，将此属性从属性集中去掉，在每个子集中选择信息增益值最大的属性，作为当前子集的根节点，上层集合的根节点的子节点，如此循环递归，如果得到的子集中所有的样本属于一个类别，则递归停止。ID3算法对数据的要求：所有属性必须为离散量； 所有的训练例的所有属性必须有一个明确的值；相同的因素必须得到相同的结论且训练例必须唯一。实例：假如有一个网球爱好者，天气状况（天气、温度、湿度、风力）是决定他是否去打球的重要因素，利用ID3算法构筑决策树。以往部分打球数据库类标记的训练元组统计如表所示：类标号打球有两个取值（即是，否），因此有两个不同的类，即m=2，设C1类对应与是，C2类对应于否。C1有9个元组，C2有5个元组。我们根据公式1可以计算D中元组分类所需要的期望信息：如果根据天气属性划分，根据公式2则对D的元组进行分类所需要的期望信息为：根据公式3这种划分的信息增益是：Gain（天气）=info（D）-info天气（D）=0.940-0.694=0.246位类似地，可以计算：Gain(温度) = 0.029Gain(湿度)=0.151Gain(风力)=0.048由于天气在属性中具有最高信息增益，它被选作测试属性。创建一个节点，用天气标记，并根据每个属性值，引出一个分枝。注意，落在分区天气= 多云”的样本都属于同一类，根据算法，要在该分支的端点创建一个树叶，并用“是”标记。同理，在“晴朗”和“雨天” 这两个分支上，分别对“温度”、“湿度”、“风力”属性计算其信息增益，分别选取下一个测试属性。依算法全部计算后返回的最终决策树如图所示2. C4.5算法由于ID3算法在实际应用中存在一些问题，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一个改进算法。C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。C4.5算法的优点：产生的分类规则易于理解，准确率较高。C4.5算法的缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。分类决策树算法：C4.5算法是机器学习算法中的一种分类决策树算法，其核心算法是ID3算法。分类决策树算法是从大量事例中进行提取分类规则的自上而下的决策树。四、实现在Visual Studio2013中C+语言ID3算法实现决策树：代码：#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;class ID3class Nodepublic:string value;bool isLeaf;map map;public:Node() :value(), isLeaf(false);private:vector attribute;/vectorvector attributevalue;vectorvectordata;int decatt;Node *root;public:ID3()/ 从文件中加载数据ifstream fin(C:UsersAdministratorDesktopplayData.txt);string line, str;getline(fin, line); /read a line from the inputfin to lineistringstream istring(line); / bind to istring to the line we readwhile (!istring.eof()istring str; /read a word from lineattribute.push_back(str); while (!fin.eof()getline(fin, line);vector vecStr;istringstream istring(line);while (!istring.eof()istring str;vecStr.push_back(str);data.push_back(vecStr);fin.close();void run()setDec(4);vector subSet;for (int i = 0; idata.size(); i+)subSet.push_back(i);vector candidateAtt;for (int i = 0; iattribute.size(); i+)if (i != decatt)candidateAtt.push_back(i);Node *tree = buildDT(subSet, candidateAtt);/ 输出树结构root = tree;vector s;printTreeDepth(root, s);void setDec(int n)if (n= attribute.size()cout 指定决策树变量错误! endl;exit(0);decatt = n;double getEntropy(vector subSet)/ 获得子集信息熵double entropy = 0;double p, n;p = n = 0;vector vec;for (int i = 0; isubSet.size(); i+)if (datasubSetidecatt = yes)p+;elsen+;/ 判断属于同一类，熵为零的情况if (0 = p | 0 = n)return 0;double pR = p / (p + n), nR = n / (p + n);entropy = -pR*(log(pR) / log(2.0) - nR*(log(nR) / log(2.0);return entropy;bool isPure(vector subset)string value = datasubset0decatt;for (int i = 1; isubset.size(); i+)if (datasubsetidecatt != value)return false;return true;double gain(vector subset, int index) / 返回以index为节点的信息增益/ 统计正例个数和范例个数double entropy = getEntropy(subset);double sum = 0;/ 求可能的所有属性值mapstring, vector mapSub;for (int i = 0; isubset.size(); i+)mapSubdatasubsetiindex.push_back(subseti);for (mapstring, vector:iterator iter = mapSub.begin();iter != mapSub.end(); +iter)double tt = (iter-second.size() / (double)subset.size()*getEntropy(iter-second);/coutfirst:ttendl;sum += tt;return entropy - sum;/ suSet 指子集， value:属性值 attribute: 候选属性 tree: 根节点指针的指针Node* buildDT(vector subSet, vector attr)Node *p = new Node();if (isPure(subSet)p-isLeaf = true;p-value = datasubSet0decatt;/*if(*tree!=NULL)(*tree)-mapvalue=p;else(*tree)=p;*/return p;if (attr.size() = 0)int y, n;y = n = 0;for (int i = 0; i= n)p-isLeaf = true;p-value = yes;elsep-isLeaf = true;p-value = no;return p;/ 选择一个最优的属性int best = 0;double dmax = 0;int bestIndex = 0;for (int i = 0; idmax)dmax = dd;best = attri;bestIndex = i;/ 获得这个属性的所有属性值和其所对应的子集mapstring, vector mapAttValue;for (int i = 0; ivalue = this-attributebest;for (mapstring, vector:iterator iter = mapAttValue.begin();iter != mapAttValue.end(); +iter)p-mapiter-first = buildDT(iter-second, attr);/ 遍历每个属性值被选择后的子集，递归的创建树return p;private:void space(int n)for (int i = 0; in; i+)cout ;public:/ 输出从根节点到叶子节点的所有路径void printTree()Node *t = root;queue que;que.push(t);Node *q = t, *p;while (!que.empty()p = que.front();que.pop();cout setw(10) value;bool flag = false;if (p = q)cout endl;flag = true;for (map:iterator iter = p-map.begin();iter != p-map.end(); +iter)que.push(iter-second);if (flag)map:iterator iter1 = iter;iter1+;if (iter1 = p-map.end()q = iter-second;flag = false;void printTreeDepth(Node *t, vector vec)if (t-isLeaf)for (int i = 0; ivec.size(); i += 2)if (i != 0)cout ;cout veci : veci + 1;cout value;cout endl;cout value);for (map:iterator iter = t-map.begin();iter != t-map.end(); +iter)vec.push_back(iter-first);printTreeDepth(iter-second, vec);vec.pop_back();int main()ID3 id3;id3.run();return 0;playData.txt中训练数据：outlooktemperaturehumiditywindyplaysunnyhothighFALSEnosunnyhothighTRUEnoovercasthothighFALSEyesrainymildhighFALSEyesrainycoolnormalFALSEyesrainycoolnormalTRUEnoovercastcoolnormalTRUEyessunnymildhighFALSEnosunnycoolnormalFALSEyesrainymildnormalFALSEyessunnymildnormalTRUEyesovercastmildhighTRUEyesovercasthotnormalFALSEyesrainymildhighTRUEno结果：（二）概念学习一、定义及一些描述1. 定义：概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。通俗的说，就是给定一个样例集合以及每个样例是否属于某个概念的标注，怎样推断出该概念的一般定义。又称从样例中逼近布尔函数。2. 概念学习任务的描述：任何概念学习任务能被描述为：实例的集合、实例集合上的目标函数、候选假设的集合以及训练样例的集合。具体以Enjoy Sport为例，如图表2-1：表2-1 目标概念EnjoySport的训练样例No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes那么Enjoy Sport学习任务可以描述为：已知：实例集X：可能的日子，每个日子由下面的属性描述：sky:(可取值 sunny,Cloudy和Rainy)AirTemp:(可取值为Warm和Cold)Humidity:(可取值为Normal和High)Wind:(可取值为：Strong和Weak)Water：(可取值为Warm和Cold)Forecast:(可取值为Same和Change)假设集H：每个假设描述为6个属性：Sky,AirTemp,Humidity,Wind,Water和Forecast的值约束的合取。约束可以为“？”（表示接受任意值），“”（表示拒绝所有值），或一特定值目标概念C:EnjoySport: X-0,1训练样例集D：目标函数的正例和反例求解：H中的一假设h，使对于X中任意x，h(x)=c(x)3. 一些术语概念：实例集（X）:概念定义的实例集合目标概念（c）：待学习概念或函数训练样例（D）:每个样例为X中的一个实例x以及它的目标概念值c(x)。c(x)=1的实例被称为正例（positive example），c(x)=0的实例为反例（negative example），经常用序偶来描述训练样例。H表示所有可能假设的集合。H中每个假设H表示X上定义的布尔函数，即h:X-0,1。机器学习的目标就是寻找一个假设h，使对于X中的所有x，h(x)=c(x)。归纳学习假设：任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。二、 作为搜索的概念学习1. 概念学习可以看作一个在假设空间上搜索的过程，目标是找到能够最好地拟合训练样例的假设，学习的过程可以看作是一个从训练样例到假设空间选取的一个过程。2. 关系的“更一般”任给实例x和假设h，说x满足h，当且仅当h(x)=1。令hj和hk为在X上定义的布尔函数，称hj more_general_than_or_equal_to hk（记做hjghk），当且仅当(xX)(hk(x)=1)(hj(x)=1)利用这个关系，无需列举所有假设，就能在无限的假设空间中进行彻底的搜索三、 FIND-S：寻找极大特殊假设使用more_general_than偏序的搜索算法：从H中最特殊假设开始，然后在该假设覆盖正例失败时将其一般化（当一假设能正确地划分一个正例时，称该假设“覆盖”该正例）。1. FIND-S算法描述：1) 将h初始化为H中最特殊假设2) 对每个正例x：对h的每个属性约束ai，如果x满足ai，那么不做任何处理；否则将h中ai替换为x满足的下一个更一般的约束3). 输出假设h2. Find-S算法演示了一种利用more_general_than偏序来搜索假设空间的方法，沿着偏序链，从较特殊的假设逐渐转移到较一般的假设。因此，每一步得到的假设都是在那一点上与训练样例一致的最特殊的假设。Find-S的重要特点：对以属性约束的合取式描述的假设空间H，保证输出为H中与正例一致的最特殊的假设。四、 变换空间和候选消除算法（CANDIDATE-ELIMINATION）FIND-S输出的假设只是H中能够拟合训练样例的多个假设中的一个。而在候选消除算法中，输出的是与训练样例一致的所有假设的集合，且候选消除算法在描述这一集合时不需要明确列举所有成员，利用more_general_than偏序结构，可以维护一个一致假设集合的简洁表示1.几个定义一致：一个假设h与训练样例集合D一致，当且仅当对D中每一个样例都有h(x)=c(x)。Consistent(h,D)(D) h(x)=c(x)变型空间:关于假设空间H和训练样例集D的变型空间，标记为VSH,D，是H中与训练样例D一致的所有假设构成的子集。VSH,DhH|Consistent(h,D)2.列表后消除算法（LIST-THEN-ELIMINATE）描述（1）变型空间VersionSpace-包含H中所有假设的列表（2）对每个训练样例，从变型空间中移除所有h(x)c(x)的假设h（3）输出VersionSpace中个假设列表3. 变型空间的更简洁表示变型空间被表示为它的极大一般和极大特殊的成员，这些成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出变型空间。关于假设空间H和训练数据D的一般边界G，是在H中与D相一致的极大一般成员的集合。关于假设空间H和训练数据D的特殊边界S，是在H中与D相一致的极大特殊成员的集合4. 候选消除学习算法-初始化G和S-如果d是一个正例从G中移去所有与d不一致的假设对S中每个与d不一致的假设s-从S中移去s-把s的所有的极小泛化式h加入到S中，其中h满足：h与 d一致，而且G的某个成员比h更一般-从S中移去所有这样的假设：它比S中另一个假设更一般-如果d是一个反例从S中移去所有与d不一致的假设对G中每个与d不一致的假设g-从G中移去g-把g的所有的极小特殊化式h加入到G中，其中h满足：h与d一致，而且S的某个成员比h更特殊-从G中移去所有这样的假设：它比G中另一个假设更特殊5. 示例No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes把S集合初始化为H中极大特殊假设：把G集合初始化为H中极大一般假设：首先加载第一条和第二条样本：这个过程是特殊向一般的转变，这个过程非常地类似FIND-S算法接着我们处理第三条样本：回到数据，我们发现，Sky，AirTemp和Foreast和以前的数据不一致，我们可以怀疑是这三个数据导致最后结果的变化。所以，我们就针对这3个数据进行一次特殊化：接着，我们输入第四条样本：在处理第四条样本的时候，我们先对于S集合进行一般化：然后，为了让G集合覆盖S集合，我们需要剔除，过程为：在处理完了这四个样本后，我们就可以获取所有的假设：当前为6个假设，当我们可以获取到更多的训练集的时候，我们可以划出更小的设计空间。六、实现在Visual Studio2013中实现：/ bianxingspace.cpp#pragma warning (disable: 4996)#include using namespace std;#define A_CHAR_MAX 16#define A_VALUE_MAX 16#define A_NUM_MAX 32#define SAMPLES_MAX 256#define ALL -1#define NUL -2#define YES 1#define NO 0#define NUKOWN -1/ 属性struct Attributechar nameA_CHAR_MAX; / 属性名称int num; / 属性值个数char attA_VALUE_MAXA_CHAR_MAX; / 属性值;/ 假设struct Hypothesisint num; / 属性个数Attribute anA_NUM_MAX; / 属性集合;/ 假设值struct HypoValueint valueA_NUM_MAX;/ 样本struct SampleHypoValue ev; / 假设int result; / 正例/反例;Hypothesis g_Hypo; / 假设集合Sample g_saSAMPLES_MAX; / 样本空间int g_sn; / 样本数list g_G; / 一般边界Glist g_S; / 特殊边界S/ 从文件中读取假设集合/*/ 文件格式属性个数n属性名称1 属性值个数 属性值1 属性值2 属性值3 属性名称2 属性值个数 属性值1 属性值2 属性值3 属性名称n 属性值个数 属性值1 属性值2 属性值3 /*/bool ReadHypothesis(const char* filename)FILE* file;if (fopen_s(&file, filename , r) return false;int i,j,k;fscanf(file, %dn, &g_Hypo.num);for (i=0; ig_Hypo.num ; i+) fscanf(file, %s%d, g_H, &k); g_Hypo.ani.num = k; for (j=0; jk; j+) fscanf(file, %s, g_Hypo.ani.attj); fscanf(file, n);fclose(file);return true;/ 从文件中读取样本/*/ 文件格式样本个数m样本1属性1的值的序号 样本1属性2的值的序号 样本1属性n的值的序号 1（正例）或者0（反例）样本2属性1的值的序号 样本2属性2的值的序号 样本2属性n的值的序号 1（正例）或者0（反例）样本m属性1的值的序号 样本m属性2的值的序号 样本m属性n的值的序号 1（正例）或者0（反例）/*/bool ReadSamples(const char* filename)FILE* file;if (fopen_s(&file, filename , r) return false;int i,j;fscanf(file, %dn, &g_sn);for (i=0; ig_sn ; i+) for (j=0; jg_Hypo.num; j+) fscanf(file, %d, &g_sai.ev.valuej); fscanf(file, %dn,&g_sai.result);fclose(file);return true;/ 初始化G和Svoid InitGandS()HypoValue* evg = new HypoValue();HypoValue* evs = new HypoValue();for (int i=0; ivaluei = ALL; evs-valuei = NUL;g_G.push_back(evg);g_S.push_back(evs);/ 正例ps与假设h是否一致bool PositiveisConsistent(HypoValue h, HypoValue ps)for (int i=0; ig_Hypo.num; i+) if (h.valuei=ALL) continue; else if (h.valuei!=ps.valuei) return false;return true;/ 反例ns与假设h是否一致bool NegativeisConsistent(HypoValue h, HypoValue ns)for (int i=0; ig_Hypo.num; i+) if (h.valuei!=ALL & h.valuei!=ns.valuei) return true;return false;/ G的某个成员是否比h更一般bool GMemberMoreGeneral(HypoValue h)int i;list:iterator it;HypoValue mem;for (it=g_G.begin(); it!=g_G.end(); it+) mem = *it; for (i=0; ig_Hypo.num; i+) if (mem.valuei=h.valuei) continue; else if (mem.valuei=ALL | h.valuei=NUL) continue; else break; if (i=g_Hypo.num) return true;return false;/ 把s的所有的极小泛化式h加入到S中，并且满足h与d一致，而且G的某个成员比h更一般void MiniGeneral(HypoValue s, HypoValue d)HypoValue* h = new HypoValue();for (int i=0; ivaluei = ALL; else h-valuei = d.valuei;if (GMemberMoreGeneral(*h) g_S.push_front(h);else delete h;/ 从S中移去所有这样的假设：它比S中另一个假设更一般void RemoveMoreGeneralFromS()bool r1,r2;int i;HypoValue e1, e2;list:iterator it;list:iterator next;list:iterator temp;for (it=g_S.begin(); it!=g_S.end();) e1 = * *it; next = it; r1 = r2 = false; for (next+; next!=g_S.end();) e2 = * *next; r1 = r2 = false; for (i=0; ig_Hypo.num; i+) /if (e1.valuei=ALL & e2.valuei=ALL) / continue; /else if (e1.valuei=e2.valuei) continue; else if (e1.valuei=ALL) r1 = true; if (r2) break; else if (e2.valuei=ALL) r2 = true; if (r1) break; else r1 = r2 = true; break; if (r1=true & r2=false) /it比next更一般 break; if (r1=false) /next比it更一般或两者相同 temp = next; next+; g_S.remove(*temp); else /两者没有谁比谁更一般的关系 next+; if (r1=true & r2=false) /it比next更一般 temp = it; it+; g_S.remove(*temp); else it+;/ S的某个成员是否比h更特殊bool SMemberMoreSpecial(HypoValue h)int i;list:iterator it;HypoValue mem;for (it=g_S.begin(); it!=g_S.end(); it+) mem = *it; for (i=0;