含属性加权模糊序决策信息系统的近似约简

doi:10.13232/j.cnki.jnju.2022.02.009

含属性加权模糊序决策信息系统的近似约简

徐伟华^,, 孔子默, 陈曜琦

西南大学人工智能学院，重庆，400715

Approximate reduction of fuzzy ordered decision information system with attribute weighting

Xu Weihua^,, Kong Zimo, Chen Yaoqi

College of Artificial Intelligent，Southwest University，Chongqing，400715，China

通讯作者: E⁃mail：chxuwh@gmail.com

收稿日期: 2021-10-22

基金资助:

国家自然科学基金. 61976245

Received: 2021-10-22

摘要

为保证关键属性在属性约简时能够被保留，可对信息系统的属性进行加权，从而提高关键属性的影响力.基于此，在属性加权的模糊序决策信息系统中建立了上、下近似约简的模型，得到两种约简的判定定理，并且给出求解上、下近似约简的辨识矩阵以及约简方法.最后，通过实例验证了该约简方法的有效性.

关键词： 辨识矩阵 ; 模糊序决策信息系统 ; 属性加权 ; 近似约简

Abstract

In order to ensure that the key attributes can be retained during attribute reduction process，attributes of the information system can be weighted，so as to improve the influence of the key attributes. Based on this，this paper establishes the models of upper and lower approximate reduction in fuzzy order decision information system with attribute weighting，obtains the judgment theorems of two kinds of reduction，and gives the identification matrix and reduction method for solving the upper and lower approximate reduction. Finally，an example is given to verify the effectiveness of the reduction method.

Keywords： identification matrix ; fuzzy ordered decision information system ; attribute weighting ; approximate reduction

PDF (365KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

徐伟华, 孔子默, 陈曜琦. 含属性加权模糊序决策信息系统的近似约简. 南京大学学报（自然科学）[J], 2022, 58(2): 255-263 doi:10.13232/j.cnki.jnju.2022.02.009

Xu Weihua, Kong Zimo, Chen Yaoqi. Approximate reduction of fuzzy ordered decision information system with attribute weighting. Journal of nanjing University[J], 2022, 58(2): 255-263 doi:10.13232/j.cnki.jnju.2022.02.009

粗糙集理论是1982年由波兰科学院院士、华沙理工大学教授Pawlak提出的，用于处理不确定、不精确和模糊知识的软计算，其主要是利用已知的信息来近似描述不确定的、模糊的信息.在分类问题中，粗糙集理论利用特征来归纳二元关系，从而将样本区分开.研究知识约简正是利用不同二元关系下形成的类以对特征进行提取.目前，在数据挖掘^［1-4］、模式识别^［5-6］、人工智能以及智能信息处理^［7-10］等领域有广泛的应用.

粗糙集理论经过多年的发展，已经形成了比较完善的理论体系.属性约简是粗糙集理论体系中非常重要的一个部分，要求在决策能力和知识库分类不变的情况下，尽可能地删除其中不相关或者不重要的属性，从而消除冗余的属性，在降低空间复杂度和时间复杂度的情况下没有丢失重要的信息^［10］.目前，已经有很多学者对属性约简进行了深入研究^［11-17］.

模糊集是1965年由美国学者Zadeh提出的，它将经典集合进行扩充、推广，引入元素隶属度这一概念，对生活中那些不确定的问题量化、建模以及研究.模糊集是研究不确定性问题的一个重要工具.在模糊集中，元素与集合的关系不再是简单的属于或不属于，而是利用一个在0到1之间的隶属度来表示和刻画的.

属性加权是根据个人的喜好以及对事物的认知，人为地给不同的事物添加权重，事物的重要程度是根据个人的认知与习惯而改变的.属性加权在生活中有重要的作用，据此可以对不同的事物进行分类，而将其加入模糊序信息系统则可以更好地量化生活中不确定的事物，并按照个人的偏好对其进行重要程度的排序.

现实生活中，很多不确定性问题的信息系统属于不协调的基于属性加权的模糊序决策信息系统.因此，本文首先定义模糊序关系，根据个人喜好对每个属性加权，并根据加权得分函数重新定义模糊序信息系统，引入决策属性，从而建立不协调属性加权的模糊序决策信息系统.在此基础上引入上、下近似函数，上、下近似协调集以及上、下近似约简，上、下近似约简辨识矩阵，得到近似约简的方法，并通过案例分析比较了两种约简方法的优劣性.

1 基于属性加权的模糊序决策信息系统

决策信息系统是既有条件属性也有决策属性的一种特殊的信息系统，其研究的主要问题是这两种属性之间的关系.为了方便理解，下面给出一些相关的基本概念.

定义1^［10］

$I = (U, A T ⋃ D T, F, G)$ 是一个五元组，称为决策信息系统； $(U, A T, F)$ 是一个三元组，称为信息系统； $A T$ 被称为条件属性集， $D T$ 被称为目标属性集.其中，

$U$ 为对象集， $U = \{x_{1}, x_{2}, \dots, x_{n}\}$ ；

$A T$ 为条件属性集， $A T = \{a_{1}, a_{2}, \dots, a_{m}\}$ ；

$D T$ 为决策属性集， $D T = \{d_{1}, d_{2}, \dots, d_{p}\}$ ；

$F$ 是 $U$ 与 $A T$ 的关系集， $F = \{f_{k} : U \to V_{k},$

$k \leq p\}$ ，其中， $V_{k}$ 是 $a_{k}$ 的值域；

$G$ 是 $U$ 与 $D T$ 的关系集， $G = \{g_{k^{'}} : U \to V_{k^{'}},$

$k^{'} \leq q\}$ ，其中， $V_{k^{'}}$ 是 $d_{k^{'}}$ 的值域.

定义2^［10］

设 $I = (U, A T ⋃ \{d\}, F, G)$ 为决策信息系统，对任意的 $f \in F, g \in G, a \in A T, x \in U$ 都有：

f (x_{i}, a) = μ_{a} (x_{i}), g (x, d) \in R (R 为 实 数 集)

其中， $μ_{a} : U \to [0,1]$ 并满足 $0 \leq μ_{a} (x) \leq 1$ . $μ_{a} (x)$ 称为 $x \in U$ 在条件属性 $a$ 下的隶属度，记 $f (a) = \{f (x, a)| a \in A T\}$ ，称 $f (a)$ 为 $U$ 上的模糊集， $I_{*} = (U, A T ⋃ \{d\}, F, G)$ 为模糊决策信息系统.

定义3

设 $I = (U, A T ⋃ D T, F, G)$ 为一个模糊决策信息系统， $\forall x \in U, \forall a_{i} \in A T$ ，定义对象 $x$ 对属性 $(a_{1}, a_{2}, \dots, a_{n})$ 的加权等分函数为：

S (x) = \sum_{i = 1}^{n} ω_{i} μ_{a_{i}} (x), i = 1,2, \dots, n

其中， $μ_{a_{i}} (x)$ 表示对象 $x$ 在条件属性 $a_{i}$ 下的隶属度， $ω_{i}$ 表示在属性 $a_{i}$ 下的权重，对于所有属性权重满足 $ω_{1} + ω_{2} + ω_{3} + \dots + ω_{n} = 1 (0 \leq ω_{i} \leq 1,$

i = 1,2, \dots, n)

$ω_{i}$ 为 $a_{i}$ 的权重，在得分评价时，越看重某个属性，对应的 $ω_{i}$ 越大.因此，需要根据实际需求，给出相应的权重.

以上可以得出在模糊序信息系统中对象集在条件属性下的得分情况，并根据得分的大小得出之间的大小关系.下面考虑这样的优势关系.

定义4

称一个四元数组 $I_{*}^{\leq} = (U, A T ⋃ \{d\},$

$F, G)$ 为模糊决策信息系统，对于 $A \subseteq A T$ ，令：

\begin{array}{l} R_{A}^{\leq} = \{(x_{i}, x_{j}) \in U \times U| x_{i} \leq x_{j}\} = \\ \{(x_{i}, x_{j}) \in U \times U| S (x_{i}) \leq S (x_{j}), \forall a \in A, f \in F\} \end{array}

R_{d}^{\leq} = \{(x_{i}, x_{j}) \in U \times U| g (x_{i}, d) \leq g (x_{j}, d), g \in G\}

$R_{A}^{\leq}, R_{d}^{\leq}$ 称为模糊序决策信息系统的优势关系，此时该决策信息系统称为基于优势关系下的模糊序决策信息系统.

记：

\begin{array}{l} {[x_{i}]}_{A}^{\leq} = \{x_{j} \in U| (x_{i}, x_{j}) \in R_{A}^{\leq}\} = \\ \{x_{j} \in U| S (x_{i}) \leq S (x_{j}), \forall a \in A, f \in F\} \end{array}

{[x_{i}]}_{d}^{\leq} = \{x_{j} \in U| g (x_{i}, d) \leq g (x_{j}, d), \forall g \in G\}

定理1

设 $I_{*}^{\leq} = (U, A T ⋃ \{d\}, F, G)$ 为模糊序决策信息系统， $R_{A}^{\leq}, R_{d}^{\leq}$ 称为模糊序决策信息系统的优势关系，则以下命题成立：

（1） $R_{A}^{\leq}$ 满足自反性和传递性，未必满足对称性，因而不一定是等价关系.

（2）若 $B_{1} \subseteq B_{2} \subseteq A T$ ，则 $R_{A T}^{\leq} \subseteq R_{B_{2}}^{\leq} \subseteq R_{B_{1}}^{\leq}$ .

（3）若 $B_{1} \subseteq B_{2} \subseteq A T$ ，则 ${[x_{i}]}_{A T}^{\leq} \subseteq {[x_{i}]}_{B_{2}}^{\leq} \subseteq$

{[x_{i}]}_{B_{1}}^{\leq}

（4）若 $x_{j} \in {[x_{i}]}_{A}^{\leq}$ ，则 ${[x_{j}]}_{A}^{\leq} \subseteq {[x_{i}]}_{A}^{\leq}$ .

对于任意 $X \subseteq U$ ，定义 $X$ 在优势关系 $R_{A}^{\leq}$ 下的下近似和上近似分别为：

\begin{array}{l} \underset{̲}{R_{A}^{\leq}} (X) = \{x_{i} \in U : {[x_{i}]}_{A}^{\leq} \subseteq X\} \\ \bar{R_{A}^{\leq}} (X) = \{x_{i} \in U : {[x_{i}]}_{A}^{\leq} ⋂ X \neq \emptyset\} \end{array}

根据上述定理，即可求出决策信息系统的上、下近似.后续章节将研究不协调模糊序信息系统的近似约简的具体基于辨识矩阵的求解方法.

2 不协调模糊序信息系统的近似约简

由于优势关系不同于等价关系，在对象集上不能形成划分，而是形成一个覆盖，因此，对于优势关系下的模糊序信息系统，不能采用Pawlak的近似空间下决策信息系统中的方法定义分布函数和最大分布函数.下面给出模糊序决策信息系统的分布函数和最大分布函数的定义.

定义5

设 $I = (U, A T ⋃ \{d\}, F, G)$ 是模糊序决策信息系统， $R_{A}^{\leq}, R_{d}^{\leq}$ 分别为条件属性集 $A T$ 和决策属性 $d$ 生成的 $U$ 上的优势关系，对于 $A \subseteq A T, x \in U$ ，记：

U / R_{A}^{\leq} = \{{[x_{i}]}_{A}^{\leq} : x_{i} \in U\}

U / R_{d}^{\leq} = \{D_{1}, D_{2}, \dots, D_{r}\}

σ_{A}^{\leq} = (\underset{̲}{R_{A}^{\leq}} (D_{1}), \underset{̲}{R_{A}^{\leq}} (D_{2}), \dots, \underset{̲}{R_{A}^{\leq}} (D_{r}))

λ_{A}^{\leq} = (\bar{R_{A}^{\leq}} (D_{1}), \bar{R_{A}^{\leq}} (D_{2}), \dots, \bar{R_{A}^{\leq}} (D_{r}))

称 $σ_{A}^{\leq}$ 与 $λ_{A}^{\leq}$ 分别为 $U$ 上关于属性子集 $A$ 的下近似函数与上近似函数.

定义6

设 $I = (U, A T ⋃ \{d\}, F, G)$ 是模糊序决策信息系统， $A \subseteq A T$ ：

若 $σ_{A}^{\leq} = σ_{A T}^{\leq}$ ，则称 $A$ 是下近似协调集；进一步，若 $A$ 是下近似协调集，且 $A$ 的任意真子集都不是下近似协调集，则称 $A$ 是下近似约简.

若 $λ_{A}^{\leq} = λ_{A T}^{\leq}$ ，则称 $A$ 是上近似协调集；进一步，若 $A$ 是上近似协调集，且 $A$ 的任意真子集都不是上近似协调集，则称 $A$ 是上近似约简.

定理2

设 $I = (U, A T ⋃ \{d\}, F, G)$ 为模糊序决策信息系统， $A \subseteq A T$ ，则：

（1）若属性子集 $A$ 为下近似协调集，当且仅当对于 $\forall D_{i} \in U / R_{d}^{\leq}$ ，都有 $\underset{̲}{R_{A}^{\leq}} (D_{i}) = \underset{̲}{R_{A T}^{\leq}} (D_{i})$ 时成立.

（2）若属性子集 $A$ 为上近似协调集，当且仅当对于 $\forall D_{i} \in U / R_{d}^{\leq}$ ，都有 $\bar{R_{A}^{\leq}} (D_{i}) = \bar{R_{A T}^{\leq}} (D_{i})$ 时成立.

证明

（1）对于下近似协调集的情况证明如下.

充分性：利用反证法证明.

假设 $\exists D_{k} \in U / R_{d}^{\leq}$ ，使得 $\underset{̲}{R_{A}^{\leq}} (D_{k}) \neq \underset{̲}{R_{A T}^{\leq}} (D_{i})$ 成立，那么，由前文可知 $\underset{̲}{R_{A}^{\leq}} (D_{k}) \subseteq \underset{̲}{R_{A T}^{\leq}} (D_{k})$ ，那么只少存在一个 $\underset{̲}{R_{A T}^{\leq}} (D_{k})$ ，使得 $\underset{̲}{R_{A T}^{\leq}} (D_{k}) \in σ_{A T}^{\leq}$ 且 $\underset{̲}{R_{A T}^{\leq}} (D_{k}) \notin σ_{A}^{\leq}$ ，同样也至少存在一个 $\underset{̲}{R_{A}^{\leq}} (D_{k})$ ，使得 $\underset{̲}{R_{A}^{\leq}} (D_{k}) \in σ_{A}^{\leq} 且 \underset{̲}{R_{A}^{\leq}} (D_{k}) \notin σ_{A T}^{\leq}$ ，那么 $σ_{A}^{\leq} \neq σ_{A T}^{\leq}$ .然而，属性子集 $A$ 为下近似协调集，推导结论 $σ_{A}^{\leq} \neq σ_{A T}^{\leq}$ 与定义6相矛盾.所以，充分性即证明.

必要性：同样使用反证法证明.

假设属性子集 $A$ 不是下近似协调集，那么 $σ_{A}^{\leq} \neq σ_{A T}^{\leq}$ ，然而，对于属性子集 $A$ ， $\forall D_{i} \in U / R_{d}^{\leq}$ ，都有 $\underset{̲}{R_{A}^{\leq}} (D_{i}) = \underset{̲}{R_{A T}^{\leq}} (D_{i})$ ，显然 $σ_{A}^{\leq} = σ_{A T}^{\leq}$ ，矛盾.所以必要性即证明.

（2）与（1）同理可证.

表1给出了一个模糊序决策信息系统.

表1 一个模糊序决策信息系统

Table 1 A fuzzy ordered decision information system

$U$	$a_{1} (ω_{1} = 0.1)$	$a_{2} (ω_{2} = 0.4)$	$a_{3} (ω_{3} = 0.5)$	$d$
$x_{1}$	$0.7$	$0.3$	$0.9$	$3$
$x_{2}$	$0.5$	$0.1$	$0.1$	$1$
$x_{3}$	$0.5$	$0.3$	$0$	$2$
$x_{4}$	$0.5$	$0.2$	$0.4$	$5$
$x_{5}$	$0.7$	$0.4$	$0.5$	$4$

新窗口打开| 下载CSV

计算可知 $R_{A T}^{\leq} \subseteq R_{d}^{\leq}$ 是不成立的，因此，该模糊序信息系统是不协调的.对属性 $(a_{1}, a_{2}, a_{3})$ 加权 $(ω_{1} = 0.1, ω_{2} = 0.4, ω_{3} = 0.5)$ .记：

D_{1} = {[x_{1}]}_{d}^{\leq} = \{x_{1}, x_{4}, x_{5}\}

D_{2} = {[x_{2}]}_{d}^{\leq} = \{x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\}

D_{3} = {[x_{3}]}_{d}^{\leq} = \{x_{1}, x_{3}, x_{4}, x_{5}\}

D_{4} = {[x_{4}]}_{d}^{\leq} = \{x_{4}\}

D_{5} = {[x_{5}]}_{d}^{\leq} = \{x_{4}, x_{5}\}

有：

\begin{array}{l} S_{x_{1}} = 0.64, S_{x_{2}} = 0.14, S_{x_{3}} = 0.17, \\ S_{x_{4}} = 0.33, S_{x_{5}} = 0.48 \end{array}

又：

{[x_{1}]}_{A T}^{\leq} = \{x_{1}\}

{[x_{2}]}_{A T}^{\leq} = \{x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\}

{[x_{3}]}_{A T}^{\leq} = \{x_{1}, x_{2}, x_{4}, x_{5}\}

{[x_{4}]}_{A T}^{\leq} = \{x_{1}, x_{4}, x_{5}\}

{[x_{5}]}_{A T}^{\leq} = \{x_{1}, x_{5}\}

计算可得：

\underset{̲}{R_{A T}^{\leq}} (D_{1}) = \{x_{1}, x_{4}, x_{5}\}

\underset{̲}{R_{A T}^{\leq}} (D_{2}) = \{x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\}

\underset{̲}{R_{A T}^{\leq}} (D_{3}) = \{x_{1}, x_{3}, x_{4}, x_{5}\}

\underset{̲}{R_{A T}^{\leq}} (D_{4}) = \emptyset

\underset{̲}{R_{A T}^{\leq}} (D_{5}) = \emptyset

\bar{R_{A T}^{\leq}} (D_{1}) = \{x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\}

\bar{R_{A T}^{\leq}} (D_{2}) = \{x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\}

\bar{R_{A T}^{\leq}} (D_{3}) = \{x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\}

\bar{R_{A T}^{\leq}} (D_{4}) = \{x_{2}, x_{3}, x_{4}\}

\bar{R_{A T}^{\leq}} (D_{5}) = \{x_{2}, x_{3}, x_{4}, x_{5}\}

若取 $A = \{a_{2}, a_{3}\}$ ，则：

\begin{array}{l} S_{x_{1}}^{'} = 0.57, S_{x_{2}}^{'} = 0.09, S_{x_{3}}^{'} = 0.12, \\ S_{x_{4}}^{'} = 0.28, S_{x_{5}}^{'} = 0.41 \end{array}

\underset{̲}{R_{A}^{\leq}} (D_{1}) = \{x_{1}, x_{4}, x_{5}\} = \underset{̲}{R_{A T}^{\leq}} (D_{1})

\underset{̲}{R_{A}^{\leq}} (D_{2}) = \{x_{1}, x_{3}, x_{4}, x_{5}\} = \underset{̲}{R_{A T}^{\leq}} (D_{2})

\underset{̲}{R_{A}^{\leq}} (D_{3}) = \{x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} = \underset{̲}{R_{A T}^{\leq}} (D_{3})

\underset{̲}{R_{A}^{\leq}} (D_{4}) = \emptyset = \underset{̲}{R_{A T}^{\leq}} (D_{4})

\underset{̲}{R_{A}^{\leq}} (D_{5}) = \emptyset = \underset{̲}{R_{A T}^{\leq}} (D_{5})

即 $σ_{A}^{\leq} = σ_{A T}^{\leq}$ ， $A = \{a_{2}, a_{3}\}$ 是下近似协调集.验证可知， $A$ 的任意真子集都不是下近似协调集，所以， $A$ 是下近似约简.

同理可得，当 $A = \{a_{3}\} 时 λ_{A}^{\leq} = λ_{A T}^{\leq}$ ，所以， $A = \{a_{3}\}$ 是上近似约简.

下面给出模糊序信息系统的上近似约简与下近似约简的判定定理.

定理3

设 $I = (U, A T ⋃ \{d\}, F, G)$ 是模糊序信息系统， $A \subseteq A T$ ，则：

（1） $A$ 是下近似协调集，当且仅当对任意 $D_{i} \in U / R_{d}^{\leq}$ ，当 $x_{i} \in \underset{̲}{R_{A T}^{\leq}} (D_{i}), x_{j} \notin \underset{̲}{R_{A T}^{\leq}} (D_{i})$ 时 $S (x_{i}) < S (x_{j})$ 成立.

（2） $A$ 是上近似协调集，当且仅当对任意 $D_{i} \in U / R_{d}^{\leq}$ ，当 $x_{i} \in \bar{R_{A T}^{\leq}} (D_{i}), x_{j} \notin \bar{R_{A T}^{\leq}} (D_{i})$ 时 $S (x_{i}) < S (x_{j})$ 成立.

证明

（1）必要性：假设存在 $D_{i} \in U / R_{d}^{\leq}$ ，当 $x_{i} \in \underset{̲}{R_{A T}^{\leq}} (D_{i}), x_{j} \notin \underset{̲}{R_{A T}^{\leq}} (D_{i})$ 时，都有 $S (x_{i}) < S (x_{j})$ .由优势类的定义可知， $x_{j} \in {[x_{i}]}_{A}^{\leq}$ ，而 $A$ 是下近似协调集，所以对于任意的 $D_{i} \in U / R_{d}^{\leq}$ ，有 $\underset{̲}{R_{A}^{\leq}} (D_{i}) = \underset{̲}{R_{A T}^{\leq}} (D_{i})$ ，故必要性得证.

充分性：若 $A$ 不是下近似协调集，则必然存在 $D_{i} \in U / R_{d}^{\leq}$ ，使得 $\underset{̲}{R_{A}^{\leq}} (D_{i}) \neq \underset{̲}{R_{A T}^{\leq}} (D_{i})$ ，即存在 $x \in \underset{̲}{R_{A T}^{\leq}} (D_{i})$ ，但 $x \notin \underset{̲}{R_{A}^{\leq}} (D_{i})$ ，故有 ${[x]}_{A T}^{\leq} \subseteq D_{i}$ ，但 ${[x]}_{A}^{\leq} ⊄ D_{i}$ .而 ${[x]}_{A T}^{\leq} \subseteq {[x]}_{A}^{\leq}$ ，故存在 $x_{0} \in {[x]}_{A}^{\leq}$ ，但 $x_{0} \notin D_{i}$ ，从而 $x_{0} \notin \underset{̲}{R_{A T}^{\leq}} (D_{i})$ .所以有 $x \in \underset{̲}{R_{C}^{\leq}} (D_{i})$ ， $x_{0} \notin \underset{̲}{R_{A T}^{\leq}} (D_{i})$ ，故存在 $a_{k} \in A$ ，使得 $S (x_{i}) > S (x_{j})$ ，与 $x_{0} \in {[x]}_{A}^{\leq}$ 矛盾.故充分性得证.

（2）方法同（1）.

3 上、下近似约简的辨识矩阵及约简方法

前文已经介绍了上近似约简和下近似约简的定义以及判定定理.然而，直接利用定义求解上、下近似的过程过于复杂，现给出辨识矩阵的定义，利用辨识矩阵求出上近似约简和下近似约简.

定义7

设 $I = (U, A T ⋃ \{d\}, F, G)$ 是不协调模糊序信息系统，记 $D_{f} = \{(x_{i}, x_{j}) : x_{i} \in \underset{̲}{R_{A T}^{\leq}} (D_{i}), x_{j} \notin \underset{̲}{R_{A T}^{\leq}} (D_{i}), D_{i} \in R_{d}^{\leq}\}$ ，分别定义上近似辨识矩阵和下近似辨识矩阵：

将属性按照权重 $ω$ 从大到小的顺序排列，比较 $F_{i, n} = \sum_{k = 1}^{n} ω_{k} μ_{a_{k}} (x_{i}), (n = 1,2, \dots, m)$ 与 $F_{j, n} = \sum_{k = 1}^{n} ω_{k} μ_{a_{k}} (x_{j}) (n = 1,2, \dots, m)$ 的大小.如果 $F_{i, n} < F_{j, n}$ ，则记录下此时的 $a_{n}$ ，否则，记为 $\emptyset$ .

D_{λ} \{x_{i}, x_{j}\} = \{\begin{matrix} \{a_{n} \in A T : F_{i, n} < F_{j, n}\}, (x_{i}, x_{j}) \in D_{f} \\ \emptyset, (x_{i}, x_{j}) \notin D_{f} \end{matrix}

使用与刚才求 $D_{λ} \{x_{i}, x_{j}\}$ 相同的方法，在最后，记录下第一个使得 $F_{i, n} > F_{j, n}$ 的 $a_{n}$ .

D_{σ} \{x_{i}, x_{j}\} = \{\begin{matrix} \{a_{n} \in A T : F_{i, n} > F_{j, n}\} (x_{i}, x_{j}) \in D_{f} \\ \emptyset, (x_{i}, x_{j}) \notin D_{f} \end{matrix}

由 $D_{λ}$ 和 $D_{σ}$ 形成的矩阵 $M_{λ} = (D_{λ} (x_{i}, x_{j}),$

$x_{i}, x_{j} \in U)$ 和 $M_{σ} = (D_{σ} (x_{i}, x_{j}), x_{i}, x_{j} \in U)$ 分别称为上近似辨识矩阵和下近似辨识矩阵.

定理4

设 $I = (U, A T ⋃ \{d\}, F, G)$ 是不协调模糊序信息系统， $A \subseteq A T$ ，则：

（1） $A$ 是上近似协调集，当且仅当对 $\forall (x_{i}, x_{j}) \in D_{f}$ ，有 $A ⋂ D_{λ} (x_{i}, x_{j}) \neq \emptyset$ .

（2） $A$ 是下近似协调集，当且仅当对 $\forall (x_{i}, x_{j}) \in D_{f}$ ，有 $A ⋂ D_{λ} (x_{i}, x_{j}) \neq \emptyset$ .

证明

（1）必要性：对于 $\forall (x_{i}, x_{j}) \in D_{f}$ ，存在 $D_{i} \in U / R_{d}^{\leq}$ ，使得 $x_{i} \in \underset{̲}{R_{A T}^{\leq}} (D_{i}), x_{j} \notin \underset{̲}{R_{A T}^{\leq}} (D_{i})$ .由定理1可知，一定存在 $a_{k} \in A$ ，使得 $F (x_{i}) < F (x_{j})$ ，从而有 $a_{k} \in D_{λ} (x_{i}, x_{j})$ .因此，若 $A$ 是上近似协调集，则 $\forall (x_{i}, x_{j}) \in D_{f}$ ，有 $A ⋂ D_{λ} (x_{i}, x_{j}) \neq \emptyset$ ，得证.

充分性：若对于 $\forall (x_{i}, x_{j}) \in D_{f}$ ，都有 $A ⋂ D_{λ} (x_{i}, x_{j}) \neq \emptyset$ ，则至少存在 $a_{k} \in A$ ，使得 $a_{k} \in D_{λ} (x_{i}, x_{j})$ ，故有 $F (x_{i}) < F (x_{j})$ .而 $x_{i} \in \underset{̲}{R_{A T}^{\leq}} (D_{i})$ ，

$x_{j} \notin \underset{̲}{R_{A T}^{\leq}} (D_{i})$ ，由定理1可知， $A$ 是上近似协调集，得证.

（2）证明过程类似（1）.

定义8

设 $I = (U, A T ⋃ \{d\}, F, G)$ 是不协调模糊序信息系统， $M_{λ}$ 与 $M_{σ}$ 为其上近似辨识矩阵和下近似辨识矩阵，称：

G_{λ} = \land \{\lor \{a_{k} : a_{k} \in D_{λ} (x_{i}, x_{j})\}, x_{i}, x_{j} \in D_{f}\}

G_{σ} = \land \{\lor \{a_{k} : a_{k} \in D_{σ} (x_{i}, x_{j})\}, x_{i}, x_{j} \in D_{f}\}

分别为该模糊序信息系统的上近似辨识函数和下近似辨识函数.

定理5

设 $I = (U, A T ⋃ \{d\}, F, G)$ 是不协调模糊序信息系统，则有：

上近似辨识函数 $G_{λ}$ 的极小析取范式为 $G_{λ} = \overset{p}{\underset{k = 1}{⋁}} (\overset{q_{k}}{\underset{s = 1}{⋀}} a_{s})$ .若记 $B_{λ}^{k} = \{a_{s}, s = 1,2, \dots, q_{k}\}$ ，则 $\{B_{λ}^{k}, k = 1,2, \dots, p\}$ 是所有上近似约简形式的集合.

下近似辨识函数 $G_{σ}$ 的极小析取范式为 $G_{σ} = \overset{p}{\underset{k = 1}{⋁}} (\overset{q_{k}}{\underset{s = 1}{⋀}} a_{s})$ .若记 $B_{σ}^{k} = \{a_{s}, s = 1,2, \dots, q_{k}\}$ ，则 $\{B_{λ}^{k}, k = 1,2, \dots, p\}$ 是所有下近似约简形式的集合.

证明

对于 $\forall (x_{i}, x_{j}) \in D_{f}$ ，由极小析取范式的定义可知：

B_{λ}^{k} ⋂ D_{λ} (x_{i}, x_{j}) \neq \emptyset

再由前面的定理可知 $B_{λ}^{k}$ 是上近似协调集.由 $G_{λ} = \overset{p}{\underset{k = 1}{⋁}} (B_{λ}^{k})$ 在 $B_{λ}^{k}$ 中去掉一个元素形成 $B_{λ}^{k^{'}}$ ，必然存在 $(x_{i}, x_{j}) \in D_{f}$ ，使得 $B_{λ}^{k^{'}} ⋂ D_{λ} (x_{i}, x_{j}) = \emptyset$ ，故 $B_{λ}^{k^{'}}$ 不是上近似协调集，所以 $B_{λ}^{k}$ 是上近似约简.而上近似识别函数中包含了所有的 $D_{λ} (x_{i}, x_{j})$ .因此，不可能存在其他的上近似约简了.

例1

利用辨识矩阵求表1中属性加权的模糊序信息系统的上近似约简和下近似约简.

上近似辨识矩阵如表2所示.

表2 表1的上近似辨识矩阵

Table 2 The upper approximation identification matrix of Table 1

	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$
$x_{1}$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$
$x_{2}$	$\emptyset$	$\emptyset$	$a_{3}$	$\emptyset$	$\emptyset$
$x_{3}$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$
$x_{4}$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$
$x_{5}$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$

新窗口打开| 下载CSV

可以计算得到：

G_{λ} = a_{3}

所以上近似约简为 $\{a_{3}\}$ ，该结果与第2节的计算结果一致.

下近似辨识矩阵如表3所示.

表3 表1的下近似辨识矩阵

Table 3 The lower approximation identification matrix of Table 1

	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$
$x_{1}$	$\emptyset$	$a_{3}$	$a_{3}$	$\emptyset$	$\emptyset$
$x_{2}$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$
$x_{3}$	$\emptyset$	$a_{2}$	$\emptyset$	$\emptyset$	$\emptyset$
$x_{4}$	$\emptyset$	$a_{3}$	$a_{3}$	$\emptyset$	$\emptyset$
$x_{5}$	$\emptyset$	$a_{3}$	$a_{3}$	$\emptyset$	$\emptyset$

新窗口打开| 下载CSV

可以计算得到：

G_{σ} = a_{2} \land a_{3}

因此，下近似约简为 $\{a_{2}, a_{3}\}$ ，该结果与第2节的计算结果一致.

与模糊序信息系统的近似约简相比，同样考虑其上近似约简和下近似约简问题，并研究了两种约简的判定定理和辨识矩阵的计算方法.然而，与模糊序信息系统的近似约简不同的是，本文对属性集增加了权重并对其求和，争取将权值大的属性保留，同时尽力删除权值小的属性.

4 算法与实验

本节利用上述的含属性加权的模糊序信息系统的近似约简的辨识矩阵方法，进行算法设计，下面分别写出上、下近似约简的伪代码，并且给出详细的数值实验.

首先给出上近似约简的具体算法.

算法1 含属性加权的模糊序信息系统的上近似约简算法

Input： $I = (U, C ⋃ \{d\}, F, G, W)$

Output：含属性加权的模糊序信息系统的上近似约简集 $R e d$

1.Selected feature subset $R e d \leftarrow \emptyset$ ；

2.Count the number of score function $S (x) = \sum_{i = 1}^{n} ω_{i} μ_{a_{i}} (x), i = 1,2, \dots, n$ ；∥计算出得分函数∥

3.for $i$ =1 to $|U|$ do：

4. $d e c = \emptyset$

5. for $j$ =1 to $|U|$ do：

6. if $S_{x_{i}} \leq S_{x_{j}}$ then do：

7. $d e c \leftarrow x_{j}$

8. end if

9. end for

10. $D e c = D e c ⋃ d e c$

11.end for

12.for $i$ =1 to $|U|$ do：

13.d= $\emptyset$

14. for $j$ =1 to $|U|$ do：

15. if $d_{i} \leq d_{j}$ then do：

16. $d \leftarrow d_{j}$

17. end if

18. end for

19. $D = D ⋃ d$

20.end for

21.for $i$ =1 to $|U|$ do：

22. $\bar{R_{C}^{\leq}} (i) = \emptyset$

23. for $j$ =1 to $|U|$ do：

24. if $D e c [i] ⋂ d [j] \neq \emptyset$ then do：

25. $\bar{R_{C}^{\leq}} (i) \leftarrow x_{i}$

26. end if

27. end for

28. $\bar{R_{C}^{\leq}} = \bar{R_{C}^{\leq}} ⋃ \bar{R_{C}^{\leq}} (i)$

29.end for

30.for $k$ =1 to $|U|$ do：

31. $D_{f} = \emptyset$

32. for $i$ =1 to $|U|$ do：

33. for $j$ =1 to $|U|$ do：

34. if $x_{i} \in \bar{R_{C}^{\leq}} (k) a n d x_{j} \notin \bar{R_{C}^{\leq}} (k)$ then do：

35. $x_{i} = x_{j} = 0$

36. for $m = 1$ to $|C|$ ：

37. $x_{i} = x_{i} + ω_{i_{m}} μ_{i_{m}}, x_{j} = x_{j} + ω_{j_{m}} μ_{j_{m}}$

38. if $x_{i} < x_{j}$ then do：

39. $D_{f} \leftarrow a_{m}$

40. end if

41. end for

42. end if

43. end for

44. end for

45. $M_{λ}$ = $M_{λ} ⋃ D_{f}$

46.end for

47.Red is the Minimal disjunctive normal form of $M_{λ}$

48.end

下面给出算法1的时间复杂度分析：第2步要求出每个对象对应的得分函数，所以时间复杂度为 $O ({|U|}^{2})$ ；第3步至第11步需要求优势类，时间复杂度为 $O ({|U|}^{2})$ ；第12步至第20步为求决策类，时间复杂度为 $O ({|U|}^{2})$ ；第21步至第29步求上近似，时间复杂度为 $O ({|U|}^{2})$ ；第30步至第46步求辨识矩阵，时间复杂度为 $O ({|U|}^{3} |C|)$ ；第47步为根据辨识矩阵求约简结果，时间复杂度为 $O ({|U|}^{2})$ .因此，算法1总的时间复杂度为 $O ({|U|}^{2} + {|U|}^{2} + {|U|}^{2} + {|U|}^{3} |C| + {|U|}^{2})$ .

下面给出下近似约简的具体算法.

算法2 含属性加权的模糊序信息系统的下近似约简算法

Input： $I = (U, C ⋃ \{d\}, F, G, W)$

Output：含属性加权的模糊序信息系统的下近似约简集 $R e d$

1.与上近似约简的1~29步相同

2.for $k$ to $|U|$ then do：

3. $D_{f} = \emptyset$

4. for $i$ to $|U|$ then do：

5. for $j$ to $|U|$ then do：

6. if $x_{i} \in \underset{̲}{R_{C}^{\leq}} (k) a n d x_{j} \notin \underset{̲}{R_{C}^{\leq}} (k)$ then do：

7. $x_{i} = x_{j} = 0$

8. for m=1 to $|C|$ ：

9. $x_{i} = x_{i} + ω_{i_{m}} μ_{i_{m}}, x_{j} = x_{j} + ω_{j_{m}} μ_{j_{m}}$

10. if $x_{i} > x_{j}$ then do：

11. $D_{f} \leftarrow a_{m}$

12. end if

13. end for

14. end if

15. end for

16. end for

17. $M_{σ} = M_{σ} ⋃ D_{f}$

18.end for

19.Red is the Minimal disjunctive normal form of $M_{σ}$

20.end

与上近似约简相同，其时间复杂度为 $O ({|U|}^{2} + {|U|}^{2} + {|U|}^{2} + {|U|}^{3} |C| + {|U|}^{2})$ .

根据系列实验来分别验证上近似约简算法和下近似约简算法的有效性.使用的计算机配置如下：Intel（R） Core（TM） i7⁃9750H CPU @ 2.60 GHz，内存16 GB，操作系统为64位Windows 10，实现程序采用Jupyter平台.实验中使用的数据集信息如表4所示.

表4 实验数据集总览

Table 4 The experimental datasets

No.	数据集	样本数	特征数	分类数
1	Caesarian Section Classification Dataset	79	4	2
2	iris	150	4	3
3	wine	178	13	3
4	Connectionist Bench	208	60	2
5	seed	210	7	3
6	Blood Transfusion Service Center	748	4	2
7	audit_risk	776	26	2
8	banknote authentication	1372	3	2

新窗口打开| 下载CSV

根据算法1求出表4数据集的上近似约简，并分别使用KNN和SVM分类器对约简结果进行分类，求出其分类的精度，如表5所示.

表5 在SVM与KNN下所得上近似约简的分类精度

Table 5 Classification accuracy of upper approximate reduction under SVM and KNN

数据集	SVM	KNN
平均	$84.27 % \pm 2.91 %$	$81.08 % \pm 3.06 %$
Caesarian Section Classification Dataset	$61.90 % \pm 5.83 %$	$68.75 % \pm 4.93 %$
iris	$99.17 % \pm 0.55 %$	$96.67 % \pm 0.72 %$
wine	$95.71 % \pm 0.63 %$	$97.14 % \pm 0.47 %$
Connectionist Bench	$84.85 % \pm 3.26 %$	$76.16 % \pm 2.96 %$
seed	$71.86 % \pm 4.38 %$	$61.90 % \pm 6.47 %$
Blood Transfusion Service Center	$76.76 % \pm 4.72 %$	$75.33 % \pm 4.37 %$
audit_risk	$86.13 % \pm 2.36 %$	$81.41 % \pm 2.74 %$
banknote authentication	$97.81 % \pm 1.51 %$	$91.27 % \pm 1.79 %$

新窗口打开| 下载CSV

根据算法2求出表4数据集的下近似约简，并分别使用KNN和SVM分类器对约简结果进行分类，求出其分类的精度，如表6所示.

表6 在SVM与KNN下所得下近似约简的分类精度

Table 6 Classification accuracy of upper approximate reduction under SVM and KNN

数据集	SVM	KNN
平均	$87.51 % \pm 2.97 %$	$73.01 % \pm 4.45 %$
Caesarian Section Classification Dataset	$74.60 % \pm 5.47 %$	$43.75 % \pm 7.46 %$
iris	$74.17 % \pm 4.68 %$	$63.33 % \pm 4.37 %$
wine	$91.43 % \pm 3.62 %$	$65.71 % \pm 4.73 %$
Connectionist Bench	$88.79 % \pm 4.38 %$	$69.52 % \pm 6.24 %$
seed	$99.04 % \pm 1.49 %$	$85.71 % \pm 2.84 %$
Blood Transfusion Service Center	$78.92 % \pm 5.37 %$	$77.33 % \pm 5.22 %$
audit_risk	$95.81 % \pm 1.74 %$	$87.82 % \pm 2.68 %$
banknote authentication	$97.35 % \pm 1.37 %$	$90.91 % \pm 2.03 %$

新窗口打开| 下载CSV

通过表5和表6的结果可以看出，利用上述算法1、算法2所求得的上近似约简和下近似约简进行分类，不论是采用SVM算法分类还是KNN算法分类，分类精度都可以尽量保持在一个比较高的数值.其中，在上近似约简中，SVM算法和KNN算法所求得的平均精度分别为84.27%和81.08%；在下近似约简中，SVM算法和KNN算法所求得的平均精度则分别为87.51%和73.01%，所有的结果都具有一定的可信度.

5 结论

本文首先介绍了模糊序信息系统，进而对模糊序信息系统进行加权，定义了带有属性加权的模糊序信息系统，并且在该信息系统中引入了近似约简的概念，通过研究得到了近似约简的判定定理和上、下近似约简的可辨识矩阵，建立了在属性加权的模糊序关系下不协调决策信息系统的近似约简方法，同时通过实例证明了该约简方法的有效性.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Taj

S M

， Sudha

， Kumaravel

. Predicting heart failure using data mining with rough set theory and Fuzzy Petri Net. Journal of Physics：Conference Series，2021(1724)：012033.

[本文引用: 1]

[2]

Wang

G Q

， Li

T R

， Zhang

P F

，et al.

Double⁃local rough sets for efficient data mining

Information Sciences，2021(571)：475-498.

[3]

Wang

Y F

Mining stock price using fuzzy rough set system

Expert Systems with Applications，2003，24(1)：13-23.

[4]

W T

， Pang

， Jia

X Y

，et al.

Fuzzy rough sets and fuzzy rough neural networks for feature selection：A review

WIREs Data Mining and Knowledge Discovery，2021，11(3)：e1402.

[本文引用: 1]

[5]

高建来，运士伟，张永胜. 融合粗糙集与球形支持向量机的多分类识别. 河南科技大学学报：自然科学版，2011，32(5)：77-80.

[本文引用: 1]

Gao

J L

， Yun

S W

， Zhang

Y S

. Multi⁃classification pattern recognition based on fusion of rough set and sphere⁃structured support vector machines. Journal of Henan University of Science and Technology：Natural Science，2011，32(5)：77-80.

[本文引用: 1]

[6]

王江荣，黄建华，罗资琴，等.

基于粗糙集的Logistic回归模型在矿井突水模式识别中的应用

煤田地质与勘探，2015，43(6)：70-74.

[本文引用: 1]

Wang

J R

， Huang

J H

， Luo

Z Q

，et al.

Application of logistic regression model based on rough set in recognition of mine water inrush pattern

Coal Geology & Exploration，2015，43(6)：70-74.

[本文引用: 1]

[7]

Csajbók

Partial approximative set theory：A generalization of the rough set theory

∥2010 International Conference of Soft Computing and Pattern Recognition. Cergy⁃Pontoise，France：IEEE，2010：51-56.

[本文引用: 1]

[8]

Zhou

， Wang

， Shi

C Q

，et al. Study of fault diagnosis distribution network based on rough set and artificial intelligence. Journal of Physics：Conference Series，2021(1754)：012204.

[9]

Trabelsi

， Elouedi

， Lingras

Belief rough set classifier

∥Proceedings of the 22nd Canadian Conference on Artificial Intelligence：Advances in Artificial Intelligence. Springer Berlin Heidelberg，2009：257-261.

[10]

徐伟华

. 序信息系统与粗糙集. 北京：科学出版社，2013.

[本文引用: 4]

[11]

袁修久，张文修.

模糊目标信息系统的属性约简

系统工程理论与实践，2004，24(5)：116-120，125.

[本文引用: 1]

Yuan

X J

， Zhang

W X

Attribute reductions in fuzzy inconsistent information systems

Systems Engineering⁃Theory & Practice，2004，24(5)：116-120，125.

[本文引用: 1]

[12]

Jensen

， Shen

Fuzzy–rough attribute reduction with application to web categorization

Fuzzy Sets and Systems，2004，141(3)：469-485.

[13]

Jensen

， Shen

Fuzzy⁃rough data reduction with ant colony optimization

Fuzzy Sets and Systems，2005，149(1)：5-20.

[14]

Pawlak

. Rough Sets：Theoretical aspects of reasoning about data. Norwell：Kluwer Academic Publishers，1992.

[15]

Pawlak

， Grzymala⁃Busse

， Slowinski

，et al.

Rough sets

Communications of the ACM，1995，38(11)：88-95.

[16]

张文修，米据生，吴伟志.

不协调目标信息系统的知识约简

计算机学报，2003，26 (1)：12-18.

Zhang

W X

， Mi

J S

， Wu

W Z

Knowledge reductions in inconsistent information systems

Chinese Journal of Computers，2003，26(1)：12-18.

[17]

王珏，苗夺谦，周育健.

关于Rough Set理论与应用的综述

模式识别与人工智能，1996，9(4)：337-344.

[本文引用: 1]

Wang

， Miao

D Q

， Zhou

Y J

Rough set theory and its application：A Survey

PR & AI，1996，9(4)：337-344.

[本文引用: 1]

... 粗糙集理论是1982年由波兰科学院院士、华沙理工大学教授Pawlak提出的，用于处理不确定、不精确和模糊知识的软计算，其主要是利用已知的信息来近似描述不确定的、模糊的信息.在分类问题中，粗糙集理论利用特征来归纳二元关系，从而将样本区分开.研究知识约简正是利用不同二元关系下形成的类以对特征进行提取.目前，在数据挖掘^［1-4］、模式识别^［5-6］、人工智能以及智能信息处理^［7-10］等领域有广泛的应用. ...

Double?local rough sets for efficient data mining

2021

Mining stock price using fuzzy rough set system

2003

Fuzzy rough sets and fuzzy rough neural networks for feature selection：A review

2021

2011

基于粗糙集的Logistic回归模型在矿井突水模式识别中的应用

2015

基于粗糙集的Logistic回归模型在矿井突水模式识别中的应用

2015

Partial approximative set theory：A generalization of the rough set theory

2010

Belief rough set classifier

2009

2013

... 粗糙集理论经过多年的发展，已经形成了比较完善的理论体系.属性约简是粗糙集理论体系中非常重要的一个部分，要求在决策能力和知识库分类不变的情况下，尽可能地删除其中不相关或者不重要的属性，从而消除冗余的属性，在降低空间复杂度和时间复杂度的情况下没有丢失重要的信息^［10］.目前，已经有很多学者对属性约简进行了深入研究^［11-17］. ...

... 定义1^［10］ ...

... 定义2^［10］ ...

模糊目标信息系统的属性约简

2004

模糊目标信息系统的属性约简

2004

Fuzzy–rough attribute reduction with application to web categorization

2004

Fuzzy?rough data reduction with ant colony optimization

2005

1992

Rough sets

1995

不协调目标信息系统的知识约简

2003

不协调目标信息系统的知识约简

2003

关于Rough Set理论与应用的综述

1996

关于Rough Set理论与应用的综述

1996

〈

〉