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