肿瘤基因表达谱数据聚类的谱方法研究

含其他人已经发表或撰写过的研究成果，也不包含为获得零徽粤或其他教学位论文作者签名：]岛隽学位论文作者签名：篙荡独创性声明学位论文版权使用授权书本学位论文作者完全了解宝韵叔大粤有关保留、使用学位论文的规定，和借阅。本人授权壶书敝孥以将学位论文的全部或部分内容编入有关数据库牛日6月年日6月红日l弓年6月oI≥年本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包育机构的学位或证书而使用过的材料。与我-MI作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书)签字日期：签字日期：2学位论文作者毕业去向：工作单位：通讯地址：导师签名：电话：邮编：zoI摘要基因表达谱数据的聚类分析研究是生物信息学研究的重点。肿瘤样本的聚类分析有助于发现新的肿瘤类型或亚型。通过样本的聚类，不仅能确定肿瘤的类别，同时可以根据已知聚类的肿瘤样本对未知聚类的样本进行预测和分类，从而帮助诊断。另外，对于不同肿瘤类型或同一肿瘤的不同亚型，可以通过找出信息基因或不同致病时期的信息基因，来研究肿瘤的病变及转移等机制。而对基因进行聚类可以帮助找出功能表达相似的基因，从而发现基因之间的调控关系，并发掘出具有研究价值的基因，并从中筛选药靶和诊断靶。本文提出了几种有效的基于谱图理论的聚类或半监督聚类算法，并将其应用于肿瘤基因表达谱的聚类分析中。通过构图的方法将基于数字序列的无结构信息的基因表达谱矩阵转化为具有结构信息的图结构，在使数据有效降维的同时，获取肿瘤样本的图结构的特征表示，并利用相关的图论算法对肿瘤样本进行划分与识别，同时分析了相应的实验结果。主要内容如下：1．提出一种改进的谱聚类方法。通过对基因表达谱数据构造概率矩阵，经奇异值分解(SVD)后提取前k个特征向量，并以此作为肿瘤样本的特征表示，运用模糊C均值(FCM)进行聚类分析。对比实验证明了该方法的有效性。2．提出一种基于谱隙和单位特征向量的谱聚类算法。首先，以肿瘤样本为图的节点构造Laplacian矩阵；然后，计算Laplacian矩阵的特征值和相应的特征向量，并利用谱隙序列的最大值确定该方法的聚类个数；最后，选取相同个数的特征向量作为原始样本的特征表示，并从单位化特征向量着手，以实现样本的聚类。通过模拟数据与癌症数据的实验，证明了该方法的有效性。3．提出一种基于Gauss．Seidel迭代的标记传播算法，并将其应用于基因表达谱数据分析。首先将高维基因表达谱数据表示为权值矩阵，同时定义一个表示样本类别属性的标记序列，并将其中少量样本标记为已知；然后利用根据Gauss—Seidel迭代算法推导出的迭代 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 更新标记序列，并证明了标记序列的解的收敛性；最后采用正负标记的方式，根据标记序列各分量的符号差异实现数据类别的划分。通过白血病和结肠癌数据集的实验，证明了该方法的有效性。关键字：基因表达谱，谱聚类，谱隙，单位特征向量，Gauss—Seidel迭代，标记传播安徽大学硕士学位论文摘要bioinformatics．Theinformation．Insimultaneously．Thedata．Then，thenormalizedproposedwithoutwithdatacorrespondingconstructed丽Ⅱldecomposition(SVD)，whichdata．Abstractsubtypes．Meanwhile，onCanbeneficialbetweenandcanclusteringsemi-supervisedanalysisdimensionalityeffectively．Meanwhile，werelevantanalyseexperimentalusingc-means(FCM)．laplacianemphasistumorsamplesthebasisofclustering，theclassified．Insametumor,theinformationdiseasesearchedresearchpathologicalmechanism．Geneoutsimilarimportantvalues，amongInmethodstheorymeansmethod，thematrixbasedway,thesamples．Combined、ⅣiⅡlgraph—theoreticalalgorithms，weclassifymainasimprovedalgorithmWasproposed．First，theextractedsingularregardedrepresentationsamples．Finally,theproblemmatrix、析tll安徽大学硕士学位论文Thegeneexpressionprofileiscontributesdiscoveringnewtypesknownunknownbepredictedaddition，fordifferentsubtypesvirulencegenesinperiodschangetransferhelpfindfunctionalexpression．Itdiscoverregulatecontrolrelationshipexploregenes、杭tllwhichwefilterdrugtargetsdiagnosistargets．thisdissertation,severaleffectivegraphwereintroducedintodata．Bydigitalsequencestructuraltranslatedoriginalreducedobtaincharacterbyrecognizeresultsfollows：1．AnspectralprobabilityfirstkeigenvectorsvaluefeaturesolvedFuzzy2．AEigengapUnitEigenvectoritappliedclusterThisconstructedtostructurecontentoronCallIImaximumeigengap．Then，theinformationdata．Then，theformulaweighteddata．Meanwhile，theandadjacentclusteringGauss—Seidellabelusingplus—minusClustering，Eigengap，UnitthenumberWasdeterminedsequence．Finally,theproblemdata．First,thematrixclasssamplesmarkedasfromconverged．Finally,thebasisKeywords：Gene安徽大学硕士学位论文肿瘤基因表达谱数据聚类的谱方法研究profiledatasobtainedcorrespondingeigenvalueseigenvectorsthrougheigenvaluedecomposition．Thedifferencebetweenwasdescribed、Ⅳitllbysearchingofeigengapsolveddirectlyuniteigenvector．3．Apropagationmethodbasediterationpresentedintroducedintoanalysisgeneexpressionconstructedwithsequenceindicatingdefined，whereseveralwerelabeledupdatediterativewhichinspiredsolutionprovedbesignssequence．ExpressionProfile，SpectralEigenvector,Iteration，LabelPropagationtoonallIllDNA芯片的应用与研究方向⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯42．6本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一123．2谱聚类⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．13第四章基于谱隙和单位特征向量的谱聚类算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。195．2半监督学习方法概述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．26目录摘要要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。I第一章绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11．1研究背景与意义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11．2基因芯片与基因表达谱数据⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯21．2．1基因芯片⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯21．2．2数据获取⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯31．2．3数据特点⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯31=3本文研究内容及组织结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯4第二章基因表达谱数据分析基础⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯62．1基因表达谱数据的数学描述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯62．2基因表达谱数据集⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯62．3基因表达谱数据的预处理⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯72．4传统基因表达谱分析方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯82．4．1特征提取与选择⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯82．4．2分类与聚类⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一12．5基于图论的基因表达谱分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．11第三章基于改进谱聚类的基因表达谱数据分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一13．1基因表达谱数据的Laplacian矩阵表示⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一133．3改进的谱聚类算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．143．3．1概率转移矩阵⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯1433．2模糊C均值⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．1433．3算法步骤⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。13．4实验结果与分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．163．5本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．14．1谱隙确定类别个数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯194．2基于单位特征向量的数据类别划分⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．2043基于谱隙和单位特征向量的谱聚类算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．204．4实验结果与分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．214．4．1模拟数据实验⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一2l4．4．2癌症数据实验⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一234．5本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．25第五章基于Gauss．Seidel迭代的标记传播算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．265．1引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯26安徽大学硕士学位论文Abstract⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．II1．2．403585．3高斯随机场与调和函数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．275．3．1高斯随机场⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一275．3．3调和函数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．285．4标记传播(LP)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．29LP算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一295．4．2局部和全局一致性方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一295．5基于Gauss．Seidel迭代的标记传播算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．30Gauss-Seidel迭代⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯305．5．2基于Gauss．Seidel迭代的标记传播算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一305．5．3收敛性证明⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一35．6实验结果与分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．325．6．1实验数据⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一325．6．2白血病数据实验⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一325．6．3结肠癌数据实验⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．335．6．4对比验证⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．355．7本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．36第六章总结与展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．376．1本文总结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．376．2研究展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．37参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯39攻读硕士学位期间发表的论文和参加的科研项目⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯475．3．2图的Laplacian算子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯28致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一46安徽大学硕二f：学位论文肿瘤基因表达谱数据聚类的谱方法研究5．4．15．5．1lV第一章绪论1．1研究背景与意义随着DNA芯片技术成为生命科学工作者研究的热点和重点，人类开始在分子水平上研究生命的本质。DNA芯片中所蕴含的不同人体及不同组织的基因数片数据较之前已更加容易，然而不同地理位置和环境对基因本体的影响，造成世界基因本体的差异性，使得获取具有研究价值的DNA芯片数据并不简单。研究表明，基因之间的相互作用和影响是一个复杂多样的网状关系，它们之间的调控关系可以通过DNA微阵列数据的分析得到证实，并且进一步揭示生命体的生理状态、病理过程以及疾病诊治方法等。DNA微阵列数据的典型缺点——较高的维度，通常会达到成千上万维，较低的样本数，通常仅有几十个，使得传统的DNA微阵列数据分析方法并不能很好地解决上述问题。因此，如何从较少的DNA芯片样本中分析出具有实际应用价值的信息，已成为生物信息学研究的重点和难恶性肿瘤是一类身心疾病，它不但是威胁人类生命健康的多发病和常见病，而且带给患者巨大的精神压力，忧郁、恐惧、绝望等情绪也随之而来。据世界卫生组织(WHO)报告，一九九零年的全球癌症发病率较一九七五年增长了百分之三十七点四，癌症新发病例数达到八百多万，全球癌症的死亡数在一九九七年约为六百二十万人。根据当前趋势进行预测，世界人口在二零二零年将达到八十亿，同时每年有两千万的新癌症人群，其中癌症死亡人数约为一千两百万人。据统计，肿瘤患者数量仍呈继续增长趋势，而且绝大多数将是发展中国家人口。因此肿瘤的预防和治疗是全世界生命科学研究者研究的焦点。生物信息学工作者依据组织形态的不同，把肿瘤分为不同的种类和不同的肿瘤亚型，临床中根据不同的肿瘤亚型给出不同的治疗方法。然而在临床上有个难点：临床症状相同，组织形态上相似的肿瘤，治疗方法却完全不相同，由此得出正确判断肿瘤的类型及亚型是临床治疗的首要条件【M】。随着DNA微阵列技术的不断发展，DNA微阵列数据获取的数量越来越庞大，同时数据的准确性越来越高。DNA微阵列技术的一个重要分支就是肿瘤基据信息的总和称为DNA微阵列数据或基因表达谱数据。虽然目前获取DNA芯点。安徽大学硕士学位论文第一章绪论1．2基因芯片与基因表达谱数据1．2．1基因芯片因表达谱技术，该技术为肿瘤学研究提供了全新的研究手段，并且逐渐地受到临床肿瘤研究的重视。肿瘤基因表达谱数据的分析研究主要是利用微阵列数据来识别肿瘤类型，同域，从而认识繁杂的生物过程和生命本质，如发育、衰老和肿瘤等。它可以帮助人们掌握肿瘤的病变机制从而对癌症患者进行准确的医学临床诊断和治疗，同时在疫苗和药物研究、基因数据库建立和环境基因组研究等方面，同样具有重要的研究意义和价值【341。随着人类基因组 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 (HumanProjeet,HGP)的DNA测序工作的完阵列技术对肿瘤的及其亚型的预测和诊断，构建基因关系调控网络，意义将十分基因芯片属于生物芯片，其概念于1993年由Fodor等【5】提出，也被称为DNA芯片、DNA微阵列技术或寡核苷酸芯片等。基因芯片主要是利用两个互补DNA分子杂交信号对碱基对之间的互补杂交性进行监测，从而获得待测生物样本的基因表达丰度，也可简单解释为序列特异性核酸的杂交。DNA芯片的特异性和敏感性很强，可同时监测成千上万个mRNA拷贝的转录情况，实现对生物样本的高效、快速和并行的分析与检测。DNA芯片从其制备方法上主要有两种，一是点样法，这种方法较简单，且技术环节成熟，可以用于制备一些点阵规模一般的DNA芯片：二是光导向平板印刷技术，这种方法工艺先进，如根据组合化学原根据功能划分，主要有美国Affymetrix公司研制的寡核苷酸微阵列、Stanford大学研制的eDNA微阵列以及其他生物传感芯片等。根据制作方法划分，主要有液相型、原位合成型和预合成型微阵列等。根据载体材料划分，主要有玻璃芯片、硅芯片和膜芯片等。根据市场划分，主要有研究型和临床型微阵列。时分析重要基因的功能以及互相之间的调控关系，确定相应的基因网络和调控区成，使得对肿瘤的产生和发展机理在分子水平上的观测成为可能，运用DNA微深远。理对DNA位点进行安排，使芯片在反应后比较容易寻址。安徽大学硕二仁学位论文肿瘤基因表达谱数据聚类的谱方法研究Genomic■，■■，眦，。卜∞儿，：■|一c1．2．2数据获取1．2．3数据特点基因表达谱数据集的获取是一个非常复杂的过程，图1．1(a)为一次DNA芯片实验的全过程，其主要分为以下几步：1：制备DNA芯片。其制备方法主要有点样法和光导向平板印刷技术两种，可以在玻璃片、硅片或尼龙膜上依照一定的排序方式固定上万个探针，形成2：制备荧光标记探针。通常将红色荧光(Cye5)和绿色荧光(Cye3)分别标记为实验样本和对照样本。3：将芯片与标记探针杂交。同时，还要将未结合的探针洗去，并对荧4：扫描杂交芯片。用一定波长的激光激发杂交芯片，使探针发出波长各不相同的荧光，扫描后可得到图像Cye3及Cye5，叠加后就可以得到杂交图像。图1．1(b)就是一幅杂交图像。DNA芯片。光信号进行扫描和分析。5：从杂交图像中提取基因表达谱数据。(a)(b)图l一1DNA芯片实验过程和生成的杂交图像安徽火学硕：J：学位论文第一章绪论StepomputerFig．1—1ExperimentalprocessofDNAchipandgeneratedhybridimage1．3本文研究内容及组织结构DNA芯片的应用与研究方向随着DNA芯片技术的发展，使得基因表达谱数据的获取变的容易，但在数据的处理和分析过程中仍然存在着很多问题。首先，数据在获取过程中常会出现一些误差，如荧光基团性能的差异和灰尘造成的玻片表面的不均匀造成的误差等，因此，数据中存在噪声和异常表达值是难免的；其次，数据的庞大规模使得很多算法的效率较低，从而需要 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 复杂度较低的有效算法；另外，数据的非线性特点也显现出传统线性方法的局限性，如何设计有效的非线性方法对数据进行处理也是一个重点问题；最后，DNA微阵列数据的最显著特点是高维小样本，一般肿瘤相关基因只有几十个，而原始数据中存在着很多冗余基因，因此，问题的关键就在于如何从肿瘤数据中提取出数据的特征属性或信息基因集合以达到降维的目的。DNA芯片技术是临床诊断和生物信息学研究的基本工具，在DNA序列分析、疾病分型及诊断、药物研究和大型分析仪器的产生等方面得到了广泛应用，另外在基因识别、分型、诊断和突变确认等方面也显示出其重要的价值，尤其是基因诊断，已成为基因芯片最有商业价值的应用。目前，DNA芯片技术的研究主要可分为以下几点：(1)基因表达时空特征的分析；(2)差异表达基因的检测；(3)新基因的发现；(4)大规模的DNA测序；(5)疾病诊断和治疗；(6)药物研究；(7)DNA计算机的应用。DNA芯片技术在上述各个方面都有着广泛的应用价值，相信随着技术的发展与完善，必将为人类本文基于谱图理论，对基因表达谱数据进行了研究。通过构图的方法对肿瘤数据进行有效的降维，实现无结构信息的数字序列到具有结构信息的图结构的转变，同时获取肿瘤样本的图结构的特征表示，并基于图论中的相关聚类和半监督聚类算法，为划分肿瘤类型及发现肿瘤相关基因提供了新的可行途径。对算法和实验结果的分析说明本文方法具有如下优点：(1)构图可使数据有效的降维，避免了维数灾难问题；(2)图结构的特征表示和其他图的不变量，有助于更加有效带来巨大的经济和社会效益。1．2．4安徽大学硕士学位论文肿瘤基因表达谱数据聚类的谱方法研究的对肿瘤类型进行判断；(3)鲁棒性较好。本章简单介绍了研究背景与意义，DNA芯片的基本概念、应用范围及相应的研究方向，基因表达谱数据的获取过程和数据的主要特点等。本章首先介绍了基因芯片数据的误差来源和预处理方法，其次分析了传统基因表达谱分析中的相关特征提取、信息基因选取方法以及常用的分类聚类方法，最后简要介绍了基于图论的基因表达谱分析的研究现状。第三章基于改进谱聚类的基因表达谱数据分析本章提出一种改进的谱聚类方法。通过对基因表达谱数据构造概率矩阵，经奇异值分解(SVD)后提取前k个特征向量，并以此作为肿瘤样本的特征表示，运用模糊C均值(FCM)对样本进行聚类分析。实验结果证明了该方法的有效性。第四章基于谱隙和单位特征向量的谱聚类方法本章提出一种基于谱隙和单位特征向量的谱聚类方法。首先，以肿瘤样本为图的节点构造Laplacian矩阵；然后，计算Laplacian矩阵的特征值和相应的特征向量，并利用谱隙序列的最大值确定该方法的聚类个数；最后，选取相同个数的特征向量作为原始样本的特征表示，并从单位化特征向量着手，以实现样本的聚类。通过模拟数据与癌症数据的实验，证明了该方法的有效性。第五章基于Gauss—Seidel迭代的标记传播算法本章提出一种基于Gauss．Seidel迭代的标记传播算法，并将其应用于基因表达谱数据分析中。首先将高维基因表达谱数据表示为权值矩阵，同时定义一个表示样本类别属性的标记序列，并将其中少量样本标记为已知；然后利用根据Gauss．Seidel迭代算法推导出的迭代公式更新标记序列，并证明了标记序列的解的收敛性；最后采用正负标记的方式，根据标记序列各分量的符号差异实现数据类别的划分。通过白血病和结肠癌数据集的实验，证明了该方法的有效性。本章总结了本文研究内容，同时指出了其中的不足之处，对未来需要解决的本文组织结构如下：第一章绪论第二章基因表达谱数据分析基础第六章总结与展望问题和相关工作进行了展望。安徽大学硕士学位论文第二章基因表达谱数据分析基础2．1基因表达谱数据的数学描述2．2基因表达谱数据集探索和改进DNA微阵列数据的处理方法，对基因表达谱数据进行深入的挖掘与分析，从而得到与生物学相关的潜在信息，是基因表达谱数据分析的最重要内容。肿瘤样本集经过特征提取或基因选择后，可以带来许多潜在的优点，包括改善分类模型的识别准确率、删除冗余信息和特征、简化分类模型、缩短分类器学习与训练时间、降低测量成本、改善参数估计的可靠性、提高分类模型的运行速度和获取肿瘤样本集的知识等。设{曲，92，⋯，gm)表示使用DNA芯片进行一次测量后得到的所有基因构成的表达值集合，其中gj(1≤，≤m)为一个基因，m表示基因个数；设{xl，X2，⋯，Xn)表示使用DNA芯片进行多次测量后得到的所有样本构成的集合，其中而(1≤f≤咒)表示在同一条件下所有基因的表达值，甩表示样本个数，由所有样本构成的基因表达谱矩阵G可用下式表示其中，岛表示基因毋在样本而中的表达水平。1999年，Golub等利用急性白血病的基因表达谱数据集实现了肿瘤亚型的分类，并由此开启了基于基因表达谱的肿瘤分子诊断。随后，大量的基因表达谱数据集被公布到网上，表2-1列出了几种常见的基因表达谱数据集。(2—1)鼠，＆；岛g!⋯安徽大学硕士学位论文g、gmG=gl，1gl，292，I92，2gn，1gn，2而％6一：●■mRNA样本备份阴织类型爪试剂盒等因素裟感度胍晰造成的样翮光信号的非线性传递、饱和效应繁要箩成的图像分析差异以及图像分割2．3基因表达谱数据的预处理在基因表达谱数据的获取过程中，不可避免的会出现人为失误和实验系统误差，如由于不同荧光基因具有不同的标记能力所造成的系统误差等。除此之外，还有很多系统误差来源，表2—2总结了常见的误差来源。为了使不同通道的基因具有相似的表达水平，同时也由于基因表达谱数据的复杂性，在对肿瘤数据分析前进行一定的预处理是必须的，其预处理过程主要包括丢失数据的修补、异常数据的修正和数据的转换等。表2．1几种常见的基因表达谱数据集表2-2DNA微阵列数据常见的误差来源误差来源说明荧光标记荧光基因性能的差异PCR扩槽温度、时间、缓冲液等对杂交反应后的影响探针性能探针的组成、长度、固定性能及基因的表面性能载玻片的性能灰尘、划痕等因素造成的玻片表面的不均匀性背景噪声近邻点信号和背景信号平均强度的差异所引起的非特异性信号图像处理安徽大学硕士学位论文肿瘤基因表达谱数据聚类的谱方法研究commonmicroarrayTable2一lSeveralgeneexpressionprofiledatasetS2-2Thec：‘)mmonofDNAdata7errorSOUI'ceS2．4传统基因表达谱分析方法2．4．1特征提取与选择在基因表达谱数据中，芯片图像的损坏、芯片上的划痕、灰尘、样本被污染低信号强度、荧光信号过弱以及图像的分辨率不够等都有可能造成数据的丢失，从而导致很多方法无法正常应用，如PCA[6]和K均值[71等。将丢失的数据置零或以平均值替代是最简单的数据修补方法，但这种方法的缺点很明显，如缺失的基因易被错误聚类等。Bo等【8】利用最小二乘法(LeastSquares，LS)原理和矩阵与基因的相关性相结合的方法来估计数据的缺失值；杨涛等【91提出了基于马氏距离的填充算法应用于数据中缺失值的估计；Oba等【10】提出了一种基于贝叶斯定理的主成分分析(BPCA)来估计DNA微阵列数据中的缺失值。异常数据是指那些偏离群体分布的数据，包括单个DNA芯片的异常和单个DNA芯片上的某个基因点的表达异常。异常指的是同一种芯片的某一些由于出现较大的变异性而无法正常使用。通常，DNA芯片上的最大值和最小值会被作为异常数据修正，也可通过设置阈值的方式来剔除异常数据。数据的转换是为了调整由基因芯片引起的误差，使数据转变为利用分析的形式，通常可 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 化数据到一定的区间或构造新的数据形式，具体包括对数转换、均值中心化、中值中心化和数据归一化等。这些方法的目的都是为了提高数据的精确性，便于进一步进行数据挖掘，但也都有着一定的前提和假设，因此也存在基于基因表达谱的特征提取与选择方法和技术的基本任务就是从基因表达谱数据中提取样本的特征，并从众多特征中选择出那些对分类识别最有效的特征，从而降低特征空间的维数。当选取了样本的分类特征后，就能建立相应的聚类或分类模型，对肿瘤样本进行划分识别。特征提取是在保持原基因空间不变的条件下，通过对原基因空间进行某种形尽可能强的综合属性作为全部基因的代表。典型的应用于DNA芯片数据的特征提取方法包括主成分分析(PCA)‘61、偏最小二乘(PLS)‘111、最大边缘准则(MMC)‘12】相应的不足之处。式的变换，寻找新的特征属性空间的过程，目的是提取尽可能少的并且分类能力安徽大学硕士学位论文第二章基因表达谱数据分析基础(LE)【16】、局部线性嵌入(LLE)【171和Riemman艄>--J(RML)[181等。这些方法在处和独立分量分析(ICA)【13】等。上述方法在肿瘤分类中均取得了一定的效果，但它们都是线性特征提取方法，而非线性分布的数据在线性空间可能是不可分的，当这些方法应用于非线性结构的基因表达谱数据时，其可行性有待迸一步研究。近年来，许多非线性特征提取方法被陆续提出。基于非线性分布的数据在非线性空问是可分的认识，人们常常引进一种核模式，如核PCA[14】等，其在保持数据的非线性结构的同时，可以很好的提高数据的可分性能。另一方面，流形学>-j【15．181也属于非线性方法，如等规度映射OSOMAP)[151、Laplacian特征映射理具有高维非线性结构特点的数据时，不仅可以保留数据局部结构的特点，并且能有效地发现数据的本质维数。经过特征提取所获得的新的特征空间与原始空间具有较大的差别，但其关键在于可以间接反映原始样本信息。采用特征提取方法能够大幅度地降低数据维数而保持较高的分类准确率，但是对于肿瘤模式分类问题而言，信息基因的选取仍是一个必须完成的关键任务，它通过在原始数据中选取分类性能较好的基因来降低数据的维数，同时保证数据的可靠性。信息基因选取的方法主要分为过滤法、缠绕法、混合法、嵌入法和集成法等。过滤法是最简单的基因选取方法，它将特征选择和分类的过程分开，对单个特征进行 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 ，如信噪比【19】、相关系数口01、信息增益【2l】、卜检验瞄1和EnrichmentScore[231等。对于那些基于单个特征的特征选择算法，由于仅考虑单独一个特征，没有将特征间的互相依赖关系考虑进去，为此，李颖新等124]基于Relief算法选取特征基因，然而该算法包含一个复杂的特征评价过程。上述方法都是基于单变量的方法，并不考虑不同基因之间的互相关系。最近，出现了很多基于多变量的方法，如Lee等口51提出的基于Bayes变量的方法、Bae等126]提出的基于双层Bayes模型的多变量方法和Chris等提出的MRMR法等。缠绕法是将特征选择过程与分类过程相结合，利用分类算法来评价特征集合的性能，主要包括：(1)基于分类器反馈的方法，如基于贝叶斯【271、支持向量机(SVM)【28】、K近邻(KNN)【29】和PKLRl301等分类器的Wrapper方法。Wang等1311比较和讨论了基于决策树、Bayes分类器和SVM等三种分类的Wrapper方法，这些方法主要都是结合特定的分类器并根据分类的学习算法特点而设计的。(2)基安徽大学硕二l二学位论文肿瘤基因表达谱数据聚类的谱方法研究9化的方法；混合法，Tan等阳采用三种不同的方法对基因进行排序后，选取相应2．4．2分类与聚类Algorith)M算法、HGSOT(Hierarchical于启发式搜索的方法，如顺序前进法(sFS)【321、遗传算法(GA)【331和蚁群算法(1380)[34]等，这些算法在基因表达谱分析中也得到了广泛应用。当使用不同的分类器时，Wrapper方法可以筛选出适合该分类器的基因特征。另外，还有很多常用的信息基因选取方法：嵌入法，Ghosh等【35】的基于正则的信息基因子集，再在子集中用遗传算法进行搜索；集成法，如Bagging[371和Boosting[381方法等，Li等‘391提出的基于集成策略的信息基因选取方法也是其中的分类是在已知某些样本类别的情况下，通过建立相应的分类模型，对未知类别的样本进行划分和识别，属于有监督方法。分类算法可分为一下两种：(1)Lazy算法，如K近邻【29，4叫和基于案例的推理(Case．Based都是从局部出发，在新的测试样本出现之前，并不断对训练样本进行归纳；(2)Eager算法，如决策树口1’42】、SVMl28,431和BP神经网络1431等，都是从全局出发，由训练样本对目标函数进行归纳，直到新的测试样本出现。聚类是在完全不知道样本类别的情况下，依靠样本的本质属性对样本进行划分和识别，属于无监督方法。常见的聚类方法有K均值【71、模糊C均值(FCM)m】和层次聚类(HC)【45-461等。K均值将r／个实体划分为k个类，把类别均值作为各个类的中心，通过类中心与样本的距离来更新类中心，并判断样本的类别。K均值需要事先确定类别数k，且存在鲁棒性差和分类结果不确定等缺点。FCM与K均值是类似的。层次聚类可分为层次凝聚聚类(HAC)mJ和层次分裂聚类顺序的影响等。为了克服这些问题，一些新的层次聚类方法被陆续提出，如Gro丽ngTree)‘48】算法和DGSOT(Dynamical1501。虽然上述方法在基因表达谱数据的分类识别上已有了一定的成果，但仍然一种。Reasoning)1411等，这些方法(HDC)[461，但这些算法都存在某些缺点，如解不唯一、缺乏鲁棒性和受数据输入SOTA(Self-OrganizingTree)[49】算法等。另外，半监督方法在基因表达谱数据的聚类或分类也已经得到了广泛的应用Self-Organizing安徽大学硕士学位论文第二章基因表达谱数据分析基础TeeGrowing102．5基于图论的基因表达谱分析基于图划分理论的基因表达谱数据分析陋531，王年等‘521利用基因表达谱数存在许多难题需要解决，如数据中的噪声问题、维数灾难问题和肿瘤相关基因的定位问题等。近年来，基于图论的基因表达谱数据分析方法得到了广泛发展，利用谱图理论可以获取图的特征表示，应用这些特征来刻画图的拓扑结构性质。考虑到单个样本的基因数据由一个庞大的数字序列构成，将这个数字序列看作一个高维向量，则一个样本即为高维空间中的一个点。如果使用传统的肿瘤识别方法来处理高维空间中的样本点，维数灾难等问题依旧存在。根据初步研究，由基因表达谱数据构成的空间点集，具有不同的空间分布与结构，而图结构可以较好地显示出其空间结构的差异。针对这些高维数据，基于图的方法只需对高维空间中的点进行简单的构图运算，使得运算复杂度大大降低。基于谱学习的基因表达谱数据分析【511，提取基因表达谱数据中的“棋盘模式”，在具有棋盘结构的基因表达谱矩阵中同时从基因和样本两个方向上寻找具有特殊表达模式的特征向量；利用基因表达谱数据构造加权图，并通过优化原始谱聚类算法的目标函数，得到一种全新的谱聚类方法，以实现基因表达谱数据的聚类。Fiedler向量分量的符号差异来进行基因表达谱数据的分类；Xu等【53】提出基于最小生成树(1订ST)的基因表达谱数据聚类方法，将高维基因表达谱数据用最小生成树表示，而MST的一个子树就代表基因表达谱数据的一个子类，利用MST来表示高维基因表达谱数据具有以下两点优势：MST的简单结构有利于实现复杂的聚类问题；基于MST的聚类问题不依赖于子类的几何形状。以谱图理论为基础【541，利用基因表达谱数据构造新的数据模型GEG(GeneGraphs)，该模型占用的计算机内存只取决于构建模型所用的样本个数，通过该模型可以更好地反映出健结合基因本体论和具有统计意义的数值计算方法【551，并利用图的拓扑特性据构造Laplacian矩阵，经SVD分解后获得Fiedler向量，利用各样本所对应的Graphs)和DGEG(Differential康样本和病变样本中肿瘤相关基因和无关基因之间的区别与联系。安徽大学硕士学位论文肿瘤基因表达谱数据聚类的谱方法研究ExpressionGene2．6本章小结来提高功能基因组的得分，消除功能基因组对相关区域近邻点的局部依赖性，确定相关生物学过程和功能。聚类或分类方法已被广泛应用于肿瘤和疾病研究，传统的基因表达谱数据分析方法主要是对基因数据进行信息基因选取或特征属性提取后，再用相应的分类或聚类方法对样本进行识别，但由于基因表达数据的高维特性，使得许多算法面临运算效率较低的问题，基于图论的方法是将基因表达数据的样本视为高维空间中的点，其低样本特性决定了构造的矩阵规模较小，从而具有较低的运算复杂度。安徽大学硕士学位论文第二章基因表达谱数据分析基础陟。={P孚；三乡z，／=，，2，⋯，，z第三章基于改进谱聚类的基因表达谱数据分析其中，D为度矩阵，且满足域=∑七％，Dj，表示与节点薯连接的所有节点的边3．1基因表达谱数据的Laplacian矩阵表示3．2谱聚类研究热点，此类算法主要有最小生成树‘531，图传导嗣和谱聚类‘57铘1等。其中，边集。设节点‘和‘之间的边权值为％，该文所选择的亲近度量为：其中：乃表示节点薯和■之间的欧氏距离，盯为权重参数。显然，对于任意的‘，_和盯，有o≤％≤1，反映了节点玉和一之间的亲近程度，％越大，则节点构造赋权图G(V，E)，其中V为待聚类的样本集，E=VxV表示节点之间的节点jcf和x，就越有可能属于同一类。规范Laplacian矩阵的定义如下：c3一-，安徽大学硕士学位论文第三章基于改进谱聚类的基因表达谱数据分析弓2』∑kM=lLwik假设M个样本(_，j=l，2，⋯，M)被分为c个模糊类，且每个给定样本能够用3．3改进的谱聚类算法3．3．1概率转移矩阵图像分割【561和形状检索㈣等。概率转移矩阵的定义如下：3．3．2模糊C均值谱聚类的基本思想是根据给定的数据集构造Laplacian矩阵三，计算矩阵￡的特征值和特征向量，然后选择合适的特征向量聚类不同的数据点。Ng等A[571通过选取对称形式的规范Laplacian矩阵的前k个最大特征值对应的特征向量，将原始数据映射到R‘空间，对R‘空间中的数据点使用k均值或其它稳定的聚类算法。谱聚类的主要步骤如下：Step2：求矩阵三的前k个特征向量，将原始样本数据映射到R‘空间；3：对R‘空间中的数据点使用k均值或其它稳定的聚类算法，划分为k个簇。谱聚类方法中，节点间亲近度量的选择是重要的一步，而Meila和Shit581将亲近程度解释为Markov链中的随机游动，分析了这种随机游动概率转移矩阵(又称概率矩阵)的特征向量；之后，概率转移矩阵又被应用于许多不同的场合，如可以发现，概率矩阵P的行和为1。根据马尔科夫随机游走理论，这里的随机节点序列(K，t=l，2，⋯，门)是一个马尔科夫链，假设i是一个已标记的节点，那么B就表示从节点f到节点，的单步转移概率。因此，P比形更能反映节点之间的亲近程度。值在[O，l】间的隶属度去确定其属于各个类的程度，隶属度矩阵U的定义如下：1：由原始数据构造亲近矩阵∥，并构造Laplacian矩阵L；i,j=1,2,---,n(3-3)安徽大学硕士学位论文肿瘤基因表达谱数据聚类的谱方法研究Step14圹酊1㈦，2，⋯川-1，2’⋯∥其中，嘞=忙--Vin2。万一z3：根据式(3-6)计算代价函数。如果它满足”‘一J川忙丁，则停止迭代，I，‘其中，％∈[o，1】为第／个样本属于第f个类的隶属度，矩阵u描述的是一种模糊关∑％=lJ(v，H，⋯，心)=∑∑％m％2∑《_M=号厂一扛l，2，⋯，C∑”孑1：设定聚类个数c，初始化式(3-4)，使其满足式(3．5)和‰∈【o，11,3．3．3算法步骤系，其约束条件如下：j=l，2，⋯，M式(3．5)表示每个样本属于各个类的隶属度之和为1。通过不断优化矩阵U，就能得到更为准确的聚类结果，代价函数如下：V。表示类f的中心，m为权重指数。上述优化问题可以通过不断更新类中心u和隶属度‰来解决，迭代公式如下所示：2：用式(3．7)计算聚类中心Ⅵ；4：根据式(3．8)计算新的隶属度矩阵U，返回Step(3-4)(3-5)(3-6)(3—7)(3-8)⋯”2Mi=1，2，⋯，cl，，⋯，安徽大学硕士学位论文第三章基于改进谱聚类的基因表达谱数据分析U=VStep2。H2H22M2／=l1i=lC^，j=lstep4埔斛肭衲猷妫靴幄确到腓川噶2寿；3：计算矩阵P的前后个特征向量葺，⋯，xk，记为X=【五，⋯，xk】；3．4实验结果与分析本章算法步骤如下：l：构造赋权图G(V，E)，V为基因表达谱样本节点的集合，节点的边的集合；2：利用式(3．3)构造概率矩阵P；5：将矩阵y的一行作为基因表达谱数据中一个样本的特征表示，使用FCM确定c个聚类。本实验选用两组肿瘤数据集，即白血病数据(Leukemia)和结肠癌数据(ColonCancer)，其具体描述见2．2节。由于数据获取过程中仪器的误差和人为失误等，使得数据中含有较多噪声及异常表达值，同时基因表达谱数据存在很多与样本类数据进行筛选：其中，max(i)，min(i)和mean(i)分别为第i个基因在所有样本中表达值的最大值、最小值及平均值，T为给定的阈值。如果某个基因的表达情况符合式(3．9)实验l：对白血病两个亚型(ALL和AML)进行了实验，结果如图3-l和图E为连接别无关的冗余基因。因此，对数据进行预处理是必要的，定义下式对基因表达谱(3-9)便将该基因剔除。3．2所示：安徽大学硕士学位论文肿瘤基因表达谱数据聚类的谱方法研究Step16卜、，』＼-^_雾蚤硷妇图3．1为该方法的聚类准确率随提取的特征向量的维数k的变化。由图3．1可知，该方法在k=2，4时，获取最高准确率，达到了98．08％；并且，随着维数k的增加，聚类准确率并没有明显的降低，说明该方法具有一定的鲁棒性。图3．2为维数k=2时的散点图。由图3．2可知，该方法将两类样本很好的划分开来，聚类效果非常明显，只有一个样本被错分。实验2：对结肠癌数据设计了一组对比实验，将该方法与阮晓刚等【删的S2N方法和Sin曲D【401等的S2NKNN方法进行对比，在内存2G，酷褂器蛄图3．1白血病数据准确率随k的变化零m图3-2自血病数据提取二维特征向量安徽大学硕士学位论文第三章基于改进谱聚类的基因表达谱数据分析Fig．3一lkbydata《^砒国(CLUSTERResultswithusingLeukemiad⋯1Fig．3—22Dfigureofe，、Omisclass币cation薯《o，、^o3．5本章小结睿双核2．60GHz的计算机上运行本实验的结果如表3．1所示：由表3一l可知，本章方法的结肠癌聚类准确率达到了91．94％，显然优于另外两种传统的方法；而在时间效率上，本章方法仅用时0．348秒，而KNN方法分别耗时41．97秒和6．52秒，同样优于后两种方法。基于DNA微阵列技术的聚类研究是当前生物信息学领域的研究热点。本章将概率矩阵分解和FCM方法应用于基因表达谱聚类中，实验证明，本章方法具有较高的准确率，且运算时间较传统方法也有了很大的提高。但该方法前期的基因筛选对结果的影响是比较大的，因此，本章方法的鲁棒性还有待改进。S2N方法和S2N肿瘤基因表达谱数据聚类的谱方法研究表3．1实验结果对比安徽大学硕士学位论文CLUSTERTable3-1Comparisonofexperimentresults第四章基于谱隙和单位特征向量的谱聚类算法彳=k，X2，⋯，坼)=旧，口：T，⋯，《y】，=河，掰，⋯，群厂，那么以屈作为Rk空间中的样本所形成的克个聚类是彼此正4．1谱隙确定类别个数应的谱隙序列{81，嚷，⋯，瓯一。I点=五一丑+。)。Ng等A[5n指出：对于七个彼此分离的传统的谱聚类方法大多是通过先验知识来确定聚类个数，这大大影响了聚类的准确性和灵敏性，已有的自动确定聚类个数的谱聚类算法有：基于Rcut的谱聚类‘611、基于距离的启发式算法[621和多层高度平行谱聚类‘631等。这些算法在一定程度上解决了聚类个数的问题，但在一些实际数据中得到的聚类个数和聚类结果都不够理想。针对传统谱聚类方法存在的问题，本章提出一种基于谱隙和单位特征向量的谱聚类方法，利用谱隙序列的最大值确定该方法的聚类个数，并且在新的特征空间中不再引入其他聚类算法，而是直接从单位化的特征向量着手实现本章从矩阵谱隙的角度来确定聚类个数。设丑≥五≥⋯≥以是规范Laplaeian矩阵三的特征值，相邻特征值的差值就称为谱隙(eigengap)，记为万，可以得到相理想数据样本，可以证明三的前k个最大特征值为1，而第k+1个特征值严格小于1，即五。=⋯=五。=1，兄。+。<1，且五+，和相应的谱隙坑的大小取决于这七个聚类的分布情况，当这七个聚类的分离度越大，五+。的值就越小，瓯的值也就越设而，x2，⋯，Xk是Laplaeian矩阵三的前k个最大特征值对应的特征向量，构造矩阵X如下：其中，％是X的第f个行向量。将矩阵X的行向量规范化为单位长度，得到矩阵交的，且分布在R‘空间中的单位球上，同时对应了原始空间中所有样本形成的k样本的聚类。大。(4．1)安徽大学硕士学位论文第四章基于谱隙和单位特征向量的谱聚类算法19’4．2基于单位特征向量的数据类别划分4．3基于谱隙和单位特征向量的谱聚类算法七=argmax溉=以一五+。Ii=l，2，⋯，门一1}相应的样本点，Q(f，／)=l表示f，J两个样本属于同一类别，Q(／，／)=o表示f，J两个样本属于不同类别。一般情形下，若样本f，J同类，则Q(f，，)的值接近于l，若样本f，J不同类，则Q(f，／)的值接近于o。5：取三的前七个特征向量五，X2，⋯，砟，构造矩阵x=k，X2，⋯，‰)；个聚类。对于一般分布的数据，样本的类别数k与谱隙同样有紧密的联系，当样本类内分布越紧密，类间分布越分离时，相应的最大谱隙值瓯就越大，同时前k个特征值对应的特征向量形成的特征子空间也就越稳定，因此可以在谱隙序列中寻找最大值，该值对应的下标就是所求的聚类个数，聚类个数k可以用下式来确定：确定聚类个数后，本章直接从单位特征向量着手实现数据类别的划分。利用矩阵三的前k个单位特征向量构成的矩阵】，，构造新的矩阵Q=YYr，上文提到，理想情形下，以】，矩阵的每行作为R‘空间中的样本所形成的k个聚类是彼此正交的，且分布在尺‘空间中的单位球上，因此可以根据Q中的元素聚类不论是基于何种理论的谱聚类算法，最后都是转化为求Laplacian矩阵的特征值和特征向量的问题，本章算法的主要步骤总结如下：l：根据给定的待聚类的样本集构造赋权图G(V，E)，利用式(3—1)的相似性度量构造相似矩阵W；2：利用式(3．2)构造规范Laplacian矩阵L；3：计算三的特征值^≥五≥⋯≥五和相应的特征向量而，x：，⋯，矗；(4．2)4：按式(4—2)计算聚类个数k：安徽大学硕士学位论文肿瘤基因表达谱数据聚类的谱方法研究Step20咖6漕斛肭砷戥黼靴舱埔到肼Ⅲ喁2寿；尸(f，．，)={≥耋g：；；三三篓‘／=，，2，⋯，甩#．繁毒。|：4．4实验结果与分析e(i，／)=o就将f，jf两个样本归为不同的类。_弋等主4．4．1模拟数据实验7：构造矩阵O=YY71，选取阈值flag，令根据P中元素的值进行聚类，如果P(i，，)=1就将f，歹两个样本归为一类，如果首先在模拟数据上进行了实验，构造一组分离度比较大的理想点集，图4．1为模拟数据分布，图4．2为在模拟数据上使用本章算法的聚类结果。由图4．2可知，待分类点集被准确地划分为三类。+毒+．笙。抖¨图4．1模拟数据分布安徽大学硕士学位论文第四章基于谱隙和单位特征向量的谱聚类算法Step◆～～气。．毒Fig．4—1Simulationdatadistribution2l+●：+’鼍黎鸯?％喵垂。哎。图4-3为模拟数据的特征值序列，由图4．3可知，将Laplacian矩阵￡的特征值按从大到小的顺序排列后，三的前4个特征值为：因此，在理想情况下，Laplacian矩阵的特征值l的重数即为原始数据的类别数。图4—4为模拟数据的谱隙序列，由图4．4可知，最大谱隙值以出现在第一