姓名：梁祥 学号：17021210935
转载自：http://page.renren.com/600717490/note/727394344?op=pre&curTime=1305686801000，有删改。
【嵌牛导读】：情报从来都是克敌制胜的重要法宝，但是很多时候我们都是空有一座金山，却无法发掘。这里有一个理论上成立的小想法，希望能让吃腻狗粮的你找到一个脱单之路。
【嵌牛鼻子】：数据挖掘、候选消除
【嵌牛提问】：数据挖掘到底离我们有多远？
【嵌牛正文】：
这是一个曲折但不漫长的故事，万年单机党小明暗恋着小美，但是小明不知道自己是不是小美喜欢的类型，所以拿不定主意要不要向小美表白。可喜可贺的是小明是一个工科技术宅，并且对小美喜欢男生的类型有所了解。也就是下面的这张表：
今天要介绍一种机器学习的算法，叫做Candidate-elimination learning.
在介绍这种方法之前，我们先看看小明和小明的妈妈的对话以及他们的想法吧。
小明说：“我想有十足的把握才会向小美表白。我不想冒一点风险。这四个男生中，有三个是小美的喜欢类型。保守一点的话，如果我的情况和这三个男生任意一个情况完全相同，那么我一定是小美喜欢的类型。如果我的情况和这三个男生情况不一样，即使我和那个不受欣赏的男生情况也不一样，我还是没有十足把握。既然我不是那三种情况之一，为了保守起见，就当做小美不欣赏我吧。”
说完小明叹了口气，想要放弃了。
小明妈安慰道，“儿子不要轻易放弃。追女生要胆大点。哪怕一点点希望都不能放弃。你不如反过来想。这四个人中只有一个是小美不喜欢的类型。只要你不是那种情况，就不能说小美一定不喜欢你。勇敢点。只要不是那一类，你就有希望。只要你不是那个小美不喜欢的类型，你就当你是小美喜欢的类型。”
不知道大家对这两种想法怎么看。是不是觉得都有点道理，又都有点没道理？小明的看法太保守了，可能会白白错过机会；小明妈妈的看法又太乐观，这就可能冒风险。
难道只有从保守的方法和乐观的方法中选择一个才行吗？有没有更好的方法？如果我们能有一种方法介于最保守和最乐观之间的，岂不就是一个更好的办法。
2. Candidate-elimination
这个方法就是我在这篇解答里要介绍给大家的。它的专业名字叫做Candidate-elimination learning。我们先来探讨一下这种方法的本质：就是将保守和乐观结合起来。
在这种方法里，我们设定两个边界，最保守边界(most specific boundary)和最乐观边界(most general boundary)。设定这两个边界的原因，是我们要找到介于他们中间的判断方法。介于他们中间的方法，既不会因为保守而白白丢掉那些可能被小美喜欢的情况，又不会因为盲目乐观而冒风险。
好现在我们来规定一些字母和标记，来方便我们进行讨论：
在这种方法里，我们设定两个边界，最保守边界(most specific boundary)和最乐观边界(most general boundary)。设定这两个边界的原因，是我们要找到介于他们中间的判断方法。介于他们中间的方法，既不会因为保守而白白丢掉那些可能被小美喜欢的情况，又不会因为盲目乐观而冒风险。
好现在我们来规定一些字母和标记，来方便我们进行讨论：
首先我们将“大学，身高，幽默感，专业，喜欢的运动，性格”这6个方面看做6个属性。我们的判断是基于这6个属性的取值。
当身高属性值取“高”时我们用“高”表示。
当一个属性值用“0”表示，代表这个属性什么值也不可以取。
当一个属性值用“？”表示，代表这个属性任何值都可以取。
我们用G来代表最乐观边界，用S来代表最保守边界
在我们故事的例子中，我们用G0来表示G的初始化值（既最乐观边界的初始化）
G0{？，？，？，？，？，？} 则代表初始化时，最乐观边界是：每个属性无论取什么值都可以。即这6个属性，无论取什么值，都判断为是小美喜欢的类型。
同样，我们用S0来代表S的初始化值（既最保守边界的初始化）
S0 {0, 0，0，0， 0， 0} 则代表初始化时，最精确边界：是每个属性任何值都不能取，即初始化时，无论每个属性取什么值，都不是小美欣赏的类型。
3此种方法machine learning 的步骤
接下来就是machine learning 的过程。在machine learning 里，我们要做的就是根据不断遇到的信息对S不断放宽，对G不断缩窄。
1.每当遇到一个小美喜欢的类型。我们要从G里删除任何不能包容这个例子的方法。如果此刻S还不考括这种情况，我们要加进去使S能够包括这种情况
2.每当遇到一个小美不喜欢的类型。我们从S里移除任何可能包含这个例子的方法。然后对G加以修改，使G不包含这个反面例子。
4. 具体步骤详细解释
这样说起来比较抽象。具体解决这个问题应该会给大家更深刻的印象。
首先我们初始化S和G。S和G旁边的数字代表着这是遇到第几个例子后得到的结果
1）初始化
S0 {<0, 0，0，0， 0， 0>}
G0{<？，？，？，？，？，？>}
2）第一个例子：
这是一个小美喜欢的类型。首先我们看到最乐观的边界G0此时是将所有情况（当然也包括第一个例子的情况）都认定为小美喜欢的类型。所以我们对G不做任何更改。我们得到的结果是G1=G0
初始化的S0不包括任何情况，所有的男生在S0处都是小美不喜欢的类型。但是现在我们明确知道第一个例子是小美喜欢的。我们对S0做出更改，让它能够包含例子1。以下是这一步得到的结果。
S1 {<重点，高，不幽默，理科，篮球，外向>}
G1{<？，？，？，？，？，？>}
3）第二个例子
还是小美喜欢的类型。同样的我们对G不做改变。我们改变S，使它能包括这个例子。我们看到这个例子和第一个例子很多属性取值一样，对于这些属性就不做更改。对于取值不一样的属性，我们再一次放宽取值，取“？”既任何值。这代表了此属性取值对于判断结果影响不大。
S2{<重点，高，？，理科，篮球，外向>}
G2{<？，？，？，？，？，？>}
4）第三个例子
这是小美喜欢的类型。
我们看到了关于性格属性是“内向”。说明内向不是让小美不喜欢的属性。我们需要将S放宽。并且去除掉G中“<？，？，？，？，外向>”，因为通过例子4我们明确知道了性格内向会让小美不喜欢的这种可能性不存在。
我们要再一次放宽S，将性格取值由“外向”改为“？”，将运动取值由“篮球”改为“？”
S4{<重点大学，高，？，理科，？，?>}
G4{<重点，？，？，？，？，？>,<？，高，？，？，？，？>}
5.存在于最乐观和最保守之间的判断方法
此时S4和G4就是我们最终得到的最保守边界，和最乐观边界。这两个边界本身就是一个判断的标准，只是他们存在着缺陷，即太保守或太乐观了。那些在这两个边界之间的判断标准则有效地避免了太乐观或太保守的缺点。
这两个边界之间还包含了什么判断标准呢？
S4{<重点大学，高，？，理科，？，？>}
<重点，？，？，理科，？，？>， <重点，高，？，？，？，？>，<？,高，？，理科，？，？>
G4{<重点，？，？，？，？，？>,<？，高，？，？，？，？>}
以上6个判断标准就是我们最终得到的所有能将四个例子正确分类的判断标准。我
们来看一下小明的情况：重点大学，身高高，不幽默，理科，喜欢足球，性格较内向。小明的情况会被所有的判断方法判断为受小美喜欢的类型。
当然我们只需要用最保守的判断即“S4{<重点大学，高，？，理科，？，？>}”即可。因为如果小明在最保守的判断下能被小美喜欢，那么其他更加乐观的判断方法也会得到一样的结果。
6.缺点
那么其他的情况呢，如果有小黑，小白，他们的情况也能通过这些判断标准找到绝对答案吗？
如果有个男生是：重点中学，高，不幽默，文科，篮球，外向，又会被断定为哪种结果呢？
这种情况下，有三种判断标准会将其判定为小美喜欢的类型，而另外三种则相反。所以我们无法做出最后的结论。
当然这也是因为我们现在的信息太少。如果我们能有更多的信息，随着S不断放宽，G不断缩窄，他们之间的空间也会不断变小，那么我们的判断也会更加精确。
