(3) 将属性p加入到集合B中,B=B∪{p};
(4) 若I(B,D)=I(C,D),算法结束;否则,转入(1);
步骤4 属性集合B就是决策表S=(U,R,Vf)的一个约简结果。
MIBARK算法同样是一种启发式的约简算法,它可以获得决策表的约简结果。但该算法该算法引用了概率分布和信息熵等描述不确定性问题的概念,所以它关注的是该属性对将要处理的数据集合中不确定分类子集的作用,而没有顾及该属性对论域中确定分类子集的影响。因此,该算法不一定能够保证得到决策表的最小约简属性[25]。
3.5属性值的约简算法
3.5.1一般值约简算法
对于一个经过属性约简而得到的决策表,我们可以对应其中的每一个样本形成一条决策规则。因此,我们可以将决策表中的样本用规则来表示,这样,约简后的决策表实际上就是一个规则集合。对于这个集合,我们可以用以下算法来进行简化[18]:对属性约简后的决策表(即规则集合)中的每条规则,去掉其任意一个条件属性后,若与其他规则冲突,即剩余条件属性值相同,而决策属性值不同,则该属性是可以去掉的;否则,保留该属性。
从理论上讲,经过这样处理得到的规则集合中的所有规则都不含有冗余的条件属性。但这个算法的实现有很多任意性,比如,由于处理规则的顺序不同,或者处理规则中条件属性的顺序不同,我们都可以得到不同的值约简结果,得到的规则集合就会有所不同[18]。因此,我们往往需要一些启发式知识来指导这一过程进行。
3.5.2基于正域的属性值约简算法 [26]
由正域定义知,决策属性D的条件属性C正域POSC(D)表示:由D对论域进行划分形成的等价类在C对论域划分形成的等价类的下近似集的并集,亦即属于D划分的论域等价类能在条件属性集C下能被正确分类的那些对象的集合。因而,基于正域的属性值约简算法可描述为:对于一个经过属性约简后的决策信息系统S=(U,C∪D,f),C={a1,a2,…,an},那么POSC\{ai}(D)( ai∈C,i=1,2,…,n)就表示不需要属性ai就能确定分类的对象集,因而在进行属性值约简时就可以将这些对象在该属性下的值删除,去掉重复记录,最终得到该决策信息系统约简后的规则集。
3.5.3典型的基于决策表的启发式值约简算法 [27]
给定的一个属性约简后的决策信息系统Sˊ=(Uˊ,RED∪D,Vˊ,f)),该算法对其进行值约简是先从值核入手,具体处理过程如文献[15]所述。该算法对要处理的规则的出现顺序没有要求,但对每条规则不同条件属性值先后处理顺序上有要求,可能会导致得不到最佳或较佳的属性值约简结果,即得到规则有时也会存在冗余。并且当决策信息系统约简后的条件属性仍然较多时,采用该算法得到的约简结果泛化能力较弱。而且该算法在执行的过程中,虽然不需要很多次遍历决策表,但当规则数集约简属性数较多时,耗费的时间便会增加。与此同时,在每一次遍历决策表时,都需要对去掉(或恢复)某属性值后的规则是否与其他规则发生冲突进行判定,这也会增加系统在空间和时间上的开销。总的说来,该算法是一种较为低效的属性值约简算法。与一般值约简算法一样。 基于粗糙集理论的多源信息决策知识约简研究(10):http://www.youerw.com/guanli/lunwen_7823.html