機器學習演算法實現：[1]候選消除學習演算法?

機器學習(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. ,EnjoySport=Yes

2. ,EnjoySport=Yes

3. ,EnjoySport=No

4. ,EnjoySport=Yes

工具/原料

Devc++

方法/步驟

資料結構定義：

#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 g_G; // 一般邊界G

list g_S; // 特殊邊界S

讀檔案和進行樣例對G邊界進行特殊化，S邊界進行一般化：

列印輸出函式如下：

void printdata(list &g_S,list &g_G,int i)

{

int j,k;

list ::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

{

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

{

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

}

執行輸出的每一次樣例一般化S邊界與特殊化G邊界的結果集合，和最終的一般化S邊界與特殊化G邊界的結果集合：

第1樣例使特殊邊界S一般化後的集合有1個極小一般化成員為：

第1樣例使特殊邊界G特殊化後的集合有1個極小特殊化成員為：

第2樣例使特殊邊界S一般化後的集合有1個極小一般化成員為：

第2樣例使特殊邊界G特殊化後的集合有1個極小特殊化成員為：

第3樣例使特殊邊界S一般化後的集合有1個極小一般化成員為：

第3樣例使特殊邊界G特殊化後的集合有3個極小特殊化成員為：

第4樣例使特殊邊界S一般化後的集合有1個極小一般化成員為：

第4樣例使特殊邊界G特殊化後的集合有2個極小特殊化成員為：

最終的特殊邊界S集合有1個極小一般化成員為：

最終的一般邊界G集合有2個極小特殊化成員為：

請按任意鍵繼續. . .

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（反例）]

/*/

附完整程式碼如下：

#include

#include

#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 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 g_G; // 一般邊界G

list 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

{

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

g_Hypo.an[i].num = k;

for (j=0; j

{

fscanf(file, "%s", g_Hypo.an[i].att[j]);

}/*[email protected]*/

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

{/*[email protected]*/

for (j=0; 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

{

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

{

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

continue;

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

return false;

}

return true;

}/*[email protected]*/

// 反例ns與假設h是否一致

bool NagativeisConsistent(HypoValue h, HypoValue ns)

{

for (int i=0; i

{

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

return true;/*[email protected]*/

}

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; 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;/*[email protected]*/

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; /*[email protected]*/ 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 ::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; /*[email protected]*/ 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 /*[email protected]*/ && r2==false)

{

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

{

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[email protected]*/

g_G.push_front(h);

else

delete h;

}

}

}

}

// 從G中移去所有這樣的假設：它比G中另一個假設更特殊

void RemoveMoreSpecialFromG()

{

bool r1,r2;

int i;

HypoValue e1, e2;

list ::iterator it;

list ::iterator next;

list ::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

{

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

continue;

else if (e1.value[i]==e2.value[i])/*[email protected]*/

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)/*[email protected]*/

{

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 &g_S,list &g_G,int i)

{/*[email protected]*/

int j,k;

list ::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

{

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

}/*[email protected]*/

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;/*[email protected]163.com*/

printf("<");

for (k=0; 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)/*[email protected]*/

{

system("title 曉博List-Then-Eliminate試驗程式");

printf("Designed by wangxiaobo email:[email protected]");

// 讀取假設和樣本

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 ::iterator it;/* [email protected]*/

list ::iterator temp;

int i,j,k;

for (i=0; 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);/*[email protected]*/

}

}

// 對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();

}/*[email protected]*/

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))/*[email protected]*/

{

MiniSpecial(**it, g_sa[i].ev);

temp = it;/*[email protected]*/

it++;

g_G.remove(*temp); /*[email protected]*/ // 從G中移去g

RemoveMoreSpecialFromG();/*[email protected]*/

}

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());/*[email protected]*/

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

system("pause");

return 0;

}