第2期 陈玉明，等：基因表达数据在邻域关系中的特征选择 ·211· 很少一部分的关键基因影响样本的分类，其他的基 当p=1时，称为曼哈顿距离，当p=2时，称为 因往往是冗余的或者是不重要的。在设计基因表达 欧氏距离。 数据分类器之前进行特征选择，可以有效降低分类 定义3给定邻域信息系统I=(,A,V,f,6), 器的时间复杂度，提高分类精度。目前最常用的基 对于任一x∈U,B二A,定义x在B上的δ邻域 因表达数据特征选择方法主要有2类：基于过滤算 n(x)为 法(filter)的选择方法)与基于wrapper的选择方 ng(x)={ylx,y∈U,Dg(x,y）≤8} 法[]。基于lter的基因表达数据特征选择方法使 根据距离函数的定义，邻域n。(x)满足： 用数据本身的内在特性作为评价基因的准则，但通 1)n8(x)≠0； 过filter选择出来的若干个基因可能具有较强的相 2)x∈ng(x): 关性。基于wrapper的基因表达数据特征选择方法 3)y∈n8(x)台x∈ng(y); 根据分类器的某种性能来评价基因或基因子集的重 要性，而基于wrapper方法在基因的选择过程中反 4)n8(x)=U。 复调用分类算法，往往造成较高的时间复杂度。 定义4给定邻域信息系统1s=(U,A,Vf,6), 粗糙集由波兰科学家Pawlak于1982年提 任一特征子集BCA决定了一个邻域阈值δ上的邻 出)，用于处理不确定、不一致、不精确数据的数学 域关系NRs(B):NR,(B)={(x,y)∈U×UIDg(x, 理论工具。现已广泛应用在人工智能、数据挖掘、机 y)≤！。U/NR,(B)构成了U的一个邻域划分，称 器学习等领域[47】。然而，Pawlak粗糙集只能处理 其为U上的一簇邻域知识，其中每个邻域划分称为 离散化的数据，对于现实世界广泛而大量存在的连 一个邻域类或者邻域知识。上述邻域n(x)即为一 续数据却缺乏有效的处理能力。基因表达数据也往 个邻域类。 往都是连续的，目前大多数方法是将基因表达数据 2基于邻域关系的基因选择方法 先进行离散化[⑧劉，离散化过程必定会造成某种程度 的信息丢失，并影响分类系统的分类精度。 基于等价关系的信息熵、互信息、粗糙嫡等概念 度量了知识的粗细程度，也反映了决策系统中的分 1邻域关系 类能力大小，但主要处理离散型数据的决策系统，对 传统粗糙集理论采用等价类形式化地表示知识 于连续型的数据并不能够直接处理。下面结合邻域 分类。然而，等价类是基于离散型的数据形成的等价 关系与邻域类的定义，进一步定义了邻域特征选择 关系划分而得到的，对于连续型的数据并不能构造合 概念，用于连续型的基因表达数据的特征选择当中。 适的等价类。因此，下面引入邻域关系处理连续型的 同时，提出一种基于邻域关系的启发式基因表达数 基因表达数据，用于基因表达数据的特征选择。 据特征选择算法。 定义1设五元组1=(U,A,V,f,)为邻域信 2.1邻域特征选择 息系统，其中U是非空有限集，称为论域，A是有限 定义5定义D,=(U,CUD,Vf,8)为一个 特征集，V=UV。,V表示特征a的值域，f:U×A→ 邻域决策表，其中C为条件特征，特征值为连续型 V是一个信息函数，即对Hx∈U,a∈A,有 的数据，邻域阈值为8，其邻域划分为U/NR。(C)= f(x,a)∈Va,6∈[0，l]为邻域阈值。 {X1,X2,…,X},D为决策特征，决策特征是一些决 定义2给定邻域信息系统I、=(U,A,Vf,8), 策分类信息，为离散型的数据，以等价关系划分为 对于任-x,y∈U,B二A,B={a1,a2,,an},定义 U/D={Y,Y2,…,Yn}o B上的距离函数D(x,y)满足： 定义6设D,=(U,CUD,V,f,8)为一个邻 1)Da(x,y)≥0，非负； 域决策表，HB≤C,XCU,记U/NR(B)={B, 2)Ds(x,y)=0,当且仅当x=y: B2,,B},则称B。(X)G=U{B1B∈ 3)D(x,y)=D(y,x),对称； U/NRs(B),B:SX}为X关于B的邻域下近似集， 4)Dg(x,y)+Ds(y,z)≥Dg(x,z)。 称B·(X)6=U{B:IB:∈U/NRs(B),B:∩X≠O} 式中： 为X关于B的邻域上近似集。 De(x,y)= 定义7设邻域决策表D,=(U,CUD,V,f, (Σ(1fx,a,)-fy,a)1)P) δ)，其中C为条件特征，特征值为连续型的数据，邻 域阈值为δ，D为决策特征，决策特征是一些决策分很少一部分的关键基因影响样本的分类，其他的基 因往往是冗余的或者是不重要的。 在设计基因表达 数据分类器之前进行特征选择，可以有效降低分类 器的时间复杂度，提高分类精度。 目前最常用的基 因表达数据特征选择方法主要有 ２ 类：基于过滤算 法（ｆｉｌｔｅｒ） 的选择方法［１］ 与基于 ｗｒａｐｐｅｒ 的选择方 法［２］ 。 基于 ｆｉｌｔｅｒ 的基因表达数据特征选择方法使 用数据本身的内在特性作为评价基因的准则，但通 过 ｆｉｌｔｅｒ 选择出来的若干个基因可能具有较强的相 关性。 基于 ｗｒａｐｐｅｒ 的基因表达数据特征选择方法 根据分类器的某种性能来评价基因或基因子集的重 要性，而基于 ｗｒａｐｐｅｒ 方法在基因的选择过程中反 复调用分类算法，往往造成较高的时间复杂度。 粗糙 集 由 波 兰 科 学 家 Ｐａｗｌａｋ 于 １９８２ 年 提 出［３］ ，用于处理不确定、不一致、不精确数据的数学 理论工具。 现已广泛应用在人工智能、数据挖掘、机 器学习等领域［４⁃７ ］ 。 然而，Ｐａｗｌａｋ 粗糙集只能处理 离散化的数据，对于现实世界广泛而大量存在的连 续数据却缺乏有效的处理能力。 基因表达数据也往 往都是连续的，目前大多数方法是将基因表达数据 先进行离散化［８］ ，离散化过程必定会造成某种程度 的信息丢失，并影响分类系统的分类精度。 １ 邻域关系 传统粗糙集理论采用等价类形式化地表示知识 分类。 然而，等价类是基于离散型的数据形成的等价 关系划分而得到的，对于连续型的数据并不能构造合 适的等价类。 因此，下面引入邻域关系处理连续型的 基因表达数据，用于基因表达数据的特征选择。 定义 １ 设五元组 ＩＳ ＝ （Ｕ，Ａ，Ｖ，ｆ，δ） 为邻域信 息系统，其中 Ｕ 是非空有限集，称为论域， Ａ 是有限 特征集， Ｖ ＝∪ａ∈Ａ Ｖａ ， Ｖａ 表示特征 ａ 的值域， ｆ：Ｕ ×Ａ → Ｖ 是 一 个 信 息 函 数， 即 对 ∀ｘ ∈ Ｕ，ａ ∈ Ａ， 有 ｆ（ｘ，ａ） ∈Ｖａ，δ ∈ ［０，１］ 为邻域阈值。 定义 ２ 给定邻域信息系统 ＩＳ ＝ （Ｕ，Ａ，Ｖ，ｆ，δ）， 对于任一 ｘ，ｙ ∈ Ｕ，Ｂ ⊆ Ａ，Ｂ ＝ ｛ａ１ ，ａ２ ，．．．，ａｎ ｝， 定义 Ｂ 上的距离函数 ＤＢ（ｘ，ｙ） 满足： １） ＤＢ（ｘ，ｙ） ≥ ０， 非负； ２） ＤＢ（ｘ，ｙ） ＝ ０， 当且仅当 ｘ ＝ ｙ； ３） ＤＢ（ｘ，ｙ） ＝ ＤＢ（ｙ，ｘ）， 对称； ４） ＤＢ（ｘ，ｙ） ＋ ＤＢ（ｙ，ｚ） ≥ ＤＢ（ｘ，ｚ）。 式中： ＤＢ（ｘ，ｙ） ＝ （∑ ｎ ｉ ＝ １ （｜ ｆ（ｘ，ａｉ） － ｆ（ｙ，ａｉ） ｜ ） ｐ ） １／ ｐ 当 ｐ ＝ １ 时，称为曼哈顿距离，当 ｐ ＝ ２ 时，称为 欧氏距离。 定义 ３ 给定邻域信息系统 ＩＳ ＝ （Ｕ，Ａ，Ｖ，ｆ，δ）， 对于任一 ｘ ∈ Ｕ， Ｂ ⊆ Ａ， 定义 ｘ 在 Ｂ 上的 δ 邻域 ｎ δ Ｂ（ｘ） 为 ｎ δ Ｂ（ｘ） ＝ ｛ｙ ｜ ｘ，ｙ ∈ Ｕ，ＤＢ（ｘ，ｙ） ≤ δ｝ 根据距离函数的定义，邻域 ｎ δ Ｂ（ｘ） 满足： １） ｎ δ Ｂ（ｘ） ≠ ⌀； ２） ｘ ∈ ｎ δ Ｂ（ｘ）； ３） ｙ ∈ ｎ δ Ｂ（ｘ）⇔ｘ ∈ ｎ δ Ｂ（ｙ）； ４） ∪ｘ∈Ｕ ｎ δ Ｂ（ｘ） ＝ Ｕ。 定义 ４ 给定邻域信息系统 ＩＳ ＝ （Ｕ，Ａ，Ｖ，ｆ，δ）， 任一特征子集 Ｂ ⊆ Ａ 决定了一个邻域阈值 δ 上的邻 域关系 ＮＲδ（Ｂ） ： ＮＲδ（Ｂ） ＝ ｛（ｘ，ｙ） ∈Ｕ × Ｕ｜ ＤＢ（ｘ， ｙ） ≤δ｝。 Ｕ／ ＮＲδ（Ｂ） 构成了 Ｕ 的一个邻域划分，称 其为 Ｕ 上的一簇邻域知识，其中每个邻域划分称为 一个邻域类或者邻域知识。 上述邻域 ｎ δ Ｂ（ｘ） 即为一 个邻域类。 ２ 基于邻域关系的基因选择方法 基于等价关系的信息熵、互信息、粗糙熵等概念 度量了知识的粗细程度，也反映了决策系统中的分 类能力大小，但主要处理离散型数据的决策系统，对 于连续型的数据并不能够直接处理。 下面结合邻域 关系与邻域类的定义，进一步定义了邻域特征选择 概念，用于连续型的基因表达数据的特征选择当中。 同时，提出一种基于邻域关系的启发式基因表达数 据特征选择算法。 ２．１ 邻域特征选择 定义 ５ 定义 ＤＴ ＝ （Ｕ，Ｃ ∪ Ｄ，Ｖ，ｆ，δ） 为一个 邻域决策表，其中 Ｃ 为条件特征，特征值为连续型 的数据，邻域阈值为 δ， 其邻域划分为 Ｕ／ ＮＲδ（Ｃ） ＝ ｛Ｘ１ ，Ｘ２ ，．．．，Ｘｍ ｝， Ｄ 为决策特征，决策特征是一些决 策分类信息，为离散型的数据，以等价关系划分为 Ｕ／ Ｄ ＝ ｛Ｙ１ ，Ｙ２ ，．．．，Ｙｎ ｝。 定义 ６ 设 ＤＴ ＝ （Ｕ，Ｃ ∪ Ｄ，Ｖ，ｆ，δ） 为一个邻 域决策表， ∀Ｂ ⊆ Ｃ， Ｘ ⊆ Ｕ， 记 Ｕ／ ＮＲδ（Ｂ） ＝ ｛Ｂ１ ， Ｂ２ ，．．．，Ｂｉ｝， 则 称 Ｂ∗ （Ｘ）δ ＝∪ ｛Ｂｉ ｜ Ｂｉ ∈ Ｕ／ ＮＲδ（Ｂ），Ｂｉ ⊆ Ｘ｝ 为 Ｘ 关于 Ｂ 的邻域下近似集， 称 Ｂ ∗ （Ｘ）δ ＝∪｛Ｂｉ ｜ Ｂｉ ∈Ｕ／ ＮＲδ（Ｂ），Ｂｉ ∩Ｘ≠∅｝ 为 Ｘ 关于 Ｂ 的邻域上近似集。 定义 ７ 设邻域决策表 ＤＴ ＝ （Ｕ，Ｃ ∪ Ｄ，Ｖ，ｆ， δ）， 其中 Ｃ 为条件特征，特征值为连续型的数据，邻 域阈值为 δ， Ｄ 为决策特征，决策特征是一些决策分 第 ２ 期 陈玉明，等：基因表达数据在邻域关系中的特征选择 ·２１１·