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

..机器学习期末报告〔一决策树一、决策树简介决策树是一种用来表示人们为了做出某个决策而进行的一系列判断过程的树形图。决策树方法的基本思想是：利用训练集数据自动地构造决策树,然后根据这个决策树对任意实例进行判定。决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法,首先对数据进行处理,利用归纳算法生成可读的规则和决策树,然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树方法最早产生于上世纪60年代,到70年代末。由JRossQuinlan提出了ID3算法,此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。C4.5算法在ID3算法的基础上进行了改进,对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大改进,既适合于分类问题,又适合于回归问题。决策树算法构造决策树来发现数据中蕴涵的分类规则．如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步,决策树的生成：由训练样本集生成决策树的过程。一般情况下,训练样本数据集是根据实际需要有历史的、有一定综合程度的,用于数据分析处理的数据集。第二步,决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程,主要是用新的样本数扼集〔称为测试数据集中的数据校验决策树生成过程中产生的初步规则,将那些影响预衡准确性的分枝剪除二、决策树的工作原理决策树一般都是自上而下的来生成的。选择分割的方法有多种,但是目的都是一致的,即对目标类尝试进行最佳的分割。从根节点到叶子节点都有一条路径,这条路径就是一条"规则"。决策树可以是二叉的,也可以是多叉的。对每个节点的衡量：1>通过该节点的记录数；2>如果是叶子节点的话,分类的路径；3>对叶子节点正确分类的比例。有些规则的效果可以比其他的一些规则要好。YYYYYNNNNw1Tx≥0w4Tx≥0w3Tx≥0w2Tx≥0二叉决策树框图三、决策树算法决策树的典型算法有ID3,C4.5,CART等。国际权威的学术组织,数据挖掘国际会议ICDM〔theIEEEInternationalConferenceonDataMining在20XX12月评选出了数据挖掘领域的十大经典算法中,C4.5算法排名第一。C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法。C4.5算法产生的分类规则易于理解,准确率较高。不过在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,在实际应用中因而会导致算法的低效。决策树算法的优点如下：〔1分类精度高；〔2生成的模式简单；〔3对噪声数据有很好的健壮性。因而是目前应用最为广泛的归纳推理算法之一,在数据挖掘中受到研究者的广泛关注。1.ID3算法ID3算法是一个众所周之的决策树算法,该算法是澳大利亚悉尼大学的RossQuinlan于1986年提出,也是国际上最早、最有影响力的决策树算法,其他的许多算法如C4.5、CART算法等都是在ID3算法基础上的改进。在ID3算法中,决策节点属性的选择运用了信息论中的熵概念作为启发式函数。在这种属性选择方法中,选择具有最大信息增益〔informationgain的属性作为当前划分节点。通过这种方式选择的节点属性可以保证决策树具有最小的分枝数量,使得到的决策树冗余最小。公式1：设数据划分D为类标记的元组的训练集。假定类标号属性具有M个不同值,定义m个不同的类Ci〔I＝1,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〔DID3算法大概的流程就是在属性集A中寻找信息增益值最大的属性,作为根节点,按照根节点属性的取值将样本集合分成几个子集,将此属性从属性集中去掉,在每个子集中选择信息增益值最大的属性,作为当前子集的根节点,上层集合的根节点的子节点,如此循环递归,如果得到的子集中所有的样本属于一个类别,则递归停止。ID3算法对数据的要求：eq\o\ac<○,1>所有属性必须为离散量；eq\o\ac<○,2>所有的训练例的所有属性必须有一个明确的值；eq\o\ac<○,3>相同的因素必须得到相同的结论且训练例必须唯一。实例：假如有一个网球爱好者,天气状况〔天气、温度、湿度、风力是决定他是否去打球的重要因素,利用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算法进行了改进：eq\o\ac<○,1>用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足；eq\o\ac<○,2>在树构造过程中进行剪枝；eq\o\ac<○,3>能够完成对连续属性的离散化处理；eq\o\ac<○,4>能够对不完整数据进行处理。C4.5算法的优点：产生的分类规则易于理解,准确率较高。C4.5算法的缺点：在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。此外,C4.5只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。分类决策树算法：C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法。分类决策树算法是从大量事例中进行提取分类规则的自上而下的决策树。四、实现在VisualStudio2013中C++语言ID3算法实现决策树：代码：#include<iostream>#include<list>#include<cstring>#include<string>#include<vector>#include<map>#include<sstream>#include<iomanip>#include<cmath>#include<fstream>#include<algorithm>#include<set>#include<queue>usingnamespacestd;classID3{ classNode { public: stringvalue; boolisLeaf; map<string,Node*>map; public: Node<>:value<"">,isLeaf<false> { } };private: vector<string>attribute; // vector<vector<string>>attributevalue; vector<vector<string>>data; intdecatt; Node*root;public: ID3<> { //从文件中加载数据 ifstreamfin<"C:\\Users\\Administrator\\Desktop\\playData.txt">; stringline,str; getline<fin,line>;//readalinefromtheinput"fin"to"line" istringstreamistring<line>;//bindto"istring"tothe"line"weread while<!istring.eof<>> { istring>>str;//readawordfromline attribute.push_back<str>; } while<!fin.eof<>> { getline<fin,line>; vector<string>vecStr; istringstreamistring<line>; while<!istring.eof<>> { istring>>str; vecStr.push_back<str>; } data.push_back<vecStr>; } fin.close<>; } voidrun<> { setDec<4>; vector<int>subSet; for<inti=0;i<data.size<>;i++> { subSet.push_back<i>; } vector<int>candidateAtt; for<inti=0;i<attribute.size<>;i++> { if<i!=decatt> { candidateAtt.push_back<i>; } } Node*tree=buildDT<subSet,candidateAtt>; //输出树结构 root=tree; vector<string>s; printTreeDepth<root,s>; } voidsetDec<intn> { if<n<0||n>=attribute.size<>> { cout<<"指定决策树变量错误!"<<endl; exit<0>; } decatt=n; } doublegetEntropy<vector<int>subSet>//获得子集信息熵 { doubleentropy=0; doublep,n; p=n=0; vector<string>vec; for<inti=0;i<subSet.size<>;i++> { if<data[subSet[i]][decatt]=="yes"> p++; else n++; } //判断属于同一类,熵为零的情况 if<0==p||0==n> return0; doublepR=p/<p+n>,nR=n/<p+n>; entropy=-pR*<log<pR>/log<2.0>>-nR*<log<nR>/log<2.0>>; returnentropy; } boolisPure<vector<int>subset> { stringvalue=data[subset[0]][decatt]; for<inti=1;i<subset.size<>;i++> { if<data[subset[i]][decatt]!=value> { returnfalse; } } returntrue; } doublegain<vector<int>subset,intindex>//返回以index为节点的信息增益 { //统计正例个数和范例个数 doubleentropy=getEntropy<subset>; doublesum=0; //求可能的所有属性值 map<string,vector<int>>mapSub; for<inti=0;i<subset.size<>;i++> { mapSub[data[subset[i]][index]].push_back<subset[i]>; } for<map<string,vector<int>>::iteratoriter=mapSub.begin<>; iter!=mapSub.end<>;++iter> { doublett=<iter->second.size<>/<double>subset.size<>>*getEntropy<iter->second>; //cout<<iter->first<<":"<<tt<<endl; sum+=tt; } returnentropy-sum; } //suSet指子集,value:属性值attribute:候选属性tree:根节点指针的指针 Node*buildDT<vector<int>subSet,vector<int>attr> { Node*p=newNode<>; if<isPure<subSet>> { p->isLeaf=true; p->value=data[subSet[0]][decatt]; /*if<*tree!=NULL> { <*tree>->map[value]=p; } else { <*tree>=p; }*/ returnp; } if<attr.size<>==0> { inty,n; y=n=0; for<inti=0;i<subSet.size<>;i++> { if<data[subSet[i]][decatt]=="yes"> { y++; } else n++; } if<y>=n> { p->isLeaf=true; p->value="yes"; } else { p->isLeaf=true; p->value="no"; } returnp; } //选择一个最优的属性 intbest=0; doubledmax=0; intbestIndex=0; for<inti=0;i<attr.size<>;i++> { doubledd=gain<subSet,attr[i]>; if<dd>dmax> { dmax=dd; best=attr[i]; bestIndex=i; } } //获得这个属性的所有属性值和其所对应的子集 map<string,vector<int>>mapAttValue; for<inti=0;i<subSet.size<>;i++> { mapAttValue[data[subSet[i]][best]].push_back<subSet[i]>; } attr.erase<attr.begin<>+bestIndex>;// p->value=this->attribute[best]; for<map<string,vector<int>>::iteratoriter=mapAttValue.begin<>; iter!=mapAttValue.end<>;++iter> { p->map[iter->first]=buildDT<iter->second,attr>; } //遍历每个属性值被选择后的子集,递归的创建树 returnp; }private: voidspace<intn> { for<inti=0;i<n;i++> cout<<""; }public: //输出从根节点到叶子节点的所有路径 voidprintTree<> { Node*t=root; queue<Node*>que; que.push<t>; Node*q=t,*p; while<!que.empty<>> { p=que.front<>; que.pop<>; cout<<setw<10><<p->value; boolflag=false; if<p==q> { cout<<endl; flag=true; } for<map<string,Node*>::iteratoriter=p->map.begin<>; iter!=p->map.end<>;++iter> { que.push<iter->second>; if<flag> { map<string,Node*>::iteratoriter1=iter; iter1++; if<iter1==p->map.end<>> { q=iter->second; flag=false; } } } } } voidprintTreeDepth<Node*t,vector<string>vec> { if<t->isLeaf> { for<inti=0;i<vec.size<>;i+=2> { if<i!=0> cout<<"->"; cout<<vec[i]<<":"<<vec[i+1]; } cout<<"->"<<t->value; cout<<endl; cout<<endl; } else { vec.push_back<t->value>; for<map<string,Node*>::iteratoriter=t->map.begin<>; iter!=t->map.end<>;++iter> { vec.push_back<iter->first>; printTreeDepth<iter->second,vec>; vec.pop_back<>; } } }};intmain<>{ ID3id3; id3.run<>; return0;}playData.txt中训练数据：outlook temperature humidity windy playsunny hot high FALSE nosunny hot high TRUE noovercast hot high FALSE yesrainy mild high FALSE yesrainy cool normal FALSE yesrainy cool normal TRUE noovercast cool normal TRUE yessunny mild high FALSE nosunny cool normal FALSE yesrainy mild normal FALSE yessunny mild normal TRUE yesovercast mild high TRUE yesovercast hot normal FALSE yesrainy mild high TRUE no结果：〔二概念学习一、定义及一些描述1.定义：概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。通俗的说,就是给定一个样例集合以及每个样例是否属于某个概念的标注,怎样推断出该概念的一般定义。又称从样例中逼近布尔函数。2.概念学习任务的描述：任何概念学习任务能被描述为：实例的集合、实例集合上的目标函数、候选假设的集合以及训练样例的集合。具体以EnjoySport为例,如图表2-1：表2-1目标概念EnjoySport的训练样例No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes那么EnjoySport学习任务可以描述为：已知：实例集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的实例被称为正例〔positiveexample,c<x>=0的实例为反例〔negativeexample,经常用序偶<x,c<x>>来描述训练样例。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上定义的布尔函数,称hjmore_general_than_or_equal_tohk〔记做hj≥ghk,当且仅当<∨x∈X>[<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-ELIMINATIONFIND-S输出的假设只是H中能够拟合训练样例的多个假设中的一个。而在候选消除算法中,输出的是与训练样例一致的所有假设的集合,且候选消除算法在描述这一集合时不需要明确列举所有成员,利用more_general_than偏序结构,可以维护一个一致假设集合的简洁表示1.几个定义一致：一个假设h与训练样例集合D一致,当且仅当对D中每一个样例<x,c<x>>都有h<x>=c<x>。Consistent<h,D>≡<∨<x,c<x>>∈D>h<x>=c<x>变型空间:关于假设空间H和训练样例集D的变型空间,标记为VSH,D,是H中与训练样例D一致的所有假设构成的子集。VSH,D≡{h∈H|Consistent<h,D>}2.列表后消除算法〔LIST-THEN-ELIMINATE描述〔1变型空间VersionSpace<-包含H中所有假设的列表〔2对每个训练样例<x,c<x>>,从变型空间中移除所有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集合,我们需要剔除<?,?,?,?,?,same>},过程为：在处理完了这四个样本后,我们就可以获取所有的假设：当前为6个假设,当我们可以获取到更多的训练集的时候,我们可以划出更小的设计空间。六、实现在VisualStudio2013中实现：//bianxingspace.cpp#pragmawarning<disable:4996>#include<list>usingnamespacestd;#defineA_CHAR_MAX16#defineA_VALUE_MAX16#defineA_NUM_MAX32#defineSAMPLES_MAX256#defineALL-1#defineNUL-2#defineYES1#defineNO0#defineNUKOWN-1//属性structAttribute{charname[A_CHAR_MAX];//属性名称intnum;//属性值个数charatt[A_VALUE_MAX][A_CHAR_MAX];//属性值};//假设structHypothesis{intnum;//属性个数Attributean[A_NUM_MAX];//属性集合};//假设值structHypoValue{intvalue[A_NUM_MAX];};//样本structSample{HypoValueev;//假设intresult;//正例/反例};Hypothesisg_Hypo;//假设集合Sampleg_sa[SAMPLES_MAX];//样本空间intg_sn;//样本数list<HypoValue*>g_G;//一般边界Glist<HypoValue*>g_S;//特殊边界S//从文件中读取假设集合/*/文件格式[属性个数n][属性名称1][属性值个数][属性值1][属性值2][属性值3]……[属性名称2][属性值个数][属性值1][属性值2][属性值3]…………[属性名称n][属性值个数][属性值1][属性值2][属性值3]……/*/boolReadHypothesis<constchar*filename>{FILE*file;if<fopen_s<&file,filename,"r">>returnfalse;inti,j,k;fscanf<file,"%d\n",&g_Hypo.num>;for<i=0;i<g_Hypo.num;i++>{fscanf<file,"%s%d",g_Hypo.an[i].name,&k>;g_Hypo.an[i].num=k;for<j=0;j<k;j++>{fscanf<file,"%s",g_Hypo.an[i].att[j]>;}fscanf<file,"\n">;}fclose<file>;returntrue;}//从文件中读取样本/*/文件格式[样本个数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〔反例]/*/boolReadSamples<constchar*filename>{FILE*file;if<fopen_s<&file,filename,"r">>returnfalse;inti,j;fscanf<file,"%d\n",&g_sn>;for<i=0;i<g_sn;i++>{for<j=0;j<g_Hypo.num;j++>{fscanf<file,"%d",&g_sa[i].ev.value[j]>;}fscanf<file,"%d\n",&g_sa[i].result>;}fclose<file>;returntrue;}//初始化G和SvoidInitGandS<>{HypoValue*evg=newHypoValue<>;HypoValue*evs=newHypoValue<>;for<inti=0;i<g_Hypo.num;i++>{evg->value[i]=ALL;evs->value[i]=NUL;}g_G.push_back<evg>;g_S.push_back<evs>;}//正例ps与假设h是否一致boolPositiveisConsistent<HypoValueh,HypoValueps>{for<inti=0;i<g_Hypo.num;i++>{if<h.value[i]==ALL>continue;elseif<h.value[i]!=ps.value[i]>returnfalse;}returntrue;}//反例ns与假设h是否一致boolNegativeisConsistent<HypoValueh,HypoValuens>{for<inti=0;i<g_Hypo.num;i++>{if<h.value[i]!=ALL&&h.value[i]!=ns.value[i]>returntrue;}returnfalse;}//G的某个成员是否比h更一般boolGMemberMoreGeneral<HypoValueh>{inti;list<HypoValue*>::iteratorit;HypoValuemem;for<it=g_G.begin<>;it!=g_G.end<>;it++>{mem=**it;for<i=0;i<g_Hypo.num;i++>{if<mem.value[i]==h.value[i]>continue;elseif<mem.value[i]==ALL||h.value[i]==NUL>continue;elsebreak;}if<i==g_Hypo.num>returntrue;}returnfalse;}//把s的所有的极小泛化式h加入到S中,并且满足h与d一致,而且G的某个成员比h更一般voidMiniGeneral<HypoValues,HypoValued>{HypoValue*h=newHypoValue<>;for<inti=0;i<g_Hypo.num;i++>{if<s.value[i]!=NUL&&s.value[i]!=d.value[i]>h->value[i]=ALL;elseh->value[i]=d.value[i];}if<GMemberMoreGeneral<*h>>g_S.push_front<h>;elsedeleteh;}//从S中移去所有这样的假设：它比S中另一个假设更一般voidRemoveMoreGeneralFromS<>{boolr1,r2;inti;HypoValuee1,e2;list<HypoValue*>::iteratorit;list<HypoValue*>::iteratornext;list<HypoValue*>::iteratortemp;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;i<g_Hypo.num;i++>{//if<e1.value[i]==ALL&&e2.value[i]==ALL>//continue;//else if<e1.value[i]==e2.value[i]>continue;elseif<e1.value[i]==ALL>{r1=true;if<r2>break;}elseif<e2.value[i]==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>;}elseit++;}}//S的某个成员是否比h更特殊boolSMemberMoreSpecial<HypoValueh>{inti;list<HypoValue*>::iteratorit;HypoValuemem;for<it=g_S.begin<>;it!=g_S.end<>;it++>{mem=**it;for<i=0;i<g_Hypo.num;i++>{if<mem.value[i]==h.value[i]>continue;elseif<mem.value[i]==NUL||h.value[i]==ALL>continue;elsebreak;}if<i==g_Hypo.num>returntrue;}returnfalse;}//把g的所有的极小特殊化式h加入到G中,其中h满足h与d一致,而且S的某个成员比h更特殊voidMiniSpecial<HypoValueg,HypoValued>{inti,j;for<i=0;i<g_Hypo.num;i++>{for<j=1;j<=g_Hypo.an[i].num;j++>{if<j!=d.value[i]>{HypoValue*h=newHypoValue<g>;h->value[i]=j;if<SMemberMoreSpecial<*h>>g_G.push_front<h>;elsedeleteh;}}}}//从G中移去所有这样的假设：它比G中另一个假设更特殊voidRemoveMoreSpecialFromG<>{boolr1,r2;inti;HypoValuee1,e2;list<HypoValue*>::iteratorit;list<HypoValue*>::iteratornext;list<HypoValue*>::iteratortemp;for<it=g_G.begin<>;it!=g_G.end<>;>{e1=**it;next=it;r1=r2=false;for<next++;next!=g_G.end<>;>{e2=**next;r1=r2=false;for<i=0;i<g_Hypo.num;i++>{if<e1.value[i]==e2.value[i]>continue;elseif<e2.value[i]==ALL>{r1=true;if<r2>break;}elseif<e1.value[i]==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_G.remove<*temp>;}else//两者没有谁比谁更特殊的关系next++;}if<r1==true&&r2==false>//it比next更特殊{temp=it;it++;g_G.remove<*temp>;}elseit++;}}//主函数intmain<intarc,char**argv>{//读取假设和样本if<!ReadHypothesis<"hypothesis.txt">>{printf<"readHypothesisfileerror">;return0;}if<!ReadSamples<"samples.txt">>{printf<"readsamplesfileerror">;return0;}//初始化G和SInitGandS<>;list<HypoValue*>::iteratorit;list<HypoValue*>::iteratortemp;inti;for<i=0;i<g_sn;i++>{if<g_sa[i].result==YES>//正例时{//从G中移去所有与d不一致的假设for<it=g_G.begin<>;it!=g_G.end<>;>{if<!PositiveisConsistent<**it,g_sa[i].ev>>{temp=it;it++;g_G.remove<*temp>;} else it++;}//对S中每个与d不一致的假设sfor<it=g_S.begin<>;it!=g_S.end<>;>{if<!PositiveisConsistent<**it,g_sa[i].ev>>{MiniGeneral<**it,g_sa[i].ev>;temp=it;it++;g_S.remove<*temp>;//从S中移去sRemoveMoreGeneralFromS<>;}elseit++;}}else//反例时{//从S中移去所有与d不一致的假设for<it=g_S.begin<>;it!=g_S.end<>;>{if<!NegativeisConsistent<**it,g_sa[i].ev>>{temp=it;it++;g_S.remove<*temp>;} else it++;}//对G中每个与d不一致的假设gfor<it=g_G.begin<>;it!=g_G.end<>;>{if<!NegativeisConsistent<**it,g_sa[i].ev>>{MiniSpecial<**it,g_sa[i].ev>;temp=it;it++;g_G.remove<*temp>;//从G中移去gRemoveMoreSpecialFromG<>;}elseit++;}}}//输出Sprintf<"特殊边界S：\n">;for<it=g_S.begin<>;it!=g_S.end<>;it++>{HypoValues=**it;printf<"<">;for<i=0;i<g_Hypo.num-1;i++>{if<s.value[i]==ALL>printf<"?,">;elseif<s.value[i]==NUL>printf<"O,">;elseprintf<"%s,",g_Hypo.an[i].att[s.value[i]-1]>;}if<s.value[i]==ALL>printf<"?>\n">;elseif<s.value[i]==NUL>printf<"O>\n">;elseprintf<"%s>\n",g_Hypo.an[i].att[s.value[i]-1]>;}//输出Gprintf<"一般边界G：\n">;for<it=g_G.begin<>;it!=g_G.end<>;it++>{HypoValues=**it;printf<"<">;for<i=0;i<g_Hypo.num-1;i++>{if<s.value[i]==ALL>printf<"?,">;elseif<s.value[i]==NUL>printf<"O,">;elseprintf<"%s,",g_Hypo.an[i].att[s.value[i]-1]>;}if<s.value[i]==ALL>printf<"?>\n">;elseif<s.value[i]==NUL>printf<"O>\n">;elseprintf<"%s>\n",g_Hypo.an[i].att[s.value[i]-1]>;}//释放空间g_S.erase<g_S.begin<>,g_S.end<>>;g_G.erase<g_G.begin<>,g_G.end<>>;getchar<>;return0;}〔三BP神经网络一、介绍BP神经网络是一种多层前馈神经网络,该网络的主要特点是信号前向传递,误差反向传播。在前向传递中,输入信号从输入层经隐含层逐层处理,直至输出层。每一层的神经元状态只影响下一层神经元状态。如果输出层得不到期望输出,则转入反向传播,根据预测误差调整网络权值和阈值,从而使BP神经网络预测输出不断逼近期望输出。BP神经网络的拓扑结构如图1.1所示。图3.1BP神经网络拓扑结构图图3.1中,,……是BP神经网络的输入值,,……是BP神经的预测值,和为BP神经网络权值。从图3.1可以看出,BP神经网络可以看成一个非线性函数,网络输入值和预测值分别为该函数的自变量和因变量。当输入节点数为n,输出节点数为m时,BP神经网络就表达了从n个自变量到m个因变量的函数映射关系。二、设计步骤BP神经网络预测前首先要训练网络,通过训练使网络具有联想记忆和预测能力。BP神经网络的训练过程包括以下几个步骤。步骤1:网络初始化。根据系统输入输出序列<x,y>确定网络输入层节点数n、隐含层节点数l,输出层节点数m,初始化输入层、隐含层和输出层神经元之间的连接权值和,初始化隐含层阈值,输出层阈值,给定学习速率和神经元激励函数。步骤2:隐含层输出计算。根据输入向量x,输入层和隐含层间连接权值以及隐含层阈值a,计算隐含层输出H。式中,l为隐含层节点数;f为隐含层激励函数,该函数有多种表达形式,本章所选函数为:步骤3:输出层输出计算。根据隐含层输出,连接权值和阈值,计算BP神经网络预测输出。步骤4:误差计算。根据网络预测输出和期望输出,计算网络预测误差。步骤5:权值更新。根据网络预测误差更新网络连接权值,。式中,为学习速率。步骤6:阈值更新。根据网络预测误差更新网络节点阈值,。步骤7:判断算法迭代是否结束,若没有结束,返回步骤2。三、MATLAB实现根据BP神经网络理论,在MATLAB软件中编程实现基于BP算法的多层前馈网在催化剂配方中的建模。1、归一化方法及MATLAB函数数据归一化方法是神经网络预测前对数据常做的一种处理方法。数据归一化处理把所有数据都转化为绝对值为之间的数,其目的是取消各维数据间数量级差别,避免因为输入输出数据数量级差别较大而造成网络预测误差较大。数据归一化的方法主要有以下两种。1>最大最小法。函数形式如下:式中,为数据序列中的最小数;为序列中的最大数。2>平均数方差法,函数形式如下:式中,为数据序列的均值;为数据的方差。本案例采用第二种数据归一化方法,归一化函数采用MATLAB自带函数premnmx,该函数有多种形式,常用的方法如下。input_train,output_train是训练输入、输出原始数据,input_train1,output_train1是归一化后的数据。minp,maxp,mint,maxt为数据归一化后得到的结构体,里面包含了数据最大值、最小值和平均值等信息,可用于测试数据归一化和反归一化。测试数据归一化和反归一化程序如下。input_test是测试输入原始数据,input_test1是归一化后的数据。minp,maxp表示根据input_train的值对input_test进行归一化。outputp1是训练输出数据的归一化值,output是反归一化之后的网络预测输出,mint,maxt表示根据output_train对数据进行反归一化。2数据选择首先利用正交表安排实验,得到18组准确的实验数据分别作为神经网络的训练样本〔15组及测试样本〔3组,分别存储于input_train,output_train二维数组中。5维输入向量与配方组成因素相对应,3维输出向量与三个待优化指标：脂肪酸甲脂转化率TR%、脂肪醇产率YOH%和脂肪醇选择性SOH%相对应。input_train数组为5行15列,output_train数组为3行15列,并对训练数据进行归一化处理。3BP神经网络结构初始化根据数据特点确定BP神经网络的结构为5—4—3,随机初始化BP神经网络权值和阈值。4BP神经网络训练用训练数据训练BP神经网络,在训练过程中根据网络预测误差调整网络的权值和阈值。设定训练次数为10000,学习率为0.05,误差限为0.001。5结果分析用训练好的BP神经网络测试数据。BP神经网络误差如表3.1所示。从BP神经网络分类结果可以看出,基于BP神经网络的算法具有较高的准确性,能够较准确得到催化剂配方配比。表3.3BP神经网络训练结果误差实测值网络预测值相对误差实测值网络预测值相对误差实测值网络预测值相对误差186.1595.76090.111575.6567.93810.101986.5077.97770.0985277．1578.15350.013071.9067.55500.060491.80102.79180.1197396.0596.01750.000394.6067.65120.284898.00103.50100.0561〔四朴素贝叶斯分类贝叶斯分类是一类分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。我想通过实例讨论贝叶斯分类中最简单的一种：朴素贝叶斯分类。一.分类问题从数学角度来说,分类问题可做如下定义：已知集合：和,确定映射规则,使得任意有且仅有一个使得成立。〔不考虑模糊数学里的模糊集情况。其中C叫做类别集合,其中每一个元素是一个类别,而I叫做项集合,其中每一个元素是一个待分类项,f叫做分类器。分类算法的任务就是构造分类器f。这里要着重强调,分类问题往往采用经验性方法构造映射规则,即一般情况下的分类问题缺少足够的信息来构造100%正确的映射规则,而是通过对经验数据的学习从而实现一定概率意义上正确的分类,因此所训练出的分类器并不是一定能将每个待分类项准确映射到其分类,分类器的质量与分类器构造方法、待分类数据的特性以及训练样本数量等诸多因素有关。例如,医生对病人进行诊断就是一个典型的分类过程,任何一个医生都无法直接看到病人的病情,只能观察病人表现出的症状和各种化验检测数据来推断病情,这时医生就好比一个分类器,而这个医生诊断的准确率,与他当初受到的教育方式〔构造方法、病人的症状是否突出〔待分类数据的特性以及医生的经验多少〔训练样本数量都有密切关系。二.贝叶斯分类的基础—贝叶斯定理贝叶斯定理：贝叶斯定理之所以有用,是因为我们在生活中经常遇到这种情况：我们可以很容易直接得出P<A|B>,P<B|A>则很难直接得出,但我们更关心P<B|A>,贝叶斯定理就为我们打通从P<A|B>获得P<B|A>的道路。三.朴素贝叶斯的原理和流程朴素贝叶斯分类是一种十分简单的分类算法,叫它朴素贝叶斯分类是因为这种方法的思想真的很朴素,朴素贝叶斯的思想基础是这样的：对于给出的待分类项,求解在此项出现的条件下各个类别出现的概率,哪个最大,就认为此待分类项属于哪个类别,这就是朴素贝叶斯的思想基础。朴素贝叶斯分类或简单贝叶斯分类的工作过程如下：1.每个数据样本用一个n维特征向量表示,分别描述对n个属性A