c) 选择使SGF(p,B,D)最大的属性(当同时有两个以上的属性达到最大值时，选取断点个数最少的)，假设是p,则将p插入到B的头部。如果|A|=|B|，转step;否则，转b);
Step3: 对每个属性aj ∈A 进行下面的过程：
Step4: 对属性aj 中的每一个断点cj ,考虑它的存在性,把决策表中与cj 相邻的两个属性值的较小值改为较大值,如果决策表不引起冲突,则Caj = Caj \{cj} ;否则,把修改过的属性值还原。
Step5:此时CUT={ Ca1，Ca2，…，Cak }即为所求的断点集,同时得到离散化后的决策表。
该算法判定每一个断点存在的必要性,去掉冗余的断点,简化了决策表,易于生成更一般的决策规则.由于离散化过程始终不改变决策表的不可分辩关系，因此算法得到的新决策表仍然是一致的.由于断点的判定是从它所属的条件属性相对于决策属性的相对熵由大到小（也即属性重要性由小到大）的顺序进行的,所以,属性重要性较小的属性的断点被淘汰的概率更大,从而避免了从重要性较大的属性中去掉过多的断点,提高了决策表的分类能力.这个离散化过程同时也是属性约简的过程(如果一个属性的所有断点都被去掉了,就意味着这个属性是冗余的,可以从决策表中去掉)。
3.2 算法的时间复杂性
(1) 求一个属性的候选断点集，要经过排序和求平均，其时间复杂性为O(n2) , 所以Step1时间复杂性为O(kn2) ;
(2) 计算相对熵E(D|ai),属性重要性SGF(p,B,D)的时间复杂性为O(kn2) ,对属性重要性SGF(p,B,D)进行排序的时间复杂性为klogk , 所以Step2时间复杂性为O(kn2) ;
(3) 把决策表中与cj相邻的两个属性值的较小值改为较大值,检验决策表是否引起冲突的时间复杂性为O(n2),所以完成Step3、Step4的时间复杂性为O(kn2)。
因此，整个算法的时间复杂性为O(3kn2)。
3.3举例
设原始决策表如表1所示，其中，决策属性A={a,b},条件属性D={d}.显然有：
U/{d}={{1,4,6,7,8},{2,3,5}}={Y1,Y2};
U/{a}={{1},{2},{3,6},{4,5},{7,8}}={X1,X2,X3,X4,X5};
U/{b}={{1,5},{2},{3,7,8},{4,6}}={Z1,Z2,Z3,Z4};
计算属性重要性，开始B=Φ， 
所以SGF(a,D)=E(D)-E(D|a)>E(D)-E(D|b)=SGF(b,D)
对决策表1，其候选断点集为：Ca={0.8,1.1,1.4,1.8,3}; Cb={0.9,2,4}
由上面的计算知SGF(b,D)<SGF(a,D),所以从属性b开始：首先考虑断点0.9,它有相邻属性值为0.8和1,把属性值0.8改为1后，不引起决策表的冲突，则断点0.9是多余的；接着考虑断点2，它的相邻属性值为1和3；当把1改为3时，实例4和5将会冲突，这说明断点2是保持决策表的不分明关系所必须具有的断点，故应该保留；最后考虑断点4, 它的相邻属性值为3和5, 把属性值3改为5后，不引起决策表的冲突，则断点4是多余的；得到的决策表为表2
表1 原始决策表 表2 属性b离散化后的决策表
|
U |
a |
b |
D |
|
1 |
0.6 |
3 |
1 |
|
2 |
1 |
0.8 |
0 |
|
3 |
1.2 |
5 |
0 |
|
4 |
1.6 |
1 |
1 |
|
5 |
1.6 |
3 |
0 |
|
6 |
1.2 |
1 |
1 |
|
7 |
2 |
5 |
1 |
|
8 |
4 |
5 |
1 |
|
U |
a |
b |
D |
|
1 |
0.6 |
5 |
1 |
|
2 |
1 |
1 |
0 |
|
3 |
1.2 |
5 |
0 |
|
4 |
1.6 |
1 |
1 |
|
5 |
1.6 |
5 |
0 |
|
6 |
1.2 |
1 |
1 |
|
7 |
2 |
5 |
1 |
|
8 |
4 |
5 |
1 |
同样对属性a的断点Ca={0.9,1.15,1.35,1.5,2.2}进行判断，得决策表为表3，最终得到的决策表为表4。
表3 属性a离散化后的决策表 表4 最终的决策表
|
U |
a |
b |
D |
|
1 |
1 |
5 |
1 |
|
2 |
1 |
1 |
0 |
|
3 |
1.6 |
5 |
0 |
|
4 |
1.6 |
1 |
1 |
|
5 |
1.6 |
5 |
0 |
|
6 |
1.6 |
1 |
1 |
|
7 |
4 |
5 |
1 |
|
8 |
4 |
5 |
1 |
|
U |
a |
b |
D |
|
1 |
0 |
1 |
1 |
|
2 |
0 |
0 |
0 |
|
3 |
1 |
1 |
0 |
|
4 |
1 |
0 |
1 |
|
5 |
1 |
1 |
0 |
|
6 |
1 |
0 |
1 |
|
7 |
2 |
1 |
1 |
|
8 |
2 |
1 |
1 |
4 结束语
提出的基于相对熵的离散化算法可在离散化数据的同时约简冗余的属性,而且保持决策表的一致性不变。数值离散化以后对属性表的所有数据作属性约简和值约减操作,最终获得简化的决策表，决策表的每一条记录就是一个决策规则.该算法易于理解，计算简单。
参考文献:
[1]Pawlak Z. Rough set theoretical aspects of reasoning about date[M] . Poland : Warsaw , 1991
[2]王国胤.Rough 集理论与知识获取[M].西安:西安交通大学出版社,2001.24-31,51.
[3]林仁炳,王基一.连续属性离散化算法的时间复杂性分析[J].计算机与现代化,2005,9: 40-42
[4]林镇飚,桂现才.粗糙集理论中决策表属性约简的信息量表示[J].广西师范学院学报, 2005,22(2): 35-38
[5]梁吉业,曲开社,徐宗本.信息系统的属性约简[J].系统工程理论与实践,2001,21(12): 76-80.
[6]JiYe Liang, Chin K.S, ChuangYin Dang,et al. A new mothod for measuring uncertainty and fuzziness in rough set theory. International Journal of General System. 2002,31(4):33-342
[7]王国胤,于洪,杨大春.基于条件信息熵的决策表约简[J].计算机学报,2002,25(7):759- 766
[8]桂现才,彭宏.决策表属性约简及其条件信息量表示[J].计算机工程与应用，2006,(待发表)
企业标准化体系的工作流管理系统的开发
登录方式的改进设计与实现