«上一篇
文章快速检索     高级检索
下一篇»
  智能系统学报  2020, Vol. 15 Issue (1): 166-174  DOI: 10.11992/tis.201904037
0

引用本文  

杨洁, 王国胤, 张清华. 基于知识距离的粗糙粒结构的评价模型[J]. 智能系统学报, 2020, 15(1): 166-174. DOI: 10.11992/tis.201904037.
YANG Jie, WANG Guoyin, ZHANG Qinghua. Evaluation model of rough granular structure based on knowledge distance[J]. CAAI Transactions on Intelligent Systems, 2020, 15(1): 166-174. DOI: 10.11992/tis.201904037.

基金项目

国家自然科学基金项目(61572091)

通信作者

杨洁. E-mail:530966074@qq.com

作者简介

杨洁,副教授,博士,主要研究方向为粒计算、数据挖掘、粗糙集。参与国家自然科学基金项目2项,授权国家发明专利5项。发表学术论文20余篇;
王国胤,教授,博士生导师,博士,重庆邮电大学研究生院院长、人工智能学院院长,主要研究方向为粗糙集、粒计算、认知计算、数据挖掘、智能信息处理。主持国家自然科学基金项目 10 余项。入选“重庆高校创新团队”、“重庆市首席专家工作室”和“国家级教学团队”;获国家级教学成果二等奖、重庆市自然科学一等奖、重庆市科技进步一等奖、重庆市教学成果一等奖和吴文俊人工智能科学技术奖科技进步一等奖等多项国家级/省部级教学和科技成果奖励。出版著作10余部,发表学术论文300余篇;
张清华,教授,博士生导师,博士,主要研究方向为粗糙集、模糊集、粒计算、三支决策。主持国家自然科学基金项目2项。发表学术论文40余篇

文章历史

收稿日期:2019-04-16
基于知识距离的粗糙粒结构的评价模型
杨洁 1,2, 王国胤 1,2,3, 张清华 1,2,3     
1. 重庆邮电大学 计算智能重庆市重点实验室,重庆 400065;
2. 重庆邮电大学 计算机科学与技术学院,重庆 400065;
3. 重庆邮电大学 人工智能学院,重庆 400065
摘要:在粒计算理论中,通过不同的粒计算机制可以生成不同的粒结构。在粗糙集中,对于同一个信息表而言,通过不同的属性添加顺序可以得到由不同的序贯层次结构,即粗糙粒结构。在粗糙粒结构中,不同的属性获取顺序导致了对不确定性问题求解的不同程度。因此,如何有效评价粗糙粒结构是一个值得研究的问题。本文将从知识距离的角度研究这个问题。首先,在前期工作所提出的知识距离框架上提出了一种粗糙近似空间距离,用于度量粗糙近似空间之间差异性。基于提出的知识距离,研究了粗糙粒结构的结构特征。在粗糙粒结构中,在对不确定性问题进行求解时,本文希望在约束条件下可以利用尽可能少的知识空间使不确定性降低达到最大化。基于这个思想并利用以上得出的结论,在属性代价约束条件下,引入了一个评价参数λ,并在此基础建立了一种粗糙粒结构的评价模型,该方法实现了在属性代价约束条件下选择粗糙粒结构的功能。最后,通过实例验证了本文提出的模型的有效性。
关键词粗糙粒结构    知识距离    不确定性度量    评价模型    粒计算    粗糙集    约束条件    不确定性度量    
Evaluation model of rough granular structure based on knowledge distance
YANG Jie 1,2, WANG Guoyin 1,2,3, ZHANG Qinghua 1,2,3     
1. Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Posts and Telecommunications, Chongqing 400065, China;
2. School of computer science and technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China;
3. College of Artificial Intelligence, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
Abstract: In the theory of granular computing (GrC), different granular structures are generated by various grain calculation mechanisms. In rough sets, for the same information table, different attribute adding sequence produces different sequential hierarchical structure, namely the rough granular structure. In rough granular structure, various order of attribute acquisition leads to different effects of solving uncertain problems. This leads to an interesting research topic: how to effectively evaluate the rough granular structures. This problem is solved from the perspective of knowledge distance in the paper. Firstly, the knowledge distance mentioned in our previous works is introduced and then a rough approximation space distance (RASD) is proposed to measure the difference between rough approximate space. On the basis of the knowledge distance mentioned above, the characteristic of rough granular structure (RGS) is investigated. In the rough granular structure, when solving uncertain problem, we expect to to maximize the uncertainty reduction as much as possible by using smaller knowledge space. Then, based on this idea and the above conclusions, an evaluation parameter λ is introduced under the constraint of attribute cost, and further, an evaluation model of rough granular structure is established. This achieves a way to select the rough granular structure according to the constraint. Finally, the effectiveness of this method is verified by an example.
Key words: rough granular structure    knowledge distance    uncertainty measure    evaluation model    granular computing    rough sets    constraint condition    uncertainty measure    

早在1997年,Zadeh教授[1]就提出了粒计算是模糊信息粒化、粗糙集理论和区间计算的超集,是粒数学的子集。粒计算[2-5]是一种新的模拟人类思维机制的方法论,在粒计算的“大伞”之下,包含了很多具体的模型,如:模糊集[6]、粗糙集[7]、商空间[8]、云模型[9]等。粒计算是研究基于多层次粒结构的思维方式、问题求解方法、信息处理模式的理论[10]

基于粒计算理论,Yao[12]提出了序贯三支决策理论(sequential three-way decisions,S3WD)。从多粒度的角度来说[13-14],随着信息系统中属性或信息的增加,S3WD中等价类将逐渐变小。S3WD是一种利用粗糙近似空间的渐近式问题求解模型,本质上是粗糙粒结构,即通过由粗到细的切换粒度,实现问题的逐步求解。为了实现渐近式的最优尺度的选择和属性约简,文献[15]提出了一种局部规则提取方法,本质上运用了序贯三支决策的思想。在现实的决策分析中,S3WD为求解复杂问题提供了一种模拟人类的多粒度思维。从层次商空间结构(hierarchical quotient space structure,HQSS)[16-18]的角度来说,等价类将会随着粒度的细化逐渐细分成更细的等价类,这意味着在S3WD模型中,随着属性或信息的增加,一个目标概念可以通过不同粒度的知识进行描述。再者,由于较细粒度的知识空间上包含了更多的信息,所以在较细粒度的知识空间上可以更准确地刻画目标概念。但是,构建较细粒度的知识空间需要更多的代价以及在较细粒度上进行问题求解需要更多的时间消耗。

通过以上分析,在S3WD模型中,本文希望在约束条件下可以利用尽可能少的知识空间最大化降低问题的不确定性,从而对问题进行求解,并且针对不同的约束条件评价并选择不同的粗糙粒结构进行问题求解也是需要解决的问题。

基于这个思想,本文从知识距离的角度研究粗糙粒结构的评价模型(为了简单起见,本文仅考虑属性代价为约束条件下粗糙粒结构进行评价选择)。首先,基于前期工作中提出的知识距离框架进一步提出了一种粗糙近似空间距离并讨论了其相关性质。其次,基于提出的粗糙近似空间距离研究了层次粒结构对目标概念的刻画能力,并得到同一个粗糙粒结构中的两个知识空间的不确定性差异等于它们之间的知识距离的结论,并通过实例表验证了本文的评价模型的有效性。此外,本文的评价模型具有可扩展性,针对不同的粒结构设计合适的知识距离,可用于评价不同类型的粒结构,例如层次聚类、多尺度图像分割以及多粒度社区发现等问题。

1 基本概念

一个信息系统是一个四元组,可表示为 $S = (U,C \cup D,V,f)$ ,其中 $U$ 为一个非空论域, $C$ 为条件属性集合, $D$ 为决策属性集, $V$ 为对每个对象对应的属性值集合, $f:U \times C$ 是一个信息函数。

定义1 粗糙集[7]。设一个信息系统 $S = (U,C \cup D,V,f)$ ,其中 $R \subseteq C$ $X \subseteq U$ ,那么 $X$ 的上、下近似集定义如下:

$ \begin{array}{*{20}{c}} {\underline R (X) = \{ \left. {x \in U} \right|{[x]_R} \subseteq X\} }\\ {\overline R (X) = \{ \left. {x \in U} \right|{[x]_R} \cap X \ne \text{Ø} \} } \end{array} $

其中 ${[x]_R}$ 代表由等价关系 ${U / R}$ 诱导的等价类, 即 ${U / R} = \{ {[x]_1},{[x]_2}, \cdots ,{[x]_m}\} $

本章中,仅从划分的角度,一个知识空间 ${U / R}$ 通常叫做一个商空间,当利用 ${U / R}$ 对目标概念 $X$ 进行粗糙近似描述时,通常将 ${U / R}$ 表示为 ${U / R}(X)$ ,称为粗糙近似空间。简单而言, 为了防止混淆本文假设 ${[x]_R} \displaystyle\triangleq [x]$ 。如果 $\overline R (X) = \underline R (X)$ ,则 $X$ 是一个可定义集, 否则 $X$ 是一个粗糙集。在粗糙集中,论域 $U$ 通常被划分为正域、负域和边界域,分别定义如下:

$ \begin{array}{*{20}{c}} {\text{POS}{_R}(X) = \underline R (X)}\\ {\text{BND}{_R}(X) = \overline R (X) - \underline R (X)}\\ {\text{NEG}{_R}(X) = U - \overline R (X)} \end{array} $

定义2 粒度度量[19-21]。假设 $U$ 为一个有限非空论域,一个函数 ${2^U} \to \Re $ 对于任意 $P,Q \in {2^U}$ ,如果满足以下条件:

1) $m(x) \geqslant 0$

2) $P \subset Q \Rightarrow m(P) < m(Q)$

3) $P{ \equiv _s}Q \Rightarrow m(P) = m(Q)$

则它是一个粒度度量。

定义3 距离度量[22]。假设 $U$ 为一个非空有限论域,ABC是3个有限集合, $\forall A$ $B$ $C \subseteq U $ 。如果满足以下3个条件:

1)正定性: $V(A,B) \geqslant 0$

2)对称性: $V(A,B) = V(B,A)$

3)三角不等式: $V\left( {A,B} \right) + V\left( {B,C} \right) \geqslant V\left( {A,C} \right)$

则函数 $V( \cdot , \cdot )$ 是一个真正的距离度量。

定义4[23]  假设 $P = \{ ({p_1},{w_{{p_1}}}),({p_2},{w_{{p_2}}}), \ldots ,$ $ ({p_l},{w_{{p_l}}})\} $ $Q = \{ ({q_1},{w_{{q_1}}}),({q_2},{w_{{q_2}}}), \ldots ,({q_m},{w_{{q_m}}})\} $ 分别是两个具有lm个类簇的分布。 ${p_i}$ ${q_j}$ 代表 $P$ $Q$ 类簇, ${w_{{p_i}}}$ ${w_{{q_j}}}$ 分别 ${p_i}$ ${q_j}$ 的权重。 ${c_{ij}}$ 代表 ${p_i}$ ${q_j}$ 之间的差异性度量,例如,欧式距离。EMD的目标是寻找一个流量矩阵 ${F} = [{f_{ij}}]$ 最小化总代价,其中 ${f_{ij}}$ 代表 ${p_i}$ ${q_j}$ 的流量。

$\text{work}(P,Q) = \displaystyle\sum\limits_{i = 1}^l {\displaystyle\sum\limits_{j = 1}^m {{c_{ij}}{f_{ij}}} } $
$\begin{array}{*{20}{l}} {\text{s.t.}}\\ {\;\;\;\;\;\;\;\;\;\;\;\;{f_{ij}} \geqslant 0;1 \leqslant i \leqslant n,1 \leqslant j \leqslant m} \end{array}$ (1)
$\displaystyle\sum\limits_{j = 1}^m {{f_{ij}}} \leqslant {w_i};1 \leqslant i \leqslant n$ (3)
$\displaystyle\sum\limits_{i = 1}^l {{f_{ij}}} \leqslant {w_j};1 \leqslant j \leqslant m$ (4)
$\displaystyle\sum\limits_{i = 1}^l {\displaystyle\sum\limits_{j = 1}^m {{f_{ij}}} } = \min \Bigg\{ \displaystyle\sum\limits_{i = 1}^l {{w_i}} ,\displaystyle\sum\limits_{j = 1}^m {{w_j}} \Bigg\} $ (5)

式(1)限制流量传递过程为PQ, 不能反向;式(2)限制从Pi运出去的总流量不能超过自身的总流量;式(3)限制Qj接收的总流量不能超过自身的总流量;式(4)限制总传递流量的上限是PQ的流量的最小值。当这个运输问题解决时,这个最优的流量分配即可求得,即EMD被定义为由总流量归一化的结果:

$\text{EMD}(P,Q) = \frac{{\displaystyle\sum\limits_{i = 1}^l {\displaystyle\sum\limits_{j = 1}^m {{c_{ij}}{f_{ij}}} } }}{{\displaystyle\sum\limits_{i = 1}^l {\displaystyle\sum\limits_{j = 1}^m {{f_{ij}}} } }}$ (6)

一般来说,式(5)中的 $c( \cdot , \cdot )$ 可以是任意差异性度量,可根据具体问题来选取。

定理1[23-24]  如果 $c( \cdot , \cdot )$ 是一个真正的度量,且两个分布的总权重相同,即 $\displaystyle\sum\limits_{i = 1}^n {{w_i}} = \displaystyle\sum\limits_{j = 1}^m {{w_j}} $ ,那么EMD为一个真正的距离度量。

在粒计算中,信息粒化旨在建立基于外部世界的有效的并以用户为中心的概念,同时简化物理世界和虚拟世界的认识,可以高效地提供“实用”的非精确解。信息粒化首先需要研究信息粒、粒层和整个粒结构的表示,然后针对表示方法进行构建[11]。同一粒化准则对应一个知识空间,不同粒化准则对应多个知识空间,不同知识空间 (相邻两知识空间或跨知识空间) 中信息粒之间的相互关系构成一个结构,由此得到的多个知识空间及知识空间之间的关系称为粒的拓扑空间,简称为粒结构,如图1所示,为一个粒结构的整体示意图。

Download:
图 1 粒结构示意图 Fig. 1 Schematic diagram of granular structure

在S3WD模型中,随着粒度的细分,一方面,如果知识空间之间的不确定性差异太小,意味着新增加的属性对于不确定性的降低几乎没有贡献,因此原先在边界域的样本有可能仍然在边界域,无法对它们进行决策;另一方面,如果知识空间之间的不确定性差异太大,意味着获取新增加的属性需要很大的代价,因此有可能无法满足用户的时限约束条件。如图2所示,图2(a)图2(b)分别表示了上面分析的两种情况,图2(c)表示两个知识空间之间不确定性差异适中的情况。

Download:
图 2 3种不同程度的知识空间细分情况 Fig. 2 Three different levels of knowledge spaces subdivision
2 知识距离

从粒计算的角度来说,无论是信息熵还是知识粒度都无法刻画粒结构中知识空间之间的差异性。在粗糙集模型中,不确定性度量用于度量粗糙近似空间刻画目标概念的不确定性程度。虽然当前存在许多不确定性度量方法[25-29],但是这些方法仍然不够准确,即具有相同不确定性的两个知识空间不一定等价,它们的差异性如何刻画?为了解决这个问题,钱宇华[30-32]首次提出了基于邻域信息粒的知识距离,并建立了同一知识基中完备粒空间与不完备粒空间之间的关系。杨习贝[33-34]将知识距离应用到多粒度空间,通过知识距离代数格导出一个偏序关系,可用于描述多粒度空间中的层次结构。但是,当前的知识距离模型缺乏清晰的物理解释和理论背景,并且不具有扩展性。在前期工作中[35-36],本文基于EMD提出了一种知识距离框架(knowledge distance framework, KDF)并给出了知识距离的物理意义,在此基础上进一步构建了一种商空间知识距离(quotient space distance,QSD)。

定义5 知识距离框架[35]。假设 $K = (U,\Re )$ 是一个知识基, ${K_P} = \left\{ {{p_1},{p_2}, \cdots ,{p_l}} \right\}$ ${K_Q} = $ $ \left\{ {{q_1},{q_2}, \cdots ,{q_m}} \right\}$ 是两个分别由等价关系 $P$ $Q$ 产生的知识空间, ${d_{ij}} = d({p_i},{q_j})$ 代表信息粒 ${p_i}$ ${q_j}$ 之间的距离,fij代表 ${p_i}$ ${q_j}$ 之间的流量,其中 ${f_{ij}} = \left| {{p_i} \cap {q_j}} \right|$ ${K_P}$ ${K_Q}$ 之间的知识距离框架有如下定义:

$\text{KDF}({K_P},{K_Q}) = \frac{1}{{\left| U \right|}}\displaystyle\sum\limits_{i = 1}^l {\displaystyle\sum\limits_{j = 1}^m {{d_{ij}}{f_{ij}}} } $ (7)

由于对同一论域进行划分的不同知识空间的对象数是相同的,故 $\displaystyle\sum\limits_{i = 1}^l {\left| {{p_i}} \right|} = \displaystyle\sum\limits_{j = 1}^m {\left| {{q_j}} \right|} = \left| U \right|$ ,式(6)符合约束条件式(4)。同样,式(7)符合约束条件式(1)~(3)。KDF表示的是同一个知识基的任意两个知识空间之间匹配对象的最小成本。显然,通过采用不同的信息粒距离,可以产生一组基于划分的知识距离。基于EMD的优点,KDF可以实现一个多对多的匹配,更符合人类的认知,可以更准确地刻画两个知识空间的差异性。因此,KDF是一个有效直观的描述知识空间之间差异性的数学工具,可扩展到度量任何形式的知识空间之间的差异性(或相似性)。

定义6 商空间知识距离[35]。设一个信息系统 $S = (U,C \cup D,V,f)$ ${R_1},{R_2} \subseteq C$ ${U / {{R_1}}} =$ $ \left\{ {{p_1},{p_2}, \cdots, {p_l}} \right\}$ ${U / {{R_2}}} = \left\{ {{q_1},{q_2}, \cdots, {q_m}} \right\}$ $U$ 上的两个知识空间, ${d_{ij}} = d({p_i},{q_j})$ 代表信息粒 ${p_i}$ ${q_j}$ 之间的距离,fij代表 ${p_i}$ ${q_j}$ 之间的流量,其中 ${f_{ij}} =$ $ \left| {{p_i} \cap {q_j}} \right|\;\;$ ${U / {{R_1}}} = $ $\left\{ {{p_1},{p_2}, \cdots, {p_l}} \right\}\;\;$ $U/{R_2} = \left\{ {{q_1},{q_2}, \cdots ,} \right.$ $\left. {{q_m}} \right\}$ 之间的知识距离框架有如下定义:

$\text{QSD}({U / {{R_1}}},{U / {{R_2}}}) = \frac{1}{{\left| U \right|}}\displaystyle\sum\limits_{i = 1}^l {\displaystyle\sum\limits_{j = 1}^m {\frac{{\left| {{p_i} \oplus {q_j}} \right|}}{{\left| U \right|}}} } \left| {{p_i} \cap {q_j}} \right|$

式中 $\left| {{p_i} \oplus {q_j}} \right| = \left| {{p_i} \cup {q_j}} \right| - \left| {{p_i} \cap {q_j}} \right|$

例1 设一个信息系统 $S = \left( {U,C \cup D,V,f} \right),U =\left\{ {{x_1},} \right.$ $\left. {{x_2}, \cdots ,{x_9}} \right\}$ ${R_1},{R_2} \subseteq C$ $X = \dfrac{0}{{{x_1}}} + \dfrac{0}{{{x_2}}} + \dfrac{0}{{{x_3}}} + $ $ \dfrac{1}{{{x_4}}} +\dfrac{1}{{{x_5}}} + \dfrac{1}{{{x_6}}} + $ $\dfrac{1}{{{x_7}}} + \dfrac{0}{{{x_8}}} + \dfrac{1}{{{x_9}}} $ $U$ 上的一个目标概念,即 $X =\{ {x_4},{x_5},$ ${x_6},{x_7},{x_9}\} $ $U/{R_1} = \left\{ {\left\{ {{x_1},{x_2}, \cdots ,{x_6}} \right\},\left\{ {{x_7},{x_8},{x_9}} \right\}} \right\}$ $U/{R_2} = $ $\{ \left\{ {{x_1},{x_2},{x_3},{x_4}} \right\}, $ $\left\{ {{x_5},{x_6},{x_7}} \right\},\left\{ {{x_8},{x_9}} \right\} \}$ $U$ 上的两个知识空间。

$\begin{array}{l} \text{QSD}({U / {{R_1}}},{U / {{R_2}}}) = \dfrac{1}{{\left| U \right|}}\displaystyle\sum\limits_{i = 1}^2 {\displaystyle\sum\limits_{j = 1}^3 {\dfrac{{\left| {{p_i} \oplus {q_j}} \right|}}{{\left| U \right|}}} } \left| {{p_i} \cap {q_j}} \right| =\\ \;\;\;\;\;\;\;\; \dfrac{{\dfrac{2}{9} \times 4 + \dfrac{5}{9} \times 2 + \dfrac{4}{9} \times 1 + \dfrac{1}{9} \times 2}}{9} = 0.296 \\ \end{array} $

通过多对多匹配计算, $\text{QSD}$ 实现了两个知识空间之间的差异性度量。但是,对于粗糙集来说,当前知识距离的工作(包括 $\text{QSD}$ )仅仅是从知识空间的角度出发,反映的是两个知识空间划分差异性,并没有考虑它们对目标概念刻画时的差异性,有可能导致同一目标概念在两个不同粒度的知识空间中具有相同的不确定性度量结果,从而无法区分它们对目标概念的近似能力。为了解决以上问题,本文提出了一种粗糙近似空间知识距离(rough approximation space distance, RASD)。如图3所示,为 $\text{QSD}$ $\text{RASD}$ 两种类型的知识距离的示意图,与 $\text{QSD}$ 相比, $\text{RASD}$ 可以体现两个知识空间对目标概念刻画能力的差异性。

Download:
图 3 两种类型的知识距离 Fig. 3 Two types of knowledge distance
2.1 粗糙近似空间距离

为了反映不同知识空间对目标概念的刻画能力的差异性,本文基于知识距离框架进一步提出了一种粗糙近似空间距离。

定义7 模糊集合距离。假设 $U$ 为一个非空有限论域, $X$ $U$ 上的一个目标概念。如果 $\widetilde A$ $\widetilde B$ $U$ 上的两个有限集合, $A$ $B$ 之间的距离为

$\delta (\widetilde A,\widetilde B) = \frac{{\displaystyle\sum\limits_{x \in \widetilde A \cup \widetilde B} {\mu (x)} - \displaystyle\sum\limits_{x \in \widetilde A \cap \widetilde B} {\mu (x)} }}{{\left| U \right|}}$

由定义7可知,无论 $X$ $U$ 上的一个清晰集还是模糊集, $\delta (\widetilde A,\widetilde B)$ 都可以刻画两个集合(清晰集或模糊集)之间的距离。

定理2 假设 $U$ 为一个非空有限论域, $\delta \left( { \cdot , \cdot } \right)$ $U$ 上的一个距离度量。

证明 假设 $\widetilde A$ $\widetilde B$ $\widetilde C$ $U$ 上的3个有限集合。显然, $\delta \left( { \cdot , \cdot } \right)$ 满足正定性和对称性。通过文献[36]可知:

$\begin{array}{l} (\displaystyle\sum\limits_{x \in \widetilde A \cup \widetilde B} {\mu (x)} - \displaystyle\sum\limits_{x \in \widetilde A \cap \widetilde B} {\mu (x)} ) + (\displaystyle\sum\limits_{x \in \widetilde B \cup \widetilde C} {\mu (x)} - \displaystyle\sum\limits_{x \in \widetilde B \cap \widetilde C} {\mu (x)} ) \geqslant \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(\displaystyle\sum\limits_{x \in \widetilde A \cup \widetilde C} {\mu (x)} - \displaystyle\sum\limits_{x \in \widetilde A \cap \widetilde C} {\mu (x)} ) \\ \end{array} $

显然

$\begin{array}{*{20}{l}} {\dfrac{{\displaystyle\sum\limits_{x \in \widetilde A \cup \widetilde B} {\mu \left( x \right)} - \displaystyle\sum\limits_{x \in \widetilde A \cap \widetilde B} {\mu \left( x \right)} }}{{\left| U \right|}} + \dfrac{{\displaystyle\sum\limits_{x \in \widetilde B \cup \widetilde C} {\mu \left( x \right)} - \displaystyle\sum\limits_{x \in \widetilde B \cap \widetilde C} {\mu \left( x \right)} }}{{\left| U \right|}}} \geqslant\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{ \dfrac{{\displaystyle\sum\limits_{x \in \widetilde A \cup \widetilde C} {\mu \left( x \right)} - \displaystyle\sum\limits_{x \in \widetilde A \cap \widetilde C} {\mu \left( x \right)} }}{{\left| U \right|}}} \end{array} $

$\delta (\widetilde A,\widetilde B) + \delta (\widetilde B,\widetilde C) \geqslant \delta (\widetilde A,\widetilde C)$

因此, $\delta \left( { \cdot , \cdot } \right)$ $U$ 上的一个距离度量。

例2 假设 $U = \left\{ {{x_1},{x_2},{x_3},{x_4},{x_5},{x_6},{x_7}} \right\},X = \dfrac{{0.3}}{{{x_1}}} +$ $ \dfrac{{0.5}}{{{x_2}}} + \dfrac{{0.7}}{{{x_3}}} + \dfrac{{0.9}}{{{x_4}}} + \dfrac{{0.8}}{{{x_5}}} + \dfrac{{0.5}}{{{x_6}}} + \dfrac{{0.2}}{{{x_7}}}$ $U$ 上的一个目标概念, $A = \left\{ {{x_1},{x_2},{x_3},{x_4}} \right\}$ $B = \left\{ {{x_4},{x_5},{x_6},{x_7}} \right\}$ ,则 $\widetilde A = \dfrac{{0.3}}{{{x_1}}} +$ $ \dfrac{{0.5}}{{{x_2}}} + \dfrac{{0.7}}{{{x_3}}} + \dfrac{{0.9}}{{{x_4}}}$ $\widetilde B = \dfrac{{0.9}}{{{x_4}}} + \dfrac{{0.8}}{{{x_5}}} + \dfrac{{0.5}}{{{x_6}}} + \dfrac{{0.2}}{{{x_7}}}$ $\displaystyle\sum\limits_{x \in X} {\mu (x)} = 3.9$ $\displaystyle\sum\limits_{x \in \widetilde A \cap \widetilde B} {\mu (x)}\!=\!0.7 + 0.9\!=\!1.6 \qquad \;$ $\displaystyle\sum\limits_{x \in \widetilde A \cup \widetilde B} {\mu (x)} = 0.3 +$ $ 0.5 + 0.7 + 0.9 + $ $0.8 + 0.5 = 3.7\;\;\;$ ,因此, $\delta (\widetilde A,\widetilde B) = $ $\dfrac{{3.7 - 1.6}}{7} = 0.3\;\;\;$

定义8 设一个信息系统 $S = (U,C \cup D,V,f)$ ${R_1},{R_2} \subseteq C$ $X$ $U$ 上的一个目标概念。 ${U / {{R_1}}} =$ $ \left\{ {{p_1},{p_2}, \cdots ,{p_l}} \right\}$ ${U / {{R_2}}} = \left\{ {{q_1},{q_2}, \cdots ,{q_m}} \right\}$ $U$ 上的两个知识空间。对于描述 $X$ ${U / {{R_1}}}$ ${U / {{R_2}}}$ 的知识距离定义为

$\text{RASD}\left( {{U / {{R_1}}}(X),{U / {{R_2}(X)}}} \right) = \frac{{\displaystyle\sum\limits_{i = 1}^l {\displaystyle\sum\limits_{j = 1}^m {{\delta _{ij}}{f_{ij}}} } }}{{\left| U \right|}}$ (10)

式中: ${\delta _{ij}} = \delta (\widetilde {{p_i}},\widetilde {{q_j}})$ $\widetilde {{p_i}}$ $\widetilde {{q_j}}$ 分别代表 ${p_i}$ ${q_j}$ 对应的模糊集; ${f_{ij}} = \left| {{p_i} \cap {q_j}} \right|$

由于对同一论域进行划分的不同知识空间的对象数是相同的,即 $\displaystyle\sum\limits_{i = 1}^l {\left| {{p_i}} \right|} = \displaystyle\sum\limits_{j = 1}^m {\left| {{q_j}} \right|} = \left| U \right|$ ,式(7)符合约束条件式(4)。同样,式(7)符合约束条件式(1)~(3)。

定理3 假设 $U$ 为一个非空有限论域, $\text{RASD}$ $U$ 上的一个距离度量。

证明 假设 ${U / {{R_1}}} = \left\{ {{p_1},{p_2}, \cdots ,{p_l}} \right\}$ ${U / {{R_2}}} = $ $\left\{ {{q_1},{q_2}, \cdots ,{q_m}} \right\}$ 是两个 $U$ 上的知识空间。对于同一个论域而言,式(7)中 $\displaystyle\sum\limits_{i = 1}^l {\left| {{p_i}} \right|} = \displaystyle\sum\limits_{j = 1}^m {\left| {{q_j}} \right|} = \left| U \right|$ 。由定理2可知, $\delta \left( { \cdot , \cdot } \right)$ $U$ 上的距离度量。通过定理1可知,类似于EMD,RASD也是 $U$ 上的距离度量。

由定义7和定义8可知,无论 $X$ $U$ 上的一个清晰集还是模糊集,RASD都可以刻画两个知识空间之间的对 $X$ 近似刻画能力的差异,即RASD不仅适用于经典粗糙集,同样适用于粗糙模糊集。由于继承了EMD的优点,RASD能够有效和直观的刻画不同知识空间对目标概念的描述能力的差异性。

例3(续例1) 

$ \begin{array}{*{20}{l}} \;\;\;\;\;{\rm{RASD}}\left( {{U / {{R_1}(X)}},{U / {{R_2}(X)}}} \right) = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\dfrac{{\displaystyle\sum\limits_{i = 1}^2 {\displaystyle\sum\limits_{j = 1}^3 {{\delta _{ij}}{f_{ij}}} } }}{{\left| U \right|}}\;\;}=\\ { \dfrac{{\dfrac{2}{9} \times 4 + \dfrac{2}{9} \times 2 + \dfrac{3}{9} \times 1 + \dfrac{1}{9} \times 2}}{9}}= {0.209} \end{array} $
2.2 粗糙粒结构的结构特征

定理4 设一个信息系统 $S = \left( {U,C \cup D,V,f} \right)$ ${R_1}$ ${R_2}$ ${R_3} \subseteq C$ $X$ $U$ 上的一个目标概念。如果 ${R_1} \subseteq $ ${R_2} \subseteq {R_3}$ ,则 ${\rm RASD}\left( {U/{R_1}(X),U/{R_3}(X)} \right) = {\rm{RASD}}$ $\left( {U/{R_1}(X),} \right.$ $\left. {U/{R_2}(X)} \right) + {\rm{RASD}}\left( {U/{R_2}(X),U/{R_3}(X)} \right)。$

证明 假设 $U = \left\{ {{x_1},{x_2}, \cdots ,{x_n}} \right\}$ 是一个非空论域, ${U / {{R_1}}} = \left\{ {{p_1},{p_2}, \cdots ,{p_l}} \right\}$ ${U / {{R_2}}} = \left\{ {{q_1},{q_2}, \cdots ,{q_m}} \right\}$ ${U / {{R_3}}} = $ $\left\{ {{r_1},{r_2}, \cdots ,{r_s}} \right\}$ $U$ 上的3个知识空间。由于 ${R_1} \subseteq $ ${R_2} \subseteq {R_3}$ ,故 ${U / {{R_1}}}\underline \prec {U / {{R_2}}}\underline \prec {U / {{R_3}}}$ 。为了简单化,本文假设仅有一个信息粒 ${p_1}$ $\left( {{p_1} \in {U / {{R_1}}}} \right)$ 细分为两个更细的信息粒 ${q_1}$ ${q_2} $ $\left( {{q_1},{q_2} \in {U / {{R_2}}}} \right)$ ,仅有一个信息粒 ${q_1}$ 细分为两个更细的信息粒 ${r_1},{r_2}$ (其他复杂情形均可转化为这种情形,这里不再重复)。则 ${p_1} = {q_1} \cup $ ${q_2}$ ${p_2} = {q_3}$ ,…, ${p_n} = {q_m}$ $\left( {m = l + 1} \right)$ ${q_1} = {r_1} \cup {r_2}$ ${q_2} = {r_3}$ ,…, ${q_n} = {r_s}$ $\left( {s = m + 1} \right)$ ,那么 ${U / {{R_2}}} = \left\{ {{q_1},{q_2},{p_2},{p_3}, \cdots ,{p_l}} \right\}$ 以及 ${U / {{R_3}}} = \left\{ {{r_1},{r_2},{q_2},{q_3}, \cdots ,} \right.$ $\left. {{q_l}} \right\}$ 。通过公式,可得:

$ \begin{array}{*{20}{l}} {\;\;\;\;\;\;\;\;\;\;\text{RASD}\left( {{U / {{R_1}(X)}},{U / {{R_2}(X)}}} \right)}=\\ { \dfrac{1}{{\left| U \right|}}\displaystyle\sum\limits_{i = 1}^l {\displaystyle\sum\limits_{j = 1}^m {\dfrac{{(\displaystyle\sum\limits_{x \in \widetilde {{p_i}}} {\mu \left( x \right)} - \displaystyle\sum\limits_{x \in \widetilde {{q_j}}} {\mu \left( x \right)} )\displaystyle\sum\limits_{x \in \widetilde {{q_j}}} {\mu \left( x \right)} }}{{\left| U \right|}}} } } \end{array} $
$ \begin{array}{*{20}{l}} {\;\;\;\;\;\;\;\;\;\;\text{RASD}\left( {{U / {{R_1}(X)}},{U /{{R_3}(X)}}} \right)}=\\ { \dfrac{1}{{\left| U \right|}}\displaystyle\sum\limits_{i = 1}^l {\displaystyle\sum\limits_{k = 1}^s {\dfrac{{(\displaystyle\sum\limits_{x \in \widetilde {{p_i}}} {\mu (x)} - \displaystyle\sum\limits_{x \in \widetilde {{r_k}}} {\mu (x)} )\displaystyle\sum\limits_{x \in \widetilde {{r_k}}} {\mu (x)} }}{{\left| U \right|}}} } } \end{array} $

由于 ${p_1} = {q_1} \cup {q_2}$ ${q_1} = {r_1} \cup {r_2}$ ,故 ${\mu _{{p_1}}} = {\mu _{{q_1}}} + {\mu _{{q_2}}}$ ${\mu _{{q_1}}} = {\mu _{{r_1}}} + {\mu _{{r_2}}}$

$ \begin{array}{*{20}{l}} {\;\;\text{RASD}\left( {{U / {{R_1}}}(X),{U / {{R_2}(X)}}} \right)}= \end{array} $
$ \begin{array}{*{20}{l}} { \dfrac{1}{{\left| U \right|}} \cdot \dfrac{{{\mu _{{p_1}}}\left( {{\mu _{{q_1}}} + {\mu _{{q_2}}}} \right) - \left( {\mu _{{q_1}}^2 + \mu _{{q_2}}^2} \right)}}{{\left| U \right|}}} \end{array} $
$\begin{array}{*{20}{l}} {\;\;\;\;\;\;\;\;\;\;\text{RASD}\left( {{U / {{R_1}}}(X),{U / {{R_3}(X)}}} \right)}=\\ { \dfrac{1}{{\left| U \right|}} \cdot \dfrac{{{\mu _{{p_1}}}\left( {{\mu _{{r_1}}} + {\mu _{{r_2}}} + {\mu _{{r_3}}}} \right) - \left( {\mu _{{r_1}}^2 + \mu _{{r_2}}^2 + \mu _{{r_3}}^2} \right)}}{{\left| U \right|}}}=\\ {\;\;\;\;\;\;\;\;\;\; \dfrac{1}{{\left| U \right|}} \cdot \dfrac{{2\left( {{\mu _{{r_1}}}{\mu _{{r_2}}} + {\mu _{{r_2}}}{\mu _{{r_3}}} + {\mu _{{r_1}}}{\mu _{{r_3}}}} \right)}}{{\left| U \right|}}。} \end{array} $

同理, $\text{RASD}\left( {{U / {{R_2}}}(X),{U / {{R_3}(X)}}} \right)=$

$\begin{array}{l} \dfrac{1}{{\left| U \right|}} \cdot \dfrac{{\left( {{\mu _{{q_1}}} - {\mu _{{r_1}}}} \right){\mu _{{r_1}}} + \left( {{\mu _{{q_1}}} - {\mu _{{r_2}}}} \right){\mu _{{r_2}}}}}{{\left| U \right|}}=\\ \;\;\;\;\dfrac{1}{{\left| U \right|}} \cdot \dfrac{{\left( {{\mu _{{q_1}}}{\mu _{{r_1}}} + {\mu _{{q_1}}}{\mu _{{r_2}}}} \right) - \left( {\mu _{{r_1}}^2 + \mu _{{r_2}}^2} \right)}}{{\left| U \right|}} \end{array} $

由于 ${p_1} = {q_1} \cup {q_2}$ ${q_1} = {r_1} \cup {r_2}$ ,故 ${\mu _{{p_1}}} = {\mu _{{q_1}}} + {\mu _{{q_2}}}$ ${\mu _{{q_1}}} = {\mu _{{r_1}}} + {\mu _{{r_2}}}$ ,则

$ \begin{array}{*{20}{c}} {\text{RASD}\left( {{U / {{R_1}(X)}},{U / {{R_2}(X)}}} \right) + \text{RASD}\left( {{U / {{R_2}}}(X),{U / {{R_3}(X)}}} \right)}=\\ { \dfrac{1}{{\left| U \right|}} \cdot \dfrac{{2\left( {{\mu _{{r_1}}}{\mu _{{r_2}}} + {\mu _{{q_1}}}{\mu _{{q_2}}}} \right)}}{{\left| U \right|}}}=\\ { \dfrac{1}{{\left| U \right|}} \cdot \dfrac{{2\left( {{\mu _{{r_1}}}{\mu _{{r_2}}} + {\mu _{{r_1}}}{\mu _{{r_3}}} + {\mu _{{r_2}}}{\mu _{{r_3}}}} \right)}}{{\left| U \right|}}}= \\ { \text{RASD}\left( {{U / {{R_1}(X)}},{U / {{R_3}(X)}}} \right)} \end{array} $

由定理4可知,同一个粗糙粒结构中的两个粗糙近似空间的不确定性差异等于它们之间的知识距离。

例4 设一个信息系统 $S = \left( {U,C \cup D,V,f} \right)$ $U =$ $ \left\{ {{x_1},{x_2}, \cdots ,{x_9}} \right\}$ , ${R_1}$ ${R_2}$ ${R_3} \subseteq C$ $X \!=\!\dfrac{{0.4}}{{{x_1}}} \! +\! \dfrac{{0.6}}{{{x_2}}} +$ $\dfrac{{0.8}}{{{x_3}}} + \dfrac{{0.9}}{{{x_4}}} + $ $ \dfrac{{0.8}}{{{x_5}}} + \dfrac{{0.5}}{{{x_6}}} + \dfrac{{0.4}}{{{x_7}}} + \dfrac{{0.4}}{{{x_8}}} + \dfrac{{0.2}}{{{x_9}}}$ $U$ 上的一个目标概念, $U/{R_1} = \left\{ {\left\{ {{x_1},{x_2}, \cdots ,{x_6}} \right\},} \right.$ $\left. {\left\{ {{x_7},{x_8},{x_9}} \right\}} \right\}$ $U/{R_2} =\left\{ {\left\{ {{x_1},{x_2},{x_3},{x_4}} \right\},} \right.$ $\left. {\left\{ {{x_5},{x_6}} \right\},\left\{ {{x_7},{x_8},{x_9}} \right\}} \right\}$ ,以及 $U/{R_3} = $ $\left\{ {\left\{ {{x_1},{x_2},{x_3}} \right\},\left\{ {{x_4}} \right\}\left\{ {{x_5},{x_6}} \right\},} \right. $ $\left.{\left\{ {{x_7}} \right\},\left\{ {{x_8},{x_9}} \right\}} \right\}$ $U$ 上的3个知识空间。

$\text{RASD}\left( {{U / {{R_1}(X)}},{U / {{R_2}(X)}}} \right) = \dfrac{{\dfrac{{1.3}}{5} \times 2.7 + \dfrac{{2.7}}{5} \times 1.3}}{9} = \dfrac{{10.6}}{{81}}$

类似地

$ \begin{array}{*{20}{l}} \;{\text{RASD}\left( {{U / {{R_2}(X)}},{U / {{R_3}(X)}}} \right) = \dfrac{{5.9}}{{81}}}\\ {\text{RASD}\left( {{U / {{R_1}}}(X),{U / {{R_3}(X)}}} \right) = \dfrac{{16.5}}{{81}}} \end{array} $

因此

$ \begin{array}{*{20}{l}} \;\;\;\;\;\;\;\;\;\;{\text{RASD}\left( {{U / {{R_1}}},{U / {{R_3}}}} \right)}=\\ \;\;\;\;\text{RASD}\left( {U/{R_1}(X),U/{R_2}(X)} \right) + \\ \text{RASD}\left( {U/{R_2}(X),U/{R_3}(X)} \right)={ \dfrac{{16.5}}{{81}}} \end{array} $

在本文中,将一个信息系统中的最粗知识空间和最细知识空间分别表示为 $\sigma $ $\omega $ 。通过定理4,本文可得到以下推论。

推论1 设一个信息系统 $S = \left( {U,C \cup D,V,f} \right)$ ${R_1},{R_2} \subseteq C$ $X$ $U$ 上的一个目标概念。如果 ${R_1} \subseteq {R_2}$ ,则:

$ \begin{array}{*{20}{l}} {\;\;\;\;\;\;\;\;\;\;\;\;{\rm RASD}\left( {{U / {{R_1}(X)}},{U / {{R_2}(X)}}} \right)}=\\ {{\rm RASD}\left( {{U / {{R_1}(X)}},\omega } \right) -{\rm RASD}\left( {{U / {{R_2}}}(X),\omega } \right)} \end{array} $

推论2 设一个信息系统 $S = \left( {U,C \cup D,V,f} \right)$ ${R_1},{R_2} \subseteq C$ $X$ $U$ 上的一个目标概念。如果 ${R_1} \subseteq {R_2}$ ,则:

$ \begin{array}{*{20}{l}} {\;\;\;\;\;\;\;\;\;\;\;\;\text{RASD}\left( {{U / {{R_1}(X)}},{U / {{R_2}(X)}}} \right)}=\\ {\text{RASD}\left( {{U / {{R_2}(X)}},\sigma } \right) - \text{RASD}\left( {{U / {{R_1}}}(X),\sigma } \right)} \end{array} $

定理5 设一个信息系统 $S = \left( {U,C \cup D,V,f} \right)$ ${R_1} \subseteq C$ $X$ $U$ 上的一个目标概念, $\text{RASD}\left( {{U / {{R_1}(X)}},\omega } \right)$ 是一个粒度度量。

证明 1)由定理3可知, $\text{RASD}\left( {{U / {{R_1}(X)}},\omega } \right)$ $ \geqslant 0$

2)假设 ${R_2} \subseteq C$ ,当 ${R_1} = {R_2}$ 时,可得:

$ \text{RASD}\left( {{U / {{R_1}(X)}},\omega } \right) = \text{RASD}\left( {{U / {{R_2}(X)}},\omega } \right) $

3)由推论1可知,如果 ${R_1} \subseteq {R_2}$ ,那么RASD $\left( {{U / {{R_2}(X)}},\omega } \right) \leqslant \text{RASD}\left( {{U / {{R_1}(X)}},\omega } \right)$

定理6 设一个信息系统 $S = \left( {U,C \cup D,V,f} \right)$ ${R_1} \subseteq C$ $X$ $U$ 上的一个目标概念, $\text{RASD}\left( {{U / {{R_1}(X)}},\sigma } \right)$ 是一个信息度量。

证明 1)由定理3可知, $\text{RASD}\left( {{U / {{R_1}(X)}},\sigma } \right)$ $ \geqslant 0$

2)假设 ${R_2} \subseteq C$ ,当 ${R_1} = {R_2}$ 时,可得:

$ \text{RASD}\left( {{U / {{R_1}(X)}},\sigma } \right) = {\rm RASD}\left( {{U / {{R_2}(X)}},\sigma } \right) $

3)由推论1可知,如果 ${R_1} \subseteq {R_2}$ ,那么RASD $\left( {{U / {{R_1}(X)}},\sigma } \right) \leqslant \text{RASD}\left( {{U / {{R_2}(X)}},\sigma } \right)$

通过推论1和定理5可知,对于一个目标概念,粗糙粒结构中的任意两个粗糙近似空间的RASD等于它们之间的粒度度量差异。通过推论2和定理6可知,对于一个目标概念,粗糙粒结构中的任意两个粗糙近似空间的RASD等于它们之间的信息度量差异。结合定理4,本文以粗糙粒结构中的 $\omega $ 为原点,可以将粗糙近似空间通过RASD映射到一维坐标上。

3 粗糙粒结构的评价模型

在粗糙粒结构中,对不确定性问题进行求解时,通常希望在约束条件下可以利用尽可能少的知识空间使不确定性降低最大化。为了简单化,本文仅考虑约束条件为属性代价时的情形,通过第2节定义的粗糙知识距离以及在粗糙粒结构上得出的结论,提出了一种粗糙粒结构的评价模型。

定义9 知识距离序列。假设一个信息系统 $S = (U,C \cup D,V,f)$ ,其中 $R \subseteq C$ $X \subseteq U$ ${\rm GS} = (\text{KS}{_1},$ $\text{KS}{_2}, \cdots ,\text{KS}{_\xi })$ 是一个由 $\xi $ 个知识空间组成的粗糙粒结构,其中 $\text{KS}{_i} = {U / {{R_i}}}$ $i = 1,2, \cdots ,\xi $ ${R_i}$ 为一个条件属性集, ${R_\xi } \subset \cdots \subset {R_2} \subset {R_1} \subseteq C$ ,知识距离序列可表示为 ${L_{GS}} = ({\Delta _1},{\Delta _2}, \cdots ,{\Delta _{\xi - 1}})$ ,其中 ${\Delta _i} = \text{RASD}({U / {{R_i}(X)}},$ ${U / {{R_{i + 1}}(X)}}),$ $i \in [1,\xi - 1]$

基于定义9,本文提出了一种属性约束条件下的粗糙粒结构的评价模型,首先,本文在定义10中定义了一个评价参数 $\lambda $

定义10 评价参数。假设一个信息系统S = $ (U,C \cup D,V,f)$ ,其中 $R \subseteq C$ $X \subseteq U$ $\text{GS} = (\text{KS}{_1},\text{KS}{_2}, \cdots ,$ $\text{KS}{_\xi })$ 是一个由 $\xi $ 个知识空间组成的粗糙粒结构, ${L_{\text{GS}}}= ({\Delta _1},{\Delta _2}, \cdots ,{\Delta _{\xi - 1}})$ ,则

$\lambda = \frac{{\displaystyle\sum\limits_{i = 1}^{\psi - 1} {{\Delta _i}} }}{\psi }$ (11)

其中,

$\psi = \mathop {\max }\limits_{1 \leqslant k \leqslant \xi } \;k$
$\begin{array}{*{20}{l}} {\text{s.t.}}{\;\;\;\;\;\;\;\;\;\;\;\;\text{T}{\text{C}_{\text{K}{\text{S}_k}}} \leqslant \text{T}{\text{C}_{\text{user}}}} \end{array}$

通过式(8)可知, $\lambda $ 越大,说明对应的粗糙粒结构就越好,即该粒结构能够在约束条件下利用尽可能少的知识空间实现不确定性的降低最大化。

图4所示,为整个粗糙粒结构评价模型的流程图。首先,通过粗糙近似空间距离计算出不同的粗糙粒结构对应的知识距离序列,然后,通过式(8)并结合不同的约束条件计算得到对应的评价参数,从而实现不同约束条件下的粗糙粒结构的评价和选择。

Download:
图 4 粗糙粒结构的评价模型 Fig. 4 Evaluation model of rough granular structure

例5 如图5所示,设一个信息系统S= $\left( {U,\;C \cup D,\;V,\;f} \right)$ $X\;=\;\dfrac{0}{{{x_1}}} + \dfrac{0}{{{x_2}}} + \dfrac{1}{{{x_3}}} + \dfrac{0}{{{x_4}}} + \dfrac{1}{{{x_5}}} + \dfrac{1}{{{x_6}}} + \dfrac{1}{{{x_7}}} + $ $\dfrac{1}{{{x_8}}} + \dfrac{0}{{{x_9}}}$ $U$ 上的一个目标概念, $\text{GS}{_1} =(\text{KS}_1^1,\text{KS}_2^1,$ $\text{KS}_3^1,\text{KS}_4^1)$ $\text{GS}{_2} = (\text{KS}_1^2,\text{KS}_2^2,\text{KS}_3^2,$ $\text{KS}_4^2)$ 是两个粗糙粒结构,它们的属性代价序列分别为 $\text{TC}{_1} = (2,13,27,31)$ $\text{TC}{_2} =$ $ (2,7,22,28)$ ,其中属性代价序列为 $\text{TC}{_{\text{user}}} =$ $ (10,20,30,40)$

Download:
图 5 两个粗糙粒结构中的知识空间 Fig. 5 Knowledge spaces in two rough granular structures

通过式(7)可计算出 $\text{GS}{_1}$ $\text{GS}{_2}$ 的知识距离序列分别为 ${L_{\text{GS}{_1}}} = \Bigg(\dfrac{{10}}{{81}},\dfrac{{25}}{{81}},\dfrac{3}{{81}}\Bigg)$ ${L_{\text{GS}{_2}}} = \Bigg(\dfrac{5}{{81}},$ $\dfrac{{18}}{{81}},\dfrac{8}{{81}}\Bigg)$ ,结合已知条件,由式(8)可得, $\text{GS}{_1}$ 中的 $\text{KS}_1^1$ $\text{GS}{_2}$ 中的 $\text{KS}_1^2$ $\text{KS}_2^2 $ 属性代价小于 $\text{T}{\text{C}_{\text{user}}} = 10$ ,那么, ${\lambda _1} = 0$ ${\lambda _2} = \dfrac{5}{{81}}$ ,此时, ${\rm BN{D_1}}(X) = $ $\{ {x_1},{x_2}, \cdots ,{x_9}\} $ ${\rm BN{D_2}}(X) = $ $\{ {x_1},{x_2}, \cdots ,{x_8}\}$

因此, ${\lambda _1} > {\lambda _2}$ $\left| {\text{BN}{\text{D}_1}(X)} \right| > \left| {\text{BN}{\text{D}_2}(X)} \right|$ 。由于 $\text{GS}{_1}$ 在约束条件下只有一个知识空间可利用,无法进一步降低降不确定性,不能进行渐近式计算,而 $\text{GS}{_2}$ 在约束条件下利用知识空间进一步降低了不确定性,所以在约束条件 $\text{TC}{_{\text{user}}} = 10$ 下应该选择粗糙粒结构 $\text{GS}{_2}$ 进行问题求解。

$\text{GS}{_1}$ 中的 $\text{KS}_1^1$ $\text{KS}_2^1 $ $\text{GS}{_2}$ 中的 $\text{KS}_1^2$ $\text{KS}_2^2$ $\text{KS}_3^2$ 属性代价小于 $\text{T}{\text{C}_{\text{user}}} = 20$ ,那么:

$ {\lambda _1} = \dfrac{{\dfrac{{10}}{{81}}}}{{2 - 1}} = \dfrac{{10}}{{81}},\;{\lambda _2} = \dfrac{{\dfrac{5}{{81}} + \dfrac{{18}}{{81}}}}{{3 - 1}} = \dfrac{{23}}{{162}} $

此时, $\text{BND}{_1}(X) = \{ {x_3},{x_4}, \cdots ,{x_9}\} $ $\text{BND}{_2}(X) =\{ {x_1},$ $ {x_2}, \cdots ,{x_6}\} $

因此, ${\lambda _1} < {\lambda _2}$ $\left| {\text{BN}{\text{D}_1}(X)} \right| > \left|{\text{BN}{\text{D}_2}(X)} \right|$ ,虽然 $\text{GS}{_2}$ 在约束条件下利用了更多的知识空间个数,但是总体上却更大程度的降低了不确定性,所以在约束条件 $\text{T}{\text{C}_{\text{user}}} = 20$ 下应该选择粗糙粒结构 $\text{GS}{_2}$ 进行问题求解。

同理, $\text{GS}{_1}$ 中的 $\text{KS}_1^1$ $\text{KS}_2^1$ $\text{KS}_3^1$ $\text{GS}{_2}$ 中的 $\text{KS}_1^2$ $\text{KS}_2^2$ $\text{KS}_3^2$ $\text{KS}_4^2$ 属性代价小于 $\text{T}{\text{C}_{\text{user}}} = 30$ ,那么:

$ {\lambda _1} = \dfrac{{\dfrac{{10}}{{81}} + \dfrac{{25}}{{81}}}}{{3 - 1}} = \dfrac{{35}}{{162}},\;{\lambda _2} = \dfrac{{\dfrac{5}{{81}} + \dfrac{{18}}{{81}} + \dfrac{8}{{81}}}}{{4 - 1}} = \dfrac{{31}}{{243}} $

此时, $\text{BND}{_1}(X) = \{ {x_3},{x_4}\} $ $\text{BND}{_2}(X) = \{ {x_1},{x_2},$ ${x_3},{x_4}\} $

因此, ${\lambda _1} > {\lambda _2}$ $\left| {\text{BND}{_1}(X)} \right| < \left| {\text{BND}{_2}(X)} \right|$ 。由于 $\text{GS}{_1}$ 在约束条件下利用了更少的知识空间个数降低了更多的不确定性,所以在约束条件 $\text{T}{\text{C}_{\text{user}}} = 30$ 下应该选择粗糙粒结构 $\text{GS}{_1}$ 进行问题求解。

$\text{GS}{_1}$ 中的 $\text{KS}_1^1$ $\text{KS}_2^1$ $\text{KS}_3^1$ $\text{KS}_4^1$ $\text{GS}{_2}$ 中的 $\text{KS}_1^2$ $\text{KS}_2^2$ $\text{KS}_3^2$ $\text{KS}_4^2$ 属性代价小于 $\text{T}{\text{C}_{\text{user}}} = 40$ ,那么:

$ {\lambda _1} = \dfrac{{\dfrac{{10}}{{81}} + \dfrac{{25}}{{81}} + \dfrac{3}{{81}}}}{{4 - 1}} = \dfrac{{38}}{{243}},\;{\lambda _2} = \dfrac{{\dfrac{5}{{81}} + \dfrac{{18}}{{81}} + \dfrac{8}{{81}}}}{{4 - 1}} = \dfrac{{31}}{{243}} $

此时, $\text{BND}{_1}(X) = \text{Ø} $ $\text{BND}{_2}(X) = \{ {x_1},{x_2},{x_3},{x_4}\}。$

因此, ${\lambda _1} > {\lambda _2}$ $\left| {{\rm BN{D_1}}(X)} \right| < \left| {{\rm BN{D_2}}(X)} \right|$ 。由于 ${\rm GS}{_1}$ 在相同的知识空间个数上降低了更多得不确定性,所以在约束条件 $\text{T}{\text{C}_{\text{user}}} = 40$ 下应该选择粗糙粒结构 $\text{GS}{_1}$ 进行问题求解。

4 结束语

不同的粒化机制可以形成不同的粒结构,在粗糙集的序贯三支决策模型中,通过不同的属性集添加顺序可形成不同的粗糙粒结构。如何建立对这些粗糙粒结构的评价方法是本文的主要研究内容。在前期工作的基础上,提出了一种粗糙近似空间距离,并利用该距离研究了粗糙粒结构的结构特征,得到了粗糙粒结构中的两个知识空间的不确定性差异等于它们之间知识距离的结论。利用该结论,本文建立了一种在属性代价约束条件下的粗糙粒结构的评价模型,解决了在不同约束条件下评价并选择不同粗糙粒结构的问题。由于本文采用的是基于EMD的知识距离框架,因此,本文的方法具有扩展性,可以针对不同类型的粒结构设计评价模型,例如,对不同层次聚类算法、多尺度图像分割算法以及多粒度社区发现算法的评价和选择。但是,本文的工作还处于初步阶段,仅研究了如何评价粗糙粒结构,并没有考虑粗糙粒结构的构建问题,并且只考虑了属性代价为约束条件,评价模型的目标函数还有待进一步改进,尤其如何根据不同的约束条件设计目标函数是下一步工作的主要目标。

参考文献
[1] ZADEH L A. Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic[J]. Fuzzy sets and systems, 1997, 90(2): 111-127. DOI:10.1016/S0165-0114(97)00077-8 (0)
[2] PEDRYCZ W, SKOWRON A, KREINOVICH V. Handbook of granular computing[M]. Chichester: John Wiley & Sons, 2008: 719−740. (0)
[3] PEDRYCZ W, AL-HMOUZ R, MORFEQ A, et al. The design of free structure granular mappings: the use of the principle of justifiable granularity[J]. IEEE transactions on cybernetics, 2013, 43(6): 2105-2113. DOI:10.1109/TCYB.2013.2240384 (0)
[4] WANG Guoyin, YANG Jie, XU Ji. Granular computing: from granularity optimization to multi-granularity joint problem solving[J]. Granular computing, 2017, 2(3): 105-120. DOI:10.1007/s41066-016-0032-3 (0)
[5] YAO Yiyu. Perspectives of granular computing[C]//Proceedings of 2015 IEEE International Conference on Granular Computing. Beijing, China, 2005: 85−90. (0)
[6] ZADEH L A. Fuzzy sets[J]. Information and control, 1965, 8(3): 338-353. DOI:10.1016/S0019-9958(65)90241-X (0)
[7] PAWLAK Z. Rough sets[J]. International journal of computer & information sciences, 1982, 11(5): 341-356. (0)
[8] 张钹, 张铃. 问题求解理论及应用[M]. 北京: 清华大学出版社, 1990. (0)
[9] 李德毅, 孟海军, 史雪梅. 隶属云和隶属云发生器[J]. 计算机研究与发展, 1995(6): 15-20.
LI Deyi, MENG Haijun, SHI Xuemei. Membership clouds and membership cloud generators[J]. Journal of computer research and development, 1995(6): 15-20. (0)
[10] 苗夺谦, 李德毅, 姚一豫, 等. 不确定性与粒计算[M]. 北京: 科学出版社, 2011. (0)
[11] 徐计, 王国胤, 于洪. 基于粒计算的大数据处理[J]. 计算机学报, 2015(8): 1497-1517.
XU Ji, WANG Guoyin, YU Hong. Review of big data processing based on granular computing[J]. Chinese journal of computers, 2015(8): 1497-1517. DOI:10.11897/SP.J.1016.2015.01497 (0)
[12] YAO Yiyu. Three-way decisions with probabilistic rough sets[J]. Information sciences, 2010, 180(3): 341-353. DOI:10.1016/j.ins.2009.09.021 (0)
[13] 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 (0)
[14] 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 (0)
[15] QIAN Yuhua, CHENG Honghong, WANG Jieting, et al. Grouping granular structures in human granulation intelligence[J]. Information sciences, 2017, 382-383: 150-169. DOI:10.1016/j.ins.2016.11.024 (0)
[16] 张钹, 张铃. 问题求解理论及应用[M]. 北京: 清华大学出版社, 1990. (0)
[17] ZHANG Ling, ZHANG Bo. The structure analysis of fuzzy sets[J]. International journal of approximate reasoning, 2005, 40(1/2): 92-108. (0)
[18] ZHANG Ling, ZHANG Bo. Fuzzy reasoning model under quotient space structure[J]. Information sciences, 2005, 173(4): 353-364. DOI:10.1016/j.ins.2005.03.005 (0)
[19] WIERMAN M J. Measuring uncertainty in rough set theory[J]. International journal of general systems, 1999, 28(4/5): 283-297. (0)
[20] LIANG Jiye, CHIN K S, DANG Chuangyin, et al. A new method for measuring uncertainty and fuzziness in rough set theory[J]. International journal of general systems, 2002, 31(4): 331-342. DOI:10.1080/0308107021000013635 (0)
[21] YAO Yiyu, ZHAO Liquan. A measurement theory view on the granularity of partitions[J]. Information sciences, 2012, 213: 1-13. DOI:10.1016/j.ins.2012.05.021 (0)
[22] LAWVERE F W. Metric spaces, generalized logic, and closed categories[J]. Rendiconti del seminario matematico e fisico di milano, 1973, 43(1): 135-166. DOI:10.1007/BF02924844 (0)
[23] RUBNER Y, GUIBAS L, TOMASI C. The earth mover's distance, multi-dimensional scaling, and color-based image retrieval[C]//Proceedings of the ARPA Image Understanding Workshop. 1997: 661−668. (0)
[24] RUBNER Y, TOMASI C, GUIBAS L J. The earth mover's distance as a metric for image retrieval[J]. International journal of computer vision, 2000, 40(2): 99-121. DOI:10.1023/A:1026543900054 (0)
[25] 郭增晓, 米据生. 粗糙模糊集的模糊性度量[J]. 模糊系统与数学, 2005, 19(4): 135-140.
GUO Zengxiao, MI Jusheng. An uncertainty measure in rough fuzzy sets[J]. Fuzzy systems and mathematics, 2005, 19(4): 135-140. DOI:10.3969/j.issn.1001-7402.2005.04.023 (0)
[26] QIN Huani, LUO Darong. New uncertainty measure of rough fuzzy sets and entropy weight method for fuzzy-target decision-making tables[J]. Journal of applied mathematics, 2014, 2014: 487036. (0)
[27] HU J, PEDRYCZ W, WANG G. A roughness measure of fuzzy sets from the perspective of distance[J]. International journal of general systems, 2016, 45(3): 352-367. DOI:10.1080/03081079.2015.1086580 (0)
[28] SUN Bingzhen, MA Weimin. Uncertainty measure for general relation-based rough fuzzy set[J]. Kybernetes, 2013, 42(6): 979-992. DOI:10.1108/K-12-2012-0119 (0)
[29] DAI Jianhua, WANG Wentao, XU Qing. An uncertainty measure for incomplete decision tables and its applications[J]. IEEE transactions on cybernetics, 2013, 43(4): 1277-1289. DOI:10.1109/TSMCB.2012.2228480 (0)
[30] QIAN Y H, LIANG J Y, DANG C Y, et al. Knowledge granulation and knowledge distance in a knowledge base[J]. International journal of approximate reasoning, 2011, 19(2): 263-264. (0)
[31] QIAN Yuhau, LI Yebin, LIANG Jiye, et al. Fuzzy granular structure distance[J]. IEEE transactions on fuzzy systems, 2015, 23(6): 2245-2259. DOI:10.1109/TFUZZ.2015.2417893 (0)
[32] LIANG Jiye, LI Ru, QIAN Yuhau. Distance: a more comprehensible perspective for measures in rough set theory[J]. Knowledge-based systems, 2012, 27: 126-136. DOI:10.1016/j.knosys.2011.11.003 (0)
[33] YANG Xibei, QIAN Yuhua, YANG Jingyu. On characterizing hierarchies of granulation structures via distances[J]. Fundamenta informaticae, 2013, 123(3): 365-380. DOI:10.3233/FI-2012-816 (0)
[34] YANG Xibei, SONG Xiaoning, SHE Yanhong, et al. Hierarchy on multigranulation structures: a knowledge distance approach[J]. International journal of general systems, 2013, 42(7): 754-773. DOI:10.1080/03081079.2013.810625 (0)
[35] YANG Jie, WANG Guoyin, ZHANG Qinghua. Knowledge distance measure in multigranulation spaces of fuzzy equivalence relations[J]. Information sciences, 2018, 448-449: 18-35. DOI:10.1016/j.ins.2018.03.026 (0)
[36] YANG Jie, WANG Guoyin, LI Xukun. Multi-granularity similarity measure of cloud concept[C]//International Joint Conference on Rough Sets. Santiago, Chile, 2016: 318−330. (0)