第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为决策特征,决策特征是一些决策分很少一部分的关键基因影响样本的分类,其他的基 因往往是冗余的或者是不重要的。 在设计基因表达 数据分类器之前进行特征选择,可以有效降低分类 器的时间复杂度,提高分类精度。 目前最常用的基 因表达数据特征选择方法主要有 2 类:基于过滤算 法(filter) 的选择方法[1] 与基于 wrapper 的选择方 法[2] 。 基于 filter 的基因表达数据特征选择方法使 用数据本身的内在特性作为评价基因的准则,但通 过 filter 选择出来的若干个基因可能具有较强的相 关性。 基于 wrapper 的基因表达数据特征选择方法 根据分类器的某种性能来评价基因或基因子集的重 要性,而基于 wrapper 方法在基因的选择过程中反 复调用分类算法,往往造成较高的时间复杂度。 粗糙 集 由 波 兰 科 学 家 Pawlak 于 1982 年 提 出[3] ,用于处理不确定、不一致、不精确数据的数学 理论工具。 现已广泛应用在人工智能、数据挖掘、机 器学习等领域[4⁃7 ] 。 然而,Pawlak 粗糙集只能处理 离散化的数据,对于现实世界广泛而大量存在的连 续数据却缺乏有效的处理能力。 基因表达数据也往 往都是连续的,目前大多数方法是将基因表达数据 先进行离散化[8] ,离散化过程必定会造成某种程度 的信息丢失,并影响分类系统的分类精度。 1 邻域关系 传统粗糙集理论采用等价类形式化地表示知识 分类。 然而,等价类是基于离散型的数据形成的等价 关系划分而得到的,对于连续型的数据并不能构造合 适的等价类。 因此,下面引入邻域关系处理连续型的 基因表达数据,用于基因表达数据的特征选择。 定义 1 设五元组 IS = (U,A,V,f,δ) 为邻域信 息系统,其中 U 是非空有限集,称为论域, A 是有限 特征集, V =∪a∈A Va , Va 表示特征 a 的值域, f:U ×A → V 是 一 个 信 息 函 数, 即 对 ∀x ∈ U,a ∈ A, 有 f(x,a) ∈Va,δ ∈ [0,1] 为邻域阈值。 定义 2 给定邻域信息系统 IS = (U,A,V,f,δ), 对于任一 x,y ∈ U,B ⊆ A,B = {a1 ,a2 ,...,an }, 定义 B 上的距离函数 DB(x,y) 满足: 1) DB(x,y) ≥ 0, 非负; 2) DB(x,y) = 0, 当且仅当 x = y; 3) DB(x,y) = DB(y,x), 对称; 4) DB(x,y) + DB(y,z) ≥ DB(x,z)。 式中: DB(x,y) = (∑ n i = 1 (| f(x,ai) - f(y,ai) | ) p ) 1/ p 当 p = 1 时,称为曼哈顿距离,当 p = 2 时,称为 欧氏距离。 定义 3 给定邻域信息系统 IS = (U,A,V,f,δ), 对于任一 x ∈ U, B ⊆ A, 定义 x 在 B 上的 δ 邻域 n δ B(x) 为 n δ B(x) = {y | x,y ∈ U,DB(x,y) ≤ δ} 根据距离函数的定义,邻域 n δ B(x) 满足: 1) n δ B(x) ≠ ⌀; 2) x ∈ n δ B(x); 3) y ∈ n δ B(x)⇔x ∈ n δ B(y); 4) ∪x∈U n δ B(x) = U。 定义 4 给定邻域信息系统 IS = (U,A,V,f,δ), 任一特征子集 B ⊆ A 决定了一个邻域阈值 δ 上的邻 域关系 NRδ(B) : NRδ(B) = {(x,y) ∈U × U| DB(x, y) ≤δ}。 U/ NRδ(B) 构成了 U 的一个邻域划分,称 其为 U 上的一簇邻域知识,其中每个邻域划分称为 一个邻域类或者邻域知识。 上述邻域 n δ B(x) 即为一 个邻域类。 2 基于邻域关系的基因选择方法 基于等价关系的信息熵、互信息、粗糙熵等概念 度量了知识的粗细程度,也反映了决策系统中的分 类能力大小,但主要处理离散型数据的决策系统,对 于连续型的数据并不能够直接处理。 下面结合邻域 关系与邻域类的定义,进一步定义了邻域特征选择 概念,用于连续型的基因表达数据的特征选择当中。 同时,提出一种基于邻域关系的启发式基因表达数 据特征选择算法。 2.1 邻域特征选择 定义 5 定义 DT = (U,C ∪ D,V,f,δ) 为一个 邻域决策表,其中 C 为条件特征,特征值为连续型 的数据,邻域阈值为 δ, 其邻域划分为 U/ NRδ(C) = {X1 ,X2 ,...,Xm }, D 为决策特征,决策特征是一些决 策分类信息,为离散型的数据,以等价关系划分为 U/ D = {Y1 ,Y2 ,...,Yn }。 定义 6 设 DT = (U,C ∪ D,V,f,δ) 为一个邻 域决策表, ∀B ⊆ C, X ⊆ U, 记 U/ NRδ(B) = {B1 , B2 ,...,Bi}, 则 称 B∗ (X)δ =∪ {Bi | Bi ∈ U/ NRδ(B),Bi ⊆ X} 为 X 关于 B 的邻域下近似集, 称 B ∗ (X)δ =∪{Bi | Bi ∈U/ NRδ(B),Bi ∩X≠∅} 为 X 关于 B 的邻域上近似集。 定义 7 设邻域决策表 DT = (U,C ∪ D,V,f, δ), 其中 C 为条件特征,特征值为连续型的数据,邻 域阈值为 δ, D 为决策特征,决策特征是一些决策分 第 2 期 陈玉明,等:基因表达数据在邻域关系中的特征选择 ·211·