前面讨论了粗糙集理论的基础知识，这一部分将讨论知识表达系统的一种——决策表的知识约简算法。
决策表的基本概念
决策表的定义
决策表是知识表达系统的一种，关于知识表达系统的定义可以参考上篇blog，这里不再赘述，主要理解一下决策表的不同的特点：
$A = C \cup D$，其中C称为条件属性集，每个C中的元素称为C的一个简单属性；D称为决策属性集，且有$C \cap D = \varnothing \, C \ne \varnothing \, D \ne \varnothing$。
当$IND(C) \subseteq IND(D)$时，我们称决策表是相容的，因为不存在条件属性一致但是决策属性不同的样本。
决策规则
给定一个决策表$DT = (U,C \cup D,V,f)$，令$X \in U/IND(C) , Y \in U/IND(D) , \forall x \in X , des(X) = \bigcap_{\forall \alpha \in C}(\alpha,\alpha(x))$表示等价类X的描述；$\forall y \in Y , des(Y) = \bigcap_{\forall \beta \in D}(\beta,\beta(Y))$表示等价类Y的描述，则定义：
为从X到Y的决策规则。因为$IND(C) \subseteq IND(D)$，所以我认为上述公式应该满足$X \subseteq Y$。
决策表的属性约简算法
盲目删除属性约简算法
盲目删除算法的基本思路是：首先任意选择一个条件属性$\alpha_{i} \in C$，如果从决策表中删除该条件属性$\alpha_{i}$使得相对于D的正域没有改变，则说明属性$\alpha_{i}$是C中相对于决策D不必要的，从决策表中删除该属性以及其对应的属性值，然后继续重复上述步骤，直至不能删除其中的任一个元素为止，这时当前的条件属性集就是决策表的一个相对于D的属性约简。
对应的算法流程如下：
输入：$DT = (U,C\cup D,V,f)$
输出：DT的一个相对约简B，$B \in RED_{D}(C)$
(1) 令B = C
(2) $\forall \alpha \in C$，若$\alpha \in B$，则令$Mark(\alpha) = 0$，否则令$Mark(\alpha) = 1$
(3) 任选一个$\alpha \in B$，且$Mark(\alpha) = 0$，令$Mark(\alpha) = 1$，如果有
则从B中删除条件属性α，即$B \Leftarrow B-\{\alpha\}$，转到(2)，否则，转到(4)
(4) 若$ \exists \alpha \in B$ 且$ Mark(\alpha) = 0$，转到(3)，否则输出$B \in RED_{D}(C)$，算法结束。
盲目算法虽然可以得到一个相对约简，但是不一定能够得到一个满意的相对约简，即约简结果存在很大的随机性，当然也可以采用搜索策略得到所有可能的约简结果，然后验证是否属于$RED_{D}(C)$，但是搜索往往是一个组合爆炸问题，代价很高，效果并不理想。
基于Pawlak属性重要度的属性约简算法
首先讨论一下如何“启发式”的计算条件属性的重要度：给定一个DT，$B \subseteq C , \alpha \in C$，定义
为条件属性α对条件属性集B相对于决策属性D的重要度，因为分母是定值，所以计算的时候经常省略分母。
事实上，我们还可以“启发性”的定义各种各样的属性重要度，它在启发式属性约简算法的构造中占有重要地位，如果重要度函数定义的合理，则可以提高决策表属性约简算法的效率。
对应的算法流程如下：
输入：$DT = (U,C\cup D,V,f)$
输出：DT的一个相对约简B，$B \in RED_{D}(C)$
(1) 计算C相对于D的核$CORE_{D}(C)$
(2) 令$B = CORE_{D}(C)$，如果$pos_{B}(D) = pos_{C}(D)$，转到(5)
(3) 取$\forall c_{i} \in C-B$，计算属性重要度$sig(c_{i},B;D)$，求得$c_{m} = argmax_{c_{i} \in C-B}sig(c_{i},B;D)$，若同时存在多个属性满足最大值，则从中选取一个划分集合最少的属性作为$c_{m}$，令$B = B\cup \{c_{m}\}$
(4) 如果$pos_{B}(D) \ne pos_{C}(D)$，则转到(3)，否则转到(5)
(5) 输出 $B \in RED_{D}(C)$，算法结束。
基于差别矩阵的决策表的属性约简算法
差别矩阵的定义
决策表的差别矩阵：设DT是一个决策表，其中论域U是对象的一个非空有限集合，$U=\{x_{1},x_{2},…,x_{n}\},|U| = n$，则定义：
为决策表的差别矩阵，矩阵元素的取值满足如下关系：
其中如果决策属性D对应相等的两个对象，我们没有必要研究它们存在的差异，所以对应的差别矩阵值为“$-$”；如果存在决策属性值D不同，但是条件属性C值相同的两个对象，那么该决策表一定是不相容的；只有那些决策属性值不同的对象间的不同条件属性才是我们应该研究的重点。
利用差别矩阵计算核
在一个相容决策表中，决策表的相对D核等于该决策表的差别矩阵中所有简单属性(单个属性)元素组成的集合，即：
证明：因为删除上述公式中的属性α，就无法正确分类对象$x_{i},x_{j}$，即属性α在C中是绝对必要的，这是充分条件；如果$CORE_{C}(D)$存在这之外的元素，假设为属性β，删除β不会导致差别矩阵的变化，即无法改变C的对象区分能力，所以β是不必要的，所以不存在这样的β，这是必要条件。
利用差别矩阵计算相对约简
$\forall B \subseteq C$，若B满足如下两个条件：(1)$\forall c_{ij} \in M_{n \times n}$，当$ c_{ij} \ne \varnothing , c_{ij} \ne -$时，都有$B \cap c_{ij} \ne \varnothing $，(2)B是相对于D独立的。那么B是决策表的一个相对约简。
证明：由条件(1)可得，属性簇B可以区分所以的决策属性D不同的论域元素$x_{i}$，即有$pos_{IND(B)}(D) \wedge pos_{IND(C)}(D)$成立，又因为$B \subseteq C$，所以必有$pos_{IND(C)}(D) \wedge pos_{IND(B)}(D)$，由此证明得到$pos_{IND(B)}(D) = pos_{IND(C)}(D)$。同时配合条件(2)的独立性，可得B是C上相对于D的一个约简。
最后给出基于Skowron(差别矩阵的提出者)差别矩阵的决策表属性约简算法流程：
输入：$DT = (U,C\cup D,V,f)$
输出：DT的所有相对约简B，$B \in RED_{D}(C)$
(1) 根据差别矩阵的定义，写出$M_{n \times n}$，因为差别矩阵存在对称性，所以一般写出下(上)矩阵即可
(2) 搜索差别矩阵的所有元素，若没有∅ ，则转到(3)，反之则为不相容决策表，退出算法
(3) 搜索决策表差别矩阵中的所有单属性元素，求并得到$CORE_{D}(C)$
(4) 求出所有包含$CORE_{D}(C)$的可能的属性集合，判断是否满足1、$\forall c_{ij} \in M_{n \times n}(DT)$，当$c_{ij} \ne \varnothing$时，是否有$B \cap c_{ij} \ne \varnothing$，以及2、B是否是独立的。若满足上述两个条件，则令$RED_{D}(C) = RED_{D}(C) \cup \{B\}$
(5) 输出$RED_{D}(C)$，算法结束。
该算法还有一个变种，即基于Skowron差别矩阵和属性选择的决策属性约简算法
输入：$DT = (U,C\cup D,V,f)$
输出：DT的一个相对约简B，$B \in RED_{D}(C)$
(1) 求差别矩阵$M_{n \times n} = (c_{ij})_{n \times n}$
(2) 计算决策表的相对核$CORE_{D}(C)$，令$B = CORE_{D}(C)$
(3) 对任意的$c_{ij}$，如果$c_{ij} \cup B \ne \varnothing$，则 $c_{ij} = \varnothing$
(4) 对任意的$c_{ij}$，如果都有$c_{ij} = \varnothing$，额转到(6)，否则转到(5)
(5) 统计当前差别矩阵中每个属性出现的次数，选取出现次数最多的元素为$\alpha_{m}$，令$B = B \cup \{\alpha_{m}\}$，转到(3)
(6) 输出 $B \in RED_{D}(C)$，算法结束。
该变种算法属于一种启发式的思路，即“自下而上”的构造集合B，并在每步中选取最重要的——最有可能属于B的元素加入B，并验证新的集合B是否满足相对约简的条件。
决策表的值约简算法
给定一个决策表$DT = (U,C\cup D,V,f)$，经属性约简后得到一个相对约简的关系数据表$T(B) = (U_{B},B\cup D,V,f)$，将表T(B)中的每一个样本视为一条决策规则，这样T(B)就转换为一个决策规则集，在此基础上进行属性值的约简，得到抽象程度更高的决策规则。
下面介绍一个最简单的属性值约简算法，即决策表的盲目删除值约简算法：
输入： $T(B) = (U_{B},B\cup D,V,f)$
输出： 规则集T(B)关于决策属性D的完全简化的一组规则集(值约简)$R \in \widehat{RED_{D}(C)}$
(1) 设
(2) 对于规则集合${r_{i}| 1 \le i \le |U_{B}|}$中的每条规则$r_{i}$，如果从$r_{i}$中删除$(\alpha_{j},\upsilon_{ij})$，其余的规则也同时删除相同的列，及条件属性$\alpha_{j}$所在的列后，不会产生与$r_{i}$不相容的规则，则称属性$\alpha_{j}$下的值$\upsilon_{ij}$是不必要的，反之则为必要的，不能删除。接着上面的结果，继续删除决策规则$r_{i}$中不同属性下的其他值，直至获得规则$r_{i}$的一个完全约简规则$r_{i}^{}$为止，然后令$R \Leftarrow R \cup \{r_{i}^{}\}$，用上述的方法遍历所有的决策规则
(3) 输出$R \in \widehat{RED_{D}(C)}$
这种方法得到的结果存在很大的随机性，并不能保证得到的是一个满意的约简。通常需要一些启发式的知识来指导这一过程，比如归纳值约简算法、基于决策矩阵的决策表值约简算法、属性值增量约简算法等。