基于粗糙集理论的多源信息决策知识约简研究(8)
下面将具体介绍几种决策表属性约简的算法[15]：这里，设初试决策表的条件属性集合为P={ai∣i=1,2,…,n},决策属性集合为D={d}。
3.4.1一般约简算法
对于决策表中的每一个条件属性ai，进行如下过程，直至条件属性集合不再发生变化为止[18]：
如果删除该属性ai，使得POS{P-{ai}}(D)= POSP(D)，则说明属性ai是相对于决策属性d不必要，从决策表中删除属性ai所在列并进行重复的行进行合并；否则，说明属性ai是相对于决策属性d是必要的，不能删除。
通过上述算法，我们能够得到决策表的一个属性约简结果，但不一定能够得到一个满意的属性约简结果。利用这个算法，我们也可以用搜索策略得到所有可能的属性约简结果。如果采用宽度有限策略，可以首先从原始决策表中删除一个属性，得到所有可能的包含n-1个条件属性的子决策表，然后再反复地在这些子决策表上进行上述操作，最终就可以得到所有可能的属性约简结果。同样，也可以采用深度优先策略。但不幸的是，由于这是一个组合爆炸问题，穷尽的搜索所需要的时间和空间代价都很高，实际计算属性约简的时候，往往采用某种启发式算法
3.4.2分明矩阵约简算法
3.3.2.1可辨识矩阵
Skowron[21] 提出的可辨识矩阵对于求取决策表的核属性是一种行之有效的方法，它也可以通过生成可辨识函数对属性进行约简。
定义3.2[18]令决策表系统为S=(U,A,V,f),A=P∪D是属性集合，子集P={ai∣i=1,2,…,n}和D={d}分别称为条件属性集和决策属性集，U={x1,x2,…,xn }是论域，ai(xj)是样本xj在属性ai上的取值。CD(i,j)表示可辨识矩阵中第i行j列的元素，则可辨识矩阵CD定义为：
{ ak∣aK (xi)≠aK (xj)}，d(xi)≠d(xj);
CD(i,j)=
0 ，d(xi)＝d(xj);
显然，可辨识矩阵是一个依主对角线对称的矩阵，在考虑可辨识矩阵的时候，只需要考虑其上三角（或下三角）部分就可以了。
根据可辨识矩阵的定义可知：当两个样本（实例）的决策属性取值相同时，它们所对应的可辨识矩阵元素的取值为0；当两个样本的决策属性不同且可以通过某些条件属性的取值不同加以区分时，它们所对应的可辨识矩阵元素的取值为这两个样本的条件属性集合，即可以区分这样个样本的条件属性集合；当两个样本发生冲突时，即素有的条件属性取值相同而决策属性的取值不同时，则它们所对应的可辨识矩阵中的元素取值为空集。显然，可辨识矩阵元素中是否包含空集元素可以作为判定决策表系统中是否包含不一致信息依据。
3.3.2.2算法的执行步骤
上面介绍了不可辨识矩阵的定义，那么下面我们来介绍基于可辨识矩阵和逻辑运算的属性约简算法的步骤[18]：
第1步 计算决策表的可辨识矩阵CD；
第2步 对于可辨识矩阵中的所有取值为非空集合的元素Cij（Cij≠0，Cij≠ø），建立相应的析取逻辑表达式Lij，其中： ；
第3步 将所有的析取逻辑表达式Lij进行合取运算，得一个合取范式L，即：
第4步 将合取范式L转换为析取范式的形式，得： ；
第5步 输出属性约简结果。析取范式的每个合取项就对应一个属性约简的结果，每个合取项中所包含的属性组成约简后的条件属性集合。
基于可辨识矩阵和逻辑运算的属性约简算法可以得到决策表的多有可能约简结果，它实际上是将对属性组合情况的搜索演变成为逻辑共识的化简，从而简化问题。但是我们可以看到，算法第二步建立的析取逻辑表达式Lij是很多的，甚至还会有重复，这将导致逻辑公式化简时的计算量增大。
上一篇：歌帝梵巧克力行业消费者行为分析