一种加权K—均值基因聚类算法

姚登举+詹晓娟+张晓晶

摘要：针对微阵列表达数据集中基因-基因之间存在复杂相关关系的问题，基于随机森林变量重要性分数，提出了一种新的加权K-均值基因聚类算法。首先，以微阵列表达数据中的样本为对象、基因为特征，训练随机森林分类器，计算每个基因的变量重要性分数；然后，以基因为对象、样本为特征、基因的变量重要性分数为权重进行K-均值聚类。在Leukemia、Breast、DLBCL等3个微阵列表数据集上进行了实验，结果表明：所提出的加权K-均值聚类算法与原始的K-均值聚类算法相比，类间距离与总距离的比值平均高出177个百分点，具有更好的同质性和差异性。

关键词：微阵列表达数据；聚类分析；随机森林；K-均值

DOI：1015938/jjhust201702021

中图分类号： TP391

文献标志码： A

文章编号： 1007-2683（2017）02-0112-05

Abstract：In view of the complex correlation between gene and gene in the microarray data set， a weighted K mean gene clustering algorithm based on random forest variable importance score was proposed First， the proposed algorithm begins with training random forest classifier on the microarray data， using the samples as objects and the genes as features， variable importance scores were calculated for each gene； then， a weighted Kmeans clustering were performed with genes as objects， samples as features， and variable importance score as weighted value Experiments were carried out on Leukemia， Breast and DLBCL three datasets The experimental results show that the proposed weighted K mean clustering algorithm has an average of 177 percentage points higher than the original K mean clustering algorithm with respective to the ratio of the distance between the class and the total distance and has better homogeneity and difference

Keywords：microarray expression data； clustering analysis； random forest； Kmeans

0引言

聚类是将物理或抽象对象的集合分组为由类似的对象组成的多个集合的过程，其中属于同一个集合的对象之间彼此相似，属于不同集合的对象之间彼此相异[1]。聚类是机器学习和数据挖据中的重要研究内容，被广泛应用于经济、管理、地质勘探、图像识别、生物医学、生物信息学等领域中[2-6]。随着高通量测序技术（Highthroughput Sequencing）的迅速发展，各物种的基因表达数据（Gene expression data）出现了爆炸式增长，同时大量的基因表达数据能够在公共数据库（如由美国NCBI管理和维护的GEO数据库、由美国斯坦福大学管理和维护的SMD数据库、由欧洲EBI管理和维护的ArraryExpress数据库和由日本多所大学合作提供的CGED数据库等）中得到[7-11]。在基因表达数据分析任务中，基因聚类分析有着非常广泛的应用。当前，基因聚类分析方法主要有三类：基于基因的聚类（Genebased clustering）、基于样本的聚类（Samplebased clustering）和两路聚类（Biclustering）[12，13]。基于基因的聚类将基因看成聚类的对象，将样本看成描述基因的特征，表达模式类似的基因（即共表达的基因，Coexpression gene）通常被划分为同一类，一般具有相同的功能，因此可以根据聚类中已知基因的功能推断某些未知基因的功能；基于样本的聚类则以基因为特征，以样本为对象，通过样本聚类，可以发现样本的显性结构（Phenotype structure），自动对病理特征或实验条件进行分类；两路聚类是指同时对基因和样本进行的聚类，目的是找出在某些条件下参与调控的基因聚类以及与某些基因相关联的条件，从而更精确、更细致地探索基因和样本间的相互关系。

基因聚类的主要对象是基因表达微陣列数据。原始的基因表达微阵列数据中存在着大量的冗余基因、噪声基因和不相关基因，并且研究表明，对于某类疾病的发生发展，通常是多个基因共同作用的结果，亦即基因表达微阵列中多个基因之间存在着复杂的相互作用，所以一般的基于统计的度量标准，如皮尔森相关系数、信息熵等，难以准确地表达基因的相对重要性[14]。随机森林作为一种流行的机器学习算法，由于在训练决策树的过程中，既考虑了单个变量对于目标变量的影响，又考虑了多个变量之间的相互作用，其变量重要性分数被广泛应用于评价数据集中特征变量的相对重要性，尤其是应用在生物医学与生物信息学研究中[15-17]。当前，基于随机森林和K-均值聚类相结合的方法已经被应用在网络入侵检测[18]等研究中，然而在基因聚类任务中，基于随机森林变量重要性分数对基因进行加权聚类研究较少，仍然是一个值得探索的领域。本文主要针对基于基因的聚类分析任务，将随机森林的变量重要性分数引入到K-均值聚类的过程中，提出了一种基于随机森林变量重要性分数的加权K-均值聚类算法，能够提高基因聚类结果的质量。

1算法设计

12随机森林

随机森林（Random Forest，RF）[19]是一个由一组决策树分类器{h（X，θk），k=1，2，，K}组成的集成分类器，其中θk是服从独立同分布的随机向量，K表示随机森林中决策树的个数，在给定自变量X下，每个决策树分类器通过投票来决定最优的分类结果[5]。随机森林是许多决策树集成在一起的分类器，如果把决策树看成分类任务中的一个专家，随机森林就是许多专家在一起对某种任务进行分类。生成随机森林的步骤如下[20]：

1）从原始训练数据集中，应用Bootstrap方法有放回地随机抽取K个新的自助样本集，并由此构建K棵分类回归树，每次未被抽到的样本组成了K个袋外数据（outofbag， OOB）。

2）设有n个特征，则在每一棵树的每个节点处随机抽取mtry个特征（mtry<=n），通过计算每个特征蕴含的信息量，在mtry个特征中选择一个最具有分类能力的特征进行节点分裂。

3）每棵树最大限度生长，不做任何剪裁。

4）将生成的多棵樹组成随机森林，用随机森林对新的数据进行分类，分类结果按树分类器的投票多少而定。

由于决策树算法在节点分裂过程中考虑了特征之间的相互影响，随机森林算法能够有效地揭示多个特征之间的相互作用，对于单个特征具有小的边际效应但多个特征的组合对目标变量有较大影响的数据集合，表现出优异的分类和预测性能，而且随机森林算法不需要先验假设[7]。目前，RF已经被广泛应用于各种分类、预测、变量重要性研究、特征选择以及异常点检测问题中，尤其在生物医学和生物信息学领域，随机森林由于能识别多个特征变量之间的相互作用而受到青睐[21-22]。

随机森林算法的一个重要产物是变量重要性分数，它可以很好地反映训练数据集中分类变量对于目标变量的影响程度，目前，随机森林变量重要性分数已经被广泛应用于各种数据挖掘任务中。随机森林提供了4种变量重要性分数供选择，本文采用基于置换的变量重要性分数[16]。基于置换的变量重要性分数定义为在袋外数据（OOB）上当变量发生轻微扰动前后分类模型的分类正确率的平均减少量，它采用了直觉排列策略，既考虑到每一个变量单独的影响，又考虑了多个变量之间的相关作用。

给定训练样本集合D，集合中的特征标记为Xj，j=1，2，，N，Xj的基于置换的变量重要性分数表示为IMj，则IMj的计算过程如下[20]：

1）对训练集D进行Bootstrap随机重采样B次，得到B个样本子集Db，b=1，2，，B；

2）设置b=1；

3）在样本集合Db上训练决策树Tb，袋外数据标记为Loobb；

4）在袋外数据Loobb上，应用决策树分类器Tb对测试数据进行分类，正确分类的样本个数标记为Roobb；

5）对特征Xj，j=1，2，，N，随机地扰动Loobb中每一个样本直到它与目标变量的原始关系被打断，扰动后的数据集标记为Loobbj；

6）在扰动后的数据集Loobbj上，应用决策树分类器Tb对数据进行分类，正确分类的样本个数标记为Roobbj；如果特征Xj与目标变量相关，那么分类器的分类性能将明显降低；

7）对于b=2，，B，重复第3）-6）步；

8）按照下式计算特征Xj的变量重要性分数：

IMj=1B∑Bi=1Roobb-Roobbj；

9）输出所有特征的重要性分数：

IM={IM1，IM2，，IMN}。

13基于随机森林变量重要性分数的加权K-均值基因聚类算法

基因数据通常以DNA微阵列表达数据形式存储。一般而言，微阵列表达数据集是一个N×（M+1） 的矩阵，矩阵中的每一行表示一个样本，除最后列以外的每一列表示该样本的一个基因，每一个元素gi，j是一个数值，表示第i个样本第j个基因的基因表达水平，最后一列表示第i个样本的类标签，如图1所示。

g1，1g1，2…g1，MC1

g2，1g2，2…g2，MC2

……………

gN，1gN，2…gN，MCN

2实验与结果分析

21数据集

为了验证本文提出的算法的有效性，在Leukemia（白血病）、Breast（乳腺癌）、DLBCL（弥漫性大B细胞淋巴瘤）等3个微阵列表数据集上进行了实验。这些数据集的基本信息如表1所示。

原始的微阵列表达数据集中通常包含大量的噪声基因，为了降低计算时间和存储空间需求，在执行基因聚类分析之前首先采用四分位距方法和单因素方差分析法来过滤掉明显不相关的基因和噪声基因，所有表达水平低于总体IQR 1/5的基因在这一步被过滤掉。基因过滤后的数据信息如表2所示。

23实验结果及分析

在3个实验数据集上对原始的K-均值算法和本文提出的基于随机森林变量重要性分数的加权K-均值算法进行了实验，指定聚类数目k=100，最大迭代次数T=60。采用类内离散度和J和类间加权距离和D指标来衡量算法的性能，10次实验结果的平均值如表3所示。

从表3可以看出，本文提出的基于随机森林变量重要性分数的加权K-均值聚类算法的J值明显低于原始的K-均值算法，说明类内基因表达模式高度相关；所提出的算法的R值比原始的K-均值算法平均高177个百分点，表明基于随机森林变量重要性分数的加权K-均值聚类算法得到的聚类划分中，类间差异比原始的K-均值聚类算法显著。

3结语

提出了一种基于随机森林变量重要性分数的加权K-均值基因聚类算法，相对于原始的K-均值聚类算法，该算法能够有效地提高类内相似度和类间差异度，即提高聚类结果的质量。如何针对基因表达数据的特点，选择或设计合适的聚类准则函数，利用本文提出的算法探索生物医学信息，有待于进一步研究。

参 考 文 献：

[1]周志华.机器学习[M].北京：清华大学出版社，2016：211-213

[2]刘帅，林克正，孙旭东，等.基于聚类的SIFT人脸检测算法[J].哈尔滨理工大学学报，2014，19（1）：31-35

[3]吴娱，钟诚，尹梦晓.基因表达数据的分层近邻传播聚类算法[J].计算机工程与设计，2016，37（11）：2961-2966

[4]陈伟，程咏梅，张绍武，潘泉.邻域种子的启发式454序列聚类方法[J].软件学报，2014，25（5）：929-938

[5]黄伟华，马中，戴新发，徐明迪，高毅，刘利民.一种特征加权模糊聚类的负载均衡算法[J].西安电子科技大学学报（自然科学报），2017，44（2）：138-143

[6]余晓东，雷英杰，岳韶华，王睿.基于粒子群优化的直觉模糊核聚类算法研究[J].通信学报，2015，36（5）：1-7

[7]李霞，雷健波，李亦学，李劲松.生物信息学[M].北京：人民卫生出版社，2015：286-287

[8]李雨童，姚登举，李哲，侯金利.基于R的医学大数据挖掘系统研究[J].哈尔滨理工大学学报，2016，21（2）：38-43

[9]高敬阳，齐飞，管瑞.基于高通量测序技术的基因组结构变异检测算法[J].生物信息学，2014，12（1）：5-9

[10]李晟，程福东，孙啸.高通量DNA测序技术与疾病诊断及预防[J].生物医学工程与临床，2016，20（2）：210-215

[11]吴林寰，陆震鸣，龚劲松，史劲松，许正宏.高通量测序技术在食品微生物研究中的應用[J].生物工程学报，2016，32（9）：1164-1174

[12]岳峰，孙亮，王宽全，王永吉，左旺孟.基因表达数据的聚类分析研究进展[J].自动化学报，2008，34（2）：113-120

[13]张国印，程慧杰，刘咏梅，姚爱红.一种新算法在基因表达谱聚类中的应用[J].计算机工程与应用，2009，45（36）：216-218

[14]王爱国.微阵列基因表达数据的特征分析方法研究[D].安徽：合肥工业大学，2015：1-5

[15]ALI Anaissi， PAUL J KENNEDY， Madhu Goyal1 Daniel R Catchpoole A Balanced Iterative Random Forest for Gene Selection from Microarray Data[J] BMC Bioinformatics， 2013， 14： 261P

[16]QI， Y Random Forest for Bioinformatics [J]. Ensemble Machine Learning， 2012： 307-323

[17]孙磊，许驰，胡学龙.一种基于随机森林的长非编码RNA预测方法[J].扬州大学学报：自然科学版，2016，19（4）：50-53

[18]ELBASIONY R M， SALLAM E A， ELTOBELY T E， et al A Hybrid Network Intrusion Detection Framework Based on Random Forests and Weighted kmeans [J]. Ain Shams Engineering Journal， 2013， 4（4）：753-762

[19]BREINMAN L Random Forests [J]. Machine Learning， 2001， 45： 5–32

[20]姚登举，杨静，詹晓娟.基于随机森林的特征选择算法[J].吉林大学学报工学版，2014，44（1）：137-141

[21]VERIKAS A，GELZINIS A，BACAUSKIENE M Mining Data with Random Forests： A Survey and Results of New Tests [J]. Pattern Recognition， 2011， 44： 330–349

[22]刘勘，袁蕴英，刘萍.基于随机森林分类的微博机器用户识别研究[J].北京大学学报（自然科学版），2015，51（2）：289-300

（编辑：王萍）