多用户偏好下基于三支决策的动态属性约简

图1 三支决策模型

Fig.1 The model of three⁃way decisions

2 用户偏好指标及属性三分策略

不同用户对属性的偏好程度往往是不一致的，本文采用属性组序的方式对用户偏好进行描述，其语义可以解释为按照信息熵，属性重要度，或者不确定性等所形成的序列．同时也可以从语义层面表示用户对属性的需求．

2.1　多用户偏好表示方法

定义7

属性组序^［5］给定决策表 $D T$ ， $C = \{a_{1}, a_{2}, \dots, a_{m}\}$ 是 $D T$ 的条件属性集， $m = |C|$ ， $\{G_{1}, G_{2}, \dots, G_{n}\}$ 是 $C$ 的一个属性划分，其包含 $n$ 个组，并满足 $G_{1} ⋃ G_{2} ⋃ \dots ⋃ G_{n} = C$ ， $G_{i} ⋂ G_{j} = \emptyset$ ， $i, j = 1, \dots, n$ ， $i \neq j$ ，则属性组序记为 $S$ ：

S = G_{n} > G_{n - 1} > \dots > G_{2} > G_{1}

(6)

该属性组序描述了用户对属性的偏好程度，组间 $G_{n} > G_{n - 1}$ 表示 $G_{n}$ 组中的属性优于 $G_{n - 1}$ 组中的属性，而同一组中的属性具有相同的用户偏好程度．

例1 根据表1，可以给出不同用户下的属性组序关系．用户1： $S_{1} = \{a_{1}, a_{3}\} > \{a_{2}\} > \{a_{4}, a_{5}\}$ ，用户2： $S_{2} = \{a_{3}, a_{5}\} > \{a_{2}, a_{4}\} > \{a_{1}\}$ ，用户3： $S_{3} = \{a_{4}\} > \{a_{1}, a_{3}, a_{5}\} > \{a_{2}\}$ ．此三个用户的不同组序关系，展现了面对相同属性时各个用户的不同偏好．

表1 决策表

Table 1 Decision table

$a_{1}$	$a_{2}$	$a_{3}$	$a_{4}$	$a_{5}$	$D$
2	1	1	1	1	1
1	1	1	2	1	1
1	2	0	1	2	1
1	2	1	1	1	2
0	1	2	1	1	2
2	1	1	3	2	2
2	2	1	1	2	2

基于给定的用户属性组序，引入用户偏好矩阵对多用户偏好进行融合，来表示属性间的优势关系，同时定义属性偏好度代表该属性在一个用户组下的偏好程度．

定义8

用户偏好矩阵给定决策表 $D T$ ， $C$ 为非空属性集合， $n = |C|$ ．用户偏好矩阵表示为 $U P M$ ．初始情况下 $U P M^{0}$ 为 $n$ 维取值全为0的矩阵． $U P M^{k - 1} = {(u m p_{x y}^{k - 1})}_{n \times n}$ 是 $k - 1$ 个用户的用户偏好矩阵．更新第 $k$ 个用户属性组序 $S_{k} = G_{m} > \dots > G_{i} > G_{j} > \dots > G_{1}$ ， $U P M^{k +} = {(u m p_{x y}^{k +})}_{n \times n}$ 表示新增用户后的用户偏好矩阵，其中：

\begin{array}{l} u p m_{x y}^{k +} = \\ \{\begin{matrix} u p m_{x y}^{k - 1} + 1 x \in G_{i}, y \in G_{j} \\ u p m_{x y}^{k - 1}, x \in G_{j}, y \in G_{i} ⋃ x, y \in G_{z}, z = 1, \dots, m \end{matrix} \end{array}

(7)

$U P M^{k -} = {(u m p_{x y}^{k -})}_{n \times n}$ 表示减少已存在用户后的用户偏好矩阵，其中：

\begin{array}{l} u p m_{x y}^{k -} = \\ \{\begin{matrix} u p m_{x y}^{k - 1} - 1, x \in G_{i}, y \in G_{j} \\ u p m_{x y}^{k - 1}, x \in G_{j}, y \in G_{i} ⋃ x, y \in G_{z}, z = 1, \dots, m \end{matrix} \end{array}

(8)

用户偏好矩阵表示的是在一个用户组下属性间优劣次数．

定义9

属性偏好度给定用户偏好矩阵 $U P M^{k}$ ，则属性 $a$ 在当前 $k$ 个用户组下的属性偏好度为：

φ {(a)}^{k} = \sum u p m_{x y}^{k}, x = a, y \in C

(9)

属性偏好度表示该属性在当前用户组下相较于其余属性的优势程度．对于属性集 $B$ ，其属性偏好度为 $φ {(B)}^{k} = \sum_{a \in B} φ {(a)}^{k}$ ．

例2 根据用户1的属性组序 $S_{1} = \{a_{1}, a_{3}\} >$

$\{a_{2}\} > \{a_{4}, a_{5}\}$ ，可以计算出用户1的偏好矩阵为：

U P M^{1} = (\begin{matrix} a_{1} & a_{2} & a_{3} & a_{4} & a_{5} \\ a_{1} & 0 & 1 & 0 & 1 & 1 \\ a_{2} & 0 & 0 & 0 & 1 & 1 \\ a_{3} & 0 & 1 & 0 & 1 & 1 \\ a_{4} & 0 & 0 & 0 & 0 & 0 \\ a_{5} & 0 & 0 & 0 & 0 & 0 \end{matrix})

由用户偏好矩阵可得各个属性的偏好度， $φ {(a_{1})}^{1} = 3$ ， $φ {(a_{2})}^{1} = 2$ ， $φ {(a_{3})}^{1} = 3$ ， $φ {(a_{4})}^{1} = 0$ ， $φ {(a_{5})}^{1} = 0$ ．

2.2　属性三分策略

根据属性偏好度及代价，定义一种度量指标作为选择属性的启发函数，据此利用三支决策理论对约简集和非约简集进行属性三分．设获取表1属性所需代价如表2所示.

表2 属性代价矩阵

Table 2 Attribute cost matrix

属性	$a_{1}$	$a_{2}$	$a_{3}$	$a_{4}$	$a_{5}$
$t (a)$	6	12	8	15	10

任意非空属性集 $B \subseteq A$ 的代价为 $t (B) = \sum_{a \in B} t (a)$ ，例如 $t (\{a_{1}, a_{2}\}) = t (a_{1}) + t (a_{2}) =$

$6 + 12 = 18$ ．为综合属性偏好度和属性代价，提出用户偏好指标 $(U s e r P r e f e r e n c e I n d e x, U P I)$ ．

定义10

用户偏好指标给定一个决策信息表 $D T$ ，对于任意非空属性集 $B \subseteq C$ ，属性 $a \in C - B$ 在当前 $k$ 用户组下的用户偏好指标 $U P I$ 为：

\begin{array}{l} U P I {(a, B)}^{k} = \\ \{\begin{matrix} \begin{array}{l} (φ (B ⋃ \{a\}) - φ (B)) {(t (B ⋃ \{a\}) - t (B))}^{λ}, \\ t (B ⋃ \{a\}) \neq t (B) \end{array} \\ 0, 其 他 \end{matrix} \end{array}

(10)

其中， $λ$ 为代价的惩罚因子，一般设定为-0.5．

例3 假设信息表如表1所示，并且 $B = \{a_{2}, a_{3}\}$ ，那么 $a_{1}$ 在用户1偏好下的 $U P I$ 值为：

\begin{array}{l} U P I {(a_{1}, B)}^{1} = \\ (φ (B ⋃ (a_{1})) - φ (B)) {(t (B ⋃ (a_{1})) - t (B))}^{λ} = \\ (φ (a_{1}, a_{2}, a_{3}) - φ (a_{2}, a_{3})) {(t (a_{1}, a_{2}, a_{3}) - t (a_{2}, a_{3}))}^{- \frac{1}{2}} = \\ (8 - 5) {(26 - 20)}^{- \frac{1}{2}} = 1.2247 \end{array}

同理，在用户1的偏好下可以得到：

U P I {(a_{1}, C)}^{1} = 1.2247

，

U P I {(a_{2}, C)}^{1} = 0.5774

U P I {(a_{3}, C)}^{1} = 1.0607

，

U P I {(a_{4}, C)}^{1} = 0

U P I {(a_{5}, C)}^{1} = 0

通过 $U P I$ 选择属性，假定以正域为判断标准，得到基于用户1偏好下的约简集合为 ${a_{3}, a_{2}, a_{4}}$ ．

这里将信息粒度看作用户偏好，随着用户偏好的增加，描述属性的信息粒度变细，同时属性的 $U P I$ 也在相应变化.通过约简集和非约简集中属性 $U P I$ 值的比较，可将属性三分而治，对三分属性集采用不同的策略达到在当前信息粒度下动态更新约简的目的．

定义11

三分属性集给定属性集合 $R$ 是第 $k - 1$ 个用户组偏好下的一个约简，非约简集合用 $\bar{R}$ 表示，基于 $k$ 用户组下偏好指标 $U P I$ ，可将属性 $a \in R ⋃ \bar{R}$ 分为三个两两不相交的属性集：

\begin{array}{l} R_{i n} (a) = \{a \in R |U P I (a) > {\bar{R}}_{m a x}\} \\ R_{c a n d i d a t e} (a) = \\ \{a \in R |U P I (a) \leq {\bar{R}}_{m a x}\} ⋃ \{a \in \bar{R} | U P I (a) \geq R_{m i n}\} \\ R_{o u t} (a) = \{a \in \bar{R} |U P I (a) < R_{m i n}\} (11) \end{array}

其中， ${\bar{R}}_{m a x}$ 表示非约简集合中 $U P I$ 最大属性的值， $R_{m i n}$ 表示约简集合中 $U P I$ 最小属性的值．对三个属性集合采用不同的策略， $R_{i n} (a)$ 中属性为 $k$ 用户组下部分约简属性， $R_{c a n d i d a t e} (a)$ 中属性为 $k$ 用户组下候选属性集， $R_{o u t} (a)$ 中属性为 $k$ 用户组下非约简属性．图2展示了属性三分的过程．

图2

图2 属性三分过程

Fig.2 The process of dividing attributes into three parts

将 $R_{i n} (a)$ 集合中的属性直接作为 $k$ 用户组下部分约简属性，再从候选属性集中根据 $U P I$ 值进行属性选择，达到与原始信息系统正域不变的条件，即得到 $k$ 用户组下的约简．可见，通过属性三分的方式可以降低重新选择属性时约简准则的判断次数．对于第一个用户，候选属性集为全集．

例4 假设有条件属性为 $C = \{a_{1}, a_{2}, a_{3}, a_{4}, a_{5}\}$ ，若存在约简 $R = \{a_{2}, a_{3}, a_{4}\}$ ，则 $\bar{R} = \{a_{1}, a_{5}\}$ ，在此基础上新增第 $k$ 个用户偏好后重新计算 $U P I$ ，如有：

U P I {(a_{1}, C)}^{k} = 0.75

，

U P I {(a_{2}, C)}^{k} = 1.15

U P I {(a_{3}, C)}^{k} = 2.65

，

U P I {(a_{4}, C)}^{k} = 0.25

U P I {(a_{5}, C)}^{k} = 0.95

由此可将属性三分为：

R_{i n} (a) = \{a_{2}, a_{3}\}

R_{c a n d i d a t e} (a) = \{a_{1}, a_{4}, a_{5}\}

R_{o u t} (a) = \emptyset

3 面向多用户的三支动态约简算法

为了解决多用户偏好下属性约简问题，以正域不变作为约简判断条件， $U P I$ 值作为启发函数，通过动态三分策略更新约简子集．在此基础上需要获得初始情形下的约简，于是提出基于给定用户的属性约简初始化算法.

算法1 基于给定用户的属性约简初始化算法

输入：决策表 $D T$ ，属性组序 $S$ ，代价函数 $t (a)$ ．

输出：初始约简 $R$ ．

1.令 $R = \emptyset$ ；

2.计算每个属性的 $U P I {(a, C)}^{1}$ 值；

3.执行循环；

（1）令 $a^{'} = m a x (U P I (a, C))$ ；

（2） $R = R ⋃ \{a^{'}\}$ ；

（3）从属性集 $C$ 中删除属性 $a^{'}$ ；

直到 $P O S_{R} (D) = P O S_{C} (D)$ ，停止循环；

4.对于任意属性 $a \in R$ ，如果 $P O S_{R} (D) = P O S_{R - \{a\}} (D)$ ，则删除属性 $a$ ；

5.返回约简 $R$ ．

当用户偏好增加或者减少的情况下，由此提出多用户下三支动态属性约简更新算法.

算法2 多用户下三支动态属性约简更新算法

输入： $k$ 用户组下的约简 $R_{k}$ ，第 $k + 1$ 个用户偏好 $S_{k + 1}$ ，代价函数 $t (a)$ ．

输出： $k + 1$ 个用户组下的约简 $R_{k + 1}$ ．

1.初始化 $R_{k}$ ， ${\bar{R}}_{k} = C - R_{k}$ ， $R_{k + 1} = \emptyset$ ；

2.计算 $k + 1$ 个用户组下每个属性的 $U P I {(a, C)}^{k + 1}$ ；

3.将 $R_{k}, {\bar{R}}_{k}$ 集合三分为 $R_{i n} (a), R_{c a n d i d a t e} (a), R_{o u t} (a)$ ；

4. $R_{k + 1} = R_{k + 1} ⋃ R_{i n} (a)$ ；

5.执行循环；

（1）令 $a^{'}$ 为 $R_{c a n d i d a t e} (a)$ 集合中 $U P I$ 最大的属性；

（2） $R_{c a n d i d a t e} (a) = R_{c a n d i d a t e} (a) - \{a^{'}\}$ ；

（3） $R_{k + 1} = R_{k + 1} ⋃ \{a^{'}\}$ ；

直到 $P O S_{R_{k + 1}} (D) = P O S_{C} (D)$ ，停止循环；

6.对于任意属性 $a \in R_{k + 1}$ ，如果 $P O S_{R_{k + 1}} (D) = P O S_{R_{k + 1} - \{a\}} (D)$ ，则删除属性 $a$ ；

⑦返回约简 $R_{k + 1}$ ．

算法时间复杂度：设 $|C|$ 和 $|U|$ 分别代表决策表中条件属性个数和样本个数，算法1步骤2中计算每个属性的 $U P I$ 值的时间复杂度为 $O (|C|)$ ，步骤3中计算正域的时间复杂度为 $O (|C| {|U|}^{2})$ ，选择属性时依次遍历各个属性，所以时间复杂度为 $O (|C|)$ ，故算法1的时间复杂度为 $O (|C| {|U|}^{2})$ .算法2步骤2和步骤3的时间复杂度为 $O (|C|)$ ，步骤5进行正域计算的时间复杂度为 $O (|C| {|U|}^{2})$ ，则算法2整体的时间复杂度为 $O (|C| {|U|}^{2})$ .

空间复杂度：在算法1和算法2中，用户偏好矩阵需要开辟 $O ({|C|}^{2})$ 空间大小，其余变量的空间复杂度为 $O (1)$ ，最终算法的空间复杂度为 $O ({|C|}^{2})$ .

综合算法1和算法2，多用户下动态约简算法整体流程如图3所示．

图3

图3 多用户下动态约简算法流程图

Fig.3 Dynamic reduction algorithm flowchart under multiple users

例5 以表1的决策信息表为例，求得：

U P I {(a_{1}, C)}^{1} = 1.2247

，

U P I {(a_{2}, C)}^{1} = 0.5774

U P I {(a_{3}, C)}^{1} = 1.0607

，

U P I {(a_{4}, C)}^{1} = 0

U P I {(a_{5}, C)}^{1} = 0

根据正域判断约简准则得到用户1下的约简为 $\{a_{3}, a_{2}, a_{4}\}$ ．在此基础上新增用户2偏好 $S_{2} = \{a_{3}, a_{5}\} > \{a_{2}, a_{4}\} > \{a_{1}\}$ ，重新计算得：

U P I {(a_{1}, C)}^{2} = 1.2247

，

U P I {(a_{2}, C)}^{2} = 0.866

U P I {(a_{3}, C)}^{2} = 2.1213

，

U P I {(a_{4}, C)}^{2} = 0.2582

U P I {(a_{5}, C)}^{2} = 0.9487

三分属性集合为：

R_{i n} (a) = \{a_{3}\}

R_{c a n d i d a t e} (a) = \{a_{1}, a_{2}, a_{4}, a_{5}\}

R_{o u t} (a) = \emptyset

$R_{i n} (a)$ 集合中的属性集直接归入约简集中，再从 $R_{c a n d i d a t e} (a)$ 集合中选择属性，由此在用户2下得到约简 $\{a_{3}, a_{5}, a_{2}\}$ ．同理，基于用户3偏好下的约简结果为 $\{a_{1}, a_{4}, a_{5}\}$ ．可以看到实例中用户偏好动态增加，约简集也动态更新，即 $\{a_{3}, a_{2}, a_{4}\} \Rightarrow \{a_{3}, a_{5}, a_{2}\} \Rightarrow \{a_{1}, a_{4}, a_{5}\}$ ．

4 实验分析

为了验证本文算法的有效性，在四组UCI数据集上进行了实验分析．分别用 $a, b, c, d$ 代表Lymphography数据集、Lung⁃cancer数据集、Dermatology数据集和Connect⁃4数据集条件属性，其中Connect⁃4数据集中选取部分数据进行实验，四组UCI数据集信息如表3所示．

表3 实验中使用的UCI数据集

Table 3 UCI datasets used in experiments

数据集	样本数量	属性数量
Lymphography	148	18
Lung⁃cancer	32	56
Dermatology	366	34
Connect⁃4	497	42

实验中模拟动态获取10个用户偏好的情形，对10个用户的属性偏好采用随机不均等的分组方式，设置组数 $G = 3$ ，并采用分布函数的方式设定属性的代价 $t (a_{i})$ 为 $[1,20]$ 中的随机数．主要针对约简更新，约简分类精度和多用户偏好下约简的优劣三个方面进行实验．其中，分类算法为CART算法和基于线性核函数的SVM算法，并进行100次分类验证取其均值．

表4至表7展示了10个用户以不同顺序增加用户偏好的情形下约简集合变化的趋势，“ $↑$ ”表示新增属性，“ $↓$ ”表示删除属性，“---”表示约简未改变．由表可见，对于新增用户偏好，属性子集也相应动态更新，并且以不同的顺序增加用户偏好时，其约简子集的变化也是不同的．但是，考虑10个用户的属性偏好，无论用户增加的顺序如何，最终的约简结果都是相同的．其原因在于，在10个用户偏好确定的情形下，融合后的用户偏好矩阵就是唯一的，则每个属性的用户偏好指标也是唯一的，这使得最终的约简结果也是相同的．

表4 Lymphography数据集上的约简更新过程

Table 4 Reduction update process on Lymphography dataset

UserID	Reduct	UserID	Reduct
1	$a_{5}, a_{14}, a_{12}, a_{2}, a_{6}, a_{11}, a_{8}, a_{18}, a_{1}$	10	$a_{12}, a_{15}, a_{5}, a_{13}, a_{2}, a_{10}, a_{14}$
2	$↑ a_{3}, a_{15}, ↓ a_{5}, a_{11}, a_{1}$	9	$↑ a_{17}, a_{18}, ↓ a_{5}, a_{10}$
3	---	8	$↑ a_{16}, ↓ a_{12}, a_{17}$
4	$↑ a_{11}, a_{10}, ↓ a_{2}, a_{6}$	7	$↑ a_{5}, a_{1}, a_{11}, ↓ a_{18}, a_{16}$
5	$↑ a_{2}, a_{6}, ↓ a_{11}, a_{10}$	6	$↑ a_{18}, a_{12}, a_{17}, ↓ a_{5}, a_{1}, a_{11}$
6	$↑ a_{17}, a_{13}, ↓ a_{2}, a_{8}$	5	$↑ a_{1}, ↓ a_{12}$
7	$↑ a_{1}, ↓ a_{3}, a_{17}$	4	$↑ a_{12}, ↓ a_{1}$
8	---	3	---
9	---	2	---
10	$↑ a_{3}, a_{11}, ↓ a_{1}, a_{6}$	1	$↑ a_{3}, a_{11}, ↓ a_{17}, a_{2}$
Final	$a_{3}, a_{12}, a_{15}, a_{18}, a_{13}, a_{14}, a_{11}$	Final	$a_{3}, a_{12}, a_{15}, a_{18}, a_{13}, a_{14}, a_{11}$

表5 Lung⁃cancer数据集上的约简更新过程

Table 5 Reduction update process on Lung⁃cancer dataset

UserID	Reduct	UserID	Reduct
1	$b_{17}, b_{21}, b_{30}, b_{12}, b_{33}, b_{28}, b_{53}, b_{27}$	10	$b_{18}, b_{33}, b_{32}, b_{43}, b_{5}, b_{10}, b_{56}, b_{28}, b_{16}$
2	$↑ b_{38}, b_{5}, b_{55}, b_{52}, b_{8}, ↓ b_{17}, b_{21}, b_{30}, b_{53}, b_{27}$	9	$↑ b_{12}, b_{38}, b_{3}, ↓ b_{18}, b_{32}, b_{43}, b_{56}, b_{28}, b_{16}$
3	$↑ b_{40}, b_{15}, b_{6}, ↓ b_{33}, b_{38}, b_{28}, b_{55}, b_{8}$	8	$↑ b_{18}, b_{21}, b_{7}, b_{11}, b_{16}, ↓ b_{38}, b_{10}, b_{3}$
4	$↑ b_{46}, b_{30}, b_{16}, ↓ b_{40}, b_{15}$	7	$↑ b_{38}, b_{55}, b_{8}, b_{10}, ↓ b_{21}, b_{7}, b_{11}, b_{16}$
5	$↑ b_{21}, b_{38}, ↓ b_{12}, b_{16}$	6	$↑ b_{7}, b_{2}, ↓ b_{38}, b_{8}, b_{10}$
6	---	5	$↑ b_{38}, b_{32}, b_{30}, b_{25}, ↓ b_{18}, b_{5}, b_{12}, b_{55}, b_{2}$
7	$↑ b_{33}, b_{12}, ↓ b_{5}, b_{46}, b_{21}$	4	---
8	$↑ b_{5}, b_{21}, b_{46}, ↓ b_{33}, b_{12}$	3	$↑ b_{18}, b_{5}, b_{21}, b_{12}, b_{10}, ↓ b_{32}, b_{7}, b_{25}$
9	---	2	$↑ b_{52}, b_{15}, b_{6}, ↓ b_{18}, b_{38}, b_{30}, b_{12}, b_{10}$
10	$↑ b_{33}, b_{32}, ↓ b_{5}, b_{46}$	1	$↑ b_{38}, b_{32}, b_{30}, ↓ b_{5}, b_{15}$
Final	$b_{33}, b_{21}, b_{38}, b_{32}, b_{52}, b_{30}, b_{6}$	Final	$b_{33}, b_{21}, b_{38}, b_{32}, b_{52}, b_{30}, b_{6}$

表6 Dermatology数据集上的约简更新过程

Table 6 Reduction update process on Dermatology dataset

UserID	Reduct	UserID	Reduct
1	$c_{33}, c_{17}, c_{16}, c_{19}, c_{21}, c_{9}, c_{4}, c_{5}, c_{18}$	10	$c_{14}, c_{4}, c_{1}, c_{32}, c_{26}, c_{18}, c_{34}$
2	$↑ c_{8}, c_{1}, c_{34}, ↓ c_{33}, c_{16}, c_{9}, c_{5}, c_{18}$	9	$↑ c_{12}, c_{3}, ↓ c_{18}$
3	$↑ c_{3}, c_{33}, c_{26}, ↓ c_{8}, c_{4}$	8	---
4	$↑ c_{29}, c_{16}, ↓ c_{33}, c_{1}$	7	$↑ c_{33}, c_{10}, c_{5}, c_{9}, c_{28}, ↓ c_{12}, c_{34}$
5	$↑ c_{4}, ↓ c_{16}, c_{26}$	6	$↑ c_{24}, c_{21}, c_{18}, ↓ c_{10}, c_{26}, c_{5}, c_{28}$
6	---	5	---
7	$↑ c_{8}, c_{9}, ↓ c_{17}, c_{29}$	4	$↑ c_{8}, ↓ c_{33}$
8	$↑ c_{17}, c_{29}, c_{1}, c_{18}, c_{23}, c_{32}, ↓ c_{8}, c_{34}$	3	$↑ c_{12}, ↓ c_{8}$
9	$↑ c_{33}, c_{15}, c_{34}, ↓ c_{3}, c_{29}, c_{19}, c_{9}, c_{18}, c_{23}, c_{32}$	2	$↑ c_{17}, c_{34}, ↓ c_{12}, c_{1}, c_{9}, c_{24}, c_{18}, c_{14}$
10	$↑ c_{3}, c_{32}, ↓ c_{33}, c_{1}, c_{15}$	1	---
Final	$c_{3}, c_{17}, c_{4}, c_{21}, c_{32}, c_{34}$	Final	$c_{3}, c_{17}, c_{4}, c_{21}, c_{32}, c_{34}$

表7 Connect⁃4数据集上的约简更新过程

Table 7 Reduction update process on Connect⁃4 dataset

UserID	Reduct	UserID	Recuct
1	$d_{8}, d_{16}, d_{26}, d_{24}, d_{2}, d_{7}, d_{3}, d_{25}, d_{37}, d_{13},$ $d_{39}, d_{15}, d_{27}, d_{14}, d_{22}, d_{38}, d_{1}, d_{17}, d_{31}$	10	$d_{15}, d_{27}, d_{1}, d_{7}, d_{38}, d_{37}, d_{33}, d_{8},$ $d_{26}, d_{31}, d_{25}, d_{2}, d_{13}, d_{14}, d_{21}$
2	$↑ d_{21}, ↓ d_{16}, d_{3}, d_{13}, d_{39}, d_{27}, d_{17}$	9	$↑ d_{23}, d_{17}, ↓ d_{27}, d_{33}, d_{25}$
3	---	8	$↑ d_{16}, d_{32}, d_{22}, ↓ d_{2}, d_{13}$
4	$↑ d_{16}, d_{39}, d_{13}, d_{17}, d_{3}, d_{27}, ↓ d_{21}$	7	$↑ d_{13}, ↓ d_{22}$
5	$↑ d_{32}, d_{21}, ↓ d_{24}, d_{14}, d_{26}, d_{39}, d_{13}, d_{17}, d_{3}, d_{27}$	6	---
6	$↑ d_{26}, d_{24}, d_{14}, d_{13}, ↓ d_{32}, d_{8}, d_{7}$	5	---
7	$↑ d_{23}, d_{7}, ↓ d_{24}, d_{22}$	4	---
8	$↑ d_{32}, d_{22}, ↓ d_{38}, d_{7}$	3	---
9	$↑ d_{38}, d_{8}, d_{7}, d_{17}, ↓ d_{22}, d_{25}, d_{2}$	2	---
10	$↑ d_{25}, ↓ d_{17}$	1	$↑ d_{25}, ↓ d_{17}$
Final	$d_{16}, d_{15}, d_{26}, d_{31}, d_{32}, d_{38}, d_{23}, d_{1},$ $d_{8}, d_{7}, d_{14}, d_{13}, d_{25}, d_{37}, d_{21}$	Final	$d_{16}, d_{15}, d_{26}, d_{31}, d_{32}, d_{38}, d_{23}, d_{1},$ $d_{8}, d_{7}, d_{14}, d_{13}, d_{25}, d_{37}, d_{21}$

图4至图7展示了随着用户顺序增加的情形下，不同用户组的约简使用CART（Classification And Regression Tree）和SVM（Support Vector Machine）分类器的平均分类精度．由图可见，不断更新的约简和原始属性的分类精度相比，能保持与原始信息系统的分类结果差异不大，在Lung⁃cancer数据集中有略微提升，Dermatology数据集中有略微下降，但整体相差不大．可见，约简前后信息系统的分类能力基本不变．

图4

图4 Lymphography数据集上使用不同分类器的分类精度

Fig.4 Classification accuracy of different classifier on Lymphography dataset

图5

图5 Lung⁃cancer数据集上使用不同分类器的分类精度

Fig.5 Classification accuracy of different classifier on Lung⁃cancer dataset

图6

图6 Dermatology数据集上使用不同分类器的分类精度

Fig.6 Classification accuracy of different classifier on Dermatology dataset

图7

图7 Connect⁃4数据集上使用不同分类器的分类精度

Fig.7 Classification accuracy of different classifier on Connect⁃4 dataset

为了从用户偏好角度衡量不同约简的优劣，引入子集平均偏好因子（SAP）^［19］定量评判约简的优劣．表示约简集合整体所处于该属性组序下的平均位置．给定属性组序 $S = G_{n} > G_{n - 1} > \dots > G_{2} > G_{1}$ 以及约简集合 $A = \{a_{1}, a_{2}, \dots, a_{m}\}$ ，集合 $A$ 中每个属性所在属性组序 $S$ 里的位置下标即为该属性的贡献度，记为 $p (a_{m})$ ．则约简集合 $A$ 的平均偏好因子为 $S A P (A) = \sum_{i = 1}^{m} p (a_{i}) / m$ ．

图8至图11展示了以顺序和逆序的方式在不同用户组数下所得到的约简在多用户偏好下的平均 $S A P$ 变化曲线．随着用户数的增加，多用户的需求更明确，希望得到的约简子集能较好地综合多用户的需求．由图可见，在属性组数为三的情形下，约简子集在多用户偏好下的平均 $S A P$ 中等偏上，表明该约简的大部分属性来源于偏好较高的分组，可以满足多用户对属性偏好的需求．其次，平均 $S A P$ 随用户数的增加而趋于稳定，证明该算法能较好地综合多用户需求，得到的约简也能较好地满足多用户需求．

图8

图8 Lymphography数据集上的平均SAP

Fig.8 Average SAP onLymphography dataset

图9

图9 Lung⁃cancer数据集上的平均SAP

Fig.9 Average SAP onLung⁃cancer dataset

图10

图10 Dermatology数据集上的平均SAP

Fig.10 Average SAP onDermatology dataset

图11

图11 Connect⁃4数据集上的平均SAP

Fig.11 Average SAP onConnect⁃4 dataset

5 结论

本文针对多用户对属性的偏好不同的情形，提出一种基于三支决策的动态属性约简方法．通过融合多用户偏好定量描述各个属性偏好程度，再结合现实中的代价问题，将属性偏好度和代价结合，定义一种新的属性重要度度量方式作为启发信息.对于动态改变的用户偏好，采用三支决策理论对属性集三分，以达到更新约简的目的．同时，设计了面向多用户的初始化约简算法和三支动态约简更新算法，并通过实例展示了该算法更新约简的过程．实验结果证明本文提出方法的有效性，能够较好地满足多用户偏好需求，并随着用户偏好的改变更新约简集合．

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Pawlak

Rough sets

International Journal of Computer and Information Sciences，1982，11(5)：341-356.

[2]

Jia

X Y

，Shang

，Zhou

，et al.

Generalized attribute reduct in rough set theory

Knowledge⁃Based Systems，2016(91)：204-218.

[3]

Min

，He

H P

，Qian

Y H

，et al.

Test⁃cost⁃sensitive attribute reduction

Information Sciences，2011，181(22)：4928-4942.

[4]

Wang

，Wang

Reduction algorithms based on discernibility matrix：The ordered attributes method

Journal of Computer Science and Technology，2001，16(6)：489-504.

[5]

Zhao

，Wang

A reduction algorithm meeting users' requirements

Journal of Computer Science and Technology，2002，17(5)：578.

[本文引用: 2]

[6]

韩素青，阴桂梅.

一种面向用户需求的属性约简算法

模式识别与人工智能，2014，27(3)：281-288.

Han

S Q

，Yin

G M

An user⁃oriented attribute reduct construction algorithm

Pattern Recognition and Artificial Intelligence，2014，27(3)：281-288.

[7]

Yao

Y Y

，Zhao

，Wang

，et al.

A model of machine learning based on user preference of attributes

∥International Conference on Rough Sets and Current Trends in Computing. Springer Berlin Heidelberg，2006：587-596.

[8]

Yao

Y Y

，Zhao

，Wang

，et al.

A model of user⁃oriented reduct construction for machine learning

∥Transactions on rough sets VIII. Springer Berlin Heidelberg，2008：332-351.

[9]

Liang

H L

，Wang

，Yao

Y Y

User⁃oriented feature selection for machine learning

The Computer Journal，2007，50(4)：421-434.

[10]

官礼和，王国胤，于洪.

属性序下的增量式Pawlak约简算法

西南交通大学学报，2011，46(3)：461-468.

Guan

L H

，Wang

G Y

，Yu

Incremental algorithm of Pawlak reduction based on attribute order

Journal of Southwest Jiaotong University，2011，46(3)：461-468.

[11]

官礼和，王国胤，胡峰.

一种基于属性序的决策规则挖掘算法

控制与决策，2012，27(2)：313-316.

Guan

L H

，Wang

G Y

，Hu

A decision rules mining algorithm based on attribute order

Control and Decision，2012，27(2)：313-316.

[12]

Yue

X D

，Chen

Y F

，Qian

，et al.

Attributes reduction model with user preferences

∥2014 IEEE 7^th Joint International Information Technology and Artificial Intelligence Conference. Chongqing，China：IEEE，2014：191-196.

[13]

Jing

Y G

，Li

T R

，Fujita

，et al.

An incremental attribute reduction method for dynamic data mining

Information Sciences，2018(465)：202-218.

[14]

F M

，Ding

M W

，Zhang

T F

，et al.

Compressed binary discernibility matrix based incremental attribute reduction algorithm for group dynamic data

Neurocomputing，2019(344)：20-27.

[15]

Wang

，Liang

J Y

，Dang

C Y

Attribute reduction for dynamic data sets

Applied Soft Computing，2013，13(1)：676-689.

[16]

王国胤

. Rough集理论与知识获取. 西安：西安交通大学出版社，2001：23-26，133-136.

[本文引用: 5]

[17]

刘盾，李天瑞，杨新，等.

三支决策：基于粗糙集与粒计算研究视角

智能系统学报，2019，14(6)：1111-1120.

[本文引用: 2]

Liu

，Li

T R

，Yang

，et al.

Three⁃way decisions：Research perspectives for rough sets and granular computing

CAAI Transactions on Intelligent Systems，2019，14(6)：1111-1120.

[本文引用: 2]

[18]

Yao

Y Y

Three⁃way decision and granular computing

International Journal of Approximate Reasoning，2018(103)：107-123.

[19]

刘鑫，胡军，张清华.

属性组序下基于代价敏感的约简方法

南京大学学报(自然科学)，2020，56(4)：469-479.

Liu

，Hu

，Zhang

Q H

Attribute reduction based on cost sensitive under attribute group order

Nanjing University (Natural Science)，2020，56(4)：469-479.