基于马氏距离的缺失值填充算法

收稿日期:2005-06-03；修订日期:2005-08-22 基金项目：湖南省自然科学基金(03JJ Y3095)

作者简介：杨涛(1977-)，女，四川内江人，硕士研究生，主要研究方向：生物基因数据挖掘; 骆嘉伟(1964-)，女，湖南长沙人，副教授，主要研究方向：生物信息处理、数据挖掘; 王艳(1981-)，女，湖南邵阳人，硕士研究生，主要研究方向：数据挖掘; 吴君浩(1981-)，男，湖南怀化人，硕士研究生，主要研究方向：生物序列数据挖掘.

文章编号:1001-9081(2005)12-2868-04

基于马氏距离的缺失值填充算法

杨涛，骆嘉伟，王艳，吴君浩

(湖南大学计算机与通信学院，湖南长沙410082)

(taox tao @ m )

摘要：提出了一种基于马氏距离的填充算法来估计基因表达数据集中的缺失数据。该算法通过基因之间的马氏距离来选择最近邻居基因，并将已得到的估计值应用到后续的估计过程中，然后采用信息论中熵值的概念计算最近邻居的加权系数，得到缺失数据的填充值。实验结果证明了该算法具有有效性，其性能优于其他基于最近邻居法的缺失值处理算法。

关键词：微阵列；缺失值估计；马氏距离；信息熵中图分类号:TP311.13 文献标识码:A

M issi ng va l ue esti m ation for gene expressi on data

based on M ahalanobis distance

YANG Tao ,LUO Jia -w e,i WANG Yan,WU Jun -hao

(C ollege of Computer and Comm unications,H unan Uni versity,ChangshaH unan 410082,Chi na)

Abstract :A i m pu tati on m ethod based on M aha l anob i s distance was proposed t o esti m ate m i ssi ng va l ues i n t he gene

expression data .T he nearest ne i ghbors were chosen by t he M aha l anob i s distance bet w een g enes ,and t hen the concept of en tropy w as utili zed to ob tain esti m ations of m i ssi ng values .T he i m puted va l ues w ere used for the l a ter i m putati on .Expe ri m en ts prove t hat the m et hod is va li d and its performance is higher than the o t her i m pu tati on m ethods based on k -nearest ne i ghbors for gene expressi on data .

K ey words :m icroarray ;m iss i ng v al ue esti m ati on ;M ahalanobis d i stance ;entropy

0 引言

DNA 微阵列技术[1]

可以同时监测并获得各种环境下的

成千上万个基因表达水平值，将基因的活动状态比较完整地展现出来。微阵列实验获得的基因表达数据通常是以大矩阵的形式表现的，矩阵的行表示基因的表达水平值，而矩阵的列表示试验条件。由于DNA 微阵列试验的各个步骤中存在有许多非理性的因素[2]，如：不完全分解、图像损坏、表面有灰尘或划痕、试验错误等，造成获得的基因表达数据中常常包含缺失值。

为了从大量的基因表达数据中提取潜在的生物事实和意义，通常采用分类、聚类等各种数据分析方法，如多元监督分类法中的支持向量机(S VM s)[5]、主成分分析(PCA )[6]和单值分解法(S VD )[7]等，这些方法都要求输入完整的数据矩阵，不能对存在有缺失值的数据进行分析。如果使用填充值代替缺失值进行数据分析，则填充值的准确性会直接影响分析结果。因此，为了保证数据分析和处理的正确性和有效性，确保提供有效的数据，对缺失值进行正确的处理是一个非常重要的预处理过程。

解决生物数据缺失的一个方法就是重复试验[8]，但是这个方法的代价太高，非常耗时，在实际运用中不可取。还有一些处理缺失值的简单方法如直接删除或忽略缺失值、使用

00值填充或者使用样本数据的平均值代替[9]

，这些方法都存在着很大的不足与缺陷，未考虑数据的属性和数据之间的

相关性，没有充分利用数据集所蕴涵的有价值的信息。近年

来，在基因表达数据缺失值问题处理上提出了一些更为准确、复杂的方法，如单值分解法[10]、基于最近邻居法的缺失值填

充算法KNN i m pute [10]

、基于贝叶斯公式填充方法[11]以及基于最小平方原则的基因表达缺失值的处理算法[12]。这些算法基于不同模型、从不同角度研究了基因表达数据中缺失值的处理问题。其中,KNN i m pute 是一种简单、快速的算法，它利用本身具有完全值的相似基因的表达值实现对缺失数据的估计。在KNN i m pute 算法的基础上，文献[13]提出了一种新的基于最近邻居的缺失值填充方法)))有序最近邻居算法(SKNN )，不仅利用了现有的具有完全值的基因，而且考虑了经过缺失值填充后的基因所包含的信息，使得在缺失率较大的情况下，也能获得比较好的性能。虽然KNN i m pute 和SKNN 两个算法对基因表达数据中的缺失值填充有较好的性能和准确度，但是二者都是根据欧氏距离选择相似基因，欧氏距离与各指标的量纲有关，且没有考虑各变量之间的相关性和重要性，可能会造成相似基因的选择并不是最佳选择；

而且在计算其估计值时，各邻居基因的加权系数也是根据欧氏距离来确定的，从而影响估计结果的准确度。

针对KNN i m pute 和SKNN 的缺失值填充算法的不足之处，本文提出一种新的基于马氏距离的缺失值处理算法MKNN 。该算法采用了一种新的相似基因度量指标)))马氏距离，它不仅考虑了观测变量之间的相关性，而且也考虑到了各个观测指标取值的差异程度，能更好地描述基因之间的相似程度。

第25卷第12期

2005年12月

计算机应用

C o mpu ter App lications

V o.l 25No .12

Dec .2005

然后利用信息论中熵值的概念，通过基因之间的马氏距离提

供的信息决定各个相似基因的加权系数，其相应位置的加权平均值即为缺失数据的估计值。

1 KNN 与S KNN 算法

1.1 KNN 算法

文献[10]提出的基于最近邻居的缺失值填充算法

KNN i m pute 考虑了基因表达数据之间的相关性，因而预测结果较为准确。通过指定最近邻居基因数为K，根据邻居基因提供的信息，对微阵列数据集中的缺失值进行预测和估计。KNN i m pute 算法首先根据目标基因(包含有缺失值的基因)与其他具有完全值的基因之间的欧氏距离，在数据集中选择与目标基因的距离最小的K 个最相近邻居基因，然后对选择出的K 个最近邻居基因赋予相应的权值，其相应位置值的加权平均值即为目标基因缺失数据的估计值。

KNN 算法流程的伪代码描述:

I npu t :Gene D ata[][]:Gene express i on dat a w it h m i ss i ng va l ues ,K :t h e num ber of nearest neighbors ;Ou t put :Est Data[][]:gene express i on dat a w it h esti m ati on val ue ;(1)In i ti ali ze data ,con struct experi m ent data m atri x ;

(2)Co m pu te t he Eu cli d i an distance d i (z i ,z)=(z i -g )T (z i -g ),

g i s t he t arget ge ne w hic h con t ai ns m i ss i ng val ues ;(3)Select K cl osest gen es as nearest ne i ghbor gen es from data set based on Eucli d i an d i stan ce ;(4)Calcu l ate the w ei ght of the nearest n ei ghbor genes :

w i =1/d i

k i=1

1/d i

;

(5)E sti m ate the m issi ng val u e :g ~=

E k

i=1

w i x i ,x i is the corres pond i ng exp ress i on val ue i n t he nearest gen es .

1.2 SKNN 算法

文献[13]提出的有序最近邻居的缺失值填充算法S KNN 是在KNN i m pute 算法基础上发展而来的，二者选择最近邻居基因的度量指标和计算邻居基因加权系数的方法均相同。作为KNN i m pute 的改进算法,S KNN 主要在两个方面不同于KNN 方法:1)根据数据集中的缺失率进行排序，从缺失率最小的基因开始填充;2)SKNN 算法不仅利用数据集中具有完全值的基因，还将经过S KNN 算法处理后的具有完全值的基因加入到相似基因的选择范围内，因此即使在缺失率较大的情况下，也能获得比较好的性能。在S KNN 算法中，对包含有缺失数据的基因只需一次相似基因的选择过程，即可对其中的所有缺失值同时进行填充，而不同于KNN i m pute 需对每个缺失数据均进行相似基因的选择过程，这样就减少了执行时间。通过上述的改进,S KNN 算法在数据缺失率大的情况下具有较好的性能和实用价值。

2 基于马氏距离的缺失值填充算法MKNN

在前面分析的KNN i m pute 和SKNN 算法中，两者在选择最近邻居基因时都是以欧氏距离为度量指标，但是欧氏距离具有两个主要的缺点:1)欧氏距离的值与各指标的量纲有关,

而各指标计量单位的选择有一定的人为性和随意性，而且任何一个变量计量单位的改变都会使此距离的数值改变，从而使该距离的数值依赖于各变量计量单位的选择;2)欧氏距离的定义没有考虑各个变量之间的相关性和重要性。实际上,

欧氏距离是把各个变量都同等看待，将两个样本在各个变量

上的离差简单地进行了综合。

为了克服上述欧氏距离的缺点，本文采用马氏距离来度量基因之间的相似程度，马氏距离相对于其他距离如欧氏距离而言具有以下优点[14]:1)马氏距离是欧几里德空间中非均匀分布的归一化距离，不用考虑各特征参数的量纲;2)马氏距离是根据整个空间上的特征分布情况来作为判别依据的，排除了样本之间的相关性影响。因此，它能更好地描述基因之间的相似性，为更高一级的数据分析提供有效的数据。在信息论[15]中，熵值是系统无序程度或混乱程度的度量，信息被解释为系统无序程度的减少，其表现为系统的某项指标的变异度。熵值越小，不确定性越小，则它所蕴涵的确定性信息就越大；反之，熵值越大，不确定性越大，则它所蕴涵的确定性信息就越小。

在KNN i m pute 和SKNN 算法中，计算缺失数据估计值使用的加权系数是通过欧氏距离的简单计算得到的，并不能准确反映各最近邻居对含有缺失值的目标基因的影响。本文从信息论的观点出发，利用信息熵的概念，计算最近邻居的加权系数，最终得到缺失数据的填充值。

基于马氏距离的缺失值填充算法由以下三个主要部分组成:

2.1 基因数据降维处理

通常来说从试验中得到的数据规模很大，具体表现为基因数目繁多，而试验条件相对较小，一般在20~100范围内。在数量众多的基因中，不是所有基因都对包含有缺失值的目标基因有意义，其中存在有不相关或相关较小的基因，而且当变量较多时，会增加马氏距离的计算复杂度。因此对数据集进行降维处理，减少后续工作的计算量和复杂度。

采用对基因表达数据集进行相关性分析方法，根据基因之间的相似程度对基因进行筛选，计算过程中使用行平均值代替存在的缺失值。基因之间的相似系数越大，它们就越相近，就越能准确描述目标基因的信息。

设目标基因g =[g 1,g 2,,,g m ]T ，则与基因z i =[z i 1,z i 2,,,z i m ]T 之间的相似系数计算公式为: C i =

k =1

(g k -g )(z ik -z i )

[

k =1

(g k -g )2][

k =1

(z ik -z i )2]

,i =1,2,,,n

(1)

其中:g =

1m E m

k =1g k ,z i =1

m E

k=1z ik

,n 为基因总数。在对数据进行降维处理时，选择与目标基因相似度大的基因作为后续工作的处理数据，并且考虑试验条件的个数(列)。一般说来，当相关系数r 在[0.5,0.8]之间时，二者为显著相关,r 在[0.8,1]之间时，二者为高度相关，当r =1时，两者的关系为完全相关[16]。为了适应各种数据集的规模大小，预选择相似基因数通过下述公式获得:

n c =n n <5m

5m 5m <n <10m

10m n >10m

(2)

其中,n 为基因总数,m 为实验条件数,n c 为筛选后得到的相似基因数。2.2 计算基因之间的马氏距离

马氏距离不仅考虑了观测变量之间的相关性，而且也考虑到了各个观测指标取值的差异程度，从而弥补了欧氏距离

2869第12期杨涛等：基于马氏距离的缺失值填充算法

的不足，能更好地描述基因之间的相似性。其计算公式为:

d i =

(g -z i )T r

-1

(g -z i ),i =1,2,,,n c

(3)

其中g =[g 1,g 2,,,g m ]T ,z i =[z i 1,z i 2,,,z i m ]T ,g 为包含有缺失数据的目标基因,z i 属于矩阵Z c ,Z c 是经过降维处理后得到的基因表达数据矩阵，且g X z i 。r 表示观测变量之间的协方差矩阵。若总体协方差矩阵r 未知，则用样本协方差矩阵代替。从Z c 中选择具有典型代表性的基因作为代替总体的样本抽样，即选择与z 相关性较强的基因。当n c <2m，则选取前m 个相似系数大的基因作作为代替总体的一个样本；其他情况，则从数据集Z c 中选取2m 个与g 相似系数大的基因作为代替总体的两个样本。总体的协方差r 为:

r =s

n c <2m,s 为样本协方差1

(s 1+s 2)n c\2m;s 1,s 2为样本协方差

(4)

2.3

估计目标基因的缺失值

根据计算得到的马氏距离，选择距离最短的K 个基因作

为目标基因g 的最近邻居，然后通过这K 个邻居基因提供的信息，对目标基因中缺失值进行预测和估计。本文采用对相似基因进行加权平均形式的预测模型，对目标基因中的缺失值

进行估计。预测的核心问题就是如何求出加权系数，使得结果具有较高的预测精度。

本文利用信息论中熵值的概念，确定各最近邻居基因在对缺失值估计时的加权系数，其步骤如下:

(1)将计算得到的K 个最近邻居基因的马氏距离单位化:

p i =

d i

E k

i=1

,i =1,2,,,k

(5)

d i 为第i 个邻居与目标基因之间的马氏距离。显然,

E k

i=1

=1。

(2)计算第i 个邻居基因的熵值:h i =-mp i l n p i ,i =1,2,,,k (6)

其中,m 为大于0的常数，且m =(l n k )-1,l n 为自然对

数。

(3)计算第i 个邻居基因的变异程度系数:

当心生活中的核辐射因为0[h i [1，根据熵值的大小与其变异程度相反的原则，所以定义第i 个相似基因的变异程度系数为:

v i =1-h i ,i =1,2,,k

(7)(4)计算第i 个邻居基因的加权系数:w i =

1k -1

1-v i

E k

i=1v

,i =1,2,,,k

(8)

某个相似基因的变异程度越小，其包含的确定性信息就

越大，则其在预测中对应的加权系数就越大，反之就越小。所有的加权系数满足:

i=1

w i =1。

(5)计算预测值:

目标基因g 中的缺失值可由下列公式计算获得:g ~

长江三角洲经济圈

E k

i=1

不公平的游戏

i离子刻蚀

@x i ,i =1,2,,,k

(9)

其中x i 为相似基因中与缺失值对应位置的表达水平值，计算得到的g ~

值即为目标基因中缺失数据的估计值。

2.4 算法的伪代码描述

Input :GeneDat a[][]:Gene express i on data w ith m i ss i ng val ues ,

K :the nu m ber of nearest n ei ghbors ;Output :E st Data[][]:genes exp ressi on data w i th esti m ati on val u e ;(1)Co m pute t h e average val ues of t he gen es t hat con tai n m i ss i ng

val ues ;(2)Rep l ace m i ssing values w ith correspond i ng average val u e ;

(3)Co m pu t e t h e correl ativit y of the t arget gen e g and ot h er gene z i ;(4)S el ect t h e s i m il ar genes for g on t he basis of correl ativit y ,obtai n n e w m atri x Z c ;(5)Co m pu t e t h eM ahalanob i s d i stance of g and other gene z i i n Z c ;(6)S el ect k clos est gen es as nearest nei ghbor gen es f or g;and co m pute

the w ei gh ted value of each nearest gene ;(7)Obtai n the esti m ati on ofm i ss i ng val ues i n g;

3 实验结果分析

3.1 实验方法

基因表达数据可从开放的公共基因数据库获取，本文实验所用数据集分别在下述研究中使用：识别酵母中能调节细胞周期的基因的研究[17]、酵母从发酵到氧化过程中新陈代谢变化对应的临时基因表达的探索研究[18]、在酵母中环境变化引起的基因表达变化的研究[19]。前两个数据集是时间序列数据，其中一个包含的噪声较小，称其为时间序列；另一个则有较大的噪声，称为噪声时间序列；最后一个为非时间序列数据集。

从数据库中获取的数据本身可能会包含有缺失值，如果直接作为实验数据，则得到的结果无法进行评价，因此需要将其中包含有缺失数据的行和列删除，人为地获得完整的数据集。在获得的完整的数据

集中，根据算法的需要随机删除一定比例的数据产生测试数据，然后再使用各种算法来恢复测试数据中的缺失值，并将估计值与真实值进行比较。

对各种算法的缺失值估计算的性能采用均方根误差(R oo tM ean Squared error ,RM S error )来评价:

RM S error =

i=1

(R i -I i )2N

(10)

其中,R i 为真实值,I i 是估计值,N 为缺失值个数。计算得到的RM S error 的值越小，其估计值就越准确，反之结果就越差。

本文从各种数据缺失率和不同的最近邻居个数两个方面来测试M KNN 算法的性能，并与KNN i m pute

和SKNN 算法的实验结果进行比较。3.2 实验结果

分别使用时间序列、噪声时间序列和非时间序列三个不同类型的数据集，产生不同数据缺失率的测试数据，测试三种算法的性能。对时间序列数据集，使用不同的最近邻居数来获得各种算法的R M S err o r 值。

从实验结果中可以得出，算法MKNN 的性能优于KNN i m pute 算法和SKNN 算法。在KNN i m pute 算法中，数据缺失率对算法的影响很大。因为当缺失率较大时，相似基因的选择范围就会变得很小，可能造成选择的基因的相似性并不高，因

而当缺失率到一定程度时，性能会急剧下降。而在S KNN 算法中，不仅利用数据集本身具有完全值的基因，而且还利用了经过算法处理后的具有完全值的基因所蕴含的信息，使其也作为选择相似基因的候选基因。这样，即使在缺失率大的情

2870 计算机应用基因敲除

2005年

况下也能比KNN i m pute 选择出更为相似的基因，从而提高了性能和准确度。在算法MKNN 中，摒弃了前两种算法中使用的欧氏距离，采用马氏距离来选择最相似基因，并同S KNN 一样，充分利用经过

M KNN 算法处理后的具有完全值的基因，而且采用信息论中熵的概念计算最近邻居的加权系数，能更准确地反映各相似基因对目标基因的贡献大小，使得最终得到的缺失数据的填充

值更为准确。

图1 各算法对时间序列数据处理的RM S er ror

值

图2 各算法对噪声时间序列数据处理的RM S er ror

值

图3 各算法对非时间序列数据处理的RM S er ror

值

图4 邻居数对各算法的RM Serror 值影响变化图注：图1~图4中的KNN 为KNN i m pute 的简写

4 结语

本文采用马氏距离作为基因之间相似性的度量指标，并利用信息熵的概念，提出了一种对基因表达数

据中缺失值的填充算法MKNN 。将M KNN 算法应用到时间序列、噪声时间序列和非时间序列三种不同类型的数据集中，分析其性能，并与同类算法KNN i m pute 和S KNN 进行比较，实验结果表明M KNN 算法是一个有效的基因表达数据缺失值的填充算法。参考文献:

[1] DUDO I T S,YANG Y H,CALLO W M J ,et a l .Statisti calm et hods for -i

dentif y i ng d i ff eren tiall y expressed genes i n rep licated cDNA m icroar -ray experi m en ts[J].S tatistica S i n i ca ,2002,12(1):111-139.[2] ARBE I TMAN M N ,FURLONG EE M,I MAM F ,et a l .Gene expres -sion duri ng t he life cycle of Drosoph il a m el anogaster[J].Sci en ce ,2002,297(5590):2270-2275.

[3] GASCH AP ,SPELL M AN PT ,KAO CM,et a l .Genom ic express i on

progra m s i n the res pon s e of yeast cells to environm ental changes[J].M olecu lar B i ology of the C ell 2000,11:4241-4257.

[4] BOHEN SP ,TROYANSKAYA OG ,ALTER O,et a l .Vari ati on i n

gen e exp ress i on patter n s i n f olli cu lar l ympho m a and the res pon s e to rit ux i m ab[J].P roc N atl Acad S c,i USA,2003,100(4):1926-1930.

[5] BRO W NM P ,GRUNDY W N ,L I N D,et a l .Kno w ledge -based ana l ysis

ofm i croarray gene expression dat a by u si ng s upport vect or m ach i nes [J].Proc .Natl Acad.Sc,i USA ,2000,97,262-267.

[6] RAYCHA UDHURI S,STUART J M,ALT M AN R .Pri n ci pal co m po -nents ana l ysis t o s umm ariz e m i croarray experi m ents :app lication to sporu lati on ti m e seri es[J].Pac .Sy m p.15B i oco m put .,2000,455-466.

[7] ALTER O ,BRO W N PO ,BOTSTE I N D.S i ngular val ue decompositi on

for geno m e -w i de expression data processi ng and m odeling[J ].Proc .NatlA cad.Sc.i USA,2000,97(18):10101-10106.

[8] BUTTE A J ,YE J ,NIEDERFELLNER G,e t a l .Deter m i n i ng s i gn if-i

can t f ol d d ifferen ces i n gene expression anal ys i s [J ].Pac .Symp.B i oco mpu t .,2001,6:6-17.

[9] ALIZADEH AA,E ISEN M B,D AVIS RE,et a l .D isti n ct t yp es of d i-f

f u se l arge B -cell l y m pho m a i den tified by gene expressi on profili n

g [J].Nature ,2000,403,503-511.

[10] TROYANSKAYA O ,CANTOR M,SHERLOCK G ,et a l .M i ss i ng

value esti m ati on m ethods for DNA m icroarrays[J].B i o i nfor mati cs ,2001,17:520-525.

[11] SH I GEYUK I OBA ,M ASA -AK I SATO ,ICH I RO TAKEM ASA ,et

al .A B ayesian m i ss i ng val u e esti m ati on m ethod for gene express i on p rofile dat a[J].B i o i nfor m ati cs ,2003,19(16).

[12] K I M Y H,GOLUBZ G H,PARKY H.M issi ng Value Es ti m ation f or

DNA M icroarrayG ene Expression D ata :LocalLeast Squares I m pu-t ati on[J].B i oi n f or m atics ,2004.

[13] K I -YEOL K I M ,BYOUNG-JI N K I M ,GWAN-SU YI .Reu s e of i m -pu ted data i n m i croarray anal ys i s i ncreases i m putati on effici en cy [J].BM C B i oi n for m ati cs 2004,5:160.

[14] 何晓.多元统计分析[M ].北京：中国人民大学出版社,2004.[15] 傅祖芸.信息论)))基础理论与应用[M ].北京，电子工业出版

社,2001.

[16] 贾俊平.统计学[M ].北京：中国人民大学出版社,2002.[17] SPELL M AN PT,SHERLOCK G ,Z HANG M Q ,et al .C o mp rehen si ve

identificati on of cell cycle -regu l ated genes of t h e yeast Saccharo m y -ces cerevi s i ae by m icroarray hybrid i zati on[J].M ol B i ol Cel,l 1998,9(12):3273-3297.

[18] DERISI J L ,I YER VR ,BRO W N PO .Exp lori ng t h e m et ab olic and

geneti c contro l of gene xp res s i on on a geno m ic scale[J].Sci en ce ,1997,278,680-686.

[19] GASCH AP ,SPELL M AN PT ,KAO CM,et al .G eno m ic express i on

progra m s i n t he respon s e of yeast cells to env i ron m en tal changes [J].M o lB iolC el,l 2000,11(12):4241-4257.

2871第12期杨涛等：基于马氏距离的缺失值填充算法

氯化氢

本文发布于:2024-09-24 06:30:03，感谢您对本站的认可！

本文链接：https://www.17tex.com/xueshu/328628.html

上一篇：资产评估师 cpv 评估相关知识-经营预测与全面预算的概述

下一篇：反距离加权插值法例题_GMS插值中的反距离权重法（Inversedistanceweighted）