機器學習演算法實現：[2]FIND-S演算法?

機器學習(Machine Learning, ML)是一門多領域交叉學科，涉及概率論、統計學、逼近論、凸分析、演算法複雜度理論等多門學科。專門研究計算機怎樣模擬或實現人類的學習行為，以獲取新的知識或技能，重新組織已有的知識結構使之不斷改善自身的效能。

它是人工智慧的核心，是使計算機具有智慧的根本途徑，其應用遍及人工智慧的各個領域，它主要使用歸納、綜合而不是演繹。

FIND-S演算法

1. 將h初始化為H中最特殊假設

2.對每個正例x

對h的每個屬性約束ai

如果x滿足ai

那麼不做任何處理

否則將h中ai替換為x滿足的下一個更一般的約束

3. 輸出假設h

工具/原料

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; // 樣本數

HypoValue g_hm; // 極大假設

讀檔案和進行樣例一般化如下圖：

列印輸出函式如下：

void printdata(Hypothesis &g_Hypo,int i)

{int ii;

if(i==-3)

printf("極大特殊假設h：<");

else

printf("第%d個訓練樣例一般化後 輸出假設h：<",i+1);

for (ii=0; ii

{

if (g_hm.value[ii]==ALL)

printf("?, ");

else if (g_hm.value[ii]==NUL)

printf("O, ");

else

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

}

if (g_hm.value[ii]==ALL)

printf("?>\n");

else if (g_hm.value[ii]==NUL)

printf("O>\n");

else

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

//.....................迴圈輸出每次一般化後的假設.............................

}

執行輸出的每一次樣例一般化結果和，最終的一般化：

第1個訓練樣例一般化後輸出假設h：

第2個訓練樣例一般化後輸出假設h：

第3個訓練樣例一般化後輸出假設h：

第4個訓練樣例一般化後輸出假設h：

極大特殊假設h：

請按任意鍵繼續. . .

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

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

{ /*[email protected]*/

char name[A_CHAR_MAX]; // 屬性名稱

int num; // 屬性值個數

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

};

// 假設

struct Hypothesis

{ /*[email protected]*/

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; // 樣本數

HypoValue g_hm; // 極大假設

// 從檔案中讀取假設集合

bool ReadHypothesis( const char* filename)

{ /*[email protected]*/

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

}

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

{

for (j=0; j

{ /*[email protected]*/

fscanf(file, "%d", &g_sa[i].ev.value[j]);

}

fscanf(file, "%d\n",&g_sa[i].result);

}

fclose(file);

return true;

}

void printdata(Hypothesis &g_Hypo,int i)

{int ii;

if(i==-3)

printf("極大特殊假設h：<");

else

printf("第%d個訓練樣例一般化後 輸出假設h：<",i+1);

for (ii=0; ii

{

if (g_hm.value[ii]==ALL)

printf("?, ");

else if (g_hm.value[ii]==NUL)

printf("O, ");

else

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

}

if (g_hm.value[ii]==ALL)

printf("?>\n");

else if (g_hm.value[ii]==NUL)

printf("O>\n");

else

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

//.....................迴圈輸出每次一般化後的假設.............................

}

/*[email protected]*/

int main(int arc, char** argv)

{

system("title 曉博Find-S試驗程式");

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;

}

int i,j;

for (i=0; i

{

g_hm.value[i] =NUL;

}

for (i=0; i

{

if (g_sa[i].result==YES)

{

for (j=0; j

{

if (g_hm.value[j]==NUL)

g_hm.value[j] = g_sa[i].ev.value[j];

else if (g_hm.value[j]==ALL)// strcmp(h[j], "?")==0)

;

else if (g_hm.value[j]!=g_sa[i].ev.value[j]) // strcmp(h[j], H[i][j])!=0)

g_hm.value[j] = ALL;

}

}

//................ 迴圈輸出每次一般化後的假設............................

printdata(g_Hypo,i);

} /*[email protected]*/

printdata(g_Hypo,-3);//用於選擇輸出dos螢幕

system("pause");

return 0;

}