第15卷第1期 智能系统学报 Vol.15 No.1 2020年1月 CAAI Transactions on Intelligent Systems Jan.2020 D0L:10.11992tis.201904037 基于知识距离的粗糙粒结构的评价模型 杨洁2，王国胤2，张清华2 (1,重庆邮电大学计算智能重庆市重点实验室，重庆400065,2.重庆邮电大学计算机科学与技术学院，重庆400065； 3.重庆邮电大学人工智能学院.重庆400065) 摘要：在粒计算理论中，通过不同的粒计算机制可以生成不同的粒结构。在粗糙集中，对于同一个信息表而 言，通过不同的属性添加顺序可以得到由不同的序贯层次结构，即粗糙粒结构。在粗糙粒结构中，不同的属性 获取顺序导致了对不确定性问题求解的不同程度。因此，如何有效评价粗糙粒结构是一个值得研究的问题。 本文将从知识距离的角度研究这个问题。首先，在前期工作所提出的知识距离框架上提出了一种粗糙近似空 间距离，用于度量粗糙近似空间之间差异性。基于提出的知识距离，研究了粗糙粒结构的结构特征。在粗糙粒 结构中，在对不确定性问题进行求解时，本文希望在约束条件下可以利用尽可能少的知识空间使不确定性降低 达到最大化。基于这个思想并利用以上得出的结论，在属性代价约束条件下，引入了一个评价参数，并在此 基础建立了一种粗糙粒结构的评价模型，该方法实现了在属性代价约束条件下选择粗糙粒结构的功能。最后， 通过实例验证了本文提出的模型的有效性。 关键词：粗糙粒结构；知识距离：不确定性度量：评价模型；粒计算；粗糙集；约束条件：不确定性度量 中图分类号：TP311文献标志码：A文章编号：1673-4785(2020)01-0166-09 中文引用格式：杨洁，王国胤，张清华.基于知识距离的粗糙粒结构的评价模型.智能系统学报，2020,15(1)：166-174. 英文引用格式：YANG Jie,.WANG Guoyin,.ZHANG Qinghua..Evaluation model of rough granular structure based on knowledge distance[JI.CAAI transactions on intelligent systems,2020,15(1):166-174. Evaluation model of rough granular structure based on knowledge distance YANG Jie2,WANG Guoyin'2,ZHANG Qinghua23 (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 calcu- lation 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 attrib- ute 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 approxima- tion 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 pos- sible by using smaller knowledge space.Then,based on this idea and the above conclusions,an evaluation parameter A is introduced under the constraint of attribute cost,and further,an evaluation model of rough granular structure is estab- lished.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. Keywords:rough granular structure;knowledge distance;uncertainty measure;evaluation model;granular computing; rough sets;constraint condition;uncertainty measure 收稿日期：2019-04-16 基金项目：国家自然科学基金项目(61572091)：贵州省教育厅科 早在1997年，Zadeh教授U就提出了粒计算 技人才成长项目(KY(2018)No.318). 通信作者：杨洁.E-mail:530966074@qq.com 是模糊信息粒化、粗糙集理论和区间计算的超
DOI: 10.11992/tis.201904037 基于知识距离的粗糙粒结构的评价模型 杨洁1,2，王国胤1,2,3，张清华1,2,3 （1. 重庆邮电大学 计算智能重庆市重点实验室，重庆 400065; 2. 重庆邮电大学 计算机科学与技术学院，重庆 400065; 3. 重庆邮电大学 人工智能学院，重庆 400065） 摘 要：在粒计算理论中，通过不同的粒计算机制可以生成不同的粒结构。在粗糙集中，对于同一个信息表而 言，通过不同的属性添加顺序可以得到由不同的序贯层次结构，即粗糙粒结构。在粗糙粒结构中，不同的属性 获取顺序导致了对不确定性问题求解的不同程度。因此，如何有效评价粗糙粒结构是一个值得研究的问题。 本文将从知识距离的角度研究这个问题。首先，在前期工作所提出的知识距离框架上提出了一种粗糙近似空 间距离，用于度量粗糙近似空间之间差异性。基于提出的知识距离，研究了粗糙粒结构的结构特征。在粗糙粒 结构中，在对不确定性问题进行求解时，本文希望在约束条件下可以利用尽可能少的知识空间使不确定性降低 达到最大化。基于这个思想并利用以上得出的结论，在属性代价约束条件下，引入了一个评价参数 λ，并在此 基础建立了一种粗糙粒结构的评价模型，该方法实现了在属性代价约束条件下选择粗糙粒结构的功能。最后， 通过实例验证了本文提出的模型的有效性。 关键词：粗糙粒结构；知识距离；不确定性度量；评价模型；粒计算；粗糙集；约束条件；不确定性度量 中图分类号：TP311 文献标志码：A 文章编号：1673−4785(2020)01−0166−09 中文引用格式：杨洁, 王国胤, 张清华. 基于知识距离的粗糙粒结构的评价模型 [J]. 智能系统学报, 2020, 15(1): 166–174. 英文引用格式：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. Evaluation model of rough granular structure based on knowledge distance YANG Jie1,2 ，WANG Guoyin1,2,3 ，ZHANG Qinghua1,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. Keywords: rough granular structure; knowledge distance; uncertainty measure; evaluation model; granular computing; rough sets; constraint condition; uncertainty measure 早在 1997 年，Zadeh 教授[1] 就提出了粒计算 是模糊信息粒化、粗糙集理论和区间计算的超 收稿日期：2019−04−16. 基金项目：国家自然科学基金项目 (61572091);贵州省教育厅科 技人才成长项目 (KY(2018)No.318). 通信作者：杨洁. E-mail：530966074@qq.com. 第 15 卷第 1 期 智 能 系 统 学 报 Vol.15 No.1 2020 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2020
第1期 杨洁，等：基于知识距离的粗糙粒结构的评价模型 ·167· 集，是粒数学的子集。粒计算是一种新的模拟 1基本概念 人类思维机制的方法论，在粒计算的“大伞”之 下，包含了很多具体的模型，如模糊集、粗糙集四 一个信息系统是一个四元组，可表示为 商空间、云模型等。粒计算是研究基于多层 S=(U,CUD,Vf),其中U为一个非空论域，C为 次粒结构的思维方式、问题求解方法、信息处理 条件属性集合，D为决策属性集，V为对每个对象 模式的理论o。 对应的属性值集合，f:U×C是一个信息函数。 基于粒计算理论，Yao提出了序贯三支决 定义1粗糙集1。设一个信息系统S= 策理论(sequential three-way decisions,.S3WD)。从 (U,CUD,Vf),其中RsC和XsU,那么X的上、 多粒度的角度来说3，随着信息系统中属性或 下近似集定义如下： 信息的增加，S3WD中等价类将逐渐变小。S3WD RX)={x∈UI[xRSX) 是一种利用粗糙近似空间的渐近式问题求解模 R(X)={x∈UI[xRnX≠O) 型，本质上是粗糙粒结构，即通过由粗到细的切 其中[xR代表由等价关系U/R诱导的等价类，即 换粒度，实现问题的逐步求解。为了实现渐近式 U/R={[x1,[x2,…,[xmlo 的最优尺度的选择和属性约简，文献[15]提出了 本章中，仅从划分的角度，一个知识空间UR 一种局部规则提取方法，本质上运用了序贯三支 通常叫做一个商空间，当利用U/R对目标概念X 进行粗糙近似描述时，通常将U/R表示为U/R(X), 决策的思想。在现实的决策分析中，S3WD为求 称为粗糙近似空间。简单而言，为了防止混淆本 解复杂问题提供了一种模拟人类的多粒度思维。 文假设[xk兰[x。如果R(X)=R(X),则X是一个 从层次商空间结构(hierarchical quotient space structure,.HQSS)Is18的角度来说，等价类将会随 可定义集，否则X是一个粗糙集。在粗糙集中， 论域U通常被划分为正域、负域和边界域，分别 着粒度的细化逐渐细分成更细的等价类，这意味 定义如下： 着在S3WD模型中，随着属性或信息的增加， POSR(X)=R(X) 个目标概念可以通过不同粒度的知识进行描述。 BND&(X)=R(X)-R(X) 再者，由于较细粒度的知识空间上包含了更多的 NEGR(X)=U-R(X) 信息，所以在较细粒度的知识空间上可以更准确 定义2粒度度量92。假设U为一个有限 地刻画目标概念。但是，构建较细粒度的知识空 非空论域，一个函数2'→R对于任意PQ∈2， 间需要更多的代价以及在较细粒度上进行问题求 如果满足以下条件： 解需要更多的时间消耗。 1)m(x)≥0： 通过以上分析，在S3WD模型中，本文希望 2)PcQ→m(P)<m(Q): 在约束条件下可以利用尽可能少的知识空间最大 3)P=,Q→m(P)=m(Q)月 化降低问题的不确定性，从而对问题进行求解， 则它是一个粒度度量。 并且针对不同的约束条件评价并选择不同的粗糙 定义3距离度量2四。假设U为一个非空有 粒结构进行问题求解也是需要解决的问题。 限论域，A、B、C是3个有限集合，YA、B、CcU。 基于这个思想，本文从知识距离的角度研究 如果满足以下3个条件： 粗糙粒结构的评价模型（为了简单起见，本文仅 1)正定性：VA,B)≥0： 考虑属性代价为约束条件下粗糙粒结构进行评价 2)对称性：V(A,B)=V(B,A): 选择)。首先，基于前期工作中提出的知识距离框 3)三角不等式：V(A,B)+V(B,C)≥V(A,C): 架进一步提出了一种粗糙近似空间距离并讨论了 则函数V(,)是一个真正的距离度量。 其相关性质。其次，基于提出的粗糙近似空间距 定义4I231假设P={(p1,w,(p2,w… 离研究了层次粒结构对目标概念的刻画能力，并 (p,wn)》和Q={q1,wg,),(q2,w),,(qm,wg月分别是 得到同一个粗糙粒结构中的两个知识空间的不确 两个具有I和m个类簇的分布。P:和q,代表P 定性差异等于它们之间的知识距离的结论，并通 和Q类簇，wn和wg,分别P:和q的权重。c代 过实例表验证了本文的评价模型的有效性。此 表P,和9之间的差异性度量，例如，欧式距离。 外，本文的评价模型具有可扩展性，针对不同的 EMD的目标是寻找一个流量矩阵F=[f最小化 粒结构设计合适的知识距离，可用于评价不同类 总代价，其中f代表卫：到9的流量。 型的粒结构，例如层次聚类、多尺度图像分割以 :. 及多粒度社区发现等问题
集，是粒数学的子集。粒计算[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 ∪ D,V, f) U C D V f : U ×C 一个信息系统是一个四元组，可表示为 ，其中 为一个非空论域， 为 条件属性集合， 为决策属性集， 为对每个对象 对应的属性值集合， 是一个信息函数。 S = (U,C ∪ D,V, f) R ⊆ C X ⊆ U X 定 义 1 粗糙集 [ 7 ]。设一个信息系统 ，其中 和 ，那么 的上、 下近似集定义如下： R(X) = { x ∈ U|[x]R ⊆ X} R(X) = { x ∈ U|[x]R ∩ X , Ø} [x]R U/R U/R = {[x]1,[x]2,··· ,[x]m} 其中 代表由等价关系 诱导的等价类, 即 。 U/R U/R X U/R U/R(X) [x]R ≜ [x] R(X) = R(X) X X U 本章中，仅从划分的角度，一个知识空间 通常叫做一个商空间，当利用 对目标概念 进行粗糙近似描述时，通常将 表示为 ， 称为粗糙近似空间。简单而言, 为了防止混淆本 文假设 。如果 ，则 是一个 可定义集, 否则 是一个粗糙集。在粗糙集中， 论域 通常被划分为正域、负域和边界域，分别 定义如下： POSR(X) = R(X) BNDR(X) = R(X)−R(X) NEGR(X) = U −R(X) U 2 U → ℜ P,Q ∈ 2 U 定义 2 粒度度量[19-21]。假设 为一个有限 非空论域，一个函数 对于任意 ， 如果满足以下条件： 1) m(x) ⩾ 0 ； 2) P ⊂ Q ⇒ m(P) < m(Q) ； 3) P≡sQ ⇒ m(P) = m(Q) ； 则它是一个粒度度量。 U ∀A B C ⊆ U 定义 3 距离度量[22]。假设 为一个非空有 限论域，A、B、C 是 3 个有限集合， 、 、 。 如果满足以下 3 个条件： 1) 正定性： V(A,B) ⩾ 0 ； 2) 对称性： V(A,B) = V(B,A) ； 3) 三角不等式： V (A,B)+V (B,C) ⩾ V (A,C) ； 则函数 V(·,·) 是一个真正的距离度量。 P = {(p1,wp1 ),(p2,wp2 ),..., (pl ,wpl )} Q = {(q1,wq1 ),(q2,wq2 ),...,(qm,wqm )} pi qj P Q wpi wqj pi qj ci j pi qj F = [fi j] fi j pi qj 定 义 4 [ 2 3 ] 假设 和 分别是 两个具有 l 和 m 个类簇的分布。 和 代表 和 类簇， 和 分别 和 的权重。 代 表 和 之间的差异性度量，例如，欧式距离。 EMD 的目标是寻找一个流量矩阵 最小化 总代价，其中 代表 到 的流量。 work(P,Q) = ∑l i=1 ∑m j=1 ci j fi j 第 1 期 杨洁，等：基于知识距离的粗糙粒结构的评价模型 ·167·
·168· 智能系统学报 第15卷 S.t. 分别表示了上面分析的两种情况，图2（©）表示两 f≥01≤i≤n,1≤j≤m (1) 个知识空间之间不确定性差异适中的情况。 25≤：1in (2) 2≤1jm (3) 2=②2列 (4) 式(1)限制流量传递过程为P到Q,不能反 向；式(2)限制从P,运出去的总流量不能超过自 身的总流量；式(3)限制Q,接收的总流量不能超 过自身的总流量；式(4)限制总传递流量的上限 KS] ,=,- 中中中”中”中中中中”中”1””” 是P和Q的流量的最小值。当这个运输问题解 决时，这个最优的流量分配即可求得，即EMD被 图1粒结构示意图 Fig.1 Schematic diagram of granular structure 定义为由总流量归一化的结果： AR-RI-RI 1j=1 UIR UIR EMD(P.O)= (5) (a)知识空间之间不确定性较小 一般来说，式（⑤）中的c(,)可以是任意差异 性度量，可根据具体问题来选取。 △R=R1 定理12324 如果c(,)是一个真正的度量， UIR 且两个分布的总权重相同，即公=乃，那么 人 (b)知识空间之间不确定性较大 EMD为一个真正的距离度量。 在粒计算中，信息粒化旨在建立基于外部世 △R=R,-R 界的有效的并以用户为中心的概念，同时简化物 UIR UIR 理世界和虚拟世界的认识，可以高效地提供“实 用”的非精确解。信息粒化首先需要研究信息 (c)知识空间之间不确定性适中 粒、粒层和整个粒结构的表示，然后针对表示方 Target X☐POS()☐BND(☐NEG9() 法进行构建。同一粒化准则对应一个知识空 图23种不同程度的知识空间细分情况 间，不同粒化准则对应多个知识空间，不同知识 Fig.2 Three different levels of knowledge spaces subdivi- 空间（相邻两知识空间或跨知识空间）中信息粒 sion 之间的相互关系构成一个结构，由此得到的多个 2知识距离 知识空间及知识空间之间的关系称为粒的拓扑空 间，简称为粒结构，如图1所示，为一个粒结构的 从粒计算的角度来说，无论是信息嫡还是知 整体示意图。 识粒度都无法刻画粒结构中知识空间之间的差异 在S3WD模型中，随着粒度的细分，一方面， 性。在粗糙集模型中，不确定性度量用于度量粗 如果知识空间之间的不确定性差异太小，意味着 糙近似空间刻画目标概念的不确定性程度。虽然 新增加的属性对于不确定性的降低几乎没有贡 当前存在许多不确定性度量方法2s2,但是这些 献，因此原先在边界域的样本有可能仍然在边界 方法仍然不够准确，即具有相同不确定性的两个 域，无法对它们进行决策；另一方面，如果知识空 知识空间不一定等价，它们的差异性如何刻画？ 间之间的不确定性差异太大，意味着获取新增加 为了解决这个问题，钱字华0刘首次提出了基于 的属性需要很大的代价，因此有可能无法满足用 邻域信息粒的知识距离，并建立了同一知识基中 户的时限约束条件。如图2所示，图2(a)和图2b) 完备粒空间与不完备粒空间之间的关系。杨习
s.t. fi j ⩾ 0; 1 ⩽ i ⩽ n,1 ⩽ j ⩽ m (1) ∑m j=1 fi j ⩽ wi ; 1 ⩽ i ⩽ n (2) ∑l i=1 fi j ⩽ wj ; 1 ⩽ j ⩽ m (3) ∑l i=1 ∑m j=1 fi j = min{∑l i=1 wi , ∑m j=1 wj } (4) 式 (1) 限制流量传递过程为 P 到 Q, 不能反 向；式 (2) 限制从 Pi 运出去的总流量不能超过自 身的总流量；式 (3) 限制 Qj 接收的总流量不能超 过自身的总流量；式 (4) 限制总传递流量的上限 是 P 和 Q 的流量的最小值。当这个运输问题解 决时，这个最优的流量分配即可求得，即 EMD 被 定义为由总流量归一化的结果： EMD(P,Q) = ∑l i=1 ∑m j=1 ci j fi j ∑l i=1 ∑m j=1 fi j (5) 一般来说，式 (5) 中的 c(·,·) 可以是任意差异 性度量，可根据具体问题来选取。 c(·,·) ∑n i=1 wi = ∑m j=1 wj 定理 1 [23-24] 如果 是一个真正的度量， 且两个分布的总权重相同，即 ，那么 EMD 为一个真正的距离度量。 在粒计算中，信息粒化旨在建立基于外部世 界的有效的并以用户为中心的概念，同时简化物 理世界和虚拟世界的认识，可以高效地提供“实 用”的非精确解。信息粒化首先需要研究信息 粒、粒层和整个粒结构的表示，然后针对表示方 法进行构建[11]。同一粒化准则对应一个知识空 间，不同粒化准则对应多个知识空间，不同知识 空间 (相邻两知识空间或跨知识空间) 中信息粒 之间的相互关系构成一个结构，由此得到的多个 知识空间及知识空间之间的关系称为粒的拓扑空 间，简称为粒结构，如图 1 所示，为一个粒结构的 整体示意图。 在 S3WD 模型中，随着粒度的细分，一方面， 如果知识空间之间的不确定性差异太小，意味着 新增加的属性对于不确定性的降低几乎没有贡 献，因此原先在边界域的样本有可能仍然在边界 域，无法对它们进行决策；另一方面，如果知识空 间之间的不确定性差异太大，意味着获取新增加 的属性需要很大的代价，因此有可能无法满足用 户的时限约束条件。如图 2 所示，图 2(a) 和图 2(b) 分别表示了上面分析的两种情况，图 2(c) 表示两 个知识空间之间不确定性差异适中的情况。 ………………………… ………………………… ………………………… ………………………… ………………………… … KS1 KSj−1 KSj KSi … … … … 图 1 粒结构示意图 Fig. 1 Schematic diagram of granular structure U/R1 U/R2 ΔR=R1−R2 U/R1 U/R3 ΔR=R1−R3 U/R1 U/R4 ΔR=R1−R4 Target X POSR (α,β) (X) BNDR (α,β) (X) NEGR (α,β) (X) (a) 知识空间之间不确定性较小 (b) 知识空间之间不确定性较大 (c) 知识空间之间不确定性适中 图 2 3 种不同程度的知识空间细分情况 Fig. 2 Three different levels of knowledge spaces subdivision 2 知识距离 从粒计算的角度来说，无论是信息熵还是知 识粒度都无法刻画粒结构中知识空间之间的差异 性。在粗糙集模型中，不确定性度量用于度量粗 糙近似空间刻画目标概念的不确定性程度。虽然 当前存在许多不确定性度量方法[25-29] ，但是这些 方法仍然不够准确，即具有相同不确定性的两个 知识空间不一定等价，它们的差异性如何刻画？ 为了解决这个问题，钱宇华[30-32] 首次提出了基于 邻域信息粒的知识距离，并建立了同一知识基中 完备粒空间与不完备粒空间之间的关系。杨习 ·168· 智 能 系 统 学 报 第 15 卷
第1期 杨洁，等：基于知识距离的粗糙粒结构的评价模型 ·169· 贝训将知识距离应用到多粒度空间，通过知识 距离代数格导出一个偏序关系，可用于描述多粒 QSD(U/R1.U/R2)= 22 Pinq= 度空间中的层次结构。但是，当前的知识距离模 2 5 4 1 型缺乏清晰的物理解释和理论背景，并且不具有 ×4+×2+×1+g×2 91 =0.296 扩展性。在前期工作中Bs3,本文基于EMD提出 9 了一种知识距离框架(knowledge distance frame-. 通过多对多匹配计算，QSD实现了两个知识 wok,KDF)并给出了知识距离的物理意义，在此 空间之间的差异性度量。但是，对于粗糙集来 基础上进一步构建了一种商空间知识距离(quo- 说，当前知识距离的工作（包括QSD)仅仅是从知 tient space distance,QSD) 识空间的角度出发，反映的是两个知识空间划分 定义5知识距离框架。假设K=(U,R)是 差异性，并没有考虑它们对目标概念刻画时的差 -个知识基，Kp={p1,P2,…,pl和Kg={q1,q2,…,9m} 异性，有可能导致同一目标概念在两个不同粒度 是两个分别由等价关系P和Q产生的知识空间， 的知识空间中具有相同的不确定性度量结果，从 d=d(p,q)代表信息粒p:和q,之间的距离，代 而无法区分它们对目标概念的近似能力。为了解 表p:和q之间的流量，其中=lP:nq。K和 决以上问题，本文提出了一种粗糙近似空间知识 Ke之间的知识距离框架有如下定义： (rough approximation space distance,RASD). 如图3所示，为QSD和RASD两种类型的知识距 KDF(Kp,Ko)= 22 (6) 离的示意图，与QSD相比，RASD可以体现两个知 识空间对目标概念刻画能力的差异性。 由于对同一论域进行划分的不同知识空间的 对象数是相同的，故∑l=∑=UL.式(6)符 QSD (U/RI,UIR2)- =1 i=1 合约束条件式(4)。同样，式(7)符合约束条件式 (I)(3)。KDF表示的是同一个知识基的任意两个 UIR UIR 知识空间之间匹配对象的最小成本。显然，通过 采用不同的信息粒距离，可以产生一组基于划分 的知识距离。基于EMD的优点，KDF可以实现 -RASD (UIRUIR,)- 一个多对多的匹配，更符合人类的认知，可以更 准确地刻画两个知识空间的差异性。因此，KDF UIR (X) UIR (X) 是一个有效直观的描述知识空间之间差异性的数 学工具，可扩展到度量任何形式的知识空间之间 的差异性（或相似性）。 图3两种类型的知识距离 定义6商空间知识距离。设一个信息系 Fig.3 Two types of knowledge distance 统S=(U,CUD,Vf,R,R2C,U/R1={p1,P2,…,Pl 2.1 粗糙近似空间距离 和U/R2={q,2,…,9m}是U上的两个知识空间， 为了反映不同知识空间对目标概念的刻画能 d=d(P,9)代表信息粒P:和9，之间的距离，g代 力的差异性，本文基于知识距离框架进一步提出 表p:和q之间的流量，其中f=P:nq。UIR= 了一种粗糙近似空间距离。 {p1,P2,…,p和U/R2={q,92,…,qm}之间的知识距离 定义7模糊集合距离。假设U为一个非空 框架有如下定义： 有限论域，X是U上的一个目标概念。如果A、B是 QSD(UIR.UIR)=p. 台台 UIP:0g U上的两个有限集合，A和B之间的距离为 ∑-∑) 式中lp:⊕ql=piUqi-pingso 6(A,B)=AuB 例1设一个信息系统S=(U,CUD,Vf月，U={x1, IU八 ,l,RRcC,X=0+0+0+1+1t 由定义7可知，无论X为U上的一个清晰集 还是模糊集，6A,B)都可以刻画两个集合（请晰集 心的一个目标相 或模糊集)之间的距离。 x6x,xg},U/R1={1,2,…,x6},{,xg,}和U/R2= 定理2假设U为一个非空有限论域，6(，) {x1,2,x3,x4},{5,x6,,{x8,g是U上的两个知识空间。 是U上的一个距离度量
贝 [33-34] 将知识距离应用到多粒度空间，通过知识 距离代数格导出一个偏序关系，可用于描述多粒 度空间中的层次结构。但是，当前的知识距离模 型缺乏清晰的物理解释和理论背景，并且不具有 扩展性。在前期工作中[35-36] ，本文基于 EMD 提出 了一种知识距离框架 (knowledge distance framework, KDF) 并给出了知识距离的物理意义，在此 基础上进一步构建了一种商空间知识距离 (quotient space distance，QSD)。 K = (U,ℜ) KP = {p1, p2,··· , pl} KQ ={q1,q2,··· ,qm} P Q di j = d(pi ,qj) pi qj pi qj fi j = pi ∩qj KP KQ 定义 5 知识距离框架[35]。假设 是 一个知识基， 和 是两个分别由等价关系 和 产生的知识空间， 代表信息粒 和 之间的距离，fij 代 表 和 之间的流量，其中 。 和 之间的知识距离框架有如下定义： KDF(KP,KQ) = 1 |U| ∑l i=1 ∑m j=1 di j fi j (6) ∑l i=1 |pi | = ∑m j=1 qj = |U| 由于对同一论域进行划分的不同知识空间的 对象数是相同的，故 ，式 (6) 符 合约束条件式 (4)。同样，式 (7) 符合约束条件式 (1)~(3)。KDF 表示的是同一个知识基的任意两个 知识空间之间匹配对象的最小成本。显然，通过 采用不同的信息粒距离，可以产生一组基于划分 的知识距离。基于 EMD 的优点，KDF 可以实现 一个多对多的匹配，更符合人类的认知，可以更 准确地刻画两个知识空间的差异性。因此，KDF 是一个有效直观的描述知识空间之间差异性的数 学工具，可扩展到度量任何形式的知识空间之间 的差异性 (或相似性)。 S = (U,C ∪ D,V, f) R1,R2 ⊆ C U/R1 ={p1, p2,··· , pl} U/R2 = {q1,q2,··· ,qm} U di j = d(pi ,qj) pi qj pi qj fi j = pi ∩qj U/R1 = {p1, p2,··· , pl} U/R2 = {q1,q2,··· ,qm} 定义 6 商空间知识距离[35]。设一个信息系 统 ， ， 和 是 上的两个知识空间， 代表信息粒 和 之间的距离，fij 代 表 和 之 间 的流量，其中 。 和 之间的知识距离 框架有如下定义： QSD(U/R1 ,U/R2) = 1 |U| ∑l i=1 ∑m j=1 pi ⊕qj |U| pi ∩qj pi ⊕qj = pi ∪qj − pi ∩qj 式中 。 S = (U,C ∪ D,V, f),U = {x1, x2,··· , x9} R1,R2 ⊆ C X = 0 x1 + 0 x2 + 0 x3 + 1 x4 + 1 x5 + 1 x6 + 1 x7 + 0 x8 + 1 x9 U X = {x4, x5, x6, x7, x9} U/R1 = {{x1, x2,··· , x6},{x7, x8, x9}} U/R2 = {{x1, x2, x3, x4},{x5, x6, x7},{x8, x9}} U 例1 设一个信息系统 ， ， 是 上的一个目标概念，即 ， 和 是 上的两个知识空间。 QSD(U/R1 ,U/R2) = 1 |U| ∑2 i=1 ∑3 j=1 pi ⊕qj |U| pi ∩qj = 2 9 ×4+ 5 9 ×2+ 4 9 ×1+ 1 9 ×2 9 = 0.296 QSDQSD QSD RASD QSD RASD 通过多对多匹配计算， 实现了两个知识 空间之间的差异性度量。但是，对于粗糙集来 说，当前知识距离的工作 (包括 ) 仅仅是从知 识空间的角度出发，反映的是两个知识空间划分 差异性，并没有考虑它们对目标概念刻画时的差 异性，有可能导致同一目标概念在两个不同粒度 的知识空间中具有相同的不确定性度量结果，从 而无法区分它们对目标概念的近似能力。为了解 决以上问题，本文提出了一种粗糙近似空间知识 距离 (rough approximation space distance, RASD)。 如图 3 所示，为 和 两种类型的知识距 离的示意图，与 相比， 可以体现两个知 识空间对目标概念刻画能力的差异性。 U/R1 U/R2 QSD (U/R1, U/R2) U/R1 (X) U/R2 (X) RASD (U/R1, U/R2) 图 3 两种类型的知识距离 Fig. 3 Two types of knowledge distance 2.1 粗糙近似空间距离 为了反映不同知识空间对目标概念的刻画能 力的差异性，本文基于知识距离框架进一步提出 了一种粗糙近似空间距离。 U X U Ae Be U A B 定义 7 模糊集合距离。假设 为一个非空 有限论域， 是 上的一个目标概念。如果 、 是 上的两个有限集合， 和 之间的距离为 δ(Ae,Be) = ∑ x∈Ae∪Be µ(x)− ∑ x∈Ae∩Be µ(x) |U| X U δ(Ae,Be) 由定义 7 可知，无论 为 上的一个清晰集 还是模糊集， 都可以刻画两个集合 (清晰集 或模糊集) 之间的距离。 U δ(·,·) U 定理 2 假设 为一个非空有限论域， 是 上的一个距离度量。 第 1 期 杨洁，等：基于知识距离的粗糙粒结构的评价模型 ·169·
·170· 智能系统学报 第15卷 证明假设A、B、C是U上的3个有限集合。 理2可知，6(，)是U上的距离度量。通过定理1 显然，6(，)满足正定性和对称性。通过文献[36] 可知，类似于EMD,RASD也是U上的距离度量。 可知： 由定义7和定义8可知，无论X为U上的 (∑()-∑()+（∑μ）-∑(》≥ 个清晰集还是模糊集，RASD都可以刻画两个知 IEAUB xEBUC 识空间之间的对X近似刻画能力的差异，即 (∑(-∑ RASD不仅适用于经典粗糙集，同样适用于粗糙 REAnC 模糊集。由于继承了EMD的优点，RASD能够有 显然 效和直观的刻画不同知识空间对目标概念的描述 -县 ∑μ)-∑μ 能力的差异性。 KEAnB xEBnC I01 IUI 例3（续例1） RASD(U/R(X),U/R2(X)= ∑)-∑ EAUC EAnC ∑∑si IUI i=ljl 10 = 则 6A,B)+6B,C≥6A,⊙ 2 2 3. 1 ×4+号×2+g×1+g×2 因此，6(，)是U上的一个距离度量。 =0.209 9 例2假设U=,,,,X=03+ 2.2粗糙粒结构的结构特征 05,07+09+08+05+02是U上的一个目标 定理4设一个信息系统S=(U,CUD,V,f, 55x45x6 R、R2、RSC,X是U上的一个目标概念。如果R1S 概念，A=,,,x,B={x,6,,则A=03+ R2 C R3,RASD(U/R(X).U/R;(X))=RASD(U/R (X). 05+02+09.B-09+08+05+2∑=39. U/R2(X))+RASD(U/R2(X).U/R3(X)). 十 x456 证明假设U={x1,x2,…,xn}是一个非空论域， ∑)=0.7+0.9=1.6，∑)=0.3+0.5+0.7+0.9+ U/R={p1,P2,,P,U/R2={q1,92,…,9m}和U1R= 0.8+0.5=3.7,因此，64B-3.7-16=0.3。 {,2,…,}是U上的3个知识空间。由于R≤ 7 定义8设一个信息系统S=(U,CUD,Vf), R2SR,故UIR≤U/R2≤U/R。为了简单化，本文假 R,RSC,X是U上的一个目标概念。U/R1= 设仅有一个信息粒p1(p1∈U/R)细分为两个更细 {p1,P2,…,Pl和U/R2={q,92,…,9m}是U上的两个 的信息粒q1、92(q1,92∈U/R),仅有一个信息粒1 知识空间。对于描述X、U/R和U/R2的知识距离 细分为两个更细的信息粒”，2（其他复杂情形均 定义为 可转化为这种情形，这里不再重复)。则P1=qU 92,p2=q3,…,Pn=qm(m=1+1),q1=nUn,92=r3, ∑ …,9n=r(s=m+1),那么U/R2={q1,q2,pP2,pP3,…,pl RASD(U/R(X),U/R2(X))= (7) 以及U/R3={,n,92,,…,qml}。通过公式，可得： 式中：6=6p.q),p和9分别代表p:和q对应 RASD(U/R(X).U/R(X))= 的模糊集；f=lp:ngo (∑μ-∑μx∑μ() 由于对同一论域进行划分的不同知识空间 I01 的对象数是相同的.即∑pl=∑l=M,式() RASD(U/R(X).U/R3(X))= 1 符合约束条件式(4)。同样，式(7)符合约束条件 (∑μ)-∑μ)∑μ() 式(1(3). 22 1= IUI 定理3假设U为一个非空有限论域，RASD 由于p1=q1Uq2和qh=nU2,故4，=4，+4 是U上的一个距离度量。 和，=4+o 证明假设U/R1={p1,P2,…,P}和U/R2= RASD(U/R(X).U/R2(X))= q1,q2,…,9m}是两个U上的知识空间。对于同 个论域而言，式()中pl=al=u。由定 1nt)-(G+) IUI 101 =1
Ae Be Ce U δ(·,·) 证明 假设 、 、 是 上的 3 个有限集合。 显然， 满足正定性和对称性。通过文献 [36] 可知： ( ∑ x∈Ae∪Be µ(x)− ∑ x∈Ae∩Be µ(x))+( ∑ x∈Be∪Ce µ(x)− ∑ x∈Be∩Ce µ(x)) ⩾ ( ∑ x∈Ae∪Ce µ(x)− ∑ x∈Ae∩Ce µ(x)) 显然 ∑ x∈Ae∪Be µ(x)− ∑ x∈Ae∩Be µ(x) |U| + ∑ x∈Be∪Ce µ(x)− ∑ x∈Be∩Ce µ(x) |U| ⩾ ∑ x∈Ae∪Ce µ(x)− ∑ x∈Ae∩Ce µ(x) |U| 则 δ(Ae,Be)+δ(Be,Ce) ⩾ δ(Ae,Ce) 因此， δ(·,·) 是 U 上的一个距离度量。 U = {x1, x2, x3, x4, x5, x6, x7},X = 0.3 x1 + 0.5 x2 + 0.7 x3 + 0.9 x4 + 0.8 x5 + 0.5 x6 + 0.2 x7 U A = {x1, x2, x3, x4} B = {x4, x5, x6, x7} Ae= 0.3 x1 + 0.5 x2 + 0.7 x3 + 0.9 x4 Be= 0.9 x4 + 0.8 x5 + 0.5 x6 + 0.2 x7 ∑ x∈X µ(x) = 3.9 ∑ x∈Ae∩Be µ(x)=0.7+0.9=1.6 ∑ x∈Ae∪Be µ(x) = 0.3+ 0.5+0.7+0.9+ 0.8+0.5 = 3.7 δ(Ae,Be) = 3.7−1.6 7 = 0.3 例 2 假 设 是 上的一个目标 概念， ， ，则 ， ， ， ，因此， 。 S = (U,C ∪ D,V, f) R1,R2 ⊆ C X U U/R1 = {p1, p2,··· , pl} U/R2 = {q1,q2,··· ,qm} U X U/R1 U/R2 定义 8 设一个信息系统 ， ， 是 上的一个目标概念。 和 是 上的两个 知识空间。对于描述 、 和 的知识距离 定义为 RASD(U/R1(X),U/R2(X)) = ∑l i=1 ∑m j=1 δi j fi j |U| (7) δi j = δ(epi ,qej) epi qej pi qj fi j = pi ∩qj 式中： ， 和 分别代表 和 对应 的模糊集； 。 ∑l i=1 |pi | = ∑m j=1 qj = |U| 由于对同一论域进行划分的不同知识空间 的对象数是相同的，即 ，式 (7) 符合约束条件式 (4)。同样，式 (7) 符合约束条件 式 (1)~(3)。 U RASD U 定理 3 假设 为一个非空有限论域， 是 上的一个距离度量。 U/R1 = {p1, p2,··· , pl} U/R2 = {q1,q2,··· ,qm} U ∑l i=1 |pi | = ∑m j=1 qj = |U| 证 明 假设 和 是两个 上的知识空间。对于同一 个论域而言，式 (7) 中 。由定 δ(·,·) U U 理 2 可知， 是 上的距离度量。通过定理 1 可知，类似于 EMD，RASD 也是 上的距离度量。 X U X 由定义 7 和定义 8 可知，无论 为 上的一 个清晰集还是模糊集，RASD 都可以刻画两个知 识空间之间的对 近似刻画能力的差异， 即 RASD 不仅适用于经典粗糙集，同样适用于粗糙 模糊集。由于继承了 EMD 的优点，RASD 能够有 效和直观的刻画不同知识空间对目标概念的描述 能力的差异性。 例 3(续例 1) RASD(U/R1(X),U/R2(X)) = ∑2 i=1 ∑3 j=1 δi j fi j |U| = 2 9 ×4+ 2 9 ×2+ 3 9 ×1+ 1 9 ×2 9 = 0.209 2.2 粗糙粒结构的结构特征 S = (U,C ∪ D,V, f) R1 R2 R3 ⊆ C X U R1 ⊆ R2 ⊆ R3 RASD(U/R1(X),U/R3(X)) = RASD(U/R1(X), U/R2(X))+RASD(U/R2(X),U/R3(X)) 定理 4 设一个信息系统 ， 、 、 ， 是 上的一个目标概念。如果 ，则 。 U = {x1, x2,··· , xn} U/R1 = {p1, p2,··· , pl} U/R2 = {q1,q2,··· ,qm} U/R3 = {r1,r2,··· ,rs} U R1 ⊆ R2 ⊆ R3 U/R1≺U/R2≺U/R3 p1(p1 ∈ U/R1) q1 q2(q1,q2 ∈ U/R2) q1 r1,r2 p1 = q1∪ q2 p2 = q3 pn = qm (m = l+1) q1 = r1 ∪r2 q2 = r3 qn = rs(s = m+1) U/R2 = {q1,q2, p2, p3,··· , pl} U/R3 = {r1,r2,q2,q3,··· ,ql} 证明 假设 是一个非空论域， ， 和 是 上的 3 个知识空间。由于 ，故 。为了简单化，本文假 设仅有一个信息粒 细分为两个更细 的信息粒 、 ，仅有一个信息粒 细分为两个更细的信息粒 (其他复杂情形均 可转化为这种情形，这里不再重复)。则 ， ， … , ， ， ， …, ，那么 以及 。通过公式，可得： RASD(U/R1(X),U/R2(X)) = 1 |U| ∑l i=1 ∑m j=1 ( ∑ x∈pei µ(x)− ∑ x∈qej µ(x)) ∑ x∈qej µ(x) |U| RASD(U/R1(X),U/R3(X)) = 1 |U| ∑l i=1 ∑s k=1 ( ∑ x∈pei µ(x)− ∑ x∈rek µ(x))∑ x∈rek µ(x) |U| p1 = q1 ∪q2 q1 = r1 ∪r2 µp1 = µq1 +µq2 µq1 = µr1 +µr2 由于 和 ，故 和 。 RASD(U/R1(X),U/R2(X)) = 1 |U| · µp1 ( µq1 +µq2 ) − ( µ 2 q1 +µ 2 q2 ) |U| ·170· 智 能 系 统 学 报 第 15 卷