第八章 决策表值约简

123第八章信息表值约简值约简是在属性约简的基础上对决策表的进一步简化。本章将就决策表的值约简问题进行系统分析，并介绍几种主要的值约简算法。8.1决策表值约简概述在第7章中，我们介绍了决策信息表的属性约简，通过属性约简，可以将决策表中对决策分类不必要的属性省略，从而实现决策表的简化，这有利于从决策表中分析发现对决策分类起作用的属性。但是，属性约简只是在一定程度上去掉了决策表中的冗余属性，但是还没有充分去掉决策表中的冗余信息。例如，在表7.3-1所示的关于气象信息的决策表表的属性约简结果中，如果在条件Outlook=SunnyTemperature=Hot下，决策属性的取值肯定是N，而无需考虑条件属性Windy的取值是True还是False。显然，这个属性约简结果，对于决策分类来说，仍然包含冗余信息。根据第四章中介绍的决策规则，我们不能够直接从该表中得到满意的决策规则。这就是说我们还需要进一步对决策表进行处理，得到更加简化的决策表，这就是我们本章将要讨论的决策表值约简问题。与属性约简中的属性核一样，值约简中也可以定义相应的值核。决策表S=(U,C,D,V,f)，对于任意的xU，用dx表示决策规则，即dx：des([x]C)des([x]D)，dx(a)=a(x)，aCD，且dx|C、dx|D分别称为dx的条件和决策。定义8.1-1考虑一个相容知识表达系统S，对决策规则dx有[x]C[x]D。若rC，有[x]C-{r}[x]D，则r为dx的核值属性，r为dx中不可省略的；若[x]C-{r}[x]D，则r不是dx的核值属性，r为dx中可省略的。1248.2决策表值约简算法8.2.1一般值约简算法对于一个经过属性约简而得到的决策表，我们可以对应其中的每一个样本形成一条决策规则。因此，我们可以将决策表中的样本用规则来表示，这样，约简后的决策表，实际上就是一个规则集合。对于这个规则集合，我们可以利用如下算法来进行简化：对于规则集合中的每条规则对于该规则中的任意条件属性如果去掉该条件属性，该规则不和规则集中的其它规则冲突，则可以从该规则中去掉该条件属性；经过这样处理得到的规则集合中的所有规则都不含有冗余条件属性，也就是说，规则的条件属性数目已经被尽可能减少了。但是，这个算法的实现有很多任意性，比如，由于处理规则的顺序不同，或者处理规则中条件属性的顺序不同，我们都可以得到不同的值约简结果，得到的规则集合就会有所不同。因此，我们往往需要一些启发式知识来指导这一过程的进行。8.2.2归纳值约简算法我们在7.3.3一节中对归纳属性约简进行了介绍，这里对归纳值约简加以讨论。由核值的定义，求得每个规则dx的核值属性，就可形成决策表的条件属性核值表。但是，这样做的工作量太大。为了介绍归纳值约简算法，先看如下命题。命题8.2-1对相容知识表达系统S=(U,C,D,V,f)，则以属性a为核值属性的决策规则集合为core(a)={dx|x(U-posC-{a}(D))}。证明：aC，令B=posC-{a}(D)。对xU-B，如果规则dx：des([x]C-{a})des([x]D)为不相容决策规则，则必存在一决策规则dx’，使得dx’|(C-{a})=dx|(C-{a})，而dx’|Ddx|D，即x’[x]C-{a}，但x’[x]D，因此[x]C-{a}[x]D。125所以a为决策规则dx的核值属性，即core(a)={dx|x(U-posC-{a}(D))}。根据上述命题，可以方便地求取任意条件属性a的core(a)，从而得到决策表的条件属性核值表。在此基础上，我们来计算决策规则属性值的简化。令U/D={y1,y2,,yn}表示论域U上由决策属性划分的决策类集，对每一个决策等价类，定义决策规则类DRC为DRC(y)={dx:des([x]C)des([x]D)|xU且[x]Cy}，yU/D。求解知识表达系统决策表的最小决策算法，可通过分别求解各个决策类的最小决策算法来实现。各决策类的最小决策算法则通过删除决策规则类中决策规则的冗余属性值及冗余规则来实现。用core(y)，yU/D表示决策类y的核值属性集，core(dx)表示决策规则dx的核值属性集，则有core(y)C，core(dx)C，且)()()(yDRCdxxdcoreycore。下面给出求取决策类y的最小决策算法步骤：1）任取dxDRC(y)；2）如果yxxdcore)(][，则输出决策规则dx:)()(]/[)()(),]([)]([xxdcoreDdcorexyDRCyDRCxdesxdes，转9）；其中，)(]/[)()(xdcorexyDRCyDRC表示从DRC(y)中删除规则dx’:des([x’]C)des([x’]D)，这里，x’)(][xdcorex。3）令A1=core(y)-core(dx)，A2=C-core(y)，在测度函数w(a)=|posC-{a}(D)|/|U|下对A1、A2中元素排序，得有序集OA1、OA2，则有序集OA=OA1OA2且|OA|=m，OA的m个有序幂子集分别为T1(OA)，T2(OA)，，Tm(OA)，相应的元素个数为n1，n2，，nm。4）j=1；5）i=1；1266）令B=core(dx))(OATij，如果[x]By，输出dx:des([x]B)des([x]D)，BxyDRCyDRC]/[)()(，转9）；7）i=i+1，如果inj，转6)；8）j=j+1，如果jm，转5)；9）如果DRC(y)，转1）；10）结束。根据上述步骤，依次求得各决策类yU/D的最小决策算法，就可以得到整个决策表的最小决策算法。8.2.3启发式值约简算法分析最小值约简，也可以从值核入手。算法输入：信息系统T（假定系统有n条记录，m-1个条件属性，1个决策属性）。算法输出：T的值约简T’。第一步对信息表中条件属性进行逐列考察。删除该列后，若产生冲突记录，则保留冲突记录的原该属性值；否则，如果有重复记录，则将重复记录的该属性值标记为“*”；对于其他记录，将该属性值标记为“？”。For(j=1Tom-1)For(i=1Ton){If))?)*(((,,TTTTTTkmimklililillkmljlikTTijij,;Elseif))?*((',TTTTklililillkjlik*,Tij;127Else?,Tij;}For(i=1Ton)TTimim,;第二步删除可能产生的重复记录，并考察每条含有标记“？”的记录。若仅由未被标记的属性值即可以判断出决策，则将标记“？”改为“*”；否则，将标记“？”修改为原属性值；若某条记录的所有条件属性均被标记，则标记“？”修改为原属性值。For(j=1Tom-1)For(i=1Ton){If?,Tij{If*))?((,,TTilillmlTTijij,;ElseIf))*?((,,TTTTTTkmimklililillkml*,Tij;ElseTTijij,;}}第三步删除所有条件属性均被标记为“*”的记录及可能产生的重复记录（假定Card(T’)=n’）。第四步如果两条记录仅有一个条件属性值不同，且其中一条记录该属性被标记为“*”，那么，对该记录如果可由未被标记的属性值判断出决策，则删除另外一条记录；否则，删除本记录。Foreachtuple(i)inT’{If))(*(,,,,,TTTTTkjijjilklillkljml{If))*)(((,,,TTTTTimhmijhjijjhmj128删除记录k;Else删除记录i;}ElseIf))(*(,,,,,TTTTTkjijjklklillkljml{If))*)(((,,,TTTTTkmhmkjhjkjjhmj删除记录i;Else删除记录k;}}经过上述值约简之后得到的新信息表，所有属性值均为该表的值核，所有记录均对应为一条决策规则。8.2.4基于决策矩阵的值约简算法这里对Ziarko等人用于获取具有最大适应度（一般化）规则的值约简算法进行介绍，采用的是可变精度Rough集模型。对于一个属性约简结果信息表RED，令iX(i=1,2,,)、jX(j=1,2,,)表示关系R*(RED)的等价类，)(YPOSXREDi，)(YNEGXREDj，决策矩阵M=(Mij)定义为：),(),(,:)),(,(aXfaXfREDaaXfaMjiiij。也就是说，Mij包含了在等价类iX和jX上具有不同值的所有属性值对。给定等价类iX，将Mij的各个元素作为一个布尔表达式，决策规则集合可以表达为如下形式的布尔函数：)(ijjiMB。129可以看出，布尔函数Bi的基本蕴含实际上是属于正域)(YPOSRED的等价类iX的最大一般化规则。因此，通过发现所有决策函数Bi(i=1,2,,)的基本蕴含，就可以计算出正域)(YPOSRED的所有最大一般化规则。Ziarko等人将此算法成功地应用于一个水资源调度系统的设计中，有关内容可以参考本书10.1节。8.3缺省规则获取算法前面对属性约简和值约简的算法进行了介绍，经过约简，得到的结果就直接和决策规则对应，因此也就是得到了决策规则。对于决策表，我们也不一定需要通过约简来学习得到决策规则。下面介绍Skowron提出的一种通过投影得到缺省决策规则的算法。针对包含不一致决策情况的决策表，Skowron提出了相应的缺省规则获取方法：Skowron的缺省规则获取方法输入：决策表A*=(U,A*)，其中A*=(C*,D)，U是决策表中个体(或称为元素、样本)的全集，A*是每个个体的属性集，包括条件属性集C*和决策属性D；输出：缺省规则集。第一步：根据条件属性计算A*的不分明关系，即条件属性对决策表A*的划分：),(*CKE（),(*CKE属于)(*CINDU，)(,,1*CINDUK）。如果某个划分),(*CKE对特定决策(如Xj)的成员度超过一定阈值，则根据决策表A*的可辨识矩阵产生相应的缺省规则，即如果jrCKjCKjCKCEXEXE),(),(),(****,，则得到规则130),(),(*),(***,,:CKjCKjCKEXEDXDesCEDesR，其中，),(),(**CKjCKEXE是规则DXDesCEDesjCK,,*),(*的可信度因子。第二步：将决策表A*加入决策表集合Ψ,即Ψ={A*}。第三步：如果Ψ=Φ，则结束；否则，从Ψ中取出一个决策表A=(U,A)，计算其属性核CoreD(C)。通过删除某一核属性(如CCut)可以得到条件属性上的投影CPr=C-CCut，其中r=1,…,Card(CoreD(C))，C为该决策表的条件属性集合，CCut是删掉的核条件属性。对每个投影CPr作如下处理：①如果CPr=Φ，则不对该投影做任何操作；否则，做下面4步操作。②将投影得到的新决策表A’=(U,A’)加入Ψ(Ψ=Ψ{A’})，其中A’=(CPr,D)；③根据条件属性计算投影CPr的不分明关系，即条件属性对该投影决策表A’的划分),(PrCKE（),(PrCKE属于)(PrCINDU，)(,,1PrCINDUK）。④如果某个划分),(PrCKE对特定决策(如Xj)的成员度超过一定阈值，则根据决策表A’的可辨识矩阵产生相应的缺省规则，即如果jrCKjCKjCKCEXEXE),(),(),(PrPrPrPr,，则得到规则),(),(Pr),(PrPrPr,,:CKjCKjCKEXEDXDesCEDesR。⑤为每条缺省规则R’构造封锁该规则的事实：若存在Ei，Ei属于U/IND(C)，并