文档介绍：电子科技大学
博士学位论文
聚类分析及其应用研究
姓名:唐东明
申请学位级别:博士
专业:计算机应用技术
指导教师:朱清新
20100301
摘要
摘要
模式识别,也被称为分类或者是统计分类,模式识别学科的研究目的就是为了构建能够自动判别输入数据类别信息的分类系统。聚类分析是一种无监督的模式识别方法,是模式识别研究中的一个重要领域。无监督的聚类分析算法能够探索输入数据的内部群组结构,目前已经被广泛应用于各种数据分析场合,包括计算机视觉分析,统计分析,图像处理,医疗信息处理,生物科学,社会科学和心理科学等。聚樊分析的慕本原理就是将输入数据分成不间的群组,同一组中的成员拥有相似的特性,相反不同组中的成员特性相鼻。
本文主要针对聚类分析算法及其应用进行研究,本文研究的聚类分析算法主要应用于生物信息学数据分析,大规模选址问题,数据不规则形状分布聚类分析问题。主要的工作和取得的成果概括如下:
(1)基因表达序列分析技术(Seria1 Analysis of gene expression ,SAG巴)是一种快速详细的分析数以千计转录(甘 anscrip臼)的最佳方法,这项技术最开始由 Victor Velculescu 博士于 1995 年提出。聚类分析算法是一种非常有用的 SAGE 数据分析方法,被用于发现 SAGE 数据集中潜在的新的或隐含的转录或者是基因组, 因此已经被用于分析 SAGE 数据。尽管研究人员已经给出了多种用于 SAGE 数据分析的聚类分析算法,但是这些算法通常都需要结合一些用户自己设定的参数, 并且聚类分析的结果对参数选择有很强的依赖性。本文基于 SAGE 数据的 Poisson 统计特性和最近提出的仿射消息传播聚类分析算法提出一种自适应的聚类分析算法,在该算法中引入了一个聚类结果校验测度,并以该测度为代价函数对聚类结果进行优化调整以获得优化的聚类结果,该算法被命名为 PoissonAPS。在多个实际生命数据集上的对比实验结果表明本文给出的方法能够对 SAGE 数据进行很好的聚类分析,并且产生有意义的可解释的分类结果。
(2)随着高通量测序技术的发展,目前在生物信息数据库中已经累积了大蠢的蛋白质序列数据。但是由于实验确定蛋白质序列功能的速度无法赶上新序列测序的速度,因此造成大量的新测序的蛋白质序列尚未通过实验的方式来确定它们的生物功能和家族倩息。由于实验验证过程非常耗时并且昂贵,因此理想情况下希望仅仅依赖序列之间的相似性来探测未知功能序列和己知功能序列之间的同源关系,进而确定未知功能序列的信息。聚类分析方法能够通过将蛋白质序列分类
摘要
到不同的蛋白质家族获得有意义的信息。最近几年研究人员已经提出了多种用于蛋白质序列分析的聚类算法。面对众多的蛋白质序列聚类分析算法,有必要进行一个对比研究分析,分析的结果将有利于生命科学研究人员考察不同的算法并且选择合适的用于特定实验分析场合的算法。本文比较了四种典型的蛋白质序列分析算法,在多个数据集上考察算法的以下几方面的性能:缺省参数条件下的聚类算法性能分析:算法对蛋白质序列在数据集中所处位置是否敏感:数据集自身的真实类分布对聚类算法结果的影响;调节算法的参数,观察参数对聚类结果的影响。本文给出的实验结果能够帮助研究人员选择合适的分析算法。并且实验结果还表明蛋白质序列聚类分析算法还有很大的改进空间。
(3)随着大量的未知功能的蛋白质序列数据的累积,目前已经无法通过实验的手段来标注米知功能的蛋白质序列。聚类分析方法通过将蛋白质序列分类到不同的同源组来确定米知功能的蛋白质序列的倍息。本文引入了一种用于大数据最蛋白质序列分析的无比对的在线聚类分析方法,命名为 OnlineCAPS 0 该方浩具有速度快,可在有限内存环境下运行等优点,此外该方法还可以被部署在 WEB 服务
器上。实验结果表明该方法能够快速的分析大数据量的蛋白质序列,并且获得的
聚类结果的质量接近于其它算法。
(4) 选址布局问题是一个广泛研究的运筹学问题。通过将选址布局问题看作聚类问题,结合聚类分析算法并且将候选地址的信息映射为特征向盘,本文提出了两种求解选址布周问题的方法:基于块划分的选址布局方法:基于道路网络的选址布局方法。文中使用模拟数据集和真实数据集来评估这两种方法,实验结果表明两种方法都能够求解设施资源受限和不受限情况下的选址布局问题,而且可以很好的解决大规模的选址布周问题。
(5) 探测数据不规则形状分布的自然类簇分布是模式识别研究领域的一个困难的任务。本文给出了一种有效的数据不规则形状分布聚类分析算法,该算法结合了谱聚类和仿射消息传播聚类算法的优点,能够很好的分析数据不规则形状分布的类簇结构。与此同时,文中给出了一种新的基于邻居离散分析的相似度测度。本文给出的方法简单