第4期 孙海霞：基于对象变化的邻域决策粗糙集动态更新算法 ·747· 融入决策粗糙集模型中，提出了邻域决策粗糙 1邻域决策粗糙集模型 集模型，该模型进一步提升了决策粗糙集的适用 范围。 粗糙集理论中，数据集表示为信息系统 然而现实环境下的数据不总是静止不变的， IS=(U,AT)的形式，其中U为信息系统的对象集， 而是时刻处于动态更新之中，为了提高粗糙集模 称为论域。AT称为信息系统的属性集，若属性集 型在动态数据下的处理效率，学者们对其提出了 AT可分为条件属性集C和决策属性集D,即 多种增量式的模型和算法。在决策粗糙集等 AT=CUD,那么该信息系统又称为决策信息系 统。对于x∈U和Ya∈AT,a(x)表示对象x在属 模型中，学者们同样提出了多种增量式更新算 性a下的属性值。当条件属性集C中的每个属性 法。例如，Zhang等针对属性值动态变化情形 都为数值型属性时，此信息系统又称之为邻域型 提出了相应的增量式更新算法；针对流计算环 信息系统。 境，Xu等提出了对象在线增加和减少时的增 Yao等2】提出的决策粗糙集仅应用于离 量式更新算法；Chen等a利用集合更新的方法设 散型的信息系统，L等将邻域关系引人传统的决 计出了决策粗糙集的增量式更新算法；赵小龙 策粗糙集模型中，提出了邻域决策粗糙集。 等针对数值型信息系统，研究了邻域粒化条件 定义10设邻域型信息系统IS=(U,AT),对 嫡随对象增加和减少时的增量式更新，并进一步 于属性集A二AT确定的邻域关系定义为 地提出了对应的增量式属性约简算法：杨臻等⑧研 Ng={(x,y)∈U×Ul△a(x,y)≤6} 究了混合型信息系统下对象变化时概率的增量式 式中：6称为邻域半径，是一个非负常数；△(x,y) 更新，并进一步地提出了变精度粗糙集模型的增 表示对象x与对象y之间的闵可夫斯基距离，定 量式更新；Luo等9通过矩阵方法构造出了决策 义为 粗糙集的增量式更新算法。然而所提出的这些增 1/ 量式更新算法仅局限于离散数据环境下的决策粗 △A(,y a(x)-a(y) 糙集模型，针对邻域型的决策粗糙集还未有相关 给定邻域信息系统的邻域关系，可以进一步 研究。 得到每个对象在该邻域关系下的邻域类。 论域中对象的增加和减少是信息系统最为常 定义20设邻域型信息系统IS=(U,AT),属 见的一种变化形式，本文将针对这类问题进行邻 性集ACAT确定的邻域关系为N,邻域半径为 域决策粗糙集的增量式更新研究。邻域决策粗糙 6。那么对于x∈U在邻域关系W下的邻域类定 集通过邻域关系来对数值型数据进行信息粒化， 义为 而对其进行增量式计算时必然涉及邻域类的更新 6a(x)={y∈UI(x,y)∈N} 计算，邻域关系不同于传统的等价关系和容差关 可以看出，对象x的邻域类表示与x相近对 系，其增量式计算的复杂程度要更高。在文献[18] 象的集合，其中6体现了相近的程度。基于邻域 中，杨臻等通过单个对象逐步迭代的方式去处理 的思想，Li等0提出了邻域决策粗糙集。 混合型信息系统变精度粗糙集模型的增量式更 在邻域决策粗糙集中，给定状态集2={XX, 新，使得问题的处理方式简便高效。由于决策粗 其中X和X分别表示对象x隶属于X和X的两 糙集与变精度粗糙集有一定的相似性，因此本文 种情形，那么对象x隶属于X的程度可通过概率 将借鉴文献[18]中关于变精度粗糙集模型的增量 PX》=Kn6来表示，则对象x隶属于x的 式更新研究思路与方法，构造出邻域决策粗糙集 6(x)1 程度可表示为PX6(x)=1-PXI6(x)。给定对象 的增量式更新模型。文中首先分别研究论域中增 x划分入X和X时的3种动作T={ap,a,aw,其 加和减少一个对象时，近似集与邻域类之间概率 中ap、as和aw分别表示划分入类别的正区域、边 的变化规律，然后根据这种规律来构造单个对象 界域和负区域。这里令AP(∈{P,B,W)分别表示 变化时模型上下近似集的增量式更新，最后在单 对象x实际属于X时采取ap、as和aw动作时所 个对象变化的基础上，通过逐步迭代的方式设计 产生的决策代价，w(*∈(PB,W)分别表示对象x 了对象批量变化时的增量式更新算法。实验分析 实际属于X时采取ap、as和aw动作时所产生的 表明，所提出的算法具有较高的增量式更新性 决策代价。因此对于对象x进行不同决策动作时 能，适用于动态数据环境下邻域决策粗糙集模型 所产生的的代价为： 的动态更新。 1)Rp=R(apl6(x)=App·P(XI6x)+APw·PXox)融入决策粗糙集模型中，提出了邻域决策粗糙 集模型，该模型进一步提升了决策粗糙集的适用 范围。 然而现实环境下的数据不总是静止不变的， 而是时刻处于动态更新之中，为了提高粗糙集模 型在动态数据下的处理效率，学者们对其提出了 多种增量式的模型和算法[11-13]。在决策粗糙集等 模型中，学者们同样提出了多种增量式更新算 法。例如，Zhang 等 [14] 针对属性值动态变化情形 提出了相应的增量式更新算法；针对流计算环 境，Xu 等 [15] 提出了对象在线增加和减少时的增 量式更新算法；Chen 等 [16] 利用集合更新的方法设 计出了决策粗糙集的增量式更新算法；赵小龙 等 [17] 针对数值型信息系统，研究了邻域粒化条件 熵随对象增加和减少时的增量式更新，并进一步 地提出了对应的增量式属性约简算法；杨臻等[18] 研 究了混合型信息系统下对象变化时概率的增量式 更新，并进一步地提出了变精度粗糙集模型的增 量式更新；Luo 等 [19] 通过矩阵方法构造出了决策 粗糙集的增量式更新算法。然而所提出的这些增 量式更新算法仅局限于离散数据环境下的决策粗 糙集模型，针对邻域型的决策粗糙集还未有相关 研究。 论域中对象的增加和减少是信息系统最为常 见的一种变化形式，本文将针对这类问题进行邻 域决策粗糙集的增量式更新研究。邻域决策粗糙 集通过邻域关系来对数值型数据进行信息粒化[10] ， 而对其进行增量式计算时必然涉及邻域类的更新 计算，邻域关系不同于传统的等价关系和容差关 系，其增量式计算的复杂程度要更高。在文献 [18] 中，杨臻等通过单个对象逐步迭代的方式去处理 混合型信息系统变精度粗糙集模型的增量式更 新，使得问题的处理方式简便高效。由于决策粗 糙集与变精度粗糙集有一定的相似性，因此本文 将借鉴文献 [18] 中关于变精度粗糙集模型的增量 式更新研究思路与方法，构造出邻域决策粗糙集 的增量式更新模型。文中首先分别研究论域中增 加和减少一个对象时，近似集与邻域类之间概率 的变化规律，然后根据这种规律来构造单个对象 变化时模型上下近似集的增量式更新，最后在单 个对象变化的基础上，通过逐步迭代的方式设计 了对象批量变化时的增量式更新算法。实验分析 表明，所提出的算法具有较高的增量式更新性 能，适用于动态数据环境下邻域决策粗糙集模型 的动态更新。 1 邻域决策粗糙集模型 IS = (U,AT) U AT AT C D AT = C ∪ D ∀x ∈ U ∀a ∈ AT a(x) x a C 粗糙集理论中，数据集表示为信息系统 的形式，其中 为信息系统的对象集， 称为论域。 称为信息系统的属性集，若属性集 可分为条件属性集 和决策属性集 ，即 ，那么该信息系统又称为决策信息系 统。对于 和 ， 表示对象 在属 性 下的属性值。当条件属性集 中的每个属性 都为数值型属性时，此信息系统又称之为邻域型 信息系统。 Yao 等 [ 1 - 2 ] 提出的决策粗糙集仅应用于离 散型的信息系统，Li 等将邻域关系引入传统的决 策粗糙集模型中，提出了邻域决策粗糙集[10]。 IS = (U,AT) A ⊆ AT N δ A 定义 1 [10] 设邻域型信息系统 ，对 于属性集 确定的邻域关系 定义为 N δ A = {(x, y) ∈ U ×U |∆A(x, y) ⩽ δ } δ ∆A(x, y) x y 式中： 称为邻域半径，是一个非负常数； 表示对象 与对象 之间的闵可夫斯基距离，定 义为 ∆A(x, y) =   ∑ ∀a∈A |a(x)−a(y)| k   1/k 给定邻域信息系统的邻域关系，可以进一步 得到每个对象在该邻域关系下的邻域类。 IS = (U,AT) A ⊆ AT N δ A δ ∀x ∈ U N δ A 定义 2 [10] 设邻域型信息系统 ，属 性集 确定的邻域关系为 ，邻域半径为 。那么对于 在邻域关系 下的邻域类定 义为 δA(x) = {y ∈ U|(x, y) ∈ N δ A } x x δ 可以看出，对象 的邻域类表示与 相近对 象的集合，其中 体现了相近的程度。基于邻域 的思想，Li 等 [10] 提出了邻域决策粗糙集。 Ω = {X,X c } X X c x X X c x X P(X|δ(x)) = |X ∩δ(x)| |δ(x)| x X c P(X c |δ(x)) = 1− P(X|δ(x)) x X X c Γ = {aP,aB,aN} aP aB aN λ∗P(∗ ∈ {P,B,N}) x X aP aB aN λ∗N(∗ ∈ {P,B,N}) x X c aP aB aN x 在邻域决策粗糙集中，给定状态集 ， 其中 和 分别表示对象 隶属于 和 的两 种情形，那么对象 隶属于 的程度可通过概率 来表示，则对象 隶属于 的 程度可表示为 。给定对象 划分入 和 时的 3 种动作 ，其 中 、 和 分别表示划分入类别的正区域、边 界域和负区域。这里令 分别表示 对象 实际属于 时采取 、 和 动作时所 产生的决策代价， 分别表示对象 实际属于 时采取 、 和 动作时所产生的 决策代价。因此对于对象 进行不同决策动作时 所产生的的代价为： RP = R(aP|δ(x))= λPP · P(X|δ(x))+λPN · P(X c 1) |δ(x)) ; 第 4 期 孙海霞：基于对象变化的邻域决策粗糙集动态更新算法 ·747·