Candidate-Elimination算法是數據挖掘中的一種概念學習算法，部分解決Find-S的不足，可以輸出所有與訓練樣本一致的概念，同時利用概念間偏序關係來指導搜尋。
基本介紹
- 中文名：Candidate-Elimination算法
- 性質：概念學習算法
- 作用：部分解決Find-S的不足
- 範疇：數據挖掘
算法描述,算法舉例,
算法描述
其偽代碼描述如下：
Initialize Gto the set of most-general hypotheses in H
Initialize Sto the set of most-specific hypotheses in H
For each training example, d, do:
If dis a positive example then:
Remove from Gany hypotheses that do not match d
For each hypothesis sin Sthat does not match d
Remove sfrom S
Add to S all minimal generalizations, h, of ssuch that:
1) h matches d
2) some member of Gis more general than h
Remove fromSany hthat is more general than another hypothesis in S
If dis a negative example then:
Remove from Sany hypotheses that match d
For each hypothesis gin Gthat matches d
Remove gfrom G
Add to G all minimal specializations, h, of gsuch that:
1) hdoes not match d
2) some member of Sis more specific than h
Remove fromG any hthat is more specific than another hypothesis in G
算法舉例
基本的算法思想是，泛化邊界初始化為全？，特化邊界特化為全空集(@),
1、若遇到正實例,首先從G中刪除不包含該實例的概念，然後對S刪除與實例不相符的概念，同時做最小泛化，使其包含該實例
2、若遇到負實例,首先從S中刪除包含了該實例的概念，然後對G刪除包含了該實例的概念，同時做最小特化，注意最小特化集是與當前S一一枚舉出可能的特化概念，刪除那些符合該實例的概念
