Multi-scale decision model based on partition order product space
-
摘要: 多尺度决策系统的知识获取仅考虑了条件属性和决策属性的多个尺度，并没有考虑条件属性存在多个视角的情况，划分序乘积空间作为一种新型粒计算模型，同时考虑了多层次和多视角。因此，使用划分序乘积空间对多尺度决策问题进行描述和求解，建立基于划分序乘积空间的多尺度决策模型——划分序多尺度决策系统。首先，提出基于划分序乘积空间的划分序多尺度决策系统，从多个视角对多尺度决策问题进行描述；其次，在划分序多尺度决策系统中，给出其解空间的2种不同格结构；然后，针对2种不同格结构分别给出2种最优问题求解层选择算法，从多个视角对多尺度决策问题进行求解；最后，通过实验验证了所提模型和算法的有效性。Abstract: Knowledge acquisition in multiscale decision systems is an important research problem. Existing studies on multiscale decision systems only typically address multiple scales of condition and decision attributes, but they often overlook scenarios where condition attributes have multiple views. As a new granular computing model, the partition order product space simultaneously considers multiple levels and views. Therefore, this paper uses the partition order product space to describe and solve multiscale decision problems and establishes a multiscale decision model based on this space, which is referred to as the partition order multiscale decision system. First, the study proposes a partition order multiscale decision system based on the partition order product space, which can describe multiscale decision problems from multiple views. Second, two different lattice structures within the problem solution space of the partition order multiscale decision system are provided. Third, two optimal problem-solving level selection algorithms are introduced for the two different lattice structures to address the multiscale decision problem from multiple views. Finally, the effectiveness of the proposed model and algorithms is verified through experiments.
-
粗糙集（rough set）理论[1]是Pawlak在1982年提出的一种对不确定信息进行处理的数学工具。粗糙集理论主要使用信息系统来描述样本集，通过论域上的等价类和目标概念的近似集来实现知识发现[1-2]。在传统信息系统中，每个对象在每个属性上只取单一尺度的值，这种单尺度信息系统远远不能满足实际应用的需要[3]。近年来，多尺度信息系统的知识获取成为粗糙集数据分析领域的一个重要研究方向[4-11]。
多尺度信息系统是由Wu等[12]提出的一种粗糙集数据分析模型，被称为Wu-Leung模型[8]。Wu-Leung模型[12]认为对象属性值的多个尺度会导致论域的多粒度粒化，所以可以使用属性的不同尺度描述同一个对象。在此基础上，顾沈明等[13]、吴伟志等[14]对多尺度决策系统及其最优尺度的选择进行了广泛的研究。Li等[8]考虑到对象的不同属性会具有不同的尺度，提出了广义多尺度信息系统，并给出了其最优尺度选择算法。考虑到决策属性也会存在多个尺度，Huang等 [15]讨论了决策属性具有多个尺度的完备信息系统的知识获取问题，给出了协调的决策是多尺度的完备信息系统的最优尺度选择算法。宋茂林等[16]讨论了决策是多尺度的不完备信息系统的最优尺度选择问题。近几年，多尺度决策系统的最优尺度选择研究取得了许多成果[17-20]。
多尺度决策系统作为一种粒计算模型，与描述和求解问题的粒结构密切相关[21]。从粒计算的角度来看，多层次和多视角是构造粒结构的2个基本原则，多层次强调问题描述和求解的深度，多视角则强调问题描述和求解的广度。本质上，Wu-Leung模型及其改进模型都是一种多层次粒结构。现实生活中，人们对问题的描述和求解通常是多层次和多视角的。因此，单视角框架下的知识表示和数据处理方法远不能满足实际应用的需要。徐怡等[21]将多层次原则和多视角原则相结合，提出了一种新型粒计算模型——划分序乘积空间，可以从多个层次和多个视角来对问题进行更加全面的描述。因此，本研究使用划分序乘积空间对多尺度决策问题进行描述和求解，建立基于划分序乘积空间的多尺度决策模型——划分序多尺度决策系统。首先，提出基于划分序乘积空间的划分序多尺度决策系统；其次，在划分序多尺度决策系统中，给出其解空间的2种不同格结构；然后，针对2种不同格结构分别给出2种最优问题求解层选择算法；最后，通过实验验证了所提模型和算法的有效性。
本研究介绍多尺度决策系统和划分序乘积空间的相关基础知识；给出基于划分序乘积空间的划分序多尺度决策系统及其解空间的2种不同格结构和2种最优问题求解层选择算法，并进行实验与分析。
1. 相关理论
简要介绍多尺度决策系统和划分序乘积空间的相关基础知识。
1.1 多尺度决策系统
定义1 决策系统（decision making system，DS，式中记为DS）是1个四元组
$$ {D_{\text{S}}} = (U,{A_{\mathrm{T}}} = C \cup \{ d\} ,V,f) $$ (1) 式中：论域
$ U $ 是一个有限非空对象集； AT是一个有限非空属性集；$ C $ 为条件属性集；$ d $ 为决策属性，$ C \cap \{ d\} = \varnothing $ ；$ V $ 是 AT 的值域，$ V = { \cup _{b \in {A_{\text{T}}}}}{V_b} $ ；$ f为U\times {A}_{\text{T}}\to V $ 是一个信息函数，$ f(x,b) \in {V_b} $ ，$ f(x,b) $ 是对象$ x \in U $ 在属性$ b \in {A_{\text{T}}} $ 上的取值。在决策系统 DS 中，若每个对象
$ x \in U $ 在每个属性$ b \in {A_{\text{T}}} $ 上的取值是唯一的，则称 DS 为单尺度决策系统[22]，若每个对象在同一个属性上可以根据不同的尺度取不同的值，则称 DS 为多尺度决策系统[12]。定义2 多尺度决策系统是1个四元组
$ {D_{\text{S}}} = (U,{A_{\text{T}}} = C \cup \{ d\} ,V,f) $ 。其中，$ C = \{ {a_1},{a_2}, \cdots , {a_m}\} $ 为条件属性集，假设条件属性$ {a_i} \in C $ 具有$ {I_i} $ 个尺度，决策属性$ d $ 具有$ N $ 个尺度，则多尺度决策系统可以表示为$$ {D_{\text{S}}} = (U,{A_{\text{T}}} = \{ a_i^k|k = 1,2, \cdots ,{I_i},i = 1,2, \cdots ,m\} $$ $$ \cup \{ {d^t}|t = 1,2, \cdots ,N\} ,V,f) $$ (2) 式中：
$ {a}_{i}^{k}为U\to {V}_{{a}_{i}}^{k} $ ，$ V_{{a_i}}^k $ 是属性$ {a_i} $ 在第$ k $ 个尺度上的值域；$ {d}^{t}为U\to {V}_{d}^{t} $ ，$ V_d^t $ 是属性$ d $ 在第$ t $ 个尺度上的值域。从定义2可知，一个多尺度决策系统 DS 可以分解为
$ (\prod\nolimits_{i = 1}^m {{I_i}} ) \times N $ 个单尺度决策系统。定义3 给定一个多尺度决策系统 DS 。假设条件属性
$ a_{i} $ 取第$ {l_i} $ 个尺度，$ 1 \leqslant {l_i} \leqslant {I_i} $ ，则称$ K = ({l_1},{l_2}, \cdots ,{l_m}) $ 为 DS 的一个尺度组合。由定义3可知，多尺度决策系统 DS 使用条件属性集
$ C $ 上的多个尺度组合对论域$ U $ 进行多层次描述，所以 DS 是一种单视角下的多层次粒结构。1.2 划分序乘积空间
给定一个论域，首先使用论域上的一个划分定义一个层次；然后使用一个嵌套的划分序定义一个多层次，表示一个视角，层次与层次之间具有线性序关系；最后给定多个视角，基于这些线性序关系的笛卡尔积，定义划分序乘积空间。下面介绍划分序乘积空间的相关概念。
定义4[21] 给定一个决策系统 DS ，论域
$ U $ 上的一个划分定义为一个不为空的子集簇$ \pi = \{ {A_1}, {A_2}, \cdots ,{A_k}\} $ ，其中$ {A_i} \cap {A_j} = \varnothing (i \ne j) $ ，且$ \cup _{i = 1}^k{A_i} = U $ 。定义5[21] 给定一个决策系统 DS ，论域
$ U $ 上的2个划分分别为$ { \pi _1} = \{ {A_1},{A_2}, \cdots ,{A_k}\} $ 和$ { \pi _2} = \{ {B_1}, {B_2}, \cdots , {B_t}\} $ 。若对于$ \forall {B_i} \in { \pi _2} $ ，$ \exists {A_j} \in { \pi _1} $ ，有$ {B_i} \subseteq {A_j} $ ，则称$ { \pi _2} $ 细于$ { \pi _1} $ ，或$ { \pi _1} $ 粗于$ { \pi _2} $ ，记为$ { \pi _2} {\preceq} { \pi _1} $ 。若$ { \pi _2}{\preceq} { \pi _1} $ ，且$ { \pi _2} \ne { \pi _1} $ ，则称$ { \pi _2} $ 严格细于$ { \pi _1} $ ，记为$ { \pi _2} \prec { \pi _1} $ 。定义6[21] 给定一个决策系统 DS ，论域
$ U $ 上的一个划分序定义为一个不为空的划分簇$ P = \{ { \pi _1},{ \pi _2}, \cdots ,{ \pi _n}\} $ ，其中$ { \pi _n}{\preceq} { \pi _{n - 1}}{\preceq} \cdots {\preceq} { \pi _1} $ 。定义7 给定一个决策系统 DS ，
$ P = \{ { \pi _1}, { \pi _2}, \cdots ,{ \pi _n}\} $ 为论域$ U $ 上给定的一个划分序。由$ P $ 确定的视角$ v $ 定义为全序集合$ (P,{\preceq} ) $ ，即$ v = (P,{\preceq} ) $ ，其中$ { \pi _i} $ 定义为视角$ v $ 下的第$ i $ 个层次。本研究可以使用一个嵌套的等价关系序诱导出一个划分序。给定一个决策系统 DS ，论域
$ U $ 上的一个嵌套等价关系序为$ R = \{ {E_1},{E_2}, \cdots ,{E_n}\} $ ，其中$ {E_n} \subseteq {E_{n - 1}} \subseteq \cdots \subseteq {E_1} $ 。假设等价关系$ {E_i} $ 在$ U $ 上诱导出的划分为$ U/{E_i} = \{ {[x]_{{E_i}}}|x \in U\} $ ，其中，$ {[x]_{{E_i}}} = \{ y \in U|(x,y) \in {E_i}\} $ 为对象$ x $ 在$ {E_i} $ 下的等价类。如果将$ U/{E_i} $ 记为$ { \pi _i} $ ，则$ R $ 可以在$ U $ 上诱导出一个划分序$ P = \{ { \pi _1},{ \pi _2}, \cdots ,{ \pi _n}\} $ ，其中$ { \pi _n}{\preceq} { \pi _{n - 1}}{\preceq} \cdots {\preceq} { \pi _1} $ 。由上述分析可知，嵌套等价关系序的构造是构建视角的关键。许多学者[17,23-24]通过多种方式成功构造了嵌套的等价关系序。例如，在信息系统
$ S = \{ U,C,V,f\} $ 中，本研究可以基于一个嵌套的属性集序列$ {C_1} \subset {C_2} \subset \cdots \subset {C_n} \subseteq C $ 得到一个嵌套等价关系序。在多尺度信息系统$ S = (U,A) = (U,\{ a_j^k|k = 1,2, \cdots ,I,j = 1,2, \cdots ,m\} ) $ [24]中，本研究可以基于一个嵌套的属性值序列$ {V^I} \prec {V^{I - 1}} \prec \cdots \prec {V^1} $ 得到一个嵌套等价关系序。本研究给出由
$ m $ 个视角构成的划分序乘积空间的定义。定义8[21] 给定一个决策系统 DS ，条件属性集
$ C $ 上的$ m $ 个视角$ {v_i} = ({P_i},{\preceq} ) $ 。其中，$ {P_i} = \{ \pi _i^1, \pi _i^2, \cdots , \pi _i^{{n_i}}\} $ ，$ \pi _i^j $ 为视角$ {v_i} $ 的第$ j $ 个层次，$ {n_i} $ 为视角$ {v_i} $ 的层次数，$ 1 \leqslant i \leqslant m $ ，$ 1 \leqslant j \leqslant {n_i} $ 。则划分序乘积空间POPSm（式中记为POPSm）定义为$ m $ 个视角$ ({P_i},{\preceq} ) $ 的乘积$$ {P_{{\text{OPS}}}}_m = (\mathop \times \limits_{i = 1}^m {P_i},{\preceq _P}) $$ (3) 式中：
$ \mathop \times \limits_{i = 1}^m {P_i} = \{ ( \pi _1^{{j_1}}, \pi _2^{{j_2}}, \cdots , \pi _m^{{j_m}})| \pi _i^{{j_i}} \in {P_i},1 \leqslant i \leqslant m,1 \leqslant {j_i} \leqslant {n_i}\} $ ；$ {{\preceq} _P} $ 是一个偏序关系定义为$ \forall ( \pi _1^{{j_{11}}}, \pi _2^{{j_{21}}}, \cdots , \pi _m^{{j_{m1}}}) $ ，$ ( \pi _1^{{j_{12}}}, \pi _2^{{j_{22}}}, \cdots , \pi _m^{{j_{m2}}}) \in \mathop \times \limits_{i = 1}^m {P_i} $ ，有$ ( \pi _1^{{j_{11}}}, \pi _2^{{j_{21}}}, \cdots , \pi _m^{{j_{m1}}}){{\preceq} _P}( \pi _1^{{j_{12}}}, \pi _2^{{j_{22}}}, \cdots , \ \pi _m^{{j_{m2}}}) $ ，当且仅当$\;\;\; \forall 1 \leqslant i \leqslant m ,\; \pi _i^{{j_{i1}}}{\preceq} \pi _i^{{j_{i2}}}。$ 为叙述简便，本研究将划分序乘积空间 POPSm 简写为
$ {P_{{\text{OPS}}}}_m = ( \times {P_i},{{\preceq} _P}) $ 。定理1[21] 划分序乘积空间
$ {P_{{\text{OPS}}}}_m = ( \times {P_i},{{\preceq} _P}) $ 是一个格结构。徐怡等[21]给出了定理1的详细证明。从定义8和定理1可知，划分序乘积空间对问题的描述是多层次和多视角的。
定义9[21] 给定一个决策系统 DS ，条件属性集
$ C $ 上$ m $ 个视角$ {v_i} $ 构成的划分序乘积空间为$ {P_{{\text{OPS}}}}_m = ( \times {P_i},{{\preceq} _P}) $ 。$ \forall {l^j} = ( \pi _1^{{j_1}}, \pi _2^{{j_2}}, \cdots , \pi _m^{{j_m}}) \in \mathop \times \limits_{i = 1}^m {P_i} $ ，$ {l^j} $ 定义为 POPSm的一个问题求解层， POPSm 的问题求解层全体为$ \ell $ 。从定义9可知，划分序乘积空间中最细的问题求解层为
$ ( \pi _1^{{n_1}}, \pi _2^{{n_2}}, \cdots , \pi _m^{{n_m}}) $ ，记为$ {l^n} $ 。2. 本文模型
本研究使用划分序乘积空间对多尺度决策问题进行描述和求解，提出基于划分序乘积空间的划分序多尺度决策系统。
定义10 给定一个决策系统
$ {D_{\text{S}}} = (U,{A_{\text{T}}} = C \cup \{ d\} ,V,f) $ ，条件属性集$ C $ 上$ m $ 个视角$ {v_i} $ 构成的划分序乘积空间为$ {P_{{\text{OPS}}}}_m = ( \times {P_i},{{\preceq} _P}) $ 。假设决策属性$ d $ 具有$ N $ 个尺度，则划分序多尺度决策系统（PODS，式中记为PODS）定义为$$ {P_{{\text{ODS}}}} = (U,{P_{{\text{OPS}}}}_m,\{ {d^t}|t = 1,2, \cdots ,N\} ,V,f) $$ (4) 在PODS中，本研究可以基于决策属性的
$ N $ 个尺度得到一个嵌套的属性值序列$ {V^N} \prec {V^{N - 1}} \prec \cdots \prec {V^1} $ ，继而得到一个划分序$ {P_d} = \{ \pi _d^1, \pi _d^2, \cdots , \pi _d^N\} $ ，满足$ \pi _d^N{\preceq} \pi _d^{N - 1}{\preceq} \cdots {\preceq} \pi _d^1 $ 。定义11 给定一个划分序多尺度决策系统
$ {P_{{\text{ODS}}}} = (U,{P_{{\text{OPS}}}}_m,\{ {d^t}|t = 1,2, \cdots ,N\} ,V,f) $ ，其中，$ {P_{{\text{OPS}}}}_m = ( \times {P_i},{{\preceq} _P}) $ 是由$ m $ 个视角$ {v_i} $ 构成的划分序乘积空间。假设$ {P_d} = \{ \pi _d^1, \pi _d^2, \cdots , \pi _d^N\} $ 是由决策属性的$ N $ 个尺度诱导出的划分序，则PODS 的解空间为$ {P_{{\text{OPS}}}}_m \times {P_d} $ 。对于$ \forall {l^j} = ( \pi _1^{{j_1}}, \pi _2^{{j_2}}, \cdots , \pi _m^{{j_m}}) \in \ell $ ，$ \forall \pi _d^t \in {P_d} $ ，称$ L = ({l^j}, \pi _d^t) = ( \pi _1^{{j_1}}, \pi _2^{{j_2}}, \cdots , \pi _m^{{j_m}}, \pi _d^t) $ 为 PODS 的一个问题求解层，记 PODS 的问题求解层全体为$ \xi $ 。定义12 给定一个划分序多尺度决策系统
$ {P_{{\text{ODS}}}} = (U,{P_{{\text{OPS}}}}_m,\{ {d^t}|t = 1,2, \cdots ,N\} ,V,f) $ ，其中$ {P_{{\text{OPS}}}}_m = ( \times {P_i},{{\preceq} _P}) $ 是由$ m $ 个视角$ {v_i} $ 构成的划分序乘积空间。$ {L_1} = ({l^{{j_1}}}, \pi _d^{{t_1}}) = ( \pi _1^{{j_{11}}}, \pi _2^{{j_{21}}}, \cdots , \pi _m^{{j_{m1}}}, \pi _d^{{t_1}}) $ ，$ {L_2} = ({l^{{j_2}}}, \pi _d^{{t_2}}) = ( \pi _1^{{j_{12}}}, \pi _2^{{j_{22}}}, \cdots , \pi _m^{{j_{m2}}}, \pi _d^{{t_2}}) $ ，若满足$ {l^{{j_1}}}{{\preceq} _P}{l^{{j_2}}} $ ，且$ \pi _d^{{t_1}}{\succeq} \pi _d^{{t_2}} $ ，则称$ {L_1} $ 细于$ {L_2} $ ，或$ {L_2} $ 粗于$ {L_1} $ ，记为$ {L_1}{\preceq} {L_2} $ 。若$ {L_1}{\preceq} {L_2} $ ，且$ {l^{{j_1}}} \ne {l^{{j_2}}} $ ，或$ \pi _d^{{t_1}} \ne \pi _d^{{t_2}} $ ，则称$ {L_1} $ 严格细于$ {L_2} $ ，记为$ {L_1} \prec {L_2} $ 。定理2 给定一个划分序多尺度决策系统
$ {P_{{\text{ODS}}}} = (U,{P_{{\text{OPS}}}}_m,\{ {d^t}|t = 1,2, \cdots ,N\} ,V,f) $ 。假设$ {P_d} = \{ \pi _d^1, \pi _d^2, \cdots , \pi _d^N\} $ 是由决策属性的$ N $ 个尺度诱导出的划分序，则 PODS 的解空间$ {P_{{\text{OPS}}}}_m \times {P_d} $ 是一个格结构。定理2的证明同定理1。
本研究通过一个例子来说明划分序多尺度决策系统。
例1 表1是一个学生信息表，包括平均绩点（
$ {v_1} $ ）和科研排名（$ {v_2} $ ）这2个视角的信息，论域$ U = \{ {x_1},{x_2},{x_3},{x_4},{x_5},{x_6},{x_7},{x_8}\} $ 。为方便讨论，假定每个视角只有一个属性。表 1 学生信息表Table 1 Student information form$ U $ 平均绩点 科研排名 奖学金 $ {a}^{1} $ $ {a}^{2} $ $ {b}^{1} $ $ {b}^{2} $ $ {d}^{1} $ $ {d}^{2} $ $ {x}_{1} $ excellent (3.7, 4.0] good [1, 50] yes fs $ {x}_{2} $ excellent (3.7, 4.0] excellent (50, 100] yes ss $ {x}_{3} $ good (3.3, 3.7] excellent (100, 150] no no $ {x}_{4} $ excellent (3.7, 4.0] excellent (50, 100] yes ss $ {x}_{5} $ good (3.3, 3.7] good (150, 200] no no $ {x}_{6} $ good (3.3, 3.7] excellent (100, 150] no no $ {x}_{7} $ good [3.0, 3.3] excellent (100, 150] no no $ {x}_{8} $ good [3.0, 3.3] good (150, 200] no no 在视角
$ {v_1} $ 中，属性值具有$ {a^1} $ 和$ {a^2} $ 这2个尺度，其分别对应尺度值{excellent，good}和{(3.7, 4.0], (3.3, 3.7], [3.0, 3.3]}。$ {a^1} $ 和$ {a^2} $ 决定了一个嵌套的等价关系序，故本研究可以得到一个划分序$ {P_1} = \{ \pi _1^1, \pi _1^2\} $ ，即$ {v_1} = ({P_1},{\preceq} ) $ 。在视角$ {v_2} $ 中，本研究同样可以基于$ {b^1} $ 和$ {b^2} $ 这2个尺度对应的尺度值{excellent，good}和{[1, 50], (50, 100], (100, 150], (150,200]}得到一个划分序$ {P_2} = \{ \pi _2^1, \pi _2^2\} $ ，即$ {v_2} = ({P_2},{\preceq} ) $ 。在决策属性上，本研究可以基于$ {d^1} $ 和$ {d^2} $ 这2个尺度对应的尺度值{yes，no}和{fs，ss，no}得到一个划分序$ {P_d} = \{ \pi _d^1, \pi _d^2\} $ ，其中，fs表示一等奖学金，ss表示二等奖学金。由表1可知，视角
$ {v_1} $ 的2个层次分别为$ \pi _1^1 = \{ \{ {x_1},{x_2},{x_4}\} ,\{ {x_3},{x_5},{x_6},{x_7},{x_8}\} \} $ 和$ \pi _1^2 = \{ \{ {x_1},{x_2},{x_4}\} ,\{ {x_3},{x_5}, {x_6}\} ,\{ {x_7},{x_8}\} \} $ ，视角$ {v_2} $ 的2个层次分别为$ \pi _2^1 = \{ \{ {x_1}, {x_5},{x_8}\} ,\{ {x_2},{x_3},{x_4},{x_6},{x_7}\} \} $ 和$ \pi _2^2 = \{ \{ {x_1}\} ,\{ {x_2},{x_4}\} ,\{ {x_3},{x_6},{x_7}\} , \{ {x_5},{x_8}\} \} $ 。对于决策属性，基于$ {d^1} $ 和$ {d^2} $ 可以得到2个层次$ \pi _d^1 = \{ \{ {x_1},{x_2},{x_4}\} ,\{ {x_3},{x_5},{x_6},{x_7},{x_8}\} \} $ 和$ \pi _d^2 = \{ \{ {x_1}\} , \{ {x_2},{x_4}\} ,\{ {x_3},{x_5},{x_6},{x_7},{x_8}\} \} $ 。从上述分析可知，视角
$ {v_1} $ 的2个层次满足$ \pi _1^2{\preceq} \pi _1^1 $ ，视角$ {v_2} $ 的2个层次满足$ \pi _2^2{\preceq} \pi _2^1 $ ，由决策属性的2个尺度诱导出的2个层次满足$ \pi _d^2{\preceq} \pi _d^1 $ 。表1的划分序多尺度决策系统的解空间如图1所示。
图 1 划分序多尺度决策系统的解空间Fig. 1 Solving space of partition order multi-scale decision system
下载:
全尺寸图片
由图1可知，划分序多尺度决策系统的解空间共有8个问题求解层，可以从多个视角以及视角上的多个层次对问题进行描述和求解。在进行奖学金评审时，人们可以根据需要选择不同的视角以及同一视角上的不同层次，获得更加精确的评审结果。
本研究默认条件属性上的所有视角以及决策属性具有相同的重要程度。然而，在金融、工程制造和医疗诊断等诸多特殊领域中，人们通常会优先考虑更加精确的决策结果。本研究通过另外一个实例来说明划分序多尺度决策系统中基于决策优先的解空间。
例2。在例1的基础上，表1的划分序多尺度决策系统中基于决策优先的解空间如图2所示。
图 2 划分序多尺度决策系统中基于决策优先的解空间Fig. 2 Solving space of partition order multi-scale decision system based on decision priority下载:
全尺寸图片
3. 最优问题求解层选择算法
在多尺度决策系统的知识获取研究中[19-22]，现有学者都会在保证决策系统某个性质或某个变量不变的前提下，选择一个合适的尺度作为最优尺度，并利用其进行决策。因此，本研究主要讨论协调[16]的划分序多尺度决策系统的最优问题求解层选择问题，此外，由于问题求解层是多个单层次视角的组合，需要将多个视角融合起来进行问题求解。多粒度粗糙集模型[25-26]中有很多融合策略，本研究主要以乐观融合策略为例来讨论视角的融合，其他融合策略在融合过程上是相似的。首先给出协调的划分序多尺度决策系统的定义。
定义13 给定一个划分序多尺度决策系统
$ {P_{{\text{ODS}}}} = ( U,{P_{{\text{OPS}}}}_m,\{ {d^t}|t = 1,2, \cdots , N\} , V,f) $ ，$ {P_{{\text{OPS}}}}_m = ( \times {P_i}, {{\preceq} _P}) $ 是由$ m $ 个视角$ {v_i} $ 构成的划分序乘积空间。$ {P_d} = \{ \pi _d^1, \pi _d^2, \cdots , \pi _d^N\} $ 是由决策属性的$ N $ 个尺度诱导出的划分序，$ {l^n} = ( \pi _1^{{n_1}}, \pi _2^{{n_2}}, \cdots , \pi _m^{{n_m}}) \in \ell $ ，若满足$$ \frac{{|\{ \pi _i^{{n_i}}: \pi _i^{{n_i}}{\preceq} \pi _d^1,1 \leqslant i \leqslant m\} |}}{m} > 0 $$ (5) 则称 PODS是协调的，否则不协调。其中，“| |”表示集合的基数。
定义14 给定一个划分序多尺度决策系统
$ {P_{{\text{ODS}}}} = ( U,{P_{{\text{OPS}}}}_m,\{ {d^t}|t = 1,2, \cdots ,N\} , V,f) $ ，$ {P_{{\text{OPS}}}}_m = ( \times {P_i}, {{\preceq} _P}) $ 是由$ m $ 个视角$ {v_i} $ 构成的划分序乘积空间。$ {P_d} = \{ \pi _d^1, \pi _d^2, \cdots , \pi _d^N\} $ 是由决策属性的$ N $ 个尺度诱导出的划分序，对于$ \forall L = ({l^j}, \pi _d^t) $ ，$ {l^j} = ( \pi _1^{{j_1}}, \pi _2^{{j_2}}, \cdots , \pi _m^{{j_m}}) \in \ell $ ，$ \pi _d^t \in {P_d} $ ，若满足$$ \frac{{|\{ \pi _i^{{j_i}}: \pi _i^{{j_i}}{\preceq} \pi _d^t,1 \leqslant i \leqslant m\} |}}{m} > 0 $$ (6) 则称 PODS在
$ L $ 上是协调的，否则不协调。其中，“| |”表示集合的基数。定理3 给定一个划分序多尺度决策系统
$ {P_{{\text{ODS}}}} = ( U,{P_{{\text{OPS}}}}_m,\{ {d^t}|t = 1,2, \cdots ,N\} , V ,f) $ ，$ {P_{{\text{OPS}}}}_m = ( \times {P_i}, {{\preceq} _P}) $ 是由$ m $ 个视角$ {v_i} $ 构成的划分序乘积空间。$ {P_d} = \{ \pi _d^1, \pi _d^2, \cdots , \pi _d^N\} $ 是由决策属性的$ N $ 个尺度诱导出的划分序。$ {L_1} = ({l^{{j_1}}}, \pi _d^{{t_1}}) $ ，$ {l^{{j_1}}} = ( \pi _1^{{j_{11}}}, \pi _2^{{j_{21}}}, \cdots , \pi _m^{{j_{m1}}}) \in \ell $ ，$ \pi _d^{{t_1}} \in {P_d} $ ，$ {L_2} = ({l^{{j_2}}}, \pi _d^{{t_2}}) $ ，$ {l^{{j_2}}} = ( \pi _1^{{j_{12}}}, \pi _2^{{j_{22}}}, \cdots , \pi _m^{{j_{m2}}}) \in \ell $ ，$ \pi _d^{{t_2}} \in {P_d} $ ，若$ {L_1}{\preceq} {L_2} $ ，且PODS在$ {L_2} $ 上是协调的，则 PODS在$ {L_1} $ 上也是协调的。因为 PODS在
$ {L_2} $ 上是协调的，故$ \exists i \in \{ 1, 2, \cdots ,m\} $ 使得$ \pi _i^{{j_{i2}}} \in {l^{{j_2}}} $ 满足$ \pi _i^{{j_{i2}}}{\preceq} \pi _d^{{t_2}} $ 。由于$ {L_1}{\preceq} {L_2} $ ，故$ {l^{{j_1}}}{{\preceq} _P}{l^{{j_2}}} $ ，且$ \pi _d^{{t_1}}\succeq \pi _d^{{t_2}} $ ，从而$ \exists i \in \{ 1,2, \cdots ,m\} $ 使得$ \pi _i^{{j_{i1}}} \in {l^{{j_1}}} $ 满足$ \pi _i^{{j_{i1}}}{\preceq} \pi _d^{{t_1}} $ ，因此PODS在$ {L_1} $ 上是协调的。定理4 给定一个划分序多尺度决策系统
$ {P_{{\text{ODS}}}} = (U,{P_{{\text{OPS}}}}_m,\{ {d^t}|t = 1,2, \cdots ,N\} , V,f) $ ，$ {P_{{\text{OPS}}}}_m = ( \times {P_i}, {{\preceq} _P}) $ 是由$ m $ 个视角$ {v_i} $ 构成的划分序乘积空间。$ {P_d} = \{ \pi _d^1, \pi _d^2, \cdots , \pi _d^N\} $ 是由决策属性的$ N $ 个尺度诱导出的划分序。$ {L_1} = ({l^{{j_1}}}, \pi _d^t) $ ，$ {l^{{j_1}}} = ( \pi _1^{{j_{11}}}, \pi _2^{{j_{21}}}, \cdots , \pi _m^{{j_{m1}}}) \in \ell $ ，$ {L_2} = ({l^{{j_2}}}, \pi _d^t) $ ，$ {l^{{j_2}}} = ( \pi _1^{{j_{12}}}, \pi _2^{{j_{22}}}, \cdots , \pi _m^{{j_{m2}}}) \in \ell $ ，$ \pi _d^t \in {P_d} $ 。若满足$ {l^{{j_1}}}{{\preceq} _P}{l^{{j_2}}} $ ，且PODS在$ {L_2} $ 上是协调的，则PODS在$ {L_1} $ 上也是协调的。由定义14和定理3即可证明。
本研究给出划分序多尺度决策系统中最优问题求解层的定义。
定义15 给定一个协调的划分序多尺度决策系统PODS。对于
$ {L_1} \in \xi $ ，若PODS在$ {L_1} $ 上是协调的，但对于$ \forall {L_2} \in \xi $ ，满足$ {L_1} \prec {L_2} $ ，PODS在$ {L_2} $ 上是不协调的，则称$ {L_1} $ 是PODS的一个最优问题求解层。根据定义15，本研究给出划分序多尺度决策系统中最优问题求解层选择算法。
算法1 最优问题求解层选择算法
输出 最优问题求解层
输入 协调的划分序多尺度决策系统
$ \mathrm{P}\mathrm{O}\mathrm{D}\mathrm{S} $ ；1) 初始化队列
$ \mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{u}\mathrm{e} $ ；2) for each
$ i\in \left\{\mathrm{1,2},\cdots ,m\right\} $ 3)
$ {j}_{i}\leftarrow 1 $ ；4) end for
5)
$ {j}_{d}\leftarrow N $ ；6) 将
$ {L}_{0} $ 放入$ \mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{u}\mathrm{e} $ ；7) 标记
$ {L}_{0} $ 为已访问；8) while
$ \mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{u}\mathrm{e} $ 非空 do9) 从
$ \mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{u}\mathrm{e} $ 中取$ L=\left({ \pi }_{1}^{{j}_{1}},{ \pi }_{2}^{{j}_{2}},\cdots ,{ \pi }_{m}^{{j}_{m}},{ \pi }_{d}^{{j}_{d}}\right) $ ；10) if
$ \mathrm{P}\mathrm{O}\mathrm{D}\mathrm{S} $ 在$ L $ 上协调 then11) 返回
$ L $ ；12) else
13) for each
$ i\in \{\mathrm{1,2},\cdots ,m\} $ ；14) if
$ {j}_{i} < {n}_{i} $ then15)
$ L\leftarrow ({ \pi }_{1}^{{j}_{1}},\cdots ,{ \pi }_{i-1}^{{j}_{i-1}},{ \pi }_{i}^{{j}_{i}+1},\cdots ,{ \pi }_{m}^{{j}_{m}}, { \pi }_{d}^{{j}_{d}}) $ ；16) if
$ L $ 未被访问 then17) 将
$ L $ 放入$ \mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{u}\mathrm{e} $ ；18) 标记
$ L $ 为已访问；19) end if
20) end if
21) end for
22) if
$ {j}_{d} > 1 $ then23)
$ H\leftarrow ({ \pi }_{1}^{{j}_{1}},{ \pi }_{2}^{{j}_{2}},\cdots ,{ \pi }_{m}^{{j}_{m}},{ \pi }_{d}^{{j}_{d}-1}) $ ;24) if
$ H $ 未被访问 then25) 将
$ H $ 放入$ \mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{u}\mathrm{e} $ ；26) 标记
$ H $ 为已访问；27) end if
28) end if
29) end if
30) end while
最坏情况下，算法1遍历所有问题求解层的时间复杂度为
$O((\prod\limits_{i = 1}^m {{n_i}} ) \times N)$ 。每次循环中，判断PODS在当前问题求解层上是否协调的时间复杂度为$ O(|U{|^2} \times m) $ ，其中$ m $ 为视角数量。由于PODS中视角数量远小于对象数量，因此算法1总的时间复杂度为$O((\prod\limits_{i = 1}^m {{n_i}} ) \times N \times |U{|^2})$ 。本研究给出基于决策优先的最优问题求解层的定义。
定义16 给定一个划分序多尺度决策系统
$ {P_{{\text{ODS}}}} = (U,{P_{{\text{OPS}}}}_m,\{ {d^t}|t = 1,2, \cdots ,N\} ,V,f) $ ，$ {P_d} = \{ \pi _d^1, \pi _d^2, \cdots , \pi _d^N\} $ 是由决策属性的$ N $ 个尺度诱导出的划分序。对于$ {L_1} = ({l^{{j_1}}}, \pi _d^{{t_1}}) $ ，$ {l^{{j_1}}} = ( \pi _1^{{j_{11}}}, \pi _2^{{j_{21}}}, \cdots , \pi _m^{{j_{m1}}}) \in \ell $ ，$ \pi _d^{{t_1}} \in {P_d} $ ，若PODS在$ {L_1} $ 上是协调的，且满足以下2个条件：1）
$ {l^n} = ( \pi _1^{{n_1}}, \pi _2^{{n_2}}, \cdots , \pi _m^{{n_m}}) \in \ell $ ，对于$ \forall \pi _d^{{t_2}} \in {P_d} $ ，满足$ \pi _d^{{t_2}} \prec \pi _d^{{t_1}} $ ，$ {L_2} = ({l^n}, \pi _d^{{t_2}}) $ ，PODS在$ {L_2} $ 上是不协调的。2） 对于
$ \forall {l^{{j_2}}} = ( \pi _1^{{j_{12}}}, \pi _2^{{j_{22}}}, \cdots , \pi _m^{{j_{m2}}}) \in \ell $ ，满足$ {l^{{j_1}}}{{\preceq} _P}{l^{{j_2}}} $ ，$ {L_2} = ({l^{{j_2}}}, \pi _d^{{t_1}}) $ ，PODS在$ {L_2} $ 上是不协调的。则称
$ {L_1} $ 是PODS的一个最优问题求解层。根据定义16，本研究给出划分序多尺度决策系统中基于决策优先的最优问题求解层选择算法。
算法2 基于决策优先的最优问题求解层选择算法
输入 协调的划分序多尺度决策系统
$ \mathrm{P}\mathrm{O}\mathrm{D}\mathrm{S} $ ；输出 最优问题求解层
1) 初始化队列
$ \mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{u}\mathrm{e} $ ；2) for each
$ t\in \{\mathrm{1,2},\cdots ,N\} $ 3) 清空
$ \mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{u}\mathrm{e} $ ；4) for each
$ i\in \left\{\mathrm{1,2},\cdots ,m\right\} $ 5)
$ {j}_{i}\leftarrow 1 $ ；6) end for
7)
$ {j}_{d}\leftarrow N $ ；8) 将
$ {L}_{0} $ 放入$ \mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{u}\mathrm{e} $ ；9) 标记
$ {L}_{0} $ 为已访问；10) while
$ \mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{u}\mathrm{e} $ 非空 do11) 从
$ \mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{u}\mathrm{e} $ 中取$ L=\left({ \pi }_{1}^{{j}_{1}},{ \pi }_{2}^{{j}_{2}},\cdots ,{ \pi }_{m}^{{j}_{m}},{ \pi }_{d}^{{j}_{d}}\right) $ ；12) if
$ \mathrm{P}\mathrm{O}\mathrm{D}\mathrm{S} $ 在$ L $ 上协调 then13) 返回
$ L $ ；14) else
15) for each
$ i\in \{\mathrm{1,2},\cdots ,m\} $ ；16) if
$ {j}_{i} < {n}_{i} $ then17)
$ L\leftarrow ({ \pi }_{1}^{{j}_{1}},\cdots ,{ \pi }_{i-1}^{{j}_{i-1}},{ \pi }_{i}^{{j}_{i}+1},\cdots ,{ \pi }_{m}^{{j}_{m}},{ \pi }_{d}^{{j}_{d}}) $ ；18) if
$ L $ 未被访问 then19) 将
$ L $ 放入$ \mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{u}\mathrm{e} $ ；20) 标记
$ L $ 为已访问；21) end if
22) end if
23) end for
24) end if
25) end while
26) end for
最坏情况下，算法2与算法1的时间复杂度相同，即为
$O((\prod\limits_{i = 1}^m {{n_i}} ) \times N \times |U{|^2})$ 。4. 实验与分析
4.1 实验数据集及预处理
本研究选取了9个UCI数据集进行实验，数据集的详细信息见表2。其中，Wine quality和Thyroid Disease为连续数据集，使用文献[27]的等宽分箱法对其进行离散化。
表 2 数据集的描述Table 2 The description of data sets数据集 简写 对象
数量条件属
性数量决策类
数量Dermatology DE 366 34 6 SaYoPillow SA 630 8 5 Student prediction SP 145 31 8 Migraine Classification MI 400 23 7 Occupancy Estimation OE 10 129 16 4 Soybean SN 266 35 15 Wine quality WQ 1 599 11 6 Thyroid Disease TD 1947 28 3 Student Evaluation SE 5820 32 3 本研究为了构造每个数据集在条件属性集上的划分序乘积空间，首先将条件属性集
$ C $ 划分为若干个子集$ {C_i} $ ，每个子集表示一个视角，$ {C_i} \subseteq C $ ，$ 1 \leqslant i \leqslant m $ 。然后，将视角$ {v_i} $ 的属性集$ {C_i} $ 再划分为若干个子集$ C_i^j $ ，$ C_i^j \subseteq {C_i} $ ，$ 1 \leqslant j \leqslant n $ ，满足$C_i^1 \subset C_i^2 \subset\cdots \subset C_i^n$ ，$ \cup _{j = 1}^nC_i^j = {C_i} $ 。最后，基于嵌套的属性集序列，构建视角$ {v_i} $ 下的多个层次。表3给出了所有数据集在条件属性集上的多层次多视角粒结构。表 3 数据集在条件属性集上的多层次多视角粒结构Table 3 Multilevel multiview granular structure of data sets on conditional attribute set数据集 视角 每个层次对应的属性集 DE $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}6:\left\{{a}_{1},\dots ,{a}_{6}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{7}\right\}\mathrm{l}\mathrm{e}{\mathrm{vel}}2:\left\{{a}_{7},{a}_{8}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}6:\left\{{a}_{7},\dots ,{a}_{12}\right\} $ $\vdots $ $\vdots $ $ {v}_{6} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{31}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{31},{a}_{32}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}4:\left\{{a}_{31},\dots ,{a}_{34}\right\} $ SA $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}4:\left\{{a}_{1},\dots ,{a}_{4}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{5}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{5},{a}_{6}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}4:\left\{{a}_{5},\dots ,{a}_{8}\right\} $ SP $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}9:\left\{{a}_{1},\dots ,{a}_{9}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{10}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{10},{a}_{11}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}9:\left\{{a}_{10},\dots ,{a}_{18}\right\} $ $\vdots $ $\vdots $ $ {v}_{4} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{28}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{28},{a}_{29}\right\}\cdots \mathrm{l}\mathrm{e} $vel$ 4:\left\{{a}_{28},\dots ,{a}_{31}\right\} $ MI $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}9:\left\{{a}_{1},\dots ,{a}_{9}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{10}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{10},{a}_{11}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}9:\left\{{a}_{10},\dots ,{a}_{18}\right\} $ $ {v}_{3} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{19}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{19},{a}_{20}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}5:\left\{{a}_{19},\dots ,{a}_{23}\right\} $ OE $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}5:\left\{{a}_{1},\dots ,{a}_{5}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{6}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l} $ $ 2:\left\{{a}_{6},{a}_{7}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}5:\left\{{a}_{6},\dots ,{a}_{10}\right\} $ $\vdots $ $\vdots $ $ {v}_{4} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{16}\right\} $ SN $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}6:\left\{{a}_{1},\dots ,{a}_{6}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{7}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{7},{a}_{8}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}6:\left\{{a}_{7},\dots ,{a}_{12}\right\} $ $\vdots $ $\vdots $ $ {v}_{6} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{31}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{31},{a}_{32}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}5:\left\{{a}_{31},\dots ,{a}_{35}\right\} $ WQ $ {v}_{1} $ $ \mathrm{l}{\mathrm{evel}}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}{\mathrm{vel}}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}3:\left\{{a}_{1},\dots ,{a}_{3}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{4}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{4},{a}_{5}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}3:\left\{{a}_{4},\dots ,{a}_{6}\right\} $ $\vdots $ $\vdots $ $ {v}_{4} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{10}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{10},{a}_{11}\right\} $ TD $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}5:\left\{{a}_{1},\dots ,{a}_{5}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{6}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{6},{a}_{7}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}5:\left\{{a}_{6},\dots ,{a}_{10}\right\} $ $\vdots $ $\vdots $ $ {v}_{6} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{26}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{26},{a}_{27}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}3:\left\{{a}_{26},\dots ,{a}_{28}\right\} $ SE $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l} $ $ 2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}6:\left\{{a}_{1},\dots ,{a}_{6}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l} $ $ 1:\left\{{a}_{7}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{7},{a}_{8}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l} $ $ 6:\left\{{a}_{7},\dots ,{a}_{12}\right\} $ $\vdots $ $\vdots $ $ {v}_{6} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{31}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{31},{a}_{32}\right\} $ 在表2的数据集中，由于数据集的决策属性值均为整数，所以本研究使用以下的步骤来构造决策属性的多个尺度。
1）首先，将数据集中原始的决策属性值集合作为决策属性的最细尺度
$ {d^N} $ 。2）然后，在上一个较细尺度对应的决策属性值集合中，将所有最小的决策属性值都修改为次小的决策属性值，将修改后得到的决策属性值集合作为决策属性的一个较粗尺度。
3）重复步骤2，直至决策属性当前尺度对应的属性值集合只包含2个值，即为数据集决策属性的最粗尺度
$ {d^1} $ 。表4给出了所有数据集中决策属性的尺度数量。
表 4 数据集中决策属性的尺度数量Table 4 Number of scales for the decision attribute in data sets数据集 DE SA SP MI OE SN WQ TD SE 决策属性的尺度数量 5 4 7 6 3 14 5 2 2 4.2 实验方法
本研究进行了3组实验来验证所提模型和算法的有效性。
第1组实验的步骤为：首先，本研究在每个数据集上都给定一个问题求解层，该问题求解层在所有视角上都取最细层次，在决策属性上取最细尺度层次；然后，比较所有数据集在单个视角的最细层次上和给定问题求解层上的分类精度。其中，使用五折交叉验证的决策树作为单视图分类器来测试数据集在单个视角上的分类精度，并使用多视图分类器来测试数据集在给定问题求解层上的分类精度。使用的多视图分类器有2种：一是基于主成分分析（principal component analysis）的子空间学习算法[28]，通过获取所有视角上所选属性集合的子空间来进行分类，是一种多视角下的数据融合分类器；二是基于最大规则（maximum rule）的集成学习分类方法[29]，通过所有视角上并行生成的子分类器来进行“投票”分类，是一种多视角下的结果融合分类器。为了方便讨论，本研究将上述2种多视图分类器分别简记为SUB和MRF。
第2组实验的步骤为：首先，考虑决策属性存在多个尺度层次和决策属性仅存在一个尺度层次的2种情况；然后，针对这2种情况，分别使用算法1和算法2选择每个数据集的最优问题求解层；最后，比较2种情况下2种算法所选取问题求解层在多视图分类器上的分类精度。在这一组实验中，当数据集的决策属性仅存在一个尺度时，设置决策属性取最粗的尺度层次。
最后，第3组实验的内容为：在决策属性存在多个尺度层次的情况下，本研究比较算法1、算法2以及以下4种方法所选取问题求解层在多视图分类器上的分类精度。
1）所有视角取最细层次，决策属性取最粗尺度层次（First-Level）；
2）所有视角取最细层次，决策属性取最细尺度层次（Second-Level）；
3）所有视角取最粗层次，决策属性取最粗尺度层次（Third-Level）；
4）所有视角取最粗层次，决策属性取最细尺度层次（Fourth-Level）。
4.3 实验结果与分析
在第1组实验中，本研究首先评估了所有数据集在每个视角上的分类精度，其次评估了所有数据集在给定问题求解层上的分类精度，实验结果见表5。
表 5 实验结果Table 5 Experimental result% 数据集 单视图分类器 SUB MRF $ {v}_{1} $ $ {v}_{2} $ $ {v}_{3} $ $ {v}_{4} $ $ {v}_{5} $ $ {v}_{6} $ DE 63.70 67.87 62.85 64.53 70.99 55.30 65.30 67.65 SA 99.36 99.36 100 99.36 SP 19.31 15.17 13.10 20.68 23.96 21.27 MI 63.75 74.50 64.00 76.75 78.35 OE 83.90 84.96 86.93 85.60 86.29 91.12 SN 43.59 38.72 46.61 58.68 56.77 29.32 67.66 71.41 WQ 39.14 38.96 37.96 44.52 47.84 45.15 TD 94.55 94.55 94.55 93.73 93.52 94.55 94.76 95.27 SE 54.17 56.76 56.58 57.90 57.57 61.73 63.00 62.86 在表5中，粗体标出的数字是每一行的最大值。由于划分序多尺度决策系统可以从多个视角上对问题进行描述，所以给定的问题求解层在大部分数据集上可以获得较高的分类精度，这说明了本研究模型的有效性。
在第2组实验中，算法1和算法2在2种情况下选取的最优问题求解层及其分类精度见表6。
表 6 2种情况下选取的最优问题求解层及其分类精度Table 6 Optimal problem solving level and its classification accuracy in two cases% 数据集 决策属性存在多个尺度 决策属性仅存在一个尺度 问题求解层 SUB MRF 问题求解层 SUB MRF DE $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{5}^{1},{ \pi }_{6}^{2},{ \pi }_{d}^{1}) $ 99.44 94.41 $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{5}^{1},{ \pi }_{6}^{2},{ \pi }_{d}^{1}) $ 99.44 94.41 SA $ ({ \pi }_{1}^{1},{ \pi }_{2}^{4},{ \pi }_{d}^{4}) $ 100.00 97.46 $ ({ \pi }_{1}^{3},{ \pi }_{2}^{1},{ \pi }_{d}^{1}) $ 100.00 98.27 SP $ ({ \pi }_{1}^{1},{ \pi }_{2}^{7},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{d}^{1}) $ 88.27 88.27 $ ({ \pi }_{1}^{1},{ \pi }_{2}^{7},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{d}^{1}) $ 88.27 88.27 MI $ ({ \pi }_{1}^{9},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{d}^{2}) $ 90.75 92.75 $ ({ \pi }_{1}^{9},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{d}^{1}) $ 98.75 97.75 OE $ ({ \pi }_{1}^{1},{ \pi }_{2}^{5},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{d}^{3}) $ 85.60 88.57 $ ({ \pi }_{1}^{1},{ \pi }_{2}^{5},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{d}^{1}) $ 95.52 91.36 SN $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{4},{ \pi }_{5}^{1},{ \pi }_{6}^{1},{ \pi }_{d}^{1}) $ 95.62 96.24 $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{4},{ \pi }_{5}^{1},{ \pi }_{6}^{1},{ \pi }_{d}^{1}) $ 95.62 96.24 WQ $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{3},{ \pi }_{4}^{1},{ \pi }_{d}^{2}) $ 85.61 86.42 $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{3},{ \pi }_{4}^{1},{ \pi }_{d}^{1}) $ 87.23 86.36 TD $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{5}^{4},{ \pi }_{6}^{1},{ \pi }_{d}^{1}) $ 99.48 99.64 $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{5}^{4},{ \pi }_{6}^{1},{ \pi }_{d}^{1}) $ 99.48 99.64 SE $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{5}^{1},{ \pi }_{6}^{1},{ \pi }_{d}^{1}) $ 86.68 86.68 $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{5}^{1},{ \pi }_{6}^{1},{ \pi }_{d}^{1}) $ 86.68 86.68 由表6可以看出，算法1和算法2在第1种情况下选取的问题求解层是相同的，这是因为所有数据集上的最优问题求解层是唯一的。在第2种情况下，由于所有数据集在划分序多尺度决策系统中的解空间是相同的，所以算法1和算法2选取的问题求解层也是相同的。首先，在2种情况下，2种算法在数据集DE、SP、SN、TD以及SE上选取的问题求解层相同，因此所选取问题求解层的分类精度也相同。其次，在数据集SA上，2种算法在第1种情况下选取的问题求解层在分类精度上要高于第2种情况下选取的问题求解层，且前者在决策属性上具有更细的尺度层次，求解问题时可以获得更加精确的决策结果。
在第3组实验中，6种不同方法所选取问题求解层在多视图分类器SUB和MRF上的分类精度分别见表7和表8。其中，Optimal-Level为算法1和算法2选取的最优问题求解层，其对应表6中决策属性存在多个尺度情况下2种算法所选取的问题求解层。
表 7 问题求解层在SUB上的分类精度Table 7 Classification accuracy of problem solving level on SUB% 数据集 Optimal-Level First-Level Second-Level Third-Level Fourth-Level DE 99.44 99.44 65.30 94.72 36.59 SA 100.00 100.00 100.00 80.00 55.76 SP 88.27 85.41 23.96 86.36 22.06 MI 90.75 95.75 76.75 78.24 63.25 OE 85.60 88.95 86.29 88.95 85.41 SN 95.62 96.24 67.66 96.24 19.17 WQ 85.61 86.49 47.84 85.61 45.67 TD 99.48 99.33 94.76 99.43 94.19 SE 86.68 87.57 63.00 86.68 61.87 表 8 问题求解层在MRF上的分类精度Table 8 Classification accuracy of problem solving level on MRF% 数据集 Optimal-Level First-Level Second-Level Third-Level Fourth-Level DE 94.41 95.53 67.65 94.41 31.00 SA 97.46 100.00 99.36 80.00 61.92 SP 88.27 89.65 21.27 88.27 24.13 MI 92.75 98.00 78.35 77.32 61.75 OE 88.57 92.30 91.12 90.49 86.20 SN 96.24 96.99 71.41 96.24 17.29 WQ 86.42 86.42 45.15 85.61 44.84 TD 99.64 99.64 95.27 99.43 94.55 SE 86.68 86.52 62.86 86.68 61.87 由表7和表8可以看出，对于大多数数据集，First-Level在多视图分类器上的分类精度都要高于其他的问题求解层，这主要是因为First-Level在所有视角上都具有最细的层次且在决策属性上具有最粗的尺度层次。对于多视图分类器SUB，数据集DE和SA的Optimal-Level在分类精度上与First-Level相同，且数据集SA的Optimal-Level在决策属性上具有更细的尺度层次，其在获得较高分类精度的同时可以获得更加精确的决策结果。其次，在剩余的其他数据集上，Optimal-Level在分类精度上要接近于First-Level。上述实验的结果说明了2种最优问题求解层选择算法的有效性。
5. 结束语
本研究使用划分序乘积空间对多尺度决策问题进行描述和求解，建立了基于划分序乘积空间的多尺度决策模型。首先，提出了基于划分序乘积空间的划分序多尺度决策系统。在划分序多尺度决策系统中，给出其解空间的2种不同格结构。然后，针对2种不同格结构分别给出2种最优问题求解层选择算法。最后，通过实验验证了所提模型和算法的有效性。接下来，将针对划分序多尺度决策系统中视角和层次的约简问题进行讨论。
-
图 1 划分序多尺度决策系统的解空间
Fig. 1 Solving space of partition order multi-scale decision system
下载:
全尺寸图片
图 2 划分序多尺度决策系统中基于决策优先的解空间
Fig. 2 Solving space of partition order multi-scale decision system based on decision priority
下载:
全尺寸图片
表 1 学生信息表
Table 1 Student information form
$ U $ 平均绩点 科研排名 奖学金 $ {a}^{1} $ $ {a}^{2} $ $ {b}^{1} $ $ {b}^{2} $ $ {d}^{1} $ $ {d}^{2} $ $ {x}_{1} $ excellent (3.7, 4.0] good [1, 50] yes fs $ {x}_{2} $ excellent (3.7, 4.0] excellent (50, 100] yes ss $ {x}_{3} $ good (3.3, 3.7] excellent (100, 150] no no $ {x}_{4} $ excellent (3.7, 4.0] excellent (50, 100] yes ss $ {x}_{5} $ good (3.3, 3.7] good (150, 200] no no $ {x}_{6} $ good (3.3, 3.7] excellent (100, 150] no no $ {x}_{7} $ good [3.0, 3.3] excellent (100, 150] no no $ {x}_{8} $ good [3.0, 3.3] good (150, 200] no no 表 2 数据集的描述
Table 2 The description of data sets
数据集 简写 对象
数量条件属
性数量决策类
数量Dermatology DE 366 34 6 SaYoPillow SA 630 8 5 Student prediction SP 145 31 8 Migraine Classification MI 400 23 7 Occupancy Estimation OE 10 129 16 4 Soybean SN 266 35 15 Wine quality WQ 1 599 11 6 Thyroid Disease TD 1947 28 3 Student Evaluation SE 5820 32 3 表 3 数据集在条件属性集上的多层次多视角粒结构
Table 3 Multilevel multiview granular structure of data sets on conditional attribute set
数据集 视角 每个层次对应的属性集 DE $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}6:\left\{{a}_{1},\dots ,{a}_{6}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{7}\right\}\mathrm{l}\mathrm{e}{\mathrm{vel}}2:\left\{{a}_{7},{a}_{8}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}6:\left\{{a}_{7},\dots ,{a}_{12}\right\} $ $\vdots $ $\vdots $ $ {v}_{6} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{31}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{31},{a}_{32}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}4:\left\{{a}_{31},\dots ,{a}_{34}\right\} $ SA $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}4:\left\{{a}_{1},\dots ,{a}_{4}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{5}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{5},{a}_{6}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}4:\left\{{a}_{5},\dots ,{a}_{8}\right\} $ SP $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}9:\left\{{a}_{1},\dots ,{a}_{9}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{10}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{10},{a}_{11}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}9:\left\{{a}_{10},\dots ,{a}_{18}\right\} $ $\vdots $ $\vdots $ $ {v}_{4} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{28}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{28},{a}_{29}\right\}\cdots \mathrm{l}\mathrm{e} $vel$ 4:\left\{{a}_{28},\dots ,{a}_{31}\right\} $ MI $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}9:\left\{{a}_{1},\dots ,{a}_{9}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{10}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{10},{a}_{11}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}9:\left\{{a}_{10},\dots ,{a}_{18}\right\} $ $ {v}_{3} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{19}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{19},{a}_{20}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}5:\left\{{a}_{19},\dots ,{a}_{23}\right\} $ OE $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}5:\left\{{a}_{1},\dots ,{a}_{5}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{6}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l} $ $ 2:\left\{{a}_{6},{a}_{7}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}5:\left\{{a}_{6},\dots ,{a}_{10}\right\} $ $\vdots $ $\vdots $ $ {v}_{4} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{16}\right\} $ SN $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}6:\left\{{a}_{1},\dots ,{a}_{6}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{7}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{7},{a}_{8}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}6:\left\{{a}_{7},\dots ,{a}_{12}\right\} $ $\vdots $ $\vdots $ $ {v}_{6} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{31}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{31},{a}_{32}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}5:\left\{{a}_{31},\dots ,{a}_{35}\right\} $ WQ $ {v}_{1} $ $ \mathrm{l}{\mathrm{evel}}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}{\mathrm{vel}}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}3:\left\{{a}_{1},\dots ,{a}_{3}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{4}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{4},{a}_{5}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}3:\left\{{a}_{4},\dots ,{a}_{6}\right\} $ $\vdots $ $\vdots $ $ {v}_{4} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{10}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{10},{a}_{11}\right\} $ TD $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}5:\left\{{a}_{1},\dots ,{a}_{5}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{6}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{6},{a}_{7}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}5:\left\{{a}_{6},\dots ,{a}_{10}\right\} $ $\vdots $ $\vdots $ $ {v}_{6} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{26}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{26},{a}_{27}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}3:\left\{{a}_{26},\dots ,{a}_{28}\right\} $ SE $ {v}_{1} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{1}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l} $ $ 2:\left\{{a}_{1},{a}_{2}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}6:\left\{{a}_{1},\dots ,{a}_{6}\right\} $ $ {v}_{2} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l} $ $ 1:\left\{{a}_{7}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{7},{a}_{8}\right\}\cdots \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l} $ $ 6:\left\{{a}_{7},\dots ,{a}_{12}\right\} $ $\vdots $ $\vdots $ $ {v}_{6} $ $ \mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}1:\left\{{a}_{31}\right\}\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}2:\left\{{a}_{31},{a}_{32}\right\} $ 表 4 数据集中决策属性的尺度数量
Table 4 Number of scales for the decision attribute in data sets
数据集 DE SA SP MI OE SN WQ TD SE 决策属性的尺度数量 5 4 7 6 3 14 5 2 2 表 5 实验结果
Table 5 Experimental result
% 数据集 单视图分类器 SUB MRF $ {v}_{1} $ $ {v}_{2} $ $ {v}_{3} $ $ {v}_{4} $ $ {v}_{5} $ $ {v}_{6} $ DE 63.70 67.87 62.85 64.53 70.99 55.30 65.30 67.65 SA 99.36 99.36 100 99.36 SP 19.31 15.17 13.10 20.68 23.96 21.27 MI 63.75 74.50 64.00 76.75 78.35 OE 83.90 84.96 86.93 85.60 86.29 91.12 SN 43.59 38.72 46.61 58.68 56.77 29.32 67.66 71.41 WQ 39.14 38.96 37.96 44.52 47.84 45.15 TD 94.55 94.55 94.55 93.73 93.52 94.55 94.76 95.27 SE 54.17 56.76 56.58 57.90 57.57 61.73 63.00 62.86 表 6 2种情况下选取的最优问题求解层及其分类精度
Table 6 Optimal problem solving level and its classification accuracy in two cases
% 数据集 决策属性存在多个尺度 决策属性仅存在一个尺度 问题求解层 SUB MRF 问题求解层 SUB MRF DE $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{5}^{1},{ \pi }_{6}^{2},{ \pi }_{d}^{1}) $ 99.44 94.41 $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{5}^{1},{ \pi }_{6}^{2},{ \pi }_{d}^{1}) $ 99.44 94.41 SA $ ({ \pi }_{1}^{1},{ \pi }_{2}^{4},{ \pi }_{d}^{4}) $ 100.00 97.46 $ ({ \pi }_{1}^{3},{ \pi }_{2}^{1},{ \pi }_{d}^{1}) $ 100.00 98.27 SP $ ({ \pi }_{1}^{1},{ \pi }_{2}^{7},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{d}^{1}) $ 88.27 88.27 $ ({ \pi }_{1}^{1},{ \pi }_{2}^{7},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{d}^{1}) $ 88.27 88.27 MI $ ({ \pi }_{1}^{9},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{d}^{2}) $ 90.75 92.75 $ ({ \pi }_{1}^{9},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{d}^{1}) $ 98.75 97.75 OE $ ({ \pi }_{1}^{1},{ \pi }_{2}^{5},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{d}^{3}) $ 85.60 88.57 $ ({ \pi }_{1}^{1},{ \pi }_{2}^{5},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{d}^{1}) $ 95.52 91.36 SN $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{4},{ \pi }_{5}^{1},{ \pi }_{6}^{1},{ \pi }_{d}^{1}) $ 95.62 96.24 $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{4},{ \pi }_{5}^{1},{ \pi }_{6}^{1},{ \pi }_{d}^{1}) $ 95.62 96.24 WQ $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{3},{ \pi }_{4}^{1},{ \pi }_{d}^{2}) $ 85.61 86.42 $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{3},{ \pi }_{4}^{1},{ \pi }_{d}^{1}) $ 87.23 86.36 TD $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{5}^{4},{ \pi }_{6}^{1},{ \pi }_{d}^{1}) $ 99.48 99.64 $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{5}^{4},{ \pi }_{6}^{1},{ \pi }_{d}^{1}) $ 99.48 99.64 SE $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{5}^{1},{ \pi }_{6}^{1},{ \pi }_{d}^{1}) $ 86.68 86.68 $ ({ \pi }_{1}^{1},{ \pi }_{2}^{1},{ \pi }_{3}^{1},{ \pi }_{4}^{1},{ \pi }_{5}^{1},{ \pi }_{6}^{1},{ \pi }_{d}^{1}) $ 86.68 86.68 表 7 问题求解层在SUB上的分类精度
Table 7 Classification accuracy of problem solving level on SUB
% 数据集 Optimal-Level First-Level Second-Level Third-Level Fourth-Level DE 99.44 99.44 65.30 94.72 36.59 SA 100.00 100.00 100.00 80.00 55.76 SP 88.27 85.41 23.96 86.36 22.06 MI 90.75 95.75 76.75 78.24 63.25 OE 85.60 88.95 86.29 88.95 85.41 SN 95.62 96.24 67.66 96.24 19.17 WQ 85.61 86.49 47.84 85.61 45.67 TD 99.48 99.33 94.76 99.43 94.19 SE 86.68 87.57 63.00 86.68 61.87 表 8 问题求解层在MRF上的分类精度
Table 8 Classification accuracy of problem solving level on MRF
% 数据集 Optimal-Level First-Level Second-Level Third-Level Fourth-Level DE 94.41 95.53 67.65 94.41 31.00 SA 97.46 100.00 99.36 80.00 61.92 SP 88.27 89.65 21.27 88.27 24.13 MI 92.75 98.00 78.35 77.32 61.75 OE 88.57 92.30 91.12 90.49 86.20 SN 96.24 96.99 71.41 96.24 17.29 WQ 86.42 86.42 45.15 85.61 44.84 TD 99.64 99.64 95.27 99.43 94.55 SE 86.68 86.52 62.86 86.68 61.87 -
[1] PAWLAK Z. Rough sets[J]. International journal of computer & information sciences, 1982, 11(5): 341−356. [2] PAWLAK Z, SKOWRON A. Rudiments of rough sets[J]. Information sciences, 2007, 177(1): 3−27. doi: 10.1016/j.ins.2006.06.003 [3] YAO Jingtao. A ten-year review of granular computing[C]//2007 IEEE International Conference on Granular Computing. Fremont: IEEE, 2007: 734. [4] WU Weizhi, LEUNG Y. Optimal scale selection for multi-scale decision tables[J]. International journal of approximate reasoning, 2013, 54(8): 1107−1129. doi: 10.1016/j.ijar.2013.03.017 [5] GU Shenming, WU Weizhi. On knowledge acquisition in multi-scale decision systems[J]. International journal of machine learning and cybernetics, 2013, 4(5): 477−486. doi: 10.1007/s13042-012-0115-7 [6] WU Weizhi, QIAN Yuhua, LI Tongjun, et al. On rule acquisition in incomplete multi-scale decision tables[J]. Information sciences, 2017, 378: 282−302. doi: 10.1016/j.ins.2016.03.041 [7] LI Feng, HU Baoqing, WANG Jun. Stepwise optimal scale selection for multi-scale decision tables via attribute significance[J]. Knowledge-based systems, 2017, 129: 4−16. doi: 10.1016/j.knosys.2017.04.005 [8] LI Feng, HU Baoqing. A new approach of optimal scale selection to multi-scale decision tables[J]. Information sciences, 2017, 381: 193−208. doi: 10.1016/j.ins.2016.11.016 [9] WU Weizhi, LEUNG Y. A comparison study of optimal scale combination selection in generalized multi-scale decision tables[J]. International journal of machine learning and cybernetics, 2020, 11(5): 961−972. doi: 10.1007/s13042-019-00954-1 [10] DENG Jiang, ZHAN Jianming, WU Weizhi. A three-way decision methodology to multi-attribute decision-making in multi-scale decision information systems[J]. Information sciences, 2021, 568: 175−198. doi: 10.1016/j.ins.2021.03.058 [11] ZHAN Jianming, ZHANG Kai, WU Weizhi. An investigation on Wu-Leung multi-scale information systems and multi-expert group decision-making[J]. Expert systems with applications, 2021, 170: 114542. doi: 10.1016/j.eswa.2020.114542 [12] WU Weizhi, LEUNG Y. Theory and applications of granular labelled partitions in multi-scale decision tables[J]. Information sciences, 2011, 181(18): 3878−3897. doi: 10.1016/j.ins.2011.04.047 [13] 顾沈明, 顾金燕, 吴伟志, 等. 不完备多粒度决策系统的局部最优粒度选择[J]. 计算机研究与发展, 2017, 54(7): 1500−1509. doi: 10.7544/issn1000-1239.2017.20160349 GU Shenming, GU Jinyan, WU Weizhi, et al. Local optimal granularity selections in incomplete multi-granular decision systems[J]. Journal of computer research and development, 2017, 54(7): 1500−1509. doi: 10.7544/issn1000-1239.2017.20160349 [14] 吴伟志, 杨丽, 谭安辉, 等. 广义不完备多粒度标记决策系统的粒度选择[J]. 计算机研究与发展, 2018, 55(6): 1263−1272. doi: 10.7544/issn1000-1239.2018.20170233 WU Weizhi, YANG Li, TAN Anhui, et al. Granularity selections in generalized incomplete multi-granular labeled decision systems[J]. Journal of computer research and development, 2018, 55(6): 1263−1272. doi: 10.7544/issn1000-1239.2018.20170233 [15] HUANG Zhehuang, LI Jinjin, DAI Weizhong, et al. Generalized multi-scale decision tables with multi-scale decision attributes[J]. International journal of approximate reasoning, 2019, 115: 194−208. doi: 10.1016/j.ijar.2019.09.010 [16] 宋茂林, 吴伟志. 协调的决策多尺度不完备信息系统的最优尺度选择[J]. 河北师范大学学报(自然科学版), 2022, 46(2): 117−125. SONG Maolin, WU Weizhi. On optimal scale selection in consistent incomplete multi-scale information systems with multi-scale decisions[J]. Journal of Hebei Normal University (natural science edieion), 2022, 46(2): 117−125. [17] HAO Chen, LI Jinhai, FAN Min, et al. Optimal scale selection in dynamic multi-scale decision tables based on sequential three-way decisions[J]. Information sciences, 2017, 415/416: 213−232. doi: 10.1016/j.ins.2017.06.032 [18] ZHANG Xueqiu, ZHANG Qinghua, CHENG Yunlong, et al. Optimal scale selection by integrating uncertainty and cost-sensitive learning in multi-scale decision tables[J]. International journal of machine learning and cybernetics, 2020, 11(5): 1095−1114. doi: 10.1007/s13042-020-01101-x [19] CHENG Yunlong, ZHANG Qinghua, WANG Guoyin, et al. Optimal scale selection and attribute reduction in multi-scale decision tables based on three-way decision[J]. Information sciences, 2020, 541: 36−59. doi: 10.1016/j.ins.2020.05.109 [20] WANG Wenjue, HUANG Bing, WANG Tianxing. Optimal scale selection based on multi-scale single-valued neutrosophic decision-theoretic rough set with cost-sensitivity[J]. International journal of approximate reasoning, 2023, 155: 132−144. doi: 10.1016/j.ijar.2023.02.003 [21] 徐怡, 姚一豫. 划分序乘积空间: 基于划分的粒计算模型[J]. 计算机研究与发展, 2019, 56(4): 836−843. doi: 10.7544/issn1000-1239.2019.20180325 XU Yi, YAO Yiyu. Partition order product space: partition based granular computing model[J]. Journal of computer research and development, 2019, 56(4): 836−843. doi: 10.7544/issn1000-1239.2019.20180325 [22] 吴伟志. 多粒度粗糙集数据分析研究的回顾与展望[J]. 西北大学学报(自然科学版), 2018, 48(4): 501−512. WU Weizhi. Reviews and prospects on the study of multi-granularity rough set data analysis[J]. Journal of Northwest University (natural science edition), 2018, 48(4): 501−512. [23] CATANZARITI F, CHIASELOTTI G, INFUSINO F G, et al. Object similarity measures and Pawlak’s indiscernibility on decision tables[J]. Information sciences, 2020, 539: 104−135. doi: 10.1016/j.ins.2020.05.030 [24] LIU Fulun, ZHANG Benwen, CIUCCI D, et al. A comparison study of similarity measures for covering-based neighborhood classifiers[J]. Information sciences, 2018, 448/449: 1−17. doi: 10.1016/j.ins.2018.03.030 [25] QIAN Yuhua, LIANG Jiye, YAO Yiyu, et al. MGRS: a multi-granulation rough set[J]. Information sciences, 2010, 180(6): 949−970. doi: 10.1016/j.ins.2009.11.023 [26] QIAN Yuhua, LIANG Jiye, DANG Chuangyin. Incomplete multigranulation rough set[J]. IEEE transactions on systems, man, and cybernetics - part A: systems and humans, 2010, 40(2): 420−431. doi: 10.1109/TSMCA.2009.2035436 [27] XIE Jingjing, HU Baoqing, JIANG Haibo. A novel method to attribute reduction based on weighted neighborhood probabilistic rough sets[J]. International journal of approximate reasoning, 2022, 144: 1−17. doi: 10.1016/j.ijar.2022.01.010 [28] ABDI H, WILLIAMS L J. Principal component analysis[J]. WIREs computational statistics, 2010, 2(4): 433−459. [LinkOut] [29] POLIKAR R. Ensemble learning[M]//ZHANG Cha, MA Yunqian, eds. Ensemble Machine Learning. New York: Springer New York, 2012: 1−34.
