候选消除算法

Question

考虑以下培训数据集..

+-------+-------+----------+-------------+
| Size  | Color | Shape    | Class/Label |
+=======+=======+==========+=============+
| big   | red   | circle   | No          |
| small | red   | triangle | No          |
| small | red   | circle   | Yes         |
| big   | blue  | circle   | No          |
| small | blue  | circle   | Yes         |
+-------+-------+----------+-------------+

我想了解算法在以负面示例开始时和两个负面示例结合在一起时如何进行.

顺便说一下,这不是一个任务问题.

其他数据集的示例也欢迎!这是为了理解算法的负面部分.

Answer 1

对于您的假设空间(H),您从最大一般(G)和最大特定(S)假设开始:

G0 = {<?, ?, ?>}
S0 = {<0, 0, 0>}

当您看到一个反面例子时,您需要从S中删除任何与当前观察不一致的假设,并用G的最小特征替换G中的任何不一致假设,这些假设与观察一致,但仍然比S的某些成员更一般.

因此,对于您的第一个(负面)示例,(big, red, circle)最小特化将创建新的假设空间

G1 = {<small, ? , ?>, <?, blue, ?>, <?, ?, triangle>}
S1 = S0 = {<0, 0, 0>}

请注意,S没有改变.对于你的下一个例子,(small, red, triangle)也是负面的,你需要进一步专门化G.注意G1中的第二个假设与新的观察不匹配,所以只有G1中的第一个和第三个假设需要专门化.这会产生

G2 = {<small, blue, ?>, <small, ?, circle>, <?, blue, ?>, <big, ?, triangle>, <?, blue, triangle>}

但是,由于上面G2中的第一个和最后一个假设是中间假设(<?, blue, ?>)的特化,我们放弃这两个假设,给出

G2 = {<small, ?, circle>, <?, blue, ?>, <big, ?, triangle>}
S2 = S1 = S0 = {<0, 0, 0>}

对于积极的(small, red, circle)观察,你必须推广S并删除G中不一致的任何东西,这给出了

G3 = {<small, ?, circle>}
S3 = {<small, red, circle>}

(big, blue, circle)是下一个反面的例子.但由于它与G不一致,因此没有任何事情可做

G4 = G3 = {<small, ?, circle>}
S4 = S3 = {<small, red, circle>}

最后,您有一个积极的例子(small, blue, circle),它要求您概括S以使其与示例一致,给予

G5 = {<small, ?, circle>}
S5 = {<small, ?, circle>}

由于G和S相等,你已经学会了"小圆圈"的概念.