FOIL算法演示.pptVIP

FOIL算法提取规则 制作人：王卫平 计算机系 训练集（Training Dataset） 　 age income student credit_rating buys_computer P 31…40 high no fair yes 40 medium no fair yes 40 low yes fair yes 31…40 low yes excellent yes =30 low yes fair yes 40 medium yes fair yes 　 　 　 　 　 N =30 high no fair no =30 high no excellent no 40 low yes excellent no =30 medium no fair no 说明：首先以buys_computer=yes为正例，其它为负例 FOIL_Gain FOIL_Gain提出 假设学习类c的规则中，当前的规则是R：IF condition THEN class=c。 然后我们想知道给定属性测试逻辑合取到condition中是否导致更好的规则,称 新的条件为condition’,其中R*：IF condition’ THEN class=c。换言之，我想 知道R*比R是否要更好。这样，我们提出FOIL_Gain，它偏向具有高准确并 且覆盖许多正例的规则。 FOIL增益公式 公式中|P*|（|N*|）为被R*覆盖的正（负）元组数，|P’|（|N’|）为被R覆盖正 （负）元组数。 带入公式，求出每个属性值的增益： age =30 31~40 40 gain -1.263 1.474 0.966 income high medium low gain -0.848 0.304 0.966 student yes no gain 1.660 -1.170 Credit-rating fair excellent gain 1.257 -0.848 |P’|=6，|N’|=4; 例如，我们算一下age=30时的增益: 将 |P*|=1，|N*|=3，代入上式公式，求的FOIL_Gain=-1.263 |N’|=10，所以还要进行内循环 所以当p={ student=‘yes’}时最大的FOIL_Gain。 执行 append p to r 那么规则r ={ student=‘yes’}； 这时，移除P’、N’中不满足规则r的元组，那么P’、N’变成如下图所示： 　 age income student credit_rating buys_computer P 40 low yes fair yes 31…40 low yes excellent yes =30 low yes fair yes 40 medium yes fair yes N 40 low yes excellent no 所以当p={credit-rating=‘fair’}时有最大的FOIL_Gain。执行 append p to r 那么规则r ={ student=‘yes’AND credit-rating=‘fair’}； 移除P’、N’中不满足规则r的元组，这时，|N’|=0，内循环停止 再次求最大FOIL增益，这时|P’|=4，|N’|=1。 age =30 31~40 40 gain 0.322 0.322 -0.526 income low medium gain -0.279 0.322 credit-rating fair excellent gain 0.966 -0.678 此时|P|= 30,第二次执行外循环: P赋给P’，N赋给N’,规则r 清空,|N’|=40, 执行内循环: 接下来执行R=R∪{ r }, 这时规则R={student=‘yes’AND credit-rating=‘fair’} 移除P中满足规则R的所有元组，那么P、N变成如下图所示： age income student credit_rating buys_computer P 31…40 high no fair yes 40 medium no fair yes 31…40 low yes excellent yes