【人工智能】基于知识距离的粗糙粒结构的评价模型.pdf_大学文库

第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上的一个距离度量

·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 卷

第1期杨洁，等：基于知识距离的粗糙粒结构的评价模型 ·171· RASD(U/R(X).U/R3(X))= RASD(U/R(X).U/R,(X))= 1 4n++,)-(++） RASD(U/R2(X),)-RASD(U/R(X),) IUI U1 定理5设一个信息系统S=(U,CUD,Vf), 1 2(0n2+4r+4山 RC,X是U上的一个目标概念，RASD(U/R,(X),o) I01 IUI 是一个粒度度量。同理，RASD(U/R(X),U/R3(X)= 证明1)由定理3可知，RASD(U/R(X,d)≥0； 14-4)4+,-4Ae= 101 2)假设R2SC,当R1=R2时，可得： IUI 1(gn+g4)-(+) RASD(U/R1(X),)=RASD(U/R2(X).@) I0I 101 3)由推论1可知，如果RSR2,那么RASD 由于p1=q1Uq2和q1=nUn,故4=4，+4e (U/R2(X),)≤RASD(U/R(X),w)。和=4n+,则定理6设一个信息系统S=(U,CUD,Vf), RASD(U/R(X),U/R2(X))+RASD(U/R2(X).U/R3(X))= R1SC,X是U上的一个目标概念，RASD(U/RX,) 12n4n+g4g) 是一个信息度量。证明1)由定理3可知，RASD(U/R1(X),σ)≥0； 12un4ntnn+L=Hn） 2)假设R2C,当R1=R2时，可得： RASD(U/R(X),U/R3(X)) RASD(U/R(X),o)=RASD(U/R2(X),) 由定理4可知，同一个粗糙粒结构中的两个 3)由推论1可知，如果RSR2,那么RASD 粗糙近似空间的不确定性差异等于它们之间的知 (U/R(X),T)≤RASD(U/R2(X),σ)。识距离。通过推论1和定理5可知，对于一个目标概例4设一个信息系统S=(U,CUD,Vf),U= 念，粗糙粒结构中的任意两个粗糙近似空间的 …w,R、R、RcC,X=04+0.60.80.9 RASD等于它们之间的粒度度量差异。通过推论 X1 X2 X3 X4 2和定理6可知，对于一个目标概念，粗糙粒结构 08,05,04+04+02是U上的一个目标概念中的任意两个粗糙近似空间的RASD等于它们之 5x6 U/R1={x,2,…,x6},,g,h,U/R2={x1,x2,,x4}, 间的信息度量差异。结合定理4，本文以粗糙粒 {,x6},{7,xg,gh,以及U/R3={x1,x2,x3,{x4}{x5,x6l, 结构中的ω为原点，可以将粗糙近似空间通过 {l,{xg,x》是U上的3个知识空间。 RASD映射到一维坐标上。 1.3 RASD(U/R(X).U/R(X))=5 5×1.3 10.6 3粗糙粒结构的评价模型 9 81 在粗糙粒结构中，对不确定性问题进行求解类似地时，通常希望在约束条件下可以利用尽可能少的 RASD(U/R:(X).U/R(X)-59 81 知识空间使不确定性降低最大化。为了简单化， RASD(U/R(X),U/R3(X))= 16.5 本文仅考虑约束条件为属性代价时的情形，通过 81 第2节定义的粗糙知识距离以及在粗糙粒结构上因此得出的结论，提出了一种粗糙粒结构的评价模型。 RASD(U/R1.U/R3)= 定义9知识距离序列。假设一个信息系统 RASD(U/R(X).U/R2(X))+ RASD(U/R:(X).U/R,(X)=16.5 S=(U,CUD,V,f),其中RsC和X≤U,GS=(KS 81 KS2,…,KS)是一个由专个知识空间组成的粗糙在本文中，将一个信息系统中的最粗知识空粒结构，其中KS=U/R,i=1,2,…,5。R为一个间和最细知识空间分别表示为σ和w。通过定条件属性集，RC…CR2cR1SC,知识距离序列可理4，本文可得到以下推论。表示为LGs=(△1，△2，…，△-1，其中△=RASD(U/R,(X), 推论1设一个信息系统S=(U,CUD,Vf月， U/R+1(X),ie[1,5-1b R,R2SC,X是U上的一个目标概念。如果R1SR2,则：基于定义9，本文提出了一种属性约束条件 RASD(U/R(X).U/R2(X))= 下的粗糙粒结构的评价模型，首先，本文在定义 RASD(U/R1(X),@)-RASD(U/R2(X),@) 10中定义了一个评价参数A。推论2设一个信息系统S=(U,CUD,Vf, 定义10评价参数。假设一个信息系统S= R,R2二C,X是U上的一个目标概念。如果R1二R2,则： (U,CUD,Vf),其中RC和X∈U,GS=(KS,KS2,…

·172· 智能系统学报第15卷 KS)是一个由专个知识空间组成的粗糙粒结构，因此，>&2和IBND(X)I>BND2(XI。由于 LGs=(△1，△2，…，△-1)，则 GS1在约束条件下只有一个知识空间可利用，无法进一步降低降不确定性，不能进行渐近式计算，而GS2在约束条件下利用知识空间进一步降低了 (8) 不确定性，所以在约束条件TC=10下应该选择其中，粗糙粒结构GS2进行问题求解。少=mk GS,中的KS1、KS2和GS2中的KS、KS3、KS属性代价小于TC=20,那么： s.t. TCks.≤TCue 10 5.18 通过式(8)可知，1越大，说明对应的粗糙粒 81-10 结构就越好，即该粒结构能够在约束条件下利用 =8别=8=3- 3-1 尽可能少的知识空间实现不确定性的降低最大化。此时，BND(X)={x3,x4,·,xg},BND2(X)={x, 如图4所示，为整个粗糙粒结构评价模型的 X3,…,6}o 流程图。首先，通过粗糙近似空间距离计算出不因此，d1BND2(X儿，虽然GS2 同的粗糙粒结构对应的知识距离序列，然后，通在约束条件下利用了更多的知识空间个数，但是过式（⑧）并结合不同的约束条件计算得到对应的总体上却更大程度的降低了不确定性，所以在约评价参数，从而实现不同约束条件下的粗糙粒结束条件TCur=20下应该选择粗糙粒结构GS2进构的评价和选择。行问题求解。同理，GS,中的KS、KS2、KS和GS2中的KS、 GS: 000000-00 RASD 公式(8) KS、KS、KS属性代价小于TCur=30,那么： GS. 6=++。1 1025 5188 =8+835 4-1 243 图4粗糙粒结构的评价模型此时，BND(X={x,x4h,BND2(X)={,2,xlo Fig.4 Evaluation model of rough granular structure 因此，d>2和BND(X)I2和BND(X)<BND2(X。由于 =高，》 S=,,月 GS,在相同的知识空间个数上降低了更多得不确定性，所以在约束条件TCr=40下应该选择粗糙图={，偶》 s=任马，红粒结构GS,进行问题求解。 =}..》S=,. 4结束语图5两个粗糙粒结构中的知识空间 Fig.5 Knowledge spaces in two rough granular structures 不同的粒化机制可以形成不同的粒结构，在通过式(7)可计算出GS,和GS2的知识距离粗糙集的序贯三支决策模型中，通过不同的属性序列分别为L-侣品动)和（原贤》集添加顺序可形成不同的粗糙粒结构。如何建立对这些粗糙粒结构的评价方法是本文的主要研究结合已知条件，由式(8)可得，GS,中的KS和GS,中内容。在前期工作的基础上，提出了一种粗糙近的KS、KS号属性代价小于TCr=10,那么，d1=0, 似空间距离，并利用该距离研究了粗糙粒结构的 &=8,此时，BND)={d,,,w,BND(X= 结构特征，得到了粗糙粒结构中的两个知识空间 X1,X2,·,X8}0 的不确定性差异等于它们之间知识距离的结论

KSξ ) ξ LGS = (∆1,∆2,··· ,∆ξ−1) 是一个由个知识空间组成的粗糙粒结构，，则 λ = ∑ ψ−1 i=1 ∆i ψ (8) 其中， ψ = max 1⩽k⩽ξ k s.t. TCKSk ⩽ TCuser 通过式 (8) 可知， λ 越大，说明对应的粗糙粒结构就越好，即该粒结构能够在约束条件下利用尽可能少的知识空间实现不确定性的降低最大化。如图 4 所示，为整个粗糙粒结构评价模型的流程图。首先，通过粗糙近似空间距离计算出不同的粗糙粒结构对应的知识距离序列，然后，通过式 (8) 并结合不同的约束条件计算得到对应的评价参数，从而实现不同约束条件下的粗糙粒结构的评价和选择。 GS1 RASD GS2 公式 (8) λ2 λ1 TCuser 图 4 粗糙粒结构的评价模型 Fig. 4 Evaluation model of rough granular structure (U, C ∪ D, V, f) X = 0 x1 + 0 x2 + 1 x3 + 0 x4 + 1 x5 + 1 x6 + 1 x7 + 1 x8 + 0 x9 U GS1 = (KS1 1 ,KS1 2 , KS1 3 ,KS1 4 ) GS2 = (KS2 1 ,KS2 2 ,KS2 3 ,KS2 4 ) TC1 = (2,13,27,31) TC2 =(2,7,22,28) TCuser = (10,20,30,40) 例 5 如图 5 所示，设一个信息系统 S = ，是上的一个目标概念，和是两个粗糙粒结构，它们的属性代价序列分别为和，其中属性代价序列为。 GS1 GS2 LGS1 = ( 10 81 , 25 81 , 3 81) LGS2 = ( 5 81 , 18 81 , 8 81) GS1 KS1 1 GS2 KS2 1 KS2 2 TCuser = 10 λ1 = 0 λ2 = 5 81 BND1(X) = {x1, x2,··· , x9} BND2(X) = {x1, x2,··· , x8} 通过式 (7) 可计算出和的知识距离序列分别为和，结合已知条件，由式 (8) 可得，中的和中的、属性代价小于，那么，，，此时，，。 λ1 > λ2 |BND1(X)| > |BND2(X)| GS1 GS2 TCuser = 10 GS2 因此，和。由于在约束条件下只有一个知识空间可利用，无法进一步降低降不确定性，不能进行渐近式计算，而在约束条件下利用知识空间进一步降低了不确定性，所以在约束条件下应该选择粗糙粒结构进行问题求解。 GS1 KS1 1 KS1 2 GS2 KS2 1 KS2 2 KS2 3 TCuser = 20 中的、和中的、、属性代价小于，那么： λ1 = 10 81 2−1 = 10 81 , λ2 = 5 81 + 18 81 3−1 = 23 162 BND1(X) = {x3, x4,··· , x9} BND2(X) = {x1, x2,··· , x6} 此时，，。 λ1 |BND2(X)| GS2 TCuser = 20 GS2 因此，和，虽然在约束条件下利用了更多的知识空间个数，但是总体上却更大程度的降低了不确定性，所以在约束条件下应该选择粗糙粒结构进行问题求解。 GS1 KS1 1 KS1 2 KS1 3 GS2 KS2 1 KS2 2 KS2 3 KS2 4 TCuser = 30 同理，中的、、和中的、、、属性代价小于，那么： λ1 = 10 81 + 25 81 3−1 = 35 162 , λ2 = 5 81 + 18 81 + 8 81 4−1 = 31 243 此时， BND1(X) = {x3, x4}，BND2(X) = {x1, x2,x3, x4}。 λ1 > λ2 |BND1(X)| λ2 |BND1(X)| < |BND2(X)| GS1 TCuser = 40 GS1 因此，和。由于在相同的知识空间个数上降低了更多得不确定性，所以在约束条件下应该选择粗糙粒结构进行问题求解。 4 结束语不同的粒化机制可以形成不同的粒结构，在粗糙集的序贯三支决策模型中，通过不同的属性集添加顺序可形成不同的粗糙粒结构。如何建立对这些粗糙粒结构的评价方法是本文的主要研究内容。在前期工作的基础上，提出了一种粗糙近似空间距离，并利用该距离研究了粗糙粒结构的结构特征，得到了粗糙粒结构中的两个知识空间的不确定性差异等于它们之间知识距离的结论。图 5 两个粗糙粒结构中的知识空间 Fig. 5 Knowledge spaces in two rough granular structures ·172· 智能系统学报第 15 卷

第1期杨洁，等：基于知识距离的粗糙粒结构的评价模型 ·173· 利用该结论，本文建立了一种在属性代价约束条机学报，2015(8)：1497-1517. 件下的粗糙粒结构的评价模型，解决了在不同约 XU Ji,WANG Guoyin,YU Hong.Review of big data 束条件下评价并选择不同粗糙粒结构的问题。由 processing based on granular computing[J].Chinese 于本文采用的是基于EMD的知识距离框架，因 journal of computers,2015(8):1497-1517 此，本文的方法具有扩展性，可以针对不同类型 [12]YAO Yiyu.Three-way decisions with probabilistic rough 的粒结构设计评价模型，例如，对不同层次聚类 sets[J].Information sciences,2010,180(3):341-353. 算法、多尺度图像分割算法以及多粒度社区发现 [13]QIAN Yuhua,LIANG Jiye,YAO Yiyu,et al.MGRS:a 算法的评价和选择。但是，本文的工作还处于初 multi-granulation rough set[]].Information sciences, 步阶段，仅研究了如何评价粗糙粒结构，并没有 2010,1806:949-970. 考虑粗糙粒结构的构建问题，并且只考虑了属性 [14]QIAN Yuhua,LIANG Jiye,DANG Chuangyin.Incom- 代价为约束条件，评价模型的目标函数还有待进 plete multigranulation rough set[J].IEEE transactions on 一步改进，尤其如何根据不同的约束条件设计目 systems,man,and cybernetics-part A:systems and hu- 标函数是下一步工作的主要目标。 mans.2010,40(2):420-431. [15]QIAN Yuhua,CHENG Honghong,WANG Jieting,et al 参考文献： Grouping granular structures in human granulation intelli- [1]ZADEH L A.Toward a theory of fuzzy information granu- gence[J].Information sciences,2017,382-383:150-169. lation and its centrality in human reasoning and fuzzy lo- [16]张钹，张铃.问题求解理论及应用M.北京：清华大学 gic[J].Fuzzy sets and systems,1997,90(2):111-127 出版社，1990 [2]PEDRYCZ W.SKOWRON A.KREINOVICH V.Hand- [17]ZHANG Ling,ZHANG Bo.The structure analysis of book of granular computing[M].Chichester:John Wiley fuzzy sets[J].International journal of approximate reason- Sons.2008:719-740. ing,2005,40(1/2:92-108 [3]PEDRYCZ W.AL-HMOUZ R,MORFEQ A,et al.The [18]ZHANG Ling,ZHANG Bo.Fuzzy reasoning model un- design of free structure granular mappings:the use of the der quotient space structure[J].Information sciences, principle of justifiable granularity[J].IEEE transactions on 2005,173(4):353-364. cybernetics,2013,43(6):2105-2113 [19]WIERMAN M J.Measuring uncertainty in rough set the- [4]WANG Guoyin,YANG Jie,XU Ji.Granular computing: ory[J].International journal of general systems,1999, from granularity optimization to multi-granularity joint 28(4/5):283-297. problem solving[J].Granular computing,2017,2(3): [20]LIANG Jiye,CHIN K S,DANG Chuangyin,et al.A new 105-120 method for measuring uncertainty and fuzziness in rough [5]YAO Yiyu.Perspectives of granular computing[C]//Pro- set theory[J].International journal of general systems, ceedings of 2015 IEEE International Conference on Granu- 2002,31(4):331-342 lar Computing.Beijing,China,2005:85-90. [21]YAO Yiyu,ZHAO Liquan.A measurement theory view [6]ZADEH L A.Fuzzy sets[].Information and control,1965. on the granularity of partitions[J].Information sciences, 8(3):338-353 2012.213:1-13 [7]PAWLAK Z.Rough sets[J].International journal of com- [22]LAWVERE F W.Metric spaces,generalized logic,and puter&information sciences,1982,11(5):341-356 closed categories[J].Rendiconti del seminario matem- [8]张钹，张铃.问题求解理论及应用M北京：清华大学出 atico e fisico di milano,1973,43(1):135-166. 版社，1990. [23]RUBNER Y.GUIBAS L.TOMASI C.The earth mover's [9]李德毅，孟海军，史雪梅.隶属云和隶属云发生器几.计 distance,multi-dimensional scaling,and color-based im- 算机研究与发展，19956)：15-20. age retrieval[Cl/Proceedings of the ARPA Image Under- LI Deyi,MENG Haijun,SHI Xuemei.Membership clouds standing Workshop.1997:661-668. and membership cloud generators[J.Journal of computer [24]RUBNER Y.TOMASI C.GUIBAS L J.The earth research and development,1995(6):15-20. mover's distance as a metric for image retrieval[J].Inter- [10]苗夺谦，李德毅，姚一豫，等.不确定性与粒计算M北 national journal of computer vision,2000,40(2):99-121. 京：科学出版社，2011. [25]郭增晓，米据生.粗糙模糊集的模糊性度量J刀.模糊系 [11]徐计，王国胤，于洪.基于粒计算的大数据处理).计算统与数学，2005,19(4)：135-140

利用该结论，本文建立了一种在属性代价约束条件下的粗糙粒结构的评价模型，解决了在不同约束条件下评价并选择不同粗糙粒结构的问题。由于本文采用的是基于 EMD 的知识距离框架，因此，本文的方法具有扩展性，可以针对不同类型的粒结构设计评价模型，例如，对不同层次聚类算法、多尺度图像分割算法以及多粒度社区发现算法的评价和选择。但是，本文的工作还处于初步阶段，仅研究了如何评价粗糙粒结构，并没有考虑粗糙粒结构的构建问题，并且只考虑了属性代价为约束条件，评价模型的目标函数还有待进一步改进，尤其如何根据不同的约束条件设计目标函数是下一步工作的主要目标。参考文献： 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. [1] PEDRYCZ W, SKOWRON A, KREINOVICH V. Handbook of granular computing[M]. Chichester: John Wiley & Sons, 2008: 719−740. [2] 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. [3] 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. [4] YAO Yiyu. Perspectives of granular computing[C]//Proceedings of 2015 IEEE International Conference on Granular Computing. Beijing, China, 2005: 85−90. [5] ZADEH L A. Fuzzy sets[J]. Information and control, 1965, 8(3): 338–353. [6] PAWLAK Z. Rough sets[J]. International journal of computer & information sciences, 1982, 11(5): 341–356. [7] 张钹, 张铃. 问题求解理论及应用 [M]. 北京: 清华大学出版社, 1990. [8] 李德毅, 孟海军, 史雪梅. 隶属云和隶属云发生器 [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. [9] 苗夺谦, 李德毅, 姚一豫, 等. 不确定性与粒计算 [M]. 北京: 科学出版社, 2011. [10] [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. YAO Yiyu. Three-way decisions with probabilistic rough sets[J]. Information sciences, 2010, 180(3): 341–353. [12] QIAN Yuhua, LIANG Jiye, YAO Yiyu, et al. MGRS: a multi-granulation rough set[J]. Information sciences, 2010, 180(6): 949–970. [13] 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. [14] QIAN Yuhua, CHENG Honghong, WANG Jieting, et al. Grouping granular structures in human granulation intelligence[J]. Information sciences, 2017, 382-383: 150–169. [15] 张钹, 张铃. 问题求解理论及应用 [M]. 北京: 清华大学出版社, 1990. [16] ZHANG Ling, ZHANG Bo. The structure analysis of fuzzy sets[J]. International journal of approximate reasoning, 2005, 40(1/2): 92–108. [17] ZHANG Ling, ZHANG Bo. Fuzzy reasoning model under quotient space structure[J]. Information sciences, 2005, 173(4): 353–364. [18] WIERMAN M J. Measuring uncertainty in rough set theory[J]. International journal of general systems, 1999, 28(4/5): 283–297. [19] 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. [20] YAO Yiyu, ZHAO Liquan. A measurement theory view on the granularity of partitions[J]. Information sciences, 2012, 213: 1–13. [21] LAWVERE F W. Metric spaces, generalized logic, and closed categories[J]. Rendiconti del seminario matematico e fisico di milano, 1973, 43(1): 135–166. [22] 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. [23] 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. [24] 郭增晓, 米据生. 粗糙模糊集的模糊性度量 [J]. 模糊系统与数学, 2005, 19(4): 135–140. [25] 第 1 期杨洁，等：基于知识距离的粗糙粒结构的评价模型 ·173·

·174· 智能系统学报第15卷 GUO Zengxiao,MI Jusheng.An uncertainty measure in tems,2013,42(7):754-773 rough fuzzy sets[J].Fuzzy systems and mathematics, [35]YANG Jie,WANG Guoyin,ZHANG Qinghua.Know- 2005,19(4):135-140. ledge distance measure in multigranulation spaces of [26]QIN Huani,LUO Darong.New uncertainty measure of fuzzy equivalence relations[J].Information sciences, rough fuzzy sets and entropy weight method for fuzzy-tar- 2018.448-449:18-35. get decision-making tables[J].Journal of applied mathem- [36]YANG Jie,WANG Guoyin,LI Xukun.Multi-granularity atics..2014,2014:487036 similarity measure of cloud concept[C]//International [27]HU J,PEDRYCZ W,WANG G.A roughness measure of Joint Conference on Rough Sets.Santiago,Chile,2016: fuzzy sets from the perspective of distance[J].Internation- 318-330 al journal of general systems,2016,45(3):352-367. [28]SUN Bingzhen,MA Weimin.Uncertainty measure for 作者简介： general relation-based rough fuzzy set[J].Kybernetes, 杨洁，副教授，博士，主要研究方向为粒计算、数据挖掘、粗糙集。参与 2013.42(6:979-992. 国家自然科学基金项目2项，授权国 [29]DAI Jianhua,WANG Wentao,XU Qing.An uncertainty 家发明专利5项。发表学术论文20 measure for incomplete decision tables and its applica- 余篇。 tions[J].IEEE transactions on cybernetics,2013,43(4): 1277-1289. [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,192)263-264. 息处理。主持国家自然科学基金项目 [31]QIAN Yuhau,LI Yebin,LIANG Jiye,et al.Fuzzy granu- 10余项。入选“重庆高校创新团队” lar structure distance[J].IEEE transactions on fuzzy sys- “重庆市首席专家工作室”和“国家级 tems,2015,23(6):2245-2259. 教学团队”：获国家级教学成果二等奖、重庆市自然科学一等 [32]LIANG Jiye,LI Ru,QIAN Yuhau.Distance:a more com- 奖、重庆市科技进步一等奖、重庆市教学成果一等奖和吴文 prehensible perspective for measures in rough set 俊人工智能科学技术奖科技进步一等奖等多项国家级/省部 theory[J].Knowledge-based systems,2012,27:126-136. 级教学和科技成果奖励。出版著作10余部，发表学术论文 300余篇。 [33]YANG Xibei,QIAN Yuhua,YANG Jingyu.On charac- terizing hierarchies of granulation structures via dis- 张清华，教授，博士生导师，博士， tances[J].Fundamenta informaticae,2013,123(3): 主要研究方向为粗糙集、模糊集、粒计 365-380 算、三支决策。主持国家自然科学基金项目2项。发表学术论文40余篇。 [34]YANG Xibei,SONG Xiaoning,SHE Yanhong,et al. Hierarchy on multigranulation structures:a knowledge distance approach[J].International journal of general sys-

GUO Zengxiao, MI Jusheng. An uncertainty measure in rough fuzzy sets[J]. Fuzzy systems and mathematics, 2005, 19(4): 135–140. 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. [26] 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. [27] SUN Bingzhen, MA Weimin. Uncertainty measure for general relation-based rough fuzzy set[J]. Kybernetes, 2013, 42(6): 979–992. [28] 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. [29] 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. [30] QIAN Yuhau, LI Yebin, LIANG Jiye, et al. Fuzzy granular structure distance[J]. IEEE transactions on fuzzy systems, 2015, 23(6): 2245–2259. [31] 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. [32] YANG Xibei, QIAN Yuhua, YANG Jingyu. On characterizing hierarchies of granulation structures via distances[J]. Fundamenta informaticae, 2013, 123(3): 365–380. [33] YANG Xibei, SONG Xiaoning, SHE Yanhong, et al. Hierarchy on multigranulation structures: a knowledge distance approach[J]. International journal of general sys- [34] tems, 2013, 42(7): 754–773. YANG Jie, WANG Guoyin, ZHANG Qinghua. Knowledge distance measure in multigranulation spaces of fuzzy equivalence relations[J]. Information sciences, 2018, 448-449: 18–35. [35] 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. [36] 作者简介：杨洁，副教授，博士，主要研究方向为粒计算、数据挖掘、粗糙集。参与国家自然科学基金项目 2 项，授权国家发明专利 5 项。发表学术论文 20 余篇。王国胤，教授，博士生导师，博士，重庆邮电大学研究生院院长、人工智能学院院长，主要研究方向为粗糙集、粒计算、认知计算、数据挖掘、智能信息处理。主持国家自然科学基金项目 10 余项。入选“重庆高校创新团队”、 “重庆市首席专家工作室”和“国家级教学团队”；获国家级教学成果二等奖、重庆市自然科学一等奖、重庆市科技进步一等奖、重庆市教学成果一等奖和吴文俊人工智能科学技术奖科技进步一等奖等多项国家级/省部级教学和科技成果奖励。出版著作 10 余部，发表学术论文 300 余篇。张清华，教授，博士生导师，博士，主要研究方向为粗糙集、模糊集、粒计算、三支决策。主持国家自然科学基金项目 2 项。发表学术论文 40 余篇。 ·174· 智能系统学报第 15 卷