错误系统优化：约简规则研究

1.相关定义及性质

定义5.5.1　四元组S＝(U，G，f)是一个错误系统，其中U 表示对象的非空有限集合，称之为论域，G 表示规则的非空有限集合，G 的每一个规则子集P⊆G决定了一个二元不可区分关系IND(P)：IND(P)＝{(x，y)∈U×U|∀g∈G，f(x，g)＝f(y，g)}。

性质5.5.1　IND(P)是论域U 上的等价关系，且

性质5.5.2　令P，Q⊆G，若P⊆Q，则IND(Q)⊆IND(P)，关系IND(P)，P⊆G 构成了U 的一部分，用U|IND(P)表示，简记为U|P，U|IND(P)中的任一元素[x ]P 称为等价类。

令P，Q⊆G，U|IND(P)＝U|IND(Q)表示对于∀x∈U，有[x ]P⊆[x ]Q，且存在x∈U 有[x ]P⊂[x ]Q。

定义5.5.2　设S＝(U，G，f)是一个错误系统，g∈G，如果IND {G-(g)}＝IND(G)，则称规则g 在G 中是不必要的(多余的)，否则，称规则g 在G 中是必要的。

不必要的规则在错误系统中是多余的，如果将它从错误系统中去掉，不会改变该错误系统的分类能力，相反，若从错误系统中去掉一个必要的规则，则一定改变该错误系统的分类能力。

定义5.5.3　设S＝(U，G，f)是一个错误系统，如果每个规则g∈G 在G 中都是必要的，则称规则集G 是独立的，否则，称G 是相依的。对于相依的规则集来说，其中包含多余规则，可以对其约简。

定义5.5.4　设S＝(U，G，f)是一个错误系统，G 中所有必要的规则组成的集合成为规则集G 的核，记作Core(G).

定义5.5.5　设S＝(U，G，f)是一个错误系统，P⊆G，如果IND(P)＝IND(G)，P 是独立的，则称P 是G 的一个约简。可以证明核是所有约简的交集。

2.规则的信息量

将信息论中信息量的概念引入错误系统中。

定义5.5.6　设S＝(U，G，f)是一个错误系统，P⊆G，U|IND(P)＝{X 1，X 2，…，X n}。规则P 的信息量定义为

定理5.5.1　设S＝(U，G，f)是一个错误系统，P⊆G，若U|IND(G)⊂U|IND(P)，则I(P)＜I(G)。

证明：令(www.xing528.com)

因为U|IND(G)⊂U|IND(P)，所以n＜m。因此存在{1，2，…，m}的一个划分E＝{E 1，E 2，…，En}满足

定理5.5.2　设S＝(U，G，f)是一个错误系统，P⊆G，则U|IND(G)⊂U|IND(P)的充要条件是I(P)＝I(G)。

3.规则重要性的度量

定义5.5.7　设S＝(U，G，f)是一个错误系统，规则g∈G 在G 中的重要性定义为

特别地，当G＝{g}时，用sig(g)表示sigφ(g)：

其中，U|IND(φ)＝U{ }，I(φ)＝0。

上述定义表明规则g∈G 在G 中的重要性，由G 中去掉g 后引起的信息量变化的大小来度量。

性质5.5.4　规则g∈G 在G 中是必要的，当且仅当sig G-{g}(g)＞0。

性质5.5.5　Core(G)＝{g∈G，sig G-{g}(g)＞0}。

定义5.5.8　设S＝(U，G，f)是一个错误系统，C⊆G。任意规则g∈G-C 关于规则集C 的重要性定义为

sig C(g)＝sig C∪{g}(g)＝I(C ∪{g})-I(C)

上述定义表明规则g∈G-C 关于规则集C 的重要性，由C 中添加g 后所引起的信息量的变化大小来度量。sig C(g)的值越大，说明规则g∈G-C 关于规则集C 就越重要。可以把sig C(g)作为寻找最小规则约简的启发式信息，以减少搜索空间。

定理5.5.3　设S＝(U，G，f)是一个错误系统，P⊆G。若I(P)＝I(G)，且对任意g∈P 有sig P-{g}(g)＞0，则P 为G 的一个约简。

通过错误系统的规则约简，减少冗余规则，优化判别机制，提高判别效率及判别准确性。