第四章--属性值约简(决策规则约简)

第四章属性值约简（决策规则约简）§1属性值约简属性约简分两类，一类是信息表约简，一类是决策表约简。信息系统S={U,A}的约简，是对整个属性集A进行约简，要求利用最少属性的属性集能提供与原属性集A同样多的信息，在此若是冗余属性，则是将a去掉后则A-{a}与A具有同样的分类能力，即有下面相同的等价类族：若是独立的，即中任意去掉一个属性，都将改变其分类能力，则就是A的一个约简。A的约简是A中独立的子集P并且P与A具有同样的分类能力，而中的属性对P来说都是冗余属性。信息表的特点是属性集不再划分为条件属性集和决策属性集。对于决策表来说，约简的情况不同，它不是针对整个属性集A进行的，约简的只是条件属性集。决策表的约简分两部分：第一步：属性集约简若果，满足P是关于决策属性集D独立的，并且，则P是C的D约简。C中的所有D约简的交称为C的核，记作。第二步：属性值约简设是一致性决策表，是C的D约简。值约简是针对相对约简而言的，或说属性值约简是对决策表上每一条决策规则来说的。关于决策规则中属性值约简，下面例题提供了属性值约简的理论依据。决策表上一条决策规则的条件属性值可以被约去，当且仅当约去该属性值后，仍然保持该条规则的一致性，即不出现与该条规则不一致的规则。约简算法的步骤为：1约简属性集；2约简决策规则，即属性值约简；3从算法中消去所有过剩决策规则。关于决策表的属性约简和决策规则的属性值约简，看下面例子。例1简化给定决策表，其中为条件属性集，为决策属性集表1决策表AUabcde123456711011220001122000000210012221100222算法步骤：第一步：约简属性集：从决策表中，将属性A中的属性逐个移去，每移去一个属性立刻检查其决策表，如果决策表中的所有决策规则不出现新的不一致，则该属性是可以被约去的，否则，该属性不能被约去，称这种方法为属性约简的数据分析法。解法1：从条件属性集中移去c列后，决策表不出现新的不一致，所以c列可约去；从中移去a或移去b，或移去d后，决策表中都出现新的不一致，故a,b,d都不能移去，即a,b,d都是C的D核属性。由此得是的惟一约简。也可用差别矩阵求C的D约简。也可以用D的C正域来求C的D约简与C的核。解法2：1.U/D={{1,2},{3,4},{5,6,7}}U/a={{1,2,4,5},{4,5},{6,7}}U/b={{1,2,3}.{4,5},{6,7}}U/c={{1,2,3,4,5,6},{7}}U/d={{1,4},{2,3},{5,6,7}}则：U/C={{1},{3},{2},{4},{5},{6},{7}}。故={1,2,3,4,5,6,7}①={{1},{2,3},{4},{5},{6},{7}}所以，所以不可约；②={{1,4},{2,3},{5},{6},{7}}所以，所以b不可约；③={{1},{2},{3},{4},{5},{6,7}}所以，所以可约；（是上可约去的）④={{1,2},{3},{4,5},{6},{7}}所以，所以不可约；因中每一个属性都是上不可约去的，故是的核，也是唯一的C的D约简。上述例子相对简单，在4个条件属性中三个核属性，只一个不是核属性，去掉该属性即得惟一的由核属性构成C的D约简。由计算过程看出，解法1相对简单，是实用算法。用差别矩阵求此例的相对约简也很简单。第二步：属性值约简将表1中c列去掉得到属性集被约简的表，再去掉重复的第七行，得到一个C的D约简决策表2.表中的每一行表示一个决策规则，由此得决策规则为规则1：┆┆┆规则6：：对约简表实施属性值约简就是对逐条决策规则实施属性值约简，求取最简小决策规则。下面对表2进行属性值约简。表2AUabde123456110112000112100122110022解：对6条决策规则逐一实行属性值约简，步骤1：对每一条决策规则，去掉一个属性值，即刻观察是否出现与该条规则不一致的规则，如：规则1中去掉a值[a,1]，规则1变为，其他各条规则均不与该条规则不一致：即条件属性值相同而决策属性值不同。因此，该规则仍然为真，这时其它5条规则中不出现与该条规则不一致的规则。所以值[a,1]是可约去的属性值，或说[a,1]不是规则1的核值。去掉值[b,0]，则规则1化简为与规则4：不一致，所以，值[b,0]不能约去，即是规则1的核值；去掉值，规则1化为，不出现新的不一致，故值可约去，不是核值。对规则2,3,4,5,6重复上述步骤，求出每一条规则的核值，得到核值表3.表3核值表AUabde123456–10–––0––1–––––12–110022核值表3清楚地表明了每一条决策规则中，那一个属性值是可以约去的，那一条是不能约去的。但是，仅有核值尚不一定能构成约简决策规则。例如，第一条决策规则中，只说明不能约去，而，都是可约去的，但两个都约去却不一定构成与决策规则1等价的规则，还要看分类能力是否改变。步骤2根据表3给出的核值决策规则，分别找出所有决策规则的约简，可得包含所有约简决策规则的表4，具体作法如下：1.决策规则1……………………………………决策类…………………………………属性值为的等价类…………………………………属性值为的等价类………………………………………属性值为的等价类其中表示为核值。先看等价类是否完全包含在的决策类中，如果被包含在其中，说明的等价类中所有个体都能被正确分类，这时，成立，此时，就是规则1的值约简；否则，尚不能构成规则1的值约简，必须补充核外值。注意到约简规则中必定包含核值，因，知单一的核值构不成值约简。这时，从非核值中按每次补一个、补两个、…、一直到得到值约简为止。而，所以，同理。这样，第一条决策规则就简化为两条决策规则：和或。含义是：若个体关于、的值为、，那么，该个体也必属于决策类；若某个体关于、的值为、，那么，该个体也必属于决策类。这就是一般的决策规则。应注意：求值约简必须从核值开始，因为核值是不能被丢掉的。如规则1中，丢掉核值，仅由与之交得，是导不出决策类的2.决策规则2：，，，值约简为和3.决策规则3：，，，注意：因核值的等价类包含在中，所以核值本身构成值约简，其它属性值均是冗余的。值约简为4.决策规则4：，，，值约简为5.决策规则5：，，，值约简为6.规则6：，，，该条规则无核值，但每一个值都构成值约简，否则，则每次考虑两个、三个、…，直到求出值约简。由此得值约简为，，综上，得到包含所有约简的决策规则表4。表4包含了所有约简规则的决策表AUabde1234561–110––2––000––1––2––1–0–12––21111002222表4表明：规则1与2分别简化为两条规则，规则3简化为3条规则。步骤3：消去所有过剩规则（1）决策类1有三个最小化决策规则集：，，合成为（2）决策类0有两个最小化规则集：，合成为（3）决策类2有三个最小化规则集，，合成为给定的决策表共三类决策规则，“1类”，“0类”，“2类”。经属性约简、属性值约简后，得到三个决策类的最小值约简：；；①由此取出1个最小化决策算法（在此只取一个最小化决策算法），取法是：从每条规则中取一条最小规则，若该条规则也出现在后面某条规则中，则后面的规则中不再取规则。由此得：，，②①式是对简化后决策规则的最完整的描述，②式只是一种最小决策算法，通常不能只按一种最小决策算法实施控制。§3机器人控制系统现在我们讨论用Rough集方法处理一个机器人控制程序。机器人控制程序称做Reactive程序，它是控制智能物行为的程序。它的最简单形式是由产生式规则的有序序列组成。，其中是条件，为行为，共有个不同行为。执行原理为：从第一条规则起往下寻找第一个条件为真的规则，并执行相应行为，而且这种行为是持续不断的。亦即若某条件始终保持最先为真，则相应行为不断被执行，直到该行为最终激发另一在它前面的条件最先为真。一般情况下，是目标条件，是空行为即终止行为。机器人行为控制系统可以通过这样的Reactive程序来实现。Agent自适应系统（即机器人控制系统）是这样一个系统：Agent在所处的环境中，通过环境中的介质的传感作用，使之感知环境的变化，因而产生行为。此行为导致环境的变化，变化的环境又使它感知到新的信息，从而产生新的行为，如此往复形成一个简单的相互作用过程，被称为Agent自适应系统。如最简单的Agent抓捧自适应系统。设机器人所处的环境有6个状态，其中5个分别是Reactive程序中产生规则的前提条件，即5个条件属性；另一个状态为Reactive程序中产生规则的结论，它被看做是决策属性。它们的意义如下：a：是否在中心点，在为1，否为0；b：是否正前方面对棒，是为1，否为0；c：是否在棒中心，是为1，否为0；d：是否正前方面对中心线，是为1，否为0；e：是否已抓棒，是为1，否为0；f：表示机器人行为，有四种属性：1表示旋转；2表示前移；3表示抓棒；4表示停止。Reactive程序执行思想是：1．抓了棒就停止；2.机器人位于中心点，并且面前正对捧才可以抓棒；3.机器人处于任意位置，通过旋转可使其正前方面对棒的中心线或棒；4.通过前移使机器人到达中心线上和中心点。由此，可以得到一个机器人抓棒的控制决策系统。表1给出机器人抓捧控制决策系统AU中心点a正对捧b中心线c正对中心线d抓捧e机器人行为f机器人位置1000001旋转2001001旋转3101001旋转4000102前移5011002前移6111003抓捧7111014停止表1的解释：中心点：当Agent处在中心点位置并且面前正对捧时，就可以抓棒；第一行表示：Agent处于任意位置：即不在中心点、不在中心线上、不正对中心线、也不正对捧、没有抓捧，这时Agent旋转；第二行表示：若Agent：不在中心点，正对捧，在中心线上，但不正对中心线，没抓捧，则Agent旋转，使之面前正对捧；第三行表示：若Agent在中心点，但不正对捧，在中心线上，自然不正对中心线，没抓捧，这时Agent旋转；第四行表示：Agent不在中心点，不面对捧，不在中心线上，但正对中心线，没抓捧，则Agent旋转；第五行表示：Agent不在中心，但正对捧，在中心线上，自然不正对中心线，没抓捧，则Agent前移；第六行表示：Agent在中心点，正对捧，自然在中心线上，且不正对中心线，当没抓捧时，则抓捧。第七行表示：Agent在中心点，正面对捧，自然在中心线上且不正对中心线，当已抓捧时，则停止。对表1进行属性约简：1.属性约简：删去属性后该表一致，故可删去，但a,b,d,e不能删去，是核属性。也是帷一的约简。删去及删掉后出现的重复行得表2。2.属性值约简，求各规则的核值，得核值表3表2决策表表3核值表AUabdefAUabdef1000011-00-13100013-0--14001024--1-2501002501--2611003611-037110147---14注意：对规则1，删去值，并不出现与第一条规则不一致的情况，故可删去。虽说删去后，规则6与规则7出现不一致，但这没关系，只要不出现与第1条规则不一致就是第1条规则的非核值，由此得表3。3.根据核值表3与表2，求每条决策规则的值约简。决策规则1：，决策规则3：，决策规则4：同理得：决策规则5的值约简为：决策规则6的值约简为：决策规则7的值约简为：综合上述，得到决策规则的所有可能值约简，见表4。表4AUabdef1–00–1310––13`–00–14––––2501––2611–037–––144.最小决策规则算法由决策表4得机器人抓捧最小决策规则算法为：最小规则算法1：最小规则算法2：（算法2的第二条规则与算法1相同，故可省去）按Reactive程序执行思想，上述算法2可以将规则重新排列为：从本应用例看出，机器人抓棒控制决策系统，可以用决策表给出。这样简化控制过程就是要求机器人抓棒最简控制决策算法——对决策表进行约简，求最小决策算法。Rough集理论提供了AI的许多分支上可应用的有效算法，逐渐成为数据库知识发现（KDD）和数据挖掘（DM）研究的主要理论依据。