聚类的分析应用.pdf

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