首页 美食营养 游戏数码 手工爱好 生活家居 健康养生 运动户外 职场理财 情感交际 母婴教育 时尚美容 知识问答

机器学习算法实现：[1]候选消除学习算法

2025-10-05 10:46:27

1、数据结构定义：

#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[A_CHAR_MAX];             // 属性名称

int num;                           // 属性值个数

char att[A_VALUE_MAX][A_CHAR_MAX]; // 属性值

};

// 假设

struct Hypothesis

{

int num;                          // 属性个数

Attribute an[A_NUM_MAX];          // 属性集合

};

// 假设值

struct HypoValue

{

int value[A_NUM_MAX];

};

// 样本

struct Sample

{

HypoValue ev;                    // 假设

int result;                      // 正例/反例

};

Hypothesis g_Hypo;                   // 假设集合

Sample g_sa[SAMPLES_MAX];            // 样本空间

int g_sn;                            // 样本数

list<HypoValue*> g_G;                // 一般边界G

list<HypoValue*> g_S;                // 特殊边界S

机器学习算法实现：[1]候选消除学习算法

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

机器学习算法实现：[1]候选消除学习算法

机器学习算法实现：[1]候选消除学习算法

3、打印输出函数如下：

void printdata(list<HypoValue*> &g_S,list<HypoValue*> &g_G,int i)

{

  

     int j,k;

list<HypoValue*>::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; j<g_Hypo.num-1; j++)

   {

    if (s.value[j]==ALL)

     printf("?, ");

    else if (s.value[j]==NUL)

     printf("O, ");

    else

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

   }

   if (s.value[j]==ALL)

    printf("?>\n");

   else if (s.value[j]==NUL)

    printf("O>\n");

   else

    printf("%s>\n", g_Hypo.an[j].att[s.value[j]-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; k<g_Hypo.num-1; k++)

   {

    if (s.value[k]==ALL)

     printf("?, ");

    else if (s.value[k]==NUL)

     printf("O, ");

    else

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

   }

   if (s.value[k]==ALL)

    printf("?>\n");

   else if (s.value[k]==NUL)

    printf("O>\n");

   else

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

}   

    

4、运行输出的每一次样例一般化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, ?, ?, ?, ?,?>

请按任意键继续. . .

机器学习算法实现：[1]候选消除学习算法

5、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

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

/*/ 文件格式

[集合个数n]

[属性名称1] [属性值个数] [属性值1] [属性值2] [属性值3] ……

[属性名称2] [属性值个数] [属性值1] [属性值2] [属性值3] ……

……

[属性名称n] [属性值个数] [属性值1] [属性值2] [属性值3] ……

/*/

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

// 从文件中读取样本

/*/ 文件格式

[样本个数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（反例）]

/*/

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[A_CHAR_MAX];             // 属性名称

int num;                           // 属性值个数

char att[A_VALUE_MAX][A_CHAR_MAX]; // 属性值

};

// 假设

struct Hypothesis

{

int num;                          // 属性个数

Attribute an[A_NUM_MAX];          // 属性集合

};

// 假设值

struct HypoValue

{

int value[A_NUM_MAX];

};

// 样本

struct Sample

{

HypoValue ev;                    // 假设

int result;                      // 正例/反例

};

Hypothesis g_Hypo;                   // 假设集合

Sample g_sa[SAMPLES_MAX];            // 样本空间

int g_sn;                            // 样本数

list<HypoValue*> g_G;                // 一般边界G

list<HypoValue*> 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; i<g_Hypo.num ; i++)

{

   fscanf(file, "%s%d\n", 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]);

   }/*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; i<g_sn ; i++)

{/*1wangxiaobo@163.com*/  

   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);

return true;

}

// 初始化G和S

void InitGandS()

{

HypoValue* evg = new HypoValue();

HypoValue* evs = new HypoValue();

for (int i=0; i<g_Hypo.num; i++)

{

   evg->value[i] = ALL;    // 一般边界G

   evs->value[i] = NUL;    // 特殊边界S

}

g_G.push_back(evg);

g_S.push_back(evs);

}

// 正例ps与假设h是否一致

bool PositiveisConsistent(HypoValue h, HypoValue ps)

{

for (int i=0; i<g_Hypo.num; i++)

{

   if (h.value[i]==ALL)

    continue;

   else if (h.value[i]!=ps.value[i])

    return false;

}

return true;

}/*1wangxiaobo@163.com*/  

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

bool NagativeisConsistent(HypoValue h, HypoValue ns)

{

for (int i=0; i<g_Hypo.num; i++)

{

   if (h.value[i]!=ALL && h.value[i]!=ns.value[i])

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

}

return false;

}

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

bool GMemberMoreGeneral(HypoValue h)

{

int i;

list<HypoValue*>::iterator it;

HypoValue mem;

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

{

   mem = **it;

   for (i=0; i<g_Hypo.num; i++)

   {

    if (mem.value[i]==ALL && h.value[i]==ALL)

     continue;

    else if (mem.value[i]==h.value[i])

     continue;

    else if (mem.value[i]!=ALL && h.value[i]==ALL)

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

    else if (mem.value[i]==ALL && h.value[i]!=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*/  i<g_Hypo.num; i++)

{

   if (s.value[i]==NUL)

    h->value[i] = d.value[i];

   else if (s.value[i]==ALL)

    h->value[i] = ALL;

   else if (s.value[i]!=d.value[i])

    h->value[i] = ALL;

   else

    h->value[i] = d.value[i];

}

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;

list<HypoValue*>::iterator it;

list<HypoValue*>::iterator next;

list<HypoValue*>::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*/  i<g_Hypo.num; i++)

    {

     if (e1.value[i]==ALL && e2.value[i]==ALL)

      continue;

     else if (e1.value[i]==e2.value[i])

      continue;

     else if (e1.value[i]==ALL && e2.value[i]!=ALL)

     {

      r1 = true;

      if (r2) break;

     }

     else if (e1.value[i]!=ALL && e2.value[i]==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;

list<HypoValue*>::iterator it;

HypoValue mem;

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

{

   mem = **it;

   for (i=0; i<g_Hypo.num; i++)

   {

    if (mem.value[i]==ALL && h.value[i]==ALL)

     continue;

    else if (mem.value[i]==h.value[i])

     continue;

    else if (mem.value[i]!=ALL && h.value[i]==ALL)

     continue;

    else if (mem.value[i]==ALL && h.value[i]!=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; i<g_Hypo.num; i++)

{

   for (j=1; j<=g_Hypo.an[i].num; j++)

   {

    if (j!=d.value[i])

    {

     HypoValue* h = new HypoValue(g);

     h->value[i] = 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;

list<HypoValue*>::iterator it;

list<HypoValue*>::iterator next;

list<HypoValue*>::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; i<g_Hypo.num; i++)

    {

     if (e1.value[i]==ALL && e2.value[i]==ALL)

      continue;

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

      continue;

     else if (e1.value[i]!=ALL && e2.value[i]==ALL)

     {

      r1 = true;

      if (r2) break;

     }

     else if (e1.value[i]==ALL && e2.value[i]!=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(list<HypoValue*> &g_S,list<HypoValue*> &g_G,int i)

{/*1wangxiaobo@163.com*/  

  

     int j,k;

list<HypoValue*>::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; j<g_Hypo.num-1; j++)

   {

    if (s.value[j]==ALL)

     printf("?, ");

    else if (s.value[j]==NUL)

     printf("O, ");

    else

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

   }/*1wangxiaobo@163.com*/  

   if (s.value[j]==ALL)

    printf("?>\n");

   else if (s.value[j]==NUL)

    printf("O>\n");

   else

    printf("%s>\n", g_Hypo.an[j].att[s.value[j]-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; k<g_Hypo.num-1; k++)

   {

    if (s.value[k]==ALL)

     printf("?, ");

    else if (s.value[k]==NUL)

     printf("O, ");

    else

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

   }

   if (s.value[k]==ALL)

    printf("?>\n");

   else if (s.value[k]==NUL)

    printf("O>\n");

   else

    printf("%s>\n", g_Hypo.an[k].att[s.value[k]-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();

list<HypoValue*>::iterator it;/*1wangxiaobo@163.com*/  

list<HypoValue*>::iterator temp;

int i,j,k;

for (i=0; i<g_sn; i++)

{

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

   {

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

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

    {

     if (!PositiveisConsistent(**it, g_sa[i].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[i].ev))

     {

      MiniGeneral(**it, g_sa[i].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[i].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[i].ev))/*1wangxiaobo@163.com*/  

     {

      MiniSpecial(**it, g_sa[i].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;

}

声明：本网站引用、摘录或转载内容仅供网站访问者交流或参考，不代表本站立场，如存在版权或非法内容，请联系站长删除，联系邮箱：site.kefu@qq.com。
相关推荐
  • 坎公骑冠剑任务“迷路的少女”过关流程攻略
    阅读量：116
  • x的三次方减一怎么因式分解？
    阅读量：25
  • 【Mathematica】把二元函数拓展为双周期函数
    阅读量：35
  • 决战平安京如何关闭系统语言
    阅读量：29
  • VB菜单项如何插入图片
    阅读量：176
    • 猜你喜欢
    猜你喜欢
    © 2025 小度生活
    粤ICP备2022083104号