第9卷第2期 智能系统学报 Vol.9 No.2 2014年4月 CAAI Transactions on Intelligent Systems Apr.2014 D0I:10.3969/i.issn.1673-4785.201307014 网络出版地址:http://www.cnki.net/kcms/doi/CNKI:23-1538/TP.20131105.1202.006.html 基因表达数据在邻域关系中的特征选择 陈玉明,吴克寿1,李向军2 (1.厦门理工学院计算机科学与技术系,福建厦门361024:2.南昌大学计算机科学与技术系,江西南昌330031) 摘要:基因特征选择是基因表达数据分析中的一种重要方法。粗糙集是一种处理不确定性、不一致性、不精确性 数据的有效分类工具,其特点是保持基因表达数据集的分类能力不变,进行基因特征选择。为了避免传统粗糙集特 征选择方法所必需的离散化过程带来的信息损失,将邻域粗糙集特征选择方法应用于基因的特征选取,提出了基于 邻域粗糙集的基因选择方法。该方法从所有特征出发,根据特征重要度逐步删除冗余的特征,最后得到关键特征组 进行分类研究。在2个标准的基因表达数据集上进行特征选取,并进行了分类实验,实验结果表明该方法是有效可 行的。 关键词:粗糙集:邻域关系:基因表达数据:特征选择:分类 中图分类号:TP391文献标志码:A文章编号:1673-4785(2014)02-0210-04 中文引用格式:陈玉明,吴克寿,李向军.基因表达数据在邻域关系中的特征选择[J].智能系统学报,2014,9(2):210-213. 英文引用格式:CHEN Yuming,WU Keshou,LI Xiangjun.Gene expression data feature selection with neighborhood relation[J]. CAAI Transactions on Intelligent Systems,2014,9(2):209-212. Gene expression data feature selection with neighborhood relation CHEN Yuming',WU Keshou',LI Xiangjun2 (1.Department of Computer Science and Technology,Xiamen University of Technology,Xiamen 361024,China;2.Department of Computer Science and Technology,Nanchang University,Nanchang 330031,China) Abstract:The selection of an efficient gene feature is a key procedure for analysis of gene expression data.The rough set theory is an efficient classification tool to deal with uncertain,inconsistent and inaccurate gene data.One limitation of the rough set theory is the lack of effective methods for processing real valued data.However,gene ex- pression data sets are always continuous.Discrete methods can result in information loss.This paper investigates an approach to the selection of gene feature on the basis of the neighborhood rough set theory.Starting from all the fea- tures,this approach gradually removes the redundant features,and finally gets the key features of the group classifi- cation study based on the importance degree of characteristics.To evaluate the performance of the proposed ap- proach,we applied it to two bench mark gene expression data sets which were compared to certain aspects of the feature selections.The experimental results illustrate that our algorithm is more effective for selecting high discrimi- native genes in cancer classification tasks. Keywords:rough sets;neighborhood relation;gene expression data;feature selection;classification 美国人类基因组计划(HG)把基因组信息学基因的表达数据所构成的数据矩阵。通过对该数据 定义为:它是一个学科领域,包含着基因组信息的获 矩阵的分析,可以回答一些生物学问题。随着试验 取、处理、存储、分配、分析和解释的所有方面。基因 技术及仪器的不断改进和基因组数据的急剧增长, 表达数据分析的对象是在不同条件下,全部或部分 现代DNA微阵列或芯片技术产生的各种基因表达 数据均规模庞大、内容复杂。如何有效地分析利用 收稿日期:2012-10-26.网络出版日期:2013-11-05. 基金项目:国家自然科学青年基金资助项目(61103246). 这些数据成为生物信息学中的挑战性课题。在基因 通信作者:陈玉明.E-mail:cym0620@163.com 表达数据分析中,基因的数目成千上万,但往往只是
第 9 卷第 2 期 智 能 系 统 学 报 Vol.9 №.2 2014 年 4 月 CAAI Transactions on Intelligent Systems Apr. 2014 DOI:10.3969 / j.issn.1673⁃4785.201307014 网络出版地址:http: / / www.cnki.net / kcms/ doi / CNKI:23⁃1538 / TP.20131105.1202.006.html 基因表达数据在邻域关系中的特征选择 陈玉明1 ,吴克寿1 ,李向军2 (1. 厦门理工学院 计算机科学与技术系,福建 厦门 361024; 2. 南昌大学 计算机科学与技术系,江西 南昌 330031) 摘 要:基因特征选择是基因表达数据分析中的一种重要方法。 粗糙集是一种处理不确定性、不一致性、不精确性 数据的有效分类工具,其特点是保持基因表达数据集的分类能力不变,进行基因特征选择。 为了避免传统粗糙集特 征选择方法所必需的离散化过程带来的信息损失,将邻域粗糙集特征选择方法应用于基因的特征选取,提出了基于 邻域粗糙集的基因选择方法。 该方法从所有特征出发,根据特征重要度逐步删除冗余的特征,最后得到关键特征组 进行分类研究。 在 2 个标准的基因表达数据集上进行特征选取,并进行了分类实验,实验结果表明该方法是有效可 行的。 关键词:粗糙集;邻域关系;基因表达数据;特征选择;分类 中图分类号: TP391 文献标志码:A 文章编号:1673⁃4785(2014)02⁃0210⁃04 中文引用格式:陈玉明,吴克寿,李向军. 基因表达数据在邻域关系中的特征选择[J]. 智能系统学报, 2014, 9(2): 210⁃213. 英文引用格式:CHEN Yuming,WU Keshou,LI Xiangjun. Gene expression data feature selection with neighborhood relation[ J]. CAAI Transactions on Intelligent Systems, 2014, 9(2): 209⁃212. Gene expression data feature selection with neighborhood relation CHEN Yuming 1 , WU Keshou 1 , LI Xiangjun 2 (1. Department of Computer Science and Technology, Xiamen University of Technology, Xiamen 361024, China; 2. Department of Computer Science and Technology, Nanchang University, Nanchang 330031, China) Abstract:The selection of an efficient gene feature is a key procedure for analysis of gene expression data. The rough set theory is an efficient classification tool to deal with uncertain, inconsistent and inaccurate gene data. One limitation of the rough set theory is the lack of effective methods for processing real valued data. However, gene ex⁃ pression data sets are always continuous. Discrete methods can result in information loss. This paper investigates an approach to the selection of gene feature on the basis of the neighborhood rough set theory. Starting from all the fea⁃ tures, this approach gradually removes the redundant features, and finally gets the key features of the group classifi⁃ cation study based on the importance degree of characteristics. To evaluate the performance of the proposed ap⁃ proach, we applied it to two bench mark gene expression data sets which were compared to certain aspects of the feature selections. The experimental results illustrate that our algorithm is more effective for selecting high discrimi⁃ native genes in cancer classification tasks. Keywords:rough sets; neighborhood relation; gene expression data; feature selection; classification 收稿日期:2012⁃10⁃26. 网络出版日期:2013⁃11⁃05. 基金项目:国家自然科学青年基金资助项目(61103246). 通信作者:陈玉明. E⁃mail:cym0620@ 163.com. 美国人类基因组计划(HGP) 把基因组信息学 定义为:它是一个学科领域,包含着基因组信息的获 取、处理、存储、分配、分析和解释的所有方面。 基因 表达数据分析的对象是在不同条件下,全部或部分 基因的表达数据所构成的数据矩阵。 通过对该数据 矩阵的分析,可以回答一些生物学问题。 随着试验 技术及仪器的不断改进和基因组数据的急剧增长, 现代 DNA 微阵列或芯片技术产生的各种基因表达 数据均规模庞大、内容复杂。 如何有效地分析利用 这些数据成为生物信息学中的挑战性课题。 在基因 表达数据分析中,基因的数目成千上万,但往往只是
第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·
.212 智能系统学报 第9卷 类信息,为离散型的数据。定义决策特征D对条件 GSNRS算法的有效性。2个标准基因表达数据集分 特征C的邻域依赖度为yc(D)。=C.(D)。I/ 别为Lymphoma和Liver cancer。Lymphoma数据集 IU,其中|U川表示集合U的基数。 包含了96个样本,4026个特征基因,其中54个 定义8设邻域决策表D,=(U,CUD,Vf, Othertype子类和42个B-celllymphoma子类。Liver 8),对Hb∈BCC,若YB(D)6=Ya-b(D)6,则称 cancer数据集包含了156个样本,1648个基因,其 b为B中相对于D是不必要的:否则称b为B中相 中82个HCCs子类和74个nontumorlivers子类。实 对于D是必要的。对HB二C,若B中任一元素相 验基因数据集如表1所示。 对于D都是必要的,则称B相对于D独立。 表1基因表达数据集 定义9设邻域决策表D,=(U,CUD,V,f, Table 1 Gene expression data sets 8),若HBCC,Yg(D)s=yc(D)s且B相对于D是 数据集 基因个数 类别 样本数 独立的,则称B是选取的关键特征组,这一特征选 取过程称为邻域特征选择。 Lymphoma 4026 B-cell 42 性质1设邻域决策表D,=(U,CUD,V,f, Lymphoma 4026 Other type 54 8),若B,CB2C.SC,则0≤YB(D)6≤ Liver cancer 1648 HCCs 82 YB(D)a≤.≤Yc(D)6≤1。 Liver cancer 1648 Nontumor livers 74 定义10设邻域决策表DT=(U,CUD,V,f, 在Lymphoma和Livercancer基因表达数据中分 8),Ha∈C,RSC,定义a相对于R的特征重要度 别采用文献[9]中粗糙集的特征选择算法TRS与本 为Sign(a,R,D)=YRUlal(D)s-Yr(D)6o 文邻域特征选择算法GSNRS进行比较。首先进行 2.2基于邻域关系的基因选择算法 预处理,对于有缺失值的数据采用文献[10]的方法 性质1表明邻域依赖度具有单调性,因此可以 进行完备化。基因表达数据集是连续型的数据,对 采用删除法或添加法进行特征选择,基因表达数据 于经典粗糙集特征选择算法,需要对其数据进行离 可以表示成前面定义的邻域决策表,依据上述邻域 散化,离散化过程采用文献[8]中的方法进行。而 特征选择的定义,可设计如下基于邻域关系的基因 本文GSNRS特征选择算法,不需要离散化。设邻域 选择算法。下面以定义10的特征重要度为启发式 参数为8=0.1,特征选择结果如表2所示。 信息设计了一种基于邻域关系的基因选择算法。 表2基因数据集特征选择结果 算法GSNRS(基于邻域关系的基因选择算法) Table 2 Results of gene feature selection 输入:基因表达数据决策表D,=(U,CUD,V, f,8); 数据集 基因个数样本数TRS算法GSNRS算法 输出:D,的一个邻域约简R。 Lymphoma 4026 96 7 6 1)计算整个条件特征集C相对于决策特征D Liver cancer 1 648 156 6 5 的邻域依赖度为Yc(D)s 由表2可知,TRS算法在Lymphoma数据集中 2)R:=C。 选择出7个关键基因,在Liver cancer数据集中选择 3)当yR(D)6=Yc(D)s重复: 出6个关键基因。GSNRS算法在Lymphoma数据集 ①对所有的aeR计算特征重要度Sigm(a,R,D); 中选择出6个关键基因,在Liver cancer数据集中选 ②在R中选择特征a满足特征重要度最小; 择出5个关键基因。下面再比较2组基因的分类能 ③R:=R-{a}。 力,分别针对选取的关键基因采用KNN,C5.0分类 4)输出R。 器进行分类实验,并用留一交叉法检验分类精确率, 在算法中,每次选择特征重要度最小的特征,若 实验结果如表3所示。 去掉它后决策表的邻域依赖度仍然不变,则可以去 表3基因分类精确率 掉,否则保留下来,依次进行下去,直到得到一个条 Table 3 Gene classification accuracy rate 件特征子集,在其中去掉任何一个特征,决策表的邻 数据集 Lymphoma本文方法 域依赖度都会改变,则算法结束,该特征子集即为所 Liver cancer 选取关键特征组。 特征选择算法TRS GSNRS TRS GSNRS KNN分类器 93.6 94.9 89.1 91.4 3实验结果与分析 C5.0分类器 95.1 96.5 91.4 93.2 下面选用2个标准的基因表达数据集来验证 上述实验结果表明,基于粗糙集的基因选择方
类信息,为离散型的数据。 定义决策特征 D 对条件 特征 C 的邻域依赖度为 γC (D)δ =| C∗ (D)δ | / U , 其中 U 表示集合 U 的基数。 定义 8 设邻域决策表 DT = (U,C ∪ D,V,f, δ), 对 ∀b ∈ B ⊆ C, 若 γB (D)δ = γB-{b} (D)δ, 则称 b 为 B 中相对于 D 是不必要的;否则称 b 为 B 中相 对于 D 是必要的。 对 ∀B ⊆ C, 若 B 中任一元素相 对于 D 都是必要的,则称 B 相对于 D 独立。 定义 9 设邻域决策表 DT = (U,C ∪ D,V,f, δ), 若 ∀B⊆C, γB (D)δ = γC (D)δ 且 B 相对于 D 是 独立的,则称 B 是选取的关键特征组,这一特征选 取过程称为邻域特征选择。 性质 1 设邻域决策表 DT = (U,C ∪ D,V,f, δ), 若 B1 ⊆ B2 ⊆... ⊆ C, 则 0 ≤ γB1 (D)δ ≤ γB2 (D)δ ≤... ≤ γC (D)δ ≤ 1。 定义 10 设邻域决策表 DT = (U,C ∪ D,V,f, δ), ∀a∈C, R⊆C, 定义 a 相对于 R 的特征重要度 为 Sign(a,R,D) = γR∪{a} (D)δ - γR (D)δ。 2.2 基于邻域关系的基因选择算法 性质 1 表明邻域依赖度具有单调性,因此可以 采用删除法或添加法进行特征选择,基因表达数据 可以表示成前面定义的邻域决策表,依据上述邻域 特征选择的定义,可设计如下基于邻域关系的基因 选择算法。 下面以定义 10 的特征重要度为启发式 信息设计了一种基于邻域关系的基因选择算法。 算法 GSNRS(基于邻域关系的基因选择算法) 输入:基因表达数据决策表 DT = (U,C ∪ D,V, f,δ); 输出: DT 的一个邻域约简 R。 1)计算整个条件特征集 C 相对于决策特征 D 的邻域依赖度为 γC (D)δ。 2) R: = C。 3) 当 γR (D)δ = γC (D)δ 重复: ①对所有的a∈R 计算特征重要度Sign (a,R,D) ; ②在 R 中选择特征 a 满足特征重要度最小; ③ R: = R - {a}。 4) 输出 R。 在算法中,每次选择特征重要度最小的特征,若 去掉它后决策表的邻域依赖度仍然不变,则可以去 掉,否则保留下来,依次进行下去,直到得到一个条 件特征子集,在其中去掉任何一个特征,决策表的邻 域依赖度都会改变,则算法结束,该特征子集即为所 选取关键特征组。 3 实验结果与分析 下面选用 2 个标准的基因表达数据集来验证 GSNRS 算法的有效性。 2 个标准基因表达数据集分 别为 Lymphoma 和 Liver cancer。 Lymphoma 数据集 包含了 96 个样本,4 026 个特征基因,其中 54 个 Othertype 子类和 42 个 B⁃celllymphoma 子类。 Liver cancer 数据集包含了 156 个样本,1 648 个基因,其 中 82 个 HCCs 子类和 74 个 nontumorlivers 子类。 实 验基因数据集如表 1 所示。 表 1 基因表达数据集 Table 1 Gene expression data sets 数据集 基因个数 类别 样本数 Lymphoma 4 026 B⁃cell 42 Lymphoma 4 026 Other type 54 Liver cancer 1 648 HCCs 82 Liver cancer 1 648 Nontumor livers 74 在 Lymphoma 和 Livercancer 基因表达数据中分 别采用文献[9]中粗糙集的特征选择算法 TRS 与本 文邻域特征选择算法 GSNRS 进行比较。 首先进行 预处理,对于有缺失值的数据采用文献[10]的方法 进行完备化。 基因表达数据集是连续型的数据,对 于经典粗糙集特征选择算法,需要对其数据进行离 散化,离散化过程采用文献[8] 中的方法进行。 而 本文 GSNRS 特征选择算法,不需要离散化。 设邻域 参数为 δ = 0.1, 特征选择结果如表 2 所示。 表 2 基因数据集特征选择结果 Table 2 Results of gene feature selection 数据集 基因个数 样本数 TRS 算法 GSNRS 算法 Lymphoma 4 026 96 7 6 Liver cancer 1 648 156 6 5 由表 2 可知,TRS 算法在 Lymphoma 数据集中 选择出 7 个关键基因,在 Liver cancer 数据集中选择 出 6 个关键基因。 GSNRS 算法在 Lymphoma 数据集 中选择出 6 个关键基因,在 Liver cancer 数据集中选 择出 5 个关键基因。 下面再比较 2 组基因的分类能 力,分别针对选取的关键基因采用 KNN,C5.0 分类 器进行分类实验,并用留一交叉法检验分类精确率, 实验结果如表 3 所示。 表 3 基因分类精确率 Table 3 Gene classification accuracy rate % 数据集 特征选择算法 Lymphoma 本文方法 TRS GSNRS Liver cancer TRS GSNRS KNN 分类器 93.6 94.9 89.1 91.4 C5.0 分类器 95.1 96.5 91.4 93.2 上述实验结果表明,基于粗糙集的基因选择方 ·212· 智 能 系 统 学 报 第 9 卷
第2期 陈玉明,等:基因表达数据在邻域关系中的特征选择 .213. 法和基于邻域关系的基因选择方法都能正确提取有 [4]BANERJEE M,MITRA S,BANKA H.Evolutinary-rough 效的基因。基于邻域关系的基因选择方法不需要离 feature selection in gene expression data[J].IEEE Transac- 散化,而且由于避免了离散化过程的造成的信息丢 tions on Systems,Man,and Cybernetics,Part C:Applica- tion and Reviews,2007,37:622-632. 失,提取的特征基因个数较少。在分类精度上,基于 [5]YANG Ming,YANG Ping.A novel condensing tree struc- 邻域关系的基因选择方法提取的基因优于基于粗糙 ture for rough set feature selection[].Neurocomputing, 集的基因选择方法提取的基因。 2008.71(4/5/6):1092.1100. [6]QIAN Yuhua,LIANG Jiye.Positive approximation:an ac- 4结束语 celerator for attribute reduction in rough set theory Arti- 传统粗糙集理论中的特征选择方法往往难以处 ficial Intelligence,2010,174(9/10):597-618. 理连续性的基因表达数据,成为基因表达数据研究 [7]CHEN Yuming,MIAO Duoqian.A rough set approach to feature selection based on power set tree[J].Knowledge- 中的主要缺陷和障碍。本文针对传统粗糙集理论中 Based Systems,2011,24(2):275-281. 难以处理连续数据的缺点,在特征选择中引入邻域 [8]苗夺谦.Rough set理论中连续属性的离散化方法[J].自 关系,定义了邻域依赖度与邻域特征选择等概念,提 动化学报,2001,27(3):296-302. 出了一种基于邻域关系的基因特征选择方法。该特 MIAO Duoqian.A new method of discretization of continu- 征方法不用对数据进行离散化,避免了信息损失,从 ous attributes in rough sets [J].Acta Automatica Sinica, 而提高了被选择基因的分类准确率。拓展了粗糙集 2001,27(3):296-302. [9]王国胤.Rough集理论与知识获取[M].西安:西安交通 理论的应用范围,为基因表达数据分析技术提供了 大学出版社,2001:24-28. 一种新的尝试。 [10]GRZYMALA-BUSSE J W.Handling missing attribute val- ues[M].[S.I.]:Springer,2005:37-57. 参考文献: 作者简介: [1]TIBSHIRANI R,HASTIE T,NARASHIMAN B,et al.Di- 陈玉明,男,1977年生,副教授.主 agnosis of multiple cancer types by shrunken centroids of 要研究方向为粒计算、粗糙集、模式识 gene expression[C]//Nat'1 Academy of Sciences.[S.1.], 别、数据挖掘等。 USA,2002:6567-6572. [2]KOHAVI R,JOHN G H.Wrappers for feature subset selec- tion[J].Artificial Intelligence,1997,97(1/2):273-324. [3]PAWLAK Z.Rough sets[J].International Journal of Com- puter and Information Science,1982,11(5):341-356
法和基于邻域关系的基因选择方法都能正确提取有 效的基因。 基于邻域关系的基因选择方法不需要离 散化,而且由于避免了离散化过程的造成的信息丢 失,提取的特征基因个数较少。 在分类精度上,基于 邻域关系的基因选择方法提取的基因优于基于粗糙 集的基因选择方法提取的基因。 4 结束语 传统粗糙集理论中的特征选择方法往往难以处 理连续性的基因表达数据,成为基因表达数据研究 中的主要缺陷和障碍。 本文针对传统粗糙集理论中 难以处理连续数据的缺点,在特征选择中引入邻域 关系,定义了邻域依赖度与邻域特征选择等概念,提 出了一种基于邻域关系的基因特征选择方法。 该特 征方法不用对数据进行离散化,避免了信息损失,从 而提高了被选择基因的分类准确率。 拓展了粗糙集 理论的应用范围,为基因表达数据分析技术提供了 一种新的尝试。 参考文献: [1]TIBSHIRANI R, HASTIE T, NARASHIMAN B, et al. Di⁃ agnosis of multiple cancer types by shrunken centroids of gene expression[C] / / Nat’1 Academy of Sciences. [ S.l.], USA, 2002: 6567⁃6572. [2]KOHAVI R, JOHN G H. Wrappers for feature subset selec⁃ tion[J]. Artificial Intelligence, 1997, 97(1 / 2): 273⁃324. [3]PAWLAK Z. Rough sets[ J]. International Journal of Com⁃ puter and Information Science, 1982, 11(5): 341⁃356. [4] BANERJEE M, MITRA S, BANKA H. Evolutinary⁃rough feature selection in gene expression data[J]. IEEE Transac⁃ tions on Systems, Man, and Cybernetics, Part C: Applica⁃ tion and Reviews, 2007, 37: 622⁃632. [5]YANG Ming, YANG Ping. A novel condensing tree struc⁃ ture for rough set feature selection [ J]. Neurocomputing, 2008, 71(4 / 5 / 6): 1092⁃1100. [6]QIAN Yuhua, LIANG Jiye. Positive approximation: an ac⁃ celerator for attribute reduction in rough set theory[J]. Arti⁃ ficial Intelligence, 2010, 174(9 / 10): 597⁃618. [7] CHEN Yuming, MIAO Duoqian. A rough set approach to feature selection based on power set tree [ J]. Knowledge⁃ Based Systems, 2011, 24(2): 275⁃281. [8]苗夺谦. Rough set 理论中连续属性的离散化方法[J]. 自 动化学报, 2001, 27(3): 296⁃302. MIAO Duoqian. A new method of discretization of continu⁃ ous attributes in rough sets [ J]. Acta Automatica Sinica, 2001, 27(3): 296⁃302. [9]王国胤. Rough 集理论与知识获取[M]. 西安: 西安交通 大学出版社, 2001:24⁃28. [10]GRZYMALA⁃BUSSE J W. Handling missing attribute val⁃ ues[M]. [S.l.]: Springer, 2005: 37⁃57. 作者简介: 陈玉明,男,1977 年生,副教授,主 要研究方向为粒计算、粗糙集、模式识 别、数据挖掘等。 第 2 期 陈玉明,等:基因表达数据在邻域关系中的特征选择 ·213·