第6期 高媛，等：面向一致性样本的属性约简 ·1171· 足，涌现出了一批可以处理复杂类型数据的拓展 中[x]。表示与x属于同一个决策类的样本的 粗糙集模型B。 集合。 众所周知，无论是在经典粗糙集还是在众多 定义1给定一个决策系统DS,VACAT,则邻 拓展粗糙集研究中，属性约简610一直扮演着核 域关系定义为 心角色。根据问题求解需求的不同，属性约简可 Na={x,y)∈U×U:(x,y)≤61 (1) 以使用不同的度量准则加以定义，因此其具有丰 其中，x,y∈U,(x,y)表示样本x与y之间的欧氏 富的解释与含义。例如近似质量可以用来度量数 距离，>0称为邻域半径。 据中的确定性程度，条件熵可以用来描述条件属 则由式(1)，容易得到关于A样本x的邻域： 性相对于决策属性的鉴别能力。属性约简，就可 6a(x)={ylr(x,y)≤6l (2) 以依据这些度量准则，找到数据中的冗余属性并 定义2给定一个决策系统DS,UIND(D)= 加以删除，以达到满足度量准则所对应的约束条 {X,X2,,X,},VACAT,YX。∈UIND(D),X2关于 件。通过这一策略，还能够使得后续的学习过程 A的下近似集和上近似集分别定义为 仅需在一部分属性上构建模型，从而达到降低学 NX,={x∈U6a(w)∈Xp} (3) 习难度以及降低学习时间消耗的目的。 NaX2={x∈U6a()nX,≠} (4) 目前在粗糙集理论中，穷举法与启发式方法 定义32！给定一个决策系统DS,UND(D)= 被公认为是求解约简的两大类基本方法。然而很 {X,X,,X,},VACAT,D关于A的近似质量定义 多穷举搜索与启发式搜索策略都将数据集中的所 如下： 有样本视为同等重要，当样本量非常巨大时，这 会带来较低的约简求解效率。为解决这一问题， y(A,D)= (5) 已有众多学者将样本选择的概念引入到约简求解 过程中。样本选择的概念最早是由Hat提出，他 其中UU表示集合X的基数。 提出了压缩近邻规则，随后亦有学者提出了很 显然0≤4，D)≤1成立。(4，D)表示根据条 多改进策略，如缩减最近邻)、有序最近邻)和 件属性A,那些确定属于某一决策类别的样本占 快速压缩最近邻，等。当涉及约简求解的问题 总体样本的比例。 时，已有学者s9关注到不同的样本对属性重要 条件嫡是属性约简中另外一种常用的度量准 度评价的贡献是不同的，如王熙照等提出的K 则，它能反映条件属性相对于决策属性的鉴别能 means样本选择算法将远离类簇中心点的样本视 力。根据不同的需求，很多学者设计并定义了多 为重要的：随后Xu等将这种方法应用到多标 种形式的条件嫡22，一种经典的形式可定义为： 记数据的维度压缩问题中。但他们在追求时间效 定义421给定一个决策系统DS,VACAT, 率的同时忽略了约简在测试集上的分类性能。 D关于A的条件嫡定义如下： 基于以上分析，笔者提出了一种基于样本一 ENT(A,D)=- 1>1og A(x)0[xII (6) IUI 致性原则的样本选择算法（以下简称为一致性采 样)，一致性采样的主要思想为：1)给定一个样本， 显然，条件嫡的值越小，条件属性相对于决策 找到距离自己最近的邻居；2)判断这一邻居是否 属性鉴别能力越大。 与自身属于同一类别，若属于同一类别，则将该 样本选中；3)最后将所有选中的样本组成一个新 2属性约简 的数据集。 属性约简作为粗糙集领域的一个核心内容， 1基础知识 其主要目的是根据某一给定的约束条件来去除全 部属性中的冗余、不相关的属性。目前求解约简 在粗糙集理论中，一个决策系统可表示为一 的常用策略包括穷举式算法和启发式算法。虽然 个二元组DS=<U,ATUD>,U是所有样本构成的 前者可以得到一个数据中的所有约简，但当数据 非空有限集合，即论域；AT是所有条件属性的集 维数急剧升高时，它的时间消耗随之增大，过大 合；D是决策属性的集合且AT∩D=O。当D的取 的时间消耗导致算法并不适用于处理实际问题。 值都为离散型时，可得UND(D)={X,X2,,X,}, 与穷举式算法不同，启发式算法因其较高的时间 其表示根据决策属性D所诱导出的论域上的划 效率得到了众多学者的青睐，它运用贪心策略，每 分，对于X,∈UNDD),X表示第p个决策类，其 次迭代过程中其将属性重要度最大的属性加入到足，涌现出了一批可以处理复杂类型数据的拓展 粗糙集模型[3-5]。 众所周知，无论是在经典粗糙集还是在众多 拓展粗糙集研究中，属性约简[6-10] 一直扮演着核 心角色。根据问题求解需求的不同，属性约简可 以使用不同的度量准则加以定义，因此其具有丰 富的解释与含义。例如近似质量可以用来度量数 据中的确定性程度，条件熵可以用来描述条件属 性相对于决策属性的鉴别能力。属性约简，就可 以依据这些度量准则，找到数据中的冗余属性并 加以删除，以达到满足度量准则所对应的约束条 件。通过这一策略，还能够使得后续的学习过程 仅需在一部分属性上构建模型，从而达到降低学 习难度以及降低学习时间消耗的目的。 目前在粗糙集理论中，穷举法与启发式方法 被公认为是求解约简的两大类基本方法。然而很 多穷举搜索与启发式搜索策略都将数据集中的所 有样本视为同等重要，当样本量非常巨大时，这 会带来较低的约简求解效率。为解决这一问题， 已有众多学者将样本选择的概念引入到约简求解 过程中。样本选择的概念最早是由 Hart 提出，他 提出了压缩近邻规则[11] ，随后亦有学者提出了很 多改进策略，如缩减最近邻[12] 、有序最近邻[13] 和 快速压缩最近邻[14] 等。当涉及约简求解的问题 时，已有学者[15-19] 关注到不同的样本对属性重要 度评价的贡献是不同的，如王熙照等[15] 提出的 K￾means 样本选择算法将远离类簇中心点的样本视 为重要的；随后 Xu 等 [19] 将这种方法应用到多标 记数据的维度压缩问题中。但他们在追求时间效 率的同时忽略了约简在测试集上的分类性能。 基于以上分析，笔者提出了一种基于样本一 致性原则的样本选择算法 (以下简称为一致性采 样)，一致性采样的主要思想为：1) 给定一个样本， 找到距离自己最近的邻居；2) 判断这一邻居是否 与自身属于同一类别，若属于同一类别，则将该 样本选中；3) 最后将所有选中的样本组成一个新 的数据集。 1 基础知识 Ø ··· ∀ 在粗糙集理论中，一个决策系统可表示为一 个二元组 DS=<U, AT∪D>, U 是所有样本构成的 非空有限集合，即论域；AT 是所有条件属性的集 合；D 是决策属性的集合且 AT∩D= 。当 D 的取 值都为离散型时，可得 U/IND (D)={X1 , X2 , , Xq}， 其表示根据决策属性 D 所诱导出的论域上的划 分，对于 Xp∈U/IND(D), Xp 表示第 p 个决策类，其 中 [ x ] D 表示与 x 属于同一个决策类的样本的 集合。 定义 1 给定一个决策系统 DS, ∀ A ⊆ AT, 则邻 域关系定义为 NA = {(x, y) ∈ U ×U : r(x, y) ⩽ δ} (1) 其中， ∀ x, y∈U, r(x, y) 表示样本 x 与 y 之间的欧氏 距离，δ>0 称为邻域半径。 则由式 (1)，容易得到关于 A 样本 x 的邻域： δA (x) = {y|r(x, y) ⩽ δ} (2) ··· ∀ ⊆ ∀ 定义 2 给定一个决策系统 DS, U/IND(D)= {X1 , X2 , , Xq}, A AT, Xp∈U/IND(D), Xp 关于 A 的下近似集和上近似集分别定义为 NAXp = {x ∈ U|δA (x) ⊆ Xp} (3) NAXp = {x ∈ U|δA (x)∩ Xp , ϕ} (4) ··· ∀ ⊆ 定义 3 [20] 给定一个决策系统 DS, U/IND(D)= {X1 , X2 , , Xq}, A AT, D 关于 A 的近似质量定义 如下： γ(A,D)=       ∪q p=1 NAXp       |U| (5) 其中|U|表示集合 X 的基数。 显然 0≤γ(A, D)≤1 成立。γ(A, D) 表示根据条 件属性 A, 那些确定属于某一决策类别的样本占 总体样本的比例。 条件熵是属性约简中另外一种常用的度量准 则，它能反映条件属性相对于决策属性的鉴别能 力。根据不同的需求，很多学者设计并定义了多 种形式的条件熵[21-25] ，一种经典的形式可定义为： 定义 4 ∀ ⊆ [25] 给定一个决策系统 DS, A AT, D 关于 A 的条件熵定义如下： ENT(A,D) = − 1 |U| ∑ x∈U log |δA(x)∩[x]D| |U| (6) 显然，条件熵的值越小，条件属性相对于决策 属性鉴别能力越大。 2 属性约简 属性约简作为粗糙集领域的一个核心内容， 其主要目的是根据某一给定的约束条件来去除全 部属性中的冗余、不相关的属性。目前求解约简 的常用策略包括穷举式算法和启发式算法。虽然 前者可以得到一个数据中的所有约简，但当数据 维数急剧升高时，它的时间消耗随之增大，过大 的时间消耗导致算法并不适用于处理实际问题。 与穷举式算法不同，启发式算法因其较高的时间 效率得到了众多学者的青睐，它运用贪心策略，每 次迭代过程中其将属性重要度最大的属性加入到 第 6 期 高媛，等：面向一致性样本的属性约简 ·1171·