机器学习(Machine Learning, ML)是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。它是人工智能的核心，是使计算机具有智能的根本途径，其应用遍及人工智能的各个领域，它主要使用归纳、综合而不是演绎。候选消除学习算法将G集合初始化为H中极大一般假设将S集合初始化为H中极大特殊假设对每个训练例d，进行以下操作：如果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中另一假设更特殊初始化S边界,G边界：已知：实例集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)训练样例：1.Sunny,Warm,Normal,Strong,Warm,Same,EnjoySport=Yes2.Sunny,Warm,High,Strong,Warm,Same,EnjoySport=Yes3.Rainy,Cold,High,Strong,Warm,Change,EnjoySport=No4.Sunny,Warm,High,Storage,Cool,Change,EnjoySport=Yes工具/原料moreDevc++方法/步骤1/6分步阅读

数据结构定义：

#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 Attribute

{

char name; // 属性名称

int num; // 属性值个数

char att; // 属性值

};

// 假设

struct Hypothesis

{

int num; // 属性个数

Attribute an; // 属性集合

};

// 假设值

struct HypoValue

{

int value;

};

// 样本

struct Sample

{

HypoValue ev; // 假设

int result; // 正例/反例

};

Hypothesis g_Hypo; // 假设集合

Sample g_sa; // 样本空间

int g_sn; // 样本数

listHypoValue* g_G; // 一般边界G

listHypoValue* g_S; // 特殊边界S

2/6

读文件和进行样例对G边界进行特殊化，S边界进行一般化：

3/6

打印输出函数如下：

void printdata(listHypoValue* g_S,listHypoValue* g_G,int i)

{

int j,k;

listHypoValue*::iterator it;

if(i==-3)

printf("最终的特殊边界S集合有%d个极小一般化成员为：\n",g_S.size());

else

printf("第%d样例使特殊边界S一般化后的集合有%d个极小一般化成员为：\n",i+1,g_S.size());

for (it=g_S.begin(); it!=g_S.end(); it++)

{

HypoValue s = **it;

printf("");

for (j=0; jg_Hypo.num-1; j++)

{

if (s.value==ALL)

printf("?, ");

else if (s.value==NUL)

printf("O, ");

else

printf("%s, ", g_Hypo.an.att-1]);

}

if (s.value==ALL)

printf("?\n");

else if (s.value==NUL)

printf("O\n");

else

printf("%s\n", g_Hypo.an.att-1]);

}

//printf("特殊边界G：%d\n",g_G.size());

// 输出G

if(i==-3)

printf("最终的一般边界G集合有%d个极小特殊化成员为：\n",g_G.size());

else

printf("第%d样例使特殊边界G特殊化后的集合有%d个极小特殊化成员为：\n",i+1,g_G.size());

for (it=g_G.begin(); it!=g_G.end(); it++)

{

HypoValue s = **it;

printf("");

for (k=0; kg_Hypo.num-1; k++)

{

if (s.value==ALL)

printf("?, ");

else if (s.value==NUL)

printf("O, ");

else

printf("%s, ", g_Hypo.an.att-1]);

}

if (s.value==ALL)

printf("?\n");

else if (s.value==NUL)

printf("O\n");

else

printf("%s\n", g_Hypo.an.att-1]);

}

4/6

运行输出的每一次样例一般化S边界与特殊化G边界的结果集合，和最终的一般化S边界与特殊化G边界的结果集合：

第1样例使特殊边界S一般化后的集合有1个极小一般化成员为：

sunny, warm, normal,strong, warm, same

第1样例使特殊边界G特殊化后的集合有1个极小特殊化成员为：

?, ?, ?, ?, ?, ?

第2样例使特殊边界S一般化后的集合有1个极小一般化成员为：

sunny, warm, ?,strong, warm, same

第2样例使特殊边界G特殊化后的集合有1个极小特殊化成员为：

?, ?, ?, ?, ?, ?

第3样例使特殊边界S一般化后的集合有1个极小一般化成员为：

sunny, warm, ?,strong, warm, same

第3样例使特殊边界G特殊化后的集合有3个极小特殊化成员为：

?, ?, ?, ?, ?,same

?, warm, ?, ?, ?,?

sunny, ?, ?, ?, ?,?

第4样例使特殊边界S一般化后的集合有1个极小一般化成员为：

sunny, warm, ?,strong, ?, ?

第4样例使特殊边界G特殊化后的集合有2个极小特殊化成员为：

?, warm, ?, ?, ?,?

sunny, ?, ?, ?, ?,?

最终的特殊边界S集合有1个极小一般化成员为：

sunny, warm, ?,strong, ?, ?

最终的一般边界G集合有2个极小特殊化成员为：

?, warm, ?, ?, ?,?

sunny, ?, ?, ?, ?,?

请按任意键继续. . .

5/6

hypothesis.txt与samples.txt文件中的内容如下：

hypothesis.txt

6

sky 3 sunny rainy cloudy

airtemp 2 warm cold

humidity 2 normal high

wind 2 strong weak

water 2 warm cool

forecast 2 same change

// 从文件中读取假设集合

/*/ 文件格式

……

……

……

……

/*/

samples.txt

4

1 1 1 1 1 1 1

1 1 2 1 1 1 1

2 2 2 1 1 2 0

1 1 2 1 2 2 1

// 从文件中读取样本

/*/ 文件格式

……

……

……

……

/*/

6/6

附完整代码如下：

#include iostream

#include string

#include list

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 Attribute

{

char name; // 属性名称

int num; // 属性值个数

char att; // 属性值

};

// 假设

struct Hypothesis

{

int num; // 属性个数

Attribute an; // 属性集合

};

// 假设值

struct HypoValue

{

int value;

};

// 样本

struct Sample

{

HypoValue ev; // 假设

int result; // 正例/反例

};

Hypothesis g_Hypo; // 假设集合

Sample g_sa; // 样本空间

int g_sn; // 样本数

listHypoValue* g_G; // 一般边界G

listHypoValue* g_S; // 特殊边界S

bool ReadHypothesis(const char* filename)

{

FILE* file;

if (!(file=fopen(filename , "r")))

return false;

int i,j,k;

fscanf(file, "%d\n", g_Hypo.num);

for (i=0; ig_Hypo.num ; i++)

{

fscanf(file, "%s%d\n", g_Hypo.an.name, k);

g_Hypo.an.num = k;

for (j=0; jk; j++)

{

fscanf(file, "%s", g_Hypo.an.att);

}/*1wangxiaobo@163.com*/

fscanf(file, "\n");

}

fclose(file);

return true;

}

bool ReadSamples(const char* filename)

{

FILE* file;

if (!(file=fopen(filename , "r")))

return false;

int i,j;

fscanf(file, "%d\n", g_sn);

for (i=0; ig_sn ; i++)

{/*1wangxiaobo@163.com*/

for (j=0; jg_Hypo.num; j++)

{

fscanf(file, "%d", g_sa.ev.value);

}

fscanf(file, "%d\n",g_sa.result);

}

fclose(file);

return true;

}

// 初始化G和S

void InitGandS()

{

HypoValue* evg = new HypoValue();

HypoValue* evs = new HypoValue();

for (int i=0; ig_Hypo.num; i++)

{

evg-value = ALL; // 一般边界G

evs-value = NUL; // 特殊边界S

}

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.value==ALL)

continue;

else if (h.value!=ps.value)

return false;

}

return true;

}/*1wangxiaobo@163.com*/

// 反例ns与假设h是否一致

bool NagativeisConsistent(HypoValue h, HypoValue ns)

{

for (int i=0; ig_Hypo.num; i++)

{

if (h.value!=ALL h.value!=ns.value)

return true;/*1wangxiaobo@163.com*/

}

return false;

}

// G的某个成员是否比h更一般

bool GMemberMoreGeneral(HypoValue h)

{

int i;

listHypoValue*::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.value==ALL h.value==ALL)

continue;

else if (mem.value==h.value)

continue;

else if (mem.value!=ALL h.value==ALL)

break;/*1wangxiaobo@163.com*/

else if (mem.value==ALL h.value!=ALL)

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; /*1wangxiaobo@163.com*/ ig_Hypo.num; i++)

{

if (s.value==NUL)

h-value = d.value;

else if (s.value==ALL)

h-value = ALL;

else if (s.value!=d.value)

h-value = ALL;

else

h-value = d.value;

}

if (GMemberMoreGeneral(*h))// G的某个成员是否比h更一般

g_S.push_front(h);

else

delete h;

}

// 从S中移去所有这样的假设：它比S中另一个假设更一般

void RemoveMoreGeneralFromS()

{

bool r1,r2;

int i;

HypoValue e1, e2;

listHypoValue*::iterator it;

listHypoValue*::iterator next;

listHypoValue*::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; /*1wangxiaobo@163.com*/ ig_Hypo.num; i++)

{

if (e1.value==ALL e2.value==ALL)

continue;

else if (e1.value==e2.value)

continue;

else if (e1.value==ALL e2.value!=ALL)

{

r1 = true;

if (r2) break;

}

else if (e1.value!=ALL e2.value==ALL)

{

r2 = true;

if (r1) break;

}

else

{

r1 = r2 = true;

break;

}

}

if (r1==true r2==false)

break;

if (r1==false)

{

temp = next;

next++;

g_S.remove(*temp);

}

else

next++;

}

if (r1==true /*1wangxiaobo@163.com*/ r2==false)

{

temp = it;

it++;

g_S.remove(*temp);

}

else

it++;

}

}

// S的某个成员是否比h更特殊

bool SMemberMoreSpecial(HypoValue h)

{

int i;

listHypoValue*::iterator it;

HypoValue mem;

for (it=g_S.begin(); it!=g_S.end(); it++)

{

mem = **it;

for (i=0; ig_Hypo.num; i++)

{

if (mem.value==ALL h.value==ALL)

continue;

else if (mem.value==h.value)

continue;

else if (mem.value!=ALL h.value==ALL)

continue;

else if (mem.value==ALL h.value!=ALL)

break;

else

break;

}

if (i==g_Hypo.num)

return true;

}

return false;

}

// 把g的所有的极小特殊化式h加入到G中，其中h满足h与d一致，而且S的某个成员比h更特殊

void MiniSpecial(HypoValue g, HypoValue d)

{

int i,j;

for (i=0; ig_Hypo.num; i++)

{

for (j=1; j=g_Hypo.an.num; j++)

{

if (j!=d.value)

{

HypoValue* h = new HypoValue(g);

h-value = j;

if (SMemberMoreSpecial(*h))/*1wangxiaobo@163.com*/

g_G.push_front(h);

else

delete h;

}

}

}

}

// 从G中移去所有这样的假设：它比G中另一个假设更特殊

void RemoveMoreSpecialFromG()

{

bool r1,r2;

int i;

HypoValue e1, e2;

listHypoValue*::iterator it;

listHypoValue*::iterator next;

listHypoValue*::iterator temp;

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; ig_Hypo.num; i++)

{

if (e1.value==ALL e2.value==ALL)

continue;

else if (e1.value==e2.value)/*1wangxiaobo@163.com*/

continue;

else if (e1.value!=ALL e2.value==ALL)

{

r1 = true;

if (r2) break;

}

else if (e1.value==ALL e2.value!=ALL)

{

r2 = true;

if (r1) break;

}

else

{

r1 = r2 = true;

break;

}

}

if (r1==true r2==false)

break;

if (r1==false)/*1wangxiaobo@163.com*/

{

temp = next;

next++;

g_G.remove(*temp);

}

else

next++;

}

if (r1==true r2==false)

{

temp = it;

it++;

g_G.remove(*temp);

}

else

it++;

}

}

void printdata(listHypoValue* g_S,listHypoValue* g_G,int i)

{/*1wangxiaobo@163.com*/

int j,k;

listHypoValue*::iterator it;

if(i==-3)

printf("最终的特殊边界S集合有%d个极小一般化成员为：\n",g_S.size());

else

printf("第%d样例使特殊边界S一般化后的集合有%d个极小一般化成员为：\n",i+1,g_S.size());

for (it=g_S.begin(); it!=g_S.end(); it++)

{

HypoValue s = **it;

printf("");

for (j=0; jg_Hypo.num-1; j++)

{

if (s.value==ALL)

printf("?, ");

else if (s.value==NUL)

printf("O, ");

else

printf("%s, ", g_Hypo.an.att-1]);

}/*1wangxiaobo@163.com*/

if (s.value==ALL)

printf("?\n");

else if (s.value==NUL)

printf("O\n");

else

printf("%s\n", g_Hypo.an.att-1]);

}

//printf("特殊边界G：%d\n",g_G.size());

// 输出G

if(i==-3)

printf("最终的一般边界G集合有%d个极小特殊化成员为：\n",g_G.size());

else

printf("第%d样例使特殊边界G特殊化后的集合有%d个极小特殊化成员为：\n",i+1,g_G.size());

for (it=g_G.begin(); it!=g_G.end(); it++)

{

HypoValue s = **it;/*1wangxiaobo@163.com*/

printf("");

for (k=0; kg_Hypo.num-1; k++)

{

if (s.value==ALL)

printf("?, ");

else if (s.value==NUL)

printf("O, ");

else

printf("%s, ", g_Hypo.an.att-1]);

}

if (s.value==ALL)

printf("?\n");

else if (s.value==NUL)

printf("O\n");

else

printf("%s\n", g_Hypo.an.att-1]);

}

}

// 主函数

int main(int arc, char** argv)/*1wangxiaobo@163.com*/

{

system("title 晓博List-Then-Eliminate试验程序");

printf("Designed by wangxiaobo email:1wangxiaobo@163.com");

// 读取假设和样本

if (!ReadHypothesis("hypothesis.txt"))

{

printf("read Hypothesis file error");

return 0;

}

if (!ReadSamples("samples.txt"))

{

printf("read samples file error");

return 0;

}

// 初始化G和S

InitGandS();

listHypoValue*::iterator it;/*1wangxiaobo@163.com*/

listHypoValue*::iterator temp;

int i,j,k;

for (i=0; ig_sn; i++)

{

if (g_sa.result==YES) // 正例时

{

// 从G中移去所有与d不一致的假设

for (it=g_G.begin(); it!=g_G.end(); it++)

{

if (!PositiveisConsistent(**it, g_sa.ev))

{

temp = it;

it++;

g_G.remove(*temp);/*1wangxiaobo@163.com*/

}

}

// 对S中每个与d不一致的假设s

for (it=g_S.begin(); it!=g_S.end();)

{

if (!PositiveisConsistent(**it, g_sa.ev))

{

MiniGeneral(**it, g_sa.ev);

temp = it;

it++;

g_S.remove(*temp); // 从S中移去s

RemoveMoreGeneralFromS();

}/*1wangxiaobo@163.com*/

else

it++;

}

}

else // 反例时

{

// 从S中移去所有与d不一致的假设

for (it=g_S.begin(); it!=g_S.end(); it++)

{

if (!NagativeisConsistent(**it, g_sa.ev))

{

temp = it;

it++;

g_S.remove(*temp);

}

}

// 对G中每个与d不一致的假设g

for (it=g_G.begin(); it!=g_G.end();)

{

if (!NagativeisConsistent(**it, g_sa.ev))/*1wangxiaobo@163.com*/

{

MiniSpecial(**it, g_sa.ev);

temp = it;/*1wangxiaobo@163.com*/

it++;

g_G.remove(*temp); /*1wangxiaobo@163.com*/ // 从G中移去g

RemoveMoreSpecialFromG();/*1wangxiaobo@163.com*/

}

else

it++;

}

}

//.........................................................................

//printf("特殊边界S：%d\n",g_S.size());

printdata(g_S,g_G,i);

//....................................................................

}

// 最终输出

printdata(g_S,g_G,-3);//用于选择输出dos屏幕

// 释放空间

g_S.erase(g_S.begin(), g_S.end());/*1wangxiaobo@163.com*/

g_G.erase(g_G.begin(), g_G.end());

system("pause");

return 0;

}

算法消除