粗糙集理论最早由波兰数学家华沙理工大学教授Z.Pawlak于1982年提出, 是一种处理不精确、不一致、不完整等数据的数学工具, 同时对处理非常复杂的系统非常有效. 属性约简是粗糙集理论研究的核心内容之一, 其中基于区分矩阵的方法是现有的一种具有代表性的属性约简算法, 很多属性约简及其拓展的工作都以此为基础^[1–4]. 目前, 对现有算法的改进大多是提高算法的效率, 如文献[5–8], 或扩大其应用范围如文献[9–11], 而此次实现的改进则是针对数据而言. 由于现有的算法都只用于处理离散数据, 对于连续数据需要先进行离散化处理. 而本次实现的改进则取缔了离散化这一步骤, 可以对离散数据和连续数据统一进行处理.

泛逻辑是本世纪初由何华灿教授提出. 它基于二值逻辑, 多值逻辑和模糊逻辑, 并可以有效地处理人工智能中不精确、不完整和连续的数据, 不完备和模糊数据. 它可以被认为是一种柔性逻辑. 粗糙集理论和泛逻辑都可以用来处理不精确和不确定问题, 因此结合两个理论来取得更好的效果是可行和方便的^[12].

1 基本概念 1.1 粗糙集

定义1^[13]. 一个信息表可以描述为 $S = \{ U,A,V,f\} $ , 其中U是论域, $A = C \cup \{ d\} $ : C是条件属性集, d是决策属性. $V = Ua \in A$ 是属性的值域, 其中, V_a是属性a的值域. $f:U \times A \to V$ 是信息决策函数. 当 $d \ne \phi $ 时, 该信息表是一个决策信息表.

定义2. 不可分辨关系: 对于任意子集 $B \subseteq C \cup D$ , 记 $IND(B) = \{ (x,y) \in {U^2}|f(x,{a_k}) = f(y,{a_k}),\forall {a_k} \in B\} $ , 则 $IND(B)$ 是U上的不可分辨关系, 它产生的U上的划分为 $U/IND(B) = \{ {[x]_B}:x \in U\} $ , 其中, $[{x_B}] = \{ y:(x,y)$ $ \in IND(B)\}$ , 是x关于B的等价类^[1,12].

1.2 属性约简

在粗糙集信息系统中, 设R是一个等价关系簇, $I \in R$ , 如果 $IND\{ R - \{ I\} \} = IND\{ R\} $ , 则称I在等价关系簇R中是不必要的. 否则称I在等价关系簇R中是必要的. 若R中的每一个等价关系I都是必要的, 则称R是独立的. 属性约简就是在知识库分类能力保持不变的情况下, 删除冗余属性.

定义3. 对于信息系统 $S = \{ U,A,V,f\} $ , 若对于属性子集 $B \subseteq A$ 中每一个属性在B中都是必要的, 则称B是独立的; 若在属性子集 $B \subseteq A$ 中, 存在某一属性在B中是不必要的, 则称B是相依的.

定义4. 若 $D \subseteq B$ , 满足下面两个条件:

(1) D是独立的,

(2) $IND(D) = IND(B)$ .

则称D是B的一个约简. 记为: $D \in {\mathop{\rm Re}\nolimits} d(B)$ . 其中所有的必要关系组成的集合, 称为B的核, 记为: $Core(B)$ . 即: $Core(B) = \cap {\mathop{\rm Re}\nolimits} d(B)$ . 核是信息系统中的核心属性集, 是所有约简的公共部分.

1.3 区分矩阵

定义5^[5]. 设 $S = \left\{ {U,C \cup D} \right\}$ 为一个决策表, 其中C为条件属性集, D为决策属性集, $C \cap D = \phi $ 决策表S的区分矩阵被定义为 ${({C_{ij}})_{n \times n}}$ , 其中 $i,j = 1,2,\cdots, n$ .

${C_{i,j}}\left\{ {\begin{array}{*{20}{l}}{{a_k} \in C,{a_k}({X_i}) \ne {a_k}({X_j}) \wedge D({X_i}) \ne D({X_j})}\\{\Phi,D({X_i}) \ne D({X_j})}\end{array}} \right.$

(1)

2 算法原理

(1) 首先根据信息表S构造区分矩阵M, 按照公式(1)规则构造矩阵.

构造区分矩阵时, 需要将信息表中所有数据一一进行对比, 在此以第 $i,j$ 条数据举例说明具体构造过程: 首先判断第 $i,j$ 条数据决策属性值是否相同, 若相同, 即 $D({X_i}) = D({X_j})$ , 则将 ${m_{i,j}}$ 值记为空; 若决策属性值不同, 即 $D({X_i}) \ne D({X_j})$ , 此时从第一个条件属性开始比较这两条数据的所有条件属性, 若两条数据的条件属性a_k相等, 则不作处理; 若两条数据的条件属性a_k不相等, 则将a_k属性添加到 ${m_{i,j}}$ 值中. 由于每两条数据只需要单向比较一次即可, 所以结合矩阵的特点, 我们可以知道最后得到的区分矩阵是一个主对角线上元素为空的上三角矩阵或下三角矩阵.

(2) 根据区分矩阵构造区分函数, 规则如下:

1) 不为空的每项中的元素析取 $ \vee {m_{i,j}}$ , L_i,j= $\vee \left\{ {{a_i}|{a_i} \in {C_{i,j}}} \right\}$ , $\left( {{C_{i,j}} \ne 0,{C_{i,j}} \ne \phi } \right)$ .

2) 再将这些析取分量的逻辑表达式取合取 $ \wedge ( \vee {m_{i,j}})$ , $L = \wedge \left\{ {{L_{i,j}}|{C_{i,j}} \ne 0,{C_{i,j}} \ne \phi } \right\}$ .

(3) 删除包含关系: 将所有析取表达式合取得到的合取范式通常都很复杂, 甚至含有大量重复内容. 在这种情况下若是直接将合取范式转化为析取范式需要花费大量的时间和空间, 且十分不必要. 根据离散定律中幂等律和吸收律特点, 我们可以简化合取范式的内容, 有效地减少后续工作的工作量. 幂等律: $A \wedge A = A$ , 吸收律: $A \wedge (A \vee B) = A$ 拓展为包含关系可以将相等或较大的一项析取范式删掉, 且对最后结果没有影响. 证明过程参见定理1的证明. 所以, 我们可以在求出区分矩阵之后先将包含关系删除, 再对简化后的区分矩阵进行后续操作. 这一方法可以有效降低系统开销, 缩短程序运行时间, 提高算法运行效率.

将合取范式转化为析取范式, 即将L转化为析取范式L', $L' = \vee \{ L\} $ . 通过离散定律分配律 $ A \wedge (B \vee C) =$ $ (A \vee B) \wedge (A \vee C)$ 可以将合取范式转化为析取范式, 最终得到结果一个或多个约简集 ${\mathop{\rm Re}\nolimits} d(S)$ 以及所有约简集的交集——核 $Core(R)$ .

3 算法改进 3.1 改进原理

由于原始的算法只能用于处理离散的数据, 然而现实生活中我们收集的数据大部分都是既包含连续数据又包含离散数据. 因此对于这些数据, 我们需要先进行离散化处理再进行属性约简. 然而在使用等区间离散化方法时经常会出现以下问题: 两个边界值的数值非常接近, 但它们离散化后属于不同区域, 因此它们会被置于不同的等价集中. 这显然是不合理的, 这是人为的离散化带来的错误. 但是如果使用柔性逻辑等价关系就可以避免这种错误. 因为等区间离散化方法是将该属性划分为一定的区间数, 每个区间距离相同, 将位于同一区间的数据离散化为同一结果. 因此这种离散化方法对于边界值的处理会产生错误, 比如说位于不同区间但数值十分相近的两个数值, 很明显这两个数值应当离散化为相同的结果, 但是对于等区间离散化方法而言, 对于这一类数据的处理就会发生错误. 而使用柔性逻辑等价关系时, 使用的是中心等价公式: $Q(x,y,0.5) = {Q_1} = 1 - |x - y|$ . 此时判断x和y离散化结果是否相同时, 判断条件不是这两个数值是否位于同一区间, 而是这两个数值的差距是否超过固定的区间距离. 这样就可以避免边界值由于等区间离散化方法而产生的错误. 本文只讨论了最简单的离散化方法(等区间离散), 如果连续属性具有不同的特征, 并且使用不同的离散化方法来使数据离散, 我们也可以调整参数, 使用不同的等价公式来处理这些连续数据. 如果零级泛逻辑不足以覆盖使用, 我们也可以引入自相关参数k以获得更大的柔性.

改进算法利用了柔性逻辑中的中心等价公式. 在柔性逻辑理论中, 定义了一组连续而灵活的运算符集, 以表示广义相关性和广义自相关性^[14]. 在本文中, 我们只考虑广义相关性^[15], 而广义相关性可以被量化为广义相关系数, 一般用h表示, h在[0, 1]中连续取值.

使用T范数来表示AND关系, S范数来表示OR关系, 这是泛逻辑的数学基础. 广义相关性被定义为h和两个仅由h控制的两个函数, T生成元完整簇 ${F_0}(x,h) = {x^m}$ 和S生成元完整簇 ${G_0}(x,h) = 1 - {(1 - x)^m}$ . 把它们应用到AND运算模型和OR运算模型, 我们可以得到 $T(x,y,h)$ 和 $S(x,y,h)$ :

$T(x,y,h) = {(\max ({0^m},{x^m} + {y^m} - 1))^{1/m}},m \in R,h \in (0,1)$

(2)

$\begin{array}{c}\!\!\!\!S(x,y,h) = 1 - {(\max ({0^m},{(1 - x)^m} + {(1 - y)^m} - 1))^{1/m}},\\m \in R,h \in (0,1)\end{array}$

(3)

将T生成元完整簇 ${F_0}(x,h) = {x^m}$ 放入蕴含运算模型中, 我们可以得到 $I(x,y,h)$ :

$I(x,y,h) = {(\min (1 + {0^m},1 - {x^m} + {y^m}))^{1/m}}$

(4)

可以把它写成“ $ \to h$ ”.

将T生成元完整簇 ${F_0}(x,h) = {x^m}$ 放入等价运算模型中, 我们可以得到 $Q(x,y,h)$ :

$Q(x,y,h) = {(1 \pm |{x^m} - {y^m}|)^{1/m}}$

(5)

当 $h \ge 0.75$ 时为+, 否则为-. 我们可以把它写成“ $ \leftrightarrow h$ ”.

附: $m = (3 - 4h)/(4h(1 - h))$ , $h = (1 + m) - ({({(1 + m)^2} - 3m)^{1/2}})/(2m)$ .

等价关系 $Q(x,y,h)$ 根据h的不同会产生不同的结果, 其中较为特殊的4个运算如下.

(1) Zadeh等价:

$Q(x,y,1) = {Q_3} = ite\{ 1|x = y;\min (x,y)\} $

(6)

(2) 概率等价:

$Q(x,y,0.75) = {Q_2} = \min (x/y,y/x)$

(7)

(3) 中心等价:

$Q(x,y,0.5) = {Q_1} = 1 - |x - y|$

(8)

(4) 最大等价:

$Q(x,y,0) = {Q_0} = ite\{ x|y = 1;y|x = 1;1\} $

(9)

其中, 函数 $ite\{ a|b;c\} $ 表示条件b成立时函数值为a, 否则函数值为c.

柔性逻辑等价关系定义为 $ {Q_k}({X_i},{X_j},h) = $ ${(1 \pm |{X_{i,k}}^m - {X_{j,k}}^m|)^{1/m}}$ . h可以在不同的环境下进行调整. ${X_{i,k}}$ 和 ${X_{j,k}}$ 是 ${X_i}$ , ${X_i}$ 的属性a_k的值. 现在我们采用h=0.5, 所以中心等价 ${Q_k}({X_i},{X_j},0.5) = 1 - |{X_{i,k}} - {X_{j,k}}|$ 被用来修改原来的等价运算, 即利用柔性逻辑等价关系取代不可分辨关系. 由于柔性逻辑可以有效地处理人工智能中不精确、不完整和连续的数据, 因此将柔性逻辑与粗糙集相结合, 对离散数据和连续数据统一进行处理. 对于不可分辨关系, 可以简单理解为: 在分类过程中, 相差不大的个体被归于同一类, 这些个体的关系就是不可分辨关系. 在这个算法中, 不可分辨关系的用处就是将所有数据划分成不同的等价类. 而柔性逻辑等价关系则可以使用统一的方法将所有的属性划分成基于柔性逻辑的等价类. 在文献[12]中有详细的证明: 可以证明不可分辨关系P被包含在新的柔性逻辑等价关系Q中, 即 $P \to Q\text{且}U/IND(P) \subseteq U/IND(Q)$ .

使用柔性逻辑中的中心等价公式:

$ Q(x,y,0.5) = {Q_1} = 1 - |x - y|$

由于x, y的取值区间只能为[0, 1], 所以将公式转化为:

$ {Q_k}({x_i},{x_j},0.5) = 1 - |{x_{i,k}} - {x_{j,k}}|/({b_k} - {a_k})$

其中 $[{a_k},{b_k}]$ 为值域. 下文将介绍公式具体应用.

构造区分矩阵 ${({M_{ij}})_{n \times n}}$ 矩阵的条件修改如式(10), 其中 $i,j = 1,2,\cdots,n$

${C_{i,j}}\left\{ {\begin{array}{*{20}{l}}{{a_k} \in C,Q({X_i},{X_j},0.5) \le 1 - \alpha \wedge D({X_i}) \ne D({X_j})}\\{\Phi,D({X_i}) \ne D({X_j})}\end{array}} \right.\!\!\!\!\!$

(10)

与改进前的算法相比较, 改进后算法只是将构造区分矩阵的条件由公式(1)改为公式(10).公式(10)主要描述了构造区分矩阵的规则, 规则如下: 首先判断X_i和X_i的决策属性值是否相同, 若相同则将该矩阵的i行j列置空, 若其决策属性值不同, 则依次计算 $Q({x_i},{x_j},0.5)$ 的结果, 将该结果与参数 $1 - \alpha $ 进行比较, 若该结果小于等于 $1 - \alpha $ , 则将该属性加入到该项中, 若大于 $1 - \alpha $ , 则不将该属性加入该项. 公式(1)与公式(10)的区别在于: 在判断条件属性是否加入该项时, 公式(1)是对离散化后的结果直接进行判断, 等于或不等关系. 而公式(10)则直接将离散数据或连续数据根据中心等价公式进行计算, 再将计算结果与 $\alpha $ 值进行比较. 其实这两种判断条件直接体现出了不可分辨关系和柔性逻辑等价关系的区别.

3.2 实例说明

在实现区分矩阵属性约简算法时, 通常需要先将原始数据离散化, 再对离散数值进行属性约简. 现在提出一种利用柔性逻辑等价关系替代原本的不可分辨关系, 省略离散化这一过程. 这一改进使用公式(8), 只针对等区间离散化这一方法进行改进.

为了完整的研究算法, 现引入一个覆盖算法涉及到的全部步骤的气象表, 如表1. 表中数据后的小括号内容表示对应的离散化后的结果.

表中存在2个连续属性, 分别为a₂和a₃. 将a₂划分为3个区间, 分别为: [6, 19), [19, 28), [28, 39], 对应离散值为3, 2, 1. 将a₃划分为2个区间, 分别为:[28, 55), [55, 82), 对应离散值为2, 1.

传统的区分矩阵属性约简算法大致分为3步:

1) 首先根据信息系统S构造区分矩阵M(S);

2) 根据区分矩阵构造区分函数;

3) 计算区分函数, 将合取范式转化为析取范式.

改进的算法对代码改动较小, 只需在构造区分矩阵时将原来的不可分辨关系判断条件改为柔性逻辑等价关系的判断条件即可.

改进前后构造的区分矩阵结果略有不同. 分析这些不同, 主要有以下两种情况:

1) 改进后的矩阵某一项增加了某一属性: 如X_{6, 9}改进前的内容为a₁a₄, 改进后为a₁a₃a₄. 针对a₃属性进行分析, 湿度52%和28.5%离散化后均为2.所以改进前区分矩阵该项的内容中并不包括a₃属性. 但是52%和28.5%均属于边界值, 虽然同属一个区间, 但实际差距还是很大的. 因此改进后的算法更合理.

2) 改进后的矩阵某一项删除了某一属性. 如X_{1, 4}改进前的内容为a₁a₂, 改进后为a₁. 针对a₂属性进行分析, 温度32和25离散化后分别为1和2.所以改进前区分矩阵该项的内容中包括a₃属性. 但是32和25均属于边界值, 虽然属于不同区间, 但实际差距不大的. 因此改进后的算法更合理.

对改进前后的算法效率进行比较, 发现: 改进后的算法效率与改进前的算法效率几乎持平, 甚至在数据量逐渐增多的情况下, 改进后的算法效率要低于改进前的算法效率. 而且, 改进后的算法效率在构建区分矩阵部分所消耗的时间远大于改进前的算法. 由于机器限制, 只比较了具有5个属性的数据表在100~900, 1000~7000条数据等不同情况下的运行时间. 实验结果如表4和表5.

测试硬件环境: 联想PC, 1.90 GHZ, 内存2.0 GB, 测试软件环境: Microsoft Windows7 旗舰版, 编程语言: Java, 开发环境: MyEclipse Professional 2014.

4 结论与展望

本文实现了基于区分矩阵的属性约简基础算法, 并实现了利用柔性逻辑对该算法的改进, 将改进前后的算法进行了内容和效率两方面的对比并得出结论. 但是本文使用的柔性逻辑等价关系只针对等区间离散化方法, 对于其他的离散化方法并不适用, 因此今后的研究方向是利用柔性了逻辑对其他的离散化方法进行改进, 将柔性逻辑和粗糙集理论做一个更好的统一.