基于单调邻域粗糙集的特征基因提取

摘要：为了避免连续数据离散化处理时造成的信息损失，降低样本属性邻域求解的复杂度，提高特征基因提取的效率。该文在单调度量空间上，提出了一种基于单调邻域粗糙集的特征基因提取方法。并在两个标准的基因表达数据上进行了实验，结果证明该方法是有效可行的。

关键词：粗糙集；单调邻域；特征基因；属性约简

中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)19-4658-03

The Extract of Feature Gene Based on Monotonicity Neighborhood Rough Set

SONG Yan-pei, LI Yi-zhe, LI Chao, WU Wan-tao

(College of Computer and Information Technology, Henan Normal University, Xinxiang 453007, China)

Abstract: In order to avoid the information losing when dispersing serial data, Lower complexity of sample attribute solving neighborhood, improve the efficiency of extracting characteristics gene. In this paper, on the monotonicity metric space, proposes a gene extraction method based on montonicity neighborhood rough set. And experiments it on the two standard gene expression data, the result proves that the method is effective and feasible.

Key words: rough set; monotonicity neighborhood; characteristics gene; attribute reduction

基于属性约简算法的特征基因选择是为了获得一组基因数量尽可能小而分类能力却尽可能强的特征基因子集。采用基于经典粗糙集理论属性约简的方法从基因表达谱中选择特征基因是一个有效的方法，但是，这种方法在基因约简前必须对连续实数型的基因表达谱数据进行离散化处理，造成部分分类信息的损失，使选出的特征基因子集的分类准确率较其他方法不高。

基于单调邻域粗糙集的特征基因提取方法是在邻域粗糙集理论模型的基础上提出的，在单调度量空间提出一种邻域求解方法，以此为基础，进行属性约简。以实数空间中的每一个点形成一个δ邻域，δ邻域构成了描述空间中任意概念的基本信息粒子。在空间中的任意子集，可以通过基本信息粒子进行逼近。邻域粗糙集不需要对连续数据进行离散化处理，单调邻域求解方法能够降低邻域求解的复杂度，二者结合，避免了连续数据离散化处理时的信息损失，同时，提高了特征基因子集提取的效率。

1 基于单调邻域粗糙集的基本知识

定义1[1] 设四元组S=(U,A,V,f)是一个信息系统，其中，U表示对象的非空有限集合，也称为论域；A表示属性的非有限集A=C∪D，C∩D=?堙,C表示条件属性集，D表示决策属性集V=∪{Va│a∪A}；Va为属性A的值域；f:U×AV是一个信息函数，它为每个对象的每个属性赋予一个信息值，即?坌a∈A，x∈U，有f(x,a∈Va)。特别是，当D≠?堙时，称信息系统S为决策系统。

定义2[3] 根据在某一度量上邻域中心点到边界的最大距离定义邻域，给定一个n维实数空间Rn，称Δ:Rn×RnR是空间Rn上的一个度量，如果Δ满足下面三个条件：

Δ (x1,x2 )≥0, Δ(x1,x2 )=0当且仅当x1=x2，?坌x1,x2∈Rn；

Δ (x1,x2 )= Δ(x2,x1 ),?坌x1,x2∈Rn；

Δ (x1,x3 )≤Δ(x1,x2 )+ Δ(x2,x3 ),?坌x1,x2,x3∈Rn。

称< Rn, Δ>为度量空间。

定义3[4]对于?坌xi∈U，定义xi的邻域为：

δ(xi )={xj│xj∈U,Δ(xj,xi)≤δ}

其中，δ≥0。δ(xi )称为xi的邻域粒子。根据度量的性质，我们可以得出以下结论：

1）δ(xi )≠?堙，因为xi∈δ(xi )；

2）xj∈δ(xi )?圯 xi ∈δ(xj )

3）δ(x1) ∪ δ(x2 )∪δ(x(n-1)) ∪ δ(xn)=U 。

由上可知，邻域粒子族{δ(xi)│i=1,2,...n}构成了U的一个覆盖。由邻域信息粒子族，我们可以引导出论域空间U上的一个邻域关系N，可用关系矩阵M(N)=(rij) n×n来表示，如果(?坌xj ∈δ(xi )，则rij=1；否则，rij=0。对于邻域关系N，可得出：

rij=1；

rij=rji.

定义4 给定度量空间< Rn, Δd>，定义单调度量方法Δd为：

已知?坌x1,x2,x3∈U，x1≤x2≤x3，如果Δd (x1,x3)≤δ，则Δd (x1,x2)≤δ。

定理：给定度量空间< Rn, Δd>，并且Δd为单调度量方法，假设数据集N={x1,x2,x3,…xi,…xn}集是升序排列的，在单调度量方法Δd上，如果Δd (xj,xi )≤δ，Δd (xj+1,xi)≥δ，那么x1,x2,…xj∈δ(xi )。

证明：由于数据集N是升序排列，则x1≤x2≤x3,…≤xj,…≤xn。Δd (xj+1,xi)≥δ, Δd (xj,xi)≤δ则xj∈δ(xi )。由单调度量方法Δd的性质可以得到：Δd (xj+1,xi)≥δ,…Δd (xn,xi )≥δ，Δd (x1,xi )≤δ，…Δd (xj,xi)≤δ

则可以得到xj+1,xj+2,…xn不属于δ(xi )，而x1,x2,…xj∈δ(xi )。

定义5[5] 给定实数空间上的非空有限集合U和U的邻域关系N，称二元组NAS=为一邻域近似空间。X在邻域近似空间NAS的上近似和下近似、边界分别定义为：

Lower(X) ={xi│δ(xi )?哿X,xi∈U}

Upper(X) ={xi│δ(xi )∩X≠Φ,xi∈U}

BNX= Upper(X) -Lower(X)

X的在近似空间的正域即是NAS的下近似，X的负域定义为：

Neg(X) =U-Upper(X) = {xi│δ(xi )∩X=Φ}。

定义6[4]设A和B是两个集合，定义A包含于B的程度I(A,B)为：

当A=Φ时，定义I(A,B)=0，则0≤I(A,B)≤1。

定义7[5] 给定一个邻域决策系统NDS=,设?坌B?哿C,那么决策属性D关于条件属性B的依赖程度定义为：

显然，0≤γ(D,B)≤1。

对于a∈B，则基因的重要度定义为：

SIG(a,D,B)=γ(D,B∪a)-γ(D,B)。

定义8[8]U表示论域，A表示U的实数型属性集合，D表示决策属性，如果A生成论域上的一族邻域关系，则邻域决策系统可以表示为NDT=。

2 基于单调邻域粗糙集的属性约简方法

该算法在邻域矩阵的基础上基于属性重要度指标，以空集开始，每次计算全部剩余基因的重要度，并选择重要度最大的基因加入到目标集合中，当所有的基因的重要度都为0时结束，从而，确保最重要的属性先被加入到目标集中。

输入： 邻域决策系统，NDT=；

输出： 约简后的属性集合core。

Step1:对于任意的属性a∈A，将对应的基因样本的值进行升序排列，得到样本值序列为xa1, xa2，xa3，xa4，…，xai，xan 。

Step2:设整型变量i、j，

当i=1时，

for (j=n; j>=1; j--)

if (Δ(xaj,xa1)≤δ) {x1,x2,…xj∈δ(x1 ); break ;}

Step3:当i>1时，

i++; j++;

for (k=j; k

if ((Δ(xak,xai)>δ)

{j=k-1;xi,xi+1,…xj∈δ(xi ); break ;}

Step4:重复第三步，直到i=n为止。

Step5:对于?坌a∈A，构建邻域关系矩阵；

Step6:令core=Φ；

Step7:对于每一个属性ai∈A-core，计算重要度

SIG(ai ,D,core)=γ(D,core∪ai )-γ(D,core);

Step8:筛选ak，使ak满足

SIG(ai ,D,core)= (SIG(ai,D,core) )。

Step9:if ak的重要度满足

SIG(ai,D,core)>0，

core=core ∪ ak;

go to Step3；

else

return core.

end.

3 实验结果与分析

基于单调邻域粗糙集的基因约简分类模型中，首先从基因表达谱获取基因知识，接着采用Relief算法[6]计算所有基因分值，并依据分值进行降序排列，选择包含大部分分类信息的前300个基因作为进一步约简的基础。然后，对选出的信息基因进行属性约简，提取出相应的特征基因。

为了验证基于单调邻域粗糙集的前向属性约简算法（DARNeM）的有效性，在两个公开的基因表达数据集上进行了实验。Liver cancer数据集（genome www.stanford.edu/hcc/） 包含有1648个基因、156个样本，其中82个HCCs子类和74个nontumor livers子类。Lymphoma数据集（llmpp.nih.gov/lymphoma）包含了4026个基因、96个样本，其中54个Othertype子类和42个B-cell lymphoma子类。实验数据集如表所示。

根据算法，首先，在Lymphoma和Liver cancer数据中，通过Relief

算法选出权重值较大的前300个基因，邻域阈值设为0.15，距离采用欧氏距离。与文献[5]中前向属性约简算法比较，得出的约简结果如表2。

实验结果表明，两种算法提取出的特征基因数相同，基于单调的属性约简算法，在计算样本属性邻域时的复杂度明显小于前向属性约简算法，前者时间复杂度的最大值为O(n*n)，而在实际的运算中，复杂度远远小于O(n*n)，有时甚至可以达到O(n)。而后者的时间复杂度均为O(n*n)。

4 结束语

本文在基于邻域粗糙集的前向属性约简算法的基础上，提出了在单调度量上的邻域求解方法，即基于单调邻域粗糙集的属性约简方法，该方法在不改变前向属性约简算法的分类约简能力的基础，降低了样本属性邻域求解的复杂度，提高了特征基因提取的效率。同时在研究过程中发现，不同的参数组合对数据集的分类准确率的影响是非常大的。但是，发现这些参数的最佳组合又是一件非常耗时的任务。在文献[4]中提到了可变精度阈值设置对分类精度和特征提取的影响，因此，提出一种有效的设置邻域值和可变精度阈值的方法有待研究。

参考文献：

[1] Pawlak Z. Rough Sets―Theoretical Aspects of Reasoning about Data. Dordrecht: Kluwer Academic, 1991.

[2] 常犁云,王国胤,吴渝.一种基于Rough Set理论的属性约简及规则提取方法[J].软件学报,1990,10(11):1206-1211.

[3] 胡清华, 赵辉, 于达仁.基于邻域粗糙集的符号与数值属性快速约简算法[J].模式识别与人工智能,2008,21(6):732-738.

[4] 胡清华,于达仁,谢宗霞.基于邻域粒化和粗糙逼近的数值属性约简[J].软件学报,2008,19(3): 640-649.

[5] 黄德双.基因表达谱数据挖掘方法研究[M].北京:科学出版社,2009.

[6] 焦娜,苗夺谦.基于相容关系的基因选择方法[J].计算机科学,2010, 37(10): 217-220.

[7] 王国胤. Rough集理论与知识获取[M].西安:西安交通大学出版社,2001.

[8] 孙丽君,苗夺谦.基于粒计算的特征选取方法[J].计算机科学,2008,35(4):14-15.

[9] Xu Jiucheng, Sun Lin. A New Knowledge Reduction Algorithm Based on Decision Power in Rough Set. Transactions on Rough Sets XII, Lecture Notes in Computer Science, 2010, 6190: 76-89.

[10] 孙丽君,苗夺谦.基于粗糙集的基因表达数据分类研究[J].计算机工程,2007,33(16):183-185.

[11] 苗夺谦, 胡桂荣.知识约简的一种启发式算法[J].计算机研究与发展,1999,36(6): 681-684.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文