候选消除算法 九

1、候选消除算法 九 / bianxingspace.cpp#pragma warning (disable: 4996)#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 Attributechar nameA_CHAR_MAX; / 属

2、性名称int num; / 属性值个数char attA_VALUE_MAXA_CHAR_MAX; / 属性值;/ 假设struct Hypothesisint num; / 属性个数Attribute anA_NUM_MAX; / 属性集合;/ 假设值struct HypoValueint valueA_NUM_MAX;/ 样本struct SampleHypoValue ev; / 假设int result; / 正例/反例;Hypothesis g_Hypo; / 假设集合Sample g_saSAMPLES_MAX; / 样本空间int g_sn; / 样本数list<HypoV

3、alue*> g_G; / 一般边界Glist<HypoValue*> g_S; / 特殊边界S/ 从文件中读取假设集合/*/ 文件格式属性个数n属性名称1 属性值个数 属性值1 属性值2 属性值3 属性名称2 属性值个数 属性值1 属性值2 属性值3 属性名称n 属性值个数 属性值1 属性值2 属性值3 /*/bool ReadHypothesis(const char* filename)FILE* file;if (fopen_s(&file, filename , "r")return false;int i,j,k;fscanf(file

4、, "%dn", &g_Hypo.num);for (i=0; i<g_Hypo.num ; i+)fscanf(file, "%s%d", g_H, &k);g_Hypo.ani.num = k;for (j=0; j<k; j+)fscanf(file, "%s", g_Hypo.ani.attj);fscanf(file, "n");fclose(file);return true;/ 从文件中读取样本/*/ 文件格式样本个数m样本1属性1的值的序号 样本1

5、属性2的值的序号 样本1属性n的值的序号 1（正例）或者0（反例）样本2属性1的值的序号 样本2属性2的值的序号 样本2属性n的值的序号 1（正例）或者0（反例）样本m属性1的值的序号 样本m属性2的值的序号 样本m属性n的值的序号 1（正例）或者0（反例）/*/bool ReadSamples(const char* filename)FILE* file;if (fopen_s(&file, filename , "r")return false;int i,j;fscanf(file, "%dn", &g_sn);for (i=0;

6、 i<g_sn ; i+)for (j=0; j<g_Hypo.num; j+)fscanf(file, "%d", &g_sai.ev.valuej);fscanf(file, "%dn",&g_sai.result);fclose(file);return true;/ 初始化G和Svoid InitGandS()HypoValue* evg = new HypoValue();HypoValue* evs = new HypoValue();for (int i=0; i<g_Hypo.num; i+)evg-&g

7、t;valuei = ALL;evs->valuei = NUL;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.valuei=ALL)continue;else if (h.valuei!=ps.valuei)return false;return true;/ 反例ns与假设h是否一致bool NegativeisConsistent(HypoV

8、alue h, HypoValue ns)for (int i=0; i<g_Hypo.num; i+)if (h.valuei!=ALL && h.valuei!=ns.valuei)return true;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<

9、g_Hypo.num; i+)if (mem.valuei=h.valuei)continue;else if (mem.valuei=ALL | h.valuei=NUL)continue;elsebreak;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; i<g_Hypo.num; i+)if

10、 (s.valuei!=NUL && s.valuei!=d.valuei)h->valuei = ALL;elseh->valuei = d.valuei;if (GMemberMoreGeneral(*h)g_S.push_front(h);elsedelete h;/ 从S中移去所有这样的假设：它比S中另一个假设更一般void RemoveMoreGeneralFromS()bool r1,r2;int i;HypoValue e1, e2;list<HypoValue*>:iterator it;list<HypoValue*>:it

11、erator 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; i<g_Hypo.num; i+)/if (e1.valuei=ALL && e2.valuei=ALL)/ continue;/else if (e1.valuei=e2.valuei)conti

12、nue;else if (e1.valuei=ALL)r1 = true;if (r2) break;else if (e2.valuei=ALL)r2 = true;if (r1) break;elser1 = 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

13、比next更一般temp = it;it+;g_S.remove(*temp);elseit+;/ 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.valuei=h.valuei)continue;else if (mem.valuei=NUL | h.value

14、i=ALL)continue;elsebreak;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.ani.num; j+)if (j!=d.valuei)HypoValue* h = new HypoValue(g);h->valuei = j;if (SMe

15、mberMoreSpecial(*h)g_G.push_front(h);elsedelete 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

16、 = 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.valuei=e2.valuei)continue;else if (e2.valuei=ALL)r1 = true;if (r2) break;else if (e1.valuei=ALL)r2 = true;if (r1) break;elser1 = r2 = true;break;if (r1=true && r2=false) /it比n

17、ext更特殊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+;/ 主函数int main(int arc, char* argv)/ 读取假设和样本if (!ReadHypothesis("hypothesis.txt")printf("read Hypot

18、hesis file error");return 0;if (!ReadSamples("samples.txt")printf("read samples file error");return 0;/ 初始化G和SInitGandS();list<HypoValue*>:iterator it;list<HypoValue*>:iterator temp;int i;for (i=0; i<g_sn; i+)if (g_sai.result=YES) / 正例时/ 从G中移去所有与d不一致的假设for (it

19、=g_G.begin(); it!=g_G.end(); )if (!PositiveisConsistent(*it, g_sai.ev)temp = it;it+;g_G.remove(*temp);elseit+; / 对S中每个与d不一致的假设sfor (it=g_S.begin(); it!=g_S.end();)if (!PositiveisConsistent(*it, g_sai.ev)MiniGeneral(*it, g_sai.ev);temp = it;it+;g_S.remove(*temp); / 从S中移去sRemoveMoreGeneralFromS();else

20、it+;else / 反例时 / 从S中移去所有与d不一致的假设for (it=g_S.begin(); it!=g_S.end();)if (!NegativeisConsistent(*it, g_sai.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_sai.ev)MiniSpecial(*it, g_sai.ev);temp = it;it+;g_G.remove(*temp);

21、 / 从G中移去gRemoveMoreSpecialFromG();elseit+;/ 输出Sprintf("特殊边界S：n");for (it=g_S.begin(); it!=g_S.end(); it+)HypoValue s = *it;printf("<");for (i=0; i<g_Hypo.num-1; i+)if (s.valuei=ALL)printf("?, ");else if (s.valuei=NUL)printf("O, ");elseprintf("%s, ", g_Hypo.a