0 引言

粗糙集理论最初由Pawlak^[1]提出，它以各种信息系统、决策信息系统为研究对象，通过定义论域上的等价关系，把不可区分的对象组合在一起构成论域的划分，并通过属性约简^[2-3]来挖掘信息系统里的最简决策规则，达到知识发现的目的。随着粗糙集理论的不断发展，经典粗糙集理论的缺点日益明显，考虑经典粗糙集理论信息系统中的属性值都是符号数据的问题，以及日常生活很多数据都是有序的，如考试成绩、价格波动等，Greco等^[4]提出了一个基于优势关系的粗糙集模型，即优势粗糙集。该模型的研究对象为有序数据，如序信息系统、区间值序信息系统、直觉模糊值序信息系统等，它用优势关系代替经典粗糙集中的等价关系，构造近似空间达到知识发现的目的。

另外，传统粗糙集模型的研究对象为信息系统，它的每个对象、每个属性只能取唯一的值，称之为单尺度信息系统。然而，在实际的生活中，人们处理的数据可能是多层次、多尺度的。为此，Wu等提出了多尺度决策信息系统的概念，简称Wu-Leung^[5]模型，并研究了协调和不协调多尺度决策信息系统的最优尺度组合^[6-10]、知识获取^[11]的问题。接着，Li等在Wu-Leung模型的基础上提出了广义多尺度决策信息系统^[12]的概念，并给出了互补模型、格模型的算法求最优尺度组合和知识获取。随后，Huang等^[13]、Wu等^[14]分别研究了在协调和不协调的情况下，决策属性也具有多尺度的广义多尺度决策信息系统的最优尺度选择问题，尤其在不协调中引入广义决策函数的方法值得称赞。

上述针对广义多尺度决策信息系统的研究主要基于等价关系^[5-14]的，而基于优势关系^[15-16]来研究广义多尺度序决策信息系统的最优尺度组合很少。尽管张嘉茹等^[15]和杨烨等^[16]分别研究了决策属性为多尺度的协调、不协调广义多尺度序决策信息系统的最优尺度选择问题和知识获取问题，但文献[16]所提出的广义决策未像文献[14]一样给出构造新的协调广义多尺度决策信息系统的方法，它重新定义了协调和最优尺度选择，不是传统最优尺度选择定义的延续。另外，所定义的广义决策最优尺度很大概率会是最细尺度，从代价来看未必是最优的。这些是当前基于优势关系的不协调广义多尺度序决策信息系统研究的不足。

为了弥补上述不足，本文在文献[13-18]和传统协调和最优尺度定义基础上，引入更加有效的广义决策并消除不协调性，构造协调广义多尺度序决策信息系统，并借助集值优势矩阵来讨论研究不协调广义多尺度序决策信息系统的最优尺度组合、属性约简和知识获取问题。最后，通过实验验证了所提广义决策最优尺度组合的有效性。

1 基础知识

定义1^[19]  信息系统是一个二元组(U, A)，其中U={x₁, x₂, …, x_n}是一个非空有限对象集，A={a₁, a₂, …, a_m}是一个非空有限属性集，$\forall a \in A$，亦表示映射a: U→V_a，V_a为属性a的取值域。

定义2^[15]  设L为非空集合，≤为L上的二元关系，若下面条件1)~4)成立，称二元组(L, ≤)为一个全序集。

1) 自反性：$\forall x \in L, x \leqslant x$；

2) 反对称性：$\forall x, y \in L, x \leqslant y, y \leqslant x \Rightarrow x=y$；

3) 传递性：$\forall x, y, z \in L, x \leqslant y, y \leqslant z \Rightarrow x \leqslant z$；

4) ≤是线性序：$\forall x, y \in L, x \leqslant y \text { 或 } y \leqslant x$。

如果一个信息系统(U, A)属性a的取值域V_a是全序集(对不同a，在没有歧义的情况下，本文均用≤或者≥表示对应的线性序，且假设属性值域均为实数)，那么这个属性就称为一个准则。如果信息系统(U, A)的所有属性都是准则，则该信息系统(U, A)称为一个序信息系统。若决策属性d∉A也是一个准则，称(U, A∪{d})是一个序决策信息系统。

对于一个序决策信息系统(U, A∪{d})，(U, A∪{d})中的广义决策^[17-18]为

$ \delta_A(x)=\left[l_A(x), u_A(x)\right]，$

其中：

$ \begin{aligned} l_A(x) & =\min \left\{d(y): y R_A^{\geqslant} x, y \in U\right\}, \\ u_A(x) & =\max \left\{d(y): x R_A^{\geqslant} y, y \in U\right\}。\end{aligned} $

广义决策反映了关于准则集A对象x根据优势原则可能属于决策类的区间，常用于不协调序决策信息系统中的分类和约简^[17-18]。u_A(x)和l_A(x)为该区间的上、下界。若$\forall x \in U, l_A(x)=u_A(x)$均成立，则称序决策信息系统是协调的；否则，称为不协调的。

2 广义多尺度序决策信息系统 2.1 集值优势矩阵

定义3  设(U, A∪{d})是一个序决策信息系统，U={x₁, x₂, …, x_n}, 记

$ \begin{aligned} & D_{i j}=\left\{a \mid a\left(x_i\right) \geqslant a\left(x_j\right), a \in A \cup\{d\}\right\}, \\ & i, j=1, 2, \cdots, n, \end{aligned} $

则称D_ij为x_i支配x_j的集值优势集，即D_ij刻画了x_i不比x_j差的准则集合，称D=(D_ij)_n×n为(U, A∪{d})的集值优势矩阵。

命题1  设(U, C)=(U, A∪{d})是一个序决策信息系统，如果$\exists i, j=1, 2, \cdots, n$, 使得{a₁, a₂, …, a_m}⊆D_ij, d∉D_ij成立，则称(U, A∪{d})是不协调的；否则，称(U, A∪{d})是协调的。

2.2 广义多尺度序决策信息系统

在现实生活中，很多属性值数据都是有序的，所以基于优势关系研究广义多尺度序决策信息系统的最优尺度是非常有意义的。下面介绍广义多尺度序决策信息系统的定义和相关性质。

定义4^[15]  对于全序集(L₁, ≤₁)和(L₂, ≤₂)，若映射g: (L₁, ≤₁)→(L₂, ≤₂)，∀x, y∈L₁，有x≤₁y⇒g(x)≤₂g(y)，则称映射g为保序的。

定义5  广义多尺度序信息系统是一个二元组S=(U, C)，其中: U={x₁, x₂, …, x_n}是一个非空有限的对象集; C={a₁, a₂, …, a_m}是一个非空有限的属性集。若属性a_j有I_j个等级尺度，则一个广义多尺度序信息系统可以表示为$S=\left(U, \left\{a_j^k \mid k=1, \right.\right.\left.\left.2, \cdots, I_j, j=1, 2, \cdots, m\right\}\right)$，其中：$a_j^k: U \rightarrow V_j^k$是一个满射函数；V_j^k是属性a_j在第k个尺度下的值域；≤_j^k是V_j^k上的线性序，即(V_j^k, ≤_j^k)是一个全序集。对j=1, 2, …, m，1≤k≤I_j-1，存在一个保序的满射函数

$ g_j^{k, k+1}:\left(V_j^k, \leqslant_j^k\right) \rightarrow\left(V_j^{k+1}, \leqslant_j^{k+1}\right), $

使得$a_j^{k+1}=g_j^{k, k+1} a_j^k$，即

$ a_j^{k+1}(x)=g_j^{k, k+1}\left(a_j^k(x)\right), x \in U, $

$g_j^{k, k+1}$称为序信息粒度转换函数。

另外，称S=(U, C∪{d})是广义多尺度序决策信息系统，其中(U, C)是一个广义多尺度序信息系统，$d \notin\left\{a_j^k \mid k=1, 2, \cdots, I_j, j=1, 2, \cdots, m\right\}, d: U \rightarrow V_d$,是一个决策属性且(V_d, ≤_d)是全序集。

定义6^[5]  设S=(U, C)为一个广义多尺度序信息系统，若将条件属性a_j(1≤j≤m)限制在该属性的第l_j(1≤l_j≤I_j)个尺度下，记为L=(l₁, l₂, …, l_m)，则L称为S的条件属性的一个尺度组合。S的所有尺度组合记为$\varsigma=\left\{\left(l_1, l_2, \cdots, l_m\right) \mid 1 \leqslant l_j \leqslant I_j, \right.j=1, 2, \cdots, m\}$。

定义7^[5]  设S=(U, C)为一个广义多尺度信息系统，对于两个尺度组合$L_1=\left(l_1^1, l_2^1, \cdots, l_m^1\right) \in \zeta, L_2=\left(l_1^2, l_2^2, \cdots, l_m^2\right) \in \varsigma$。若$\forall j \in\{1, 2, \cdots, m\}$，都有l_j¹≤l_j²，则称尺度组合L₁比L₂细，记L₁≤L₂。若L₁≤L₂，且$\exists j \in\{1, 2, \cdots, m\}$，使得l_j¹l_j²，则称尺度组合L₁严格细于L₂，记L₁<L₂。

$ \begin{aligned} & \forall j \in\{1, 2, \cdots, m\}, L_1=\left(l_1^1, l_2^1, \cdots, l_m^1\right) \in \varsigma, \\ & L_2=\left(l_1^2, l_2^2, \cdots, l_m^2\right) \in \varsigma, \text { 定义 } \\ & L_1 \wedge L_2=\left(l_1^1 \wedge l_1^2, l_2^1 \wedge l_2^2, \cdots, l_m^1 \wedge l_m^2\right), \\ & L_1 \vee L_2=\left(l_1^1 \vee l_1^2, l_2^1 \vee l_2^2, \cdots, l_m^1 \vee l_m^2\right), \end{aligned} $

其中：$l_j^1 \wedge l_j^2=\min \left(l_j^1, l_j^2\right) ; l_j^1 \vee l_j^2=\max \left(l_j^1, l_j^2\right)$。那么

$ L_1 \leqslant L_2 \Leftrightarrow L_1 \wedge L_2=L_1 \Leftrightarrow L_1 \vee L_2=L_2, $

且($\varsigma $, ≤, ∧, ∨)是一个有界格，其中最大元为(I₁, I₂, …, I_m)，最小元为(1, 1, …, 1)。

显然，对于一个广义多尺度序决策信息系统，可以分解成$\prod\limits_{j = 1}^m {{I_j}} $个序决策信息系统且具有相同的决策属性d，也可以分解得到$\prod\limits_{j = 1}^m {{I_j}} $个不同的集值优势矩阵，即定义7中格结构的每个节点加上决策属性d对应于一个集值优势矩阵。

定义8^[5]  设S=(U, C∪{d})为一个广义多尺度序决策信息系统，L=(l₁, l₂, …, l_m)∈$\varsigma $为S的一个尺度组合，定义关于准则集C^L的优势关系$R_{C^L}^{\geqslant}$、对象x的优势类$[x]_{C^L}^{\geqslant}$为

$ \begin{aligned} & R_{c^L}^{\geqslant}=\left\{(y, x) \in U \times U \mid a_j^{l_j}(y) \geqslant a_j^{l_j}(x), \forall a_j^{l_j} \in C^L\right\}, \\ & {[x]_{c^L}^{\geqslant}=\left\{y \in U \mid a_j^{l_j}(y) \geqslant a_j^{l_j}(x), \forall a_j^{l_j} \in C^L\right\}=} \\ & \left\{y \in U \mid(y, x) \in R_{c^L}^{\geqslant}\right\}。\end{aligned} $

性质1  设$S=(U, C \cup\{d\})=\left(U,\left\{a_j^k \mid k=1,\right.\right.\left.\left.2, \cdots, I_j, j=1,2, \cdots, m\right\} \cup\{d\}\right)$为一个广义多尺度序决策信息系统，$Q_1=\left(K_1, d\right)=\left(k_1^1, k_2^1, \cdots, k_m^1, d\right), Q_2=\left(K_2, d\right)=\left(k_1^2, k_2^2, \cdots, k_m^2, d\right)$。若Q₁、Q₂、K₁、K₂对应的集值优势矩阵分别为D^Q₁、D^Q₂、D^K₁、D^K₂，则性质1)~4)成立。

1) $K_1 \leqslant K_2 \Rightarrow R_{C^{K_1}}^{\geqslant} \subseteq R_{C^{K_2}}^{\geqslant}, [x]{ }_{C^{K_1}}^{\geqslant} \subseteq[x]{ }_{C^{K_2}}^{\geqslant}$；

2) $\forall B \subseteq C \Rightarrow R_C^{\geqslant} \subseteq R_B^{\geqslant}$；

3) 如果$K_1 \leqslant K_2, a_j^{k_j^1} \in D_{i_1, i_2}^{K_1}\left(a_j^{k_j^1} \in D_{i_1, i_2}^{Q_1}\right)$，则$a_j^{k_j^2} \in D_{i_1, i_2}^{K_2}\left(a_j^{k_j^2} \in D_{i_1, i_2}^{Q_2}\right), i_1, i_2=1, 2, \cdots, n$；

4) $K_1 \leqslant K_2 \Rightarrow\left|D_{i_1, i_2}^{K_1}\right| \leqslant\left|D_{i_1, i_2}^{K_2}\right|, i_1, i_2=1, 2, \cdots, n$, 其中$\left|D_{i_1, i_2}\right|$表示集值优势矩阵中项D_{i1, i2}的元素个数。

3 不协调广义多尺度序决策信息系统的最优尺度组合

在本节中，基于优势关系引入广义决策，研究了不协调广义多尺度序决策信息系统中的最优尺度组合，并用于生成单尺度序决策信息系统和提取决策规则。

3.1 不协调广义多尺度序决策信息系统的广义决策

定义9  设$S=(U, C \cup\{d\})=\left(U, \left\{a_j^k \mid k=1, \right.\right.\left.\left.2, \cdots, I_j, j=1, 2, \cdots, m\right\} \cup\{d\}\right)$是一个广义多尺度序决策信息系统，L₁=(1, 1, …, 1)，如果存在i, j=1, 2, …, m, 使得$\left\{a_1^1, a_2^1, \cdots, a_m^1\right\} \subseteq D_{i j}^{C_1^{L_1} \cup\{d\}}, d \notin D_{i j}^{C^{L_1} \cup\{d\}}$成立，即序决策信息系统(U, C^L₁∪{d})不协调，则S被称为不协调的；否则，称S是协调的。

性质2  设$S=(U, C \cup\{d\})=\left(U, \left\{a_j^k \mid k=1, \right.\right.\left.\left.2, \cdots, I_j, j=1, 2, \cdots, m\right\} \cup\{d\}\right)$为一个广义多尺度序决策信息系统，$\forall L_1, L_2 \in \mathcal{\varsigma}, L_1<L_2$。如果S^L₁=(U, C^L₁∪{d})是不协调的，则S^L₂=(U, C^L₂∪{d})也是不协调的；如果S^L₂=(U, C^L₂∪{d})是协调的，那么S^L₁=(U, C^L₁∪{d})也协调。

证明  根据性质1易证。

由于L是最优尺度组合当且仅当L是协调的，且所有比L粗的尺度组合都不协调，则根据性质2可知，若最细尺度组合和决策属性d形成的序决策信息系统不协调，那么广义多尺度序决策信息系统S的所有尺度组合和决策属性d形成的序决策信息系统都不协调，则我们无法直接遍历S的尺度组合的格结构寻找最优尺度。于是，为了确定S的最优尺度组合，我们在给定尺度组合下，定义广义多尺度序决策信息系统的广义决策。

定义10  设

$S=(U, C \cup\{d\})=\left(U, \left\{a_j^k \mid k=1, 2, \cdots, I_j, j=\right.\right.1, 2, \cdots, m\} \cup\{d\})$是一个广义多尺度序决策信息系统，K=(L, d)=(l₁, l₂, …, l_m, d)，在诱导的序决策信息系统(U, C^L∪{d})中定义广义决策函数

$ \delta_{C^L}(x)=\left[l_{C^L}(x), u_{C^L}(x)\right], $

其中：

$ \begin{aligned} l_{c^L}(x) & =\min \left\{d(y): y R_{C^L}^{\geqslant} x, y \in U\right\} ; \\ u_{C^L}(x) & =\max \left\{d(y): x R_{C^L}^{\geqslant} y, y \in U\right\} 。\end{aligned} $

记

$ R_{\delta_{c^L}}^{\geqslant}=\left\{(y, x) \in U \times U \mid \delta_{c^L}(y) \geqslant \delta_{c^L}(x)\right\}, $

$R_{\delta_{c^L}}^{\geqslant}$表示广义决策δ_C^L诱导的优势关系，通过用广义决策δ_C^L替换(U, C^L∪{d})中的决策属性d，我们就能得到一个新的序决策信息系统(U, C^L∪{δ_C^L})。为了得到(U, C^L∪{δ_C^L})的集值优势矩阵，就需要定义广义决策δ_C^L的优势关系。在具体问题中，常采用3种方法定义区间值优势关系。

定义11  设w₁=[u₁, v₁], w₂=[u₂, v₂]，定义任意两个区间值的优势关系方法为

1) 下界偏好关系：[u₁, v₁]≤[u₂, v₂]⇔u₁≤u₂；

2) 上界偏好关系：[u₁, v₁]≤[u₂, v₂]⇔v₁≤v₂；

3) 直觉偏好关系：

$ \begin{aligned} & \quad\left[u_1, v_1\right] \leqslant\left[u_2, v_2\right] \Leftrightarrow \frac{1}{2}\left(u_1+v_1\right)<\frac{1}{2}\left(u_2+\right. \\ & \left.v_2\right) \text { 或 } \frac{1}{2}\left(u_1+v_1\right)=\frac{1}{2}\left(u_2+v_2\right) \text { 且 } \frac{1}{2}\left(v_1-u_1\right) \geqslant \\ & \frac{1}{2}\left(v_2-u_2\right) 。\end{aligned} $

定理1  如果采用上述3种方法定义区间值优势关系，则用广义决策δ_C^L替换(U, C^L∪{d})中决策属性d得到的序决策信息系统(U, C^L∪{δ_C^L})是协调的。

证明  采用定义11的1)定义区间值优势关系，即证

$ \forall x, y \in U, y R_{c^L}^{\geqslant} x \Rightarrow l_{c^L}(x) \leqslant l_{c^L}(y)。$

令

$ \begin{aligned} & H_1=\left\{d\left(z_1\right): z_1 R_{c^L}^{\geqslant} x, x, z_1 \in U\right\}, \\ & H_2=\left\{d\left(z_2\right): z_2 R_{c^L}^{\geqslant} y, y, z_2 \in U\right\} 。\end{aligned} $

由于$y R_{c^L}^{\geqslant} x \text {, 有 }[y]_{c^L}^{\geqslant} \subseteq[x]{ }_{c^L}^{\geqslant}$所以H₂⊆H₁，即min(H₁)≤min(H₂)，故l_C^L(x)≤l_C^L(y)。

同理可证，定义11的2)和3)定义区间值优势关系也成立。

综上，由定义11知，用广义决策δ_C^L替换(U, C^L∪{d})中的决策属性d得到的序决策信息系统(U, C^L∪{δ_C^L})是协调的。

记$G_\delta^L=\left(U, C \cup\left\{\delta_{C^L}\right\}\right)=\left(U, \left\{a_j^k \mid k=1, 2, \cdots, \right.\right.\left.\left.I_j, j=1, 2, \cdots, m\right\} \cup\left\{\delta_{C^L}\right\}\right)$。

显然，G_δ^L是由尺度组合L诱导生成的广义多尺度序决策信息系统，决策属性为δ_C^L，且G_δ^L是协调的。

定义12  设S=(U, C∪{d})是一个不协调的广义多尺度序决策信息系统，L=(l₁, l₂, …, l_m)∈$\varsigma $，L₁=(1, 1, …, 1)∈$\varsigma $。如果$\exists i, j=1, 2, \cdots, n$, 使得$\left\{a_1^{l_1}, a_2^{l_2}, \cdots, a_m^{l_m}\right\} \subseteq D_{i j}^{c^L \cup\{{\delta}_{c^{L_1}{ }^{}}\}}, d \notin D_{i j}^{c^L \cup\{{\delta}_{c^{L_1}{ }^{}}\}}$成立，则称(U, C^L∪{δ_C^L1})是广义决策不协调的；否则，称为广义决策是协调的。

定理2  设广义多尺度序信息系统G_δ^L=(U, C∪{δ_C^L})的集值优势矩阵为D^G_δL，K=(k₁, k₂, …, k_m)∈$\varsigma $。如果$\exists i, j=1, 2, \cdots, n$, 使得$\left\{a_1^{k_1}, a_2^{k_2}, \cdots, \right.\left.a_m^{k_m}\right\} \subseteq D_{i j}^{G_\delta^L}, \delta_{c^L} \notin D_{i j}^{G_\delta^L}$成立，则序决策信息系统(U, C^K∪{δ_C^L})不协调；否则，(U, C^K∪{δ_C^L})协调。

定理3  设$S=(U, C \cup\{d\})=\left(U, \left\{a_j^k \mid k=1, \right.\right.\left.\left.2, \cdots, I_j, j=1, 2, \cdots, m\right\} \cup\{d\}\right)$是一个不协调的广义多尺度序决策信息系统，L, K∈ $\varsigma $ 且L < K。如果(U, C^L∪{δ_C^L1})是广义决策不协调的，则(U, C^K∪ {δ_C^L1})也是广义决策不协调的；如果(U, C^K∪{δ_C^L1})是广义决策协调的，则(U, C^L∪{δ_C^L1})也是广义决策协调的。

定理3表明，给定一个不协调广义多尺度序决策信息系统S，若广义决策δ_C^L1与较粗尺度组合形成的序决策信息系统协调，那么它一定与较细尺度形成的序决策信息系统协调。这一结论将帮助我们在不协调的广义多尺度序决策信息系统定义和寻找最优尺度组合。

3.2 不协调广义多尺度序决策信息系统的最优尺度

定义13  设$S=(U, C \cup\{d\})=\left(U, \left\{a_j^k \mid k=1, \right.\right.\left.\left.2, \cdots, I_j, j=1, 2, \cdots, m\right\} \cup\{d\}\right)$是一个不协调的广义多尺度序决策信息系统，L₁=(1, 1, …, 1), L=(l₁, l₂, …, l_m)∈ $\varsigma $ 。若不存在i, j=1, 2, …, n, 使得$\left\{a_1^{l_1}, a_2^{l_2}, \cdots, a_m^{l_m}\right\} \subseteq D_{i j}^{G_\delta^{L_1}}, \delta_{c^{L_1}} \notin D_{i j}^{G_\delta^{L_1}}$成立，则序决策信息系统(U, C^L∪{δ_C^L1})是协调的，即称尺度组合L是S中广义决策协调的。如果尺度组合L是S中广义决策协调的，且∀L′=(l′₁, l′₂, …, l′_m)∈ $\varsigma $ , L < L′, L′都不是S中广义决策协调的，则称L=(l₁, l₂, …, l_m)∈ $\varsigma $ 是S的广义决策最优尺度组合，简称最优尺度组合。

由于条件属性a_j具有I_j个尺度，则$\varsigma $中所有尺度组合的数量为$\prod\limits_{j = 1}^m {{I_j}} $每个尺度组合加上决策属性δ_C^L1可代表一个集值优势矩阵。又因为($\varsigma $, ≤, ∧, ∨)是一个有限格，所以可以从上到下搜索格结构($\varsigma $, ≤, ∧, ∨)求最优尺度组合。L=(l₁, l₂, …, l_m)∈$\varsigma $是S的最优尺度组合，当且仅当L为格($\varsigma $, ≤, ∧, ∨)中使得(U, C^L∪{δ_C^L1})协调的最大元素。于是我们设计了一种基于定义13寻找一个最优尺度组合的算法，见算法1。最糟糕的情况下，该算法的时间复杂度为$O\left(\prod\limits_{j = 1}^m {{I_j}} \times|U|^2\right)$。

算法1  在不协调广义多尺度序决策信息系统中求最优尺度组合的算法。

输入：一个不协调广义多尺度序决策信息系统

$ \begin{aligned} & \quad S=(U, C \cup\{d\})=\left(U, \left\{a_j^k \mid k=1, 2, \cdots, I_j, j=\right.\right. \\ & 1, 2, \cdots, m\} \cup\{d\})。\end{aligned} $

输出：S的一个最优尺度组合。

1. 计算$\boldsymbol{D}^{G_\delta^{L_1}} ; M \leftarrow \varnothing$

2. For  i, j=1 : n

3.  If δ_C^L1$\notin D_{i j}^{G_\delta^{C^{L_1}}}$

4.   $M \leftarrow D_{i j}^{G_\delta^{C^{L_1}}}$

5.  End if

6. End for

7. Queue←NULL；(l₁, l₂, …, l_m)←(I₁, I₂, …, I_m)

8. L₀←(l₁, l₂, …, l_m)；Queue.put (L₀)

9. While (Queue≠NULL)

10. L←Queue.get( )

11. If C^L⊄M

12.  Return (L)

13. End if

14. For k=1 : m

15. If (l_k>1)

16.   L←(l₁, l₂, …, l_k-1, l_k-1, l_m)；Queue.put(L)

17.  End if

18. End for

19. End while

3.3 不协调广义多尺度序决策信息系统的知识获取

本小节主要研究不协调广义多尺度序决策信息系统的知识获取，分为属性约简和规则提取。序决策信息系统的属性约简是在所有对象的基础上，保持序决策信息系统协调性不变的最小属性子集。

定义14  设$S=(U, C \cup\{d\})=\left(U, \left\{a_j^k \mid k=1, \right.\right.\left.\left.2, \cdots, I_j, j=1, 2, \cdots, m\right\} \cup\{d\}\right)$是一个不协调的广义多尺度序决策信息系统，L=(l₁, l₂, …, l_m)∈$\varsigma $是S的最优尺度组合。对$\forall B \subseteq C^L=\left\{a_1^{l_1}, a_2^{l_2}, \cdots, \right.\left.a_m^{l_m}\right\}$，若不存在i, j=1, 2, …, n, 使得$B \subseteq D_{i j}^{c^L \cup\{{\delta}_{c^{L_1}{ }^{}}\}}，\delta_{C^{L_1}} \notin D_{i j}^{c^L \cup\{{\delta}_{c^{L_1}{ }^{}}\}}$成立, 存在i, j=1, 2, …, n, ∀b∈B，使得B-{b}⊆$D_{i j}^{c^L \cup\{{\delta}_{c^{L_1}{ }^{}}\}}, \delta_{C^{L_1}} \notin D_{i j}^{c^L \cup\{{\delta}_{c^{L_1}{ }^{}}\}}$成立，则称B是C^L的一个约简。

序决策信息系统中的决策规则一般形式为t→s，t是规则的条件部分，s是规则的决策部分。对同时满足决策规则的条件部分和决策部分的对象，称为支持该条规则的对象。决策规则的确定度为$r=\mid t \wedge s \mid / t$，确定度体现了根据条件部分能得出决策部分的可信度。对于不协调广义多尺度序决策信息系统，与文献[20]类似，根据最优尺度组合和属性约简就可以提取确定规则与可能规则，其规则形式为

$ \begin{aligned} & \left(a_1^{k_1}, \geqslant, r_1\right) \wedge\left(a_2^{k_2}, \geqslant, r_2\right) \wedge \cdots \wedge \\ & \left(a_m^{k_m}, \geqslant, r_m\right) \Rightarrow\left(d, \geqslant, r_d\right)。\end{aligned} $

显然确定规则的确定度为1，可能规则的确定度小于1。

例1  假设$S=(U, C \cup\{d\})=\left(U, \left\{a_1^1, a_1^2, a_2^1, \right.\right.\left.\left.a_2^2, a_2^3, a_3^1, a_3^2\right\} \cup\{d\}\right)$是一个广义多尺度序决策信息系统，如表 1所示，则该广义多尺度序决策信息系统共有12个尺度组合，即L₁=(1, 1, 1), L₂=(2, 1, 1), L₃=(1, 2, 1), L₄=(1, 1, 2), L₅=(2, 2, 1), L₆=(2, 1, 2), L₇=(1, 2, 2), L₈=(1, 3, 1), L₉=(2, 3, 1), L₁₀=(1, 3, 2), L₁₁=(2, 2, 2), L₁₂=(2, 3, 2)。显然，L₁=(1, 1, 1)和L₁₂=(2, 3, 2)分别为格($\varsigma $, ≤, ∧, ∨)中最小元和最大元，格结构如图 1所示。

例2  在例1中，需要解决问题1)~3)，

1) 判断S是否是协调的；

2) 确定S的最优尺度组合；

3) 确定S的属性约简和决策规则。

1) 计算在尺度组合L₁=(1, 1, 1)下，序决策信息系统(U, C^L₁∪{d})的集值优势矩阵，篇幅原因，在此不具体展示。显然$\left\{a_1^1, a_2^1, a_3^1\right\} \subseteq D_{11, 4}^{C_1^{L_1} \cup\{d\}}, d \notin D_{11, 4}^{C^{L_1} \cup\{d\}}$，所以广义多尺度序决策信息系统S是不协调的。

2) 根据广义决策的定义，在最细尺度L₁=(1, 1, 1)下，可计算得到表 1中第10列所示的广义决策函数δ_C^L1(x)。由于S不协调，则替换决策属性d为δ_C^L1，并分别采用定义11的3种方法定义广义决策δ_C^L1的区间值优势关系，以此来分别求最优尺度组合。

① 采用定义11的1)定义区间值优势关系，根据定理1可知(U, C^L₁∪{δ_C^L1})是协调的。另外可得$G_\delta^{L_1}=\left(U, C \cup\left\{\delta_{C^{L_1}}\right\}\right)$的集值优势矩阵$\boldsymbol{D^{G_\delta^{L_1}}}$，由于矩阵太大和篇幅原因，在此只展示$G_\delta^{L_1}=\left(U, C \cup\left\{\delta_{C^{L_1}}\right\}\right)$的集值优势矩阵中不含决策属性δ_C^L1的项，如

$ \boldsymbol{D}^{\sigma_\delta^{L_1}}=\left[\begin{array}{ccccccc} & x_1 & x_2 & x_8 & x_9 & x_{10} & x_{12} \\ x_1 & & & & \left\{a_1^2, a_2^1, a_2^2, a_2^3\right\} & & \\ x_2 & & & &\left\{a_1^2, a_2^1, a_2^2, a_2^3, a_3^2\right\} & \\ x_3 & \left\{a_2^3\right\} & \left\{a_2^3\right\} & \left\{a_2^1, a_2^2, a_2^3\right\} & \left\{a_2^1, a_2^2, a_2^3\right\} & \left\{a_1^1, a_1^2, a_2^1, a_2^2, a_2^3\right\} & \left\{a_2^3, a_3^2\right\} \\ x_4 & \varnothing & \varnothing & \left\{a_1^1, a_1^2\right\} & \varnothing & \left\{a_1^1, a_1^2, a_2^1, a_2^2, a_2^3\right\} & \left\{a_1^2\right\} \\ x_5 & \varnothing & \varnothing & \left\{a_1^1, a_1^2\right\} & \varnothing & \left\{a_1^1, a_1^2, a_2^1, a_2^2, a_2^3\right\} & \left\{a_1^2\right\} \\ x_6 & \left\{a_2^3\right\} & \left\{a_2^3\right\} & \left\{a_2^2, a_2^3\right\} & \left\{a_2^3\right\} & \left\{a_2^1, a_2^2, a_2^3\right\} & \left\{a_2^3, a_3^1, a_3^2\right\}\\ x_7 & \varnothing & \varnothing & \varnothing & \varnothing & \left\{a_2^1, a_2^2, a_2^3\right\} & \left\{a_3^1, a_3^2\right\} \\ x_8 & & & & \left\{a_2^3\right\} \\ x_{10} & & & & \varnothing \\ x_{11} & \left\{a_2^3\right\} & \left\{a_2^3\right\} & \left\{a_1^1, a_1^2, a_2^2, a_2^3\right\} & \left\{a_2^3\right\} & \left\{a_1^1, a_1^2, a_2^1, a_2^2, a_2^3\right\} & \left\{a_1^1, a_1^2, a_2^3\right\} \\ x_{12} & & & & \left\{a_2^1, a_2^2, a_2^3\right\} & &。\end{array}\right] $

对于$C^{L_{12}}=\left\{a_1^2, a_2^3, a_3^2\right\}$，由于$\left\{a_1^2, a_2^3, a_3^2\right\} \subseteq D_{2, 9}^{G_8^{L_1}}=$\left\{a_1^2, a_2^1, a_2^2, a_2^3, a_3^2\right\}, \delta_{c^{L_1}} \notin D_{2, 9}^{G_\delta^{L_1}}$, 故$\left(U, C^{L_{12}} \cup\left\{\delta_{c^{L_1}}\right\}\right)$不协调。

对于$C^{L_{10}}=\left\{a_1^1, a_2^3, a_3^2\right\}$，由于不存在i, j=1, 2, …, n, 使得$\left\{a_1^1, a_2^3, a_3^2\right\} \subseteq D_{i j}^{G_\delta^{\delta_1}}, \delta_{L^{L_1}} \notin D_{i j}^{G_\delta^{L_1}}$成立，故(U, C^L₁₀∪{δ_C^L1})协调。

同理，也可计算得到(U, C^L₁₁∪{δ_C^L1})不协调，(U, C^L₉∪{δ_C^L1}), (U, C^L₆∪{δ_C^L1})协调。

根据最优尺度组合的定义和图 1的格结构，可知最优尺度组合为(2 3 1), (1 3 2)。

② 采用定义11的2)和3)分别定义区间值优势关系，计算过程在此不具体描述，方法与①一样，可分别得最优尺度为(2 1 2)和(1 1 2), (2 1 1)。

3) 选择定义11的1)所得的最优尺度组合L₉=(2, 3, 1)为例求其属性约简。

由于可求得不存在i, j=1, 2, …, n, 使得

$ \left\{ {a_1^2, a_3^1} \right\} \subseteq D_{ij}^{{L_9} \cup \{ {\delta _{{c^{{L_1}}}}}\} }, {\delta _{{C^{{L_1}}}}} \notin D_{ij}^{{L_9} \cup \{ {\delta _{{c^{{L_1}}}}}\} }，$

且

$ \begin{aligned} & \left\{a_1^2\right\} \subseteq D_{4.8}^{{L_9} \cup \{ {\delta _{{c^{{L_1}}}}}\} }, {\delta _{{C^{{L_1}}}}} \notin D_{4.8}^{{L_9} \cup \{ {\delta _{{c^{{L_1}}}}}\} }, \\ & \left\{a_3^1\right\} \subseteq D_{7.12}^{{L_9} \cup \{ {\delta _{{c^{{L_1}}}}}\} }, {\delta _{{C^{{L_1}}}}} \notin D_{7.12}^{{L_9} \cup \{ {\delta _{{c^{{L_1}}}}}\} }。\end{aligned} $

所以，根据定义14知{a₁², a₃¹}是序决策信息系统(U, {a₁², a₂³, a₃¹}∪{δ_C^L1})的一个约简。

又因为{a₁², a₂³}，{a₂³, a₃¹}，{a₂³}均不是(U, {a₁², a₂³, a₃¹}∪{δ_C^L1})的约简，所以{a₁², a₃¹}是(U, {a₁², a₂³, a₃¹}∪{δ_C^L1})的唯一一个约简。

因此可得

$S=(U, C \cup\{d\})=\left(U, \left\{a_1^1, a_1^2, a_2^1, a_2^2, a_2^3, a_3^1\right.\right.\left.\left.a_3^2\right\} \cup\{d\}\right)$。在L₉=(2, 3, 1)下的部分序决策规则为

r₁: (a₁², ≥, 9)∧(a₃¹, ≥, 93)⇒(d, ≥, 2)，该规则的支持对象为x₂, x₉，确定度为1；

r₂: (a₁², ≥, 7)∧(a₃¹, ≥, 71)⇒(d, ≥, 1)，该规则的支持对象为x₁, x₂, x₃, x₈, x₉, x₁₀, x₁₂，确定度为1；

r₃: (a₁², ≥, 8)∧(a₃¹, ≥, 58)⇒(d, ≥, 2)，该规则的支持对象为x₁, x₂, x₄, x₈, x₉, x₁₂, 确定度为$\frac{3}{4}$；

r₄: (a₁², ≥, 8)∧(a₃¹, ≥, 85)⇒(d, ≥, 3)，该规则的支持对象为x₁, x₈, x₉，确定度为$\frac{3}{4}$。

4 实验与分析

为了验证本文提出的算法1的有效性，即验证所提出的广义决策最优尺度组合是合理的。本节在一些公开的数据集上进行数值实验，这些数据集来自加州大学欧文分校(UCI)，具体信息如表 2所示。

由于这些数据集对应的信息系统的条件属性是单尺度的，所以必须将数据集预处理转换成多尺度信息系统。采用文献[11]方法获得多尺度信息系统，步骤如下。

1) 通过$a^1(x)=\left\lfloor\left(a(x)-m_a\right) / \mathit{std}(a)\right\rfloor$计算得到属性a的第一个尺度，其中a(x)是原始数据集对象x的属性值，m_a和std(a)分别是属性a的最小值和标准差，$\lfloor y\rfloor$表示满足z≤y的最大整数z。

2) 为了模拟数据有序的分类任务，首先计算样本在条件属性下的平均值，接着具有较大平均值的样本被分配较大的类标签，具有较小平均值样本被分配较小的类标签。考虑类标签的数量远小于样本数量，在基于平均值对类标签进行赋值过程中，采用根据类标签数量进行批量赋值的方法。例如，对于数据集iris，我们按照平均值的顺序将其分成3个数量相等的部分，并按照对应顺序为样本分配标签值。然后为了保证不协调性，随机选择5%的样本且使选择的每个类标签样本个数相等，并用其余类标签值平均替换原有标签值，就获得了不协调序决策信息系统。

3) 在第一个尺度的基础上，从下到上依次合并属性值来得到后续的尺度，直到当前尺度级的属性值域不超过3个，如假设属性a的第1个尺度的属性值域为a¹={0, 1, 2, 3, 4, 5}，则a²={1, 2, 3, 4, 5}，a³={2, 3, 4, 5}, a⁴={3, 4, 5}，故属性a有4个尺度。

显然，通过步骤1)~3)求得的广义多尺度序决策信息系统是不协调的，并利用算法1和定义11三种不同方法就可求得最优尺度组合，结果如表 3所示。表 3还显示了最优率和平均尺度，最优率表示尺度级 2的属性百分比，平均尺度为所有尺度的平均值。如数据集iris包含4个属性，在定义11的3种定义区间值优势关系方法下，最优尺度组合分别为(1, 3, 2, 2), (2, 1, 2, 1), (1, 1, 2, 1)。与最细尺度组合相比，最优率分别为0.75, 0.50, 0.25，平均尺度分别为2.00, 1.50, 1.25。

通过使用MATLAB R2020b提供的分类器K近邻(KNN, K=3)、分类回归树(CART)来评估算法所求得的最优尺度组合的性能。为了进行充分的比较，采用三种不同尺度组合比较，即最细尺度组合、最粗尺度组合、最优尺度组合。

实验中使用这些分类器的默认参数设置，采用三重交叉验证，即对于每个数据集，选择2/3的样本作为训练集，其余1/3的样本作为测试集。分类准确率作为评价指标。重复实验10次，计算分类准确率的平均值和标准差作为最终结果。实验结果如表 4~5所示。在此需要说明的是，表 4~5中最优尺度组合的三个分类准确率数据是在定义11的三种不同区间值优势关系定义方法下得到的，即相当于三个不同参数所得的结果。而最细尺度组合和最粗尺度组合不受其影响，三种定义方法下所得结果均相同。

从表 4~5可以看出，对于分类器KNN，在iris数据集上，最优尺度组合取得了最大分类准确率；分类器CART在数据集iris和vertebral-column-3c上的最优尺度组合也取得了最大分类准确率，说明将单尺度信息表转换为多尺度信息表并求得的最优尺度组合可以在一定程度上提高分类性能。相比最细尺度组合，所有数据集的最粗尺度组合分类效果较差，主要在于尺度不断合并过程导致大量信息丢失。但对于大多数数据集，最优尺度组合的分类精度与最细尺度组合分类精度接近，理论上代价也降低了，说明所提出的广义决策最优尺度组合是有效的，在一定条件下能取得较好的决策结果。

5 总结

目前，广义多尺度决策信息系统的研究大多基于等价关系，而基于优势关系进行的研究仍然较少。本文定义序决策信息系统的集值优势矩阵和广义多尺度序决策信息系统，并给出了通过集值优势矩阵判断序决策信息系统是否协调的方法。针对不协调广义多尺度序决策信息系统的最优尺度组合、知识获取问题，引入广义决策的概念，用理论证明了用广义决策δ_C^L替换序决策信息系统中的决策属性d能得到新的协调序决策信息系统。基于此，利用集值优势矩阵给出了求不协调广义多尺度序决策信息系统最优尺度组合和属性约简方法，这一方法简单且无须每次计算条件属性和决策属性的优势类。在下一步的研究中，考虑深入研究集值优势矩阵的性质，以此研究最优尺度组合的启发式算法。